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/SkPathOpsCommon.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/SkPathOpsCommon.cpp')
-rw-r--r-- | src/pathops/SkPathOpsCommon.cpp | 586 |
1 files changed, 262 insertions, 324 deletions
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index 1a5bfc1889..b0fd822a9d 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -5,47 +5,25 @@ * found in the LICENSE file. */ #include "SkAddIntersections.h" +#include "SkOpCoincidence.h" #include "SkOpEdgeBuilder.h" #include "SkPathOpsCommon.h" #include "SkPathWriter.h" #include "SkTSort.h" -static void alignMultiples(SkTArray<SkOpContour*, true>* contourList, - SkTDArray<SkOpSegment::AlignedSpan>* aligned) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; - if (contour->hasMultiples()) { - contour->alignMultiples(aligned); - } - } -} - -static void alignCoincidence(SkTArray<SkOpContour*, true>* contourList, - const SkTDArray<SkOpSegment::AlignedSpan>& aligned) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; - int count = aligned.count(); - for (int index = 0; index < count; ++index) { - contour->alignCoincidence(aligned[index]); - } - } -} - -static int contourRangeCheckY(const SkTArray<SkOpContour*, true>& contourList, SkOpSegment** currentPtr, - int* indexPtr, int* endIndexPtr, double* bestHit, SkScalar* bestDx, - bool* tryAgain, double* midPtr, bool opp) { - const int index = *indexPtr; - const int endIndex = *endIndexPtr; +static int contourRangeCheckY(const SkTDArray<SkOpContour* >& contourList, + SkOpSegment** currentPtr, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr, + double* bestHit, SkScalar* bestDx, bool* tryAgain, double* midPtr, bool opp) { + SkOpSpanBase* start = *startPtr; + SkOpSpanBase* end = *endPtr; const double mid = *midPtr; const SkOpSegment* current = *currentPtr; - double tAtMid = current->tAtMid(index, endIndex, mid); + double tAtMid = SkOpSegment::TAtMid(start, end, mid); SkPoint basePt = current->ptAtT(tAtMid); int contourCount = contourList.count(); SkScalar bestY = SK_ScalarMin; SkOpSegment* bestSeg = NULL; - int bestTIndex = 0; + SkOpSpan* bestTSpan = NULL; bool bestOpp; bool hitSomething = false; for (int cTest = 0; cTest < contourCount; ++cTest) { @@ -57,37 +35,38 @@ static int contourRangeCheckY(const SkTArray<SkOpContour*, true>& contourList, S if (bestY > contour->bounds().fBottom) { continue; } - int segmentCount = contour->segments().count(); - for (int test = 0; test < segmentCount; ++test) { - SkOpSegment* testSeg = &contour->segments()[test]; + SkOpSegment* testSeg = contour->first(); + SkASSERT(testSeg); + do { SkScalar testY = bestY; double testHit; - int testTIndex = testSeg->crossedSpanY(basePt, &testY, &testHit, &hitSomething, tAtMid, - testOpp, testSeg == current); - if (testTIndex < 0) { - if (testTIndex == SK_MinS32) { + bool vertical; + SkOpSpan* testTSpan = testSeg->crossedSpanY(basePt, tAtMid, testOpp, + testSeg == current, &testY, &testHit, &hitSomething, &vertical); + if (!testTSpan) { + if (vertical) { hitSomething = true; bestSeg = NULL; goto abortContours; // vertical encountered, return and try different point } continue; } - if (testSeg == current && current->betweenTs(index, testHit, endIndex)) { - double baseT = current->t(index); - double endT = current->t(endIndex); + if (testSeg == current && SkOpSegment::BetweenTs(start, testHit, end)) { + double baseT = start->t(); + double endT = end->t(); double newMid = (testHit - baseT) / (endT - baseT); #if DEBUG_WINDING - double midT = current->tAtMid(index, endIndex, mid); - SkPoint midXY = current->xyAtT(midT); - double newMidT = current->tAtMid(index, endIndex, newMid); - SkPoint newXY = current->xyAtT(newMidT); + double midT = SkOpSegment::TAtMid(start, end, mid); + SkPoint midXY = current->ptAtT(midT); + double newMidT = SkOpSegment::TAtMid(start, end, newMid); + SkPoint newXY = current->ptAtT(newMidT); SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)" " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__, current->debugID(), mid, newMid, - baseT, current->xAtT(index), current->yAtT(index), + baseT, start->pt().fX, start->pt().fY, baseT + mid * (endT - baseT), midXY.fX, midXY.fY, baseT + newMid * (endT - baseT), newXY.fX, newXY.fY, - endT, current->xAtT(endIndex), current->yAtT(endIndex)); + endT, end->pt().fX, end->pt().fY); #endif *midPtr = newMid * 2; // calling loop with divide by 2 before continuing return SK_MinS32; @@ -95,38 +74,39 @@ static int contourRangeCheckY(const SkTArray<SkOpContour*, true>& contourList, S bestSeg = testSeg; *bestHit = testHit; bestOpp = testOpp; - bestTIndex = testTIndex; + bestTSpan = testTSpan; bestY = testY; - } + } while ((testSeg = testSeg->next())); } abortContours: int result; if (!bestSeg) { result = hitSomething ? SK_MinS32 : 0; } else { - if (bestSeg->windSum(bestTIndex) == SK_MinS32) { + if (bestTSpan->windSum() == SK_MinS32) { *currentPtr = bestSeg; - *indexPtr = bestTIndex; - *endIndexPtr = bestSeg->nextSpan(bestTIndex, 1); - SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0); + *startPtr = bestTSpan; + *endPtr = bestTSpan->next(); + SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr); *tryAgain = true; return 0; } - result = bestSeg->windingAtT(*bestHit, bestTIndex, bestOpp, bestDx); + result = bestSeg->windingAtT(*bestHit, bestTSpan, bestOpp, bestDx); SkASSERT(result == SK_MinS32 || *bestDx); } - double baseT = current->t(index); - double endT = current->t(endIndex); + double baseT = (*startPtr)->t(); + double endT = (*endPtr)->t(); *bestHit = baseT + mid * (endT - baseT); return result; } -SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, int* end) { +SkOpSegment* FindUndone(SkTDArray<SkOpContour* >& contourList, SkOpSpanBase** startPtr, + SkOpSpanBase** endPtr) { int contourCount = contourList.count(); SkOpSegment* result; for (int cIndex = 0; cIndex < contourCount; ++cIndex) { SkOpContour* contour = contourList[cIndex]; - result = contour->undoneSegment(start, end); + result = contour->undoneSegment(startPtr, endPtr); if (result) { return result; } @@ -134,20 +114,23 @@ SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, i return NULL; } -SkOpSegment* FindChase(SkTDArray<SkOpSpan*>* chase, int* tIndex, int* endIndex) { +SkOpSegment* FindChase(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; + SkOpSegment* segment = span->segment(); + *startPtr = span->ptT()->next()->span(); 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)) { - *tIndex = last->start(); - *endIndex = last->end(); + if (last->unorderable()) { + continue; + } + *startPtr = last->start(); + *endPtr = last->end(); #if TRY_ROTATE *chase->insert(0) = span; #else @@ -162,65 +145,58 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpan*>* chase, int* tIndex, int* endIndex) continue; } // find first angle, initialize winding to computed wind sum - const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex); - const SkOpAngle* firstAngle; - SkDEBUGCODE(firstAngle = angle); - SkDEBUGCODE(bool loop = false); - int winding; + const SkOpAngle* angle = segment->spanToAngle(*startPtr, *endPtr); + if (!angle) { + continue; + } + const SkOpAngle* firstAngle = angle; + bool loop = false; + int winding = SK_MinS32; do { angle = angle->next(); - SkASSERT(angle != firstAngle || !loop); - SkDEBUGCODE(loop |= angle == firstAngle); + if (angle == firstAngle && loop) { + break; // if we get here, there's no winding, loop is unorderable + } + loop |= angle == firstAngle; segment = angle->segment(); winding = segment->windSum(angle); } while (winding == SK_MinS32); - int spanWinding = segment->spanSign(angle->start(), angle->end()); - #if DEBUG_WINDING - SkDebugf("%s winding=%d spanWinding=%d\n", __FUNCTION__, winding, spanWinding); - #endif - // turn span winding into contour winding - if (spanWinding * winding < 0) { - winding += spanWinding; - } - // we care about first sign and whether wind sum indicates this - // edge is inside or outside. Maybe need to pass span winding - // or first winding or something into this function? - // advance to first undone angle, then return it and winding - // (to set whether edges are active or not) + if (winding == SK_MinS32) { + continue; + } + int sumWinding = segment->updateWindingReverse(angle); + SkOpSegment* first = NULL; firstAngle = angle; - winding -= firstAngle->segment()->spanSign(firstAngle); while ((angle = angle->next()) != firstAngle) { segment = angle->segment(); - int maxWinding = winding; - winding -= segment->spanSign(angle); - #if DEBUG_SORT - SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__, - segment->debugID(), maxWinding, winding, angle->sign()); - #endif - *tIndex = angle->start(); - *endIndex = angle->end(); - int lesser = SkMin32(*tIndex, *endIndex); - const SkOpSpan& nextSpan = segment->span(lesser); - if (!nextSpan.fDone) { - // FIXME: this be wrong? assign startWinding if edge is in - // same direction. If the direction is opposite, winding to - // assign is flipped sign or +/- 1? - if (SkOpSegment::UseInnerWinding(maxWinding, winding)) { - maxWinding = winding; + SkOpSpanBase* start = angle->start(); + SkOpSpanBase* end = angle->end(); + int maxWinding; + segment->setUpWinding(start, end, &maxWinding, &sumWinding); + if (!segment->done(angle)) { + if (!first) { + first = segment; + *startPtr = start; + *endPtr = end; } - // allowed to do nothing - (void) segment->markAndChaseWinding(angle, maxWinding, 0, NULL); - break; + // OPTIMIZATION: should this also add to the chase? + (void) segment->markAngle(maxWinding, sumWinding, angle); } } - *chase->insert(0) = span; - return segment; + if (first) { + #if TRY_ROTATE + *chase->insert(0) = span; + #else + *chase->append() = span; + #endif + return first; + } } return NULL; } -#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY -void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList) { +#if DEBUG_ACTIVE_SPANS +void DebugShowActiveSpans(SkTDArray<SkOpContour* >& contourList) { int index; for (index = 0; index < contourList.count(); ++ index) { contourList[index]->debugShowActiveSpans(); @@ -228,11 +204,12 @@ void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList) { } #endif -static SkOpSegment* findTopSegment(const SkTArray<SkOpContour*, true>& contourList, int* index, - int* endIndex, SkPoint* topLeft, bool* unsortable, bool* done, bool firstPass) { +static SkOpSegment* findTopSegment(const SkTDArray<SkOpContour* >& contourList, + bool firstPass, SkOpSpanBase** start, SkOpSpanBase** end, SkPoint* topLeft, + bool* unsortable, bool* done, SkChunkAlloc* allocator) { SkOpSegment* result; const SkOpSegment* lastTopStart = NULL; - int lastIndex = -1, lastEndIndex = -1; + SkOpSpanBase* lastStart = NULL, * lastEnd = NULL; do { SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax}; int contourCount = contourList.count(); @@ -261,27 +238,27 @@ static SkOpSegment* findTopSegment(const SkTArray<SkOpContour*, true>& contourLi return NULL; } *topLeft = bestXY; - result = topStart->findTop(index, endIndex, unsortable, firstPass); + result = topStart->findTop(firstPass, start, end, unsortable, allocator); if (!result) { - if (lastTopStart == topStart && lastIndex == *index && lastEndIndex == *endIndex) { + if (lastTopStart == topStart && lastStart == *start && lastEnd == *end) { *done = true; return NULL; } lastTopStart = topStart; - lastIndex = *index; - lastEndIndex = *endIndex; + lastStart = *start; + lastEnd = *end; } } while (!result); return result; } -static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList, - SkOpSegment** currentPtr, int* indexPtr, int* endIndexPtr, double* tHit, +static int rightAngleWinding(const SkTDArray<SkOpContour* >& contourList, + SkOpSegment** currentPtr, SkOpSpanBase** start, SkOpSpanBase** end, double* tHit, SkScalar* hitDx, bool* tryAgain, bool* onlyVertical, bool opp) { double test = 0.9; int contourWinding; do { - contourWinding = contourRangeCheckY(contourList, currentPtr, indexPtr, endIndexPtr, + contourWinding = contourRangeCheckY(contourList, currentPtr, start, end, tHit, hitDx, tryAgain, &test, opp); if (contourWinding != SK_MinS32 || *tryAgain) { return contourWinding; @@ -296,9 +273,9 @@ static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList, return contourWinding; } -static void skipVertical(const SkTArray<SkOpContour*, true>& contourList, - SkOpSegment** current, int* index, int* endIndex) { - if (!(*current)->isVertical(*index, *endIndex)) { +static void skipVertical(const SkTDArray<SkOpContour* >& contourList, + SkOpSegment** current, SkOpSpanBase** start, SkOpSpanBase** end) { + if (!(*current)->isVertical(*start, *end)) { return; } int contourCount = contourList.count(); @@ -307,7 +284,7 @@ static void skipVertical(const SkTArray<SkOpContour*, true>& contourList, if (contour->done()) { continue; } - SkOpSegment* nonVertical = contour->nonVerticalSegment(index, endIndex); + SkOpSegment* nonVertical = contour->nonVerticalSegment(start, end); if (nonVertical) { *current = nonVertical; return; @@ -316,41 +293,41 @@ static void skipVertical(const SkTArray<SkOpContour*, true>& contourList, return; } -struct SortableTop { // error if local in pre-C++11 - SkOpSegment* fSegment; - int fIndex; - int fEndIndex; +struct SortableTop2 { // error if local in pre-C++11 + SkOpSpanBase* fStart; + SkOpSpanBase* fEnd; }; -SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, - SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr, - int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical, - bool firstPass) { - SkOpSegment* current = findTopSegment(contourList, indexPtr, endIndexPtr, topLeft, unsortable, - done, firstPass); +SkOpSegment* FindSortableTop(const SkTDArray<SkOpContour* >& contourList, bool firstPass, + SkOpAngle::IncludeType angleIncludeType, bool* firstContour, SkOpSpanBase** startPtr, + SkOpSpanBase** endPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical, + SkChunkAlloc* allocator) { + SkOpSegment* current = findTopSegment(contourList, firstPass, startPtr, endPtr, topLeft, + unsortable, done, allocator); if (!current) { return NULL; } - const int startIndex = *indexPtr; - const int endIndex = *endIndexPtr; + SkOpSpanBase* start = *startPtr; + SkOpSpanBase* end = *endPtr; + SkASSERT(current == start->segment()); if (*firstContour) { - current->initWinding(startIndex, endIndex, angleIncludeType); + current->initWinding(start, end, angleIncludeType); *firstContour = false; return current; } - int minIndex = SkMin32(startIndex, endIndex); - int sumWinding = current->windSum(minIndex); + SkOpSpan* minSpan = start->starter(end); + int sumWinding = minSpan->windSum(); if (sumWinding == SK_MinS32) { - int index = endIndex; - int oIndex = startIndex; - do { - const SkOpSpan& span = current->span(index); - if ((oIndex < index ? span.fFromAngle : span.fToAngle) == NULL) { - current->addSimpleAngle(index); + SkOpSpanBase* iSpan = end; + SkOpSpanBase* oSpan = start; + do { + bool checkFrom = oSpan->t() < iSpan->t(); + if ((checkFrom ? iSpan->fromAngle() : iSpan->upCast()->toAngle()) == NULL) { + iSpan->addSimpleAngle(checkFrom, allocator); } - sumWinding = current->computeSum(oIndex, index, angleIncludeType); - SkTSwap(index, oIndex); - } while (sumWinding == SK_MinS32 && index == startIndex); + sumWinding = current->computeSum(oSpan, iSpan, angleIncludeType); + SkTSwap(iSpan, oSpan); + } while (sumWinding == SK_MinS32 && iSpan == start); } if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) { return current; @@ -364,26 +341,28 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, SkScalar hitDx = 0; SkScalar hitOppDx = 0; // keep track of subsequent returns to detect infinite loops - SkTDArray<SortableTop> sortableTops; + SkTDArray<SortableTop2> sortableTops; do { // if current is vertical, find another candidate which is not // if only remaining candidates are vertical, then they can be marked done - SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0); - skipVertical(contourList, ¤t, indexPtr, endIndexPtr); + SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr); + SkASSERT(current == (*startPtr)->segment()); + skipVertical(contourList, ¤t, startPtr, endPtr); SkASSERT(current); // FIXME: if null, all remaining are vertical - SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0); + SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr); + SkASSERT(current == (*startPtr)->segment()); tryAgain = false; - contourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit, + contourWinding = rightAngleWinding(contourList, ¤t, startPtr, endPtr, &tHit, &hitDx, &tryAgain, onlyVertical, false); + SkASSERT(current == (*startPtr)->segment()); if (tryAgain) { bool giveUp = false; int count = sortableTops.count(); for (int index = 0; index < count; ++index) { - const SortableTop& prev = sortableTops[index]; + const SortableTop2& prev = sortableTops[index]; if (giveUp) { - prev.fSegment->markDoneFinal(prev.fIndex); - } else if (prev.fSegment == current - && (prev.fIndex == *indexPtr || prev.fEndIndex == *endIndexPtr)) { + prev.fStart->segment()->markDone(prev.fStart->starter(prev.fEnd)); + } else if (prev.fStart == *startPtr || prev.fEnd == *endPtr) { // remaining edges are non-vertical and cannot have their winding computed // mark them as done and return, and hope that assembly can fill the holes giveUp = true; @@ -395,14 +374,13 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, return NULL; } } - SortableTop* sortableTop = sortableTops.append(); - sortableTop->fSegment = current; - sortableTop->fIndex = *indexPtr; - sortableTop->fEndIndex = *endIndexPtr; + SortableTop2* sortableTop = sortableTops.append(); + sortableTop->fStart = *startPtr; + sortableTop->fEnd = *endPtr; #if DEBUG_SORT SkDebugf("%s current=%d index=%d endIndex=%d tHit=%1.9g hitDx=%1.9g try=%d vert=%d\n", - __FUNCTION__, current->debugID(), *indexPtr, *endIndexPtr, tHit, hitDx, tryAgain, - *onlyVertical); + __FUNCTION__, current->debugID(), (*startPtr)->debugID(), (*endPtr)->debugID(), + tHit, hitDx, tryAgain, *onlyVertical); #endif if (*onlyVertical) { return current; @@ -413,127 +391,35 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, if (angleIncludeType < SkOpAngle::kBinarySingle) { break; } - oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit, + oppContourWinding = rightAngleWinding(contourList, ¤t, startPtr, endPtr, &tHit, &hitOppDx, &tryAgain, NULL, true); + SkASSERT(current == (*startPtr)->segment()); } while (tryAgain); - bool success = current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, + bool success = current->initWinding(*startPtr, *endPtr, tHit, contourWinding, hitDx, oppContourWinding, hitOppDx); if (current->done()) { return NULL; } else if (!success) { // check if the span has a valid winding - int min = SkTMin(*indexPtr, *endIndexPtr); - const SkOpSpan& span = current->span(min); - if (span.fWindSum == SK_MinS32) { + SkOpSpan* minSpan = (*startPtr)->t() < (*endPtr)->t() ? (*startPtr)->upCast() + : (*endPtr)->upCast(); + if (minSpan->windSum() == SK_MinS32) { return NULL; } } return current; } -static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; - if (!contour->calcAngles()) { - return false; - } - } - return true; -} - -static void checkDuplicates(SkTArray<SkOpContour*, true>* contourList) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; - contour->checkDuplicates(); - } -} - -static bool checkEnds(SkTArray<SkOpContour*, true>* contourList) { - // it's hard to determine if the end of a cubic or conic nearly intersects another curve. - // instead, look to see if the connecting curve intersected at that same end. - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; - if (!contour->checkEnds()) { - return false; - } - } - return true; -} - -static bool checkMultiples(SkTArray<SkOpContour*, true>* contourList) { - bool hasMultiples = false; - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; - contour->checkMultiples(); - hasMultiples |= contour->hasMultiples(); - } - return hasMultiples; -} - -// A small interval of a pair of curves may collapse to lines for each, triggering coincidence -static void checkSmall(SkTArray<SkOpContour*, true>* contourList) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; - contour->checkSmall(); - } -} - -// A tiny interval may indicate an undiscovered coincidence. Find and fix. -static void checkTiny(SkTArray<SkOpContour*, true>* contourList) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; - contour->checkTiny(); - } -} - -static void fixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; - contour->fixOtherTIndex(); - } -} - -static void joinCoincidence(SkTArray<SkOpContour*, true>* contourList) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; - contour->joinCoincidence(); - } -} - -static void sortAngles(SkTArray<SkOpContour*, true>* contourList) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; - contour->sortAngles(); - } -} - -static void sortSegments(SkTArray<SkOpContour*, true>* contourList) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; - contour->sortSegments(); - } -} - -void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, true>& list, +void MakeContourList(SkOpContour* contour, SkTDArray<SkOpContour* >& list, bool evenOdd, bool oppEvenOdd) { - int count = contours.count(); - if (count == 0) { + do { + if (contour->count()) { + contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd); + *list.append() = contour; + } + } while ((contour = contour->next())); + if (list.count() < 2) { return; } - for (int index = 0; index < count; ++index) { - SkOpContour& contour = contours[index]; - contour.setOppXor(contour.operand() ? evenOdd : oppEvenOdd); - list.push_back(&contour); - } SkTQSort<SkOpContour>(list.begin(), list.end() - 1); } @@ -554,19 +440,22 @@ public: reassemble contour pieces into new path */ void Assemble(const SkPathWriter& path, SkPathWriter* simple) { + SkOpContour contour; + SkOpGlobalState globalState(NULL PATH_OPS_DEBUG_PARAMS(&contour)); #if DEBUG_PATH_CONSTRUCTION SkDebugf("%s\n", __FUNCTION__); #endif - SkTArray<SkOpContour> contours; - SkOpEdgeBuilder builder(path, contours); - builder.finish(); - int count = contours.count(); - int outer; - SkTArray<int, true> runs(count); // indices of partial contours - for (outer = 0; outer < count; ++outer) { - const SkOpContour& eContour = contours[outer]; - const SkPoint& eStart = eContour.start(); - const SkPoint& eEnd = eContour.end(); + SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune + SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState); + builder.finish(&allocator); + SkTDArray<const SkOpContour* > runs; // indices of partial contours + const SkOpContour* eContour = builder.head(); + do { + if (!eContour->count()) { + continue; + } + const SkPoint& eStart = eContour->start(); + const SkPoint& eEnd = eContour->end(); #if DEBUG_ASSEMBLE SkDebugf("%s contour", __FUNCTION__); if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) { @@ -578,44 +467,42 @@ void Assemble(const SkPathWriter& path, SkPathWriter* simple) { eStart.fX, eStart.fY, eEnd.fX, eEnd.fY); #endif if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) { - eContour.toPath(simple); + eContour->toPath(simple); continue; } - runs.push_back(outer); - } - count = runs.count(); + *runs.append() = eContour; + } while ((eContour = eContour->next())); + int count = runs.count(); if (count == 0) { return; } - SkTArray<int, true> sLink, eLink; - sLink.push_back_n(count); - eLink.push_back_n(count); + SkTDArray<int> sLink, eLink; + sLink.append(count); + eLink.append(count); int rIndex, iIndex; for (rIndex = 0; rIndex < count; ++rIndex) { sLink[rIndex] = eLink[rIndex] = SK_MaxS32; } const int ends = count * 2; // all starts and ends const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2 - SkTArray<double, true> distances; - distances.push_back_n(entries); + SkTDArray<double> distances; + distances.append(entries); for (rIndex = 0; rIndex < ends - 1; ++rIndex) { - outer = runs[rIndex >> 1]; - const SkOpContour& oContour = contours[outer]; - const SkPoint& oPt = rIndex & 1 ? oContour.end() : oContour.start(); + const SkOpContour* oContour = runs[rIndex >> 1]; + const SkPoint& oPt = rIndex & 1 ? oContour->end() : oContour->start(); const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2) * ends - rIndex - 1; for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) { - int inner = runs[iIndex >> 1]; - const SkOpContour& iContour = contours[inner]; - const SkPoint& iPt = iIndex & 1 ? iContour.end() : iContour.start(); + const SkOpContour* iContour = runs[iIndex >> 1]; + const SkPoint& iPt = iIndex & 1 ? iContour->end() : iContour->start(); double dx = iPt.fX - oPt.fX; double dy = iPt.fY - oPt.fY; double dist = dx * dx + dy * dy; distances[row + iIndex] = dist; // oStart distance from iStart } } - SkTArray<int, true> sortedDist; - sortedDist.push_back_n(entries); + SkTDArray<int> sortedDist; + sortedDist.append(entries); for (rIndex = 0; rIndex < entries; ++rIndex) { sortedDist[rIndex] = rIndex; } @@ -678,17 +565,16 @@ void Assemble(const SkPathWriter& path, SkPathWriter* simple) { eIndex < 0 ? ~eIndex : eIndex); #endif do { - outer = runs[rIndex]; - const SkOpContour& contour = contours[outer]; + const SkOpContour* contour = runs[rIndex]; if (first) { first = false; - const SkPoint* startPtr = &contour.start(); + const SkPoint* startPtr = &contour->start(); simple->deferredMove(startPtr[0]); } if (forward) { - contour.toPartialForward(simple); + contour->toPartialForward(simple); } else { - contour.toPartialBackward(simple); + contour->toPartialBackward(simple); } #if DEBUG_ASSEMBLE SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex, @@ -742,36 +628,88 @@ void Assemble(const SkPathWriter& path, SkPathWriter* simple) { #endif } -bool HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) { -#if DEBUG_SHOW_WINDING - SkOpContour::debugShowWindingValues(contourList); -#endif - if (!CoincidenceCheck(contourList, total)) { +static void align(SkTDArray<SkOpContour* >* contourList) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + contour->align(); + } +} + +static void calcAngles(SkTDArray<SkOpContour* >* contourList, SkChunkAlloc* allocator) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + contour->calcAngles(allocator); + } +} + +static void missingCoincidence(SkTDArray<SkOpContour* >* contourList, + SkOpCoincidence* coincidence, SkChunkAlloc* allocator) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + contour->missingCoincidence(coincidence, allocator); + } +} + +static bool moveNearby(SkTDArray<SkOpContour* >* contourList) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + if (!contour->moveNearby()) { + return false; + } + } + return true; +} + +static void sortAngles(SkTDArray<SkOpContour* >* contourList) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + contour->sortAngles(); + } +} + +static void sortSegments(SkTDArray<SkOpContour* >* contourList) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + contour->sortSegments(); + } +} + +bool HandleCoincidence(SkTDArray<SkOpContour* >* contourList, SkOpCoincidence* coincidence, + SkChunkAlloc* allocator, SkOpGlobalState* globalState) { + // move t values and points together to eliminate small/tiny gaps + if (!moveNearby(contourList)) { return false; } -#if DEBUG_SHOW_WINDING - SkOpContour::debugShowWindingValues(contourList); + align(contourList); // give all span members common values +#if DEBUG_VALIDATE + globalState->setPhase(SkOpGlobalState::kIntersecting); +#endif + coincidence->addMissing(allocator); +#if DEBUG_VALIDATE + globalState->setPhase(SkOpGlobalState::kWalking); #endif - fixOtherTIndex(contourList); - if (!checkEnds(contourList)) { // check if connecting curve intersected at the same end + coincidence->expand(); // check to see if, loosely, coincident ranges may be expanded + coincidence->mark(); // mark spans of coincident segments as coincident + missingCoincidence(contourList, coincidence, allocator); // look for coincidence missed earlier + if (!coincidence->apply()) { // adjust the winding value to account for coincident edges return false; } - bool hasM = checkMultiples(contourList); // check if intersections agree on t and point values - SkTDArray<SkOpSegment::AlignedSpan> aligned; - if (hasM) { - alignMultiples(contourList, &aligned); // align pairs of identical points - alignCoincidence(contourList, aligned); - } - checkDuplicates(contourList); // check if spans have the same number on the other end - checkTiny(contourList); // if pair have the same end points, mark them as parallel - checkSmall(contourList); // a pair of curves with a small span may turn into coincident lines - joinCoincidence(contourList); // join curves that connect to a coincident pair sortSegments(contourList); - if (!calcAngles(contourList)) { - return false; - } + calcAngles(contourList, allocator); sortAngles(contourList); -#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY + if (globalState->angleCoincidence()) { + missingCoincidence(contourList, coincidence, allocator); + if (!coincidence->apply()) { + return false; + } + } +#if DEBUG_ACTIVE_SPANS DebugShowActiveSpans(*contourList); #endif return true; |