1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7#include "PathOpsTestCommon.h"
8#include "SkPathOpsBounds.h"
9#include "SkPathOpsConic.h"
10#include "SkPathOpsCubic.h"
11#include "SkPathOpsLine.h"
12#include "SkPathOpsQuad.h"
13#include "SkReduceOrder.h"
14#include "SkTSort.h"
15
16static double calc_t_div(const SkDCubic& cubic, double precision, double start) {
17    const double adjust = sqrt(3.) / 36;
18    SkDCubic sub;
19    const SkDCubic* cPtr;
20    if (start == 0) {
21        cPtr = &cubic;
22    } else {
23        // OPTIMIZE: special-case half-split ?
24        sub = cubic.subDivide(start, 1);
25        cPtr = ⊂
26    }
27    const SkDCubic& c = *cPtr;
28    double dx = c[3].fX - 3 * (c[2].fX - c[1].fX) - c[0].fX;
29    double dy = c[3].fY - 3 * (c[2].fY - c[1].fY) - c[0].fY;
30    double dist = sqrt(dx * dx + dy * dy);
31    double tDiv3 = precision / (adjust * dist);
32    double t = SkDCubeRoot(tDiv3);
33    if (start > 0) {
34        t = start + (1 - start) * t;
35    }
36    return t;
37}
38
39static bool add_simple_ts(const SkDCubic& cubic, double precision, SkTArray<double, true>* ts) {
40    double tDiv = calc_t_div(cubic, precision, 0);
41    if (tDiv >= 1) {
42        return true;
43    }
44    if (tDiv >= 0.5) {
45        ts->push_back(0.5);
46        return true;
47    }
48    return false;
49}
50
51static void addTs(const SkDCubic& cubic, double precision, double start, double end,
52        SkTArray<double, true>* ts) {
53    double tDiv = calc_t_div(cubic, precision, 0);
54    double parts = ceil(1.0 / tDiv);
55    for (double index = 0; index < parts; ++index) {
56        double newT = start + (index / parts) * (end - start);
57        if (newT > 0 && newT < 1) {
58            ts->push_back(newT);
59        }
60    }
61}
62
63static void toQuadraticTs(const SkDCubic* cubic, double precision, SkTArray<double, true>* ts) {
64    SkReduceOrder reducer;
65    int order = reducer.reduce(*cubic, SkReduceOrder::kAllow_Quadratics);
66    if (order < 3) {
67        return;
68    }
69    double inflectT[5];
70    int inflections = cubic->findInflections(inflectT);
71    SkASSERT(inflections <= 2);
72    if (!cubic->endsAreExtremaInXOrY()) {
73        inflections += cubic->findMaxCurvature(&inflectT[inflections]);
74        SkASSERT(inflections <= 5);
75    }
76    SkTQSort<double>(inflectT, &inflectT[inflections - 1]);
77    // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its
78    // own subroutine?
79    while (inflections && approximately_less_than_zero(inflectT[0])) {
80        memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections);
81    }
82    int start = 0;
83    int next = 1;
84    while (next < inflections) {
85        if (!approximately_equal(inflectT[start], inflectT[next])) {
86            ++start;
87        ++next;
88            continue;
89        }
90        memmove(&inflectT[start], &inflectT[next], sizeof(inflectT[0]) * (--inflections - start));
91    }
92
93    while (inflections && approximately_greater_than_one(inflectT[inflections - 1])) {
94        --inflections;
95    }
96    SkDCubicPair pair;
97    if (inflections == 1) {
98        pair = cubic->chopAt(inflectT[0]);
99        int orderP1 = reducer.reduce(pair.first(), SkReduceOrder::kNo_Quadratics);
100        if (orderP1 < 2) {
101            --inflections;
102        } else {
103            int orderP2 = reducer.reduce(pair.second(), SkReduceOrder::kNo_Quadratics);
104            if (orderP2 < 2) {
105                --inflections;
106            }
107        }
108    }
109    if (inflections == 0 && add_simple_ts(*cubic, precision, ts)) {
110        return;
111    }
112    if (inflections == 1) {
113        pair = cubic->chopAt(inflectT[0]);
114        addTs(pair.first(), precision, 0, inflectT[0], ts);
115        addTs(pair.second(), precision, inflectT[0], 1, ts);
116        return;
117    }
118    if (inflections > 1) {
119        SkDCubic part = cubic->subDivide(0, inflectT[0]);
120        addTs(part, precision, 0, inflectT[0], ts);
121        int last = inflections - 1;
122        for (int idx = 0; idx < last; ++idx) {
123            part = cubic->subDivide(inflectT[idx], inflectT[idx + 1]);
124            addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts);
125        }
126        part = cubic->subDivide(inflectT[last], 1);
127        addTs(part, precision, inflectT[last], 1, ts);
128        return;
129    }
130    addTs(*cubic, precision, 0, 1, ts);
131}
132
133void CubicToQuads(const SkDCubic& cubic, double precision, SkTArray<SkDQuad, true>& quads) {
134    SkTArray<double, true> ts;
135    toQuadraticTs(&cubic, precision, &ts);
136    if (ts.count() <= 0) {
137        SkDQuad quad = cubic.toQuad();
138        quads.push_back(quad);
139        return;
140    }
141    double tStart = 0;
142    for (int i1 = 0; i1 <= ts.count(); ++i1) {
143        const double tEnd = i1 < ts.count() ? ts[i1] : 1;
144        SkDRect bounds;
145        bounds.setBounds(cubic);
146        SkDCubic part = cubic.subDivide(tStart, tEnd);
147        SkDQuad quad = part.toQuad();
148        if (quad[1].fX < bounds.fLeft) {
149            quad[1].fX = bounds.fLeft;
150        } else if (quad[1].fX > bounds.fRight) {
151            quad[1].fX = bounds.fRight;
152        }
153        if (quad[1].fY < bounds.fTop) {
154            quad[1].fY = bounds.fTop;
155        } else if (quad[1].fY > bounds.fBottom) {
156            quad[1].fY = bounds.fBottom;
157        }
158        quads.push_back(quad);
159        tStart = tEnd;
160    }
161}
162
163void CubicPathToQuads(const SkPath& cubicPath, SkPath* quadPath) {
164    quadPath->reset();
165    SkDCubic cubic;
166    SkTArray<SkDQuad, true> quads;
167    SkPath::RawIter iter(cubicPath);
168    uint8_t verb;
169    SkPoint pts[4];
170    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
171        switch (verb) {
172            case SkPath::kMove_Verb:
173                quadPath->moveTo(pts[0].fX, pts[0].fY);
174                continue;
175            case SkPath::kLine_Verb:
176                quadPath->lineTo(pts[1].fX, pts[1].fY);
177                break;
178            case SkPath::kQuad_Verb:
179                quadPath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
180                break;
181            case SkPath::kCubic_Verb:
182                quads.reset();
183                cubic.set(pts);
184                CubicToQuads(cubic, cubic.calcPrecision(), quads);
185                for (int index = 0; index < quads.count(); ++index) {
186                    SkPoint qPts[2] = {
187                        quads[index][1].asSkPoint(),
188                        quads[index][2].asSkPoint()
189                    };
190                    quadPath->quadTo(qPts[0].fX, qPts[0].fY, qPts[1].fX, qPts[1].fY);
191                }
192                break;
193            case SkPath::kClose_Verb:
194                 quadPath->close();
195                break;
196            default:
197                SkDEBUGFAIL("bad verb");
198                return;
199        }
200    }
201}
202
203void CubicPathToSimple(const SkPath& cubicPath, SkPath* simplePath) {
204    simplePath->reset();
205    SkDCubic cubic;
206    SkPath::RawIter iter(cubicPath);
207    uint8_t verb;
208    SkPoint pts[4];
209    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
210        switch (verb) {
211            case SkPath::kMove_Verb:
212                simplePath->moveTo(pts[0].fX, pts[0].fY);
213                continue;
214            case SkPath::kLine_Verb:
215                simplePath->lineTo(pts[1].fX, pts[1].fY);
216                break;
217            case SkPath::kQuad_Verb:
218                simplePath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
219                break;
220            case SkPath::kCubic_Verb: {
221                cubic.set(pts);
222                double tInflects[2];
223                int inflections = cubic.findInflections(tInflects);
224                if (inflections > 1 && tInflects[0] > tInflects[1]) {
225                    SkTSwap(tInflects[0], tInflects[1]);
226                }
227                double lo = 0;
228                for (int index = 0; index <= inflections; ++index) {
229                    double hi = index < inflections ? tInflects[index] : 1;
230                    SkDCubic part = cubic.subDivide(lo, hi);
231                    SkPoint cPts[3];
232                    cPts[0] = part[1].asSkPoint();
233                    cPts[1] = part[2].asSkPoint();
234                    cPts[2] = part[3].asSkPoint();
235                    simplePath->cubicTo(cPts[0].fX, cPts[0].fY, cPts[1].fX, cPts[1].fY,
236                            cPts[2].fX, cPts[2].fY);
237                    lo = hi;
238                }
239                break;
240            }
241            case SkPath::kClose_Verb:
242                 simplePath->close();
243                break;
244            default:
245                SkDEBUGFAIL("bad verb");
246                return;
247        }
248    }
249}
250
251static bool SkDoubleIsNaN(double x) {
252    return x != x;
253}
254
255bool ValidBounds(const SkPathOpsBounds& bounds) {
256    if (SkScalarIsNaN(bounds.fLeft)) {
257        return false;
258    }
259    if (SkScalarIsNaN(bounds.fTop)) {
260        return false;
261    }
262    if (SkScalarIsNaN(bounds.fRight)) {
263        return false;
264    }
265    return !SkScalarIsNaN(bounds.fBottom);
266}
267
268bool ValidConic(const SkDConic& conic) {
269    for (int index = 0; index < SkDConic::kPointCount; ++index) {
270        if (!ValidPoint(conic[index])) {
271            return false;
272        }
273    }
274    if (SkDoubleIsNaN(conic.fWeight)) {
275        return false;
276    }
277    return true;
278}
279
280bool ValidCubic(const SkDCubic& cubic) {
281    for (int index = 0; index < 4; ++index) {
282        if (!ValidPoint(cubic[index])) {
283            return false;
284        }
285    }
286    return true;
287}
288
289bool ValidLine(const SkDLine& line) {
290    for (int index = 0; index < 2; ++index) {
291        if (!ValidPoint(line[index])) {
292            return false;
293        }
294    }
295    return true;
296}
297
298bool ValidPoint(const SkDPoint& pt) {
299    if (SkDoubleIsNaN(pt.fX)) {
300        return false;
301    }
302    return !SkDoubleIsNaN(pt.fY);
303}
304
305bool ValidPoints(const SkPoint* pts, int count) {
306    for (int index = 0; index < count; ++index) {
307        if (SkScalarIsNaN(pts[index].fX)) {
308            return false;
309        }
310        if (SkScalarIsNaN(pts[index].fY)) {
311            return false;
312        }
313    }
314    return true;
315}
316
317bool ValidQuad(const SkDQuad& quad) {
318    for (int index = 0; index < 3; ++index) {
319        if (!ValidPoint(quad[index])) {
320            return false;
321        }
322    }
323    return true;
324}
325
326bool ValidVector(const SkDVector& v) {
327    if (SkDoubleIsNaN(v.fX)) {
328        return false;
329    }
330    return !SkDoubleIsNaN(v.fY);
331}
332