Enabling the canvas bit to turn the clip stack into a flat replace exposed around 100 failures when testing the 800K skp set generated from the top 1M web sites.

This fixes all but one of those failures.

Major changes include:
- Replace angle indices with angle pointers. This was motivated by the need to add angles later but not renumber existing angles.
- Aggressive segment chase. When the winding is known on a segment, more aggressively passing that winding to adjacent segments allows fragmented data sets to succeed.
- Line segments with ends nearly the same are treated as coincident first.
- Transfer partial coincidence by observing that if segment A is partially coincident to B and C then B and C may be partially coincident.

TBR=reed

Author: caryclark@google.com

Review URL: https://codereview.chromium.org/272153002

1 files changed, 48 insertions, 11 deletions

diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index 89695395e6..9ae0107173 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -154,15 +154,52 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) {
             computePoints(a, 1);
         }
     }
+/* Allow tracking that both sets of end points are near each other -- the lines are entirely 
+   coincident -- even when the end points are not exactly the same.
+   Mark this as a 'wild card' for the end points, so that either point is considered totally
+   coincident. Then, avoid folding the lines over each other, but allow either end to mate 
+   to the next set of lines.
+ */
     if (fAllowNear || !unparallel) {
-        for (int iA = 0; iA < 2; ++iA) {
-            if ((t = b.nearPoint(a[iA])) >= 0) {
-                insert(iA, t, a[iA]);
-            }
+        double aNearB[2];
+        double bNearA[2];
+        bool aNotB[2] = {false, false};
+        bool bNotA[2] = {false, false};
+        int nearCount = 0;
+        for (int index = 0; index < 2; ++index) {
+            aNearB[index] = t = b.nearPoint(a[index], &aNotB[index]);
+            nearCount += t >= 0;
+            bNearA[index] = t = a.nearPoint(b[index], &bNotA[index]);
+            nearCount += t >= 0;
         }
-        for (int iB = 0; iB < 2; ++iB) {
-            if ((t = a.nearPoint(b[iB])) >= 0) {
-                insert(t, iB, b[iB]);
+        if (nearCount > 0) {
+            for (int iA = 0; iA < 2; ++iA) {
+                if (!aNotB[iA]) {
+                    continue;
+                }
+                int nearer = aNearB[iA] > 0.5;
+                if (!bNotA[nearer]) {
+                    continue;
+                }
+                SkASSERT(a[iA] != b[nearer]);
+                SkASSERT(iA == (bNearA[nearer] > 0.5));
+                fNearlySame[iA] = true;
+                insertNear(iA, nearer, a[iA], b[nearer]);
+                aNearB[iA] = -1;
+                bNearA[nearer] = -1;
+                nearCount -= 2;
+            }
+            if (nearCount > 0) {
+                for (int iA = 0; iA < 2; ++iA) {
+                    if (aNearB[iA] >= 0) {
+                        insert(iA, aNearB[iA], a[iA]);
+                    }
+                }
+                for (int iB = 0; iB < 2; ++iB) {
+                    if (bNearA[iB] >= 0) {
+                        insert(bNearA[iB], iB, b[iB]);
+                    }
+                }
             }
         }
     }
@@ -240,12 +277,12 @@ int SkIntersections::horizontal(const SkDLine& line, double left, double right,
         }
     }
     if (fAllowNear || result == 2) {
-        if ((t = line.nearPoint(leftPt)) >= 0) {
+        if ((t = line.nearPoint(leftPt, NULL)) >= 0) {
             insert(t, (double) flipped, leftPt);
         }
         if (left != right) {
             const SkDPoint rightPt = { right, y };
-            if ((t = line.nearPoint(rightPt)) >= 0) {
+            if ((t = line.nearPoint(rightPt, NULL)) >= 0) {
                 insert(t, (double) !flipped, rightPt);
             }
             for (int index = 0; index < 2; ++index) {
@@ -328,12 +365,12 @@ int SkIntersections::vertical(const SkDLine& line, double top, double bottom,
         }
     }
     if (fAllowNear || result == 2) {
-        if ((t = line.nearPoint(topPt)) >= 0) {
+        if ((t = line.nearPoint(topPt, NULL)) >= 0) {
             insert(t, (double) flipped, topPt);
         }
         if (top != bottom) {
             SkDPoint bottomPt = { x, bottom };
-            if ((t = line.nearPoint(bottomPt)) >= 0) {
+            if ((t = line.nearPoint(bottomPt, NULL)) >= 0) {
                 insert(t, (double) !flipped, bottomPt);
             }
             for (int index = 0; index < 2; ++index) {