Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(289)

Unified Diff: src/pathops/SkOpSegment.cpp

Issue 2128633003: pathops coincidence and security rewrite (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: require resulting t to be between 0 and 1 Created 4 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: src/pathops/SkOpSegment.cpp
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 41d62369b644dfe12363173375bba0ab47ae0d9c..e4e00bbfab6fb46585aef89bb3845b24baa512b2 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -9,6 +9,8 @@
#include "SkOpSegment.h"
#include "SkPathWriter.h"
+#define FAIL_IF(cond) do { if (cond) return false; } while (false)
+
/*
After computing raw intersections, post process all segments to:
- find small collections of points that can be collapsed to a single point
@@ -159,90 +161,10 @@ bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sum
return result;
}
-void SkOpSegment::addAlignIntersection(SkOpPtT& endPtT, SkPoint& oldPt,
- SkOpContourHead* contourList, SkChunkAlloc* allocator) {
- const SkPoint& newPt = endPtT.fPt;
- if (newPt == oldPt) {
- return;
- }
- SkPoint line[2] = { newPt, oldPt };
- SkPathOpsBounds lineBounds;
- lineBounds.setBounds(line, 2);
- SkDLine aLine;
- aLine.set(line);
- SkOpContour* current = contourList;
- do {
- if (!SkPathOpsBounds::Intersects(current->bounds(), lineBounds)) {
- continue;
- }
- SkOpSegment* segment = current->first();
- do {
- if (!SkPathOpsBounds::Intersects(segment->bounds(), lineBounds)) {
- continue;
- }
- if (newPt == segment->fPts[0]) {
- continue;
- }
- if (newPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
- continue;
- }
- if (oldPt == segment->fPts[0]) {
- continue;
- }
- if (oldPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
- continue;
- }
- if (endPtT.contains(segment)) {
- continue;
- }
- SkIntersections i;
- switch (segment->fVerb) {
- case SkPath::kLine_Verb: {
- SkDLine bLine;
- bLine.set(segment->fPts);
- i.intersect(bLine, aLine);
- } break;
- case SkPath::kQuad_Verb: {
- SkDQuad bQuad;
- bQuad.set(segment->fPts);
- i.intersect(bQuad, aLine);
- } break;
- case SkPath::kConic_Verb: {
- SkDConic bConic;
- bConic.set(segment->fPts, segment->fWeight);
- i.intersect(bConic, aLine);
- } break;
- case SkPath::kCubic_Verb: {
- SkDCubic bCubic;
- bCubic.set(segment->fPts);
- i.intersect(bCubic, aLine);
- } break;
- default:
- SkASSERT(0);
- }
- if (i.used()) {
- SkASSERT(i.used() == 1);
- SkASSERT(!zero_or_one(i[0][0]));
- SkOpSpanBase* checkSpan = fHead.next();
- while (!checkSpan->final()) {
- if (checkSpan->contains(segment)) {
- goto nextSegment;
- }
- checkSpan = checkSpan->upCast()->next();
- }
- SkOpPtT* ptT = segment->addT(i[0][0], SkOpSegment::kAllowAlias, allocator);
- ptT->fPt = newPt;
- endPtT.addOpp(ptT);
- }
- nextSegment:
- ;
- } while ((segment = segment->next()));
- } while ((current = current->next()));
-}
-
bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
SkPathWriter* path) const {
if (start->starter(end)->alreadyAdded()) {
+ SkDEBUGF(("same curve added twice aborted pathops\n"));
return false;
}
SkOpCurve edge;
@@ -298,29 +220,57 @@ bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
return true;
}
-SkOpPtT* SkOpSegment::addMissing(double t, SkOpSegment* opp, SkChunkAlloc* allocator) {
- SkOpSpanBase* existing = nullptr;
- SkOpSpanBase* test = &fHead;
- double testT;
+const SkOpPtT* SkOpSegment::existing(double t, const SkOpSegment* opp) const {
+ const SkOpSpanBase* test = &fHead;
+ const SkOpPtT* testPtT;
+ SkPoint pt = this->ptAtT(t);
do {
- if ((testT = test->ptT()->fT) >= t) {
- if (testT == t) {
- existing = test;
- }
+ testPtT = test->ptT();
+ if (testPtT->fT == t) {
break;
}
+ if (!this->match(testPtT, this, t, pt, opp ? kAllowAliasMatch : kNoAliasMatch)) {
+ if (t < testPtT->fT) {
+ return nullptr;
+ }
+ continue;
+ }
+ if (!opp) {
+ return testPtT;
+ }
+ const SkOpPtT* loop = testPtT->next();
+ while (loop != testPtT) {
+ if (loop->segment() == this && loop->fT == t && loop->fPt == pt) {
+ goto foundMatch;
+ }
+ loop = loop->next();
+ }
+ return nullptr;
} while ((test = test->upCast()->next()));
- SkOpPtT* result;
- if (existing && existing->contains(opp)) {
- result = existing->ptT();
- } else {
- result = this->addT(t, SkOpSegment::kNoAlias, allocator);
+foundMatch:
+ return opp && !test->contains(opp) ? nullptr : testPtT;
+}
+
+// break the span so that the coincident part does not change the angle of the remainder
+bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* startOver) {
+ if (this->contains(newT)) {
+ return true;
}
- SkASSERT(result);
- return result;
+ SkOpPtT* newPtT = this->addT(newT, kAllowAliasMatch, startOver);
+ if (!newPtT) {
+ return false;
+ }
+ newPtT->fPt = this->ptAtT(newT);
+ // const cast away to change linked list; pt/t values stays unchanged
+ SkOpSpanBase* writableTest = const_cast<SkOpSpanBase*>(test);
+ if (writableTest->ptT()->addOpp(newPtT)) {
+ writableTest->checkForCollapsedCoincidence();
+ }
+ return true;
}
-SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* allocator) {
+// Please keep this in sync with debugAddT()
+SkOpPtT* SkOpSegment::addT(double t, AliasMatch allowAlias, bool* allocated) {
debugValidate();
SkPoint pt = this->ptAtT(t);
SkOpSpanBase* span = &fHead;
@@ -331,9 +281,9 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
if (t == result->fT) {
goto bumpSpan;
}
- if (this->match(result, this, t, pt)) {
+ if (this->match(result, this, t, pt, allowAlias)) {
// see if any existing alias matches segment, pt, and t
- loop = result->next();
+ loop = result->next();
duplicatePt = false;
while (loop != result) {
bool ptMatch = loop->fPt == pt;
@@ -343,12 +293,12 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
duplicatePt |= ptMatch;
loop = loop->next();
}
- if (kNoAlias == allowAlias) {
+ if (kNoAliasMatch == allowAlias) {
bumpSpan:
span->bumpSpanAdds();
return result;
}
- SkOpPtT* alias = SkOpTAllocator<SkOpPtT>::Allocate(allocator);
+ SkOpPtT* alias = SkOpTAllocator<SkOpPtT>::Allocate(this->globalState()->allocator());
alias->init(result->span(), t, pt, duplicatePt);
result->insert(alias);
result->span()->unaligned();
@@ -358,6 +308,9 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
alias->segment()->debugID(), alias->span()->debugID());
#endif
span->bumpSpanAdds();
+ if (allocated) {
+ *allocated = true;
+ }
return alias;
}
if (t < result->fT) {
@@ -365,7 +318,7 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
if (!prev) {
return nullptr;
}
- SkOpSpan* span = insert(prev, allocator);
+ SkOpSpan* span = insert(prev);
span->init(this, prev, t, pt);
this->debugValidate();
#if DEBUG_ADD_T
@@ -373,6 +326,9 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
span->segment()->debugID(), span->debugID());
#endif
span->bumpSpanAdds();
+ if (allocated) {
+ *allocated = true;
+ }
return span->ptT();
}
SkASSERT(span != &fTail);
@@ -381,43 +337,17 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
return nullptr;
}
-// choose a solitary t and pt value; remove aliases; align the opposite ends
-void SkOpSegment::align() {
- debugValidate();
- SkOpSpanBase* span = &fHead;
- if (!span->aligned()) {
- span->alignEnd(0, fPts[0]);
- }
- while ((span = span->upCast()->next())) {
- if (span == &fTail) {
- break;
- }
- span->align();
- }
- if (!span->aligned()) {
- span->alignEnd(1, fPts[SkPathOpsVerbToPoints(fVerb)]);
- }
- if (this->collapsed()) {
- SkOpSpan* span = &fHead;
- do {
- span->setWindValue(0);
- span->setOppValue(0);
- this->markDone(span);
- } while ((span = span->next()->upCastable()));
- }
- debugValidate();
-}
-
-void SkOpSegment::calcAngles(SkChunkAlloc* allocator) {
+void SkOpSegment::calcAngles() {
bool activePrior = !fHead.isCanceled();
if (activePrior && !fHead.simple()) {
- addStartSpan(allocator);
+ addStartSpan();
}
SkOpSpan* prior = &fHead;
SkOpSpanBase* spanBase = fHead.next();
while (spanBase != &fTail) {
if (activePrior) {
- SkOpAngle* priorAngle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
+ SkOpAngle* priorAngle = SkOpTAllocator<SkOpAngle>::Allocate(
+ this->globalState()->allocator());
priorAngle->set(spanBase, prior);
spanBase->setFromAngle(priorAngle);
}
@@ -425,7 +355,8 @@ void SkOpSegment::calcAngles(SkChunkAlloc* allocator) {
bool active = !span->isCanceled();
SkOpSpanBase* next = span->next();
if (active) {
- SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
+ SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(
+ this->globalState()->allocator());
angle->set(span, next);
span->setToAngle(angle);
}
@@ -434,12 +365,32 @@ void SkOpSegment::calcAngles(SkChunkAlloc* allocator) {
spanBase = next;
}
if (activePrior && !fTail.simple()) {
- addEndSpan(allocator);
+ addEndSpan();
}
}
+// Please keep this in sync with debugClearAll()
+void SkOpSegment::clearAll() {
+ SkOpSpan* span = &fHead;
+ do {
+ this->clearOne(span);
+ } while ((span = span->next()->upCastable()));
+ this->globalState()->coincidence()->release(this);
+}
+
+// Please keep this in sync with debugClearOne()
+void SkOpSegment::clearOne(SkOpSpan* span) {
+ span->setWindValue(0);
+ span->setOppValue(0);
+ this->markDone(span);
+}
+
+// Quads and conics collapse if the end points are the same, because
+// the curve doesn't enclose an area.
bool SkOpSegment::collapsed() const {
- return fVerb == SkPath::kLine_Verb && fHead.pt() == fTail.pt();
+ // FIXME: cubics can have also collapsed -- need to check if the
+ // control points are on a line with the end points
+ return fVerb < SkPath::kCubic_Verb && fHead.pt() == fTail.pt();
}
void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
@@ -571,12 +522,26 @@ int SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end,
return start->starter(end)->windSum();
}
+bool SkOpSegment::contains(double newT) const {
+ const SkOpSpanBase* spanBase = &fHead;
+ do {
+ if (spanBase->ptT()->contains(this, newT)) {
+ return true;
+ }
+ if (spanBase == &fTail) {
+ break;
+ }
+ spanBase = spanBase->upCast()->next();
+ } while (true);
+ return false;
+}
+
void SkOpSegment::release(const SkOpSpan* span) {
if (span->done()) {
--fDoneCount;
}
--fCount;
- SkASSERT(fCount >= fDoneCount);
+ SkASSERT(this->globalState()->debugSkipAssert() || fCount >= fDoneCount);
}
double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const {
@@ -601,15 +566,6 @@ double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const {
return closestDistSq;
}
-void SkOpSegment::findCollapsed() {
- if (fHead.contains(&fTail)) {
- markAllDone();
- // move start and end to the same point
- fHead.alignEnd(0, fHead.pt());
- fTail.setAligned();
- }
-}
-
/*
The M and S variable name parts stand for the operators.
Mi stands for Minuend (see wiki subtraction, analogous to difference)
@@ -887,14 +843,12 @@ SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** n
}
SkOpGlobalState* SkOpSegment::globalState() const {
- return contour()->globalState();
+ return contour()->globalState();
}
void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) {
fContour = contour;
fNext = nullptr;
- fOriginal[0] = pts[0];
- fOriginal[1] = pts[SkPathOpsVerbToPoints(verb)];
fPts = pts;
fWeight = weight;
fVerb = verb;
@@ -1095,15 +1049,17 @@ bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) {
}
bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT,
- const SkPoint& testPt) const {
- const SkOpSegment* baseParent = base->segment();
- if (this == baseParent && this == testParent && precisely_equal(base->fT, testT)) {
- return true;
+ const SkPoint& testPt, AliasMatch aliasMatch) const {
+ SkASSERT(this == base->segment());
+ if (this == testParent) {
+ if (precisely_equal(base->fT, testT)) {
+ return true;
+ }
}
if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) {
return false;
}
- return !this->ptsDisjoint(base->fT, base->fPt, testT, testPt);
+ return this != testParent || !this->ptsDisjoint(base->fT, base->fPt, testT, testPt);
}
static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) {
@@ -1178,7 +1134,8 @@ SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpS
return other;
}
-static void clear_visited(SkOpSpanBase* span) {
+// Please keep this in sync with DebugClearVisited()
+void SkOpSegment::ClearVisited(SkOpSpanBase* span) {
// reset visited flag back to false
do {
SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
@@ -1189,20 +1146,23 @@ static void clear_visited(SkOpSpanBase* span) {
} while (!span->final() && (span = span->upCast()->next()));
}
+// Please keep this in sync with debugMissingCoincidence()
// look for pairs of undetected coincident curves
// assumes that segments going in have visited flag clear
-// curve/curve intersection should now do a pretty good job of finding coincident runs so
-// this may be only be necessary for line/curve pairs -- so skip unless this is a line and the
-// the opp is not a line
-bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) {
- if (this->verb() != SkPath::kLine_Verb) {
- return false;
- }
+// Even though pairs of curves correct detect coincident runs, a run may be missed
+// if the coincidence is a product of multiple intersections. For instance, given
+// curves A, B, and C:
+// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near
+// the end of C that the intersection is replaced with the end of C.
+// Even though A-B correctly do not detect an intersection at point 2,
+// the resulting run from point 1 to point 2 is coincident on A and B.
+bool SkOpSegment::missingCoincidence() {
if (this->done()) {
return false;
}
SkOpSpan* prior = nullptr;
SkOpSpanBase* spanBase = &fHead;
+ bool result = false;
do {
SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
SkASSERT(ptT->span() == spanBase);
@@ -1211,9 +1171,6 @@ bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc
continue;
}
SkOpSegment* opp = ptT->span()->segment();
-// if (opp->verb() == SkPath::kLine_Verb) {
-// continue;
-// }
if (opp->done()) {
continue;
}
@@ -1224,18 +1181,18 @@ bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc
if (spanBase == &fHead) {
continue;
}
+ if (ptT->segment() == this) {
+ continue;
+ }
SkOpSpan* span = spanBase->upCastable();
// FIXME?: this assumes that if the opposite segment is coincident then no more
// coincidence needs to be detected. This may not be true.
- if (span && span->containsCoincidence(opp)) {
- continue;
- }
- if (spanBase->segment() == opp) {
+ if (span && span->containsCoincidence(opp)) {
continue;
}
if (spanBase->containsCoinEnd(opp)) {
continue;
- }
+ }
SkOpPtT* priorPtT = nullptr, * priorStopPtT;
// find prior span containing opp segment
SkOpSegment* priorOpp = nullptr;
@@ -1268,28 +1225,28 @@ bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc
SkTSwap(priorPtT, ptT);
SkTSwap(oppStart, oppEnd);
}
- bool flipped = oppStart->fT > oppEnd->fT;
- bool coincident = false;
- if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) {
+ SkOpCoincidence* coincidences = this->globalState()->coincidence();
+ SkOpPtT* rootPriorPtT = priorPtT->span()->ptT();
+ SkOpPtT* rootPtT = ptT->span()->ptT();
+ SkOpPtT* rootOppStart = oppStart->span()->ptT();
+ SkOpPtT* rootOppEnd = oppEnd->span()->ptT();
+ if (coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
goto swapBack;
}
- if (opp->verb() == SkPath::kLine_Verb) {
- coincident = (SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppStart->fPt) ||
- SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppEnd->fPt)) &&
- (SkDPoint::ApproximatelyEqual(ptT->fPt, oppStart->fPt) ||
- SkDPoint::ApproximatelyEqual(ptT->fPt, oppEnd->fPt));
- }
- if (!coincident) {
- coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000);
- }
- if (coincident) {
+ if (this->testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) {
// mark coincidence
- if (!coincidences->extend(priorPtT, ptT, oppStart, oppEnd)
- && !coincidences->extend(oppStart, oppEnd, priorPtT, ptT)) {
- coincidences->add(priorPtT, ptT, oppStart, oppEnd, allocator);
+#if DEBUG_COINCIDENCE_VERBOSE
+ SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__,
+ rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(),
+ rootOppEnd->debugID());
+#endif
+ if (!coincidences->extend(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
+ coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
}
- clear_visited(&fHead);
- return true;
+#if DEBUG_COINCIDENCE
+ SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd));
+#endif
+ result = true;
}
swapBack:
if (swapped) {
@@ -1297,19 +1254,18 @@ bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc
}
}
} while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
- clear_visited(&fHead);
- return false;
+ ClearVisited(&fHead);
+ return result;
}
+// please keep this in sync with debugMoveMultiples()
// if a span has more than one intersection, merge the other segments' span as needed
bool SkOpSegment::moveMultiples() {
debugValidate();
SkOpSpanBase* test = &fHead;
do {
int addCount = test->spanAddsCount();
- if (addCount < 1) {
- return false;
- }
+ FAIL_IF(addCount < 1);
if (addCount == 1) {
continue;
}
@@ -1392,66 +1348,126 @@ bool SkOpSegment::moveMultiples() {
oppSegment->debugValidate();
goto checkNextSpan;
}
- tryNextSpan:
+ tryNextSpan:
;
} while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
} while ((testPtT = testPtT->next()) != startPtT);
-checkNextSpan:
+checkNextSpan:
;
} while ((test = test->final() ? nullptr : test->upCast()->next()));
debugValidate();
return true;
}
+// adjacent spans may have points close by
+bool SkOpSegment::spansNearby(const SkOpSpanBase* refSpan, const SkOpSpanBase* checkSpan) const {
+ const SkOpPtT* refHead = refSpan->ptT();
+ const SkOpPtT* checkHead = checkSpan->ptT();
+// if the first pt pair from adjacent spans are far apart, assume that all are far enough apart
+ if (!SkDPoint::RoughlyEqual(refHead->fPt, checkHead->fPt)) {
+#if DEBUG_COINCIDENCE
+ // verify that no combination of points are close
+ const SkOpPtT* dBugRef = refHead;
+ do {
+ const SkOpPtT* dBugCheck = checkHead;
+ do {
+ SkASSERT(!SkDPoint::ApproximatelyEqual(dBugRef->fPt, dBugCheck->fPt));
+ dBugCheck = dBugCheck->next();
+ } while (dBugCheck != checkHead);
+ dBugRef = dBugRef->next();
+ } while (dBugRef != refHead);
+#endif
+ return false;
+ }
+ // check only unique points
+ SkScalar distSqBest = SK_ScalarMax;
+ const SkOpPtT* refBest = nullptr;
+ const SkOpPtT* checkBest = nullptr;
+ const SkOpPtT* ref = refHead;
+ do {
+ if (ref->deleted()) {
+ continue;
+ }
+ while (ref->ptAlreadySeen(refHead)) {
+ ref = ref->next();
+ if (ref == refHead) {
+ goto doneCheckingDistance;
+ }
+ }
+ const SkOpPtT* check = checkHead;
+ const SkOpSegment* refSeg = ref->segment();
+ do {
+ if (check->deleted()) {
+ continue;
+ }
+ while (check->ptAlreadySeen(checkHead)) {
+ check = check->next();
+ if (check == checkHead) {
+ goto nextRef;
+ }
+ }
+ SkScalar distSq = ref->fPt.distanceToSqd(check->fPt);
+ if (distSqBest > distSq && (refSeg != check->segment()
+ || !refSeg->ptsDisjoint(*ref, *check))) {
+ distSqBest = distSq;
+ refBest = ref;
+ checkBest = check;
+ }
+ } while ((check = check->next()) != checkHead);
+nextRef:
+ ;
+ } while ((ref = ref->next()) != refHead);
+doneCheckingDistance:
+ return checkBest && refBest->segment()->match(refBest, checkBest->segment(), checkBest->fT,
+ checkBest->fPt, kAllowAliasMatch);
+}
+
+// Please keep this function in sync with debugMoveNearby()
// Move nearby t values and pts so they all hang off the same span. Alignment happens later.
void SkOpSegment::moveNearby() {
debugValidate();
- SkOpSpanBase* spanS = &fHead;
+ // release undeleted spans pointing to this seg that are linked to the primary span
+ SkOpSpanBase* spanBase = &fHead;
do {
- SkOpSpanBase* test = spanS->upCast()->next();
- SkOpSpanBase* next;
- if (spanS->contains(test)) {
- if (!test->final()) {
- test->upCast()->release(spanS->ptT());
- continue;
- } else if (spanS != &fHead) {
- spanS->upCast()->release(test->ptT());
- spanS = test;
- continue;
+ SkOpPtT* ptT = spanBase->ptT();
+ const SkOpPtT* headPtT = ptT;
+ while ((ptT = ptT->next()) != headPtT) {
+ SkOpSpanBase* test = ptT->span();
+ if (ptT->segment() == this && !ptT->deleted() && test != spanBase
+ && test->ptT() == ptT) {
+ if (test->final()) {
+ if (spanBase == &fHead) {
+ this->clearAll();
+ return;
+ }
+ spanBase->upCast()->release(ptT);
+ } else if (test->prev()) {
+ test->upCast()->release(headPtT);
+ }
+ break;
}
}
- do { // iterate through all spans associated with start
- SkOpPtT* startBase = spanS->ptT();
- next = test->final() ? nullptr : test->upCast()->next();
- do {
- SkOpPtT* testBase = test->ptT();
- do {
- if (startBase == testBase) {
- goto checkNextSpan;
- }
- if (testBase->duplicate()) {
- continue;
- }
- if (this->match(startBase, testBase->segment(), testBase->fT, testBase->fPt)) {
- if (test == &this->fTail) {
- if (spanS == &fHead) {
- debugValidate();
- return; // if this span has collapsed, remove it from parent
- }
- this->fTail.merge(spanS->upCast());
- debugValidate();
- return;
- }
- spanS->merge(test->upCast());
- goto checkNextSpan;
- }
- } while ((testBase = testBase->next()) != test->ptT());
- } while ((startBase = startBase->next()) != spanS->ptT());
- checkNextSpan:
- ;
- } while ((test = next));
- spanS = spanS->upCast()->next();
- } while (!spanS->final());
+ spanBase = spanBase->upCast()->next();
+ } while (!spanBase->final());
+
+ // This loop looks for adjacent spans which are near by
+ spanBase = &fHead;
+ do { // iterate through all spans associated with start
+ SkOpSpanBase* test = spanBase->upCast()->next();
+ if (this->spansNearby(spanBase, test)) {
+ if (test->final()) {
+ if (spanBase->prev()) {
+ test->merge(spanBase->upCast());
+ } else {
+ this->clearAll();
+ return;
+ }
+ } else {
+ spanBase->merge(test->upCast());
+ }
+ }
+ spanBase = test;
+ } while (!spanBase->final());
debugValidate();
}
@@ -1679,8 +1695,7 @@ bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
}
bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT,
- const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp,
- SkScalar flatnessLimit) const {
+ const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp) const {
// average t, find mid pt
double midT = (prior->t() + spanBase->t()) / 2;
SkPoint midPt = this->ptAtT(midT);
@@ -1688,22 +1703,28 @@ bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT
// if the mid pt is not near either end pt, project perpendicular through opp seg
if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt)
&& !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) {
+ if (priorPtT->span() == ptT->span()) {
+ return false;
+ }
coincident = false;
SkIntersections i;
- SkVector dxdy = (*CurveSlopeAtT[fVerb])(this->pts(), this->weight(), midT);
- SkDLine ray = {{{midPt.fX, midPt.fY},
- {(double) midPt.fX + dxdy.fY, (double) midPt.fY - dxdy.fX}}};
- (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), ray, &i);
+ SkDCurve curvePart;
+ this->subDivide(prior, spanBase, &curvePart);
+ SkDVector dxdy = (*CurveDDSlopeAtT[fVerb])(curvePart, 0.5f);
+ SkDPoint partMidPt = (*CurveDDPointAtT[fVerb])(curvePart, 0.5f);
+ SkDLine ray = {{{midPt.fX, midPt.fY}, {partMidPt.fX + dxdy.fY, partMidPt.fY - dxdy.fX}}};
+ SkDCurve oppPart;
+ opp->subDivide(priorPtT->span(), ptT->span(), &oppPart);
+ (*CurveDIntersectRay[opp->verb()])(oppPart, ray, &i);
// measure distance and see if it's small enough to denote coincidence
for (int index = 0; index < i.used(); ++index) {
+ if (!between(0, i[0][index], 1)) {
+ continue;
+ }
SkDPoint oppPt = i.pt(index);
if (oppPt.approximatelyEqual(midPt)) {
- SkVector oppDxdy = (*CurveSlopeAtT[opp->verb()])(opp->pts(),
- opp->weight(), i[index][0]);
- oppDxdy.normalize();
- dxdy.normalize();
- SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILON);
- coincident |= flatness < flatnessLimit;
+ // the coincidence can occur at almost any angle
+ coincident = true;
}
}
}

Powered by Google App Engine
This is Rietveld 408576698