offset angle check edge in common

When curves cross, their intersection points may be nearby, but not exactly the same.
Sort the angles formed by the crossing curves when all angles don't have the same
origin.

This sets up the framework to solve test case that currently fail (e.g., joel6) but
does not fix all related test cases (e.g., joel9).

All older existing test cases, including extended tests, pass.

Rework the test framework to better report when tests expected to produce failing
results now pass.

Add new point and vector operations to support offset angles.

TBR=reed@google.com
BUG=skia:6041

Change-Id: I67c651ded0a25e99ad93d55d6a35109b3ee3698e
Reviewed-on: https://skia-review.googlesource.com/6624
Commit-Queue: Cary Clark <caryclark@google.com>
Reviewed-by: Cary Clark <caryclark@google.com>

6 files changed, 361 insertions, 72 deletions

diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index c07e8cc73f..f41ef234d4 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -62,23 +62,15 @@ bool SkOpAngle::after(SkOpAngle* test) {
     SkOpAngle* lh = test;
     SkOpAngle* rh = lh->fNext;
     SkASSERT(lh != rh);
-    fPart.fCurve = fOriginalCurvePart;
-    lh->fPart.fCurve = lh->fOriginalCurvePart;
-    lh->fPart.fCurve.offset(lh->segment()->verb(), fPart.fCurve[0] - lh->fPart.fCurve[0]);
-    rh->fPart.fCurve = rh->fOriginalCurvePart;
-    rh->fPart.fCurve.offset(rh->segment()->verb(), fPart.fCurve[0] - rh->fPart.fCurve[0]);
-
 #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->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());
+    this->debugAfter(lh, rh, &bugOut);
     SkString bugPart[3] = { lh->debugPart(), this->debugPart(), rh->debugPart() };
+#if 0  // convenient place to set a breakpoint to trace through a specific angle compare
+    if (lh->debugID() == 4 && this->debugID() == 16 && rh->debugID() == 5) {
+        SkDebugf("");
+    }
+#endif
 #endif
     if (lh->fComputeSector && !lh->computeSector()) {
         return COMPARE_RESULT(1, true);
@@ -90,23 +82,106 @@ bool SkOpAngle::after(SkOpAngle* test) {
         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->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());
+    this->debugAfter(lh, rh, &bugOut);
 #endif
-    bool ltrOverlap = (lh->fSectorMask | rh->fSectorMask) & fSectorMask;
-    bool lrOverlap = lh->fSectorMask & rh->fSectorMask;
+    /* If the curve pairs share a point, the computed sector is valid. Otherwise, the sectors must
+       be sufficiently different that translating them won't change the sort order. For instance,
+       curves with different origins may mis-sort if the computed sectors are 1 and 5.
+
+       Curves with different origins have more information though -- there are more ways for their
+       convex hulls not to overlap. Try to resolve different origins directly before translating
+       one curve to share the opposite's origin.
+    */
+    bool lrOverlap, ltrOverlap;
+    SkDVector lhOffset = fOriginalCurvePart[0] - lh->fOriginalCurvePart[0];
+    bool lhHasOffset = lhOffset.fX || lhOffset.fY;
+    SkDVector rhOffset = fOriginalCurvePart[0] - rh->fOriginalCurvePart[0];
+    bool rhHasOffset = rhOffset.fX || rhOffset.fY;
+    int lhStart, lhEnd, thStart, thEnd, rhStart, rhEnd;
+    bool lhX0, thX0, rhX0;
+    if (lhHasOffset | rhHasOffset) {
+        lhX0 = lh->sectorRange(&lhStart, &lhEnd, lhHasOffset);
+        thX0 = this->sectorRange(&thStart, &thEnd, false);
+        rhX0 = rh->sectorRange(&rhStart, &rhEnd, rhHasOffset);
+        lrOverlap = lhX0 + rhX0 + (lhStart <= rhEnd) + (rhStart <= lhEnd) >= 2;
+        ltrOverlap = thX0 + lhX0 + (lhStart <= thEnd) + (thStart <= lhEnd) >= 2
+                || rhX0 + thX0 + (thStart <= rhEnd) + (rhStart <= thEnd) >= 2;
+    } else {
+        lrOverlap = lh->fSectorMask & rh->fSectorMask;
+        ltrOverlap = (lh->fSectorMask | rh->fSectorMask) & fSectorMask;
+    }
+    if (!lrOverlap & !ltrOverlap) {  // no lh/this/rh sector overlap
+        return COMPARE_RESULT(4, (lh->fSectorEnd > rh->fSectorStart)
+                ^ (fSectorStart > lh->fSectorEnd) ^ (fSectorStart > rh->fSectorStart));
+    }
     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));
+    fPart.fCurve = fOriginalCurvePart;
+    lh->fPart.fCurve = lh->fOriginalCurvePart;
+    rh->fPart.fCurve = rh->fOriginalCurvePart;
+    if (lhHasOffset | rhHasOffset) {
+        bool lhSweepsCCW = lh->sweepsCCW();
+        bool thSweepsCCW = this->sweepsCCW();
+        bool rhSweepsCCW = rh->sweepsCCW();
+        Turn thStartFromLhEnd = this->ccwOf(lh, lhSweepsCCW, !thSweepsCCW);
+        Turn thEndFromRhStart = this->ccwOf(rh, !rhSweepsCCW, thSweepsCCW);
+        if (!lrOverlap && Turn::kCcw == thStartFromLhEnd && Turn::kCw == thEndFromRhStart) {
+            if (!this->sweepContains(lh) && !this->sweepContains(rh)) {
+                return COMPARE_RESULT(5, true); 
+            }
+        }
+        Turn lhStartFromRhStart = lh->ccwOf(rh, !rhSweepsCCW, !lhSweepsCCW);
+        Turn lhEndFromRhStart = lh->fPart.isCurve()
+                ? lh->ccwOf(rh, !rhSweepsCCW, lhSweepsCCW) : lhStartFromRhStart;
+        bool lhOrRhIsCurve = lh->fPart.isCurve() || rh->fPart.isCurve();
+        Turn lhStartFromRhEnd;
+        if (lhOrRhIsCurve) {
+            if (rh->fPart.isCurve()) {
+                lhStartFromRhEnd = lh->ccwOf(rh, rhSweepsCCW, !lhSweepsCCW);
+            } else {
+                lhStartFromRhEnd = lhStartFromRhStart;
+            }
+            // cancel overlap only if sweep doesn't contain other curve's sweep pts
+            if (!lh->sweepContains(rh)) {
+                // clear overlap if both turn in the same direction
+                lrOverlap &= (int) lhStartFromRhEnd * (int) lhEndFromRhStart < 0;
+            }
+        } else {
+            lrOverlap = false;
+        }
+        Turn thStartFromRhEnd  SkDEBUGCODE(= Turn::kDebugUninitialized);
+        Turn thEndFromLhStart  SkDEBUGCODE(= Turn::kDebugUninitialized);
+        if (lhOrRhIsCurve || fPart.isCurve()) {
+            thStartFromRhEnd = rh->fPart.isCurve() || fPart.isCurve()
+                    ? this->ccwOf(rh, rhSweepsCCW, !thSweepsCCW) : thEndFromRhStart;
+            thEndFromLhStart = lh->fPart.isCurve() || fPart.isCurve()
+                    ? this->ccwOf(lh, !lhSweepsCCW, thSweepsCCW) : thStartFromLhEnd;
+            // clear overlap if both pairs turn in the same direction
+            if (!this->sweepContains(lh) && !this->sweepContains(rh)) {
+                ltrOverlap &= (int) thStartFromRhEnd * (int) thEndFromRhStart <= 0
+                        || (int) thStartFromLhEnd * (int) thEndFromLhStart <= 0;
+            }
+        } else {
+            ltrOverlap = false;
         }
+        if (!lrOverlap & !ltrOverlap) {
+            Turn lhFromRh = (Turn) ((int) lhEndFromRhStart | (int) lhStartFromRhStart);
+            Turn thFromLh = (Turn) ((int) thEndFromLhStart | (int) thStartFromLhEnd);
+            Turn thFromRh = (Turn) ((int) thEndFromRhStart | (int) thStartFromRhEnd);
+            bool result = Turn::kCw == lhFromRh ?
+                     Turn::kCcw == thFromLh && Turn::kCw == thFromRh :
+                     Turn::kCcw == thFromLh || Turn::kCw == thFromRh;
+            return COMPARE_RESULT(6, result);
+        }
+        if (lhHasOffset) {
+            lh->fPart.fCurve.offset(lh->segment()->verb(), lhOffset);
+        }
+        if (rhHasOffset) {
+            rh->fPart.fCurve.offset(rh->segment()->verb(), rhOffset);
+        }
+        lrOverlap = lh->fSectorMask & rh->fSectorMask;
+        ltrOverlap = (lh->fSectorMask | rh->fSectorMask) & fSectorMask;
+    }
+    if (!lrOverlap) {  // no lh/rh sector overlap, no offsets
         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.
@@ -122,11 +197,13 @@ bool SkOpAngle::after(SkOpAngle* test) {
     } else {
         lrOrder = (int) lh->orderable(rh);
         if (!ltrOverlap) {
-            return COMPARE_RESULT(5, !lrOrder);
+            return COMPARE_RESULT(7, !lrOrder);
         }
     }
     int ltOrder;
-    SkASSERT((lh->fSectorMask & fSectorMask) || (rh->fSectorMask & fSectorMask));
+    SkDEBUGCODE(bool ltOverlap = lhHasOffset || lh->fSectorMask & fSectorMask);
+    SkDEBUGCODE(bool trOverlap = rhHasOffset || rh->fSectorMask & fSectorMask);
+    SkASSERT(ltOverlap || trOverlap);
     if (lh->fSectorMask & fSectorMask) {
         ltOrder = (int) lh->orderable(this);
     } else {
@@ -143,7 +220,7 @@ bool SkOpAngle::after(SkOpAngle* test) {
     this->alignmentSameSide(lh, &ltOrder);
     this->alignmentSameSide(rh, &trOrder);
     if (lrOrder >= 0 && ltOrder >= 0 && trOrder >= 0) {
-        return COMPARE_RESULT(7, lrOrder ? (ltOrder & trOrder) : (ltOrder | trOrder));
+        return COMPARE_RESULT(8, 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.
@@ -155,25 +232,25 @@ bool SkOpAngle::after(SkOpAngle* test) {
         SkDEBUGCODE(bool lrOpposite = lh->oppositePlanes(rh));
         bool ltOpposite = lh->oppositePlanes(this);
         SkOPASSERT(lrOpposite != ltOpposite);
-        return COMPARE_RESULT(8, ltOpposite);
+        return COMPARE_RESULT(9, ltOpposite);
     } else if (ltOrder == 1 && trOrder == 0) {
         SkASSERT(lrOrder < 0);
         bool trOpposite = oppositePlanes(rh);
-        return COMPARE_RESULT(9, trOpposite);
+        return COMPARE_RESULT(10, 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);
+        return COMPARE_RESULT(11, lrOpposite);
     }
     if (lrOrder < 0) {
         if (ltOrder < 0) {
-            return COMPARE_RESULT(11, trOrder);
+            return COMPARE_RESULT(12, trOrder);
         }
-        return COMPARE_RESULT(12, ltOrder);
+        return COMPARE_RESULT(13, ltOrder);
     }
-    return COMPARE_RESULT(13, !lrOrder);
+    return COMPARE_RESULT(14, !lrOrder);
 }
 
 // given a line, see if the opposite curve's convex hull is all on one side
@@ -248,10 +325,101 @@ void SkOpAngle::alignmentSameSide(const SkOpAngle* test, int* order) const {
     }
 }
 
-bool SkOpAngle::checkCrossesZero() const {
-    int start = SkTMin(fSectorStart, fSectorEnd);
-    int end = SkTMax(fSectorStart, fSectorEnd);
-    bool crossesZero = end - start > 16;
+static bool same_side(double cross1, double cross2) {
+    return cross1 * cross2 > 0 && !roughly_zero_when_compared_to(cross1, cross2)
+            && !roughly_zero_when_compared_to(cross2, cross1);
+}
+
+static double same_side_candidate(double cross1, double cross2) {
+    return same_side(cross1, cross2) ? SkTAbs(cross1) > SkTAbs(cross2) ? cross1 : cross2 : 0;
+}
+
+SkOpAngle::Turn SkOpAngle::ccwOf(const SkOpAngle* rh, bool rhCW, bool thisCCW, bool recursed)
+        const {
+    const SkDPoint& startPt = fPart.fCurve[0];
+    const SkDPoint& rhStartPt = rh->fPart.fCurve[0];
+    SkDVector startOffset = rhStartPt - startPt;
+    bool commonPt = 0 == startOffset.fX && 0 == startOffset.fY;
+    const SkDVector& sweep = fPart.fSweep[(int) thisCCW];
+    const SkDVector& rhSweep = rh->fPart.fSweep[(int) rhCW];
+    const SkDVector* testV;
+    SkDVector rhEndV;
+    if (commonPt) {
+        testV = &rhSweep;
+    } else {
+        rhEndV = rhSweep + startOffset;
+        testV = &rhEndV;
+    }
+    double endCheck = sweep.crossCheck(*testV);
+#if 0 && DEBUG_ANGLE  // too verbose to show on all the time
+    SkDebugf("%s {{{%1.9g,%1.9g}, {%1.9g,%1.9g}}} id=1\n", __func__, rhStartPt.fX, rhStartPt.fY,
+            rhStartPt.fX + rhSweep.fX, rhStartPt.fY + rhSweep.fY);
+    SkDebugf("%s {{{%1.9g,%1.9g}, {%1.9g,%1.9g}}} id=2\n", __func__, startPt.fX, startPt.fY,
+            startPt.fX + sweep.fX, startPt.fY + sweep.fY);
+#endif
+    if (0 == endCheck) {
+        if (sweep.dot(*testV) < 0) {
+            return Turn::kNone;  // neither clockwise nor counterclockwise
+        }
+        // if the pair of angles share an edge, use its other sweep to check the turn value
+        if ((fPart.isCurve() || rh->fPart.isCurve())) {
+            if (recursed) {
+                return Turn::kNone;
+            }
+            return this->ccwOf(rh, !rhCW, !thisCCW, true);
+        }
+    }
+    if (commonPt) {
+        return toTurn(endCheck > 0);
+    }
+    double startCheck = sweep.crossCheck(startOffset);
+    if ((startCheck == 0 || startOffset.lengthSquared() < FLT_EPSILON_SQUARED * 2049) &&
+            (endCheck == 0 || testV->lengthSquared() < FLT_EPSILON_SQUARED * 2049)) {
+        double cross = sweep.cross(rhSweep);
+        if (cross != 0)
+            return toTurn(cross > 0);
+    }
+    if (same_side(startCheck, endCheck)) {
+        return toTurn(startCheck > 0);
+    }
+    SkDVector reverseSweep = -sweep;
+    SkDVector rhReverseStartV = startOffset - sweep;
+    double reverseStartCheck = reverseSweep.crossCheck(rhReverseStartV);
+    SkDVector rhReverseEndV = rhReverseStartV + rhSweep;
+    double reverseEndCheck = reverseSweep.crossCheck(rhReverseEndV);
+    if (same_side(reverseStartCheck, reverseEndCheck)) {
+        return toTurn(reverseStartCheck < 0);
+    }
+    double rhEndCheck = rhSweep.crossCheck(rhReverseEndV);
+    double rhStartCheck = rhSweep.crossCheck(*testV);
+    double endSide = same_side_candidate(rhEndCheck, rhStartCheck);
+    SkDVector rhReverseSweep = -rhSweep;
+    double rhReverseEndCheck = rhReverseSweep.crossCheck(rhReverseStartV);
+    double rhReverseStartCheck = rhReverseSweep.crossCheck(startOffset);
+    double startSide = -same_side_candidate(rhReverseEndCheck, rhReverseStartCheck);
+    if (startSide || endSide) {
+        return toTurn((SkTAbs(startSide) > SkTAbs(endSide) ? startSide : endSide) > 0);
+    }
+    // if a pair crosses only slightly, no two ends will be on the same side
+    // look for the smaller ratio to guess which segment only crosses the other slightly
+    double crosses[] = { endCheck, reverseStartCheck, reverseEndCheck,
+        rhStartCheck, rhEndCheck, rhReverseStartCheck, rhReverseEndCheck };
+    int smallest = -1;
+    double smallCross = SkTAbs(startCheck);
+    for (int index = 0; index < (int) SK_ARRAY_COUNT(crosses); ++index) {
+        double testCross = SkTAbs(crosses[index]);
+        if (smallCross > testCross) {
+            smallCross = testCross;
+            smallest = index;
+        }
+    }
+    return toTurn((smallest <= 2 ? endCheck : -rhReverseEndCheck) > 0);
+}
+
+bool SkOpAngle::checkCrossesZero(int* start, int* end) const {
+    *start = SkTMin(fSectorStart, fSectorEnd);
+    *end = SkTMax(fSectorStart, fSectorEnd);
+    bool crossesZero = *end - *start > 16;
     return crossesZero;
 }
 
@@ -626,7 +794,6 @@ 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
 bool SkOpAngle::insert(SkOpAngle* angle) {
@@ -849,6 +1016,19 @@ SkOpAngle* SkOpAngle::previous() const {
     } while (true);
 }
 
+// returns true if rounded sector range crosses zero
+bool SkOpAngle::sectorRange(int* start, int* end, bool roundOut) const {
+    if (checkCrossesZero(start, end)) {
+        SkTSwap(*start, *end);
+    }
+    // round away since the offset curves may swap order
+    if (roundOut) {
+        *start = (((*start + 1) & ~0x03) - 1) & 0x1f;
+        *end |= 0x03;
+    }
+    return *end < *start;
+}
+
 SkOpSegment* SkOpAngle::segment() const {
     return fStart->segment();
 }
@@ -985,23 +1165,25 @@ deferTilLater:
         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;
+    int start, end;
+    bool crossesZero = this->checkCrossesZero(&start, &end);
+    bool bumpStart = (fSectorStart & 3) == 3;
+    bool bumpEnd = (fSectorEnd & 3) == 3;
+    if (bumpStart | bumpEnd) {
+        bool curveBendsCCW = (fSectorStart == start) ^ crossesZero;
+        // bump the start and end of the sector span if they are on exact compass points
+        if (bumpStart) {
+            fSectorStart = (fSectorStart + (curveBendsCCW ? 1 : 31)) & 0x1f;
+        }
+        if (bumpEnd) {
+            fSectorEnd = (fSectorEnd + (curveBendsCCW ? 31 : 1)) & 0x1f;
+        }
+        crossesZero = this->checkCrossesZero(&start, &end);
     }
-    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) | ((unsigned) -1 << end);
+        fSectorMask = (unsigned) -1 >> (31 - start) | (unsigned) -1 << end;
     }
 }
 
@@ -1009,6 +1191,70 @@ SkOpSpan* SkOpAngle::starter() {
     return fStart->starter(fEnd);
 }
 
+bool SkOpAngle::sweepsCCW() const {
+    if (!fPart.isCurve()) {
+        return false;   // lines have no sweep
+    }
+#if 0 && DEBUG_ANGLE  // too verbose to show all the time
+    SkDebugf("%s {{{0,0}, {%g,%g}}} id=1\n", __func__, fPart.fSweep[0].fX, fPart.fSweep[0].fY);
+    SkDebugf("%s {{{0,0}, {%g,%g}}} id=2\n", __func__, fPart.fSweep[1].fX, fPart.fSweep[1].fY);
+#endif
+    return fPart.fSweep[0].crossCheck(fPart.fSweep[1]) < 0;
+}
+
+static bool sweep_edge_contains(const SkDVector& edge, const SkDVector& v, double* direction) {
+    double cross = edge.crossCheck(v);
+    if (cross) {
+        if (cross * *direction < 0) {
+            return true;
+        }
+        *direction = cross;
+    }
+    return false;
+}
+
+static bool sweep_contains(const SkDVector sweep[2], const SkDVector& v, double* direction) {
+    if (sweep_edge_contains(sweep[0], v, direction)) {
+        return true;
+    }
+    return sweep_edge_contains(sweep[1], v, direction);
+}
+
+bool SkOpAngle::sweepContains(const SkOpAngle* rh) const {
+    if (!fPart.isCurve()) {
+        return false;
+    }
+    if (!rh->fPart.isCurve()) {
+        return false;
+    }
+    const SkDPoint& startPt = fPart.fCurve[0];
+    const SkDVector* sweep = fPart.fSweep;
+    const SkDPoint& rhStartPt = rh->fPart.fCurve[0];
+    double direction = 0;
+    if (startPt != rhStartPt) {
+        SkDVector vTest = rhStartPt - startPt;
+        if (sweep_contains(sweep, vTest, &direction)) {
+            return true;
+        }
+        for (int index = 0; index < (int) SK_ARRAY_COUNT(rh->fPart.fSweep); ++index) {
+            SkDPoint sweepEnd = rhStartPt;
+            sweepEnd += rh->fPart.fSweep[index];
+            SkDVector vTest = sweepEnd - startPt;
+            if (sweep_contains(sweep, vTest, &direction)) {
+                return true;
+            }
+        }
+    } else {
+        for (int index = 0; index < (int) SK_ARRAY_COUNT(rh->fPart.fSweep); ++index) {
+            const SkDVector& vTest = rh->fPart.fSweep[index];
+            if (sweep_contains(sweep, vTest, &direction)) {
+                return true;
+            }
+        }
+    }
+    return false;
+}
+
 bool SkOpAngle::tangentsDiverge(const SkOpAngle* rh, double s0xt0) {
     if (s0xt0 == 0) {
         return false;
diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h
index d8615c3229..d11a1c1ee5 100644
--- a/src/pathops/SkOpAngle.h
+++ b/src/pathops/SkOpAngle.h
@@ -41,8 +41,12 @@ public:
 #endif
 
 #if DEBUG_ANGLE
+    void debugAfter(const SkOpAngle* lh, const SkOpAngle* rh, SkString* bugOut) const;
     bool debugCheckCoincidence() const { return fCheckCoincidence; }
     void debugCheckNearCoincidence() const;
+#endif
+    SkDPoint* debugFirstPt() { return &fOriginalCurvePart.fLine.fPts[0]; }
+#if DEBUG_ANGLE
     SkString debugPart() const;
 #endif
     const SkOpPtT* debugPtT(int id) const;
@@ -96,10 +100,20 @@ public:
     }
 
 private:
+    enum class Turn {
+#ifdef SK_DEBUG
+        kDebugUninitialized = -2,
+#endif
+        kCcw = -1,
+        kNone,
+        kCw
+    };
+
     bool after(SkOpAngle* test);
     void alignmentSameSide(const SkOpAngle* test, int* order) const;
     int allOnOneSide(const SkOpAngle* test);
-    bool checkCrossesZero() const;
+    Turn ccwOf(const SkOpAngle* rh, bool rhCW, bool thisCCW, bool recursed = false) const;
+    bool checkCrossesZero(int* start, int* end) const;
     bool checkParallel(SkOpAngle* );
     bool computeSector();
     int convexHullOverlaps(const SkOpAngle* );
@@ -112,9 +126,13 @@ private:
     bool midToSide(const SkOpAngle* rh, bool* inside) const;
     bool oppositePlanes(const SkOpAngle* rh) const;
     bool orderable(SkOpAngle* rh);  // false == this < rh ; true == this > rh
+    bool sectorRange(int* start, int* end, bool roundOut) const;
     void setSector();
     void setSpans();
+    bool sweepContains(const SkOpAngle* rh) const;
+    bool sweepsCCW() const;
     bool tangentsDiverge(const SkOpAngle* rh, double s0xt0);
+    Turn toTurn(bool ccw) const { return ccw ? Turn::kCcw : Turn::kCw; }
 
     SkDCurve fOriginalCurvePart;  // the curve from start to end
     SkDCurveSweep fPart;  // the curve from start to end offset as needed
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 45a1138488..6ed37dc133 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -18,7 +18,6 @@ bool SkPathOpsDebug::gDumpOp;  // set to true to write op to file before a crash
 bool SkPathOpsDebug::gVerifyOp;  // set to true to compare result against regions
 #endif
 
-bool SkPathOpsDebug::gRunFail;  // set to true to check for success on tests known to fail
 bool SkPathOpsDebug::gVeryVerbose;  // set to true to run extensive checking tests
 
 #undef FAIL_IF
@@ -667,10 +666,6 @@ void SkOpGlobalState::debugResetLoopCounts() {
 }
 #endif
 
-bool SkOpGlobalState::DebugRunFail() {
-    return SkPathOpsDebug::gRunFail;
-}
-
 // this is const so it can be called by const methods that overwise don't alter state
 #if DEBUG_VALIDATE || DEBUG_COIN
 void SkOpGlobalState::debugSetPhase(const char* funcName  DEBUG_COIN_DECLARE_PARAMS()) const {
@@ -1249,6 +1244,17 @@ void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int
    This checks the distance between start points; the distance between
 */
 #if DEBUG_ANGLE
+void SkOpAngle::debugAfter(const SkOpAngle* lh, const SkOpAngle* rh, SkString* bugOut) const {
+        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->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());
+}
+
 void SkOpAngle::debugCheckNearCoincidence() const {
     const SkOpAngle* test = this;
     do {
@@ -1376,8 +1382,8 @@ void SkOpAngle::debugValidate() const {
         }
         next = next->fNext;
     } while (next && next != first);
-    SkASSERT(wind == 0 || !SkPathOpsDebug::gRunFail);
-    SkASSERT(opp == 0 || !SkPathOpsDebug::gRunFail);
+    SkASSERT(wind == 0);
+    SkASSERT(opp == 0);
 #endif
 }
 
@@ -1404,8 +1410,8 @@ void SkOpAngle::debugValidateNext() const {
 #ifdef SK_DEBUG
 void SkCoincidentSpans::debugStartCheck(const SkOpSpanBase* outer, const SkOpSpanBase* over,
         const SkOpGlobalState* debugState) const {
-    SkASSERT(coinPtTEnd()->span() == over || !SkOpGlobalState::DebugRunFail());
-    SkASSERT(oppPtTEnd()->span() == outer || !SkOpGlobalState::DebugRunFail());
+    SkASSERT(coinPtTEnd()->span() == over);
+    SkASSERT(oppPtTEnd()->span() == outer);
 }
 #endif
 
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index 97fa534a2a..0f3fadaf14 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -374,7 +374,6 @@ public:
     static void DumpGlitchType(GlitchType );
 #endif
 
-    static bool gRunFail;
     static bool gVeryVerbose;
 
 #if DEBUG_DUMP_VERIFY
diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h
index f314f69d0e..deadbc2aa0 100644
--- a/src/pathops/SkPathOpsPoint.h
+++ b/src/pathops/SkPathOpsPoint.h
@@ -29,13 +29,29 @@ struct SkDVector {
         fY += v.fY;
     }
 
+    SkDVector operator+(const SkDVector& v) const {
+        SkDVector result = *this;
+        result += v;
+        return result;
+    }
+
     // only called by nearestT, which is currently only used by testing
     void operator-=(const SkDVector& v) {
         fX -= v.fX;
         fY -= v.fY;
     }
 
-    // only used by testing
+    SkDVector operator-(const SkDVector& v) const {
+        SkDVector result = *this;
+        result -= v;
+        return result;
+    }
+
+    SkDVector operator-() const {
+        SkDVector result = { -fX, -fY };
+        return result;
+    }
+
     void operator/=(const double s) {
         fX /= s;
         fY /= s;
@@ -89,6 +105,13 @@ struct SkDVector {
         fX *= inverseLength;
         fY *= inverseLength;
     }
+
+    void setLengthSquared(double lenSquared) {
+        double inverseLength = lenSquared / this->lengthSquared();
+        fX *= inverseLength;
+        fY *= inverseLength;
+    }
+
 };
 
 struct SkDPoint {
@@ -127,15 +150,14 @@ struct SkDPoint {
         fY -= v.fY;
     }
 
-    // only used by testing
-    SkDPoint operator+(const SkDVector& v) {
+    SkDPoint operator+(const SkDVector& v) const {
         SkDPoint result = *this;
         result += v;
         return result;
     }
 
     // only used by testing
-    SkDPoint operator-(const SkDVector& v) {
+    SkDPoint operator-(const SkDVector& v) const {
         SkDPoint result = *this;
         result -= v;
         return result;
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index f525ea49db..4e9fbe9ac5 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -77,8 +77,6 @@ public:
     const class SkOpPtT* debugPtT(int id) const;
 #endif
 
-    static bool DebugRunFail();
-
 #ifdef SK_DEBUG
     const class SkOpSegment* debugSegment(int id) const;
     bool debugSkipAssert() const { return fDebugSkipAssert; }