diff options
author | caryclark <caryclark@google.com> | 2015-03-24 07:28:17 -0700 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2015-03-24 07:28:17 -0700 |
commit | ccec0f958ffc71a9986d236bc2eb335cb2111119 (patch) | |
tree | f864209e3594293256ac391715d50222ff22d96b /src/pathops/SkPathOpsOp.cpp | |
parent | 62a320c8d444cd04e4f2952c269ea4cbd58dee64 (diff) |
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
Diffstat (limited to 'src/pathops/SkPathOpsOp.cpp')
-rw-r--r-- | src/pathops/SkPathOpsOp.cpp | 184 |
1 files changed, 76 insertions, 108 deletions
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp index f2b25c04ec..77ae2de778 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 @@ -291,16 +255,19 @@ 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) { + 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); @@ -321,53 +288,54 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { 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); + SkChunkAlloc allocator(4096); // FIXME: add a constant expression here, tune + 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); |