1 /* 2 * Copyright 2012 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 #include "SkAddIntersections.h" 8 #include "SkOpCoincidence.h" 9 #include "SkOpEdgeBuilder.h" 10 #include "SkPathOpsCommon.h" 11 #include "SkPathWriter.h" 12 13 static SkOpSegment* findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr, 14 SkOpSpanBase** endPtr) { 15 while (chase.count()) { 16 SkOpSpanBase* span; 17 chase.pop(&span); 18 // OPTIMIZE: prev makes this compatible with old code -- but is it necessary? 19 *startPtr = span->ptT()->prev()->span(); 20 SkOpSegment* segment = (*startPtr)->segment(); 21 bool done = true; 22 *endPtr = NULL; 23 if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) { 24 *startPtr = last->start(); 25 *endPtr = last->end(); 26 #if TRY_ROTATE 27 *chase.insert(0) = span; 28 #else 29 *chase.append() = span; 30 #endif 31 return last->segment(); 32 } 33 if (done) { 34 continue; 35 } 36 int winding; 37 bool sortable; 38 const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable); 39 if (winding == SK_MinS32) { 40 continue; 41 } 42 int sumMiWinding, sumSuWinding; 43 if (sortable) { 44 segment = angle->segment(); 45 sumMiWinding = segment->updateWindingReverse(angle); 46 sumSuWinding = segment->updateOppWindingReverse(angle); 47 if (segment->operand()) { 48 SkTSwap<int>(sumMiWinding, sumSuWinding); 49 } 50 } 51 SkOpSegment* first = NULL; 52 const SkOpAngle* firstAngle = angle; 53 while ((angle = angle->next()) != firstAngle) { 54 segment = angle->segment(); 55 SkOpSpanBase* start = angle->start(); 56 SkOpSpanBase* end = angle->end(); 57 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 58 if (sortable) { 59 segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding, 60 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 61 } 62 if (!segment->done(angle)) { 63 if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) { 64 first = segment; 65 *startPtr = start; 66 *endPtr = end; 67 } 68 // OPTIMIZATION: should this also add to the chase? 69 if (sortable) { 70 (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding, 71 oppSumWinding, angle); 72 } 73 } 74 } 75 if (first) { 76 #if TRY_ROTATE 77 *chase.insert(0) = span; 78 #else 79 *chase.append() = span; 80 #endif 81 return first; 82 } 83 } 84 return NULL; 85 } 86 87 static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op, 88 const int xorMask, const int xorOpMask, SkPathWriter* simple, SkChunkAlloc* allocator) { 89 bool unsortable = false; 90 do { 91 SkOpSpan* span = FindSortableTop(contourList); 92 if (!span) { 93 break; 94 } 95 SkOpSegment* current = span->segment(); 96 SkOpSpanBase* start = span->next(); 97 SkOpSpanBase* end = span; 98 SkTDArray<SkOpSpanBase*> chase; 99 do { 100 if (current->activeOp(start, end, xorMask, xorOpMask, op)) { 101 do { 102 if (!unsortable && current->done()) { 103 break; 104 } 105 SkASSERT(unsortable || !current->done()); 106 SkOpSpanBase* nextStart = start; 107 SkOpSpanBase* nextEnd = end; 108 SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd, 109 &unsortable, op, xorMask, xorOpMask); 110 if (!next) { 111 if (!unsortable && simple->hasMove() 112 && current->verb() != SkPath::kLine_Verb 113 && !simple->isClosed()) { 114 current->addCurveTo(start, end, simple, true); 115 #if DEBUG_ACTIVE_SPANS 116 if (!simple->isClosed()) { 117 DebugShowActiveSpans(contourList); 118 } 119 #endif 120 } 121 break; 122 } 123 #if DEBUG_FLOW 124 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, 125 current->debugID(), start->pt().fX, start->pt().fY, 126 end->pt().fX, end->pt().fY); 127 #endif 128 current->addCurveTo(start, end, simple, true); 129 current = next; 130 start = nextStart; 131 end = nextEnd; 132 } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done())); 133 if (current->activeWinding(start, end) && !simple->isClosed()) { 134 SkOpSpan* spanStart = start->starter(end); 135 if (!spanStart->done()) { 136 current->addCurveTo(start, end, simple, true); 137 current->markDone(spanStart); 138 } 139 } 140 simple->close(); 141 } else { 142 SkOpSpanBase* last = current->markAndChaseDone(start, end); 143 if (last && !last->chased()) { 144 last->setChased(true); 145 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); 146 *chase.append() = last; 147 #if DEBUG_WINDING 148 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID()); 149 if (!last->final()) { 150 SkDebugf(" windSum=%d", last->upCast()->windSum()); 151 } 152 SkDebugf("\n"); 153 #endif 154 } 155 } 156 current = findChaseOp(chase, &start, &end); 157 #if DEBUG_ACTIVE_SPANS 158 DebugShowActiveSpans(contourList); 159 #endif 160 if (!current) { 161 break; 162 } 163 } while (true); 164 } while (true); 165 return simple->someAssemblyRequired(); 166 } 167 168 // pretty picture: 169 // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing 170 static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = { 171 // inside minuend outside minuend 172 // inside subtrahend outside subtrahend inside subtrahend outside subtrahend 173 {{ kDifference_SkPathOp, kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }}, 174 {{ kIntersect_SkPathOp, kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }}, 175 {{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp, kIntersect_SkPathOp }}, 176 {{ kXOR_SkPathOp, kXOR_SkPathOp }, { kXOR_SkPathOp, kXOR_SkPathOp }}, 177 {{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp, kDifference_SkPathOp }}, 178 }; 179 180 static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = { 181 {{ false, false }, { true, false }}, // diff 182 {{ false, false }, { false, true }}, // sect 183 {{ false, true }, { true, true }}, // union 184 {{ false, true }, { true, false }}, // xor 185 {{ false, true }, { false, false }}, // rev diff 186 }; 187 188 #define DEBUGGING_PATHOPS_FROM_HOST 0 // enable to debug svg in chrome -- note path hardcoded below 189 #if DEBUGGING_PATHOPS_FROM_HOST 190 #include "SkData.h" 191 #include "SkStream.h" 192 193 static void dump_path(FILE* file, const SkPath& path, bool force, bool dumpAsHex) { 194 SkDynamicMemoryWStream wStream; 195 path.dump(&wStream, force, dumpAsHex); 196 SkAutoDataUnref data(wStream.copyToData()); 197 fprintf(file, "%.*s\n", (int) data->size(), data->data()); 198 } 199 200 static int dumpID = 0; 201 202 static void dump_op(const SkPath& one, const SkPath& two, SkPathOp op) { 203 #if SK_BUILD_FOR_MAC 204 FILE* file = fopen("/Users/caryclark/Documents/svgop.txt", "w"); 205 #else 206 FILE* file = fopen("/usr/local/google/home/caryclark/Documents/svgop.txt", "w"); 207 #endif 208 fprintf(file, 209 "\nstatic void fuzz763_%d(skiatest::Reporter* reporter, const char* filename) {\n", 210 ++dumpID); 211 fprintf(file, " SkPath path;\n"); 212 fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", one.getFillType()); 213 dump_path(file, one, false, true); 214 fprintf(file, " SkPath path1(path);\n"); 215 fprintf(file, " path.reset();\n"); 216 fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", two.getFillType()); 217 dump_path(file, two, false, true); 218 fprintf(file, " SkPath path2(path);\n"); 219 fprintf(file, " testPathOp(reporter, path1, path2, (SkPathOp) %d, filename);\n", op); 220 fprintf(file, "}\n"); 221 fclose(file); 222 } 223 #endif 224 225 bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result, 226 bool expectSuccess) { 227 SkChunkAlloc allocator(4096); // FIXME: add a constant expression here, tune 228 SkOpContour contour; 229 SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour); 230 SkOpCoincidence coincidence; 231 SkOpGlobalState globalState(&coincidence, contourList); 232 #if DEBUGGING_PATHOPS_FROM_HOST 233 dump_op(one, two, op); 234 #endif 235 #if 0 && DEBUG_SHOW_TEST_NAME 236 char* debugName = DEBUG_FILENAME_STRING; 237 if (debugName && debugName[0]) { 238 SkPathOpsDebug::BumpTestName(debugName); 239 SkPathOpsDebug::ShowPath(one, two, op, debugName); 240 } 241 #endif 242 op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()]; 243 SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()] 244 ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType; 245 const SkPath* minuend = &one; 246 const SkPath* subtrahend = &two; 247 if (op == kReverseDifference_SkPathOp) { 248 minuend = &two; 249 subtrahend = &one; 250 op = kDifference_SkPathOp; 251 } 252 #if DEBUG_SORT 253 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; 254 #endif 255 // turn path into list of segments 256 SkOpEdgeBuilder builder(*minuend, &contour, &allocator, &globalState); 257 if (builder.unparseable()) { 258 return false; 259 } 260 const int xorMask = builder.xorMask(); 261 builder.addOperand(*subtrahend); 262 if (!builder.finish(&allocator)) { 263 return false; 264 } 265 #if DEBUG_DUMP_SEGMENTS 266 contour.dumpSegments(op); 267 #endif 268 269 const int xorOpMask = builder.xorMask(); 270 if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask, 271 xorOpMask == kEvenOdd_PathOpsMask)) { 272 result->reset(); 273 result->setFillType(fillType); 274 return true; 275 } 276 // find all intersections between segments 277 SkOpContour* current = contourList; 278 do { 279 SkOpContour* next = current; 280 while (AddIntersectTs(current, next, &coincidence, &allocator) 281 && (next = next->next())) 282 ; 283 } while ((current = current->next())); 284 #if DEBUG_VALIDATE 285 globalState.setPhase(SkOpGlobalState::kWalking); 286 #endif 287 if (!HandleCoincidence(contourList, &coincidence, &allocator)) { 288 return false; 289 } 290 // construct closed contours 291 result->reset(); 292 result->setFillType(fillType); 293 SkPathWriter wrapper(*result); 294 bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper, &allocator); 295 { // if some edges could not be resolved, assemble remaining fragments 296 SkPath temp; 297 temp.setFillType(fillType); 298 SkPathWriter assembled(temp); 299 Assemble(wrapper, &assembled); 300 *result = *assembled.nativePath(); 301 result->setFillType(fillType); 302 } 303 return true; 304 } 305 306 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { 307 return OpDebug(one, two, op, result, true); 308 } 309
