pathops version two
R=reed@google.com
marked 'no commit' to attempt to get trybots to run
TBR=reed@google.com
Review URL: https://codereview.chromium.org/1002693002
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index 57090ac..7a234ec 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
// 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
+ SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune
+ 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);
}