/* * 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* 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 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(list.begin(), list.end() - 1); } contour = list[0]; SkOpContourHead* contourHead = static_cast(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("\n"); #endif #if DEBUG_PATH_CONSTRUCTION SkDebugf("%s\n", __FUNCTION__); #endif SkOpEdgeBuilder builder(path, &contour, &globalState); builder.finish(); SkTDArray 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 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 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 sortedDist; sortedDist.append(entries); for (rIndex = 0; rIndex < entries; ++rIndex) { sortedDist[rIndex] = rIndex; } SkTQSort(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; }