| /* | |
| * 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 "SkOpEdgeBuilder.h" | |
| #include "SkPathOpsCommon.h" | |
| #include "SkPathWriter.h" | |
| static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* endIndex) { | |
| while (chase.count()) { | |
| SkOpSpan* span; | |
| chase.pop(&span); | |
| const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex); | |
| SkOpSegment* segment = backPtr.fOther; | |
| *tIndex = backPtr.fOtherIndex; | |
| bool sortable = true; | |
| bool done = true; | |
| *endIndex = -1; | |
| if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done, | |
| &sortable)) { | |
| if (last->unorderable()) { | |
| continue; | |
| } | |
| *tIndex = last->start(); | |
| *endIndex = last->end(); | |
| #if TRY_ROTATE | |
| *chase.insert(0) = span; | |
| #else | |
| *chase.append() = span; | |
| #endif | |
| return last->segment(); | |
| } | |
| if (done) { | |
| continue; | |
| } | |
| if (!sortable) { | |
| continue; | |
| } | |
| // find first angle, initialize winding to computed fWindSum | |
| const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex); | |
| if (!angle) { | |
| continue; | |
| } | |
| const SkOpAngle* firstAngle = angle; | |
| SkDEBUGCODE(bool loop = false); | |
| int winding; | |
| do { | |
| angle = angle->next(); | |
| SkASSERT(angle != firstAngle || !loop); | |
| SkDEBUGCODE(loop |= angle == firstAngle); | |
| segment = angle->segment(); | |
| winding = segment->windSum(angle); | |
| } while (winding == SK_MinS32); | |
| int sumMiWinding = segment->updateWindingReverse(angle); | |
| int sumSuWinding = segment->updateOppWindingReverse(angle); | |
| if (segment->operand()) { | |
| SkTSwap<int>(sumMiWinding, sumSuWinding); | |
| } | |
| SkOpSegment* first = NULL; | |
| while ((angle = angle->next()) != firstAngle) { | |
| segment = angle->segment(); | |
| int start = angle->start(); | |
| int 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; | |
| } | |
| // OPTIMIZATION: should this also add to the chase? | |
| (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding, | |
| oppSumWinding, angle); | |
| } | |
| } | |
| if (first) { | |
| #if TRY_ROTATE | |
| *chase.insert(0) = span; | |
| #else | |
| *chase.append() = span; | |
| #endif | |
| return first; | |
| } | |
| } | |
| 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) { | |
| bool firstContour = true; | |
| bool unsortable = false; | |
| bool topUnsortable = false; | |
| bool firstPass = true; | |
| SkPoint lastTopLeft; | |
| SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin}; | |
| do { | |
| int index, endIndex; | |
| bool topDone; | |
| bool onlyVertical = false; | |
| lastTopLeft = topLeft; | |
| SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour, | |
| &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass); | |
| if (!current) { | |
| if ((!topUnsortable || firstPass) && !topDone) { | |
| SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin); | |
| if (lastTopLeft.fX == SK_ScalarMin && lastTopLeft.fY == SK_ScalarMin) { | |
| if (firstPass) { | |
| firstPass = false; | |
| } else { | |
| break; | |
| } | |
| } | |
| topLeft.fX = topLeft.fY = SK_ScalarMin; | |
| continue; | |
| } | |
| break; | |
| } else if (onlyVertical) { | |
| break; | |
| } | |
| firstPass = !topUnsortable || lastTopLeft != topLeft; | |
| SkTDArray<SkOpSpan*> chase; | |
| do { | |
| if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) { | |
| do { | |
| if (!unsortable && current->done()) { | |
| break; | |
| } | |
| SkASSERT(unsortable || !current->done()); | |
| int nextStart = index; | |
| int nextEnd = endIndex; | |
| 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); | |
| #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); | |
| #endif | |
| current->addCurveTo(index, endIndex, 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); | |
| } | |
| } | |
| simple->close(); | |
| } else { | |
| SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex); | |
| if (last && !last->fChased && !last->fLoop) { | |
| last->fChased = 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); | |
| #endif | |
| } | |
| } | |
| current = findChaseOp(chase, &index, &endIndex); | |
| #if DEBUG_ACTIVE_SPANS | |
| DebugShowActiveSpans(contourList); | |
| #endif | |
| if (!current) { | |
| break; | |
| } | |
| } while (true); | |
| } while (true); | |
| return simple->someAssemblyRequired(); | |
| } | |
| // 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] = { | |
| // 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 }}, | |
| }; | |
| static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = { | |
| {{ false, false }, { true, false }}, // diff | |
| {{ false, false }, { false, true }}, // sect | |
| {{ false, true }, { true, true }}, // union | |
| {{ false, true }, { true, false }}, // xor | |
| {{ false, true }, { false, false }}, // rev diff | |
| }; | |
| bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { | |
| #if DEBUG_SHOW_TEST_NAME | |
| char* debugName = DEBUG_FILENAME_STRING; | |
| if (debugName && debugName[0]) { | |
| SkPathOpsDebug::BumpTestName(debugName); | |
| SkPathOpsDebug::ShowPath(one, two, op, debugName); | |
| } | |
| #endif | |
| op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()]; | |
| SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()] | |
| ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType; | |
| const SkPath* minuend = &one; | |
| const SkPath* subtrahend = &two; | |
| if (op == kReverseDifference_PathOp) { | |
| minuend = &two; | |
| subtrahend = &one; | |
| op = kDifference_PathOp; | |
| } | |
| #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); | |
| const int xorMask = builder.xorMask(); | |
| builder.addOperand(*subtrahend); | |
| if (!builder.finish()) { | |
| return false; | |
| } | |
| result->reset(); | |
| result->setFillType(fillType); | |
| const int xorOpMask = builder.xorMask(); | |
| SkTArray<SkOpContour*, true> contourList; | |
| MakeContourList(contours, contourList, xorMask == kEvenOdd_PathOpsMask, | |
| xorOpMask == kEvenOdd_PathOpsMask); | |
| SkOpContour** currentPtr = contourList.begin(); | |
| if (!currentPtr) { | |
| 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 (currentPtr != listEnd); | |
| // 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)) { | |
| return false; | |
| } | |
| // construct closed contours | |
| SkPathWriter wrapper(*result); | |
| bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper); | |
| { // if some edges could not be resolved, assemble remaining fragments | |
| SkPath temp; | |
| temp.setFillType(fillType); | |
| SkPathWriter assembled(temp); | |
| Assemble(wrapper, &assembled); | |
| *result = *assembled.nativePath(); | |
| result->setFillType(fillType); | |
| } | |
| return true; | |
| } |