optimize pathops coverage
Remove unused code from SkOpSegment.cpp and friends.
Add new tests exposed by coverage.
Fix a bug exposed by coverage -- removing the need to detect points that are nearby when intersecting.
Add gyp rule for building coverage flavor on Mac.
R=mtklein@google.com
Author: caryclark@google.com
Review URL: https://codereview.chromium.org/75453003
git-svn-id: http://skia.googlecode.com/svn/trunk/src@12344 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/pathops/SkAddIntersections.cpp b/pathops/SkAddIntersections.cpp
index 7d5fc0d..035a50e 100644
--- a/pathops/SkAddIntersections.cpp
+++ b/pathops/SkAddIntersections.cpp
@@ -397,8 +397,8 @@
SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1);
SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1);
SkPoint point = ts.pt(pt).asSkPoint();
- int testTAt = wt.addT(wn, point, ts[swap][pt], swap && ts.isNear(pt));
- int nextTAt = wn.addT(wt, point, ts[!swap][pt], !swap && ts.isNear(pt));
+ int testTAt = wt.addT(wn, point, ts[swap][pt]);
+ int nextTAt = wn.addT(wt, point, ts[!swap][pt]);
wt.addOtherT(testTAt, ts[!swap][pt], nextTAt);
wn.addOtherT(nextTAt, ts[swap][pt], testTAt);
}
@@ -425,7 +425,7 @@
SkASSERT(ts[1][0] >= 0 && ts[1][0] <= 1);
SkPoint point = ts.pt(0).asSkPoint();
int testTAt = wt.addSelfT(wt, point, ts[0][0]);
- int nextTAt = wt.addT(wt, point, ts[1][0], ts.isNear(0));
+ int nextTAt = wt.addT(wt, point, ts[1][0]);
wt.addOtherT(testTAt, ts[1][0], nextTAt);
wt.addOtherT(nextTAt, ts[0][0], testTAt);
} while (wt.advance());
diff --git a/pathops/SkDQuadIntersection.cpp b/pathops/SkDQuadIntersection.cpp
index 4872508..685a01f 100644
--- a/pathops/SkDQuadIntersection.cpp
+++ b/pathops/SkDQuadIntersection.cpp
@@ -162,7 +162,7 @@
#ifdef SK_DEBUG
SkDPoint qPt = q2.ptAtT(t);
SkDPoint lPt = testLines[index]->ptAtT(rootTs[1][idx2]);
- SkASSERT(qPt.approximatelyEqual(lPt));
+ SkASSERT(qPt.approximatelyPEqual(lPt));
#endif
if (approximately_negative(t - t2s) || approximately_positive(t - t2e)) {
continue;
@@ -399,20 +399,11 @@
// if the quads share an end point, check to see if they overlap
for (int i1 = 0; i1 < 3; i1 += 2) {
for (int i2 = 0; i2 < 3; i2 += 2) {
- if (q1[i1] == q2[i2]) {
+ if (q1[i1].asSkPoint() == q2[i2].asSkPoint()) {
insert(i1 >> 1, i2 >> 1, q1[i1]);
}
}
}
- if (fAllowNear || true) { // FIXME ? cubic/cubic intersection fails without (cubicOp67u)
- for (int i1 = 0; i1 < 3; i1 += 2) {
- for (int i2 = 0; i2 < 3; i2 += 2) {
- if (q1[i1] != q2[i2] && q1[i1].approximatelyEqual(q2[i2])) {
- insertNear(i1 >> 1, i2 >> 1, q1[i1]);
- }
- }
- }
- }
SkASSERT(fUsed < 3);
if (only_end_pts_in_common(q1, q2)) {
return fUsed;
diff --git a/pathops/SkIntersectionHelper.h b/pathops/SkIntersectionHelper.h
index 1d7b639..fa1aa69 100644
--- a/pathops/SkIntersectionHelper.h
+++ b/pathops/SkIntersectionHelper.h
@@ -42,8 +42,8 @@
// be nearly equal, any problems caused by this should be taken care
// of later.
// On the edge or out of range values are negative; add 2 to get end
- int addT(const SkIntersectionHelper& other, const SkPoint& pt, double newT, bool isNear) {
- return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT, isNear);
+ int addT(const SkIntersectionHelper& other, const SkPoint& pt, double newT) {
+ return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT);
}
int addSelfT(const SkIntersectionHelper& other, const SkPoint& pt, double newT) {
@@ -77,14 +77,6 @@
&& next.fIndex == fLast - 1;
}
- bool isNear(double t1, double t2, const SkDPoint& pt1, const SkDPoint& pt2) const {
- const SkOpSegment& segment = fContour->segments()[fIndex];
- double mid = (t1 + t2) / 2;
- SkDPoint midPtByT = segment.dPtAtT(mid);
- SkDPoint midPtByAvg = SkDPoint::Mid(pt1, pt2);
- return midPtByT.approximatelyEqual(midPtByAvg);
- }
-
bool isPartial(double t1, double t2, const SkDPoint& pt1, const SkDPoint& pt2) const {
const SkOpSegment& segment = fContour->segments()[fIndex];
double mid = (t1 + t2) / 2;
diff --git a/pathops/SkIntersections.cpp b/pathops/SkIntersections.cpp
index 35846f6..53cd6fe 100644
--- a/pathops/SkIntersections.cpp
+++ b/pathops/SkIntersections.cpp
@@ -108,7 +108,6 @@
int clearMask = ~((1 << index) - 1);
fIsCoincident[0] += fIsCoincident[0] & clearMask;
fIsCoincident[1] += fIsCoincident[1] & clearMask;
- fIsNear += fIsNear & clearMask;
}
fPt[index] = pt;
fT[0][index] = one;
@@ -117,14 +116,6 @@
return index;
}
-void SkIntersections::insertNear(double one, double two, const SkDPoint& pt) {
- int index = insert(one, two, pt);
- if (index < 0) {
- return;
- }
- fIsNear |= 1 << index;
-}
-
void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
int index = insertSwap(one, two, pt);
int bit = 1 << index;
@@ -188,7 +179,6 @@
fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
- fIsNear -= ((fIsNear >> 1) & ~((1 << index) - 1)) + (fIsNear & (1 << index));
}
void SkIntersections::swapPts() {
diff --git a/pathops/SkIntersections.h b/pathops/SkIntersections.h
index a3e8332..0e3fcd1 100644
--- a/pathops/SkIntersections.h
+++ b/pathops/SkIntersections.h
@@ -23,7 +23,6 @@
sk_bzero(fPt, sizeof(fPt));
sk_bzero(fT, sizeof(fT));
sk_bzero(fIsCoincident, sizeof(fIsCoincident));
- sk_bzero(&fIsNear, sizeof(fIsNear));
reset();
fMax = 0; // require that the caller set the max
}
@@ -42,7 +41,6 @@
memcpy(fPt, i.fPt, sizeof(fPt));
memcpy(fT, i.fT, sizeof(fT));
memcpy(fIsCoincident, i.fIsCoincident, sizeof(fIsCoincident));
- memcpy(&fIsNear, &i.fIsNear, sizeof(fIsNear));
fUsed = i.fUsed;
fMax = i.fMax;
fSwap = i.fSwap;
@@ -119,10 +117,6 @@
return (fIsCoincident[0] & 1 << index) != 0;
}
- bool isNear(int index) {
- return (fIsNear & 1 << index) != 0;
- }
-
int lineHorizontal(const SkPoint a[2], SkScalar left, SkScalar right, SkScalar y,
bool flipped) {
SkDLine line;
@@ -278,7 +272,6 @@
SkDPoint fPt[9]; // FIXME: since scans store points as SkPoint, this should also
double fT[2][9];
uint16_t fIsCoincident[2]; // bit set for each curve's coincident T
- uint16_t fIsNear; // bit set for each T if 2nd curve's point is near but not equal to 1st
unsigned char fUsed;
unsigned char fMax;
bool fAllowNear;
diff --git a/pathops/SkLineParameters.h b/pathops/SkLineParameters.h
index 9cbd852..0407485 100644
--- a/pathops/SkLineParameters.h
+++ b/pathops/SkLineParameters.h
@@ -23,13 +23,42 @@
class SkLineParameters {
public:
+
void cubicEndPoints(const SkDCubic& pts) {
- cubicEndPoints(pts, 0, 1);
- if (dx() == 0 && dy() == 0) {
- cubicEndPoints(pts, 0, 2);
- if (dx() == 0 && dy() == 0) {
- cubicEndPoints(pts, 0, 3);
+ int endIndex = 1;
+ cubicEndPoints(pts, 0, endIndex);
+ if (dy() != 0) {
+ return;
+ }
+ if (dx() == 0) {
+ cubicEndPoints(pts, 0, ++endIndex);
+ SkASSERT(endIndex == 2);
+ if (dy() != 0) {
+ return;
}
+ if (dx() == 0) {
+ cubicEndPoints(pts, 0, ++endIndex); // line
+ SkASSERT(endIndex == 3);
+ return;
+ }
+ }
+ if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
+ return;
+ }
+ // if cubic tangent is on x axis, look at next control point to break tie
+ // control point may be approximate, so it must move significantly to account for error
+ if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) {
+ if (pts[0].fY > pts[endIndex].fY) {
+ a = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
+ }
+ return;
+ }
+ if (endIndex == 3) {
+ return;
+ }
+ SkASSERT(endIndex == 2);
+ if (pts[0].fY > pts[3].fY) {
+ a = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
}
}
@@ -55,8 +84,18 @@
void quadEndPoints(const SkDQuad& pts) {
quadEndPoints(pts, 0, 1);
- if (dx() == 0 && dy() == 0) {
+ if (dy() != 0) {
+ return;
+ }
+ if (dx() == 0) {
quadEndPoints(pts, 0, 2);
+ return;
+ }
+ if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
+ return;
+ }
+ if (pts[0].fY > pts[2].fY) {
+ a = DBL_EPSILON;
}
}
diff --git a/pathops/SkOpAngle.cpp b/pathops/SkOpAngle.cpp
index 4144add..83ca55c 100644
--- a/pathops/SkOpAngle.cpp
+++ b/pathops/SkOpAngle.cpp
@@ -108,7 +108,9 @@
}
// see if either curve can be lengthened before trying the tangent
if (fSegment->other(fEnd) != rh.fSegment // tangents not absolutely identical
- && rh.fSegment->other(rh.fEnd) != fSegment) { // and not intersecting
+ && rh.fSegment->other(rh.fEnd) != fSegment
+ && y != -DBL_EPSILON
+ && ry != -DBL_EPSILON) { // and not intersecting
SkOpAngle longer = *this;
SkOpAngle rhLonger = rh;
if ((longer.lengthen(rh) | rhLonger.lengthen(*this)) // lengthen both
diff --git a/pathops/SkOpContour.cpp b/pathops/SkOpContour.cpp
index 5feef79..874de38 100644
--- a/pathops/SkOpContour.cpp
+++ b/pathops/SkOpContour.cpp
@@ -212,20 +212,17 @@
if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) {
bool added = false;
if (oMatchStart != 0) {
- added = thisOne.joinCoincidence(false, &other, oMatchStart, oStep, cancel);
+ added = thisOne.joinCoincidence(&other, oMatchStart, oStep, cancel);
}
- if (startT != 0 && !added) {
- (void) other.joinCoincidence(cancel, &thisOne, startT, step, cancel);
+ if (!cancel && startT != 0 && !added) {
+ (void) other.joinCoincidence(&thisOne, startT, step, cancel);
}
}
double oMatchEnd = cancel ? oStartT : oEndT;
if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) {
bool added = false;
- if (oMatchEnd != 1) {
- added = thisOne.joinCoincidence(true, &other, oMatchEnd, -oStep, cancel);
- }
- if (endT != 1 && !added) {
- (void) other.joinCoincidence(!cancel, &thisOne, endT, -step, cancel);
+ if (cancel && endT != 1 && !added) {
+ (void) other.joinCoincidence(&thisOne, endT, -step, cancel);
}
}
}
diff --git a/pathops/SkOpContour.h b/pathops/SkOpContour.h
index 6b412e5..8cedab4 100644
--- a/pathops/SkOpContour.h
+++ b/pathops/SkOpContour.h
@@ -72,10 +72,9 @@
return fSegments.count();
}
- int addT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT,
- bool isNear) {
+ int addT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) {
setContainsIntercepts();
- return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT, isNear);
+ return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT);
}
int addSelfT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) {
diff --git a/pathops/SkOpSegment.cpp b/pathops/SkOpSegment.cpp
index 6fe1fbb..0096340 100644
--- a/pathops/SkOpSegment.cpp
+++ b/pathops/SkOpSegment.cpp
@@ -407,7 +407,7 @@
// resolve overlapping ts when considering coincidence later
// add non-coincident intersection. Resulting edges are sorted in T.
-int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT, bool isNear) {
+int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) {
if (precisely_zero(newT)) {
newT = 0;
} else if (precisely_equal(newT, 1)) {
@@ -452,7 +452,6 @@
span->fT = newT;
span->fOther = other;
span->fPt = pt;
- span->fNear = isNear;
#if 0
// cubics, for instance, may not be exact enough to satisfy this check (e.g., cubicOp69d)
SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX)
@@ -646,7 +645,7 @@
int SkOpSegment::addSelfT(SkOpSegment* other, const SkPoint& pt, double newT) {
// if the tail nearly intersects itself but not quite, the caller records this separately
- int result = addT(other, pt, newT, SkOpSpan::kPointIsExact);
+ int result = addT(other, pt, newT);
SkOpSpan* span = &fTs[result];
span->fLoop = true;
return result;
@@ -672,31 +671,6 @@
*indexPtr = index;
}
-bool SkOpSegment::bumpCoincident(SkOpSpan* test, bool bigger, bool binary) {
- if (bigger) {
- if (binary) {
- if (fOppXor) {
- test->fOppValue ^= 1;
- } else {
- test->fOppValue++;
- }
- } else {
- if (fXor) {
- test->fWindValue ^= 1;
- } else {
- test->fWindValue++;
- }
- }
- if (!test->fWindValue && !test->fOppValue) {
- test->fDone = true;
- ++fDoneSpans;
- return true;
- }
- return false;
- }
- return decrementSpan(test);
-}
-
// because of the order in which coincidences are resolved, this and other
// may not have the same intermediate points. Compute the corresponding
// intermediate T values (using this as the master, other as the follower)
@@ -850,8 +824,8 @@
SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
__FUNCTION__, fID, t, other->fID, otherT);
#endif
- int insertedAt = addT(other, pt, t, SkOpSpan::kPointIsExact);
- int otherInsertedAt = other->addT(this, pt, otherT, SkOpSpan::kPointIsExact);
+ int insertedAt = addT(other, pt, t);
+ int otherInsertedAt = other->addT(this, pt, otherT);
addOtherT(insertedAt, otherT, otherInsertedAt);
other->addOtherT(otherInsertedAt, t, insertedAt);
matchWindingValue(insertedAt, t, borrowWind);
@@ -873,170 +847,6 @@
}
}
-SkOpSegment::MissingSpan::Command SkOpSegment::adjustThisNear(double startT, const SkPoint& startPt,
- const SkPoint& endPt, SkTArray<MissingSpan, true>* missingSpans) {
- // see if endPt exists on this curve, and if it has the same t or a different T than the startT
- int count = this->count();
- SkASSERT(count > 0);
- int startIndex, endIndex, step;
- if (startT == 0) {
- startIndex = 0;
- endIndex = count;
- step = 1;
- } else {
- SkASSERT(startT == 1);
- startIndex = count - 1;
- endIndex = -1;
- step = -1;
- }
- int index = startIndex;
- do {
- const SkOpSpan& span = fTs[index];
- if (span.fPt != endPt) {
- continue;
- }
- if (span.fT == startT) {
- // check to see if otherT matches some other mid curve intersection
- int inner = startIndex;
- do {
- if (inner == index) {
- continue;
- }
- const SkOpSpan& matchSpan = fTs[inner];
- double matchT = span.fOther->missingNear(span.fOtherT, matchSpan.fOther, startPt,
- endPt);
- if (matchT >= 0) {
- SkASSERT(missingSpans);
- MissingSpan& missingSpan = missingSpans->push_back();
- SkDEBUGCODE(sk_bzero(&missingSpan, sizeof(missingSpan)));
- missingSpan.fCommand = MissingSpan::kRemoveNear;
- missingSpan.fT = startT;
- missingSpan.fSegment = this;
- missingSpan.fOther = span.fOther;
- missingSpan.fOtherT = matchT;
- return missingSpan.fCommand;
- }
- } while ((inner += step) != endIndex);
- break;
- }
- double midT = (startT + span.fT) / 2;
- if (betweenPoints(midT, startPt, endPt)) {
- if (!missingSpans) {
- return MissingSpan::kZeroSpan;
- }
- MissingSpan& missingSpan = missingSpans->push_back();
- SkDEBUGCODE(sk_bzero(&missingSpan, sizeof(missingSpan)));
- missingSpan.fCommand = MissingSpan::kZeroSpan;
- missingSpan.fT = SkTMin(startT, span.fT);
- missingSpan.fEndT = SkTMax(startT, span.fT);
- missingSpan.fSegment = this;
- return missingSpan.fCommand;
- }
- } while ((index += step) != endIndex);
- return MissingSpan::kNoAction;
-}
-
-void SkOpSegment::adjustOtherNear(double startT, const SkPoint& startPt, const SkPoint& endPt,
- SkTArray<MissingSpan, true>* missingSpans) {
- int count = this->count();
- SkASSERT(count > 0);
- int startIndex, endIndex, step;
- if (startT == 0) {
- startIndex = 0;
- endIndex = count;
- step = 1;
- } else {
- SkASSERT(startT == 1);
- startIndex = count - 1;
- endIndex = -1;
- step = -1;
- }
- int index = startIndex;
- do {
- const SkOpSpan& span = fTs[index];
- if (span.fT != startT) {
- return;
- }
- SkOpSegment* other = span.fOther;
- if (other->fPts[0] == endPt) {
- other->adjustThisNear(0, endPt, startPt, missingSpans);
- } else if (other->fPts[0] == startPt) {
- other->adjustThisNear(0, startPt, endPt, missingSpans);
- }
- if (other->ptAtT(1) == endPt) {
- other->adjustThisNear(1, endPt, startPt, missingSpans);
- } else if (other->ptAtT(1) == startPt) {
- other->adjustThisNear(1, startPt, endPt, missingSpans);
- }
- } while ((index += step) != endIndex);
-}
-
-void SkOpSegment::adjustMissingNear(const SkPoint& startPt, const SkPoint& endPt,
- SkTArray<MissingSpan, true>* missingSpans) {
- int count = missingSpans->count();
- for (int index = 0; index < count; ) {
- MissingSpan& missing = (*missingSpans)[index];
- SkOpSegment* other = missing.fOther;
- MissingSpan::Command command = MissingSpan::kNoAction;
- if (missing.fPt == startPt) {
- if (missingNear(missing.fT, other, startPt, endPt) >= 0) {
- command = MissingSpan::kZeroSpan;
- } else if (other->ptAtT(0) == endPt) {
- command = other->adjustThisNear(0, endPt, startPt, NULL);
- } else if (other->ptAtT(1) == endPt) {
- command = other->adjustThisNear(1, endPt, startPt, NULL);
- }
- } else if (missing.fPt == endPt) {
- if (missingNear(missing.fT, other, endPt, startPt) >= 0) {
- command = MissingSpan::kZeroSpan;
- } else if (other->ptAtT(0) == startPt) {
- command = other->adjustThisNear(0, startPt, endPt, NULL);
- } else if (other->ptAtT(1) == startPt) {
- command = other->adjustThisNear(1, startPt, endPt, NULL);
- }
- }
- if (command == MissingSpan::kZeroSpan) {
-#if 1
- missing = missingSpans->back();
- missingSpans->pop_back();
-#else // if this is supported in the future ...
- missingSpans->removeShuffle(index);
-#endif
- --count;
- continue;
- }
- ++index;
- }
-}
-
-void SkOpSegment::adjustNear(double startT, const SkPoint& endPt,
- SkTArray<MissingSpan, true>* missingSpans) {
- const SkPoint startPt = ptAtT(startT);
- adjustMissingNear(startPt, endPt, missingSpans);
- adjustThisNear(startT, startPt, endPt, missingSpans);
- adjustOtherNear(startT, startPt, endPt, missingSpans);
-}
-
-int SkOpSegment::advanceCoincidentThis(int index) {
- SkOpSpan* const test = &fTs[index];
- SkOpSpan* end;
- do {
- end = &fTs[++index];
- } while (approximately_negative(end->fT - test->fT));
- return index;
-}
-
-int SkOpSegment::advanceCoincidentOther(double oEndT, int oIndex) {
- SkOpSpan* const oTest = &fTs[oIndex];
- SkOpSpan* oEnd = oTest;
- const double oStartT = oTest->fT;
- while (!approximately_negative(oEndT - oEnd->fT)
- && approximately_negative(oEnd->fT - oStartT)) {
- oEnd = &fTs[++oIndex];
- }
- return oIndex;
-}
-
bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const {
const SkPoint midPt = ptAtT(midT);
SkPathOpsBounds bounds;
@@ -1235,11 +1045,11 @@
nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
&sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
- true, nextAngle);
+ nextAngle);
} else {
nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
&maxWinding, &sumWinding);
- last = nextSegment->markAngle(maxWinding, sumWinding, true, nextAngle);
+ last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
}
nextAngle->setLastMarked(last);
}
@@ -1264,11 +1074,11 @@
nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
&sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
- true, nextAngle);
+ nextAngle);
} else {
nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
&maxWinding, &sumWinding);
- last = nextSegment->markAngle(maxWinding, sumWinding, true, nextAngle);
+ last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
}
nextAngle->setLastMarked(last);
}
@@ -1469,8 +1279,7 @@
}
if (missingSpans.count() > 0) {
const MissingSpan& lastMissing = missingSpans.back();
- if (lastMissing.fCommand == MissingSpan::kAddMissing
- && lastMissing.fT == t
+ if (lastMissing.fT == t
&& lastMissing.fOther == match
&& lastMissing.fOtherT == matchT) {
SkASSERT(lastMissing.fPt == peekSpan.fPt);
@@ -1486,7 +1295,6 @@
{
MissingSpan& missing = missingSpans.push_back();
SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
- missing.fCommand = MissingSpan::kAddMissing;
missing.fT = t;
missing.fOther = match;
missing.fOtherT = matchT;
@@ -1501,125 +1309,17 @@
debugValidate();
return;
}
- // if one end is near the other point, look for a coincident span
- for (int index = 0; index < count; ++index) {
- const SkOpSpan& span = fTs[index];
- if (span.fT > 0) {
- break;
- }
- const SkOpSpan& otherSpan = span.fOther->span(span.fOtherIndex);
- if (span.fNear) {
- SkASSERT(otherSpan.fPt == fPts[0]);
- adjustNear(0, span.fPt, &missingSpans);
- continue;
- }
- if (otherSpan.fNear) {
- SkASSERT(span.fPt == fPts[0]);
- adjustNear(0, otherSpan.fPt, &missingSpans);
- }
- }
- for (int index = count; --index >= 0; ) {
- const SkOpSpan& span = fTs[index];
- if (span.fT < 1) {
- break;
- }
- const SkOpSegment* other = span.fOther;
- if (span.fNear) {
- SkASSERT(other->ptAtT(span.fOtherT) == ptAtT(1));
- const SkPoint& otherPt = other->xyAtT(span.fOtherIndex);
- SkASSERT(otherPt != ptAtT(1));
- adjustNear(1, otherPt, &missingSpans);
- continue;
- }
- const SkOpSpan& otherSpan = other->span(span.fOtherIndex);
- if (otherSpan.fNear) {
- SkASSERT(otherSpan.fPt == ptAtT(1));
- SkPoint otherPt = other->ptAtT(span.fOtherT);
- SkASSERT(otherPt != ptAtT(1));
- adjustNear(1, otherPt, &missingSpans);
- }
- }
debugValidate();
int missingCount = missingSpans.count();
for (int index = 0; index < missingCount; ++index) {
MissingSpan& missing = missingSpans[index];
- switch (missing.fCommand) {
- case MissingSpan::kNoAction:
- break;
- case MissingSpan::kAddMissing:
- addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
- break;
- case MissingSpan::kRemoveNear: {
- SkOpSegment* segment = missing.fSegment;
- int count = segment->count();
- for (int inner = 0; inner < count; ++inner) {
- const SkOpSpan& span = segment->span(inner);
- if (span.fT != missing.fT && span.fOther != missing.fOther) {
- continue;
- }
- SkASSERT(span.fNear);
- SkOpSegment* other = span.fOther;
- int otherCount = other->count();
- for (int otherIndex = 0; otherIndex < otherCount; ++otherIndex) {
- const SkOpSpan& otherSpan = other->span(otherIndex);
- if (otherSpan.fT == span.fOtherT && otherSpan.fOther == segment
- && otherSpan.fOtherT == span.fT) {
- if (otherSpan.fDone) {
- other->fDoneSpans--;
- }
- other->fTs.remove(otherIndex);
- // FIXME: remove may leave a tiny dangling -- recompute tiny w/index
- break;
- }
- }
- if (span.fDone) {
- segment->fDoneSpans--;
- }
- segment->fTs.remove(inner);
- // FIXME: remove may leave a tiny dangling -- recompute tiny w/index
- break;
- }
- break;
- }
- case MissingSpan::kZeroSpan: {
- SkOpSegment* segment = missing.fSegment;
- int count = segment->count();
- for (int inner = 0; inner < count; ++inner) {
- SkOpSpan& span = segment->fTs[inner];
- if (span.fT < missing.fT) {
- continue;
- }
- if (span.fT >= missing.fEndT) {
- break;
- }
- span.fWindValue = span.fOppValue = 0;
- if (!span.fDone) {
- span.fDone = true;
- ++segment->fDoneSpans;
- }
- }
- break;
- }
- }
+ addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
}
fixOtherTIndex();
// OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to
// avoid this
for (int index = 0; index < missingCount; ++index) {
- const MissingSpan& missing = missingSpans[index];
- switch (missing.fCommand) {
- case MissingSpan::kNoAction:
- break;
- case MissingSpan::kAddMissing:
- missing.fOther->fixOtherTIndex();
- break;
- case MissingSpan::kRemoveNear:
- missing.fSegment->fixOtherTIndex();
- missing.fOther->fixOtherTIndex();
- break;
- case MissingSpan::kZeroSpan:
- break;
- }
+ missingSpans[index].fOther->fixOtherTIndex();
}
debugValidate();
}
@@ -1687,7 +1387,6 @@
// remember so we can add the missing one and recompute the indices
MissingSpan& missing = missingSpans.push_back();
SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
- missing.fCommand = MissingSpan::kAddMissing;
missing.fSegment = thisOther;
missing.fT = thisSpan->fOtherT;
missing.fOther = nextOther;
@@ -2406,7 +2105,7 @@
// if both are active, look to see if they both the connect to another coincident pair
// if one at least one is a line, then make the pair coincident
// if neither is a line, test for coincidence
-bool SkOpSegment::joinCoincidence(bool end, SkOpSegment* other, double otherT, int step,
+bool SkOpSegment::joinCoincidence(SkOpSegment* other, double otherT, int step,
bool cancel) {
int otherTIndex = other->findT(otherT, this);
int next = other->nextExactSpan(otherTIndex, step);
@@ -2416,78 +2115,31 @@
return false;
}
SkASSERT(next >= 0);
- if (end) {
- int tIndex = count() - 1;
- do {
- SkOpSpan* test = &fTs[tIndex];
- SkASSERT(test->fT == 1);
- if (test->fOther == other || test->fOtherT != 0) {
- continue;
+ int tIndex = 0;
+ do {
+ SkOpSpan* test = &fTs[tIndex];
+ SkASSERT(test->fT == 0);
+ if (test->fOther == other || test->fOtherT != 1) {
+ continue;
+ }
+ SkPoint startPt, endPt;
+ double endT;
+ if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
+ SkOpSegment* match = test->fOther;
+ if (cancel) {
+ match->addTCancel(startPt, endPt, other);
+ } else {
+ match->addTCoincident(startPt, endPt, endT, other);
}
- SkPoint startPt, endPt;
- double endT;
- if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
- SkOpSegment* match = test->fOther;
- if (cancel) {
- match->addTCancel(startPt, endPt, other);
- } else {
- match->addTCoincident(startPt, endPt, endT, other);
- }
- return true;
- }
- } while (fTs[--tIndex].fT == 1);
- } else {
- int tIndex = 0;
- do {
- SkOpSpan* test = &fTs[tIndex];
- SkASSERT(test->fT == 0);
- if (test->fOther == other || test->fOtherT != 1) {
- continue;
- }
- SkPoint startPt, endPt;
- double endT;
- if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
- SkOpSegment* match = test->fOther;
- if (cancel) {
- match->addTCancel(startPt, endPt, other);
- } else {
- match->addTCoincident(startPt, endPt, endT, other);
- }
- return true;
- }
- } while (fTs[++tIndex].fT == 0);
- }
+ return true;
+ }
+ } while (fTs[++tIndex].fT == 0);
return false;
}
// this span is excluded by the winding rule -- chase the ends
// as long as they are unambiguous to mark connections as done
// and give them the same winding value
-SkOpSpan* SkOpSegment::markAndChaseDone(int index, int endIndex, int winding) {
- int step = SkSign32(endIndex - index);
- int min = SkMin32(index, endIndex);
- markDone(min, winding);
- SkOpSpan* last;
- SkOpSegment* other = this;
- while ((other = other->nextChase(&index, step, &min, &last))) {
- other->markDone(min, winding);
- }
- return last;
-}
-
-SkOpSpan* SkOpSegment::markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding) {
- int index = angle->start();
- int endIndex = angle->end();
- int step = SkSign32(endIndex - index);
- int min = SkMin32(index, endIndex);
- markDoneBinary(min, winding, oppWinding);
- SkOpSpan* last;
- SkOpSegment* other = this;
- while ((other = other->nextChase(&index, step, &min, &last))) {
- other->markDoneBinary(min, winding, oppWinding);
- }
- return last;
-}
SkOpSpan* SkOpSegment::markAndChaseDoneBinary(int index, int endIndex) {
int step = SkSign32(endIndex - index);
@@ -2519,12 +2171,6 @@
return last;
}
-SkOpSpan* SkOpSegment::markAndChaseDoneUnary(const SkOpAngle* angle, int winding) {
- int index = angle->start();
- int endIndex = angle->end();
- return markAndChaseDone(index, endIndex, winding);
-}
-
SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, const int winding) {
int index = angle->start();
int endIndex = angle->end();
@@ -2565,18 +2211,12 @@
return markAndChaseWinding(start, end, winding, oppWinding);
}
-SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, bool activeAngle,
- const SkOpAngle* angle) {
+SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) {
SkASSERT(angle->segment() == this);
if (UseInnerWinding(maxWinding, sumWinding)) {
maxWinding = sumWinding;
}
- SkOpSpan* last;
- if (activeAngle) {
- last = markAndChaseWinding(angle, maxWinding);
- } else {
- last = markAndChaseDoneUnary(angle, maxWinding);
- }
+ SkOpSpan* last = markAndChaseWinding(angle, maxWinding);
#if DEBUG_WINDING
if (last) {
SkDebugf("%s last id=%d windSum=", __FUNCTION__,
@@ -2589,7 +2229,7 @@
}
SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
- int oppSumWinding, bool activeAngle, const SkOpAngle* angle) {
+ int oppSumWinding, const SkOpAngle* angle) {
SkASSERT(angle->segment() == this);
if (UseInnerWinding(maxWinding, sumWinding)) {
maxWinding = sumWinding;
@@ -2597,12 +2237,7 @@
if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
oppMaxWinding = oppSumWinding;
}
- SkOpSpan* last;
- if (activeAngle) {
- last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
- } else {
- last = markAndChaseDoneBinary(angle, maxWinding, oppMaxWinding);
- }
+ SkOpSpan* last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
#if DEBUG_WINDING
if (last) {
SkDebugf("%s last id=%d windSum=", __FUNCTION__,
@@ -2632,19 +2267,6 @@
} while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
}
-void SkOpSegment::markDoneBinary(int index, int winding, int oppWinding) {
- // SkASSERT(!done());
- SkASSERT(winding || oppWinding);
- double referenceT = fTs[index].fT;
- int lesser = index;
- while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
- markOneDoneBinary(__FUNCTION__, lesser, winding, oppWinding);
- }
- do {
- markOneDoneBinary(__FUNCTION__, index, winding, oppWinding);
- } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
-}
-
void SkOpSegment::markDoneBinary(int index) {
double referenceT = fTs[index].fT;
int lesser = index;
@@ -2685,15 +2307,6 @@
fDoneSpans++;
}
-void SkOpSegment::markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding) {
- SkOpSpan* span = markOneWinding(funName, tIndex, winding, oppWinding);
- if (!span) {
- return;
- }
- span->fDone = true;
- fDoneSpans++;
-}
-
void SkOpSegment::markOneDoneUnary(const char* funName, int tIndex) {
SkOpSpan* span = verifyOneWindingU(funName, tIndex);
if (!span) {
@@ -2790,8 +2403,12 @@
#if DEBUG_MARK_DONE
debugShowNewWinding(funName, span, span.fWindSum, span.fOppSum);
#endif
- SkASSERT(span.fWindSum != SK_MinS32);
- SkASSERT(span.fOppSum != SK_MinS32);
+// If the prior angle in the sort is unorderable, the winding sum may not be computable.
+// To enable the assert, the 'prior is unorderable' state could be
+// piped down to this test, but not sure it's worth it.
+// (Once the sort order is stored in the span, this test may be feasible.)
+// SkASSERT(span.fWindSum != SK_MinS32);
+// SkASSERT(span.fOppSum != SK_MinS32);
return &span;
}
@@ -2803,7 +2420,11 @@
#if DEBUG_MARK_DONE
debugShowNewWinding(funName, span, span.fWindSum);
#endif
- SkASSERT(span.fWindSum != SK_MinS32);
+// If the prior angle in the sort is unorderable, the winding sum may not be computable.
+// To enable the assert, the 'prior is unorderable' state could be
+// piped down to this test, but not sure it's worth it.
+// (Once the sort order is stored in the span, this test may be feasible.)
+// SkASSERT(span.fWindSum != SK_MinS32);
return &span;
}
@@ -2891,21 +2512,6 @@
}
}
-double SkOpSegment::missingNear(double t, const SkOpSegment* other, const SkPoint& startPt,
- const SkPoint& endPt) const {
- int count = this->count();
- for (int index = 0; index < count; ++index) {
- const SkOpSpan& span = this->span(index);
- if (span.fOther == other && span.fPt == startPt) {
- double midT = (t + span.fT) / 2;
- if (betweenPoints(midT, startPt, endPt)) {
- return span.fT;
- }
- }
- }
- return -1;
-}
-
// return span if when chasing, two or more radiating spans are not done
// OPTIMIZATION: ? multiple spans is detected when there is only one valid
// candidate and the remaining spans have windValue == 0 (canceled by
@@ -3330,24 +2936,6 @@
return windSum(index);
}
-int SkOpSegment::windValue(const SkOpAngle* angle) const {
- int start = angle->start();
- int end = angle->end();
- int index = SkMin32(start, end);
- return windValue(index);
-}
-
-int SkOpSegment::windValueAt(double t) const {
- int count = fTs.count();
- for (int index = 0; index < count; ++index) {
- if (fTs[index].fT == t) {
- return fTs[index].fWindValue;
- }
- }
- SkASSERT(0);
- return 0;
-}
-
void SkOpSegment::zeroSpan(SkOpSpan* span) {
SkASSERT(span->fWindValue > 0 || span->fOppValue != 0);
span->fWindValue = 0;
diff --git a/pathops/SkOpSegment.h b/pathops/SkOpSegment.h
index d56ce8e..55e516e 100644
--- a/pathops/SkOpSegment.h
+++ b/pathops/SkOpSegment.h
@@ -246,7 +246,7 @@
void addOtherT(int index, double otherT, int otherIndex);
void addQuad(const SkPoint pts[3], bool operand, bool evenOdd);
int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT);
- int addT(SkOpSegment* other, const SkPoint& pt, double newT, bool isNear);
+ int addT(SkOpSegment* other, const SkPoint& pt, double newT);
void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
SkOpSegment* other);
@@ -275,12 +275,12 @@
SkScalar hitOppDx);
bool isMissing(double startT, const SkPoint& pt) const;
bool isTiny(const SkOpAngle* angle) const;
- bool joinCoincidence(bool end, SkOpSegment* other, double otherT, int step, bool cancel);
+ bool joinCoincidence(SkOpSegment* other, double otherT, int step, bool cancel);
SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);
SkOpSpan* markAndChaseDoneUnary(int index, int endIndex);
SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding);
SkOpSpan* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
- bool activeAngle, const SkOpAngle* angle);
+ const SkOpAngle* angle);
void markDone(int index, int winding);
void markDoneBinary(int index);
void markDoneUnary(int index);
@@ -329,12 +329,6 @@
private:
struct MissingSpan {
- enum Command {
- kNoAction,
- kAddMissing,
- kRemoveNear,
- kZeroSpan,
- } fCommand;
double fT;
double fEndT;
SkOpSegment* fSegment;
@@ -355,21 +349,11 @@
void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt,
const SkPoint& oPt);
void addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const;
- void adjustMissingNear(const SkPoint& startPt, const SkPoint& endPt,
- SkTArray<MissingSpan, true>* );
- void adjustNear(double startT, const SkPoint& endPt, SkTArray<MissingSpan, true>* );
- void adjustOtherNear(double startT, const SkPoint& startPt, const SkPoint& endPt,
- SkTArray<MissingSpan, true>* );
- MissingSpan::Command adjustThisNear(double startT, const SkPoint& startPt, const SkPoint& endPt,
- SkTArray<MissingSpan, true>* );
- int advanceCoincidentOther(double oEndT, int oIndex);
- int advanceCoincidentThis(int index);
bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const;
bool buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const;
void buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const;
void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index,
SkTArray<SkPoint, true>* outsideTs);
- bool bumpCoincident(SkOpSpan* test, bool bigger, bool binary);
void bumpCoincidentOther(const SkOpSpan& oTest, int* index,
SkTArray<SkPoint, true>* outsideTs);
bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta);
@@ -388,7 +372,7 @@
SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding);
SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, const int winding);
SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding);
- SkOpSpan* markAngle(int maxWinding, int sumWinding, bool activeAngle, const SkOpAngle* angle);
+ SkOpSpan* markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle);
void markDoneBinary(int index, int winding, int oppWinding);
SkOpSpan* markAndChaseDoneUnary(const SkOpAngle* angle, int winding);
void markOneDone(const char* funName, int tIndex, int winding);
@@ -401,8 +385,6 @@
void markWinding(int index, int winding, int oppWinding);
void markUnsortable(int start, int end);
bool monotonicInY(int tStart, int tEnd) const;
- double missingNear(double otherT, const SkOpSegment* other, const SkPoint& startPt,
- const SkPoint& endPt) const;
bool multipleSpans(int end) const;
SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last);
int nextExactSpan(int from, int step) const;
@@ -421,8 +403,6 @@
static bool UseInnerWindingReverse(int outerWinding, int innerWinding);
SkOpSpan* verifyOneWinding(const char* funName, int tIndex);
SkOpSpan* verifyOneWindingU(const char* funName, int tIndex);
- int windValue(const SkOpAngle* angle) const;
- int windValueAt(double t) const;
void zeroSpan(SkOpSpan* span);
#if DEBUG_SWAP_TOP
diff --git a/pathops/SkOpSpan.h b/pathops/SkOpSpan.h
index 50c76d2..81ede1c 100644
--- a/pathops/SkOpSpan.h
+++ b/pathops/SkOpSpan.h
@@ -12,10 +12,6 @@
class SkOpSegment;
struct SkOpSpan {
- enum PointMatch {
- kPointIsExact,
- kPointIsNear
- };
SkOpSegment* fOther;
SkPoint fPt; // computed when the curves are intersected
double fT;
@@ -31,7 +27,6 @@
bool fSmall; // if set, consecutive points are almost equal
bool fTiny; // if set, span may still be considered once for edge following
bool fLoop; // set when a cubic loops back to this point
- bool fNear; // set if point is near segment end point
#ifdef SK_DEBUG
void dump() const;
diff --git a/pathops/SkPathOpsDebug.cpp b/pathops/SkPathOpsDebug.cpp
index 95e2204..b68ab2a 100644
--- a/pathops/SkPathOpsDebug.cpp
+++ b/pathops/SkPathOpsDebug.cpp
@@ -134,9 +134,6 @@
if (fLoop) {
SkDebugf(" loop");
}
- if (fNear) {
- SkDebugf(" near");
- }
SkDebugf("\n");
}
diff --git a/pathops/SkPathOpsOp.cpp b/pathops/SkPathOpsOp.cpp
index 9d6cd51..1b7b03b 100644
--- a/pathops/SkPathOpsOp.cpp
+++ b/pathops/SkPathOpsOp.cpp
@@ -92,7 +92,7 @@
nextEnd = end;
}
(void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
- oppSumWinding, true, angle);
+ oppSumWinding, angle);
}
} while (++nextIndex != lastIndex);
if (first) {
