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/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index e3137b7..5ef702d 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -28,8 +28,14 @@
coincidence.fTs[swap][1] = ts[0][1];
coincidence.fTs[!swap][0] = ts[1][0];
coincidence.fTs[!swap][1] = ts[1][1];
- coincidence.fPts[0] = pt0;
- coincidence.fPts[1] = pt1;
+ coincidence.fPts[swap][0] = pt0;
+ coincidence.fPts[swap][1] = pt1;
+ bool nearStart = ts.nearlySame(0);
+ bool nearEnd = ts.nearlySame(1);
+ coincidence.fPts[!swap][0] = nearStart ? ts.pt2(0).asSkPoint() : pt0;
+ coincidence.fPts[!swap][1] = nearEnd ? ts.pt2(1).asSkPoint() : pt1;
+ coincidence.fNearly[0] = nearStart;
+ coincidence.fNearly[1] = nearEnd;
return true;
}
@@ -93,28 +99,31 @@
cancelers ^= true;
}
SkASSERT(!approximately_negative(oEndT - oStartT));
+ const SkPoint& startPt = coincidence.fPts[0][startSwapped];
if (cancelers) {
// make sure startT and endT have t entries
- const SkPoint& startPt = coincidence.fPts[startSwapped];
if (startT > 0 || oEndT < 1
|| thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) {
- thisOne.addTPair(startT, &other, oEndT, true, startPt);
+ thisOne.addTPair(startT, &other, oEndT, true, startPt,
+ coincidence.fPts[1][startSwapped]);
}
- const SkPoint& oStartPt = coincidence.fPts[oStartSwapped];
+ const SkPoint& oStartPt = coincidence.fPts[1][oStartSwapped];
if (oStartT > 0 || endT < 1
|| thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) {
- other.addTPair(oStartT, &thisOne, endT, true, oStartPt);
+ other.addTPair(oStartT, &thisOne, endT, true, oStartPt,
+ coincidence.fPts[0][oStartSwapped]);
}
} else {
- const SkPoint& startPt = coincidence.fPts[startSwapped];
if (startT > 0 || oStartT > 0
|| thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) {
- thisOne.addTPair(startT, &other, oStartT, true, startPt);
+ thisOne.addTPair(startT, &other, oStartT, true, startPt,
+ coincidence.fPts[1][startSwapped]);
}
- const SkPoint& oEndPt = coincidence.fPts[!oStartSwapped];
+ const SkPoint& oEndPt = coincidence.fPts[1][!oStartSwapped];
if (endT < 1 || oEndT < 1
|| thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) {
- other.addTPair(oEndT, &thisOne, endT, true, oEndPt);
+ other.addTPair(oEndT, &thisOne, endT, true, oEndPt,
+ coincidence.fPts[0][!oStartSwapped]);
}
}
#if DEBUG_CONCIDENT
@@ -122,6 +131,32 @@
other.debugShowTs("o");
#endif
}
+ // if there are multiple pairs of coincidence that share an edge, see if the opposite
+ // are also coincident
+ for (int index = 0; index < count - 1; ++index) {
+ const SkCoincidence& coincidence = fCoincidences[index];
+ int thisIndex = coincidence.fSegments[0];
+ SkOpContour* otherContour = coincidence.fOther;
+ int otherIndex = coincidence.fSegments[1];
+ for (int idx2 = 1; idx2 < count; ++idx2) {
+ const SkCoincidence& innerCoin = fCoincidences[idx2];
+ int innerThisIndex = innerCoin.fSegments[0];
+ if (thisIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 1, innerCoin, 1, false);
+ }
+ if (this == otherContour && otherIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 0, innerCoin, 1, false);
+ }
+ SkOpContour* innerOtherContour = innerCoin.fOther;
+ innerThisIndex = innerCoin.fSegments[1];
+ if (this == innerOtherContour && thisIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 1, innerCoin, 0, false);
+ }
+ if (otherContour == innerOtherContour && otherIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 0, innerCoin, 0, false);
+ }
+ }
+ }
}
bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex,
@@ -143,11 +178,77 @@
coincidence.fTs[swap][1] = ts[0][ptIndex + 1];
coincidence.fTs[!swap][0] = ts[1][ptIndex];
coincidence.fTs[!swap][1] = ts[1][ptIndex + 1];
- coincidence.fPts[0] = pt0;
- coincidence.fPts[1] = pt1;
+ coincidence.fPts[0][0] = coincidence.fPts[1][0] = pt0;
+ coincidence.fPts[0][1] = coincidence.fPts[1][1] = pt1;
+ coincidence.fNearly[0] = 0;
+ coincidence.fNearly[1] = 0;
return true;
}
+void SkOpContour::align(const SkOpSegment::AlignedSpan& aligned, bool swap,
+ SkCoincidence* coincidence) {
+ for (int idx2 = 0; idx2 < 2; ++idx2) {
+ if (coincidence->fPts[0][idx2] == aligned.fOldPt
+ && coincidence->fTs[swap][idx2] == aligned.fOldT) {
+ SkASSERT(SkDPoint::RoughlyEqual(coincidence->fPts[0][idx2], aligned.fPt));
+ coincidence->fPts[0][idx2] = aligned.fPt;
+ SkASSERT(way_roughly_equal(coincidence->fTs[swap][idx2], aligned.fT));
+ coincidence->fTs[swap][idx2] = aligned.fT;
+ }
+ }
+}
+
+void SkOpContour::alignCoincidence(const SkOpSegment::AlignedSpan& aligned,
+ SkTArray<SkCoincidence, true>* coincidences) {
+ int count = coincidences->count();
+ for (int index = 0; index < count; ++index) {
+ SkCoincidence& coincidence = (*coincidences)[index];
+ int thisIndex = coincidence.fSegments[0];
+ const SkOpSegment* thisOne = &fSegments[thisIndex];
+ const SkOpContour* otherContour = coincidence.fOther;
+ int otherIndex = coincidence.fSegments[1];
+ const SkOpSegment* other = &otherContour->fSegments[otherIndex];
+ if (thisOne == aligned.fOther1 && other == aligned.fOther2) {
+ align(aligned, false, &coincidence);
+ } else if (thisOne == aligned.fOther2 && other == aligned.fOther1) {
+ align(aligned, true, &coincidence);
+ }
+ }
+}
+
+void SkOpContour::alignTPt(int segmentIndex, const SkOpContour* other, int otherIndex,
+ bool swap, int tIndex, SkIntersections* ts, SkPoint* point) const {
+ int zeroPt;
+ if ((zeroPt = alignT(swap, tIndex, ts)) >= 0) {
+ alignPt(segmentIndex, point, zeroPt);
+ }
+ if ((zeroPt = other->alignT(!swap, tIndex, ts)) >= 0) {
+ other->alignPt(otherIndex, point, zeroPt);
+ }
+}
+
+void SkOpContour::alignPt(int index, SkPoint* point, int zeroPt) const {
+ const SkOpSegment& segment = fSegments[index];
+ if (0 == zeroPt) {
+ *point = segment.pts()[0];
+ } else {
+ *point = segment.pts()[SkPathOpsVerbToPoints(segment.verb())];
+ }
+}
+
+int SkOpContour::alignT(bool swap, int tIndex, SkIntersections* ts) const {
+ double tVal = (*ts)[swap][tIndex];
+ if (tVal != 0 && precisely_zero(tVal)) {
+ ts->set(swap, tIndex, 0);
+ return 0;
+ }
+ if (tVal != 1 && precisely_equal(tVal, 1)) {
+ ts->set(swap, tIndex, 1);
+ return 1;
+ }
+ return -1;
+}
+
bool SkOpContour::calcAngles() {
int segmentCount = fSegments.count();
for (int test = 0; test < segmentCount; ++test) {
@@ -180,7 +281,187 @@
#endif
for (int index = 0; index < count; ++index) {
SkCoincidence& coincidence = fPartialCoincidences[index];
- calcCommonCoincidentWinding(coincidence);
+ calcCommonCoincidentWinding(coincidence);
+ }
+ // if there are multiple pairs of partial coincidence that share an edge, see if the opposite
+ // are also coincident
+ for (int index = 0; index < count - 1; ++index) {
+ const SkCoincidence& coincidence = fPartialCoincidences[index];
+ int thisIndex = coincidence.fSegments[0];
+ SkOpContour* otherContour = coincidence.fOther;
+ int otherIndex = coincidence.fSegments[1];
+ for (int idx2 = 1; idx2 < count; ++idx2) {
+ const SkCoincidence& innerCoin = fPartialCoincidences[idx2];
+ int innerThisIndex = innerCoin.fSegments[0];
+ if (thisIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 1, innerCoin, 1, true);
+ }
+ if (this == otherContour && otherIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 0, innerCoin, 1, true);
+ }
+ SkOpContour* innerOtherContour = innerCoin.fOther;
+ innerThisIndex = innerCoin.fSegments[1];
+ if (this == innerOtherContour && thisIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 1, innerCoin, 0, true);
+ }
+ if (otherContour == innerOtherContour && otherIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 0, innerCoin, 0, true);
+ }
+ }
+ }
+}
+
+void SkOpContour::checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx,
+ const SkCoincidence& twoCoin, int twoIdx, bool partial) {
+ SkASSERT((oneIdx ? this : oneCoin.fOther) == (twoIdx ? this : twoCoin.fOther));
+ SkASSERT(oneCoin.fSegments[!oneIdx] == twoCoin.fSegments[!twoIdx]);
+ // look for common overlap
+ double min = SK_ScalarMax;
+ double max = SK_ScalarMin;
+ double min1 = oneCoin.fTs[!oneIdx][0];
+ double max1 = oneCoin.fTs[!oneIdx][1];
+ double min2 = twoCoin.fTs[!twoIdx][0];
+ double max2 = twoCoin.fTs[!twoIdx][1];
+ bool cancelers = (min1 < max1) != (min2 < max2);
+ if (min1 > max1) {
+ SkTSwap(min1, max1);
+ }
+ if (min2 > max2) {
+ SkTSwap(min2, max2);
+ }
+ if (between(min1, min2, max1)) {
+ min = min2;
+ }
+ if (between(min1, max2, max1)) {
+ max = max2;
+ }
+ if (between(min2, min1, max2)) {
+ min = SkTMin(min, min1);
+ }
+ if (between(min2, max1, max2)) {
+ max = SkTMax(max, max1);
+ }
+ if (min >= max) {
+ return; // no overlap
+ }
+ // look to see if opposite are different segments
+ int seg1Index = oneCoin.fSegments[oneIdx];
+ int seg2Index = twoCoin.fSegments[twoIdx];
+ if (seg1Index == seg2Index) {
+ return;
+ }
+ SkOpContour* contour1 = oneIdx ? oneCoin.fOther : this;
+ SkOpContour* contour2 = twoIdx ? twoCoin.fOther : this;
+ SkOpSegment* segment1 = &contour1->fSegments[seg1Index];
+ SkOpSegment* segment2 = &contour2->fSegments[seg2Index];
+ // find opposite t value ranges corresponding to reference min/max range
+ const SkOpContour* refContour = oneIdx ? this : oneCoin.fOther;
+ const int refSegIndex = oneCoin.fSegments[!oneIdx];
+ const SkOpSegment* refSegment = &refContour->fSegments[refSegIndex];
+ int seg1Start = segment1->findOtherT(min, refSegment);
+ int seg1End = segment1->findOtherT(max, refSegment);
+ int seg2Start = segment2->findOtherT(min, refSegment);
+ int seg2End = segment2->findOtherT(max, refSegment);
+ // if the opposite pairs already contain min/max, we're done
+ if (seg1Start >= 0 && seg1End >= 0 && seg2Start >= 0 && seg2End >= 0) {
+ return;
+ }
+ double loEnd = SkTMin(min1, min2);
+ double hiEnd = SkTMax(max1, max2);
+ // insert the missing coincident point(s)
+ double missingT1 = -1;
+ double otherT1 = -1;
+ if (seg1Start < 0) {
+ if (seg2Start < 0) {
+ return;
+ }
+ missingT1 = segment1->calcMissingTStart(refSegment, loEnd, min, max, hiEnd,
+ segment2, seg1End);
+ if (missingT1 < 0) {
+ return;
+ }
+ const SkOpSpan* missingSpan = &segment2->span(seg2Start);
+ otherT1 = missingSpan->fT;
+ } else if (seg2Start < 0) {
+ SkASSERT(seg1Start >= 0);
+ missingT1 = segment2->calcMissingTStart(refSegment, loEnd, min, max, hiEnd,
+ segment1, seg2End);
+ if (missingT1 < 0) {
+ return;
+ }
+ const SkOpSpan* missingSpan = &segment1->span(seg1Start);
+ otherT1 = missingSpan->fT;
+ }
+ SkPoint missingPt1;
+ SkOpSegment* addTo1 = NULL;
+ SkOpSegment* addOther1 = seg1Start < 0 ? segment2 : segment1;
+ int minTIndex = refSegment->findExactT(min, addOther1);
+ SkASSERT(minTIndex >= 0);
+ if (missingT1 >= 0) {
+ missingPt1 = refSegment->span(minTIndex).fPt;
+ addTo1 = seg1Start < 0 ? segment1 : segment2;
+ }
+ double missingT2 = -1;
+ double otherT2 = -1;
+ if (seg1End < 0) {
+ if (seg2End < 0) {
+ return;
+ }
+ missingT2 = segment1->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd,
+ segment2, seg1Start);
+ if (missingT2 < 0) {
+ return;
+ }
+ const SkOpSpan* missingSpan = &segment2->span(seg2End);
+ otherT2 = missingSpan->fT;
+ } else if (seg2End < 0) {
+ SkASSERT(seg1End >= 0);
+ missingT2 = segment2->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd,
+ segment1, seg2Start);
+ if (missingT2 < 0) {
+ return;
+ }
+ const SkOpSpan* missingSpan = &segment1->span(seg1End);
+ otherT2 = missingSpan->fT;
+ }
+ SkPoint missingPt2;
+ SkOpSegment* addTo2 = NULL;
+ SkOpSegment* addOther2 = seg1End < 0 ? segment2 : segment1;
+ int maxTIndex = refSegment->findExactT(max, addOther2);
+ SkASSERT(maxTIndex >= 0);
+ if (missingT2 >= 0) {
+ missingPt2 = refSegment->span(maxTIndex).fPt;
+ addTo2 = seg1End < 0 ? segment1 : segment2;
+ }
+ if (missingT1 >= 0) {
+ addTo1->pinT(missingPt1, &missingT1);
+ addTo1->addTPair(missingT1, addOther1, otherT1, false, missingPt1);
+ } else {
+ SkASSERT(minTIndex >= 0);
+ missingPt1 = refSegment->span(minTIndex).fPt;
+ }
+ if (missingT2 >= 0) {
+ addTo2->pinT(missingPt2, &missingT2);
+ addTo2->addTPair(missingT2, addOther2, otherT2, false, missingPt2);
+ } else {
+ SkASSERT(minTIndex >= 0);
+ missingPt2 = refSegment->span(maxTIndex).fPt;
+ }
+ if (!partial) {
+ return;
+ }
+ if (cancelers) {
+ if (missingT1 >= 0) {
+ addTo1->addTCancel(missingPt1, missingPt2, addOther1);
+ } else {
+ addTo2->addTCancel(missingPt1, missingPt2, addOther2);
+ }
+ } else if (missingT1 >= 0) {
+ addTo1->addTCoincident(missingPt1, missingPt2, addTo1 == addTo2 ? missingT2 : otherT2,
+ addOther1);
+ } else {
+ addTo2->addTCoincident(missingPt2, missingPt1, addTo2 == addTo1 ? missingT1 : otherT1,
+ addOther2);
}
}
@@ -196,9 +477,15 @@
const SkCoincidence& coincidence = coincidences[index];
int thisIndex = coincidence.fSegments[0];
SkOpSegment& thisOne = fSegments[thisIndex];
+ if (thisOne.done()) {
+ continue;
+ }
SkOpContour* otherContour = coincidence.fOther;
int otherIndex = coincidence.fSegments[1];
SkOpSegment& other = otherContour->fSegments[otherIndex];
+ if (other.done()) {
+ continue;
+ }
double startT = coincidence.fTs[0][0];
double endT = coincidence.fTs[0][1];
if (startT == endT) { // this can happen in very large compares
@@ -211,8 +498,8 @@
}
bool swapStart = startT > endT;
bool swapOther = oStartT > oEndT;
- const SkPoint* startPt = &coincidence.fPts[0];
- const SkPoint* endPt = &coincidence.fPts[1];
+ const SkPoint* startPt = &coincidence.fPts[0][0];
+ const SkPoint* endPt = &coincidence.fPts[0][1];
if (swapStart) {
SkTSwap(startT, endT);
SkTSwap(oStartT, oEndT);
@@ -243,6 +530,9 @@
}
void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
+ if (coincidence.fNearly[0] && coincidence.fNearly[1]) {
+ return;
+ }
int thisIndex = coincidence.fSegments[0];
SkOpSegment& thisOne = fSegments[thisIndex];
if (thisOne.done()) {
@@ -256,8 +546,8 @@
}
double startT = coincidence.fTs[0][0];
double endT = coincidence.fTs[0][1];
- const SkPoint* startPt = &coincidence.fPts[0];
- const SkPoint* endPt = &coincidence.fPts[1];
+ const SkPoint* startPt = &coincidence.fPts[0][0];
+ const SkPoint* endPt = &coincidence.fPts[0][1];
bool cancelers;
if ((cancelers = startT > endT)) {
SkTSwap<double>(startT, endT);
@@ -291,6 +581,57 @@
#endif
}
+void SkOpContour::resolveNearCoincidence() {
+ int count = fCoincidences.count();
+ for (int index = 0; index < count; ++index) {
+ SkCoincidence& coincidence = fCoincidences[index];
+ if (!coincidence.fNearly[0] || !coincidence.fNearly[1]) {
+ continue;
+ }
+ int thisIndex = coincidence.fSegments[0];
+ SkOpSegment& thisOne = fSegments[thisIndex];
+ SkOpContour* otherContour = coincidence.fOther;
+ int otherIndex = coincidence.fSegments[1];
+ SkOpSegment& other = otherContour->fSegments[otherIndex];
+ if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
+ // OPTIMIZATION: remove from coincidence array
+ continue;
+ }
+ #if DEBUG_CONCIDENT
+ thisOne.debugShowTs("-");
+ other.debugShowTs("o");
+ #endif
+ double startT = coincidence.fTs[0][0];
+ double endT = coincidence.fTs[0][1];
+ bool cancelers;
+ if ((cancelers = startT > endT)) {
+ SkTSwap<double>(startT, endT);
+ }
+ if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing
+ if (endT <= 1 - FLT_EPSILON) {
+ endT += FLT_EPSILON;
+ SkASSERT(endT <= 1);
+ } else {
+ startT -= FLT_EPSILON;
+ SkASSERT(startT >= 0);
+ }
+ }
+ SkASSERT(!approximately_negative(endT - startT));
+ double oStartT = coincidence.fTs[1][0];
+ double oEndT = coincidence.fTs[1][1];
+ if (oStartT > oEndT) {
+ SkTSwap<double>(oStartT, oEndT);
+ cancelers ^= true;
+ }
+ SkASSERT(!approximately_negative(oEndT - oStartT));
+ if (cancelers) {
+ thisOne.blindCancel(coincidence, &other);
+ } else {
+ thisOne.blindCoincident(coincidence, &other);
+ }
+ }
+}
+
void SkOpContour::sortAngles() {
int segmentCount = fSegments.count();
for (int test = 0; test < segmentCount; ++test) {