123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382 |
- /*
- * 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 "src/pathops/SkAddIntersections.h"
- #include "src/pathops/SkOpCoincidence.h"
- #include "src/pathops/SkOpEdgeBuilder.h"
- #include "src/pathops/SkPathOpsCommon.h"
- #include "src/pathops/SkPathWriter.h"
- #include <utility>
- static bool findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr,
- SkOpSpanBase** endPtr, SkOpSegment** result) {
- while (chase.count()) {
- SkOpSpanBase* span;
- chase.pop(&span);
- // OPTIMIZE: prev makes this compatible with old code -- but is it necessary?
- *startPtr = span->ptT()->prev()->span();
- SkOpSegment* segment = (*startPtr)->segment();
- 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
- *result = last->segment();
- return true;
- }
- if (done) {
- continue;
- }
- int winding;
- bool sortable;
- const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
- if (!angle) {
- *result = nullptr;
- return true;
- }
- if (winding == SK_MinS32) {
- continue;
- }
- int sumMiWinding, sumSuWinding;
- if (sortable) {
- segment = angle->segment();
- sumMiWinding = segment->updateWindingReverse(angle);
- if (sumMiWinding == SK_MinS32) {
- SkASSERT(segment->globalState()->debugSkipAssert());
- *result = nullptr;
- return true;
- }
- sumSuWinding = segment->updateOppWindingReverse(angle);
- if (sumSuWinding == SK_MinS32) {
- SkASSERT(segment->globalState()->debugSkipAssert());
- *result = nullptr;
- return true;
- }
- if (segment->operand()) {
- using std::swap;
- swap(sumMiWinding, sumSuWinding);
- }
- }
- 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 = 0, sumWinding = 0, oppMaxWinding = 0, oppSumWinding = 0;
- if (sortable) {
- segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
- &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
- }
- 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) {
- if (!segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
- oppSumWinding, angle, nullptr)) {
- return false;
- }
- }
- }
- }
- if (first) {
- #if TRY_ROTATE
- *chase.insert(0) = span;
- #else
- *chase.append() = span;
- #endif
- *result = first;
- return true;
- }
- }
- *result = nullptr;
- return true;
- }
- static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op,
- const int xorMask, const int xorOpMask, SkPathWriter* writer) {
- bool unsortable = false;
- bool lastSimple = false;
- bool simple = false;
- do {
- SkOpSpan* span = FindSortableTop(contourList);
- if (!span) {
- break;
- }
- SkOpSegment* current = span->segment();
- SkOpSpanBase* start = span->next();
- SkOpSpanBase* end = span;
- SkTDArray<SkOpSpanBase*> chase;
- do {
- if (current->activeOp(start, end, xorMask, xorOpMask, op)) {
- do {
- if (!unsortable && current->done()) {
- break;
- }
- SkASSERT(unsortable || !current->done());
- SkOpSpanBase* nextStart = start;
- SkOpSpanBase* nextEnd = end;
- lastSimple = simple;
- SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
- &unsortable, &simple, op, xorMask, xorOpMask);
- if (!next) {
- if (!unsortable && writer->hasMove()
- && current->verb() != SkPath::kLine_Verb
- && !writer->isClosed()) {
- if (!current->addCurveTo(start, end, writer)) {
- return false;
- }
- if (!writer->isClosed()) {
- SkPathOpsDebug::ShowActiveSpans(contourList);
- }
- } else if (lastSimple) {
- if (!current->addCurveTo(start, end, writer)) {
- return false;
- }
- }
- break;
- }
- #if DEBUG_FLOW
- 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
- if (!current->addCurveTo(start, end, writer)) {
- return false;
- }
- current = next;
- start = nextStart;
- end = nextEnd;
- } while (!writer->isClosed() && (!unsortable || !start->starter(end)->done()));
- if (current->activeWinding(start, end) && !writer->isClosed()) {
- SkOpSpan* spanStart = start->starter(end);
- if (!spanStart->done()) {
- if (!current->addCurveTo(start, end, writer)) {
- return false;
- }
- current->markDone(spanStart);
- }
- }
- writer->finishContour();
- } else {
- SkOpSpanBase* last;
- if (!current->markAndChaseDone(start, end, &last)) {
- return false;
- }
- if (last && !last->chased()) {
- last->setChased(true);
- SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
- *chase.append() = last;
- #if DEBUG_WINDING
- SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
- if (!last->final()) {
- SkDebugf(" windSum=%d", last->upCast()->windSum());
- }
- SkDebugf("\n");
- #endif
- }
- }
- if (!findChaseOp(chase, &start, &end, ¤t)) {
- return false;
- }
- SkPathOpsDebug::ShowActiveSpans(contourList);
- if (!current) {
- break;
- }
- } while (true);
- } while (true);
- return true;
- }
- // diagram of why this simplifcation is possible is here:
- // https://skia.org/dev/present/pathops link at bottom of the page
- // https://drive.google.com/file/d/0BwoLUwz9PYkHLWpsaXd0UDdaN00/view?usp=sharing
- static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = {
- // inside minuend outside minuend
- // inside subtrahend outside subtrahend inside subtrahend outside subtrahend
- {{ kDifference_SkPathOp, kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }},
- {{ kIntersect_SkPathOp, kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }},
- {{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp, kIntersect_SkPathOp }},
- {{ kXOR_SkPathOp, kXOR_SkPathOp }, { kXOR_SkPathOp, kXOR_SkPathOp }},
- {{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp, kDifference_SkPathOp }},
- };
- static const bool gOutInverse[kReverseDifference_SkPathOp + 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
- };
- #if DEBUG_T_SECT_LOOP_COUNT
- #include "include/private/SkMutex.h"
- SkOpGlobalState debugWorstState(nullptr, nullptr SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr));
- void ReportPathOpsDebugging() {
- debugWorstState.debugLoopReport();
- }
- extern void (*gVerboseFinalize)();
- #endif
- bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result
- SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
- #if DEBUG_DUMP_VERIFY
- #ifndef SK_DEBUG
- const char* testName = "release";
- #endif
- if (SkPathOpsDebug::gDumpOp) {
- SkPathOpsDebug::DumpOp(one, two, op, testName);
- }
- #endif
- op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
- bool inverseFill = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()];
- SkPath::FillType fillType = inverseFill ? SkPath::kInverseEvenOdd_FillType :
- SkPath::kEvenOdd_FillType;
- SkRect rect1, rect2;
- if (kIntersect_SkPathOp == op && one.isRect(&rect1) && two.isRect(&rect2)) {
- result->reset();
- result->setFillType(fillType);
- if (rect1.intersect(rect2)) {
- result->addRect(rect1);
- }
- return true;
- }
- if (one.isEmpty() || two.isEmpty()) {
- SkPath work;
- switch (op) {
- case kIntersect_SkPathOp:
- break;
- case kUnion_SkPathOp:
- case kXOR_SkPathOp:
- work = one.isEmpty() ? two : one;
- break;
- case kDifference_SkPathOp:
- if (!one.isEmpty()) {
- work = one;
- }
- break;
- case kReverseDifference_SkPathOp:
- if (!two.isEmpty()) {
- work = two;
- }
- break;
- default:
- SkASSERT(0); // unhandled case
- }
- if (inverseFill != work.isInverseFillType()) {
- work.toggleInverseFillType();
- }
- return Simplify(work, result);
- }
- SkSTArenaAlloc<4096> allocator; // FIXME: add a constant expression here, tune
- SkOpContour contour;
- SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
- SkOpGlobalState globalState(contourList, &allocator
- SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
- SkOpCoincidence coincidence(&globalState);
- const SkPath* minuend = &one;
- const SkPath* subtrahend = &two;
- if (op == kReverseDifference_SkPathOp) {
- using std::swap;
- swap(minuend, subtrahend);
- op = kDifference_SkPathOp;
- }
- #if DEBUG_SORT
- SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
- #endif
- // turn path into list of segments
- SkOpEdgeBuilder builder(*minuend, contourList, &globalState);
- if (builder.unparseable()) {
- return false;
- }
- const int xorMask = builder.xorMask();
- builder.addOperand(*subtrahend);
- if (!builder.finish()) {
- return false;
- }
- #if DEBUG_DUMP_SEGMENTS
- contourList->dumpSegments("seg", op);
- #endif
- const int xorOpMask = builder.xorMask();
- if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
- xorOpMask == kEvenOdd_PathOpsMask)) {
- result->reset();
- result->setFillType(fillType);
- return true;
- }
- // find all intersections between segments
- SkOpContour* current = contourList;
- do {
- SkOpContour* next = current;
- while (AddIntersectTs(current, next, &coincidence)
- && (next = next->next()))
- ;
- } while ((current = current->next()));
- #if DEBUG_VALIDATE
- globalState.setPhase(SkOpPhase::kWalking);
- #endif
- bool success = HandleCoincidence(contourList, &coincidence);
- #if DEBUG_COIN
- globalState.debugAddToGlobalCoinDicts();
- #endif
- if (!success) {
- return false;
- }
- #if DEBUG_ALIGNMENT
- contourList->dumpSegments("aligned");
- #endif
- // construct closed contours
- SkPath original = *result;
- result->reset();
- result->setFillType(fillType);
- SkPathWriter wrapper(*result);
- if (!bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper)) {
- *result = original;
- return false;
- }
- wrapper.assemble(); // if some edges could not be resolved, assemble remaining
- #if DEBUG_T_SECT_LOOP_COUNT
- static SkMutex& debugWorstLoop = *(new SkMutex);
- {
- SkAutoMutexExclusive autoM(debugWorstLoop);
- if (!gVerboseFinalize) {
- gVerboseFinalize = &ReportPathOpsDebugging;
- }
- debugWorstState.debugDoYourWorst(&globalState);
- }
- #endif
- return true;
- }
- bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
- #if DEBUG_DUMP_VERIFY
- if (SkPathOpsDebug::gVerifyOp) {
- if (!OpDebug(one, two, op, result SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) {
- SkPathOpsDebug::ReportOpFail(one, two, op);
- return false;
- }
- SkPathOpsDebug::VerifyOp(one, two, op, *result);
- return true;
- }
- #endif
- return OpDebug(one, two, op, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr));
- }
|