update pathops to circle sort

src/pathops/SkPathOpsCommon.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 "SkAddIntersections.h"
 #include "SkOpEdgeBuilder.h"
 #include "SkPathOpsCommon.h"
 #include "SkPathWriter.h"
@@ skipping 93 matching lines @@
     for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
         SkOpContour* contour = contourList[cIndex];
         result = contour->undoneSegment(start, end);
         if (result) {
             return result;
         }
     }
     return NULL;
 }
 
-SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex) {
-    while (chase.count()) {
+SkOpSegment* FindChase(SkTDArray<SkOpSpan*>* chase, int* tIndex, int* endIndex) {
+    while (chase->count()) {
         SkOpSpan* span;
-        chase.pop(&span);
+        chase->pop(&span);
         const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
         SkOpSegment* segment = backPtr.fOther;
-        tIndex = backPtr.fOtherIndex;
-        SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
-        int done = 0;
-        if (segment->activeAngle(tIndex, &done, &angles)) {
-            SkOpAngle* last = angles.end() - 1;
-            tIndex = last->start();
-            endIndex = last->end();
-   #if TRY_ROTATE
-            *chase.insert(0) = span;
-   #else
-            *chase.append() = span;
-   #endif
+        *tIndex = backPtr.fOtherIndex;
+        bool sortable = true;
+        bool done = true;
+        *endIndex = -1;
+        if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done,
+                &sortable)) {
+            *tIndex = last->start();
+            *endIndex = last->end();
+    #if TRY_ROTATE
+            *chase->insert(0) = span;
+    #else
+            *chase->append() = span;
+    #endif
             return last->segment();
         }
-        if (done == angles.count()) {
+        if (done) {
             continue;
         }
-        SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
-        bool sortable = SkOpSegment::SortAngles(angles, &sorted,
-                SkOpSegment::kMayBeUnordered_SortAngleKind);
-        int angleCount = sorted.count();
-#if DEBUG_SORT
-        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0, sortable);
-#endif
         if (!sortable) {
             continue;
         }
         // find first angle, initialize winding to computed fWindSum
-        int firstIndex = -1;
-        const SkOpAngle* angle;
+        const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex);
+        const SkOpAngle* firstAngle;
+        SkDEBUGCODE(firstAngle = angle);
+        SkDEBUGCODE(bool loop = false);
         int winding;
         do {
-            angle = sorted[++firstIndex];
+            angle = angle->next();
+            SkASSERT(angle != firstAngle || !loop);
+            SkDEBUGCODE(loop |= angle == firstAngle);
             segment = angle->segment();
             winding = segment->windSum(angle);
         } while (winding == SK_MinS32);
         int spanWinding = segment->spanSign(angle->start(), angle->end());
     #if DEBUG_WINDING
-        SkDebugf("%s winding=%d spanWinding=%d\n",
-                __FUNCTION__, winding, spanWinding);
+        SkDebugf("%s winding=%d spanWinding=%d\n", __FUNCTION__, winding, spanWinding);
     #endif
         // turn span winding into contour winding
         if (spanWinding * winding < 0) {
             winding += spanWinding;
         }
-    #if DEBUG_SORT
-        segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0, sortable);
-    #endif
         // we care about first sign and whether wind sum indicates this
         // edge is inside or outside. Maybe need to pass span winding
         // or first winding or something into this function?
         // advance to first undone angle, then return it and winding
         // (to set whether edges are active or not)
-        int nextIndex = firstIndex + 1;
-        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
-        angle = sorted[firstIndex];
-        winding -= angle->segment()->spanSign(angle);
-        do {
-            SkASSERT(nextIndex != firstIndex);
-            if (nextIndex == angleCount) {
-                nextIndex = 0;
-            }
-            angle = sorted[nextIndex];
+        firstAngle = angle;
+        winding -= firstAngle->segment()->spanSign(firstAngle);
+        while ((angle = angle->next()) != firstAngle) {
             segment = angle->segment();
             int maxWinding = winding;
             winding -= segment->spanSign(angle);
     #if DEBUG_SORT
             SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__,
                     segment->debugID(), maxWinding, winding, angle->sign());
     #endif
-            tIndex = angle->start();
-            endIndex = angle->end();
-            int lesser = SkMin32(tIndex, endIndex);
+            *tIndex = angle->start();
+            *endIndex = angle->end();
+            int lesser = SkMin32(*tIndex, *endIndex);
             const SkOpSpan& nextSpan = segment->span(lesser);
             if (!nextSpan.fDone) {
             // FIXME: this be wrong? assign startWinding if edge is in
             // same direction. If the direction is opposite, winding to
             // assign is flipped sign or +/- 1?
                 if (SkOpSegment::UseInnerWinding(maxWinding, winding)) {
                     maxWinding = winding;
                 }
                 segment->markAndChaseWinding(angle, maxWinding, 0);
                 break;
             }
-        } while (++nextIndex != lastIndex);
-        *chase.insert(0) = span;
+        }
+        *chase->insert(0) = span;
         return segment;
     }
     return NULL;
 }
 
 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
 void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList) {
     int index;
     for (index = 0; index < contourList.count(); ++ index) {
         contourList[index]->debugShowActiveSpans();
     }
 }
 #endif
 
 static SkOpSegment* findSortableTop(const SkTArray<SkOpContour*, true>& contourList,
                                     int* index, int* endIndex, SkPoint* topLeft, bool* unsortable,
                                     bool* done, bool onlySortable) {
     SkOpSegment* result;
+    const SkOpSegment* lastTopStart = NULL;
+    int lastIndex = -1, lastEndIndex = -1;
     do {
         SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax};
         int contourCount = contourList.count();
         SkOpSegment* topStart = NULL;
         *done = true;
         for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
             SkOpContour* contour = contourList[cIndex];
             if (contour->done()) {
                 continue;
             }
             const SkPathOpsBounds& bounds = contour->bounds();
             if (bounds.fBottom < topLeft->fY) {
                 *done = false;
                 continue;
             }
             if (bounds.fBottom == topLeft->fY && bounds.fRight < topLeft->fX) {
                 *done = false;
                 continue;
             }
             contour->topSortableSegment(*topLeft, &bestXY, &topStart);
             if (!contour->done()) {
                 *done = false;
             }
         }
         if (!topStart) {
             return NULL;
         }
         *topLeft = bestXY;
-        result = topStart->findTop(index, endIndex, unsortable, onlySortable);
+        result = topStart->findTop(index, endIndex, unsortable);
+        if (!result) {
+            if (lastTopStart == topStart && lastIndex == *index && lastEndIndex == *endIndex) {
+                *done = true;
+                return NULL;
+            }
+            lastTopStart = topStart;
+            lastIndex = *index;
+            lastEndIndex = *endIndex;
+        }
     } while (!result);
     if (result) {
         *unsortable = false;
     }
     return result;
 }
 
 static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList,
                              SkOpSegment** current, int* index, int* endIndex, double* tHit,
                              SkScalar* hitDx, bool* tryAgain, bool opp) {
@@ skipping 33 matching lines @@
         SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr,
         int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done) {
     SkOpSegment* current = findSortableTop(contourList, indexPtr, endIndexPtr, topLeft, unsortable,
             done, true);
     if (!current) {
         return NULL;
     }
     const int index = *indexPtr;
     const int endIndex = *endIndexPtr;
     if (*firstContour) {
-        current->initWinding(index, endIndex);
+        current->initWinding(index, endIndex, angleIncludeType);
         *firstContour = false;
         return current;
     }
     int minIndex = SkMin32(index, endIndex);
     int sumWinding = current->windSum(minIndex);
     if (sumWinding != SK_MinS32) {
         return current;
     }
     SkASSERT(current->windSum(SkMin32(index, endIndex)) == SK_MinS32);
-    SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
-    SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
-    sumWinding = current->computeSum(index, endIndex, angleIncludeType, &angles, &sorted);
+    const SkOpSpan& span = current->span(endIndex);
+    if ((index < endIndex ? span.fFromAngleIndex : span.fToAngleIndex) < 0) {
+        current->addSimpleAngle(endIndex);
+    }
+    sumWinding = current->computeSum(index, endIndex, angleIncludeType);
     if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) {
         return current;
     }
     int contourWinding;
     int oppContourWinding = 0;
     // the simple upward projection of the unresolved points hit unsortable angles
     // shoot rays at right angles to the segment to find its winding, ignoring angle cases
     bool tryAgain;
     double tHit;
     SkScalar hitDx = 0;
@@ skipping 15 matching lines @@
             break;
         }
         oppContourWinding = rightAngleWinding(contourList, &current, indexPtr, endIndexPtr, &tHit,
                 &hitOppDx, &tryAgain, true);
     } while (tryAgain);
     current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, oppContourWinding,
             hitOppDx);
     return current;
 }
 
+static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) {
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        if (!contour->calcAngles()) {
+            return false;
+        }
+    }
+    return true;
+}
+
+static void checkDuplicates(SkTArray<SkOpContour*, true>* contourList) {
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        contour->checkDuplicates();
+    }
+}
+
 static void checkEnds(SkTArray<SkOpContour*, true>* contourList) {
     // it's hard to determine if the end of a cubic or conic nearly intersects another curve.
     // instead, look to see if the connecting curve intersected at that same end.
     int contourCount = (*contourList).count();
     for (int cTest = 0; cTest < contourCount; ++cTest) {
         SkOpContour* contour = (*contourList)[cTest];
         contour->checkEnds();
     }
 }
 
+static void checkMultiples(SkTArray<SkOpContour*, true>* contourList) {
+    // it's hard to determine if the end of a cubic or conic nearly intersects another curve.
+    // instead, look to see if the connecting curve intersected at that same end.
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        contour->checkMultiples();
+    }
+}
+
+// A small interval of a pair of curves may collapse to lines for each, triggering coincidence
+static void checkSmall(SkTArray<SkOpContour*, true>* contourList) {
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        contour->checkSmall();
+    }
+}
+
 // A tiny interval may indicate an undiscovered coincidence. Find and fix.
 static void checkTiny(SkTArray<SkOpContour*, true>* contourList) {
     int contourCount = (*contourList).count();
     for (int cTest = 0; cTest < contourCount; ++cTest) {
         SkOpContour* contour = (*contourList)[cTest];
         contour->checkTiny();
     }
 }
 
 static void fixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) {
     int contourCount = (*contourList).count();
     for (int cTest = 0; cTest < contourCount; ++cTest) {
         SkOpContour* contour = (*contourList)[cTest];
         contour->fixOtherTIndex();
     }
 }
 
 static void joinCoincidence(SkTArray<SkOpContour*, true>* contourList) {
     int contourCount = (*contourList).count();
     for (int cTest = 0; cTest < contourCount; ++cTest) {
         SkOpContour* contour = (*contourList)[cTest];
         contour->joinCoincidence();
     }
 }
 
+static void sortAngles(SkTArray<SkOpContour*, true>* contourList) {
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        contour->sortAngles();
+    }
+}
+
 static void sortSegments(SkTArray<SkOpContour*, true>* contourList) {
     int contourCount = (*contourList).count();
     for (int cTest = 0; cTest < contourCount; ++cTest) {
         SkOpContour* contour = (*contourList)[cTest];
         contour->sortSegments();
     }
 }
 
 void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, true>& list,
                      bool evenOdd, bool oppEvenOdd) {
@@ skipping 207 matching lines @@
         }
     } while (rIndex < count);
 #if DEBUG_ASSEMBLE
     for (rIndex = 0; rIndex < count; ++rIndex) {
        SkASSERT(sLink[rIndex] == SK_MaxS32);
        SkASSERT(eLink[rIndex] == SK_MaxS32);
     }
 #endif
 }
 
-void HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) {
+bool HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) {
 #if DEBUG_SHOW_WINDING
     SkOpContour::debugShowWindingValues(contourList);
 #endif
     CoincidenceCheck(contourList, total);
 #if DEBUG_SHOW_WINDING
     SkOpContour::debugShowWindingValues(contourList);
 #endif
     fixOtherTIndex(contourList);
     checkEnds(contourList);
+    checkMultiples(contourList);
+    checkDuplicates(contourList);
     checkTiny(contourList);
+    checkSmall(contourList);
     joinCoincidence(contourList);
     sortSegments(contourList);
+    if (!calcAngles(contourList)) {
+        return false;
+    }
+    sortAngles(contourList);
 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
     DebugShowActiveSpans(*contourList);
 #endif
+    return true;
 }