More conic-specific tests revealed a few conic-specific bugs. Because javascript / canvas make visualizing conics tricky, new native tools are required.
The utility SubsetPath removes parts of a potentially very large path to isolate a minimal test case. SubsetPath is very useful for debugging path ops, but is not path ops specific.
PathOpsBuilderConicTest compares the output of the Path Ops Builder, sequential calls to Simplify, and SkRegions for some number of rotated ovals.
Some tests caused path ops to hang. It was caught adding a loop of curves because the head was not found by the tail. Even though the root cause has been fixed, SkSegment::addCurveTo callers now abort the path op if the same curve was added twice.
The subdivided conic weight was been computed anew. Fortunately, it's a simpler computation that the one it replaces.
Some Simplify() subroutines returned false to signal that the results needed assembling. Change these to abort the current operation instead.
Coincident curve intersection triggered two small bugs; one where no perpendicular could be found for coincident curves, and one where no coincident curves remain after looping.
The SixtyOvals test can be run through multiple processes instead of multiple threads. This strategy allows a 48 core machine to saturate all cores at 100%.
The DEBUG_VISUALIZE_CONICS code in PathOpsConicIntersectionTest acknowleges that it is easier to visualize conics with Skia than with script and html canvas. This test also verifies that path ops subdivision matches geometry chopping.
TBR=reed@google.com
Review URL: https://codereview.chromium.org/1405383004
diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index 2e4b2ca..df65437 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -42,7 +42,7 @@
path->deferredMove(pt);
const SkOpSegment* segment = &fHead;
do {
- segment->addCurveTo(segment->head(), segment->tail(), path, true);
+ SkAssertResult(segment->addCurveTo(segment->head(), segment->tail(), path));
} while ((segment = segment->next()));
path->close();
}
@@ -52,7 +52,7 @@
path->deferredMove(pt);
const SkOpSegment* segment = fTail;
do {
- segment->addCurveTo(segment->tail(), segment->head(), path, true);
+ SkAssertResult(segment->addCurveTo(segment->tail(), segment->head(), path));
} while ((segment = segment->prev()));
path->close();
}
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index c612008..d0e09a3 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -397,14 +397,14 @@
void toPartialBackward(SkPathWriter* path) const {
const SkOpSegment* segment = fTail;
do {
- segment->addCurveTo(segment->tail(), segment->head(), path, true);
+ SkAssertResult(segment->addCurveTo(segment->tail(), segment->head(), path));
} while ((segment = segment->prev()));
}
void toPartialForward(SkPathWriter* path) const {
const SkOpSegment* segment = &fHead;
do {
- segment->addCurveTo(segment->head(), segment->tail(), path, true);
+ SkAssertResult(segment->addCurveTo(segment->head(), segment->tail(), path));
} while ((segment = segment->next()));
}
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 76032aa..3b81cf2 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -240,8 +240,11 @@
} while ((current = current->next()));
}
-void SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
- SkPathWriter* path, bool active) const {
+bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
+ SkPathWriter* path) const {
+ if (start->starter(end)->alreadyAdded()) {
+ return false;
+ }
SkOpCurve edge;
const SkPoint* ePtr;
SkScalar eWeight;
@@ -254,46 +257,45 @@
ePtr = edge.fPts;
eWeight = edge.fWeight;
}
- if (active) {
- bool reverse = ePtr == fPts && start != &fHead;
- if (reverse) {
- path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]);
- switch (fVerb) {
- case SkPath::kLine_Verb:
- path->deferredLine(ePtr[0]);
- break;
- case SkPath::kQuad_Verb:
- path->quadTo(ePtr[1], ePtr[0]);
- break;
- case SkPath::kConic_Verb:
- path->conicTo(ePtr[1], ePtr[0], eWeight);
- break;
- case SkPath::kCubic_Verb:
- path->cubicTo(ePtr[2], ePtr[1], ePtr[0]);
- break;
- default:
- SkASSERT(0);
- }
- } else {
- path->deferredMoveLine(ePtr[0]);
- switch (fVerb) {
- case SkPath::kLine_Verb:
- path->deferredLine(ePtr[1]);
- break;
- case SkPath::kQuad_Verb:
- path->quadTo(ePtr[1], ePtr[2]);
- break;
- case SkPath::kConic_Verb:
- path->conicTo(ePtr[1], ePtr[2], eWeight);
- break;
- case SkPath::kCubic_Verb:
- path->cubicTo(ePtr[1], ePtr[2], ePtr[3]);
- break;
- default:
- SkASSERT(0);
- }
+ bool reverse = ePtr == fPts && start != &fHead;
+ if (reverse) {
+ path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]);
+ switch (fVerb) {
+ case SkPath::kLine_Verb:
+ path->deferredLine(ePtr[0]);
+ break;
+ case SkPath::kQuad_Verb:
+ path->quadTo(ePtr[1], ePtr[0]);
+ break;
+ case SkPath::kConic_Verb:
+ path->conicTo(ePtr[1], ePtr[0], eWeight);
+ break;
+ case SkPath::kCubic_Verb:
+ path->cubicTo(ePtr[2], ePtr[1], ePtr[0]);
+ break;
+ default:
+ SkASSERT(0);
+ }
+ } else {
+ path->deferredMoveLine(ePtr[0]);
+ switch (fVerb) {
+ case SkPath::kLine_Verb:
+ path->deferredLine(ePtr[1]);
+ break;
+ case SkPath::kQuad_Verb:
+ path->quadTo(ePtr[1], ePtr[2]);
+ break;
+ case SkPath::kConic_Verb:
+ path->conicTo(ePtr[1], ePtr[2], eWeight);
+ break;
+ case SkPath::kCubic_Verb:
+ path->cubicTo(ePtr[1], ePtr[2], ePtr[3]);
+ break;
+ default:
+ SkASSERT(0);
}
}
+ return true;
}
SkOpPtT* SkOpSegment::addMissing(double t, SkOpSegment* opp, SkChunkAlloc* allocator) {
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 98e140c..06649aa 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -69,8 +69,7 @@
return this;
}
- void addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, SkPathWriter* path,
- bool active) const;
+ bool addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, SkPathWriter* path) const;
SkOpAngle* addEndSpan(SkChunkAlloc* allocator) {
SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
diff --git a/src/pathops/SkOpSpan.cpp b/src/pathops/SkOpSpan.cpp
index 4d437f7..7c98e1d 100755
--- a/src/pathops/SkOpSpan.cpp
+++ b/src/pathops/SkOpSpan.cpp
@@ -361,6 +361,7 @@
fTopTTry = 0;
fChased = fDone = false;
segment->bumpCount();
+ fAlreadyAdded = false;
}
void SkOpSpan::setOppSum(int oppSum) {
diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h
index dab0dfa..e512554 100644
--- a/src/pathops/SkOpSpan.h
+++ b/src/pathops/SkOpSpan.h
@@ -372,6 +372,14 @@
class SkOpSpan : public SkOpSpanBase {
public:
+ bool alreadyAdded() const {
+ if (fAlreadyAdded) {
+ return true;
+ }
+ fAlreadyAdded = true;
+ return false;
+ }
+
bool clearCoincident() {
SkASSERT(!final());
if (fCoincident == this) {
@@ -506,6 +514,7 @@
int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here
int fTopTTry; // specifies direction and t value to try next
bool fDone; // if set, this span to next higher T has been processed
+ mutable bool fAlreadyAdded;
};
#endif
diff --git a/src/pathops/SkPathOpsConic.cpp b/src/pathops/SkPathOpsConic.cpp
index f80af03..86bad26 100644
--- a/src/pathops/SkPathOpsConic.cpp
+++ b/src/pathops/SkPathOpsConic.cpp
@@ -153,13 +153,8 @@
double bx = 2 * dx - (ax + cx) / 2;
double by = 2 * dy - (ay + cy) / 2;
double bz = 2 * dz - (az + cz) / 2;
- SkDConic dst = {{{{ax / az, ay / az}, {bx / bz, by / bz}, {cx / cz, cy / cz}}}, 0 };
- SkDPoint dMidAC = { (dst.fPts[0].fX + dst.fPts[2].fX) / 2,
- (dst.fPts[0].fY + dst.fPts[2].fY) / 2 };
- SkDPoint dMid = { dx / dz, dy / dz };
- SkDVector dWNumer = dMidAC - dMid;
- SkDVector dWDenom = dMid - dst.fPts[1];
- dst.fWeight = dWNumer.length() / dWDenom.length();
+ SkDConic dst = {{{{ax / az, ay / az}, {bx / bz, by / bz}, {cx / cz, cy / cz}}},
+ SkDoubleToScalar(bz / sqrt(az * cz)) };
return dst;
}
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index b5e0090..257cb8e 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -111,7 +111,9 @@
if (!unsortable && simple->hasMove()
&& current->verb() != SkPath::kLine_Verb
&& !simple->isClosed()) {
- current->addCurveTo(start, end, simple, true);
+ if (!current->addCurveTo(start, end, simple)) {
+ return false;
+ }
#if DEBUG_ACTIVE_SPANS
if (!simple->isClosed()) {
DebugShowActiveSpans(contourList);
@@ -125,7 +127,9 @@
current->debugID(), start->pt().fX, start->pt().fY,
end->pt().fX, end->pt().fY);
#endif
- current->addCurveTo(start, end, simple, true);
+ if (!current->addCurveTo(start, end, simple)) {
+ return false;
+ }
current = next;
start = nextStart;
end = nextEnd;
@@ -133,7 +137,9 @@
if (current->activeWinding(start, end) && !simple->isClosed()) {
SkOpSpan* spanStart = start->starter(end);
if (!spanStart->done()) {
- current->addCurveTo(start, end, simple, true);
+ if (!current->addCurveTo(start, end, simple)) {
+ return false;
+ }
current->markDone(spanStart);
}
}
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index 34b19d1..08bb26d 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -11,7 +11,7 @@
#include "SkPathWriter.h"
static bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* simple,
- SkChunkAlloc* allocator) {
+ SkChunkAlloc* allocator, bool* closable) {
bool unsortable = false;
do {
SkOpSpan* span = FindSortableTop(contourList);
@@ -37,7 +37,9 @@
if (!unsortable && simple->hasMove()
&& current->verb() != SkPath::kLine_Verb
&& !simple->isClosed()) {
- current->addCurveTo(start, end, simple, true);
+ if (!current->addCurveTo(start, end, simple)) {
+ return false;
+ }
#if DEBUG_ACTIVE_SPANS
if (!simple->isClosed()) {
DebugShowActiveSpans(contourList);
@@ -51,7 +53,9 @@
current->debugID(), start->pt().fX, start->pt().fY,
end->pt().fX, end->pt().fY);
#endif
- current->addCurveTo(start, end, simple, true);
+ if (!current->addCurveTo(start, end, simple)) {
+ return false;
+ }
current = next;
start = nextStart;
end = nextEnd;
@@ -59,7 +63,9 @@
if (current->activeWinding(start, end) && !simple->isClosed()) {
SkOpSpan* spanStart = start->starter(end);
if (!spanStart->done()) {
- current->addCurveTo(start, end, simple, true);
+ if (!current->addCurveTo(start, end, simple)) {
+ return false;
+ }
current->markDone(spanStart);
}
}
@@ -88,17 +94,18 @@
}
} while (true);
} while (true);
- return simple->someAssemblyRequired();
+ *closable = !simple->someAssemblyRequired();
+ return true;
}
// returns true if all edges were processed
static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* simple,
- SkChunkAlloc* allocator) {
+ SkChunkAlloc* allocator, bool* closable) {
SkOpSegment* current;
SkOpSpanBase* start;
SkOpSpanBase* end;
bool unsortable = false;
- bool closable = true;
+ *closable = true;
while ((current = FindUndone(contourList, &start, &end))) {
do {
#if DEBUG_ACTIVE_SPANS
@@ -114,7 +121,9 @@
if (!unsortable && simple->hasMove()
&& current->verb() != SkPath::kLine_Verb
&& !simple->isClosed()) {
- current->addCurveTo(start, end, simple, true);
+ if (!current->addCurveTo(start, end, simple)) {
+ return false;
+ }
#if DEBUG_ACTIVE_SPANS
if (!simple->isClosed()) {
DebugShowActiveSpans(contourList);
@@ -128,7 +137,9 @@
current->debugID(), start->pt().fX, start->pt().fY,
end->pt().fX, end->pt().fY);
#endif
- current->addCurveTo(start, end, simple, true);
+ if (!current->addCurveTo(start, end, simple)) {
+ return false;
+ }
current = next;
start = nextStart;
end = nextEnd;
@@ -137,17 +148,19 @@
SkASSERT(unsortable);
SkOpSpan* spanStart = start->starter(end);
if (!spanStart->done()) {
- current->addCurveTo(start, end, simple, true);
+ if (!current->addCurveTo(start, end, simple)) {
+ return false;
+ }
current->markDone(spanStart);
}
- closable = false;
+ *closable = false;
}
simple->close();
#if DEBUG_ACTIVE_SPANS
DebugShowActiveSpans(contourList);
#endif
}
- return closable;
+ return true;
}
// FIXME : add this as a member of SkPath
@@ -203,8 +216,13 @@
result->reset();
result->setFillType(fillType);
SkPathWriter wrapper(*result);
- if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &wrapper, &allocator)
- : !bridgeXor(contourList, &wrapper, &allocator))
+ bool closable;
+ if (builder.xorMask() == kWinding_PathOpsMask
+ ? !bridgeWinding(contourList, &wrapper, &allocator, &closable)
+ : !bridgeXor(contourList, &wrapper, &allocator, &closable)) {
+ return false;
+ }
+ if (!closable)
{ // if some edges could not be resolved, assemble remaining fragments
SkPath temp;
temp.setFillType(fillType);
diff --git a/src/pathops/SkPathOpsTSect.h b/src/pathops/SkPathOpsTSect.h
index 56a320a..bebdf40 100644
--- a/src/pathops/SkPathOpsTSect.h
+++ b/src/pathops/SkPathOpsTSect.h
@@ -987,8 +987,8 @@
first->fCoinStart.setPerp(fCurve, start1s, fCurve[0], sect2->fCurve);
first->fCoinEnd.setPerp(fCurve, start1e, fCurve[TCurve::kPointLast], sect2->fCurve);
bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
- double oppStartT = SkTMax(0., first->fCoinStart.perpT());
- double oppEndT = SkTMin(1., first->fCoinEnd.perpT());
+ double oppStartT = first->fCoinStart.perpT() == -1 ? 0 : SkTMax(0., first->fCoinStart.perpT());
+ double oppEndT = first->fCoinEnd.perpT() == -1 ? 1 : SkTMin(1., first->fCoinEnd.perpT());
if (!oppMatched) {
SkTSwap(oppStartT, oppEndT);
}
@@ -2086,7 +2086,7 @@
#if DEBUG_T_SECT_LOOP_COUNT
intersections->debugBumpLoopCount(SkIntersections::kCoinCheck_DebugLoop);
#endif
- if (!--coinLoopCount) {
+ if (!--coinLoopCount && sect1->fHead && sect2->fHead) {
/* All known working cases resolve in two tries. Sadly, cubicConicTests[0]
gets stuck in a loop. It adds an extension to allow a coincident end
perpendicular to track its intersection in the opposite curve. However,
@@ -2127,8 +2127,12 @@
}
SkASSERT(sect2->fCoincident); // courtesy check : coincidence only looks at sect 1
do {
- SkASSERT(coincident->fCoinStart.isCoincident());
- SkASSERT(coincident->fCoinEnd.isCoincident());
+ if (!coincident->fCoinStart.isCoincident()) {
+ continue;
+ }
+ if (!coincident->fCoinEnd.isCoincident()) {
+ continue;
+ }
int index = intersections->insertCoincident(coincident->fStartT,
coincident->fCoinStart.perpT(), coincident->fPart[0]);
if ((intersections->insertCoincident(coincident->fEndT,