Mike R: please sanity check SkPostConfig.h

Mike K: please sanity check Test.cpp and skia_test.cpp

Feel free to look at the rest, but I don't expect any in depth review of path ops innards.

Path Ops first iteration used QuickSort to order segments radiating from an intersection to compute the winding rule.

This revision uses a circular sort instead. Breaking out the circular sort into its own long-lived structure (SkOpAngle) allows doing less work and provides a home for caching additional sorting data.

The circle sort is more stable than the former sort, has a robust ordering and fewer exceptions. It finds unsortable ordering less often. It is less reliant on the initial curve  tangent, using convex hulls instead whenever it can.

Additional debug validation makes sure that the computed structures are self-consistent. A new visualization tool helps verify that the angle ordering is correct.

The 70+M tests pass with this change on Windows, Mac, Linux 32 and Linux 64 in debug and release.

R=mtklein@google.com, reed@google.com

Author: caryclark@google.com

Review URL: https://codereview.chromium.org/131103009

git-svn-id: http://skia.googlecode.com/svn/trunk@14183 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 913 insertions, 301 deletions

diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index 742a161f6c..364ab1bf1f 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -12,19 +12,14 @@
 
 #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;
     }
 
@@ -33,7 +28,197 @@ static const int bugChar = strlen(funcName) + 1;
     #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;
@@ -59,280 +244,733 @@ bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result)
     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
+bool SkOpAngle::checkCrossesZero() const {
+    int start = SkTMin(fSectorStart, fSectorEnd);
+    int end = SkTMax(fSectorStart, fSectorEnd);
+    bool crossesZero = end - start > 16;
+    return crossesZero;
+}
 
-FIXME: maybe I could set up LineParameters lazily
-*/
-bool SkOpAngle::operator<(const SkOpAngle& rh) const {  // this/lh: left-hand; rh: right-hand
-    double y = dy();
-    double ry = rh.dy();
-#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));
-#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)) {
-#if DEBUG_ANGLE
-            bugOut.prepend("  ");
-#endif
-            return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger);
+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;
     }
-    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);
+    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;
             }
-            if (fSide2 == 0 && rh.fSide2 == 0) {
-                return COMPARE_RESULT("7a !fComputed && !rh.fComputed", x_ry < rx_y);
+            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;
             }
-        } 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 (approximately_equal_orderable(tStart, testT)) {
+                continue;
             }
+            smallTs[index] = t = testAscends ? SkTMax(t, testT) : SkTMin(t, testT);
+            limited[index] = approximately_equal_orderable(t, tEnd);
         }
     }
-    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__);
+#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
-        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;
+    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
+*/
+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;
     }
-    if (flip) {
-        leftLessThanRight = !leftLessThanRight;
+    bool singleton = NULL == fNext;
+    if (singleton) {
+        fNext = this;
     }
-    return COMPARE_RESULT("15 leftLessThanRight", leftLessThanRight);
+    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 dy() == 0 && fSegment->verb() == SkPath::kLine_Verb;
+    return !fIsCurve && fSweep[0].fY == 0;
 }
 
-// lengthen cannot cross opposite angle
-bool SkOpAngle::lengthen(const SkOpAngle& opp) {
-    if (fSegment->other(fEnd) == opp.fSegment) {
-        return false;
+SkOpSpan* SkOpAngle::lastMarked() const {
+    if (fLastMarked) {
+        if (fLastMarked->fChased) {
+            return NULL;
+        }
+        fLastMarked->fChased = true;
     }
-    // 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 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
+    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
+    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;
+        }
     }
-    return false;
+    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
+    fID = 0;
+#endif
     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;
             }
         }
@@ -354,82 +992,56 @@ void SkOpAngle::setSpans() {
             }
             // 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);
+}
+
+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;
+        }
     }
-#endif
-    return;
+    return true;
 }
 
-#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::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
 }
-#endif