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

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/pathops/SkPathOpsOp.cpp

Issue 1037573004: cumulative pathops patch (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: fix pathopsinverse gm Created 5 years, 9 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
« no previous file with comments | « src/pathops/SkPathOpsLine.cpp ('k') | src/pathops/SkPathOpsPoint.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/pathops/SkPathOpsOp.cpp
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index f2b25c04ecb52ab303519752d2db61ccd29168d3..25ddb7dec6a2302abf5e87ba498c18b6d014e313 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -5,27 +5,29 @@
* found in the LICENSE file.
*/
#include "SkAddIntersections.h"
+#include "SkOpCoincidence.h"
#include "SkOpEdgeBuilder.h"
#include "SkPathOpsCommon.h"
#include "SkPathWriter.h"
-static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* endIndex) {
+static SkOpSegment* findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr,
+ SkOpSpanBase** endPtr) {
while (chase.count()) {
- SkOpSpan* span;
+ SkOpSpanBase* span;
chase.pop(&span);
- const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
- SkOpSegment* segment = backPtr.fOther;
- *tIndex = backPtr.fOtherIndex;
+ // OPTIMIZE: prev makes this compatible with old code -- but is it necessary?
+ *startPtr = span->ptT()->prev()->span();
+ SkOpSegment* segment = (*startPtr)->segment();
bool sortable = true;
bool done = true;
- *endIndex = -1;
- if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done,
+ *endPtr = NULL;
+ if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done,
&sortable)) {
if (last->unorderable()) {
continue;
}
- *tIndex = last->start();
- *endIndex = last->end();
+ *startPtr = last->start();
+ *endPtr = last->end();
#if TRY_ROTATE
*chase.insert(0) = span;
#else
@@ -40,7 +42,7 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* e
continue;
}
// find first angle, initialize winding to computed fWindSum
- const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex);
+ const SkOpAngle* angle = segment->spanToAngle(*startPtr, *endPtr);
if (!angle) {
continue;
}
@@ -65,33 +67,25 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* e
SkTSwap<int>(sumMiWinding, sumSuWinding);
}
SkOpSegment* first = NULL;
- bool badData = false;
- while ((angle = angle->next()) != firstAngle && !badData) {
+ firstAngle = angle;
+ while ((angle = angle->next()) != firstAngle) {
segment = angle->segment();
- int start = angle->start();
- int end = angle->end();
+ SkOpSpanBase* start = angle->start();
+ SkOpSpanBase* end = angle->end();
int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
&maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
if (!segment->done(angle)) {
if (!first) {
first = segment;
- *tIndex = start;
- *endIndex = end;
- }
- if (segment->inconsistentAngle(maxWinding, sumWinding, oppMaxWinding,
- oppSumWinding, angle)) {
- badData = true;
- break;
+ *startPtr = start;
+ *endPtr = end;
}
// OPTIMIZATION: should this also add to the chase?
(void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
oppSumWinding, angle);
}
}
- if (badData) {
- continue;
- }
if (first) {
#if TRY_ROTATE
*chase.insert(0) = span;
@@ -104,36 +98,8 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* e
return NULL;
}
-/*
-static bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding,
- bool windingIsOp, PathOp op) {
- bool active = windingIsActive(winding, spanWinding);
- if (!active) {
- return false;
- }
- if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) {
- switch (op) {
- case kIntersect_Op:
- case kUnion_Op:
- return true;
- case kDifference_Op: {
- int absSpan = abs(spanWinding);
- int absOpp = abs(oppSpanWinding);
- return windingIsOp ? absSpan < absOpp : absSpan > absOpp;
- }
- case kXor_Op:
- return spanWinding != oppSpanWinding;
- default:
- SkASSERT(0);
- }
- }
- bool opActive = oppWinding != 0;
- return gOpLookup[op][opActive][windingIsOp];
-}
-*/
-
-static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp op,
- const int xorMask, const int xorOpMask, SkPathWriter* simple) {
+static bool bridgeOp(SkTDArray<SkOpContour* >& contourList, const SkPathOp op,
+ const int xorMask, const int xorOpMask, SkPathWriter* simple, SkChunkAlloc* allocator) {
bool firstContour = true;
bool unsortable = false;
bool topUnsortable = false;
@@ -141,12 +107,14 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o
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::kBinarySingle, &firstContour,
- &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass);
+ SkOpSegment* current = FindSortableTop(contourList, firstPass, SkOpAngle::kBinarySingle,
+ &firstContour, &start, &end, &topLeft, &topUnsortable, &topDone, &onlyVertical,
+ allocator);
if (!current) {
if ((!topUnsortable || firstPass) && !topDone) {
SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
@@ -165,69 +133,65 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o
break;
}
firstPass = !topUnsortable || lastTopLeft != topLeft;
- SkTDArray<SkOpSpan*> chase;
+ SkTDArray<SkOpSpanBase*> chase;
do {
- if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
+ if (current->activeOp(start, end, xorMask, xorOpMask, op)) {
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->findNextOp(&chase, &nextStart, &nextEnd,
&unsortable, op, xorMask, xorOpMask);
if (!next) {
if (!unsortable && simple->hasMove()
&& current->verb() != SkPath::kLine_Verb
&& !simple->isClosed()) {
- current->addCurveTo(index, endIndex, simple, true);
+ current->addCurveTo(start, end, simple, true);
#if DEBUG_ACTIVE_SPANS
if (!simple->isClosed()) {
DebugShowActiveSpans(contourList);
}
#endif
-// SkASSERT(simple->isClosed());
}
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);
+ SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
+ 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()) {
- // FIXME : add to simplify, xor cpaths
- int min = SkMin32(index, endIndex);
- if (!unsortable && !simple->isEmpty()) {
- unsortable = current->checkSmall(min);
- }
- if (!current->done(min)) {
- current->addCurveTo(index, endIndex, simple, true);
- current->markDoneBinary(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->markAndChaseDoneBinary(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));
*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 = findChaseOp(chase, &index, &endIndex);
+ current = findChaseOp(chase, &start, &end);
#if DEBUG_ACTIVE_SPANS
DebugShowActiveSpans(contourList);
#endif
@@ -241,17 +205,17 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o
// pretty picture:
// https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing
-static const SkPathOp gOpInverse[kReverseDifference_PathOp + 1][2][2] = {
+static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = {
// inside minuend outside minuend
// inside subtrahend outside subtrahend inside subtrahend outside subtrahend
- {{ kDifference_PathOp, kIntersect_PathOp }, { kUnion_PathOp, kReverseDifference_PathOp }},
- {{ kIntersect_PathOp, kDifference_PathOp }, { kReverseDifference_PathOp, kUnion_PathOp }},
- {{ kUnion_PathOp, kReverseDifference_PathOp }, { kDifference_PathOp, kIntersect_PathOp }},
- {{ kXOR_PathOp, kXOR_PathOp }, { kXOR_PathOp, kXOR_PathOp }},
- {{ kReverseDifference_PathOp, kUnion_PathOp }, { kIntersect_PathOp, kDifference_PathOp }},
+{{ kDifference_SkPathOp, kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }},
+{{ kIntersect_SkPathOp, kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }},
+{{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp, kIntersect_SkPathOp }},
+{{ kXOR_SkPathOp, kXOR_SkPathOp }, { kXOR_SkPathOp, kXOR_SkPathOp }},
+{{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp, kDifference_SkPathOp }},
};
-static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = {
+static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = {
{{ false, false }, { true, false }}, // diff
{{ false, false }, { false, true }}, // sect
{{ false, true }, { true, true }}, // union
@@ -291,16 +255,20 @@ static void dump_op(const SkPath& one, const SkPath& two, SkPathOp op) {
dump_path(file, two, false, true);
fprintf(file, " SkPath path2(path);\n");
fprintf(file, " testPathOp(reporter, path1, path2, (SkPathOp) %d, filename);\n", op);
- fprintf(file, "}\n");
+ fprintf(file, "}\n");
fclose(file);
}
#endif
bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
+ SkChunkAlloc allocator(4096); // FIXME: add a constant expression here, tune
+ SkOpContour contour;
+ SkOpCoincidence coincidence;
+ SkOpGlobalState globalState(&coincidence PATH_OPS_DEBUG_PARAMS(&contour));
#if DEBUGGING_PATHOPS_FROM_HOST
dump_op(one, two, op);
-#endif
-#if DEBUG_SHOW_TEST_NAME
+#endif
+#if 0 && DEBUG_SHOW_TEST_NAME
char* debugName = DEBUG_FILENAME_STRING;
if (debugName && debugName[0]) {
SkPathOpsDebug::BumpTestName(debugName);
@@ -312,62 +280,62 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
const SkPath* minuend = &one;
const SkPath* subtrahend = &two;
- if (op == kReverseDifference_PathOp) {
+ if (op == kReverseDifference_SkPathOp) {
minuend = &two;
subtrahend = &one;
- op = kDifference_PathOp;
+ op = kDifference_SkPathOp;
}
#if DEBUG_SORT || DEBUG_SWAP_TOP
SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
#endif
// turn path into list of segments
- SkTArray<SkOpContour> contours;
- // FIXME: add self-intersecting cubics' T values to segment
- SkOpEdgeBuilder builder(*minuend, contours);
+ SkOpEdgeBuilder builder(*minuend, &contour, &allocator, &globalState);
if (builder.unparseable()) {
return false;
}
const int xorMask = builder.xorMask();
builder.addOperand(*subtrahend);
- if (!builder.finish()) {
+ if (!builder.finish(&allocator)) {
return false;
}
+#if !FORCE_RELEASE
+ contour.dumpSegments(op);
+#endif
+
result->reset();
result->setFillType(fillType);
const int xorOpMask = builder.xorMask();
- SkTArray<SkOpContour*, true> contourList;
- MakeContourList(contours, contourList, xorMask == kEvenOdd_PathOpsMask,
+ SkTDArray<SkOpContour* > contourList;
+ MakeContourList(&contour, contourList, xorMask == kEvenOdd_PathOpsMask,
xorOpMask == kEvenOdd_PathOpsMask);
SkOpContour** currentPtr = contourList.begin();
if (!currentPtr) {
return true;
}
+ if ((*currentPtr)->count() == 0) {
+ SkASSERT((*currentPtr)->next() == NULL);
+ return true;
+ }
SkOpContour** listEnd = 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 (AddIntersectTs(current, next, &coincidence, &allocator) && nextPtr != listEnd);
} while (currentPtr != listEnd);
+#if DEBUG_VALIDATE
+ globalState.setPhase(SkOpGlobalState::kWalking);
+#endif
// eat through coincident edges
-
- int total = 0;
- int index;
- for (index = 0; index < contourList.count(); ++index) {
- total += contourList[index]->segments().count();
- }
- if (!HandleCoincidence(&contourList, total)) {
+ if (!HandleCoincidence(&contourList, &coincidence, &allocator, &globalState)) {
return false;
}
// construct closed contours
SkPathWriter wrapper(*result);
- bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper);
+ bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper, &allocator);
{ // if some edges could not be resolved, assemble remaining fragments
SkPath temp;
temp.setFillType(fillType);
« no previous file with comments | « src/pathops/SkPathOpsLine.cpp ('k') | src/pathops/SkPathOpsPoint.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698