| /* |
| * 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 = NULL; |
| 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 (winding == SK_MinS32) { |
| continue; |
| } |
| int sumMiWinding, sumSuWinding; |
| if (sortable) { |
| segment = angle->segment(); |
| sumMiWinding = segment->updateWindingReverse(angle); |
| sumSuWinding = segment->updateOppWindingReverse(angle); |
| if (segment->operand()) { |
| SkTSwap<int>(sumMiWinding, sumSuWinding); |
| } |
| } |
| SkOpSegment* first = NULL; |
| 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 NULL; |
| } |
| |
| static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op, |
| const int xorMask, const int xorOpMask, SkPathWriter* simple, SkChunkAlloc* allocator) { |
| 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()) { |
| current->addCurveTo(start, end, simple, true); |
| #if DEBUG_ACTIVE_SPANS |
| if (!simple->isClosed()) { |
| DebugShowActiveSpans(contourList); |
| } |
| #endif |
| } |
| 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 |
| current->addCurveTo(start, end, simple, true); |
| 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()) { |
| current->addCurveTo(start, end, simple, true); |
| 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); |
| #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_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); |
| SkAutoDataUnref 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 |
| |
| bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result, |
| bool expectSuccess) { |
| SkChunkAlloc allocator(4096); // FIXME: add a constant expression here, tune |
| SkOpContour contour; |
| SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour); |
| SkOpCoincidence coincidence; |
| SkOpGlobalState globalState(&coincidence, contourList); |
| #if DEBUGGING_PATHOPS_FROM_HOST |
| dump_op(one, two, op); |
| #endif |
| #if 0 && 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_SkPathOp) { |
| minuend = &two; |
| subtrahend = &one; |
| op = kDifference_SkPathOp; |
| } |
| #if DEBUG_SORT |
| SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; |
| #endif |
| // turn path into list of segments |
| SkOpEdgeBuilder builder(*minuend, &contour, &allocator, &globalState); |
| if (builder.unparseable()) { |
| return false; |
| } |
| const int xorMask = builder.xorMask(); |
| builder.addOperand(*subtrahend); |
| if (!builder.finish(&allocator)) { |
| return false; |
| } |
| #if DEBUG_DUMP_SEGMENTS |
| contour.dumpSegments(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, &allocator) |
| && (next = next->next())) |
| ; |
| } while ((current = current->next())); |
| #if DEBUG_VALIDATE |
| globalState.setPhase(SkOpGlobalState::kWalking); |
| #endif |
| if (!HandleCoincidence(contourList, &coincidence, &allocator)) { |
| return false; |
| } |
| // construct closed contours |
| result->reset(); |
| result->setFillType(fillType); |
| SkPathWriter wrapper(*result); |
| bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper, &allocator); |
| { // 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; |
| } |
| |
| bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { |
| return OpDebug(one, two, op, result, true); |
| } |
