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
diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index 8969539..9ae0107 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -154,15 +154,52 @@
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 @@
}
}
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 @@
}
}
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) {