update pathops to circle sort

src/pathops/SkOpAngle.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #include "SkIntersections.h"
 #include "SkOpAngle.h"
 #include "SkOpSegment.h"
 #include "SkPathOpsCurve.h"
 #include "SkTSort.h"
 
 #if DEBUG_ANGLE
 #include "SkString.h"
-
-static const char funcName[] = "SkOpSegment::operator<";
-static const int bugChar = strlen(funcName) + 1;
 #endif
 
 /* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest
    positive y. The largest angle has a positive x and a zero y. */
 
 #if DEBUG_ANGLE
-    static bool CompareResult(SkString* bugOut, const char* append, bool compare) {
-        bugOut->appendf("%s", append);
-        bugOut->writable_str()[bugChar] = "><"[compare];
-        SkDebugf("%s\n", bugOut->c_str());
+    static bool CompareResult(SkString* bugOut, int append, bool compare) {
+        SkDebugf("%s %c %d\n", bugOut->c_str(), compare ? 'T' : 'F', append);
         return compare;
     }
 
     #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, compare)
 #else
     #define COMPARE_RESULT(append, compare) compare
 #endif
 
-bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const{
+/*             quarter angle values for sector
+
+31   x > 0, y == 0              horizontal line (to the right)
+0    x > 0, y == epsilon        quad/cubic horizontal tangent eventually going +y
+1    x > 0, y > 0, x > y        nearer horizontal angle
+2                  x + e == y   quad/cubic 45 going horiz
+3    x > 0, y > 0, x == y       45 angle
+4                  x == y + e   quad/cubic 45 going vert
+5    x > 0, y > 0, x < y        nearer vertical angle
+6    x == epsilon, y > 0        quad/cubic vertical tangent eventually going +x
+7    x == 0, y > 0              vertical line (to the top)
+
+                                      8  7  6
+                                 9       |       5
+                              10         |          4
+                            11           |            3
+                          12  \          |           / 2
+                         13              |              1
+                        14               |               0
+                        15 --------------+------------- 31
+                        16               |              30
+                         17              |             29
+                          18  /          |          \ 28
+                            19           |           27
+                              20         |         26
+                                 21      |      25
+                                     22 23 24
+*/
+
+// return true if lh < this < rh
+bool SkOpAngle::after(const SkOpAngle* test) const {
+    const SkOpAngle& lh = *test;
+    const SkOpAngle& rh = *lh.fNext;
+    SkASSERT(&lh != &rh);
+#if DEBUG_ANGLE
+    SkString bugOut;
+    bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
+                  " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
+                  " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__,
+            lh.fSegment->debugID(), lh.debugID(), lh.fSectorStart, lh.fSectorEnd,
+            lh.fSegment->t(lh.fStart), lh.fSegment->t(lh.fEnd),
+            fSegment->debugID(), debugID(), fSectorStart, fSectorEnd, fSegment->t(fStart),
+            fSegment->t(fEnd),
+            rh.fSegment->debugID(), rh.debugID(), rh.fSectorStart, rh.fSectorEnd,
+            rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd));
+#endif
+    if (lh.fComputeSector && !const_cast<SkOpAngle&>(lh).computeSector()) {
+        return COMPARE_RESULT(1, true);
+    }
+    if (fComputeSector && !const_cast<SkOpAngle*>(this)->computeSector()) {
+        return COMPARE_RESULT(2, true);
+    }
+    if (rh.fComputeSector && !const_cast<SkOpAngle&>(rh).computeSector()) {
+        return COMPARE_RESULT(3, true);
+    }
+#if DEBUG_ANGLE  // reset bugOut with computed sectors
+    bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
+                  " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
+                  " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__,
+            lh.fSegment->debugID(), lh.debugID(), lh.fSectorStart, lh.fSectorEnd,
+            lh.fSegment->t(lh.fStart), lh.fSegment->t(lh.fEnd),
+            fSegment->debugID(), debugID(), fSectorStart, fSectorEnd, fSegment->t(fStart),
+            fSegment->t(fEnd),
+            rh.fSegment->debugID(), rh.debugID(), rh.fSectorStart, rh.fSectorEnd,
+            rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd));
+#endif
+    bool ltrOverlap = (lh.fSectorMask | rh.fSectorMask) & fSectorMask;
+    bool lrOverlap = lh.fSectorMask & rh.fSectorMask;
+    int lrOrder;  // set to -1 if either order works
+    if (!lrOverlap) {  // no lh/rh sector overlap
+        if (!ltrOverlap) {  // no lh/this/rh sector overlap
+            return COMPARE_RESULT(4,  (lh.fSectorEnd > rh.fSectorStart)
+                    ^ (fSectorStart > lh.fSectorEnd) ^ (fSectorStart > rh.fSectorStart));
+        }
+        int lrGap = (rh.fSectorStart - lh.fSectorStart + 32) & 0x1f;
+        /* A tiny change can move the start +/- 4. The order can only be determined if
+           lr gap is not 12 to 20 or -12 to -20.
+               -31 ..-21      1
+               -20 ..-12     -1
+               -11 .. -1      0
+                 0          shouldn't get here
+                11 ..  1      1
+                12 .. 20     -1
+                21 .. 31      0
+         */
+        lrOrder = lrGap > 20 ? 0 : lrGap > 11 ? -1 : 1;
+    } else {
+        lrOrder = (int) lh.orderable(rh);
+        if (!ltrOverlap) {
+            return COMPARE_RESULT(5, !lrOrder);
+        }
+    }
+    int ltOrder;
+    SkASSERT((lh.fSectorMask & fSectorMask) || (rh.fSectorMask & fSectorMask));
+    if (lh.fSectorMask & fSectorMask) {
+        ltOrder = (int) lh.orderable(*this);
+    } else {
+        int ltGap = (fSectorStart - lh.fSectorStart + 32) & 0x1f;
+        ltOrder = ltGap > 20 ? 0 : ltGap > 11 ? -1 : 1;
+    }
+    int trOrder;
+    if (rh.fSectorMask & fSectorMask) {
+        trOrder = (int) orderable(rh);
+    } else {
+        int trGap = (rh.fSectorStart - fSectorStart + 32) & 0x1f;
+        trOrder = trGap > 20 ? 0 : trGap > 11 ? -1 : 1;
+    }
+    if (lrOrder >= 0 && ltOrder >= 0 && trOrder >= 0) {
+        return COMPARE_RESULT(7, lrOrder ? (ltOrder & trOrder) : (ltOrder | trOrder));
+    }
+    SkASSERT(lrOrder >= 0 || ltOrder >= 0 || trOrder >= 0);
+// There's not enough information to sort. Get the pairs of angles in opposite planes.
+// If an order is < 0, the pair is already in an opposite plane. Check the remaining pairs.
+    // FIXME : once all variants are understood, rewrite this more simply
+    if (ltOrder == 0 && lrOrder == 0) {
+        SkASSERT(trOrder < 0);
+        // FIXME : once this is verified to work, remove one opposite angle call
+        SkDEBUGCODE(bool lrOpposite = lh.oppositePlanes(rh));
+        bool ltOpposite = lh.oppositePlanes(*this);
+        SkASSERT(lrOpposite != ltOpposite);
+        return COMPARE_RESULT(8, ltOpposite);
+    } else if (ltOrder == 1 && trOrder == 0) {
+        SkASSERT(lrOrder < 0);
+        SkDEBUGCODE(bool ltOpposite = lh.oppositePlanes(*this));
+        bool trOpposite = oppositePlanes(rh);
+        SkASSERT(ltOpposite != trOpposite);
+        return COMPARE_RESULT(9, trOpposite);
+    } else if (lrOrder == 1 && trOrder == 1) {
+        SkASSERT(ltOrder < 0);
+        SkDEBUGCODE(bool trOpposite = oppositePlanes(rh));
+        bool lrOpposite = lh.oppositePlanes(rh);
+        SkASSERT(lrOpposite != trOpposite);
+        return COMPARE_RESULT(10, lrOpposite);
+    }
+    if (lrOrder < 0) {
+        if (ltOrder < 0) {
+            return COMPARE_RESULT(11, trOrder);
+        }
+        return COMPARE_RESULT(12, ltOrder);
+    }
+    return COMPARE_RESULT(13, !lrOrder);
+}
+
+// given a line, see if the opposite curve's convex hull is all on one side
+// returns -1=not on one side    0=this CW of test   1=this CCW of test
+int SkOpAngle::allOnOneSide(const SkOpAngle& test) const {
+    SkASSERT(!fIsCurve);
+    SkASSERT(test.fIsCurve);
+    const SkDPoint& origin = test.fCurvePart[0];
+    SkVector line;
+    if (fSegment->verb() == SkPath::kLine_Verb) {
+        const SkPoint* linePts = fSegment->pts();
+        int lineStart = fStart < fEnd ? 0 : 1;
+        line = linePts[lineStart ^ 1] - linePts[lineStart];
+    } else {
+        SkPoint shortPts[2] = { fCurvePart[0].asSkPoint(), fCurvePart[1].asSkPoint() };
+        line = shortPts[1] - shortPts[0];
+    }
+    float crosses[3];
+    SkPath::Verb testVerb = test.fSegment->verb();
+    int iMax = SkPathOpsVerbToPoints(testVerb);
+//    SkASSERT(origin == test.fCurveHalf[0]);
+    const SkDCubic& testCurve = test.fCurvePart;
+//    do {
+        for (int index = 1; index <= iMax; ++index) {
+            float xy1 = (float) (line.fX * (testCurve[index].fY - origin.fY));
+            float xy2 = (float) (line.fY * (testCurve[index].fX - origin.fX));
+            crosses[index - 1] = AlmostEqualUlps(xy1, xy2) ? 0 : xy1 - xy2;
+        }
+        if (crosses[0] * crosses[1] < 0) {
+            return -1;
+        }
+        if (SkPath::kCubic_Verb == testVerb) {
+            if (crosses[0] * crosses[2] < 0 || crosses[1] * crosses[2] < 0) {
+                return -1;
+            }
+        }
+        if (crosses[0]) {
+            return crosses[0] < 0;
+        }
+        if (crosses[1]) {
+            return crosses[1] < 0;
+        }
+        if (SkPath::kCubic_Verb == testVerb && crosses[2]) {
+            return crosses[2] < 0;
+        }
+    fUnorderable = true;
+    return -1;
+}
+
+bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const {
     double absX = fabs(x);
     double absY = fabs(y);
     double length = absX < absY ? absX / 2 + absY : absX + absY / 2;
     int exponent;
     (void) frexp(length, &exponent);
     double epsilon = ldexp(FLT_EPSILON, exponent);
     SkPath::Verb verb = fSegment->verb();
     SkASSERT(verb == SkPath::kQuad_Verb || verb == SkPath::kCubic_Verb);
     // FIXME: the quad and cubic factors are made up ; determine actual values
     double slop = verb == SkPath::kQuad_Verb ? 4 * epsilon : 512 * epsilon;
     double xSlop = slop;
     double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ?
     double x1 = x - xSlop;
     double y1 = y + ySlop;
     double x_ry1 = x1 * ry;
     double rx_y1 = rx * y1;
     *result = x_ry1 < rx_y1;
     double x2 = x + xSlop;
     double y2 = y - ySlop;
     double x_ry2 = x2 * ry;
     double rx_y2 = rx * y2;
     bool less2 = x_ry2 < rx_y2;
     return *result == less2;
 }
 
-/*
-for quads and cubics, set up a parameterized line (e.g. LineParameters )
-for points [0] to [1]. See if point [2] is on that line, or on one side
-or the other. If it both quads' end points are on the same side, choose
-the shorter tangent. If the tangents are equal, choose the better second
-tangent angle
-
-FIXME: maybe I could set up LineParameters lazily
+bool SkOpAngle::checkCrossesZero() const {
+    int start = SkTMin(fSectorStart, fSectorEnd);
+    int end = SkTMax(fSectorStart, fSectorEnd);
+    bool crossesZero = end - start > 16;
+    return crossesZero;
+}
+
+bool SkOpAngle::checkParallel(const SkOpAngle& rh) const {
+    SkDVector scratch[2];
+    const SkDVector* sweep, * tweep;
+    if (!fUnorderedSweep) {
+        sweep = fSweep;
+    } else {
+        scratch[0] = fCurvePart[1] - fCurvePart[0];
+        sweep = &scratch[0];
+    }
+    if (!rh.fUnorderedSweep) {
+        tweep = rh.fSweep;
+    } else {
+        scratch[1] = rh.fCurvePart[1] - rh.fCurvePart[0];
+        tweep = &scratch[1];
+    }
+    double s0xt0 = sweep->crossCheck(*tweep);
+    if (tangentsDiverge(rh, s0xt0)) {
+        return s0xt0 < 0;
+    }
+    SkDVector m0 = fSegment->dPtAtT(midT()) - fCurvePart[0];
+    SkDVector m1 = rh.fSegment->dPtAtT(rh.midT()) - rh.fCurvePart[0];
+    double m0xm1 = m0.crossCheck(m1);
+    if (m0xm1 == 0) {
+        fUnorderable = true;
+        rh.fUnorderable = true;
+        return true;
+    }
+    return m0xm1 < 0;
+}
+
+// the original angle is too short to get meaningful sector information
+// lengthen it until it is long enough to be meaningful or leave it unset if lengthening it
+// would cause it to intersect one of the adjacent angles
+bool SkOpAngle::computeSector() {
+    if (fComputedSector) {
+        // FIXME: logically, this should return !fUnorderable, but doing so breaks testQuadratic51
+        // -- but in general, this code may not work so this may be the least of problems
+        // adding the bang fixes testQuads46x in release, however
+        return fUnorderable;
+    }
+    SkASSERT(fSegment->verb() != SkPath::kLine_Verb && small());
+    fComputedSector = true;
+    int step = fStart < fEnd ? 1 : -1;
+    int limit = step > 0 ? fSegment->count() : -1;
+    int checkEnd = fEnd;
+    do {
+// advance end
+        const SkOpSpan& span = fSegment->span(checkEnd);
+        const SkOpSegment* other = span.fOther;
+        int oCount = other->count();
+        for (int oIndex = 0; oIndex < oCount; ++oIndex) {
+            const SkOpSpan& oSpan = other->span(oIndex);
+            if (oSpan.fOther != fSegment) {
+                continue;
+            }
+            if (oSpan.fOtherIndex == checkEnd) {
+                continue;
+            }
+            if (!approximately_equal(oSpan.fOtherT, span.fT)) {
+                continue;
+            }
+            goto recomputeSector;
+        }
+        checkEnd += step;
+    } while (checkEnd != limit);
+recomputeSector:
+    if (checkEnd == fEnd || checkEnd - step == fEnd) {
+        fUnorderable = true;
+        return false;
+    }
+    fEnd = checkEnd - step;
+    setSpans();
+    setSector();
+    return !fUnorderable;
+}
+
+// returns -1 if overlaps   0 if no overlap cw    1 if no overlap ccw
+int SkOpAngle::convexHullOverlaps(const SkOpAngle& rh) const {
+    const SkDVector* sweep = fSweep;
+    const SkDVector* tweep = rh.fSweep;
+    double s0xs1 = sweep[0].crossCheck(sweep[1]);
+    double s0xt0 = sweep[0].crossCheck(tweep[0]);
+    double s1xt0 = sweep[1].crossCheck(tweep[0]);
+    bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0;
+    double s0xt1 = sweep[0].crossCheck(tweep[1]);
+    double s1xt1 = sweep[1].crossCheck(tweep[1]);
+    tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0;
+    double t0xt1 = tweep[0].crossCheck(tweep[1]);
+    if (tBetweenS) {
+        return -1;
+    }
+    if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) {  // s0 to s1 equals t0 to t1
+        return -1;
+    }
+    bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0;
+    sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0;
+    if (sBetweenT) {
+        return -1;
+    }
+    // if all of the sweeps are in the same half plane, then the order of any pair is enough
+    if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) {
+        return 0;
+    }
+    if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) {
+        return 1;
+    }
+    // if the outside sweeps are greater than 180 degress:
+        // first assume the inital tangents are the ordering
+        // if the midpoint direction matches the inital order, that is enough
+    SkDVector m0 = fSegment->dPtAtT(midT()) - fCurvePart[0];
+    SkDVector m1 = rh.fSegment->dPtAtT(rh.midT()) - rh.fCurvePart[0];
+    double m0xm1 = m0.crossCheck(m1);
+    if (s0xt0 > 0 && m0xm1 > 0) {
+        return 0;
+    }
+    if (s0xt0 < 0 && m0xm1 < 0) {
+        return 1;
+    }
+    if (tangentsDiverge(rh, s0xt0)) {
+        return s0xt0 < 0;
+    }
+    return m0xm1 < 0;
+}
+
+// OPTIMIZATION: longest can all be either lazily computed here or precomputed in setup
+double SkOpAngle::distEndRatio(double dist) const {
+    double longest = 0;
+    const SkOpSegment& segment = *this->segment();
+    int ptCount = SkPathOpsVerbToPoints(segment.verb());
+    const SkPoint* pts = segment.pts();
+    for (int idx1 = 0; idx1 <= ptCount - 1; ++idx1) {
+        for (int idx2 = idx1 + 1; idx2 <= ptCount; ++idx2) {
+            if (idx1 == idx2) {
+                continue;
+            }
+            SkDVector v;
+            v.set(pts[idx2] - pts[idx1]);
+            double lenSq = v.lengthSquared();
+            longest = SkTMax(longest, lenSq);
+        }
+    }
+    return sqrt(longest) / dist;
+}
+
+bool SkOpAngle::endsIntersect(const SkOpAngle& rh) const {
+    SkPath::Verb lVerb = fSegment->verb();
+    SkPath::Verb rVerb = rh.fSegment->verb();
+    int lPts = SkPathOpsVerbToPoints(lVerb);
+    int rPts = SkPathOpsVerbToPoints(rVerb);
+    SkDLine rays[] = {{{fCurvePart[0], rh.fCurvePart[rPts]}},
+            {{fCurvePart[0], fCurvePart[lPts]}}};
+    if (rays[0][1] == rays[1][1]) {
+        return checkParallel(rh);
+    }
+    double smallTs[2] = {-1, -1};
+    bool limited[2] = {false, false};
+    for (int index = 0; index < 2; ++index) {
+        const SkOpSegment& segment = index ? *rh.fSegment : *fSegment;
+        SkIntersections i;
+        (*CurveIntersectRay[index ? rPts : lPts])(segment.pts(), rays[index], &i);
+//      SkASSERT(i.used() >= 1);
+        if (i.used() <= 1) {
+            continue;
+        }
+        double tStart = segment.t(index ? rh.fStart : fStart);
+        double tEnd = segment.t(index ? rh.fEnd : fEnd);
+        bool testAscends = index ? rh.fStart < rh.fEnd : fStart < fEnd;
+        double t = testAscends ? 0 : 1;
+        for (int idx2 = 0; idx2 < i.used(); ++idx2) {
+            double testT = i[0][idx2];
+            if (!approximately_between_orderable(tStart, testT, tEnd)) {
+                continue;
+            }
+            if (approximately_equal_orderable(tStart, testT)) {
+                continue;
+            }
+            smallTs[index] = t = testAscends ? SkTMax(t, testT) : SkTMin(t, testT);
+            limited[index] = approximately_equal_orderable(t, tEnd);
+        }
+    }
+#if 0
+    if (smallTs[0] < 0 && smallTs[1] < 0) {  // if neither ray intersects, do endpoint sort
+        double m0xm1 = 0;
+        if (lVerb == SkPath::kLine_Verb) {
+            SkASSERT(rVerb != SkPath::kLine_Verb);
+            SkDVector m0 = rays[1][1] - fCurvePart[0];
+            SkDPoint endPt;
+            endPt.set(rh.fSegment->pts()[rh.fStart < rh.fEnd ? rPts : 0]);
+            SkDVector m1 = endPt - fCurvePart[0];
+            m0xm1 = m0.crossCheck(m1);
+        }
+        if (rVerb == SkPath::kLine_Verb) {
+            SkDPoint endPt;
+            endPt.set(fSegment->pts()[fStart < fEnd ? lPts : 0]);
+            SkDVector m0 = endPt - fCurvePart[0];
+            SkDVector m1 = rays[0][1] - fCurvePart[0];
+            m0xm1 = m0.crossCheck(m1);
+        }
+        if (m0xm1 != 0) {
+            return m0xm1 < 0;
+        }
+    }
+#endif
+    bool sRayLonger = false;
+    SkDVector sCept = {0, 0};
+    double sCeptT = -1;
+    int sIndex = -1;
+    bool useIntersect = false;
+    for (int index = 0; index < 2; ++index) {
+        if (smallTs[index] < 0) {
+            continue;
+        }
+        const SkOpSegment& segment = index ? *rh.fSegment : *fSegment;
+        const SkDPoint& dPt = segment.dPtAtT(smallTs[index]);
+        SkDVector cept = dPt - rays[index][0];
+        // If this point is on the curve, it should have been detected earlier by ordinary
+        // curve intersection. This may be hard to determine in general, but for lines,
+        // the point could be close to or equal to its end, but shouldn't be near the start.
+        if ((index ? lPts : rPts) == 1) {
+            SkDVector total = rays[index][1] - rays[index][0];
+            if (cept.lengthSquared() * 2 < total.lengthSquared()) {
+                continue;
+            }
+        }
+        SkDVector end = rays[index][1] - rays[index][0];
+        if (cept.fX * end.fX < 0 || cept.fY * end.fY < 0) {
+            continue;
+        }
+        double rayDist = cept.length();
+        double endDist = end.length();
+        bool rayLonger = rayDist > endDist;
+        if (limited[0] && limited[1] && rayLonger) {
+            useIntersect = true;
+            sRayLonger = rayLonger;
+            sCept = cept;
+            sCeptT = smallTs[index];
+            sIndex = index;
+            break;
+        }
+        double delta = fabs(rayDist - endDist);
+        double minX, minY, maxX, maxY;
+        minX = minY = SK_ScalarInfinity;
+        maxX = maxY = -SK_ScalarInfinity;
+        const SkDCubic& curve = index ? rh.fCurvePart : fCurvePart;
+        int ptCount = index ? rPts : lPts;
+        for (int idx2 = 0; idx2 <= ptCount; ++idx2) {
+            minX = SkTMin(minX, curve[idx2].fX);
+            minY = SkTMin(minY, curve[idx2].fY);
+            maxX = SkTMax(maxX, curve[idx2].fX);
+            maxY = SkTMax(maxY, curve[idx2].fY);
+        }
+        double maxWidth = SkTMax(maxX - minX, maxY - minY);
+        delta /= maxWidth;
+        if (delta > 1e-4 && (useIntersect ^= true)) {  // FIXME: move this magic number
+            sRayLonger = rayLonger;
+            sCept = cept;
+            sCeptT = smallTs[index];
+            sIndex = index;
+        }
+    }
+    if (useIntersect) {
+        const SkDCubic& curve = sIndex ? rh.fCurvePart : fCurvePart;
+        const SkOpSegment& segment = sIndex ? *rh.fSegment : *fSegment;
+        double tStart = segment.t(sIndex ? rh.fStart : fStart);
+        SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0];
+        double septDir = mid.crossCheck(sCept);
+        if (!septDir) {
+            return checkParallel(rh);
+        }
+        return sRayLonger ^ (sIndex == 0) ^ (septDir < 0);
+    } else {
+        return checkParallel(rh);
+    }
+}
+
+// Most of the time, the first one can be found trivially by detecting the smallest sector value.
+// If all angles have the same sector value, actual sorting is required.
+const SkOpAngle* SkOpAngle::findFirst() const {
+    const SkOpAngle* best = this;
+    int bestStart = SkTMin(fSectorStart, fSectorEnd);
+    const SkOpAngle* angle = this;
+    while ((angle = angle->fNext) != this) {
+        int angleEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd);
+        if (angleEnd < bestStart) {
+            return angle;    // we wrapped around
+        }
+        int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd);
+        if (bestStart > angleStart) {
+            best = angle;
+            bestStart = angleStart;
+        }
+    }
+    // back up to the first possible angle
+    const SkOpAngle* firstBest = best;
+    angle = best;
+    int bestEnd = SkTMax(best->fSectorStart, best->fSectorEnd);
+    while ((angle = angle->previous()) != firstBest) {
+        if (angle->fStop) {
+            break;
+        }
+        int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd);
+        // angles that are smaller by one aren't necessary better, since the larger may be a line
+        // and the smaller may be a curve that curls to the other side of the line. 
+        if (bestEnd + 1 < angleStart) {
+            return best;
+        }
+        best = angle;
+        bestEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd);
+    }
+    // in the case where all angles are nearly in the same sector, check the order to find the best
+    firstBest = best;
+    angle = best;
+    do {
+        angle = angle->fNext;
+        if (angle->fStop) {
+            return firstBest;
+        }
+        bool orderable = best->orderable(*angle);  // note: may return an unorderable angle
+        if (orderable == 0) {
+            return angle;
+        }
+        best = angle;
+    } while (angle != firstBest);
+    // if the angles are equally ordered, fall back on the initial tangent
+    bool foundBelow = false;
+    while ((angle = angle->fNext)) {
+        SkDVector scratch[2];
+        const SkDVector* sweep;
+        if (!angle->fUnorderedSweep) {
+            sweep = angle->fSweep;
+        } else {
+            scratch[0] = angle->fCurvePart[1] - angle->fCurvePart[0];
+            sweep = &scratch[0];
+        }
+        bool isAbove = sweep->fY <= 0;
+        if (isAbove && foundBelow) {
+            return angle;
+        }
+        foundBelow |= !isAbove;
+        if (angle == firstBest) {
+            return NULL; // should not loop around
+        }
+    }
+    SkASSERT(0);  // should never get here
+    return NULL;
+}
+
+/*      y<0 y==0 y>0  x<0 x==0 x>0 xy<0 xy==0 xy>0
+    0    x                      x               x
+    1    x                      x          x
+    2    x                      x    x
+    3    x                  x        x
+    4    x             x             x
+    5    x             x                   x
+    6    x             x                        x
+    7         x        x                        x
+    8             x    x                        x
+    9             x    x                   x
+    10            x    x             x
+    11            x         x        x
+    12            x             x    x
+    13            x             x          x
+    14            x             x               x
+    15        x                 x               x
 */
-bool SkOpAngle::operator<(const SkOpAngle& rh) const {  // this/lh: left-hand; rh: right-hand
-    double y = dy();
-    double ry = rh.dy();
+int SkOpAngle::findSector(SkPath::Verb verb, double x, double y) const {
+    double absX = fabs(x);
+    double absY = fabs(y);
+    double xy = SkPath::kLine_Verb == verb || !AlmostEqualUlps(absX, absY) ? absX - absY : 0;
+    // If there are four quadrants and eight octants, and since the Latin for sixteen is sedecim,
+    // one could coin the term sedecimant for a space divided into 16 sections.
+   // http://english.stackexchange.com/questions/133688/word-for-something-partitioned-into-16-parts
+    static const int sedecimant[3][3][3] = {
+    //       y<0           y==0           y>0
+    //   x<0 x==0 x>0  x<0 x==0 x>0  x<0 x==0 x>0
+        {{ 4,  3,  2}, { 7, -1, 15}, {10, 11, 12}},  // abs(x) <  abs(y)
+        {{ 5, -1,  1}, {-1, -1, -1}, { 9, -1, 13}},  // abs(x) == abs(y)
+        {{ 6,  3,  0}, { 7, -1, 15}, { 8, 11, 14}},  // abs(x) >  abs(y)
+    };
+    int sector = sedecimant[(xy >= 0) + (xy > 0)][(y >= 0) + (y > 0)][(x >= 0) + (x > 0)] * 2 + 1;
+    SkASSERT(SkPath::kLine_Verb == verb || sector >= 0);
+    return sector;
+}
+
+// OPTIMIZE: if this loops to only one other angle, after first compare fails, insert on other side
+// OPTIMIZE: return where insertion succeeded. Then, start next insertion on opposite side
+void SkOpAngle::insert(SkOpAngle* angle) {
+    if (angle->fNext) {
+        if (loopCount() >= angle->loopCount()) {
+            if (!merge(angle)) {
+                return;
+            }
+        } else if (fNext) {
+            if (!angle->merge(this)) {
+                return;
+            }
+        } else {
+            angle->insert(this);
+        }
+        return;
+    }
+    bool singleton = NULL == fNext;
+    if (singleton) {
+        fNext = this;
+    }
+    SkOpAngle* next = fNext;
+    if (next->fNext == this) {
+        if (singleton || angle->after(this)) {
+            this->fNext = angle;
+            angle->fNext = next;
+        } else {
+            next->fNext = angle;
+            angle->fNext = this;
+        }
+        debugValidateNext();
+        return;
+    }
+    SkOpAngle* last = this;
+    do {
+        SkASSERT(last->fNext == next);
+        if (angle->after(last)) {
+            last->fNext = angle;
+            angle->fNext = next;
+            debugValidateNext();
+            return;
+        }
+        last = next;
+        next = next->fNext;
+        if (last == this && next->fUnorderable) {
+            fUnorderable = true;
+            return;
+        }
+        SkASSERT(last != this);
+    } while (true);
+}
+
+bool SkOpAngle::isHorizontal() const {
+    return !fIsCurve && fSweep[0].fY == 0;
+}
+
+SkOpSpan* SkOpAngle::lastMarked() const {
+    if (fLastMarked) {
+        if (fLastMarked->fChased) {
+            return NULL;
+        }
+        fLastMarked->fChased = true;
+    }
+    return fLastMarked;
+}
+
+int SkOpAngle::loopCount() const {
+    int count = 0;
+    const SkOpAngle* first = this;
+    const SkOpAngle* next = this;
+    do {
+        next = next->fNext;
+        ++count;
+    } while (next && next != first);
+    return count;
+}
+
+// OPTIMIZATION: can this be done better in after when angles are sorted?
+void SkOpAngle::markStops() {
+    SkOpAngle* angle = this;
+    int lastEnd = SkTMax(fSectorStart, fSectorEnd);
+    do {
+        angle = angle->fNext;
+        int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd);
+        // angles that are smaller by one aren't necessary better, since the larger may be a line
+        // and the smaller may be a curve that curls to the other side of the line. 
+        if (lastEnd + 1 < angleStart) {
+            angle->fStop = true;
+        }
+        lastEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd);
+    } while (angle != this);
+}
+
+bool SkOpAngle::merge(SkOpAngle* angle) {
+    SkASSERT(fNext);
+    SkASSERT(angle->fNext);
+    SkOpAngle* working = angle;
+    do {
+        if (this == working) {
+            return false;
+        }
+        working = working->fNext;
+    } while (working != angle);
+    do {
+        SkOpAngle* next = working->fNext;
+        working->fNext = NULL;
+        insert(working);
+        working = next;
+    } while (working != angle);
+    // it's likely that a pair of the angles are unorderable
 #if DEBUG_ANGLE
-    SkString bugOut;
-    bugOut.printf("%s _ id=%d segId=%d tStart=%1.9g tEnd=%1.9g"
-        " | id=%d segId=%d tStart=%1.9g tEnd=%1.9g ", funcName,
-        fID, fSegment->debugID(), fSegment->t(fStart), fSegment->t(fEnd),
-        rh.fID, rh.fSegment->debugID(), rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd));
+    SkOpAngle* last = angle;
+    working = angle->fNext;
+    do {
+        SkASSERT(last->fNext == working);
+        last->fNext = working->fNext;
+        SkASSERT(working->after(last));
+        last->fNext = working;
+        last = working;
+        working = working->fNext;
+    } while (last != angle);
 #endif
-    double y_ry = y * ry;
-    if (y_ry < 0) {  // if y's are opposite signs, we can do a quick return
-        return COMPARE_RESULT("1 y * ry < 0", y < 0);
-    }
-    // at this point, both y's must be the same sign, or one (or both) is zero
-    double x = dx();
-    double rx = rh.dx();
-    if (x * rx < 0) {  // if x's are opposite signs, use y to determine first or second half
-        if (y < 0 && ry < 0) {  // if y's are negative, lh x is smaller if positive
-            return COMPARE_RESULT("2 x_rx < 0 && y < 0 ...", x > 0);
-        }
-        if (y >= 0 && ry >= 0) {  // if y's are zero or positive, lh x is smaller if negative
-            return COMPARE_RESULT("3 x_rx < 0 && y >= 0 ...", x < 0);
-        }
-        SkASSERT((y == 0) ^ (ry == 0));  // if one y is zero and one is negative, neg y is smaller
-        return COMPARE_RESULT("4 x_rx < 0 && y == 0 ...", y < 0);
-    }
-    // at this point, both x's must be the same sign, or one (or both) is zero
-    if (y_ry == 0) { // if either y is zero
-        if (y + ry < 0) { // if the other y is less than zero, it must be smaller
-            return COMPARE_RESULT("5 y_ry == 0 && y + ry < 0", y < 0);
-        }
-        if (y + ry > 0) { // if a y is greater than zero and an x is positive,  non zero is smaller
-            return COMPARE_RESULT("6 y_ry == 0 && y + ry > 0", (x + rx > 0) ^ (y == 0));
-        }
-        // at this point, both y's are zero, so lines are coincident or one is degenerate
-        SkASSERT(x * rx != 0);  // and a degenerate line should haven't gotten this far
-    }
-    // see if either curve can be lengthened before trying the tangent
-    if (fSegment->other(fEnd) != rh.fSegment  // tangents not absolutely identical
-            && rh.fSegment->other(rh.fEnd) != fSegment
-            && y != -DBL_EPSILON
-            && ry != -DBL_EPSILON) {  // and not intersecting
-        SkOpAngle longer = *this;
-        SkOpAngle rhLonger = rh;
-        if ((longer.lengthen(rh) | rhLonger.lengthen(*this))  // lengthen both
-                && (fUnorderable || !longer.fUnorderable)
-                && (rh.fUnorderable || !rhLonger.fUnorderable)) {
+    debugValidateNext();
+    return true;
+}
+
+double SkOpAngle::midT() const {
+    return (fSegment->t(fStart) + fSegment->t(fEnd)) / 2;
+}
+
+bool SkOpAngle::oppositePlanes(const SkOpAngle& rh) const {
+    int startSpan = abs(rh.fSectorStart - fSectorStart);
+    return startSpan >= 8;
+}
+
+bool SkOpAngle::orderable(const SkOpAngle& rh) const {
+    int result;
+    if (!fIsCurve) {
+        if (!rh.fIsCurve) {
+            double leftX = fTangentHalf.dx();
+            double leftY = fTangentHalf.dy();
+            double rightX = rh.fTangentHalf.dx();
+            double rightY = rh.fTangentHalf.dy();
+            double x_ry = leftX * rightY;
+            double rx_y = rightX * leftY;
+            if (x_ry == rx_y) {
+                if (leftX * rightX < 0 || leftY * rightY < 0) {
+                    return true;  // exactly 180 degrees apart
+                }
+                goto unorderable;
+            }
+            SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- worth finding earlier
+            return x_ry < rx_y;
+        }
+        if ((result = allOnOneSide(rh)) >= 0) {
+            return result;
+        }
+        if (fUnorderable || approximately_zero(rh.fSide)) {
+            goto unorderable;
+        }
+    } else if (!rh.fIsCurve) {
+        if ((result = rh.allOnOneSide(*this)) >= 0) {
+            return !result;
+        }
+        if (rh.fUnorderable || approximately_zero(fSide)) {
+            goto unorderable;
+        }
+    }
+    if ((result = convexHullOverlaps(rh)) >= 0) {
+        return result;
+    }
+    return endsIntersect(rh);
+unorderable:
+    fUnorderable = true;
+    rh.fUnorderable = true;
+    return true;
+}
+
+// OPTIMIZE: if this shows up in a profile, add a previous pointer
+// as is, this should be rarely called
+SkOpAngle* SkOpAngle::previous() const {
+    SkOpAngle* last = fNext;
+    do {
+        SkOpAngle* next = last->fNext;
+        if (next == this) {
+            return last;
+        }
+        last = next;
+    } while (true);
+}
+
+void SkOpAngle::set(const SkOpSegment* segment, int start, int end) {
 #if DEBUG_ANGLE
-            bugOut.prepend("  ");
+    fID = 0;
 #endif
-            return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger);
-        }
-    }
-    SkPath::Verb verb = fSegment->verb();
-    SkPath::Verb rVerb = rh.fSegment->verb();
-    if (y_ry != 0) { // if they aren't coincident, look for a stable cross product
-        // at this point, y's are the same sign, neither is zero
-        //   and x's are the same sign, or one (or both) is zero
-        double x_ry = x * ry;
-        double rx_y = rx * y;
-        if (!fComputed && !rh.fComputed) {
-            if (!SkDLine::NearRay(x, y, rx, ry) && x_ry != rx_y) {
-                return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y);
-            }
-            if (fSide2 == 0 && rh.fSide2 == 0) {
-                return COMPARE_RESULT("7a !fComputed && !rh.fComputed", x_ry < rx_y);
-            }
-        } else {
-            // if the vector was a result of subdividing a curve, see if it is stable
-            bool sloppy1 = x_ry < rx_y;
-            bool sloppy2 = !sloppy1;
-            if ((!fComputed || calcSlop(x, y, rx, ry, &sloppy1))
-                    && (!rh.fComputed || rh.calcSlop(rx, ry, x, y, &sloppy2))
-                    && sloppy1 != sloppy2) {
-                return COMPARE_RESULT("8 CalcSlop(x, y ...", sloppy1);
-            }
-        }
-    }
-    if (fSide2 * rh.fSide2 == 0) {  // one is zero
-#if DEBUG_ANGLE
-        if (fSide2 == rh.fSide2 && y_ry) {  // both is zero; coincidence was undetected
-            SkDebugf("%s coincidence!\n", __FUNCTION__);
-        }
-#endif
-        return COMPARE_RESULT("9a fSide2 * rh.fSide2 == 0 ...", fSide2 < rh.fSide2);
-    }
-    // at this point, the initial tangent line is nearly coincident
-    // see if edges curl away from each other
-    if (fSide * rh.fSide < 0 && (!approximately_zero(fSide) || !approximately_zero(rh.fSide))) {
-        return COMPARE_RESULT("9b fSide * rh.fSide < 0 ...", fSide < rh.fSide);
-    }
-    if (fUnsortable || rh.fUnsortable) {
-        // even with no solution, return a stable sort
-        return COMPARE_RESULT("11 fUnsortable || rh.fUnsortable", this < &rh);
-    }
-    if ((verb == SkPath::kLine_Verb && approximately_zero(y) && approximately_zero(x))
-            || (rVerb == SkPath::kLine_Verb
-            && approximately_zero(ry) && approximately_zero(rx))) {
-        // See general unsortable comment below. This case can happen when
-        // one line has a non-zero change in t but no change in x and y.
-        fUnsortable = true;
-        return COMPARE_RESULT("12 verb == SkPath::kLine_Verb ...", this < &rh);
-    }
-    if (fSegment->isTiny(this) || rh.fSegment->isTiny(&rh)) {
-        fUnsortable = true;
-        return COMPARE_RESULT("13 verb == fSegment->isTiny(this) ...", this < &rh);
-    }
-    SkASSERT(verb >= SkPath::kQuad_Verb);
-    SkASSERT(rVerb >= SkPath::kQuad_Verb);
-    // FIXME: until I can think of something better, project a ray from the
-    // end of the shorter tangent to midway between the end points
-    // through both curves and use the resulting angle to sort
-    // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive
-    double len = fTangentPart.normalSquared();
-    double rlen = rh.fTangentPart.normalSquared();
-    SkDLine ray;
-    SkIntersections i, ri;
-    int roots, rroots;
-    bool flip = false;
-    bool useThis;
-    bool leftLessThanRight = fSide > 0;
-    do {
-        useThis = (len < rlen) ^ flip;
-        const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart;
-        SkPath::Verb partVerb = useThis ? verb : rVerb;
-        ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ?
-            part[2] : part[1];
-        ray[1] = SkDPoint::Mid(part[0], part[SkPathOpsVerbToPoints(partVerb)]);
-        SkASSERT(ray[0] != ray[1]);
-        roots = (i.*CurveRay[SkPathOpsVerbToPoints(verb)])(fSegment->pts(), ray);
-        rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rVerb)])(rh.fSegment->pts(), ray);
-    } while ((roots == 0 || rroots == 0) && (flip ^= true));
-    if (roots == 0 || rroots == 0) {
-        // FIXME: we don't have a solution in this case. The interim solution
-        // is to mark the edges as unsortable, exclude them from this and
-        // future computations, and allow the returned path to be fragmented
-        fUnsortable = true;
-        return COMPARE_RESULT("roots == 0 || rroots == 0", this < &rh);
-    }
-    SkASSERT(fSide != 0 && rh.fSide != 0);
-    if (fSide * rh.fSide < 0) {
-        fUnsortable = true;
-        return COMPARE_RESULT("14 fSide * rh.fSide < 0", this < &rh);
-    }
-    SkDPoint lLoc;
-    double best = SK_ScalarInfinity;
-#if DEBUG_SORT
-    SkDebugf("lh=%d rh=%d use-lh=%d ray={{%1.9g,%1.9g}, {%1.9g,%1.9g}} %c\n",
-            fSegment->debugID(), rh.fSegment->debugID(), useThis, ray[0].fX, ray[0].fY,
-            ray[1].fX, ray[1].fY, "-+"[fSide > 0]);
-#endif
-    for (int index = 0; index < roots; ++index) {
-        SkDPoint loc = i.pt(index);
-        SkDVector dxy = loc - ray[0];
-        double dist = dxy.lengthSquared();
-#if DEBUG_SORT
-        SkDebugf("best=%1.9g dist=%1.9g loc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n",
-                best, dist, loc.fX, loc.fY, dxy.fX, dxy.fY);
-#endif
-        if (best > dist) {
-            lLoc = loc;
-            best = dist;
-        }
-    }
-    flip = false;
-    SkDPoint rLoc;
-    for (int index = 0; index < rroots; ++index) {
-        rLoc = ri.pt(index);
-        SkDVector dxy = rLoc - ray[0];
-        double dist = dxy.lengthSquared();
-#if DEBUG_SORT
-        SkDebugf("best=%1.9g dist=%1.9g %c=(fSide < 0) rLoc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n",
-                best, dist, "><"[fSide < 0], rLoc.fX, rLoc.fY, dxy.fX, dxy.fY);
-#endif
-        if (best > dist) {
-            flip = true;
-            break;
-        }
-    }
-    if (flip) {
-        leftLessThanRight = !leftLessThanRight;
-    }
-    return COMPARE_RESULT("15 leftLessThanRight", leftLessThanRight);
-}
-
-bool SkOpAngle::isHorizontal() const {
-    return dy() == 0 && fSegment->verb() == SkPath::kLine_Verb;
-}
-
-// lengthen cannot cross opposite angle
-bool SkOpAngle::lengthen(const SkOpAngle& opp) {
-    if (fSegment->other(fEnd) == opp.fSegment) {
-        return false;
-    }
-    // FIXME: make this a while loop instead and make it as large as possible?
-    int newEnd = fEnd;
-    if (fStart < fEnd ? ++newEnd < fSegment->count() : --newEnd >= 0) {
-        fEnd = newEnd;
-        setSpans();
-        return true;
-    }
-    return false;
-}
-
-void SkOpAngle::set(const SkOpSegment* segment, int start, int end) {
     fSegment = segment;
     fStart = start;
     fEnd = end;
+    fNext = NULL;
+    fComputeSector = fComputedSector = false;
+    fStop = false;
     setSpans();
+    setSector();
+}
+
+void SkOpAngle::setCurveHullSweep() {
+    fUnorderedSweep = false;
+    fSweep[0] = fCurvePart[1] - fCurvePart[0];
+    if (SkPath::kLine_Verb == fSegment->verb()) {
+        fSweep[1] = fSweep[0];
+        return;
+    }
+    fSweep[1] = fCurvePart[2] - fCurvePart[0];
+    if (SkPath::kCubic_Verb != fSegment->verb()) {
+        if (!fSweep[0].fX && !fSweep[0].fY) {
+            fSweep[0] = fSweep[1];
+        }
+        return;
+    }
+    SkDVector thirdSweep = fCurvePart[3] - fCurvePart[0];
+    if (fSweep[0].fX == 0 && fSweep[0].fY == 0) {
+        fSweep[0] = fSweep[1];
+        fSweep[1] = thirdSweep;
+        if (fSweep[0].fX == 0 && fSweep[0].fY == 0) {
+            fSweep[0] = fSweep[1];
+            fCurvePart[1] = fCurvePart[3];
+            fIsCurve = false;
+        }
+        return;
+    }
+    double s1x3 = fSweep[0].crossCheck(thirdSweep);
+    double s3x2 = thirdSweep.crossCheck(fSweep[1]);
+    if (s1x3 * s3x2 >= 0) {  // if third vector is on or between first two vectors
+        return;
+    }
+    double s2x1 = fSweep[1].crossCheck(fSweep[0]);
+    // FIXME: If the sweep of the cubic is greater than 180 degrees, we're in trouble
+    // probably such wide sweeps should be artificially subdivided earlier so that never happens
+    SkASSERT(s1x3 * s2x1 < 0 || s1x3 * s3x2 < 0);
+    if (s3x2 * s2x1 < 0) {
+        SkASSERT(s2x1 * s1x3 > 0);
+        fSweep[0] = fSweep[1];
+        fUnorderedSweep = true;
+    }
+    fSweep[1] = thirdSweep;
+}
+
+void SkOpAngle::setSector() {
+    SkPath::Verb verb = fSegment->verb();
+    if (SkPath::kLine_Verb != verb && small()) {
+        fSectorStart = fSectorEnd = -1;
+        fSectorMask = 0;
+        fComputeSector = true;  // can't determine sector until segment length can be found
+        return;
+    }
+    fSectorStart = findSector(verb, fSweep[0].fX, fSweep[0].fY);
+    if (!fIsCurve) {  // if it's a line or line-like, note that both sectors are the same
+        SkASSERT(fSectorStart >= 0);
+        fSectorEnd = fSectorStart;
+        fSectorMask = 1 << fSectorStart;
+        return;
+    }
+    SkASSERT(SkPath::kLine_Verb != verb);
+    fSectorEnd = findSector(verb, fSweep[1].fX, fSweep[1].fY);
+    if (fSectorEnd == fSectorStart) {
+        SkASSERT((fSectorStart & 3) != 3);  // if the sector has no span, it can't be an exact angle
+        fSectorMask = 1 << fSectorStart;
+        return;
+    }
+    bool crossesZero = checkCrossesZero();
+    int start = SkTMin(fSectorStart, fSectorEnd);
+    bool curveBendsCCW = (fSectorStart == start) ^ crossesZero;
+    // bump the start and end of the sector span if they are on exact compass points
+    if ((fSectorStart & 3) == 3) {
+        fSectorStart = (fSectorStart + (curveBendsCCW ? 1 : 31)) & 0x1f;
+    }
+    if ((fSectorEnd & 3) == 3) {
+        fSectorEnd = (fSectorEnd + (curveBendsCCW ? 31 : 1)) & 0x1f;
+    }
+    crossesZero = checkCrossesZero();
+    start = SkTMin(fSectorStart, fSectorEnd);
+    int end = SkTMax(fSectorStart, fSectorEnd);
+    if (!crossesZero) {
+        fSectorMask = (unsigned) -1 >> (31 - end + start) << start;
+    } else {
+        fSectorMask = (unsigned) -1 >> (31 - start) | (-1 << end);
+    }
 }
 
 void SkOpAngle::setSpans() {
     fUnorderable = fSegment->isTiny(this);
     fLastMarked = NULL;
-    fUnsortable = false;
     const SkPoint* pts = fSegment->pts();
-    if (fSegment->verb() != SkPath::kLine_Verb) {
-        fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart);
-        fSegment->subDivide(fStart, fStart < fEnd ? fSegment->count() - 1 : 0, &fCurveHalf);
-    }
-    // FIXME: slight errors in subdivision cause sort trouble later on. As an experiment, try
-    // rounding the curve part to float precision here
-    // fCurvePart.round(fSegment->verb());
-    switch (fSegment->verb()) {
+    SkDEBUGCODE(fCurvePart[2].fX = fCurvePart[2].fY = fCurvePart[3].fX = fCurvePart[3].fY
+            = SK_ScalarNaN);
+    fSegment->subDivide(fStart, fEnd, &fCurvePart);
+    setCurveHullSweep();
+    const SkPath::Verb verb = fSegment->verb();
+    if (verb != SkPath::kLine_Verb
+            && !(fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0)) {
+        SkDLine lineHalf;
+        lineHalf[0].set(fCurvePart[0].asSkPoint());
+        lineHalf[1].set(fCurvePart[SkPathOpsVerbToPoints(verb)].asSkPoint());
+        fTangentHalf.lineEndPoints(lineHalf);
+        fSide = 0;
+    }
+    switch (verb) {
     case SkPath::kLine_Verb: {
         SkASSERT(fStart != fEnd);
-        fCurvePart[0].set(pts[fStart > fEnd]);
-        fCurvePart[1].set(pts[fStart < fEnd]);
-        fComputed = false;
-        // OPTIMIZATION: for pure line compares, we never need fTangentPart.c
-        fTangentPart.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart));
+        const SkPoint& cP1 = pts[fStart < fEnd];
+        SkDLine lineHalf;
+        lineHalf[0].set(fSegment->span(fStart).fPt);
+        lineHalf[1].set(cP1);
+        fTangentHalf.lineEndPoints(lineHalf);
         fSide = 0;
-        fSide2 = 0;
-        } break;
+        fIsCurve = false;
+        } return;
     case SkPath::kQuad_Verb: {
-        fSide2 = -fTangentHalf.quadPart(*SkTCast<SkDQuad*>(&fCurveHalf));
-        SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart);
-        fTangentPart.quadEndPoints(quad);
-        fSide = -fTangentPart.pointDistance(fCurvePart[2]);  // not normalized -- compare sign only
-        if (fComputed && dx() > 0 && approximately_zero(dy())) {
-            SkDCubic origCurve; // can't use segment's curve in place since it may be flipped
-            int last = fSegment->count() - 1;
-            fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve);
-            SkLineParameters origTan;
-            origTan.quadEndPoints(*SkTCast<SkDQuad*>(&origCurve));
-            if (origTan.dx() <= 0
-                    || (dy() != origTan.dy() && dy() * origTan.dy() <= 0)) { // signs match?
-                fUnorderable = true;
-                return;
-            }
-        }
+        SkLineParameters tangentPart;
+        SkDQuad& quad2 = *SkTCast<SkDQuad*>(&fCurvePart);
+        (void) tangentPart.quadEndPoints(quad2);
+        fSide = -tangentPart.pointDistance(fCurvePart[2]);  // not normalized -- compare sign only
         } break;
     case SkPath::kCubic_Verb: {
-        double startT = fSegment->t(fStart);
-        fSide2 = -fTangentHalf.cubicPart(fCurveHalf);
-        fTangentPart.cubicEndPoints(fCurvePart);
+        SkLineParameters tangentPart;
+        (void) tangentPart.cubicPart(fCurvePart);
+        fSide = -tangentPart.pointDistance(fCurvePart[3]);
         double testTs[4];
         // OPTIMIZATION: keep inflections precomputed with cubic segment?
         int testCount = SkDCubic::FindInflections(pts, testTs);
+        double startT = fSegment->t(fStart);
         double endT = fSegment->t(fEnd);
         double limitT = endT;
         int index;
         for (index = 0; index < testCount; ++index) {
-            if (!between(startT, testTs[index], limitT)) {
+            if (!::between(startT, testTs[index], limitT)) {
                 testTs[index] = -1;
             }
         }
         testTs[testCount++] = startT;
         testTs[testCount++] = endT;
         SkTQSort<double>(testTs, &testTs[testCount - 1]);
         double bestSide = 0;
         int testCases = (testCount << 1) - 1;
         index = 0;
         while (testTs[index] < 0) {
             ++index;
         }
         index <<= 1;
         for (; index < testCases; ++index) {
             int testIndex = index >> 1;
             double testT = testTs[testIndex];
             if (index & 1) {
                 testT = (testT + testTs[testIndex + 1]) / 2;
             }
             // OPTIMIZE: could avoid call for t == startT, endT
             SkDPoint pt = dcubic_xy_at_t(pts, testT);
-            double testSide = fTangentPart.pointDistance(pt);
+            SkLineParameters tangentPart;
+            tangentPart.cubicEndPoints(fCurvePart);
+            double testSide = tangentPart.pointDistance(pt);
             if (fabs(bestSide) < fabs(testSide)) {
                 bestSide = testSide;
             }
         }
         fSide = -bestSide;  // compare sign only
-        SkASSERT(fSide == 0 || fSide2 != 0);
-        if (fComputed && dx() > 0 && approximately_zero(dy())) {
-            SkDCubic origCurve; // can't use segment's curve in place since it may be flipped
-            int last = fSegment->count() - 1;
-            fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve);
-            SkDCubicPair split = origCurve.chopAt(startT);
-            SkLineParameters splitTan;
-            splitTan.cubicEndPoints(fStart < fEnd ? split.second() : split.first());
-            if (splitTan.dx() <= 0) {
-                fUnorderable = true;
-                fUnsortable = fSegment->isTiny(this);
-                return;
-            }
-            // if one is < 0 and the other is >= 0
-            if (dy() * splitTan.dy() < 0) {
-                fUnorderable = true;
-                fUnsortable = fSegment->isTiny(this);
-                return;
-            }
-        }
         } break;
     default:
         SkASSERT(0);
     }
-    if ((fUnsortable = approximately_zero(dx()) && approximately_zero(dy()))) {
-        return;
-    }
-    if (fSegment->verb() == SkPath::kLine_Verb) {
-        return;
-    }
-    SkASSERT(fStart != fEnd);
-    int smaller = SkMin32(fStart, fEnd);
-    int larger = SkMax32(fStart, fEnd);
-    while (smaller < larger && fSegment->span(smaller).fTiny) {
-        ++smaller;
-    }
-    if (precisely_equal(fSegment->span(smaller).fT, fSegment->span(larger).fT)) {
-    #if DEBUG_UNSORTABLE
-        SkPoint iPt = fSegment->xyAtT(fStart);
-        SkPoint ePt = fSegment->xyAtT(fEnd);
-        SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
-            fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
-    #endif
-        fUnsortable = true;
-        return;
-    }
-    fUnsortable = fStart < fEnd ? fSegment->span(smaller).fUnsortableStart
-            : fSegment->span(larger).fUnsortableEnd;
-#if DEBUG_UNSORTABLE
-    if (fUnsortable) {
-        SkPoint iPt = fSegment->xyAtT(smaller);
-        SkPoint ePt = fSegment->xyAtT(larger);
-        SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
-                smaller, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
-    }
-#endif
-    return;
 }
 
-#ifdef SK_DEBUG
-void SkOpAngle::dump() const {
-    const SkOpSpan& spanStart = fSegment->span(fStart);
-    const SkOpSpan& spanEnd = fSegment->span(fEnd);
-    const SkOpSpan& spanMin = fStart < fEnd ? spanStart : spanEnd;
-    SkDebugf("id=%d (%1.9g,%1.9g) start=%d (%1.9g) end=%d (%1.9g) sumWind=",
-            fSegment->debugID(), fSegment->xAtT(fStart), fSegment->yAtT(fStart),
-            fStart, spanStart.fT, fEnd, spanEnd.fT);
-    SkPathOpsDebug::WindingPrintf(spanMin.fWindSum);
-    SkDebugf(" oppWind=");
-    SkPathOpsDebug::WindingPrintf(spanMin.fOppSum),
-    SkDebugf(" done=%d\n", spanMin.fDone);
+bool SkOpAngle::small() const {
+    int min = SkMin32(fStart, fEnd);
+    int max = SkMax32(fStart, fEnd);
+    for (int index = min; index < max; ++index) {
+        const SkOpSpan& mSpan = fSegment->span(index);
+        if (!mSpan.fSmall) {
+            return false;
+        }
+    }
+    return true;
 }
-#endif
+
+bool SkOpAngle::tangentsDiverge(const SkOpAngle& rh, double s0xt0) const {
+    if (s0xt0 == 0) {
+        return false;
+    }
+    // if the ctrl tangents are not nearly parallel, use them
+    // solve for opposite direction displacement scale factor == m
+    // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x
+    // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1]
+    // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x)
+    //                       v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x)
+    // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x
+    // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y)
+    // m = v1.cross(v2) / v1.dot(v2)
+    const SkDVector* sweep = fSweep;
+    const SkDVector* tweep = rh.fSweep;
+    double s0dt0 = sweep[0].dot(tweep[0]);
+    if (!s0dt0) {
+        return true;
+    }
+    SkASSERT(s0dt0 != 0);
+    double m = s0xt0 / s0dt0;
+    double sDist = sweep[0].length() * m;
+    double tDist = tweep[0].length() * m;
+    bool useS = fabs(sDist) < fabs(tDist);
+    double mFactor = fabs(useS ? distEndRatio(sDist) : rh.distEndRatio(tDist));
+    return mFactor < 5000;  // empirically found limit
+}