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 "SkIntersections.h"
8#include "SkOpAngle.h"
9#include "SkOpSegment.h"
10#include "SkPathOpsCurve.h"
11#include "SkTSort.h"
12
13#if DEBUG_ANGLE
14#include "SkString.h"
15#endif
16
17/* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest
18   positive y. The largest angle has a positive x and a zero y. */
19
20#if DEBUG_ANGLE
21    static bool CompareResult(SkString* bugOut, int append, bool compare) {
22        SkDebugf("%s %c %d\n", bugOut->c_str(), compare ? 'T' : 'F', append);
23        return compare;
24    }
25
26    #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, compare)
27#else
28    #define COMPARE_RESULT(append, compare) compare
29#endif
30
31/*             quarter angle values for sector
32
3331   x > 0, y == 0              horizontal line (to the right)
340    x > 0, y == epsilon        quad/cubic horizontal tangent eventually going +y
351    x > 0, y > 0, x > y        nearer horizontal angle
362                  x + e == y   quad/cubic 45 going horiz
373    x > 0, y > 0, x == y       45 angle
384                  x == y + e   quad/cubic 45 going vert
395    x > 0, y > 0, x < y        nearer vertical angle
406    x == epsilon, y > 0        quad/cubic vertical tangent eventually going +x
417    x == 0, y > 0              vertical line (to the top)
42
43                                      8  7  6
44                                 9       |       5
45                              10         |          4
46                            11           |            3
47                          12  \          |           / 2
48                         13              |              1
49                        14               |               0
50                        15 --------------+------------- 31
51                        16               |              30
52                         17              |             29
53                          18  /          |          \ 28
54                            19           |           27
55                              20         |         26
56                                 21      |      25
57                                     22 23 24
58*/
59
60// return true if lh < this < rh
61bool SkOpAngle::after(const SkOpAngle* test) const {
62    const SkOpAngle& lh = *test;
63    const SkOpAngle& rh = *lh.fNext;
64    SkASSERT(&lh != &rh);
65#if DEBUG_ANGLE
66    SkString bugOut;
67    bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
68                  " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
69                  " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__,
70            lh.fSegment->debugID(), lh.debugID(), lh.fSectorStart, lh.fSectorEnd,
71            lh.fSegment->t(lh.fStart), lh.fSegment->t(lh.fEnd),
72            fSegment->debugID(), debugID(), fSectorStart, fSectorEnd, fSegment->t(fStart),
73            fSegment->t(fEnd),
74            rh.fSegment->debugID(), rh.debugID(), rh.fSectorStart, rh.fSectorEnd,
75            rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd));
76#endif
77    if (lh.fComputeSector && !const_cast<SkOpAngle&>(lh).computeSector()) {
78        return COMPARE_RESULT(1, true);
79    }
80    if (fComputeSector && !const_cast<SkOpAngle*>(this)->computeSector()) {
81        return COMPARE_RESULT(2, true);
82    }
83    if (rh.fComputeSector && !const_cast<SkOpAngle&>(rh).computeSector()) {
84        return COMPARE_RESULT(3, true);
85    }
86#if DEBUG_ANGLE  // reset bugOut with computed sectors
87    bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
88                  " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
89                  " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__,
90            lh.fSegment->debugID(), lh.debugID(), lh.fSectorStart, lh.fSectorEnd,
91            lh.fSegment->t(lh.fStart), lh.fSegment->t(lh.fEnd),
92            fSegment->debugID(), debugID(), fSectorStart, fSectorEnd, fSegment->t(fStart),
93            fSegment->t(fEnd),
94            rh.fSegment->debugID(), rh.debugID(), rh.fSectorStart, rh.fSectorEnd,
95            rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd));
96#endif
97    bool ltrOverlap = (lh.fSectorMask | rh.fSectorMask) & fSectorMask;
98    bool lrOverlap = lh.fSectorMask & rh.fSectorMask;
99    int lrOrder;  // set to -1 if either order works
100    if (!lrOverlap) {  // no lh/rh sector overlap
101        if (!ltrOverlap) {  // no lh/this/rh sector overlap
102            return COMPARE_RESULT(4,  (lh.fSectorEnd > rh.fSectorStart)
103                    ^ (fSectorStart > lh.fSectorEnd) ^ (fSectorStart > rh.fSectorStart));
104        }
105        int lrGap = (rh.fSectorStart - lh.fSectorStart + 32) & 0x1f;
106        /* A tiny change can move the start +/- 4. The order can only be determined if
107           lr gap is not 12 to 20 or -12 to -20.
108               -31 ..-21      1
109               -20 ..-12     -1
110               -11 .. -1      0
111                 0          shouldn't get here
112                11 ..  1      1
113                12 .. 20     -1
114                21 .. 31      0
115         */
116        lrOrder = lrGap > 20 ? 0 : lrGap > 11 ? -1 : 1;
117    } else {
118        lrOrder = (int) lh.orderable(rh);
119        if (!ltrOverlap) {
120            return COMPARE_RESULT(5, !lrOrder);
121        }
122    }
123    int ltOrder;
124    SkASSERT((lh.fSectorMask & fSectorMask) || (rh.fSectorMask & fSectorMask));
125    if (lh.fSectorMask & fSectorMask) {
126        ltOrder = (int) lh.orderable(*this);
127    } else {
128        int ltGap = (fSectorStart - lh.fSectorStart + 32) & 0x1f;
129        ltOrder = ltGap > 20 ? 0 : ltGap > 11 ? -1 : 1;
130    }
131    int trOrder;
132    if (rh.fSectorMask & fSectorMask) {
133        trOrder = (int) orderable(rh);
134    } else {
135        int trGap = (rh.fSectorStart - fSectorStart + 32) & 0x1f;
136        trOrder = trGap > 20 ? 0 : trGap > 11 ? -1 : 1;
137    }
138    if (lrOrder >= 0 && ltOrder >= 0 && trOrder >= 0) {
139        return COMPARE_RESULT(7, lrOrder ? (ltOrder & trOrder) : (ltOrder | trOrder));
140    }
141    SkASSERT(lrOrder >= 0 || ltOrder >= 0 || trOrder >= 0);
142// There's not enough information to sort. Get the pairs of angles in opposite planes.
143// If an order is < 0, the pair is already in an opposite plane. Check the remaining pairs.
144    // FIXME : once all variants are understood, rewrite this more simply
145    if (ltOrder == 0 && lrOrder == 0) {
146        SkASSERT(trOrder < 0);
147        // FIXME : once this is verified to work, remove one opposite angle call
148        SkDEBUGCODE(bool lrOpposite = lh.oppositePlanes(rh));
149        bool ltOpposite = lh.oppositePlanes(*this);
150        SkASSERT(lrOpposite != ltOpposite);
151        return COMPARE_RESULT(8, ltOpposite);
152    } else if (ltOrder == 1 && trOrder == 0) {
153        SkASSERT(lrOrder < 0);
154        SkDEBUGCODE(bool ltOpposite = lh.oppositePlanes(*this));
155        bool trOpposite = oppositePlanes(rh);
156        SkASSERT(ltOpposite != trOpposite);
157        return COMPARE_RESULT(9, trOpposite);
158    } else if (lrOrder == 1 && trOrder == 1) {
159        SkASSERT(ltOrder < 0);
160        SkDEBUGCODE(bool trOpposite = oppositePlanes(rh));
161        bool lrOpposite = lh.oppositePlanes(rh);
162        SkASSERT(lrOpposite != trOpposite);
163        return COMPARE_RESULT(10, lrOpposite);
164    }
165    if (lrOrder < 0) {
166        if (ltOrder < 0) {
167            return COMPARE_RESULT(11, trOrder);
168        }
169        return COMPARE_RESULT(12, ltOrder);
170    }
171    return COMPARE_RESULT(13, !lrOrder);
172}
173
174// given a line, see if the opposite curve's convex hull is all on one side
175// returns -1=not on one side    0=this CW of test   1=this CCW of test
176int SkOpAngle::allOnOneSide(const SkOpAngle& test) const {
177    SkASSERT(!fIsCurve);
178    SkASSERT(test.fIsCurve);
179    const SkDPoint& origin = test.fCurvePart[0];
180    SkVector line;
181    if (fSegment->verb() == SkPath::kLine_Verb) {
182        const SkPoint* linePts = fSegment->pts();
183        int lineStart = fStart < fEnd ? 0 : 1;
184        line = linePts[lineStart ^ 1] - linePts[lineStart];
185    } else {
186        SkPoint shortPts[2] = { fCurvePart[0].asSkPoint(), fCurvePart[1].asSkPoint() };
187        line = shortPts[1] - shortPts[0];
188    }
189    float crosses[3];
190    SkPath::Verb testVerb = test.fSegment->verb();
191    int iMax = SkPathOpsVerbToPoints(testVerb);
192//    SkASSERT(origin == test.fCurveHalf[0]);
193    const SkDCubic& testCurve = test.fCurvePart;
194//    do {
195        for (int index = 1; index <= iMax; ++index) {
196            float xy1 = (float) (line.fX * (testCurve[index].fY - origin.fY));
197            float xy2 = (float) (line.fY * (testCurve[index].fX - origin.fX));
198            crosses[index - 1] = AlmostEqualUlps(xy1, xy2) ? 0 : xy1 - xy2;
199        }
200        if (crosses[0] * crosses[1] < 0) {
201            return -1;
202        }
203        if (SkPath::kCubic_Verb == testVerb) {
204            if (crosses[0] * crosses[2] < 0 || crosses[1] * crosses[2] < 0) {
205                return -1;
206            }
207        }
208        if (crosses[0]) {
209            return crosses[0] < 0;
210        }
211        if (crosses[1]) {
212            return crosses[1] < 0;
213        }
214        if (SkPath::kCubic_Verb == testVerb && crosses[2]) {
215            return crosses[2] < 0;
216        }
217    fUnorderable = true;
218    return -1;
219}
220
221bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const {
222    double absX = fabs(x);
223    double absY = fabs(y);
224    double length = absX < absY ? absX / 2 + absY : absX + absY / 2;
225    int exponent;
226    (void) frexp(length, &exponent);
227    double epsilon = ldexp(FLT_EPSILON, exponent);
228    SkPath::Verb verb = fSegment->verb();
229    SkASSERT(verb == SkPath::kQuad_Verb || verb == SkPath::kCubic_Verb);
230    // FIXME: the quad and cubic factors are made up ; determine actual values
231    double slop = verb == SkPath::kQuad_Verb ? 4 * epsilon : 512 * epsilon;
232    double xSlop = slop;
233    double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ?
234    double x1 = x - xSlop;
235    double y1 = y + ySlop;
236    double x_ry1 = x1 * ry;
237    double rx_y1 = rx * y1;
238    *result = x_ry1 < rx_y1;
239    double x2 = x + xSlop;
240    double y2 = y - ySlop;
241    double x_ry2 = x2 * ry;
242    double rx_y2 = rx * y2;
243    bool less2 = x_ry2 < rx_y2;
244    return *result == less2;
245}
246
247bool SkOpAngle::checkCrossesZero() const {
248    int start = SkTMin(fSectorStart, fSectorEnd);
249    int end = SkTMax(fSectorStart, fSectorEnd);
250    bool crossesZero = end - start > 16;
251    return crossesZero;
252}
253
254bool SkOpAngle::checkParallel(const SkOpAngle& rh) const {
255    SkDVector scratch[2];
256    const SkDVector* sweep, * tweep;
257    if (!fUnorderedSweep) {
258        sweep = fSweep;
259    } else {
260        scratch[0] = fCurvePart[1] - fCurvePart[0];
261        sweep = &scratch[0];
262    }
263    if (!rh.fUnorderedSweep) {
264        tweep = rh.fSweep;
265    } else {
266        scratch[1] = rh.fCurvePart[1] - rh.fCurvePart[0];
267        tweep = &scratch[1];
268    }
269    double s0xt0 = sweep->crossCheck(*tweep);
270    if (tangentsDiverge(rh, s0xt0)) {
271        return s0xt0 < 0;
272    }
273    SkDVector m0 = fSegment->dPtAtT(midT()) - fCurvePart[0];
274    SkDVector m1 = rh.fSegment->dPtAtT(rh.midT()) - rh.fCurvePart[0];
275    double m0xm1 = m0.crossCheck(m1);
276    if (m0xm1 == 0) {
277        fUnorderable = true;
278        rh.fUnorderable = true;
279        return true;
280    }
281    return m0xm1 < 0;
282}
283
284// the original angle is too short to get meaningful sector information
285// lengthen it until it is long enough to be meaningful or leave it unset if lengthening it
286// would cause it to intersect one of the adjacent angles
287bool SkOpAngle::computeSector() {
288    if (fComputedSector) {
289        // FIXME: logically, this should return !fUnorderable, but doing so breaks testQuadratic51
290        // -- but in general, this code may not work so this may be the least of problems
291        // adding the bang fixes testQuads46x in release, however
292        return !fUnorderable;
293    }
294    SkASSERT(fSegment->verb() != SkPath::kLine_Verb && small());
295    fComputedSector = true;
296    int step = fStart < fEnd ? 1 : -1;
297    int limit = step > 0 ? fSegment->count() : -1;
298    int checkEnd = fEnd;
299    do {
300// advance end
301        const SkOpSpan& span = fSegment->span(checkEnd);
302        const SkOpSegment* other = span.fOther;
303        int oCount = other->count();
304        for (int oIndex = 0; oIndex < oCount; ++oIndex) {
305            const SkOpSpan& oSpan = other->span(oIndex);
306            if (oSpan.fOther != fSegment) {
307                continue;
308            }
309            if (oSpan.fOtherIndex == checkEnd) {
310                continue;
311            }
312            if (!approximately_equal(oSpan.fOtherT, span.fT)) {
313                continue;
314            }
315            goto recomputeSector;
316        }
317        checkEnd += step;
318    } while (checkEnd != limit);
319recomputeSector:
320    if (checkEnd == fEnd || checkEnd - step == fEnd) {
321        fUnorderable = true;
322        return false;
323    }
324    int saveEnd = fEnd;
325    fComputedEnd = fEnd = checkEnd - step;
326    setSpans();
327    setSector();
328    fEnd = saveEnd;
329    return !fUnorderable;
330}
331
332// returns -1 if overlaps   0 if no overlap cw    1 if no overlap ccw
333int SkOpAngle::convexHullOverlaps(const SkOpAngle& rh) const {
334    const SkDVector* sweep = fSweep;
335    const SkDVector* tweep = rh.fSweep;
336    double s0xs1 = sweep[0].crossCheck(sweep[1]);
337    double s0xt0 = sweep[0].crossCheck(tweep[0]);
338    double s1xt0 = sweep[1].crossCheck(tweep[0]);
339    bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0;
340    double s0xt1 = sweep[0].crossCheck(tweep[1]);
341    double s1xt1 = sweep[1].crossCheck(tweep[1]);
342    tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0;
343    double t0xt1 = tweep[0].crossCheck(tweep[1]);
344    if (tBetweenS) {
345        return -1;
346    }
347    if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) {  // s0 to s1 equals t0 to t1
348        return -1;
349    }
350    bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0;
351    sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0;
352    if (sBetweenT) {
353        return -1;
354    }
355    // if all of the sweeps are in the same half plane, then the order of any pair is enough
356    if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) {
357        return 0;
358    }
359    if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) {
360        return 1;
361    }
362    // if the outside sweeps are greater than 180 degress:
363        // first assume the inital tangents are the ordering
364        // if the midpoint direction matches the inital order, that is enough
365    SkDVector m0 = fSegment->dPtAtT(midT()) - fCurvePart[0];
366    SkDVector m1 = rh.fSegment->dPtAtT(rh.midT()) - rh.fCurvePart[0];
367    double m0xm1 = m0.crossCheck(m1);
368    if (s0xt0 > 0 && m0xm1 > 0) {
369        return 0;
370    }
371    if (s0xt0 < 0 && m0xm1 < 0) {
372        return 1;
373    }
374    if (tangentsDiverge(rh, s0xt0)) {
375        return s0xt0 < 0;
376    }
377    return m0xm1 < 0;
378}
379
380// OPTIMIZATION: longest can all be either lazily computed here or precomputed in setup
381double SkOpAngle::distEndRatio(double dist) const {
382    double longest = 0;
383    const SkOpSegment& segment = *this->segment();
384    int ptCount = SkPathOpsVerbToPoints(segment.verb());
385    const SkPoint* pts = segment.pts();
386    for (int idx1 = 0; idx1 <= ptCount - 1; ++idx1) {
387        for (int idx2 = idx1 + 1; idx2 <= ptCount; ++idx2) {
388            if (idx1 == idx2) {
389                continue;
390            }
391            SkDVector v;
392            v.set(pts[idx2] - pts[idx1]);
393            double lenSq = v.lengthSquared();
394            longest = SkTMax(longest, lenSq);
395        }
396    }
397    return sqrt(longest) / dist;
398}
399
400bool SkOpAngle::endsIntersect(const SkOpAngle& rh) const {
401    SkPath::Verb lVerb = fSegment->verb();
402    SkPath::Verb rVerb = rh.fSegment->verb();
403    int lPts = SkPathOpsVerbToPoints(lVerb);
404    int rPts = SkPathOpsVerbToPoints(rVerb);
405    SkDLine rays[] = {{{fCurvePart[0], rh.fCurvePart[rPts]}},
406            {{fCurvePart[0], fCurvePart[lPts]}}};
407    if (rays[0][1] == rays[1][1]) {
408        return checkParallel(rh);
409    }
410    double smallTs[2] = {-1, -1};
411    bool limited[2] = {false, false};
412    for (int index = 0; index < 2; ++index) {
413        const SkOpSegment& segment = index ? *rh.fSegment : *fSegment;
414        SkIntersections i;
415        (*CurveIntersectRay[index ? rPts : lPts])(segment.pts(), rays[index], &i);
416//      SkASSERT(i.used() >= 1);
417//        if (i.used() <= 1) {
418//            continue;
419//        }
420        double tStart = segment.t(index ? rh.fStart : fStart);
421        double tEnd = segment.t(index ? rh.fComputedEnd : fComputedEnd);
422        bool testAscends = index ? rh.fStart < rh.fComputedEnd : fStart < fComputedEnd;
423        double t = testAscends ? 0 : 1;
424        for (int idx2 = 0; idx2 < i.used(); ++idx2) {
425            double testT = i[0][idx2];
426            if (!approximately_between_orderable(tStart, testT, tEnd)) {
427                continue;
428            }
429            if (approximately_equal_orderable(tStart, testT)) {
430                continue;
431            }
432            smallTs[index] = t = testAscends ? SkTMax(t, testT) : SkTMin(t, testT);
433            limited[index] = approximately_equal_orderable(t, tEnd);
434        }
435    }
436#if 0
437    if (smallTs[0] < 0 && smallTs[1] < 0) {  // if neither ray intersects, do endpoint sort
438        double m0xm1 = 0;
439        if (lVerb == SkPath::kLine_Verb) {
440            SkASSERT(rVerb != SkPath::kLine_Verb);
441            SkDVector m0 = rays[1][1] - fCurvePart[0];
442            SkDPoint endPt;
443            endPt.set(rh.fSegment->pts()[rh.fStart < rh.fEnd ? rPts : 0]);
444            SkDVector m1 = endPt - fCurvePart[0];
445            m0xm1 = m0.crossCheck(m1);
446        }
447        if (rVerb == SkPath::kLine_Verb) {
448            SkDPoint endPt;
449            endPt.set(fSegment->pts()[fStart < fEnd ? lPts : 0]);
450            SkDVector m0 = endPt - fCurvePart[0];
451            SkDVector m1 = rays[0][1] - fCurvePart[0];
452            m0xm1 = m0.crossCheck(m1);
453        }
454        if (m0xm1 != 0) {
455            return m0xm1 < 0;
456        }
457    }
458#endif
459    bool sRayLonger = false;
460    SkDVector sCept = {0, 0};
461    double sCeptT = -1;
462    int sIndex = -1;
463    bool useIntersect = false;
464    for (int index = 0; index < 2; ++index) {
465        if (smallTs[index] < 0) {
466            continue;
467        }
468        const SkOpSegment& segment = index ? *rh.fSegment : *fSegment;
469        const SkDPoint& dPt = segment.dPtAtT(smallTs[index]);
470        SkDVector cept = dPt - rays[index][0];
471        // If this point is on the curve, it should have been detected earlier by ordinary
472        // curve intersection. This may be hard to determine in general, but for lines,
473        // the point could be close to or equal to its end, but shouldn't be near the start.
474        if ((index ? lPts : rPts) == 1) {
475            SkDVector total = rays[index][1] - rays[index][0];
476            if (cept.lengthSquared() * 2 < total.lengthSquared()) {
477                continue;
478            }
479        }
480        SkDVector end = rays[index][1] - rays[index][0];
481        if (cept.fX * end.fX < 0 || cept.fY * end.fY < 0) {
482            continue;
483        }
484        double rayDist = cept.length();
485        double endDist = end.length();
486        bool rayLonger = rayDist > endDist;
487        if (limited[0] && limited[1] && rayLonger) {
488            useIntersect = true;
489            sRayLonger = rayLonger;
490            sCept = cept;
491            sCeptT = smallTs[index];
492            sIndex = index;
493            break;
494        }
495        double delta = fabs(rayDist - endDist);
496        double minX, minY, maxX, maxY;
497        minX = minY = SK_ScalarInfinity;
498        maxX = maxY = -SK_ScalarInfinity;
499        const SkDCubic& curve = index ? rh.fCurvePart : fCurvePart;
500        int ptCount = index ? rPts : lPts;
501        for (int idx2 = 0; idx2 <= ptCount; ++idx2) {
502            minX = SkTMin(minX, curve[idx2].fX);
503            minY = SkTMin(minY, curve[idx2].fY);
504            maxX = SkTMax(maxX, curve[idx2].fX);
505            maxY = SkTMax(maxY, curve[idx2].fY);
506        }
507        double maxWidth = SkTMax(maxX - minX, maxY - minY);
508        delta /= maxWidth;
509        if (delta > 1e-4 && (useIntersect ^= true)) {  // FIXME: move this magic number
510            sRayLonger = rayLonger;
511            sCept = cept;
512            sCeptT = smallTs[index];
513            sIndex = index;
514        }
515    }
516    if (useIntersect) {
517        const SkDCubic& curve = sIndex ? rh.fCurvePart : fCurvePart;
518        const SkOpSegment& segment = sIndex ? *rh.fSegment : *fSegment;
519        double tStart = segment.t(sIndex ? rh.fStart : fStart);
520        SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0];
521        double septDir = mid.crossCheck(sCept);
522        if (!septDir) {
523            return checkParallel(rh);
524        }
525        return sRayLonger ^ (sIndex == 0) ^ (septDir < 0);
526    } else {
527        return checkParallel(rh);
528    }
529}
530
531// Most of the time, the first one can be found trivially by detecting the smallest sector value.
532// If all angles have the same sector value, actual sorting is required.
533const SkOpAngle* SkOpAngle::findFirst() const {
534    const SkOpAngle* best = this;
535    int bestStart = SkTMin(fSectorStart, fSectorEnd);
536    const SkOpAngle* angle = this;
537    while ((angle = angle->fNext) != this) {
538        int angleEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd);
539        if (angleEnd < bestStart) {
540            return angle;    // we wrapped around
541        }
542        int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd);
543        if (bestStart > angleStart) {
544            best = angle;
545            bestStart = angleStart;
546        }
547    }
548    // back up to the first possible angle
549    const SkOpAngle* firstBest = best;
550    angle = best;
551    int bestEnd = SkTMax(best->fSectorStart, best->fSectorEnd);
552    while ((angle = angle->previous()) != firstBest) {
553        if (angle->fStop) {
554            break;
555        }
556        int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd);
557        // angles that are smaller by one aren't necessary better, since the larger may be a line
558        // and the smaller may be a curve that curls to the other side of the line.
559        if (bestEnd + 1 < angleStart) {
560            return best;
561        }
562        best = angle;
563        bestEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd);
564    }
565    // in the case where all angles are nearly in the same sector, check the order to find the best
566    firstBest = best;
567    angle = best;
568    do {
569        angle = angle->fNext;
570        if (angle->fStop) {
571            return firstBest;
572        }
573        bool orderable = best->orderable(*angle);  // note: may return an unorderable angle
574        if (orderable == 0) {
575            return angle;
576        }
577        best = angle;
578    } while (angle != firstBest);
579    // if the angles are equally ordered, fall back on the initial tangent
580    bool foundBelow = false;
581    while ((angle = angle->fNext)) {
582        SkDVector scratch[2];
583        const SkDVector* sweep;
584        if (!angle->fUnorderedSweep) {
585            sweep = angle->fSweep;
586        } else {
587            scratch[0] = angle->fCurvePart[1] - angle->fCurvePart[0];
588            sweep = &scratch[0];
589        }
590        bool isAbove = sweep->fY <= 0;
591        if (isAbove && foundBelow) {
592            return angle;
593        }
594        foundBelow |= !isAbove;
595        if (angle == firstBest) {
596            return NULL; // should not loop around
597        }
598    }
599    SkASSERT(0);  // should never get here
600    return NULL;
601}
602
603/*      y<0 y==0 y>0  x<0 x==0 x>0 xy<0 xy==0 xy>0
604    0    x                      x               x
605    1    x                      x          x
606    2    x                      x    x
607    3    x                  x        x
608    4    x             x             x
609    5    x             x                   x
610    6    x             x                        x
611    7         x        x                        x
612    8             x    x                        x
613    9             x    x                   x
614    10            x    x             x
615    11            x         x        x
616    12            x             x    x
617    13            x             x          x
618    14            x             x               x
619    15        x                 x               x
620*/
621int SkOpAngle::findSector(SkPath::Verb verb, double x, double y) const {
622    double absX = fabs(x);
623    double absY = fabs(y);
624    double xy = SkPath::kLine_Verb == verb || !AlmostEqualUlps(absX, absY) ? absX - absY : 0;
625    // If there are four quadrants and eight octants, and since the Latin for sixteen is sedecim,
626    // one could coin the term sedecimant for a space divided into 16 sections.
627   // http://english.stackexchange.com/questions/133688/word-for-something-partitioned-into-16-parts
628    static const int sedecimant[3][3][3] = {
629    //       y<0           y==0           y>0
630    //   x<0 x==0 x>0  x<0 x==0 x>0  x<0 x==0 x>0
631        {{ 4,  3,  2}, { 7, -1, 15}, {10, 11, 12}},  // abs(x) <  abs(y)
632        {{ 5, -1,  1}, {-1, -1, -1}, { 9, -1, 13}},  // abs(x) == abs(y)
633        {{ 6,  3,  0}, { 7, -1, 15}, { 8, 11, 14}},  // abs(x) >  abs(y)
634    };
635    int sector = sedecimant[(xy >= 0) + (xy > 0)][(y >= 0) + (y > 0)][(x >= 0) + (x > 0)] * 2 + 1;
636    SkASSERT(SkPath::kLine_Verb == verb || sector >= 0);
637    return sector;
638}
639
640// OPTIMIZE: if this loops to only one other angle, after first compare fails, insert on other side
641// OPTIMIZE: return where insertion succeeded. Then, start next insertion on opposite side
642void SkOpAngle::insert(SkOpAngle* angle) {
643    if (angle->fNext) {
644        if (loopCount() >= angle->loopCount()) {
645            if (!merge(angle)) {
646                return;
647            }
648        } else if (fNext) {
649            if (!angle->merge(this)) {
650                return;
651            }
652        } else {
653            angle->insert(this);
654        }
655        return;
656    }
657    bool singleton = NULL == fNext;
658    if (singleton) {
659        fNext = this;
660    }
661    SkOpAngle* next = fNext;
662    if (next->fNext == this) {
663        if (angle->overlap(*this)) {
664            return;
665        }
666        if (singleton || angle->after(this)) {
667            this->fNext = angle;
668            angle->fNext = next;
669        } else {
670            next->fNext = angle;
671            angle->fNext = this;
672        }
673        debugValidateNext();
674        return;
675    }
676    SkOpAngle* last = this;
677    do {
678        SkASSERT(last->fNext == next);
679        if (angle->overlap(*last) || angle->overlap(*next)) {
680            return;
681        }
682        if (angle->after(last)) {
683            last->fNext = angle;
684            angle->fNext = next;
685            debugValidateNext();
686            return;
687        }
688        last = next;
689        next = next->fNext;
690        if (last == this && next->fUnorderable) {
691            fUnorderable = true;
692            return;
693        }
694        SkASSERT(last != this);
695    } while (true);
696}
697
698bool SkOpAngle::isHorizontal() const {
699    return !fIsCurve && fSweep[0].fY == 0;
700}
701
702SkOpSpan* SkOpAngle::lastMarked() const {
703    if (fLastMarked) {
704        if (fLastMarked->fChased) {
705            return NULL;
706        }
707        fLastMarked->fChased = true;
708    }
709    return fLastMarked;
710}
711
712bool SkOpAngle::loopContains(const SkOpAngle& test) const {
713    if (!fNext) {
714        return false;
715    }
716    const SkOpAngle* first = this;
717    const SkOpAngle* loop = this;
718    const SkOpSegment* tSegment = test.fSegment;
719    double tStart = tSegment->span(test.fStart).fT;
720    double tEnd = tSegment->span(test.fEnd).fT;
721    do {
722        const SkOpSegment* lSegment = loop->fSegment;
723        // FIXME : use precisely_equal ? or compare points exactly ?
724        if (lSegment != tSegment) {
725            continue;
726        }
727        double lStart = lSegment->span(loop->fStart).fT;
728        if (lStart != tEnd) {
729            continue;
730        }
731        double lEnd = lSegment->span(loop->fEnd).fT;
732        if (lEnd == tStart) {
733            return true;
734        }
735    } while ((loop = loop->fNext) != first);
736    return false;
737}
738
739int SkOpAngle::loopCount() const {
740    int count = 0;
741    const SkOpAngle* first = this;
742    const SkOpAngle* next = this;
743    do {
744        next = next->fNext;
745        ++count;
746    } while (next && next != first);
747    return count;
748}
749
750// OPTIMIZATION: can this be done better in after when angles are sorted?
751void SkOpAngle::markStops() {
752    SkOpAngle* angle = this;
753    int lastEnd = SkTMax(fSectorStart, fSectorEnd);
754    do {
755        angle = angle->fNext;
756        int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd);
757        // angles that are smaller by one aren't necessary better, since the larger may be a line
758        // and the smaller may be a curve that curls to the other side of the line.
759        if (lastEnd + 1 < angleStart) {
760            angle->fStop = true;
761        }
762        lastEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd);
763    } while (angle != this);
764}
765
766bool SkOpAngle::merge(SkOpAngle* angle) {
767    SkASSERT(fNext);
768    SkASSERT(angle->fNext);
769    SkOpAngle* working = angle;
770    do {
771        if (this == working) {
772            return false;
773        }
774        working = working->fNext;
775    } while (working != angle);
776    do {
777        SkOpAngle* next = working->fNext;
778        working->fNext = NULL;
779        insert(working);
780        working = next;
781    } while (working != angle);
782    // it's likely that a pair of the angles are unorderable
783#if DEBUG_ANGLE
784    SkOpAngle* last = angle;
785    working = angle->fNext;
786    do {
787        SkASSERT(last->fNext == working);
788        last->fNext = working->fNext;
789        SkASSERT(working->after(last));
790        last->fNext = working;
791        last = working;
792        working = working->fNext;
793    } while (last != angle);
794#endif
795    debugValidateNext();
796    return true;
797}
798
799double SkOpAngle::midT() const {
800    return (fSegment->t(fStart) + fSegment->t(fEnd)) / 2;
801}
802
803bool SkOpAngle::oppositePlanes(const SkOpAngle& rh) const {
804    int startSpan = abs(rh.fSectorStart - fSectorStart);
805    return startSpan >= 8;
806}
807
808bool SkOpAngle::orderable(const SkOpAngle& rh) const {
809    int result;
810    if (!fIsCurve) {
811        if (!rh.fIsCurve) {
812            double leftX = fTangentHalf.dx();
813            double leftY = fTangentHalf.dy();
814            double rightX = rh.fTangentHalf.dx();
815            double rightY = rh.fTangentHalf.dy();
816            double x_ry = leftX * rightY;
817            double rx_y = rightX * leftY;
818            if (x_ry == rx_y) {
819                if (leftX * rightX < 0 || leftY * rightY < 0) {
820                    return true;  // exactly 180 degrees apart
821                }
822                goto unorderable;
823            }
824            SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- worth finding earlier
825            return x_ry < rx_y;
826        }
827        if ((result = allOnOneSide(rh)) >= 0) {
828            return result;
829        }
830        if (fUnorderable || approximately_zero(rh.fSide)) {
831            goto unorderable;
832        }
833    } else if (!rh.fIsCurve) {
834        if ((result = rh.allOnOneSide(*this)) >= 0) {
835            return !result;
836        }
837        if (rh.fUnorderable || approximately_zero(fSide)) {
838            goto unorderable;
839        }
840    }
841    if ((result = convexHullOverlaps(rh)) >= 0) {
842        return result;
843    }
844    return endsIntersect(rh);
845unorderable:
846    fUnorderable = true;
847    rh.fUnorderable = true;
848    return true;
849}
850
851bool SkOpAngle::overlap(const SkOpAngle& other) const {
852    int min = SkTMin(fStart, fEnd);
853    const SkOpSpan& span = fSegment->span(min);
854    const SkOpSegment* oSeg = other.fSegment;
855    int oMin = SkTMin(other.fStart, other.fEnd);
856    const SkOpSpan& oSpan = oSeg->span(oMin);
857    if (!span.fSmall && !oSpan.fSmall) {
858        return false;
859    }
860    if (fSegment->span(fStart).fPt != oSeg->span(other.fStart).fPt) {
861        return false;
862    }
863    // see if small span is contained by opposite span
864    return span.fSmall ? oSeg->containsPt(fSegment->span(fEnd).fPt, other.fEnd, other.fStart)
865            : fSegment->containsPt(oSeg->span(other.fEnd).fPt, fEnd, fStart);
866}
867
868// OPTIMIZE: if this shows up in a profile, add a previous pointer
869// as is, this should be rarely called
870SkOpAngle* SkOpAngle::previous() const {
871    SkOpAngle* last = fNext;
872    do {
873        SkOpAngle* next = last->fNext;
874        if (next == this) {
875            return last;
876        }
877        last = next;
878    } while (true);
879}
880
881void SkOpAngle::set(const SkOpSegment* segment, int start, int end) {
882    fSegment = segment;
883    fStart = start;
884    fComputedEnd = fEnd = end;
885    fNext = NULL;
886    fComputeSector = fComputedSector = false;
887    fStop = false;
888    setSpans();
889    setSector();
890}
891
892void SkOpAngle::setCurveHullSweep() {
893    fUnorderedSweep = false;
894    fSweep[0] = fCurvePart[1] - fCurvePart[0];
895    if (SkPath::kLine_Verb == fSegment->verb()) {
896        fSweep[1] = fSweep[0];
897        return;
898    }
899    fSweep[1] = fCurvePart[2] - fCurvePart[0];
900    if (SkPath::kCubic_Verb != fSegment->verb()) {
901        if (!fSweep[0].fX && !fSweep[0].fY) {
902            fSweep[0] = fSweep[1];
903        }
904        return;
905    }
906    SkDVector thirdSweep = fCurvePart[3] - fCurvePart[0];
907    if (fSweep[0].fX == 0 && fSweep[0].fY == 0) {
908        fSweep[0] = fSweep[1];
909        fSweep[1] = thirdSweep;
910        if (fSweep[0].fX == 0 && fSweep[0].fY == 0) {
911            fSweep[0] = fSweep[1];
912            fCurvePart[1] = fCurvePart[3];
913            fIsCurve = false;
914        }
915        return;
916    }
917    double s1x3 = fSweep[0].crossCheck(thirdSweep);
918    double s3x2 = thirdSweep.crossCheck(fSweep[1]);
919    if (s1x3 * s3x2 >= 0) {  // if third vector is on or between first two vectors
920        return;
921    }
922    double s2x1 = fSweep[1].crossCheck(fSweep[0]);
923    // FIXME: If the sweep of the cubic is greater than 180 degrees, we're in trouble
924    // probably such wide sweeps should be artificially subdivided earlier so that never happens
925    SkASSERT(s1x3 * s2x1 < 0 || s1x3 * s3x2 < 0);
926    if (s3x2 * s2x1 < 0) {
927        SkASSERT(s2x1 * s1x3 > 0);
928        fSweep[0] = fSweep[1];
929        fUnorderedSweep = true;
930    }
931    fSweep[1] = thirdSweep;
932}
933
934void SkOpAngle::setSector() {
935    SkPath::Verb verb = fSegment->verb();
936    if (SkPath::kLine_Verb != verb && small()) {
937        fSectorStart = fSectorEnd = -1;
938        fSectorMask = 0;
939        fComputeSector = true;  // can't determine sector until segment length can be found
940        return;
941    }
942    fSectorStart = findSector(verb, fSweep[0].fX, fSweep[0].fY);
943    if (!fIsCurve) {  // if it's a line or line-like, note that both sectors are the same
944        SkASSERT(fSectorStart >= 0);
945        fSectorEnd = fSectorStart;
946        fSectorMask = 1 << fSectorStart;
947        return;
948    }
949    SkASSERT(SkPath::kLine_Verb != verb);
950    fSectorEnd = findSector(verb, fSweep[1].fX, fSweep[1].fY);
951    if (fSectorEnd == fSectorStart) {
952        SkASSERT((fSectorStart & 3) != 3);  // if the sector has no span, it can't be an exact angle
953        fSectorMask = 1 << fSectorStart;
954        return;
955    }
956    bool crossesZero = checkCrossesZero();
957    int start = SkTMin(fSectorStart, fSectorEnd);
958    bool curveBendsCCW = (fSectorStart == start) ^ crossesZero;
959    // bump the start and end of the sector span if they are on exact compass points
960    if ((fSectorStart & 3) == 3) {
961        fSectorStart = (fSectorStart + (curveBendsCCW ? 1 : 31)) & 0x1f;
962    }
963    if ((fSectorEnd & 3) == 3) {
964        fSectorEnd = (fSectorEnd + (curveBendsCCW ? 31 : 1)) & 0x1f;
965    }
966    crossesZero = checkCrossesZero();
967    start = SkTMin(fSectorStart, fSectorEnd);
968    int end = SkTMax(fSectorStart, fSectorEnd);
969    if (!crossesZero) {
970        fSectorMask = (unsigned) -1 >> (31 - end + start) << start;
971    } else {
972        fSectorMask = (unsigned) -1 >> (31 - start) | (-1 << end);
973    }
974}
975
976void SkOpAngle::setSpans() {
977    fUnorderable = fSegment->isTiny(this);
978    fLastMarked = NULL;
979    const SkPoint* pts = fSegment->pts();
980    SkDEBUGCODE(fCurvePart[2].fX = fCurvePart[2].fY = fCurvePart[3].fX = fCurvePart[3].fY
981            = SK_ScalarNaN);
982    fSegment->subDivide(fStart, fEnd, &fCurvePart);
983    setCurveHullSweep();
984    const SkPath::Verb verb = fSegment->verb();
985    if (verb != SkPath::kLine_Verb
986            && !(fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0)) {
987        SkDLine lineHalf;
988        lineHalf[0].set(fCurvePart[0].asSkPoint());
989        lineHalf[1].set(fCurvePart[SkPathOpsVerbToPoints(verb)].asSkPoint());
990        fTangentHalf.lineEndPoints(lineHalf);
991        fSide = 0;
992    }
993    switch (verb) {
994    case SkPath::kLine_Verb: {
995        SkASSERT(fStart != fEnd);
996        const SkPoint& cP1 = pts[fStart < fEnd];
997        SkDLine lineHalf;
998        lineHalf[0].set(fSegment->span(fStart).fPt);
999        lineHalf[1].set(cP1);
1000        fTangentHalf.lineEndPoints(lineHalf);
1001        fSide = 0;
1002        fIsCurve = false;
1003        } return;
1004    case SkPath::kQuad_Verb: {
1005        SkLineParameters tangentPart;
1006        SkDQuad& quad2 = *SkTCast<SkDQuad*>(&fCurvePart);
1007        (void) tangentPart.quadEndPoints(quad2);
1008        fSide = -tangentPart.pointDistance(fCurvePart[2]);  // not normalized -- compare sign only
1009        } break;
1010    case SkPath::kCubic_Verb: {
1011        SkLineParameters tangentPart;
1012        (void) tangentPart.cubicPart(fCurvePart);
1013        fSide = -tangentPart.pointDistance(fCurvePart[3]);
1014        double testTs[4];
1015        // OPTIMIZATION: keep inflections precomputed with cubic segment?
1016        int testCount = SkDCubic::FindInflections(pts, testTs);
1017        double startT = fSegment->t(fStart);
1018        double endT = fSegment->t(fEnd);
1019        double limitT = endT;
1020        int index;
1021        for (index = 0; index < testCount; ++index) {
1022            if (!::between(startT, testTs[index], limitT)) {
1023                testTs[index] = -1;
1024            }
1025        }
1026        testTs[testCount++] = startT;
1027        testTs[testCount++] = endT;
1028        SkTQSort<double>(testTs, &testTs[testCount - 1]);
1029        double bestSide = 0;
1030        int testCases = (testCount << 1) - 1;
1031        index = 0;
1032        while (testTs[index] < 0) {
1033            ++index;
1034        }
1035        index <<= 1;
1036        for (; index < testCases; ++index) {
1037            int testIndex = index >> 1;
1038            double testT = testTs[testIndex];
1039            if (index & 1) {
1040                testT = (testT + testTs[testIndex + 1]) / 2;
1041            }
1042            // OPTIMIZE: could avoid call for t == startT, endT
1043            SkDPoint pt = dcubic_xy_at_t(pts, testT);
1044            SkLineParameters tangentPart;
1045            tangentPart.cubicEndPoints(fCurvePart);
1046            double testSide = tangentPart.pointDistance(pt);
1047            if (fabs(bestSide) < fabs(testSide)) {
1048                bestSide = testSide;
1049            }
1050        }
1051        fSide = -bestSide;  // compare sign only
1052        } break;
1053    default:
1054        SkASSERT(0);
1055    }
1056}
1057
1058bool SkOpAngle::small() const {
1059    int min = SkMin32(fStart, fEnd);
1060    int max = SkMax32(fStart, fEnd);
1061    for (int index = min; index < max; ++index) {
1062        const SkOpSpan& mSpan = fSegment->span(index);
1063        if (!mSpan.fSmall) {
1064            return false;
1065        }
1066    }
1067    return true;
1068}
1069
1070bool SkOpAngle::tangentsDiverge(const SkOpAngle& rh, double s0xt0) const {
1071    if (s0xt0 == 0) {
1072        return false;
1073    }
1074    // if the ctrl tangents are not nearly parallel, use them
1075    // solve for opposite direction displacement scale factor == m
1076    // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x
1077    // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1]
1078    // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x)
1079    //                       v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x)
1080    // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x
1081    // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y)
1082    // m = v1.cross(v2) / v1.dot(v2)
1083    const SkDVector* sweep = fSweep;
1084    const SkDVector* tweep = rh.fSweep;
1085    double s0dt0 = sweep[0].dot(tweep[0]);
1086    if (!s0dt0) {
1087        return true;
1088    }
1089    SkASSERT(s0dt0 != 0);
1090    double m = s0xt0 / s0dt0;
1091    double sDist = sweep[0].length() * m;
1092    double tDist = tweep[0].length() * m;
1093    bool useS = fabs(sDist) < fabs(tDist);
1094    double mFactor = fabs(useS ? distEndRatio(sDist) : rh.distEndRatio(tDist));
1095    return mFactor < 5000;  // empirically found limit
1096}
1097
1098SkOpAngleSet::SkOpAngleSet()
1099    : fAngles(NULL)
1100#if DEBUG_ANGLE
1101    , fCount(0)
1102#endif
1103{
1104}
1105
1106SkOpAngleSet::~SkOpAngleSet() {
1107    SkDELETE(fAngles);
1108}
1109
1110SkOpAngle& SkOpAngleSet::push_back() {
1111    if (!fAngles) {
1112        fAngles = SkNEW_ARGS(SkChunkAlloc, (2));
1113    }
1114    void* ptr = fAngles->allocThrow(sizeof(SkOpAngle));
1115    SkOpAngle* angle = (SkOpAngle*) ptr;
1116#if DEBUG_ANGLE
1117    angle->setID(++fCount);
1118#endif
1119    return *angle;
1120}
1121
1122void SkOpAngleSet::reset() {
1123    if (fAngles) {
1124        fAngles->reset();
1125    }
1126}
1127