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 = nullptr; 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 = nullptr; 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 nullptr; 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 if (!current->addCurveTo(start, end, simple)) { 115 return false; 116 } 117 #if DEBUG_ACTIVE_SPANS 118 if (!simple->isClosed()) { 119 DebugShowActiveSpans(contourList); 120 } 121 #endif 122 } 123 break; 124 } 125 #if DEBUG_FLOW 126 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, 127 current->debugID(), start->pt().fX, start->pt().fY, 128 end->pt().fX, end->pt().fY); 129 #endif 130 if (!current->addCurveTo(start, end, simple)) { 131 return false; 132 } 133 current = next; 134 start = nextStart; 135 end = nextEnd; 136 } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done())); 137 if (current->activeWinding(start, end) && !simple->isClosed()) { 138 SkOpSpan* spanStart = start->starter(end); 139 if (!spanStart->done()) { 140 if (!current->addCurveTo(start, end, simple)) { 141 return false; 142 } 143 current->markDone(spanStart); 144 } 145 } 146 simple->close(); 147 } else { 148 SkOpSpanBase* last = current->markAndChaseDone(start, end); 149 if (last && !last->chased()) { 150 last->setChased(true); 151 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); 152 *chase.append() = last; 153 #if DEBUG_WINDING 154 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID()); 155 if (!last->final()) { 156 SkDebugf(" windSum=%d", last->upCast()->windSum()); 157 } 158 SkDebugf("\n"); 159 #endif 160 } 161 } 162 current = findChaseOp(chase, &start, &end); 163 #if DEBUG_ACTIVE_SPANS 164 DebugShowActiveSpans(contourList); 165 #endif 166 if (!current) { 167 break; 168 } 169 } while (true); 170 } while (true); 171 return simple->someAssemblyRequired(); 172 } 173 174 // pretty picture: 175 // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing 176 static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = { 177 // inside minuend outside minuend 178 // inside subtrahend outside subtrahend inside subtrahend outside subtrahend 179 {{ kDifference_SkPathOp, kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }}, 180 {{ kIntersect_SkPathOp, kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }}, 181 {{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp, kIntersect_SkPathOp }}, 182 {{ kXOR_SkPathOp, kXOR_SkPathOp }, { kXOR_SkPathOp, kXOR_SkPathOp }}, 183 {{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp, kDifference_SkPathOp }}, 184 }; 185 186 static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = { 187 {{ false, false }, { true, false }}, // diff 188 {{ false, false }, { false, true }}, // sect 189 {{ false, true }, { true, true }}, // union 190 {{ false, true }, { true, false }}, // xor 191 {{ false, true }, { false, false }}, // rev diff 192 }; 193 194 #define DEBUGGING_PATHOPS_FROM_HOST 0 // enable to debug svg in chrome -- note path hardcoded below 195 #if DEBUGGING_PATHOPS_FROM_HOST 196 #include "SkData.h" 197 #include "SkStream.h" 198 199 static void dump_path(FILE* file, const SkPath& path, bool force, bool dumpAsHex) { 200 SkDynamicMemoryWStream wStream; 201 path.dump(&wStream, force, dumpAsHex); 202 SkAutoDataUnref data(wStream.copyToData()); 203 fprintf(file, "%.*s\n", (int) data->size(), data->data()); 204 } 205 206 static int dumpID = 0; 207 208 static void dump_op(const SkPath& one, const SkPath& two, SkPathOp op) { 209 #if SK_BUILD_FOR_MAC 210 FILE* file = fopen("/Users/caryclark/Documents/svgop.txt", "w"); 211 #else 212 FILE* file = fopen("/usr/local/google/home/caryclark/Documents/svgop.txt", "w"); 213 #endif 214 fprintf(file, 215 "\nstatic void fuzz763_%d(skiatest::Reporter* reporter, const char* filename) {\n", 216 ++dumpID); 217 fprintf(file, " SkPath path;\n"); 218 fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", one.getFillType()); 219 dump_path(file, one, false, true); 220 fprintf(file, " SkPath path1(path);\n"); 221 fprintf(file, " path.reset();\n"); 222 fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", two.getFillType()); 223 dump_path(file, two, false, true); 224 fprintf(file, " SkPath path2(path);\n"); 225 fprintf(file, " testPathOp(reporter, path1, path2, (SkPathOp) %d, filename);\n", op); 226 fprintf(file, "}\n"); 227 fclose(file); 228 } 229 #endif 230 231 232 #if DEBUG_T_SECT_LOOP_COUNT 233 234 #include "SkMutex.h" 235 236 SK_DECLARE_STATIC_MUTEX(debugWorstLoop); 237 238 SkOpGlobalState debugWorstState(nullptr, nullptr SkDEBUGPARAMS(nullptr)); 239 240 void ReportPathOpsDebugging() { 241 debugWorstState.debugLoopReport(); 242 } 243 244 extern void (*gVerboseFinalize)(); 245 246 #endif 247 248 bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result, 249 bool expectSuccess SkDEBUGPARAMS(const char* testName)) { 250 SkChunkAlloc allocator(4096); // FIXME: add a constant expression here, tune 251 SkOpContour contour; 252 SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour); 253 SkOpCoincidence coincidence; 254 SkOpGlobalState globalState(&coincidence, contourList SkDEBUGPARAMS(testName)); 255 #if DEBUGGING_PATHOPS_FROM_HOST 256 dump_op(one, two, op); 257 #endif 258 #if 0 && DEBUG_SHOW_TEST_NAME 259 char* debugName = DEBUG_FILENAME_STRING; 260 if (debugName && debugName[0]) { 261 SkPathOpsDebug::BumpTestName(debugName); 262 SkPathOpsDebug::ShowPath(one, two, op, debugName); 263 } 264 #endif 265 op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()]; 266 SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()] 267 ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType; 268 const SkPath* minuend = &one; 269 const SkPath* subtrahend = &two; 270 if (op == kReverseDifference_SkPathOp) { 271 minuend = &two; 272 subtrahend = &one; 273 op = kDifference_SkPathOp; 274 } 275 #if DEBUG_SORT 276 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; 277 #endif 278 // turn path into list of segments 279 SkOpEdgeBuilder builder(*minuend, &contour, &allocator, &globalState); 280 if (builder.unparseable()) { 281 return false; 282 } 283 const int xorMask = builder.xorMask(); 284 builder.addOperand(*subtrahend); 285 if (!builder.finish(&allocator)) { 286 return false; 287 } 288 #if DEBUG_DUMP_SEGMENTS 289 contourList->dumpSegments("seg", op); 290 #endif 291 292 const int xorOpMask = builder.xorMask(); 293 if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask, 294 xorOpMask == kEvenOdd_PathOpsMask)) { 295 result->reset(); 296 result->setFillType(fillType); 297 return true; 298 } 299 // find all intersections between segments 300 SkOpContour* current = contourList; 301 do { 302 SkOpContour* next = current; 303 while (AddIntersectTs(current, next, &coincidence, &allocator) 304 && (next = next->next())) 305 ; 306 } while ((current = current->next())); 307 #if DEBUG_VALIDATE 308 globalState.setPhase(SkOpGlobalState::kWalking); 309 #endif 310 if (!HandleCoincidence(contourList, &coincidence, &allocator)) { 311 return false; 312 } 313 #if DEBUG_ALIGNMENT 314 contourList->dumpSegments("aligned"); 315 #endif 316 // construct closed contours 317 result->reset(); 318 result->setFillType(fillType); 319 SkPathWriter wrapper(*result); 320 bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper, &allocator); 321 { // if some edges could not be resolved, assemble remaining fragments 322 SkPath temp; 323 temp.setFillType(fillType); 324 SkPathWriter assembled(temp); 325 Assemble(wrapper, &assembled); 326 *result = *assembled.nativePath(); 327 result->setFillType(fillType); 328 } 329 #if DEBUG_T_SECT_LOOP_COUNT 330 { 331 SkAutoMutexAcquire autoM(debugWorstLoop); 332 if (!gVerboseFinalize) { 333 gVerboseFinalize = &ReportPathOpsDebugging; 334 } 335 debugWorstState.debugDoYourWorst(&globalState); 336 } 337 #endif 338 return true; 339 } 340 341 #define DEBUG_VERIFY 0 342 343 #if DEBUG_VERIFY 344 #include "SkBitmap.h" 345 #include "SkCanvas.h" 346 #include "SkPaint.h" 347 348 const int bitWidth = 64; 349 const int bitHeight = 64; 350 351 static void debug_scale_matrix(const SkPath& one, const SkPath& two, SkMatrix& scale) { 352 SkRect larger = one.getBounds(); 353 larger.join(two.getBounds()); 354 SkScalar largerWidth = larger.width(); 355 if (largerWidth < 4) { 356 largerWidth = 4; 357 } 358 SkScalar largerHeight = larger.height(); 359 if (largerHeight < 4) { 360 largerHeight = 4; 361 } 362 SkScalar hScale = (bitWidth - 2) / largerWidth; 363 SkScalar vScale = (bitHeight - 2) / largerHeight; 364 scale.reset(); 365 scale.preScale(hScale, vScale); 366 larger.fLeft *= hScale; 367 larger.fRight *= hScale; 368 larger.fTop *= vScale; 369 larger.fBottom *= vScale; 370 SkScalar dx = -16000 > larger.fLeft ? -16000 - larger.fLeft 371 : 16000 < larger.fRight ? 16000 - larger.fRight : 0; 372 SkScalar dy = -16000 > larger.fTop ? -16000 - larger.fTop 373 : 16000 < larger.fBottom ? 16000 - larger.fBottom : 0; 374 scale.preTranslate(dx, dy); 375 } 376 377 static int debug_paths_draw_the_same(const SkPath& one, const SkPath& two, SkBitmap& bits) { 378 if (bits.width() == 0) { 379 bits.allocN32Pixels(bitWidth * 2, bitHeight); 380 } 381 SkCanvas canvas(bits); 382 canvas.drawColor(SK_ColorWHITE); 383 SkPaint paint; 384 canvas.save(); 385 const SkRect& bounds1 = one.getBounds(); 386 canvas.translate(-bounds1.fLeft + 1, -bounds1.fTop + 1); 387 canvas.drawPath(one, paint); 388 canvas.restore(); 389 canvas.save(); 390 canvas.translate(-bounds1.fLeft + 1 + bitWidth, -bounds1.fTop + 1); 391 canvas.drawPath(two, paint); 392 canvas.restore(); 393 int errors = 0; 394 for (int y = 0; y < bitHeight - 1; ++y) { 395 uint32_t* addr1 = bits.getAddr32(0, y); 396 uint32_t* addr2 = bits.getAddr32(0, y + 1); 397 uint32_t* addr3 = bits.getAddr32(bitWidth, y); 398 uint32_t* addr4 = bits.getAddr32(bitWidth, y + 1); 399 for (int x = 0; x < bitWidth - 1; ++x) { 400 // count 2x2 blocks 401 bool err = addr1[x] != addr3[x]; 402 if (err) { 403 errors += addr1[x + 1] != addr3[x + 1] 404 && addr2[x] != addr4[x] && addr2[x + 1] != addr4[x + 1]; 405 } 406 } 407 } 408 return errors; 409 } 410 411 #endif 412 413 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { 414 #if DEBUG_VERIFY 415 if (!OpDebug(one, two, op, result, true SkDEBUGPARAMS(nullptr))) { 416 SkDebugf("%s did not expect failure\none: fill=%d\n", __FUNCTION__, one.getFillType()); 417 one.dumpHex(); 418 SkDebugf("two: fill=%d\n", two.getFillType()); 419 two.dumpHex(); 420 SkASSERT(0); 421 return false; 422 } 423 SkPath pathOut, scaledPathOut; 424 SkRegion rgnA, rgnB, openClip, rgnOut; 425 openClip.setRect(-16000, -16000, 16000, 16000); 426 rgnA.setPath(one, openClip); 427 rgnB.setPath(two, openClip); 428 rgnOut.op(rgnA, rgnB, (SkRegion::Op) op); 429 rgnOut.getBoundaryPath(&pathOut); 430 SkMatrix scale; 431 debug_scale_matrix(one, two, scale); 432 SkRegion scaledRgnA, scaledRgnB, scaledRgnOut; 433 SkPath scaledA, scaledB; 434 scaledA.addPath(one, scale); 435 scaledA.setFillType(one.getFillType()); 436 scaledB.addPath(two, scale); 437 scaledB.setFillType(two.getFillType()); 438 scaledRgnA.setPath(scaledA, openClip); 439 scaledRgnB.setPath(scaledB, openClip); 440 scaledRgnOut.op(scaledRgnA, scaledRgnB, (SkRegion::Op) op); 441 scaledRgnOut.getBoundaryPath(&scaledPathOut); 442 SkBitmap bitmap; 443 SkPath scaledOut; 444 scaledOut.addPath(*result, scale); 445 scaledOut.setFillType(result->getFillType()); 446 int errors = debug_paths_draw_the_same(scaledPathOut, scaledOut, bitmap); 447 const int MAX_ERRORS = 9; 448 if (errors > MAX_ERRORS) { 449 SkDebugf("%s did not expect failure\none: fill=%d\n", __FUNCTION__, one.getFillType()); 450 one.dumpHex(); 451 SkDebugf("two: fill=%d\n", two.getFillType()); 452 two.dumpHex(); 453 SkASSERT(0); 454 } 455 return true; 456 #else 457 return OpDebug(one, two, op, result, true SkDEBUGPARAMS(nullptr)); 458 #endif 459 } 460
