| /* | |
| * 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" | |
| static SkOpSegment* findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr, | |
| SkOpSpanBase** endPtr) { | |
| 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 | |
| return last->segment(); | |
| } | |
| if (done) { | |
| continue; | |
| } | |
| int winding; | |
| bool sortable; | |
| const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable); | |
| if (!angle) { | |
| return nullptr; | |
| } | |
| 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()); | |
| return nullptr; | |
| } | |
| sumSuWinding = segment->updateOppWindingReverse(angle); | |
| if (sumSuWinding == SK_MinS32) { | |
| SkASSERT(segment->globalState()->debugSkipAssert()); | |
| return nullptr; | |
| } | |
| if (segment->operand()) { | |
| SkTSwap<int>(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, sumWinding, oppMaxWinding, oppSumWinding; | |
| 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) { | |
| (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 nullptr; | |
| } | |
| static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op, | |
| const int xorMask, const int xorOpMask, SkPathWriter* simple) { | |
| bool unsortable = 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; | |
| SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd, | |
| &unsortable, op, xorMask, xorOpMask); | |
| if (!next) { | |
| if (!unsortable && simple->hasMove() | |
| && current->verb() != SkPath::kLine_Verb | |
| && !simple->isClosed()) { | |
| if (!current->addCurveTo(start, end, simple)) { | |
| return false; | |
| } | |
| if (!simple->isClosed()) { | |
| SkPathOpsDebug::ShowActiveSpans(contourList); | |
| } | |
| } | |
| 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, simple)) { | |
| return false; | |
| } | |
| current = next; | |
| start = nextStart; | |
| end = nextEnd; | |
| } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done())); | |
| if (current->activeWinding(start, end) && !simple->isClosed()) { | |
| SkOpSpan* spanStart = start->starter(end); | |
| if (!spanStart->done()) { | |
| if (!current->addCurveTo(start, end, simple)) { | |
| return false; | |
| } | |
| current->markDone(spanStart); | |
| } | |
| } | |
| simple->close(); | |
| } else { | |
| SkOpSpanBase* last = current->markAndChaseDone(start, end); | |
| 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 | |
| } | |
| } | |
| current = findChaseOp(chase, &start, &end); | |
| SkPathOpsDebug::ShowActiveSpans(contourList); | |
| 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_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 | |
| }; | |
| #define DEBUGGING_PATHOPS_FROM_HOST 0 // enable to debug svg in chrome -- note path hardcoded below | |
| #if DEBUGGING_PATHOPS_FROM_HOST | |
| #include "SkData.h" | |
| #include "SkStream.h" | |
| static void dump_path(FILE* file, const SkPath& path, bool force, bool dumpAsHex) { | |
| SkDynamicMemoryWStream wStream; | |
| path.dump(&wStream, force, dumpAsHex); | |
| sk_sp<SkData> data(wStream.copyToData()); | |
| fprintf(file, "%.*s\n", (int) data->size(), data->data()); | |
| } | |
| static int dumpID = 0; | |
| static void dump_op(const SkPath& one, const SkPath& two, SkPathOp op) { | |
| #if SK_BUILD_FOR_MAC | |
| FILE* file = fopen("/Users/caryclark/Documents/svgop.txt", "w"); | |
| #else | |
| FILE* file = fopen("/usr/local/google/home/caryclark/Documents/svgop.txt", "w"); | |
| #endif | |
| fprintf(file, | |
| "\nstatic void fuzz763_%d(skiatest::Reporter* reporter, const char* filename) {\n", | |
| ++dumpID); | |
| fprintf(file, " SkPath path;\n"); | |
| fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", one.getFillType()); | |
| dump_path(file, one, false, true); | |
| fprintf(file, " SkPath path1(path);\n"); | |
| fprintf(file, " path.reset();\n"); | |
| fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", two.getFillType()); | |
| dump_path(file, two, false, true); | |
| fprintf(file, " SkPath path2(path);\n"); | |
| fprintf(file, " testPathOp(reporter, path1, path2, (SkPathOp) %d, filename);\n", op); | |
| fprintf(file, "}\n"); | |
| fclose(file); | |
| } | |
| #endif | |
| #if DEBUG_T_SECT_LOOP_COUNT | |
| #include "SkMutex.h" | |
| SK_DECLARE_STATIC_MUTEX(debugWorstLoop); | |
| 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)) { | |
| SkChunkAlloc allocator(4096); // 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); | |
| #if DEBUGGING_PATHOPS_FROM_HOST | |
| dump_op(one, two, op); | |
| #endif | |
| op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()]; | |
| SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()] | |
| ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType; | |
| SkScalar scaleFactor = SkTMax(ScaleFactor(one), ScaleFactor(two)); | |
| SkPath scaledOne, scaledTwo; | |
| const SkPath* minuend, * subtrahend; | |
| if (scaleFactor > SK_Scalar1) { | |
| ScalePath(one, 1.f / scaleFactor, &scaledOne); | |
| minuend = &scaledOne; | |
| ScalePath(two, 1.f / scaleFactor, &scaledTwo); | |
| subtrahend = &scaledTwo; | |
| } else { | |
| minuend = &one; | |
| subtrahend = &two; | |
| } | |
| if (op == kReverseDifference_SkPathOp) { | |
| SkTSwap(minuend, subtrahend); | |
| op = kDifference_SkPathOp; | |
| } | |
| #if DEBUG_SORT | |
| SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; | |
| #endif | |
| // turn path into list of segments | |
| SkOpEdgeBuilder builder(*minuend, &contour, &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(SkOpGlobalState::kWalking); | |
| #endif | |
| if (!HandleCoincidence(contourList, &coincidence)) { | |
| return false; | |
| } | |
| #if DEBUG_ALIGNMENT | |
| contourList->dumpSegments("aligned"); | |
| #endif | |
| // construct closed contours | |
| result->reset(); | |
| result->setFillType(fillType); | |
| 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); | |
| } | |
| #if DEBUG_T_SECT_LOOP_COUNT | |
| { | |
| SkAutoMutexAcquire autoM(debugWorstLoop); | |
| if (!gVerboseFinalize) { | |
| gVerboseFinalize = &ReportPathOpsDebugging; | |
| } | |
| debugWorstState.debugDoYourWorst(&globalState); | |
| } | |
| #endif | |
| if (scaleFactor > 1) { | |
| ScalePath(*result, scaleFactor, result); | |
| } | |
| return true; | |
| } | |
| #define DEBUG_VERIFY 0 | |
| #if DEBUG_VERIFY | |
| #include "SkBitmap.h" | |
| #include "SkCanvas.h" | |
| #include "SkPaint.h" | |
| const int bitWidth = 64; | |
| const int bitHeight = 64; | |
| static void debug_scale_matrix(const SkPath& one, const SkPath& two, SkMatrix& scale) { | |
| SkRect larger = one.getBounds(); | |
| larger.join(two.getBounds()); | |
| SkScalar largerWidth = larger.width(); | |
| if (largerWidth < 4) { | |
| largerWidth = 4; | |
| } | |
| SkScalar largerHeight = larger.height(); | |
| if (largerHeight < 4) { | |
| largerHeight = 4; | |
| } | |
| SkScalar hScale = (bitWidth - 2) / largerWidth; | |
| SkScalar vScale = (bitHeight - 2) / largerHeight; | |
| scale.reset(); | |
| scale.preScale(hScale, vScale); | |
| larger.fLeft *= hScale; | |
| larger.fRight *= hScale; | |
| larger.fTop *= vScale; | |
| larger.fBottom *= vScale; | |
| SkScalar dx = -16000 > larger.fLeft ? -16000 - larger.fLeft | |
| : 16000 < larger.fRight ? 16000 - larger.fRight : 0; | |
| SkScalar dy = -16000 > larger.fTop ? -16000 - larger.fTop | |
| : 16000 < larger.fBottom ? 16000 - larger.fBottom : 0; | |
| scale.preTranslate(dx, dy); | |
| } | |
| static int debug_paths_draw_the_same(const SkPath& one, const SkPath& two, SkBitmap& bits) { | |
| if (bits.width() == 0) { | |
| bits.allocN32Pixels(bitWidth * 2, bitHeight); | |
| } | |
| SkCanvas canvas(bits); | |
| canvas.drawColor(SK_ColorWHITE); | |
| SkPaint paint; | |
| canvas.save(); | |
| const SkRect& bounds1 = one.getBounds(); | |
| canvas.translate(-bounds1.fLeft + 1, -bounds1.fTop + 1); | |
| canvas.drawPath(one, paint); | |
| canvas.restore(); | |
| canvas.save(); | |
| canvas.translate(-bounds1.fLeft + 1 + bitWidth, -bounds1.fTop + 1); | |
| canvas.drawPath(two, paint); | |
| canvas.restore(); | |
| int errors = 0; | |
| for (int y = 0; y < bitHeight - 1; ++y) { | |
| uint32_t* addr1 = bits.getAddr32(0, y); | |
| uint32_t* addr2 = bits.getAddr32(0, y + 1); | |
| uint32_t* addr3 = bits.getAddr32(bitWidth, y); | |
| uint32_t* addr4 = bits.getAddr32(bitWidth, y + 1); | |
| for (int x = 0; x < bitWidth - 1; ++x) { | |
| // count 2x2 blocks | |
| bool err = addr1[x] != addr3[x]; | |
| if (err) { | |
| errors += addr1[x + 1] != addr3[x + 1] | |
| && addr2[x] != addr4[x] && addr2[x + 1] != addr4[x + 1]; | |
| } | |
| } | |
| } | |
| return errors; | |
| } | |
| #endif | |
| bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { | |
| #if DEBUG_VERIFY | |
| if (!OpDebug(one, two, op, result SkDEBUGPARAMS(nullptr))) { | |
| SkDebugf("%s did not expect failure\none: fill=%d\n", __FUNCTION__, one.getFillType()); | |
| one.dumpHex(); | |
| SkDebugf("two: fill=%d\n", two.getFillType()); | |
| two.dumpHex(); | |
| SkASSERT(0); | |
| return false; | |
| } | |
| SkPath pathOut, scaledPathOut; | |
| SkRegion rgnA, rgnB, openClip, rgnOut; | |
| openClip.setRect(-16000, -16000, 16000, 16000); | |
| rgnA.setPath(one, openClip); | |
| rgnB.setPath(two, openClip); | |
| rgnOut.op(rgnA, rgnB, (SkRegion::Op) op); | |
| rgnOut.getBoundaryPath(&pathOut); | |
| SkMatrix scale; | |
| debug_scale_matrix(one, two, scale); | |
| SkRegion scaledRgnA, scaledRgnB, scaledRgnOut; | |
| SkPath scaledA, scaledB; | |
| scaledA.addPath(one, scale); | |
| scaledA.setFillType(one.getFillType()); | |
| scaledB.addPath(two, scale); | |
| scaledB.setFillType(two.getFillType()); | |
| scaledRgnA.setPath(scaledA, openClip); | |
| scaledRgnB.setPath(scaledB, openClip); | |
| scaledRgnOut.op(scaledRgnA, scaledRgnB, (SkRegion::Op) op); | |
| scaledRgnOut.getBoundaryPath(&scaledPathOut); | |
| SkBitmap bitmap; | |
| SkPath scaledOut; | |
| scaledOut.addPath(*result, scale); | |
| scaledOut.setFillType(result->getFillType()); | |
| int errors = debug_paths_draw_the_same(scaledPathOut, scaledOut, bitmap); | |
| const int MAX_ERRORS = 9; | |
| if (errors > MAX_ERRORS) { | |
| SkDebugf("%s did not expect failure\none: fill=%d\n", __FUNCTION__, one.getFillType()); | |
| one.dumpHex(); | |
| SkDebugf("two: fill=%d\n", two.getFillType()); | |
| two.dumpHex(); | |
| SkASSERT(0); | |
| } | |
| return true; | |
| #else | |
| return OpDebug(one, two, op, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr)); | |
| #endif | |
| } |