fix bugs found by computing flat clips in 800K skps

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"
 #include "SkTSort.h"
 
+static void alignMultiples(SkTArray<SkOpContour*, true>* contourList,
+        SkTDArray<SkOpSegment::AlignedSpan>* aligned) {
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        if (contour->hasMultiples()) {
+            contour->alignMultiples(aligned);
+        }
+    }
+}
+
+static void alignCoincidence(SkTArray<SkOpContour*, true>* contourList,
+        const SkTDArray<SkOpSegment::AlignedSpan>& aligned) {
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        int count = aligned.count();
+        for (int index = 0; index < count; ++index) {
+            contour->alignCoincidence(aligned[index]);
+        }
+    }    
+}
+
 static int contourRangeCheckY(const SkTArray<SkOpContour*, true>& contourList, SkOpSegment** currentPtr,
                               int* indexPtr, int* endIndexPtr, double* bestHit, SkScalar* bestDx,
                               bool* tryAgain, double* midPtr, bool opp) {
     const int index = *indexPtr;
     const int endIndex = *endIndexPtr;
     const double mid = *midPtr;
     const SkOpSegment* current = *currentPtr;
     double tAtMid = current->tAtMid(index, endIndex, mid);
     SkPoint basePt = current->ptAtT(tAtMid);
     int contourCount = contourList.count();
@@ skipping 155 matching lines @@
             *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);
+                (void) segment->markAndChaseWinding(angle, maxWinding, 0);
                 break;
             }
         }
         *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 firstPass) {
+static SkOpSegment* findTopSegment(const SkTArray<SkOpContour*, true>& contourList, int* index,
+        int* endIndex, SkPoint* topLeft, bool* unsortable, bool* done, bool firstPass) {
     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];
@@ skipping 22 matching lines @@
         if (!result) {
             if (lastTopStart == topStart && lastIndex == *index && lastEndIndex == *endIndex) {
                 *done = true;
                 return NULL;
             }
             lastTopStart = topStart;
             lastIndex = *index;
             lastEndIndex = *endIndex;
         }
     } while (!result);
-#if 0
-    if (result) {
-        *unsortable = false;
-    }
-#endif
     return result;
 }
 
 static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList,
-                             SkOpSegment** current, int* index, int* endIndex, double* tHit,
-                             SkScalar* hitDx, bool* tryAgain, bool opp) {
+        SkOpSegment** currentPtr, int* indexPtr, int* endIndexPtr, double* tHit,
+        SkScalar* hitDx, bool* tryAgain, bool* onlyVertical, bool opp) {
     double test = 0.9;
     int contourWinding;
     do {
-        contourWinding = contourRangeCheckY(contourList, current, index, endIndex, tHit, hitDx,
-                tryAgain, &test, opp);
+        contourWinding = contourRangeCheckY(contourList, currentPtr, indexPtr, endIndexPtr,
+                tHit, hitDx, tryAgain, &test, opp);
         if (contourWinding != SK_MinS32 || *tryAgain) {
             return contourWinding;
         }
+        if (*currentPtr && (*currentPtr)->isVertical()) {
+            *onlyVertical = true;
+            return contourWinding;
+        }
         test /= 2;
     } while (!approximately_negative(test));
-    SkASSERT(0);  // should be OK to comment out, but interested when this hits
+    SkASSERT(0);  // FIXME: incomplete functionality
     return contourWinding;
 }
 
 static void skipVertical(const SkTArray<SkOpContour*, true>& contourList,
         SkOpSegment** current, int* index, int* endIndex) {
     if (!(*current)->isVertical(*index, *endIndex)) {
         return;
     }
     int contourCount = contourList.count();
     for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
         SkOpContour* contour = contourList[cIndex];
         if (contour->done()) {
             continue;
         }
         SkOpSegment* nonVertical = contour->nonVerticalSegment(index, endIndex);
         if (nonVertical) {
             *current = nonVertical;
             return;
         }
     }
     return;
 }
 
 SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
         SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr,
-        int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool firstPass) {
-    SkOpSegment* current = findSortableTop(contourList, indexPtr, endIndexPtr, topLeft, unsortable,
+        int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical,
+        bool firstPass) {
+    SkOpSegment* current = findTopSegment(contourList, indexPtr, endIndexPtr, topLeft, unsortable,
             done, firstPass);
     if (!current) {
         return NULL;
     }
-    const int index = *indexPtr;
+    const int startIndex = *indexPtr;
     const int endIndex = *endIndexPtr;
     if (*firstContour) {
-        current->initWinding(index, endIndex, angleIncludeType);
+        current->initWinding(startIndex, endIndex, angleIncludeType);
         *firstContour = false;
         return current;
     }
-    int minIndex = SkMin32(index, endIndex);
+    int minIndex = SkMin32(startIndex, endIndex);
     int sumWinding = current->windSum(minIndex);
-    if (sumWinding != SK_MinS32) {
-        return current;
+    if (sumWinding == SK_MinS32) {
+        int index = endIndex;
+        int oIndex = startIndex;
+        do { 
+            const SkOpSpan& span = current->span(index);
+            if ((oIndex < index ? span.fFromAngle : span.fToAngle) == NULL) {
+                current->addSimpleAngle(index);
+            }
+            sumWinding = current->computeSum(oIndex, index, angleIncludeType);
+            SkTSwap(index, oIndex);
+        } while (sumWinding == SK_MinS32 && index == startIndex);
     }
-    SkASSERT(current->windSum(SkMin32(index, endIndex)) == SK_MinS32);
-    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;
     SkScalar hitOppDx = 0;
     do {
         // if current is vertical, find another candidate which is not
         // if only remaining candidates are vertical, then they can be marked done
         SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
         skipVertical(contourList, &current, indexPtr, endIndexPtr);
         SkASSERT(current);  // FIXME: if null, all remaining are vertical
         SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
         tryAgain = false;
         contourWinding = rightAngleWinding(contourList, &current, indexPtr, endIndexPtr, &tHit,
-                &hitDx, &tryAgain, false);
+                &hitDx, &tryAgain, onlyVertical, false);
+        if (*onlyVertical) {
+            return current;
+        }
         if (tryAgain) {
             continue;
         }
         if (angleIncludeType < SkOpAngle::kBinarySingle) {
             break;
         }
         oppContourWinding = rightAngleWinding(contourList, &current, indexPtr, endIndexPtr, &tHit,
-                &hitOppDx, &tryAgain, true);
+                &hitOppDx, &tryAgain, NULL, true);
     } while (tryAgain);
     current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, oppContourWinding,
             hitOppDx);
     if (current->done()) {
         return NULL;
     }
     return current;
 }
 
 static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) {
@@ skipping 18 matching lines @@
 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.
+static bool checkMultiples(SkTArray<SkOpContour*, true>* contourList) {
+    bool hasMultiples = false;
     int contourCount = (*contourList).count();
     for (int cTest = 0; cTest < contourCount; ++cTest) {
         SkOpContour* contour = (*contourList)[cTest];
         contour->checkMultiples();
+        hasMultiples |= contour->hasMultiples();
     }
+    return hasMultiples;
 }
 
 // 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();
     }
 }
@@ skipping 260 matching lines @@
 
 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);
+    checkEnds(contourList);  // check if connecting curve intersected at the same end
+    bool hasM = checkMultiples(contourList);  // check if intersections agree on t and point values
+    SkTDArray<SkOpSegment::AlignedSpan> aligned;
+    if (hasM) {
+        alignMultiples(contourList, &aligned);  // align pairs of identical points
+        alignCoincidence(contourList, aligned);
+    }
+    checkDuplicates(contourList);  // check if spans have the same number on the other end
+    checkTiny(contourList);  // if pair have the same end points, mark them as parallel
+    checkSmall(contourList);  // a pair of curves with a small span may turn into coincident lines
+    joinCoincidence(contourList);  // join curves that connect to a coincident pair
     sortSegments(contourList);
     if (!calcAngles(contourList)) {
         return false;
     }
     sortAngles(contourList);
 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
     DebugShowActiveSpans(*contourList);
 #endif
     return true;
 }