The path ops builder code needs to determine the winding of each contour added, and reverse windings if the contours are nested in other contours.
Cheap (one contour) paths can be evaluated and reversed as needed with a minimum of checking, but multi-contour paths invoke the regular path ops machinery to determine who is contained by whom.
More tests need to be added to verify that all corner cases are considered, but this fixes the cases in the bug thus far.
R=fmalita@chromium.org
TBR=reed@google.com
BUG=skia:3838
Review URL: https://codereview.chromium.org/1129193006
diff --git a/src/pathops/SkOpBuilder.cpp b/src/pathops/SkOpBuilder.cpp
index 1a446f1..39da2ef 100644
--- a/src/pathops/SkOpBuilder.cpp
+++ b/src/pathops/SkOpBuilder.cpp
@@ -6,8 +6,80 @@
*/
#include "SkMatrix.h"
+#include "SkOpEdgeBuilder.h"
#include "SkPath.h"
#include "SkPathOps.h"
+#include "SkPathOpsCommon.h"
+
+static bool one_contour(const SkPath& path) {
+ SkChunkAlloc allocator(256);
+ int verbCount = path.countVerbs();
+ uint8_t* verbs = (uint8_t*) allocator.alloc(sizeof(uint8_t) * verbCount,
+ SkChunkAlloc::kThrow_AllocFailType);
+ (void) path.getVerbs(verbs, verbCount);
+ for (int index = 1; index < verbCount; ++index) {
+ if (verbs[index] == SkPath::kMove_Verb) {
+ return false;
+ }
+ }
+ return true;
+}
+
+void FixWinding(SkPath* path) {
+ SkPath::FillType fillType = path->getFillType();
+ if (fillType == SkPath::kInverseEvenOdd_FillType) {
+ fillType = SkPath::kInverseWinding_FillType;
+ } else if (fillType == SkPath::kEvenOdd_FillType) {
+ fillType = SkPath::kWinding_FillType;
+ }
+ SkPath::Direction dir;
+ if (one_contour(*path) && path->cheapComputeDirection(&dir)) {
+ if (dir != SkPath::kCCW_Direction) {
+ SkPath temp;
+ temp.reverseAddPath(*path);
+ *path = temp;
+ }
+ path->setFillType(fillType);
+ return;
+ }
+ SkChunkAlloc allocator(4096);
+ SkOpContourHead contourHead;
+ SkOpGlobalState globalState(NULL, &contourHead);
+ SkOpEdgeBuilder builder(*path, &contourHead, &allocator, &globalState);
+ builder.finish(&allocator);
+ SkASSERT(contourHead.next());
+ contourHead.resetReverse();
+ bool writePath = false;
+ SkOpSpan* topSpan;
+ globalState.setPhase(SkOpGlobalState::kFixWinding);
+ while ((topSpan = FindSortableTop(&contourHead))) {
+ SkOpSegment* topSegment = topSpan->segment();
+ SkOpContour* topContour = topSegment->contour();
+ bool active = topSegment->activeWinding(topSpan, topSpan->next());
+ SkASSERT(topContour->isCcw() >= 0);
+ if (active != SkToBool(topContour->isCcw())) {
+ topContour->setReverse();
+ writePath = true;
+ }
+ topContour->markDone();
+ }
+ if (!writePath) {
+ path->setFillType(fillType);
+ return;
+ }
+ SkPath empty;
+ SkPathWriter woundPath(empty);
+ SkOpContour* test = &contourHead;
+ do {
+ if (test->reversed()) {
+ test->toReversePath(&woundPath);
+ } else {
+ test->toPath(&woundPath);
+ }
+ } while ((test = test->next()));
+ *path = *woundPath.nativePath();
+ path->setFillType(fillType);
+}
void SkOpBuilder::add(const SkPath& path, SkPathOp op) {
if (0 == fOps.count() && op != kUnion_SkPathOp) {
@@ -82,10 +154,11 @@
*result = original;
return false;
}
+ // convert the even odd result back to winding form before accumulating it
+ FixWinding(&fPathRefs[index]);
sum.addPath(fPathRefs[index]);
}
reset();
- sum.setFillType(SkPath::kEvenOdd_FillType);
bool success = Simplify(sum, result);
if (!success) {
*result = original;
diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index 178ba3e..18b6328 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -47,6 +47,16 @@
path->close();
}
+void SkOpContour::toReversePath(SkPathWriter* path) const {
+ const SkPoint& pt = fTail->pts()[0];
+ path->deferredMove(pt);
+ const SkOpSegment* segment = fTail;
+ do {
+ segment->addCurveTo(segment->tail(), segment->head(), path, true);
+ } while ((segment = segment->prev()));
+ path->close();
+}
+
SkOpSegment* SkOpContour::undoneSegment(SkOpSpanBase** startPtr, SkOpSpanBase** endPtr) {
SkOpSegment* segment = &fHead;
do {
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index dd5dbb4..f8143cf 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -207,10 +207,21 @@
SkDEBUGCODE(fID = globalState->nextContourID());
}
+ int isCcw() const {
+ return fCcw;
+ }
+
bool isXor() const {
return fXor;
}
+ void markDone() {
+ SkOpSegment* segment = &fHead;
+ do {
+ segment->markAllDone();
+ } while ((segment = segment->next()));
+ }
+
void missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) {
SkASSERT(fCount > 0);
SkOpSegment* segment = &fHead;
@@ -289,6 +300,18 @@
SkDEBUGCODE(fDebugIndent = 0);
}
+ void resetReverse() {
+ SkOpContour* next = this;
+ do {
+ next->fCcw = -1;
+ next->fReverse = false;
+ } while ((next = next->next()));
+ }
+
+ bool reversed() const {
+ return fReverse;
+ }
+
void setBounds() {
SkASSERT(fCount > 0);
const SkOpSegment* segment = &fHead;
@@ -298,6 +321,10 @@
}
}
+ void setCcw(int ccw) {
+ fCcw = ccw;
+ }
+
void setGlobalState(SkOpGlobalState* state) {
fState = state;
}
@@ -315,6 +342,10 @@
fOppXor = isOppXor;
}
+ void setReverse() {
+ fReverse = true;
+ }
+
void setXor(bool isXor) {
fXor = isXor;
}
@@ -347,6 +378,7 @@
} while ((segment = segment->next()));
}
+ void toReversePath(SkPathWriter* path) const;
void toPath(SkPathWriter* path) const;
SkOpSegment* undoneSegment(SkOpSpanBase** startPtr, SkOpSpanBase** endPtr);
@@ -356,11 +388,13 @@
SkOpSegment* fTail;
SkOpContour* fNext;
SkPathOpsBounds fBounds;
+ int fCcw;
int fCount;
int fFirstSorted;
bool fDone; // set by find top segment
bool fTopsFound;
bool fOperand; // true for the second argument to a binary operator
+ bool fReverse; // true if contour should be reverse written to path (used only by fix winding)
bool fXor; // set if original path had even-odd fill
bool fOppXor; // set if opposite path had even-odd fill
SkDEBUGCODE(int fID);
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 8bd0f03..462cff6 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -852,6 +852,13 @@
return fContour->isXor();
}
+void SkOpSegment::markAllDone() {
+ SkOpSpan* span = this->head();
+ do {
+ this->markDone(span);
+ } while ((span = span->next()->upCastable()));
+}
+
SkOpSpanBase* SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end) {
int step = start->step(end);
SkOpSpan* minSpan = start->starter(end);
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 1162c2c..38de406 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -231,6 +231,7 @@
return fPts[SkPathOpsVerbToPoints(fVerb)];
}
+ void markAllDone();
SkOpSpanBase* markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end);
bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
SkOpSpanBase** lastPtr);
diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h
index b7fbf38..f76d57c 100644
--- a/src/pathops/SkPathOpsCommon.h
+++ b/src/pathops/SkPathOpsCommon.h
@@ -22,6 +22,7 @@
SkOpSpan* FindSortableTop(SkOpContourHead* );
SkOpSegment* FindUndone(SkOpContourHead* , SkOpSpanBase** startPtr,
SkOpSpanBase** endPtr);
+void FixWinding(SkPath* path);
bool SortContourList(SkOpContourHead** , bool evenOdd, bool oppEvenOdd);
bool HandleCoincidence(SkOpContourHead* , SkOpCoincidence* , SkChunkAlloc* );
bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result, bool expectSuccess);
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index d37998b..11b6833 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -212,3 +212,4 @@
}
return true;
}
+
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index 845288f..a780a88 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -33,9 +33,7 @@
, fContourHead(head)
, fWindingFailed(false)
, fAngleCoincidence(false)
-#if DEBUG_VALIDATE
, fPhase(kIntersecting)
-#endif
SkDEBUGPARAMS(fAngleID(0))
SkDEBUGPARAMS(fContourID(0))
SkDEBUGPARAMS(fPtTID(0))
@@ -43,12 +41,11 @@
SkDEBUGPARAMS(fSpanID(0)) {
}
-#if DEBUG_VALIDATE
enum Phase {
kIntersecting,
- kWalking
+ kWalking,
+ kFixWinding,
};
-#endif
enum {
kMaxWindingTries = 10
@@ -93,11 +90,9 @@
}
#endif
-#if DEBUG_VALIDATE
Phase phase() const {
return fPhase;
}
-#endif
void setAngleCoincidence() {
fAngleCoincidence = true;
@@ -107,12 +102,10 @@
fContourHead = contourHead;
}
-#if DEBUG_VALIDATE
void setPhase(Phase phase) {
SkASSERT(fPhase != phase);
fPhase = phase;
}
-#endif
// called in very rare cases where angles are sorted incorrectly -- signfies op will fail
void setWindingFailed() {
@@ -128,9 +121,7 @@
SkOpContourHead* fContourHead;
bool fWindingFailed;
bool fAngleCoincidence;
-#if DEBUG_VALIDATE
Phase fPhase;
-#endif
#ifdef SK_DEBUG
int fAngleID;
int fContourID;
diff --git a/src/pathops/SkPathOpsWinding.cpp b/src/pathops/SkPathOpsWinding.cpp
index 53083e4..4a7b1bc 100644
--- a/src/pathops/SkPathOpsWinding.cpp
+++ b/src/pathops/SkPathOpsWinding.cpp
@@ -342,8 +342,12 @@
#endif
}
if (sumSet) {
- (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, NULL);
- (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, NULL);
+ if (this->globalState()->phase() == SkOpGlobalState::kFixWinding) {
+ hitSegment->contour()->setCcw(ccw);
+ } else {
+ (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, NULL);
+ (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, NULL);
+ }
}
if (operand) {
SkTSwap(wind, oppWind);
diff --git a/tests/PathOpsBuilderTest.cpp b/tests/PathOpsBuilderTest.cpp
index 8ab92c3..ea4c567 100644
--- a/tests/PathOpsBuilderTest.cpp
+++ b/tests/PathOpsBuilderTest.cpp
@@ -33,8 +33,10 @@
SkPath::Direction dir;
REPORTER_ASSERT(reporter, result.isRect(NULL, &closed, &dir));
REPORTER_ASSERT(reporter, closed);
- REPORTER_ASSERT(reporter, dir == SkPath::kCW_Direction);
- REPORTER_ASSERT(reporter, rectPath == result);
+ REPORTER_ASSERT(reporter, dir == SkPath::kCCW_Direction);
+ SkBitmap bitmap;
+ int pixelDiff = comparePaths(reporter, __FUNCTION__, rectPath, result, bitmap);
+ REPORTER_ASSERT(reporter, pixelDiff == 0);
rectPath.reset();
rectPath.setFillType(SkPath::kEvenOdd_FillType);
@@ -44,7 +46,7 @@
REPORTER_ASSERT(reporter, result.isRect(NULL, &closed, &dir));
REPORTER_ASSERT(reporter, closed);
REPORTER_ASSERT(reporter, dir == SkPath::kCCW_Direction);
- REPORTER_ASSERT(reporter, rectPath == result);
+ REPORTER_ASSERT(reporter, rectPath == result);
builder.add(rectPath, kDifference_SkPathOp);
REPORTER_ASSERT(reporter, builder.resolve(&result));
@@ -74,12 +76,11 @@
builder.add(circle2, kUnion_SkPathOp);
builder.add(circle3, kDifference_SkPathOp);
REPORTER_ASSERT(reporter, builder.resolve(&result));
- SkBitmap bitmap;
- int pixelDiff = comparePaths(reporter, __FUNCTION__, opCompare, result, bitmap);
+ pixelDiff = comparePaths(reporter, __FUNCTION__, opCompare, result, bitmap);
REPORTER_ASSERT(reporter, pixelDiff == 0);
}
-DEF_TEST(Issue3838, reporter) {
+DEF_TEST(BuilderIssue3838, reporter) {
SkPath path;
path.moveTo(200, 170);
path.lineTo(220, 170);
@@ -93,9 +94,6 @@
path.lineTo(200, 250);
path.lineTo(200, 170);
path.close();
- testSimplify(reporter, path, __FUNCTION__);
- SkPath path3;
- Simplify(path, &path3);
SkPath path2;
SkOpBuilder builder;
builder.add(path, kUnion_SkPathOp);
@@ -104,3 +102,18 @@
int pixelDiff = comparePaths(reporter, __FUNCTION__, path, path2, bitmap);
REPORTER_ASSERT(reporter, pixelDiff == 0);
}
+
+DEF_TEST(BuilderIssue3838_2, reporter) {
+ SkPath path;
+ path.addCircle(100, 100, 50);
+
+ SkOpBuilder builder;
+ builder.add(path, kUnion_SkPathOp);
+ builder.add(path, kUnion_SkPathOp);
+
+ SkPath result;
+ SkBitmap bitmap;
+ builder.resolve(&result);
+ int pixelDiff = comparePaths(reporter, __FUNCTION__, path, result, bitmap);
+ REPORTER_ASSERT(reporter, pixelDiff == 0);
+}