cumulative pathops patch
Replace the implicit curve intersection with a geometric curve intersection. The implicit intersection proved mathematically unstable and took a long time to zero in on an answer.
Use pointers instead of indices to refer to parts of curves. Indices required awkward renumbering.
Unify t and point values so that small intervals can be eliminated in one pass.
Break cubics up front to eliminate loops and cusps.
Make the Simplify and Op code more regular and eliminate arbitrary differences.
Add a builder that takes an array of paths and operators.
Delete unused code.
BUG=skia:3588
R=reed@google.com
Review URL: https://codereview.chromium.org/1037573004
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index 57090ac..5c8a7fd 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -5,11 +5,13 @@
* found in the LICENSE file.
*/
#include "SkAddIntersections.h"
+#include "SkOpCoincidence.h"
#include "SkOpEdgeBuilder.h"
#include "SkPathOpsCommon.h"
#include "SkPathWriter.h"
-static bool bridgeWinding(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* simple) {
+static bool bridgeWinding(SkTDArray<SkOpContour* >& contourList, SkPathWriter* simple,
+ SkChunkAlloc* allocator) {
bool firstContour = true;
bool unsortable = false;
bool topUnsortable = false;
@@ -17,15 +19,24 @@
SkPoint lastTopLeft;
SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
do {
- int index, endIndex;
+ SkOpSpanBase* start;
+ SkOpSpanBase* end;
bool topDone;
bool onlyVertical = false;
lastTopLeft = topLeft;
- SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kUnaryWinding, &firstContour,
- &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass);
+ SkOpSegment* current = FindSortableTop(contourList, firstPass, SkOpAngle::kUnaryWinding,
+ &firstContour, &start, &end, &topLeft, &topUnsortable, &topDone, &onlyVertical,
+ allocator);
if (!current) {
if ((!topUnsortable || firstPass) && !topDone) {
SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
+ if (lastTopLeft.fX == SK_ScalarMin && lastTopLeft.fY == SK_ScalarMin) {
+ if (firstPass) {
+ firstPass = false;
+ } else {
+ break;
+ }
+ }
topLeft.fX = topLeft.fY = SK_ScalarMin;
continue;
}
@@ -34,62 +45,66 @@
break;
}
firstPass = !topUnsortable || lastTopLeft != topLeft;
- SkTDArray<SkOpSpan*> chase;
+ SkTDArray<SkOpSpanBase*> chase;
do {
- if (current->activeWinding(index, endIndex)) {
+ if (current->activeWinding(start, end)) {
do {
if (!unsortable && current->done()) {
break;
}
SkASSERT(unsortable || !current->done());
- int nextStart = index;
- int nextEnd = endIndex;
+ SkOpSpanBase* nextStart = start;
+ SkOpSpanBase* nextEnd = end;
SkOpSegment* next = current->findNextWinding(&chase, &nextStart, &nextEnd,
&unsortable);
if (!next) {
if (!unsortable && simple->hasMove()
&& current->verb() != SkPath::kLine_Verb
&& !simple->isClosed()) {
- current->addCurveTo(index, endIndex, simple, true);
- SkASSERT(simple->isClosed());
+ current->addCurveTo(start, end, simple, true);
+ #if DEBUG_ACTIVE_SPANS
+ if (!simple->isClosed()) {
+ DebugShowActiveSpans(contourList);
+ }
+ #endif
}
break;
}
#if DEBUG_FLOW
SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
- current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
- current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
+ current->debugID(), start->pt().fX, start->pt().fY,
+ end->pt().fX, end->pt().fY);
#endif
- current->addCurveTo(index, endIndex, simple, true);
+ current->addCurveTo(start, end, simple, true);
current = next;
- index = nextStart;
- endIndex = nextEnd;
- } while (!simple->isClosed() && (!unsortable
- || !current->done(SkMin32(index, endIndex))));
- if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
-// SkASSERT(unsortable || simple->isEmpty());
- int min = SkMin32(index, endIndex);
- if (!current->done(min)) {
- current->addCurveTo(index, endIndex, simple, true);
- current->markDoneUnary(min);
+ start = nextStart;
+ end = nextEnd;
+ } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
+ if (current->activeWinding(start, end) && !simple->isClosed()) {
+ SkOpSpan* spanStart = start->starter(end);
+ if (!spanStart->done()) {
+ current->addCurveTo(start, end, simple, true);
+ current->markDone(spanStart);
}
}
simple->close();
} else {
- SkOpSpan* last = current->markAndChaseDoneUnary(index, endIndex);
- if (last && !last->fChased && !last->fLoop) {
- last->fChased = true;
+ SkOpSpanBase* last = current->markAndChaseDone(start, end);
+ if (last && !last->chased()) {
+ last->setChased(true);
SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
// assert that last isn't already in array
*chase.append() = last;
#if DEBUG_WINDING
- SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
- last->fOther->span(last->fOtherIndex).fOther->debugID(), last->fWindSum,
- last->fSmall);
+ SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
+ if (!last->final()) {
+ SkDebugf(" windSum=%d", last->upCast()->windSum());
+ }
+ SkDebugf("\n");
#endif
}
}
- current = FindChase(&chase, &index, &endIndex);
+ current = FindChase(&chase, &start, &end);
#if DEBUG_ACTIVE_SPANS
DebugShowActiveSpans(contourList);
#endif
@@ -102,9 +117,11 @@
}
// returns true if all edges were processed
-static bool bridgeXor(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* simple) {
+static bool bridgeXor(SkTDArray<SkOpContour* >& contourList, SkPathWriter* simple,
+ SkChunkAlloc* allocator) {
SkOpSegment* current;
- int start, end;
+ SkOpSpanBase* start;
+ SkOpSpanBase* end;
bool unsortable = false;
bool closable = true;
while ((current = FindUndone(contourList, &start, &end))) {
@@ -115,34 +132,38 @@
}
#endif
SkASSERT(unsortable || !current->done());
- int nextStart = start;
- int nextEnd = end;
+ SkOpSpanBase* nextStart = start;
+ SkOpSpanBase* nextEnd = end;
SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unsortable);
if (!next) {
if (!unsortable && simple->hasMove()
&& current->verb() != SkPath::kLine_Verb
&& !simple->isClosed()) {
current->addCurveTo(start, end, simple, true);
- SkASSERT(simple->isClosed());
+ #if DEBUG_ACTIVE_SPANS
+ if (!simple->isClosed()) {
+ DebugShowActiveSpans(contourList);
+ }
+ #endif
}
break;
}
#if DEBUG_FLOW
SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
- current->debugID(), current->xyAtT(start).fX, current->xyAtT(start).fY,
- current->xyAtT(end).fX, current->xyAtT(end).fY);
+ current->debugID(), start->pt().fX, start->pt().fY,
+ end->pt().fX, end->pt().fY);
#endif
current->addCurveTo(start, end, simple, true);
current = next;
start = nextStart;
end = nextEnd;
- } while (!simple->isClosed() && (!unsortable || !current->done(SkMin32(start, end))));
+ } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
if (!simple->isClosed()) {
SkASSERT(unsortable);
- int min = SkMin32(start, end);
- if (!current->done(min)) {
+ SkOpSpan* spanStart = start->starter(end);
+ if (!spanStart->done()) {
current->addCurveTo(start, end, simple, true);
- current->markDone(min, 1);
+ current->markDone(spanStart);
}
closable = false;
}
@@ -156,52 +177,68 @@
// FIXME : add this as a member of SkPath
bool Simplify(const SkPath& path, SkPath* result) {
-#if DEBUG_SORT || DEBUG_SWAP_TOP
- SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
-#endif
+ SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune
// returns 1 for evenodd, -1 for winding, regardless of inverse-ness
SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType
: SkPath::kEvenOdd_FillType;
-
+ if (path.isConvex()) {
+ if (result != &path) {
+ *result = path;
+ }
+ result->setFillType(fillType);
+ return true;
+ }
// turn path into list of segments
- SkTArray<SkOpContour> contours;
- SkOpEdgeBuilder builder(path, contours);
- if (!builder.finish()) {
+ SkOpCoincidence coincidence;
+ SkOpContour contour;
+ SkOpGlobalState globalState(&coincidence PATH_OPS_DEBUG_PARAMS(&contour));
+#if DEBUG_SORT || DEBUG_SWAP_TOP
+ SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
+#endif
+ SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState);
+ if (!builder.finish(&allocator)) {
return false;
}
- SkTArray<SkOpContour*, true> contourList;
- MakeContourList(contours, contourList, false, false);
- SkOpContour** currentPtr = contourList.begin();
+#if !FORCE_RELEASE
+ contour.dumpSegments((SkPathOp) -1);
+#endif
result->reset();
result->setFillType(fillType);
+ SkTDArray<SkOpContour* > contourList;
+ MakeContourList(&contour, contourList, false, false);
+ SkOpContour** currentPtr = contourList.begin();
if (!currentPtr) {
return true;
}
- SkOpContour** listEnd = contourList.end();
+ if ((*currentPtr)->count() == 0) {
+ SkASSERT((*currentPtr)->next() == NULL);
+ return true;
+ }
+ SkOpContour** listEnd2 = contourList.end();
// find all intersections between segments
do {
SkOpContour** nextPtr = currentPtr;
SkOpContour* current = *currentPtr++;
- if (current->containsCubics()) {
- AddSelfIntersectTs(current);
- }
SkOpContour* next;
do {
next = *nextPtr++;
- } while (AddIntersectTs(current, next) && nextPtr != listEnd);
- } while (currentPtr != listEnd);
- if (!HandleCoincidence(&contourList, 0)) {
+ } while (AddIntersectTs(current, next, &coincidence, &allocator) && nextPtr != listEnd2);
+ } while (currentPtr != listEnd2);
+#if DEBUG_VALIDATE
+ globalState.setPhase(SkOpGlobalState::kWalking);
+#endif
+ if (!HandleCoincidence(&contourList, &coincidence, &allocator, &globalState)) {
return false;
}
// construct closed contours
- SkPathWriter simple(*result);
- if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple)
- : !bridgeXor(contourList, &simple))
+ SkPathWriter wrapper(*result);
+ if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &wrapper, &allocator)
+ : !bridgeXor(contourList, &wrapper, &allocator))
{ // if some edges could not be resolved, assemble remaining fragments
SkPath temp;
temp.setFillType(fillType);
SkPathWriter assembled(temp);
- Assemble(simple, &assembled);
+ Assemble(wrapper, &assembled);
*result = *assembled.nativePath();
result->setFillType(fillType);
}