pathops version two

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"
-#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, int append, bool compare) {
+    static bool CompareResult(const char* func, SkString* bugOut, SkString* bugPart, int append,
+             bool compare) {
         SkDebugf("%s %c %d\n", bugOut->c_str(), compare ? 'T' : 'F', append);
+        SkDebugf("%sPart %s\n", func, bugPart[0].c_str());
+        SkDebugf("%sPart %s\n", func, bugPart[1].c_str());
+        SkDebugf("%sPart %s\n", func, bugPart[2].c_str());
         return compare;
     }
 
-    #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, compare)
+    #define COMPARE_RESULT(append, compare) CompareResult(__FUNCTION__, &bugOut, bugPart, append, \
+            compare)
 #else
     #define COMPARE_RESULT(append, compare) compare
 #endif
 
 /*             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
@@ skipping 14 matching lines @@
                         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);
+bool SkOpAngle::after(SkOpAngle* test) {
+    SkOpAngle* lh = test;
+    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));
+            lh->segment()->debugID(), lh->debugID(), lh->fSectorStart, lh->fSectorEnd,
+            lh->fStart->t(), lh->fEnd->t(),
+            segment()->debugID(), debugID(), fSectorStart, fSectorEnd, fStart->t(), fEnd->t(),
+            rh->segment()->debugID(), rh->debugID(), rh->fSectorStart, rh->fSectorEnd,
+            rh->fStart->t(), rh->fEnd->t());
+    SkString bugPart[3] = { lh->debugPart(), this->debugPart(), rh->debugPart() };
 #endif
-    if (lh.fComputeSector && !const_cast<SkOpAngle&>(lh).computeSector()) {
+    if (lh->fComputeSector && !lh->computeSector()) {
         return COMPARE_RESULT(1, true);
     }
-    if (fComputeSector && !const_cast<SkOpAngle*>(this)->computeSector()) {
+    if (fComputeSector && !this->computeSector()) {
         return COMPARE_RESULT(2, true);
     }
-    if (rh.fComputeSector && !const_cast<SkOpAngle&>(rh).computeSector()) {
+    if (rh->fComputeSector && !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));
+            lh->segment()->debugID(), lh->debugID(), lh->fSectorStart, lh->fSectorEnd,
+            lh->fStart->t(), lh->fEnd->t(),
+            segment()->debugID(), debugID(), fSectorStart, fSectorEnd, fStart->t(), fEnd->t(),
+            rh->segment()->debugID(), rh->debugID(), rh->fSectorStart, rh->fSectorEnd,
+            rh->fStart->t(), rh->fEnd->t());
 #endif
-    bool ltrOverlap = (lh.fSectorMask | rh.fSectorMask) & fSectorMask;
-    bool lrOverlap = lh.fSectorMask & rh.fSectorMask;
+    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));
+            return COMPARE_RESULT(4,  (lh->fSectorEnd > rh->fSectorStart)
+                    ^ (fSectorStart > lh->fSectorEnd) ^ (fSectorStart > rh->fSectorStart));
         }
-        int lrGap = (rh.fSectorStart - lh.fSectorStart + 32) & 0x1f;
+        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);
+        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);
+    SkASSERT((lh->fSectorMask & fSectorMask) || (rh->fSectorMask & fSectorMask));
+    if (lh->fSectorMask & fSectorMask) {
+        ltOrder = (int) lh->orderable(this);
     } else {
-        int ltGap = (fSectorStart - lh.fSectorStart + 32) & 0x1f;
+        int ltGap = (fSectorStart - lh->fSectorStart + 32) & 0x1f;
         ltOrder = ltGap > 20 ? 0 : ltGap > 11 ? -1 : 1;
     }
     int trOrder;
-    if (rh.fSectorMask & fSectorMask) {
+    if (rh->fSectorMask & fSectorMask) {
         trOrder = (int) orderable(rh);
     } else {
-        int trGap = (rh.fSectorStart - fSectorStart + 32) & 0x1f;
+        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);
+        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));
+        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);
+        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 {
+int SkOpAngle::allOnOneSide(const SkOpAngle* test) {
     SkASSERT(!fIsCurve);
-    SkASSERT(test.fIsCurve);
-    const SkDPoint& origin = test.fCurvePart[0];
+    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;
+    if (segment()->verb() == SkPath::kLine_Verb) {
+        const SkPoint* linePts = segment()->pts();
+        int lineStart = fStart->t() < fEnd->t() ? 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();
+    SkPath::Verb testVerb = test->segment()->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) {
+    const SkDCubic& testCurve = test->fCurvePart;
+    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 (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;
-        }
+    }
+    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;
-}
-
 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 {
+// loop looking for a pair of angle parts that are too close to be sorted
+/* This is called after other more simple intersection and angle sorting tests have been exhausted.
+   This should be rarely called -- the test below is thorough and time consuming.
+   This checks the distance between start points; the distance between 
+*/
+void SkOpAngle::checkNearCoincidence() {
+    SkOpAngle* test = this;
+    do {
+        SkOpSegment* testSegment = test->segment();
+        double testStartT = test->start()->t();
+        SkDPoint testStartPt = testSegment->dPtAtT(testStartT);
+        double testEndT = test->end()->t();
+        SkDPoint testEndPt = testSegment->dPtAtT(testEndT);
+        double testLenSq = testStartPt.distanceSquared(testEndPt);
+        if (0) {
+            SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID());
+        }
+        double testMidT = (testStartT + testEndT) / 2;
+        SkOpAngle* next = test;
+        while ((next = next->fNext) != this) {
+            SkOpSegment* nextSegment = next->segment();
+            double testMidDistSq = testSegment->distSq(testMidT, next);
+            double testEndDistSq = testSegment->distSq(testEndT, next);
+            double nextStartT = next->start()->t();
+            SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT);
+            double distSq = testStartPt.distanceSquared(nextStartPt);
+            double nextEndT = next->end()->t();
+            double nextMidT = (nextStartT + nextEndT) / 2;
+            double nextMidDistSq = nextSegment->distSq(nextMidT, test);
+            double nextEndDistSq = nextSegment->distSq(nextEndT, test);
+            if (0) {
+                SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq,
+                        testSegment->debugID(), nextSegment->debugID());
+                SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq);
+                SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq);
+                SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq);
+                SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq);
+                SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT);
+                double nextLenSq = nextStartPt.distanceSquared(nextEndPt);
+                SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq);
+                SkDebugf("\n");
+            }
+        }
+        test = test->fNext;
+    } while (test->fNext != this); 
+}
+
+bool SkOpAngle::checkParallel(SkOpAngle* rh) {
     SkDVector scratch[2];
     const SkDVector* sweep, * tweep;
-    if (!fUnorderedSweep) {
-        sweep = fSweep;
+    if (!this->fUnorderedSweep) {
+        sweep = this->fSweep;
     } else {
-        scratch[0] = fCurvePart[1] - fCurvePart[0];
+        scratch[0] = this->fCurvePart[1] - this->fCurvePart[0];
         sweep = &scratch[0];
     }
-    if (!rh.fUnorderedSweep) {
-        tweep = rh.fSweep;
+    if (!rh->fUnorderedSweep) {
+        tweep = rh->fSweep;
     } else {
-        scratch[1] = rh.fCurvePart[1] - rh.fCurvePart[0];
+        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];
+    // compute the perpendicular to the endpoints and see where it intersects the opposite curve
+    // if the intersections within the t range, do a cross check on those
+    bool inside;
+    if (this->endToSide(rh, &inside)) {
+        return inside;
+    }
+    if (rh->endToSide(this, &inside)) {
+        return !inside;
+    }
+    if (this->midToSide(rh, &inside)) {
+        return inside;
+    }
+    if (rh->midToSide(this, &inside)) {
+        return !inside;
+    }
+    // compute the cross check from the mid T values (last resort)
+    SkDVector m0 = segment()->dPtAtT(this->midT()) - this->fCurvePart[0];
+    SkDVector m1 = rh->segment()->dPtAtT(rh->midT()) - rh->fCurvePart[0];
     double m0xm1 = m0.crossCheck(m1);
     if (m0xm1 == 0) {
-        fUnorderable = true;
-        rh.fUnorderable = true;
+        this->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) {
         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;
+    bool stepUp = fStart->t() < fEnd->t();
+    const SkOpSpanBase* checkEnd = fEnd;
+    if (checkEnd->final() && stepUp) {
+        fUnorderable = true;
+        return false;
+    }
     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) {
+        const SkOpSegment* other = checkEnd->segment();
+        const SkOpSpanBase* oSpan = other->head();
+        do {
+            if (oSpan->segment() != segment()) {
                 continue;
             }
-            if (oSpan.fOtherIndex == checkEnd) {
+            if (oSpan == checkEnd) {
                 continue;
             }
-            if (!approximately_equal(oSpan.fOtherT, span.fT)) {
+            if (!approximately_equal(oSpan->t(), checkEnd->t())) {
                 continue;
             }
             goto recomputeSector;
-        }
-        checkEnd += step;
-    } while (checkEnd != limit);
+        } while (!oSpan->final() && (oSpan = oSpan->upCast()->next()));
+        checkEnd = stepUp ? !checkEnd->final()
+                ? checkEnd->upCast()->next() : NULL
+                : checkEnd->prev();
+    } while (checkEnd);
 recomputeSector:
-    if (checkEnd == fEnd || checkEnd - step == fEnd) {
+    SkOpSpanBase* computedEnd = stepUp ? checkEnd ? checkEnd->prev() : fEnd->segment()->head() 
+            : checkEnd ? checkEnd->upCast()->next() : fEnd->segment()->tail();
+    if (checkEnd == fEnd || computedEnd == fEnd || computedEnd == fStart) {
         fUnorderable = true;
         return false;
     }
-    int saveEnd = fEnd;
-    fComputedEnd = fEnd = checkEnd - step;
+    SkOpSpanBase* saveEnd = fEnd;
+    fComputedEnd = fEnd = computedEnd;
     setSpans();
     setSector();
     fEnd = saveEnd;
     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;
+int SkOpAngle::convexHullOverlaps(const SkOpAngle* rh) const {
+    const SkDVector* sweep = this->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];
+    SkDVector m0 = this->segment()->dPtAtT(this->midT()) - this->fCurvePart[0];
+    SkDVector m1 = rh->segment()->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;
     }
@@ skipping 13 matching lines @@
             }
             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();
+bool SkOpAngle::endsIntersect(SkOpAngle* rh) {
+    SkPath::Verb lVerb = this->segment()->verb();
+    SkPath::Verb rVerb = rh->segment()->verb();
     int lPts = SkPathOpsVerbToPoints(lVerb);
     int rPts = SkPathOpsVerbToPoints(rVerb);
-    SkDLine rays[] = {{{fCurvePart[0], rh.fCurvePart[rPts]}},
-            {{fCurvePart[0], fCurvePart[lPts]}}};
+    SkDLine rays[] = {{{this->fCurvePart[0], rh->fCurvePart[rPts]}},
+            {{this->fCurvePart[0], this->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;
         int cPts = index ? rPts : lPts;
-        (*CurveIntersectRay[cPts])(segment.pts(), rays[index], &i);
         // if the curve is a line, then the line and the ray intersect only at their crossing
         if (cPts == 1) { // line
             continue;
         }
-//      SkASSERT(i.used() >= 1);
-//        if (i.used() <= 1) {
-//            continue;
-//        }
-        double tStart = segment.t(index ? rh.fStart : fStart);
-        double tEnd = segment.t(index ? rh.fComputedEnd : fComputedEnd);
-        bool testAscends = index ? rh.fStart < rh.fComputedEnd : fStart < fComputedEnd;
+        const SkOpSegment& segment = index ? *rh->segment() : *this->segment();
+        SkIntersections i;
+        (*CurveIntersectRay[cPts])(segment.pts(), rays[index], &i);
+        double tStart = index ? rh->fStart->t() : this->fStart->t();
+        double tEnd = index ? rh->fComputedEnd->t() : this->fComputedEnd->t();
+        bool testAscends = tStart < (index ? rh->fComputedEnd->t() : this->fComputedEnd->t());
         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 SkOpSegment& segment = index ? *rh->segment() : *this->segment();
         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;
             }
@@ skipping 10 matching lines @@
             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;
+        const SkDCubic& curve = index ? rh->fCurvePart : this->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
+        if (delta > 1e-3 && (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);
+        const SkDCubic& curve = sIndex ? rh->fCurvePart : this->fCurvePart;
+        const SkOpSegment& segment = sIndex ? *rh->segment() : *this->segment();
+        double tStart = sIndex ? rh->fStart->t() : fStart->t();
         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);
     }
 }
 
+bool SkOpAngle::endToSide(const SkOpAngle* rh, bool* inside) const {
+    const SkOpSegment* segment = this->segment();
+    SkPath::Verb verb = segment->verb();
+    int pts = SkPathOpsVerbToPoints(verb);
+    SkDLine rayEnd;
+    rayEnd[0].set(this->fEnd->pt());
+    rayEnd[1] = rayEnd[0];
+    SkDVector slopeAtEnd = (*CurveDSlopeAtT[pts])(segment->pts(), this->fEnd->t());
+    rayEnd[1].fX += slopeAtEnd.fY;
+    rayEnd[1].fY -= slopeAtEnd.fX;
+    SkIntersections iEnd;
+    const SkOpSegment* oppSegment = rh->segment();
+    SkPath::Verb oppVerb = oppSegment->verb();
+    int oppPts = SkPathOpsVerbToPoints(oppVerb);
+    (*CurveIntersectRay[oppPts])(oppSegment->pts(), rayEnd, &iEnd);
+    double endDist;
+    int closestEnd = iEnd.closestTo(rh->fStart->t(), rh->fEnd->t(), rayEnd[0], &endDist);
+    if (closestEnd < 0) {
+        return false;
+    }
+    if (!endDist) {
+        return false;
+    }
+    SkDPoint start;
+    start.set(this->fStart->pt());
+    // OPTIMIZATION: multiple times in the code we find the max scalar
+    double minX, minY, maxX, maxY;
+    minX = minY = SK_ScalarInfinity;
+    maxX = maxY = -SK_ScalarInfinity;
+    const SkDCubic& curve = rh->fCurvePart;
+    for (int idx2 = 0; idx2 <= oppPts; ++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);
+    endDist /= maxWidth;
+    if (endDist < 5e-11) {  // empirically found
+        return false;
+    }
+    const SkDPoint* endPt = &rayEnd[0];
+    SkDPoint oppPt = iEnd.pt(closestEnd);
+    SkDVector vLeft = *endPt - start;
+    SkDVector vRight = oppPt - start;
+    double dir = vLeft.crossCheck(vRight);
+    if (!dir) {
+        return false;
+    }
+    *inside = dir < 0;
+    return true;
+}
+
 // 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;
+SkOpAngle* SkOpAngle::findFirst() {
+    SkOpAngle* best = this;
     int bestStart = SkTMin(fSectorStart, fSectorEnd);
-    const SkOpAngle* angle = this;
+    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;
+    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
+        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;
@@ skipping 46 matching lines @@
     //   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;
 }
 
+SkOpGlobalState* SkOpAngle::globalState() const {
+    return this->segment()->globalState();
+}
+
+
 // 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 (angle->overlap(*this)) {  // angles are essentially coincident
-            return;
-        }
         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->overlap(*last) || angle->overlap(*next)) {
-            return;
-        }
         if (angle->after(last)) {
             last->fNext = angle;
             angle->fNext = next;
             debugValidateNext();
             return;
         }
         last = next;
         next = next->fNext;
-        if (last == this && next->fUnorderable) {
-            fUnorderable = true;
+        if (last == this) {
+            if (next->fUnorderable) {
+                fUnorderable = true;
+            } else {
+                globalState()->setAngleCoincidence();
+                this->fNext = angle;
+                angle->fNext = next;
+                angle->fCheckCoincidence = true;
+            }
             return;
         }
-        SkASSERT(last != this);
     } while (true);
 }
 
-bool SkOpAngle::isHorizontal() const {
-    return !fIsCurve && fSweep[0].fY == 0;
-}
-
-SkOpSpan* SkOpAngle::lastMarked() const {
+SkOpSpanBase* SkOpAngle::lastMarked() const {
     if (fLastMarked) {
-        if (fLastMarked->fChased) {
+        if (fLastMarked->chased()) {
             return NULL;
         }
-        fLastMarked->fChased = true;
+        fLastMarked->setChased(true);
     }
     return fLastMarked;
 }
 
-bool SkOpAngle::loopContains(const SkOpAngle& test) const {
+bool SkOpAngle::loopContains(const SkOpAngle* angle) const {
     if (!fNext) {
         return false;
     }
     const SkOpAngle* first = this;
     const SkOpAngle* loop = this;
-    const SkOpSegment* tSegment = test.fSegment;
-    double tStart = tSegment->span(test.fStart).fT;
-    double tEnd = tSegment->span(test.fEnd).fT;
+    const SkOpSegment* tSegment = angle->fStart->segment();
+    double tStart = angle->fStart->t();
+    double tEnd = angle->fEnd->t();
     do {
-        const SkOpSegment* lSegment = loop->fSegment;
-        // FIXME : use precisely_equal ? or compare points exactly ?
+        const SkOpSegment* lSegment = loop->fStart->segment();
         if (lSegment != tSegment) {
             continue;
         }
-        double lStart = lSegment->span(loop->fStart).fT;
+        double lStart = loop->fStart->t();
         if (lStart != tEnd) {
             continue;
         }
-        double lEnd = lSegment->span(loop->fEnd).fT;
+        double lEnd = loop->fEnd->t();
         if (lEnd == tStart) {
             return true;
         }
     } while ((loop = loop->fNext) != first);
     return false;
 }
 
 int SkOpAngle::loopCount() const {
     int count = 0;
     const SkOpAngle* first = this;
@@ skipping 31 matching lines @@
         }
         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 0 && 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;
+    return (fStart->t() + fEnd->t()) / 2;
 }
 
-bool SkOpAngle::oppositePlanes(const SkOpAngle& rh) const {
-    int startSpan = abs(rh.fSectorStart - fSectorStart);
+bool SkOpAngle::midToSide(const SkOpAngle* rh, bool* inside) const {
+    const SkOpSegment* segment = this->segment();
+    SkPath::Verb verb = segment->verb();
+    int pts = SkPathOpsVerbToPoints(verb);
+    const SkPoint& startPt = this->fStart->pt();
+    const SkPoint& endPt = this->fEnd->pt();
+    SkDPoint dStartPt;
+    dStartPt.set(startPt);
+    SkDLine rayMid;
+    rayMid[0].fX = (startPt.fX + endPt.fX) / 2;
+    rayMid[0].fY = (startPt.fY + endPt.fY) / 2;
+    rayMid[1].fX = rayMid[0].fX + (endPt.fY - startPt.fY);
+    rayMid[1].fY = rayMid[0].fY - (endPt.fX - startPt.fX);
+    SkIntersections iMid;
+    (*CurveIntersectRay[pts])(segment->pts(), rayMid, &iMid);
+    int iOutside = iMid.mostOutside(this->fStart->t(), this->fEnd->t(), dStartPt);
+    if (iOutside < 0) {
+        return false;
+    }
+    const SkOpSegment* oppSegment = rh->segment();
+    SkPath::Verb oppVerb = oppSegment->verb();
+    int oppPts = SkPathOpsVerbToPoints(oppVerb);
+    SkIntersections oppMid;
+    (*CurveIntersectRay[oppPts])(oppSegment->pts(), rayMid, &oppMid);
+    int oppOutside = oppMid.mostOutside(rh->fStart->t(), rh->fEnd->t(), dStartPt);
+    if (oppOutside < 0) {
+        return false;
+    }
+    SkDVector iSide = iMid.pt(iOutside) - dStartPt;
+    SkDVector oppSide = oppMid.pt(oppOutside) - dStartPt;
+    double dir = iSide.crossCheck(oppSide);
+    if (!dir) {
+        return false;
+    }
+    *inside = dir < 0;
+    return true;
+}
+
+bool SkOpAngle::oppositePlanes(const SkOpAngle* rh) const {
+    int startSpan = abs(rh->fSectorStart - fSectorStart);
     return startSpan >= 8;
 }
 
-bool SkOpAngle::orderable(const SkOpAngle& rh) const {
+bool SkOpAngle::orderable(SkOpAngle* rh) {
     int result;
     if (!fIsCurve) {
-        if (!rh.fIsCurve) {
+        if (!rh->fIsCurve) {
             double leftX = fTangentHalf.dx();
             double leftY = fTangentHalf.dy();
-            double rightX = rh.fTangentHalf.dx();
-            double rightY = rh.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)) {
+        if (fUnorderable || approximately_zero(rh->fSide)) {
             goto unorderable;
         }
-    } else if (!rh.fIsCurve) {
-        if ((result = rh.allOnOneSide(*this)) >= 0) {
+    } else if (!rh->fIsCurve) {
+        if ((result = rh->allOnOneSide(this)) >= 0) {
             return !result;
         }
-        if (rh.fUnorderable || approximately_zero(fSide)) {
+        if (rh->fUnorderable || approximately_zero(fSide)) {
             goto unorderable;
         }
     }
     if ((result = convexHullOverlaps(rh)) >= 0) {
         return result;
     }
     return endsIntersect(rh);
 unorderable:
     fUnorderable = true;
-    rh.fUnorderable = true;
+    rh->fUnorderable = true;
     return true;
 }
 
-bool SkOpAngle::overlap(const SkOpAngle& other) const {
-    int min = SkTMin(fStart, fEnd);
-    const SkOpSpan& span = fSegment->span(min);
-    const SkOpSegment* oSeg = other.fSegment;
-    int oMin = SkTMin(other.fStart, other.fEnd);
-    const SkOpSpan& oSpan = oSeg->span(oMin);
-    if (!span.fSmall && !oSpan.fSmall) {
-        return false;
-    }
-    if (fSegment->span(fStart).fPt != oSeg->span(other.fStart).fPt) {
-        return false;
-    }
-    // see if small span is contained by opposite span
-    return span.fSmall ? oSeg->containsPt(fSegment->span(fEnd).fPt, other.fEnd, other.fStart)
-            : fSegment->containsPt(oSeg->span(other.fEnd).fPt, fEnd, fStart);
-}
-
 // 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) {
-    fSegment = segment;
+SkOpSegment* SkOpAngle::segment() const {
+    return fStart->segment();
+}
+
+void SkOpAngle::set(SkOpSpanBase* start, SkOpSpanBase* end) {
     fStart = start;
     fComputedEnd = fEnd = end;
+    SkASSERT(start != end);
     fNext = NULL;
-    fComputeSector = fComputedSector = false;
+    fComputeSector = fComputedSector = fCheckCoincidence = false;
     fStop = false;
     setSpans();
     setSector();
+    PATH_OPS_DEBUG_CODE(fID = start->globalState()->nextAngleID());
 }
 
 void SkOpAngle::setCurveHullSweep() {
     fUnorderedSweep = false;
     fSweep[0] = fCurvePart[1] - fCurvePart[0];
-    if (SkPath::kLine_Verb == fSegment->verb()) {
+    const SkOpSegment* segment = fStart->segment();
+    if (SkPath::kLine_Verb == segment->verb()) {
         fSweep[1] = fSweep[0];
         return;
     }
     fSweep[1] = fCurvePart[2] - fCurvePart[0];
-    if (SkPath::kCubic_Verb != fSegment->verb()) {
+    if (SkPath::kCubic_Verb != segment->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) {
@@ skipping 13 matching lines @@
     // 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()) {
-        goto deferTilLater;
-    }
-    fSectorStart = findSector(verb, fSweep[0].fX, fSweep[0].fY);
-    if (fSectorStart < 0) {
-        goto deferTilLater;
-    }
-    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 < 0) {
-deferTilLater:
-        fSectorStart = fSectorEnd = -1;
-        fSectorMask = 0;
-        fComputeSector = true;  // can't determine sector until segment length can be found
-        return;
-    }
-    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);
+    fUnorderable = false;
     fLastMarked = NULL;
-    const SkPoint* pts = fSegment->pts();
+    const SkOpSegment* segment = fStart->segment();
+    const SkPoint* pts = segment->pts();
     SkDEBUGCODE(fCurvePart[2].fX = fCurvePart[2].fY = fCurvePart[3].fX = fCurvePart[3].fY
             = SK_ScalarNaN);
-    fSegment->subDivide(fStart, fEnd, &fCurvePart);
+    segment->subDivide(fStart, fEnd, &fCurvePart);
     setCurveHullSweep();
-    const SkPath::Verb verb = fSegment->verb();
+    const SkPath::Verb verb = segment->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);
-        const SkPoint& cP1 = pts[fStart < fEnd];
+        const SkPoint& cP1 = pts[fStart->t() < fEnd->t()];
         SkDLine lineHalf;
-        lineHalf[0].set(fSegment->span(fStart).fPt);
+        lineHalf[0].set(fStart->pt());
         lineHalf[1].set(cP1);
         fTangentHalf.lineEndPoints(lineHalf);
         fSide = 0;
         fIsCurve = false;
         } return;
     case SkPath::kQuad_Verb: {
         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: {
         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 startT = fStart->t();
+        double endT = fEnd->t();
         double limitT = endT;
         int index;
         for (index = 0; index < testCount; ++index) {
             if (!::between(startT, testTs[index], limitT)) {
                 testTs[index] = -1;
             }
         }
         testTs[testCount++] = startT;
         testTs[testCount++] = endT;
         SkTQSort<double>(testTs, &testTs[testCount - 1]);
@@ skipping 19 matching lines @@
                 bestSide = testSide;
             }
         }
         fSide = -bestSide;  // compare sign only
         } break;
     default:
         SkASSERT(0);
     }
 }
 
-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;
-        }
+void SkOpAngle::setSector() {
+    const SkOpSegment* segment = fStart->segment();
+    SkPath::Verb verb = segment->verb();
+    fSectorStart = this->findSector(verb, fSweep[0].fX, fSweep[0].fY);
+    if (fSectorStart < 0) {
+        goto deferTilLater;
     }
-    return true;
+    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 = this->findSector(verb, fSweep[1].fX, fSweep[1].fY);
+    if (fSectorEnd < 0) {
+deferTilLater:
+        fSectorStart = fSectorEnd = -1;
+        fSectorMask = 0;
+        fComputeSector = true;  // can't determine sector until segment length can be found
+        return;
+    }
+    if (fSectorEnd == fSectorStart
+            && (fSectorStart & 3) != 3) { // if the sector has no span, it can't be an exact angle
+        fSectorMask = 1 << fSectorStart;
+        return;
+    }
+    bool crossesZero = this->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 = this->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);
+    }
 }
 
-bool SkOpAngle::tangentsDiverge(const SkOpAngle& rh, double s0xt0) const {
+int SkOpAngle::sign() const {
+    SkASSERT(fStart->t() != fEnd->t());
+    return fStart->t() < fEnd->t() ? -1 : 1;
+}
+
+SkOpSpan* SkOpAngle::starter() {
+    return fStart->starter(fEnd);
+}
+
+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;
+    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));
+    double mFactor = fabs(useS ? this->distEndRatio(sDist) : rh->distEndRatio(tDist));
     return mFactor < 5000;  // empirically found limit
 }
-
-SkOpAngleSet::SkOpAngleSet() 
-    : fAngles(NULL)
-#if DEBUG_ANGLE
-    , fCount(0)
-#endif
-{
-}
-
-SkOpAngleSet::~SkOpAngleSet() {
-    SkDELETE(fAngles);
-}
-
-SkOpAngle& SkOpAngleSet::push_back() {
-    if (!fAngles) {
-        fAngles = SkNEW_ARGS(SkChunkAlloc, (2));
-    }
-    void* ptr = fAngles->allocThrow(sizeof(SkOpAngle));
-    SkOpAngle* angle = (SkOpAngle*) ptr;
-#if DEBUG_ANGLE
-    angle->setID(++fCount);
-#endif
-    return *angle;
-}
-
-void SkOpAngleSet::reset() {
-    if (fAngles) {
-        fAngles->reset();
-    }
-}