| /* | |
| * Copyright 2012 Google Inc. | |
| * | |
| * Use of this source code is governed by a BSD-style license that can be | |
| * found in the LICENSE file. | |
| */ | |
| #include "SkAddIntersections.h" | |
| #include "SkOpCoincidence.h" | |
| #include "SkOpEdgeBuilder.h" | |
| #include "SkPathOpsCommon.h" | |
| #include "SkPathWriter.h" | |
| #include "SkTSort.h" | |
| SkScalar ScaleFactor(const SkPath& path) { | |
| static const SkScalar twoTo10 = 1024.f; | |
| SkScalar largest = 0; | |
| const SkScalar* oneBounds = &path.getBounds().fLeft; | |
| for (int index = 0; index < 4; ++index) { | |
| largest = SkTMax(largest, SkScalarAbs(oneBounds[index])); | |
| } | |
| SkScalar scale = twoTo10; | |
| SkScalar next; | |
| while ((next = scale * twoTo10) < largest) { | |
| scale = next; | |
| } | |
| return scale == twoTo10 ? SK_Scalar1 : scale; | |
| } | |
| void ScalePath(const SkPath& path, SkScalar scale, SkPath* scaled) { | |
| SkMatrix matrix; | |
| matrix.setScale(scale, scale); | |
| *scaled = path; | |
| scaled->transform(matrix); | |
| } | |
| const SkOpAngle* AngleWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* windingPtr, | |
| bool* sortablePtr) { | |
| // find first angle, initialize winding to computed fWindSum | |
| SkOpSegment* segment = start->segment(); | |
| const SkOpAngle* angle = segment->spanToAngle(start, end); | |
| if (!angle) { | |
| *windingPtr = SK_MinS32; | |
| return nullptr; | |
| } | |
| bool computeWinding = false; | |
| const SkOpAngle* firstAngle = angle; | |
| bool loop = false; | |
| bool unorderable = false; | |
| int winding = SK_MinS32; | |
| do { | |
| angle = angle->next(); | |
| if (!angle) { | |
| return nullptr; | |
| } | |
| unorderable |= angle->unorderable(); | |
| if ((computeWinding = unorderable || (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); | |
| // if the angle loop contains an unorderable span, the angle order may be useless | |
| // directly compute the winding in this case for each span | |
| if (computeWinding) { | |
| firstAngle = angle; | |
| winding = SK_MinS32; | |
| do { | |
| SkOpSpanBase* startSpan = angle->start(); | |
| SkOpSpanBase* endSpan = angle->end(); | |
| SkOpSpan* lesser = startSpan->starter(endSpan); | |
| int testWinding = lesser->windSum(); | |
| if (testWinding == SK_MinS32) { | |
| testWinding = lesser->computeWindSum(); | |
| } | |
| if (testWinding != SK_MinS32) { | |
| segment = angle->segment(); | |
| winding = testWinding; | |
| } | |
| angle = angle->next(); | |
| } while (angle != firstAngle); | |
| } | |
| *sortablePtr = !unorderable; | |
| *windingPtr = winding; | |
| return angle; | |
| } | |
| SkOpSegment* FindUndone(SkOpContourHead* contourList, SkOpSpanBase** startPtr, | |
| SkOpSpanBase** endPtr) { | |
| SkOpSegment* result; | |
| SkOpContour* contour = contourList; | |
| do { | |
| result = contour->undoneSegment(startPtr, endPtr); | |
| if (result) { | |
| return result; | |
| } | |
| } while ((contour = contour->next())); | |
| return nullptr; | |
| } | |
| SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr, | |
| SkOpSpanBase** endPtr) { | |
| while (chase->count()) { | |
| SkOpSpanBase* span; | |
| chase->pop(&span); | |
| SkOpSegment* segment = span->segment(); | |
| *startPtr = span->ptT()->next()->span(); | |
| bool done = true; | |
| *endPtr = nullptr; | |
| if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) { | |
| *startPtr = last->start(); | |
| *endPtr = last->end(); | |
| #if TRY_ROTATE | |
| *chase->insert(0) = span; | |
| #else | |
| *chase->append() = span; | |
| #endif | |
| return last->segment(); | |
| } | |
| if (done) { | |
| continue; | |
| } | |
| // find first angle, initialize winding to computed wind sum | |
| int winding; | |
| bool sortable; | |
| const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable); | |
| if (!angle) { | |
| return nullptr; | |
| } | |
| if (winding == SK_MinS32) { | |
| continue; | |
| } | |
| int sumWinding SK_INIT_TO_AVOID_WARNING; | |
| if (sortable) { | |
| segment = angle->segment(); | |
| sumWinding = segment->updateWindingReverse(angle); | |
| } | |
| SkOpSegment* first = nullptr; | |
| const SkOpAngle* firstAngle = angle; | |
| while ((angle = angle->next()) != firstAngle) { | |
| segment = angle->segment(); | |
| SkOpSpanBase* start = angle->start(); | |
| SkOpSpanBase* end = angle->end(); | |
| int maxWinding SK_INIT_TO_AVOID_WARNING; | |
| if (sortable) { | |
| segment->setUpWinding(start, end, &maxWinding, &sumWinding); | |
| } | |
| if (!segment->done(angle)) { | |
| if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) { | |
| first = segment; | |
| *startPtr = start; | |
| *endPtr = end; | |
| } | |
| // OPTIMIZATION: should this also add to the chase? | |
| if (sortable) { | |
| (void) segment->markAngle(maxWinding, sumWinding, angle); | |
| } | |
| } | |
| } | |
| if (first) { | |
| #if TRY_ROTATE | |
| *chase->insert(0) = span; | |
| #else | |
| *chase->append() = span; | |
| #endif | |
| return first; | |
| } | |
| } | |
| return nullptr; | |
| } | |
| bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) { | |
| SkTDArray<SkOpContour* > list; | |
| SkOpContour* contour = *contourList; | |
| do { | |
| if (contour->count()) { | |
| contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd); | |
| *list.append() = contour; | |
| } | |
| } while ((contour = contour->next())); | |
| int count = list.count(); | |
| if (!count) { | |
| return false; | |
| } | |
| if (count > 1) { | |
| SkTQSort<SkOpContour>(list.begin(), list.end() - 1); | |
| } | |
| contour = list[0]; | |
| SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour); | |
| contour->globalState()->setContourHead(contourHead); | |
| *contourList = contourHead; | |
| for (int index = 1; index < count; ++index) { | |
| SkOpContour* next = list[index]; | |
| contour->setNext(next); | |
| contour = next; | |
| } | |
| contour->setNext(nullptr); | |
| return true; | |
| } | |
| class DistanceLessThan { | |
| public: | |
| DistanceLessThan(double* distances) : fDistances(distances) { } | |
| double* fDistances; | |
| bool operator()(const int one, const int two) { | |
| return fDistances[one] < fDistances[two]; | |
| } | |
| }; | |
| /* | |
| check start and end of each contour | |
| if not the same, record them | |
| match them up | |
| connect closest | |
| reassemble contour pieces into new path | |
| */ | |
| void Assemble(const SkPathWriter& path, SkPathWriter* simple) { | |
| SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune | |
| SkOpContourHead contour; | |
| SkOpGlobalState globalState(&contour, &allocator SkDEBUGPARAMS(false) | |
| SkDEBUGPARAMS(nullptr)); | |
| #if DEBUG_SHOW_TEST_NAME | |
| SkDebugf("</div>\n"); | |
| #endif | |
| #if DEBUG_PATH_CONSTRUCTION | |
| SkDebugf("%s\n", __FUNCTION__); | |
| #endif | |
| SkOpEdgeBuilder builder(path, &contour, &globalState); | |
| builder.finish(); | |
| 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)) { | |
| SkDebugf("[%d]", runs.count()); | |
| } else { | |
| SkDebugf(" "); | |
| } | |
| SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", | |
| eStart.fX, eStart.fY, eEnd.fX, eEnd.fY); | |
| #endif | |
| if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) { | |
| eContour->toPath(simple); | |
| continue; | |
| } | |
| *runs.append() = eContour; | |
| } while ((eContour = eContour->next())); | |
| int count = runs.count(); | |
| if (count == 0) { | |
| return; | |
| } | |
| 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 | |
| SkTDArray<double> distances; | |
| distances.append(entries); | |
| for (rIndex = 0; rIndex < ends - 1; ++rIndex) { | |
| 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) { | |
| 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 | |
| } | |
| } | |
| SkTDArray<int> sortedDist; | |
| sortedDist.append(entries); | |
| for (rIndex = 0; rIndex < entries; ++rIndex) { | |
| sortedDist[rIndex] = rIndex; | |
| } | |
| SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin())); | |
| int remaining = count; // number of start/end pairs | |
| for (rIndex = 0; rIndex < entries; ++rIndex) { | |
| int pair = sortedDist[rIndex]; | |
| int row = pair / ends; | |
| int col = pair - row * ends; | |
| int thingOne = row < col ? row : ends - row - 2; | |
| int ndxOne = thingOne >> 1; | |
| bool endOne = thingOne & 1; | |
| int* linkOne = endOne ? eLink.begin() : sLink.begin(); | |
| if (linkOne[ndxOne] != SK_MaxS32) { | |
| continue; | |
| } | |
| int thingTwo = row < col ? col : ends - row + col - 1; | |
| int ndxTwo = thingTwo >> 1; | |
| bool endTwo = thingTwo & 1; | |
| int* linkTwo = endTwo ? eLink.begin() : sLink.begin(); | |
| if (linkTwo[ndxTwo] != SK_MaxS32) { | |
| continue; | |
| } | |
| SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]); | |
| bool flip = endOne == endTwo; | |
| linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo; | |
| linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne; | |
| if (!--remaining) { | |
| break; | |
| } | |
| } | |
| SkASSERT(!remaining); | |
| #if DEBUG_ASSEMBLE | |
| for (rIndex = 0; rIndex < count; ++rIndex) { | |
| int s = sLink[rIndex]; | |
| int e = eLink[rIndex]; | |
| SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e', | |
| s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e); | |
| } | |
| #endif | |
| rIndex = 0; | |
| do { | |
| bool forward = true; | |
| bool first = true; | |
| int sIndex = sLink[rIndex]; | |
| SkASSERT(sIndex != SK_MaxS32); | |
| sLink[rIndex] = SK_MaxS32; | |
| int eIndex; | |
| if (sIndex < 0) { | |
| eIndex = sLink[~sIndex]; | |
| sLink[~sIndex] = SK_MaxS32; | |
| } else { | |
| eIndex = eLink[sIndex]; | |
| eLink[sIndex] = SK_MaxS32; | |
| } | |
| SkASSERT(eIndex != SK_MaxS32); | |
| #if DEBUG_ASSEMBLE | |
| SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e', | |
| sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e', | |
| eIndex < 0 ? ~eIndex : eIndex); | |
| #endif | |
| do { | |
| const SkOpContour* contour = runs[rIndex]; | |
| if (first) { | |
| first = false; | |
| const SkPoint* startPtr = &contour->start(); | |
| simple->deferredMove(startPtr[0]); | |
| } | |
| if (forward) { | |
| contour->toPartialForward(simple); | |
| } else { | |
| contour->toPartialBackward(simple); | |
| } | |
| #if DEBUG_ASSEMBLE | |
| SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex, | |
| eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex, | |
| sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)); | |
| #endif | |
| if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) { | |
| simple->close(); | |
| break; | |
| } | |
| if (forward) { | |
| eIndex = eLink[rIndex]; | |
| SkASSERT(eIndex != SK_MaxS32); | |
| eLink[rIndex] = SK_MaxS32; | |
| if (eIndex >= 0) { | |
| SkASSERT(sLink[eIndex] == rIndex); | |
| sLink[eIndex] = SK_MaxS32; | |
| } else { | |
| SkASSERT(eLink[~eIndex] == ~rIndex); | |
| eLink[~eIndex] = SK_MaxS32; | |
| } | |
| } else { | |
| eIndex = sLink[rIndex]; | |
| SkASSERT(eIndex != SK_MaxS32); | |
| sLink[rIndex] = SK_MaxS32; | |
| if (eIndex >= 0) { | |
| SkASSERT(eLink[eIndex] == rIndex); | |
| eLink[eIndex] = SK_MaxS32; | |
| } else { | |
| SkASSERT(sLink[~eIndex] == ~rIndex); | |
| sLink[~eIndex] = SK_MaxS32; | |
| } | |
| } | |
| rIndex = eIndex; | |
| if (rIndex < 0) { | |
| forward ^= 1; | |
| rIndex = ~rIndex; | |
| } | |
| } while (true); | |
| for (rIndex = 0; rIndex < count; ++rIndex) { | |
| if (sLink[rIndex] != SK_MaxS32) { | |
| break; | |
| } | |
| } | |
| } while (rIndex < count); | |
| #if DEBUG_ASSEMBLE | |
| for (rIndex = 0; rIndex < count; ++rIndex) { | |
| SkASSERT(sLink[rIndex] == SK_MaxS32); | |
| SkASSERT(eLink[rIndex] == SK_MaxS32); | |
| } | |
| #endif | |
| } | |
| static void calcAngles(SkOpContourHead* contourList) { | |
| SkOpContour* contour = contourList; | |
| do { | |
| contour->calcAngles(); | |
| } while ((contour = contour->next())); | |
| } | |
| static bool missingCoincidence(SkOpContourHead* contourList) { | |
| SkOpContour* contour = contourList; | |
| bool result = false; | |
| do { | |
| result |= contour->missingCoincidence(); | |
| } while ((contour = contour->next())); | |
| return result; | |
| } | |
| static bool moveMultiples(SkOpContourHead* contourList) { | |
| SkOpContour* contour = contourList; | |
| do { | |
| if (!contour->moveMultiples()) { | |
| return false; | |
| } | |
| } while ((contour = contour->next())); | |
| return true; | |
| } | |
| static void moveNearby(SkOpContourHead* contourList) { | |
| SkOpContour* contour = contourList; | |
| do { | |
| contour->moveNearby(); | |
| } while ((contour = contour->next())); | |
| } | |
| static void sortAngles(SkOpContourHead* contourList) { | |
| SkOpContour* contour = contourList; | |
| do { | |
| contour->sortAngles(); | |
| } while ((contour = contour->next())); | |
| } | |
| bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence) { | |
| SkOpGlobalState* globalState = contourList->globalState(); | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "start"); | |
| #if DEBUG_VALIDATE | |
| globalState->setPhase(SkOpGlobalState::kIntersecting); | |
| #endif | |
| // match up points within the coincident runs | |
| if (!coincidence->addExpanded()) { | |
| return false; | |
| } | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded"); | |
| #if DEBUG_VALIDATE | |
| globalState->setPhase(SkOpGlobalState::kWalking); | |
| #endif | |
| // combine t values when multiple intersections occur on some segments but not others | |
| if (!moveMultiples(contourList)) { | |
| return false; | |
| } | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "moveMultiples"); | |
| // move t values and points together to eliminate small/tiny gaps | |
| (void) moveNearby(contourList); | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby"); | |
| #if DEBUG_VALIDATE | |
| globalState->setPhase(SkOpGlobalState::kIntersecting); | |
| #endif | |
| // add coincidence formed by pairing on curve points and endpoints | |
| coincidence->correctEnds(); | |
| if (!coincidence->addEndMovedSpans()) { | |
| return false; | |
| } | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "addEndMovedSpans"); | |
| const int SAFETY_COUNT = 100; // FIXME: tune | |
| int safetyHatch = SAFETY_COUNT; | |
| // look for coincidence present in A-B and A-C but missing in B-C | |
| while (coincidence->addMissing()) { | |
| if (!--safetyHatch) { | |
| SkASSERT(globalState->debugSkipAssert()); | |
| return false; | |
| } | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing"); | |
| moveNearby(contourList); | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby"); | |
| } | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing2"); | |
| // FIXME: only call this if addMissing modified something when returning false | |
| moveNearby(contourList); | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby2"); | |
| // check to see if, loosely, coincident ranges may be expanded | |
| if (coincidence->expand()) { | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "expand1"); | |
| coincidence->addMissing(); | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing2"); | |
| if (!coincidence->addExpanded()) { | |
| return false; | |
| } | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded2"); | |
| if (!moveMultiples(contourList)) { | |
| return false; | |
| } | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "moveMultiples2"); | |
| moveNearby(contourList); | |
| } | |
| #if DEBUG_VALIDATE | |
| globalState->setPhase(SkOpGlobalState::kWalking); | |
| #endif | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "expand2"); | |
| // the expanded ranges may not align -- add the missing spans | |
| if (!coincidence->addExpanded()) { | |
| return false; | |
| } | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded3"); | |
| coincidence->correctEnds(); | |
| if (!coincidence->mark()) { // mark spans of coincident segments as coincident | |
| return false; | |
| } | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "mark1"); | |
| // look for coincidence lines and curves undetected by intersection | |
| if (missingCoincidence(contourList)) { | |
| #if DEBUG_VALIDATE | |
| globalState->setPhase(SkOpGlobalState::kIntersecting); | |
| #endif | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence1"); | |
| (void) coincidence->expand(); | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "expand3"); | |
| if (!coincidence->addExpanded()) { | |
| return false; | |
| } | |
| #if DEBUG_VALIDATE | |
| globalState->setPhase(SkOpGlobalState::kWalking); | |
| #endif | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded3"); | |
| if (!coincidence->mark()) { | |
| return false; | |
| } | |
| } else { | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence2"); | |
| (void) coincidence->expand(); | |
| } | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence3"); | |
| (void) coincidence->expand(); | |
| #if 0 // under development | |
| // coincident runs may cross two or more spans, but the opposite spans may be out of order | |
| if (!coincidence->reorder()) { | |
| return false; | |
| } | |
| #endif | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "coincidence.reorder"); | |
| SkOpCoincidence overlaps(globalState); | |
| do { | |
| SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps; | |
| if (!pairs->apply()) { // adjust the winding value to account for coincident edges | |
| return false; | |
| } | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->apply"); | |
| // For each coincident pair that overlaps another, when the receivers (the 1st of the pair) | |
| // are different, construct a new pair to resolve their mutual span | |
| if (!pairs->findOverlaps(&overlaps)) { | |
| return false; | |
| } | |
| DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->findOverlaps"); | |
| } while (!overlaps.isEmpty()); | |
| calcAngles(contourList); | |
| sortAngles(contourList); | |
| if (globalState->angleCoincidence()) { | |
| (void) missingCoincidence(contourList); | |
| if (!coincidence->apply()) { | |
| return false; | |
| } | |
| } | |
| #if DEBUG_COINCIDENCE_VERBOSE | |
| coincidence->debugShowCoincidence(); | |
| #endif | |
| #if DEBUG_COINCIDENCE | |
| coincidence->debugValidate(); | |
| #endif | |
| SkPathOpsDebug::ShowActiveSpans(contourList); | |
| return true; | |
| } |