break ambiguous angle sorting loop

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 "SkOpAngle.h"
 #include "SkOpSegment.h"
 #include "SkPathOpsCurve.h"
 #include "SkTSort.h"
@@ skipping 302 matching lines @@
         return false;
     }
     SkOpSpanBase* saveEnd = fEnd;
     fComputedEnd = fEnd = computedEnd;
     setSpans();
     setSector();
     fEnd = saveEnd;
     return !fUnorderable;
 }
 
-int SkOpAngle::convexHullOverlaps(const SkOpAngle* rh) const {
+int SkOpAngle::convexHullOverlaps(const SkOpAngle* rh) {
     const SkDVector* sweep = this->fPart.fSweep;
     const SkDVector* tweep = rh->fPart.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]);
@@ skipping 252 matching lines @@
     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) {
+bool SkOpAngle::insert(SkOpAngle* angle) {
     if (angle->fNext) {
         if (loopCount() >= angle->loopCount()) {
             if (!merge(angle)) {
-                return;
+                return true;
             }
         } else if (fNext) {
             if (!angle->merge(this)) {
-                return;
+                return true;
             }
         } else {
             angle->insert(this);
         }
-        return;
+        return true;
     }
     bool singleton = nullptr == fNext;
     if (singleton) {
         fNext = this;
     }
     SkOpAngle* next = fNext;
     if (next->fNext == this) {
         if (singleton || angle->after(this)) {
             this->fNext = angle;
             angle->fNext = next;
         } else {
             next->fNext = angle;
             angle->fNext = this;
         }
         debugValidateNext();
-        return;
+        return true;
     }
     SkOpAngle* last = this;
+    bool flipAmbiguity = false;
     do {
         SkASSERT(last->fNext == next);
-        if (angle->after(last)) {
+        if (angle->after(last) ^ (angle->tangentsAmbiguous() & flipAmbiguity)) {
             last->fNext = angle;
             angle->fNext = next;
             debugValidateNext();
-            return;
+            return true;
         }
         last = next;
+        if (last == this) {
+            FAIL_IF(flipAmbiguity);
+            // We're in a loop. If a sort was ambiguous, flip it to end the loop.
+            flipAmbiguity = true;
+        }
         next = next->fNext;
     } while (true);
+    return true;
 }
 
 SkOpSpanBase* SkOpAngle::lastMarked() const {
     if (fLastMarked) {
         if (fLastMarked->chased()) {
             return nullptr;
         }
         fLastMarked->setChased(true);
     }
     return fLastMarked;
@@ skipping 159 matching lines @@
 
 SkOpSegment* SkOpAngle::segment() const {
     return fStart->segment();
 }
 
 void SkOpAngle::set(SkOpSpanBase* start, SkOpSpanBase* end) {
     fStart = start;
     fComputedEnd = fEnd = end;
     SkASSERT(start != end);
     fNext = nullptr;
-    fComputeSector = fComputedSector = fCheckCoincidence = false;
+    fComputeSector = fComputedSector = fCheckCoincidence = fTangentsAmbiguous = false;
     setSpans();
     setSector();
     SkDEBUGCODE(fID = start ? start->globalState()->nextAngleID() : -1);
 }
 
 void SkOpAngle::setSpans() {
     fUnorderable = false;
     fLastMarked = nullptr;
     if (!fStart) {
         fUnorderable = true;
@@ skipping 130 matching lines @@
         fSectorMask = (unsigned) -1 >> (31 - end + start) << start;
     } else {
         fSectorMask = (unsigned) -1 >> (31 - start) | ((unsigned) -1 << end);
     }
 }
 
 SkOpSpan* SkOpAngle::starter() {
     return fStart->starter(fEnd);
 }
 
-bool SkOpAngle::tangentsDiverge(const SkOpAngle* rh, double s0xt0) const {
+bool SkOpAngle::tangentsDiverge(const SkOpAngle* rh, double s0xt0) {
     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 = fPart.fSweep;
     const SkDVector* tweep = rh->fPart.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 ? this->distEndRatio(sDist) : rh->distEndRatio(tDist));
+    fTangentsAmbiguous = mFactor >= 50 && mFactor < 200;
     return mFactor < 50;   // empirically found limit
 }