/* * 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& 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(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 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(&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); }