1 /* 2 * Copyright 2013 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 8 #include "SkMutex.h" 9 #include "SkOpCoincidence.h" 10 #include "SkOpContour.h" 11 #include "SkPath.h" 12 #include "SkPathOpsDebug.h" 13 #include "SkString.h" 14 15 struct SkCoincidentSpans; 16 17 #if DEBUG_VALIDATE 18 extern bool FLAGS_runFail; 19 #endif 20 21 #if DEBUG_SORT 22 int SkPathOpsDebug::gSortCountDefault = SK_MaxS32; 23 int SkPathOpsDebug::gSortCount; 24 #endif 25 26 #if DEBUG_ACTIVE_OP 27 const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"}; 28 #endif 29 30 #if defined SK_DEBUG || !FORCE_RELEASE 31 32 const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"}; 33 34 int SkPathOpsDebug::gContourID = 0; 35 int SkPathOpsDebug::gSegmentID = 0; 36 37 bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase* >& chaseArray, 38 const SkOpSpanBase* span) { 39 for (int index = 0; index < chaseArray.count(); ++index) { 40 const SkOpSpanBase* entry = chaseArray[index]; 41 if (entry == span) { 42 return true; 43 } 44 } 45 return false; 46 } 47 #endif 48 49 #if DEBUG_COINCIDENCE 50 enum GlitchType { 51 kAddCorruptCoin_Glitch, 52 kAddExpandedCoin_Glitch, 53 kAddMissingCoin_Glitch, 54 kCollapsedCoin_Glitch, 55 kCollapsedDone_Glitch, 56 kCollapsedOppValue_Glitch, 57 kCollapsedSpan_Glitch, 58 kCollapsedWindValue_Glitch, 59 kDeletedCoin_Glitch, 60 kExpandCoin_Glitch, 61 kMarkCoinEnd_Glitch, 62 kMarkCoinInsert_Glitch, 63 kMissingCoin_Glitch, 64 kMissingDone_Glitch, 65 kMissingIntersection_Glitch, 66 kMoveMultiple_Glitch, 67 kUnaligned_Glitch, 68 kUnalignedHead_Glitch, 69 kUnalignedTail_Glitch, 70 kUndetachedSpan_Glitch, 71 kUnmergedSpan_Glitch, 72 }; 73 74 static const int kGlitchType_Count = kUnmergedSpan_Glitch + 1; 75 76 struct SpanGlitch { 77 const char* fStage; 78 const SkOpSpanBase* fBase; 79 const SkOpSpanBase* fSuspect; 80 const SkCoincidentSpans* fCoin; 81 const SkOpSegment* fSegment; 82 const SkOpPtT* fCoinSpan; 83 const SkOpPtT* fEndSpan; 84 const SkOpPtT* fOppSpan; 85 const SkOpPtT* fOppEndSpan; 86 double fT; 87 SkPoint fPt; 88 GlitchType fType; 89 }; 90 91 struct SkPathOpsDebug::GlitchLog { 92 SpanGlitch* recordCommon(GlitchType type, const char* stage) { 93 SpanGlitch* glitch = fGlitches.push(); 94 glitch->fStage = stage; 95 glitch->fBase = nullptr; 96 glitch->fSuspect = nullptr; 97 glitch->fCoin = nullptr; 98 glitch->fSegment = nullptr; 99 glitch->fCoinSpan = nullptr; 100 glitch->fEndSpan = nullptr; 101 glitch->fOppSpan = nullptr; 102 glitch->fOppEndSpan = nullptr; 103 glitch->fT = SK_ScalarNaN; 104 glitch->fPt = { SK_ScalarNaN, SK_ScalarNaN }; 105 glitch->fType = type; 106 return glitch; 107 } 108 109 void record(GlitchType type, const char* stage, const SkOpSpanBase* base, 110 const SkOpSpanBase* suspect = NULL) { 111 SpanGlitch* glitch = recordCommon(type, stage); 112 glitch->fBase = base; 113 glitch->fSuspect = suspect; 114 } 115 116 void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin, 117 const SkOpPtT* coinSpan) { 118 SpanGlitch* glitch = recordCommon(type, stage); 119 glitch->fCoin = coin; 120 glitch->fCoinSpan = coinSpan; 121 } 122 123 void record(GlitchType type, const char* stage, const SkOpSpanBase* base, 124 const SkOpSegment* seg, double t, SkPoint pt) { 125 SpanGlitch* glitch = recordCommon(type, stage); 126 glitch->fBase = base; 127 glitch->fSegment = seg; 128 glitch->fT = t; 129 glitch->fPt = pt; 130 } 131 132 void record(GlitchType type, const char* stage, const SkOpSpanBase* base, double t, 133 SkPoint pt) { 134 SpanGlitch* glitch = recordCommon(type, stage); 135 glitch->fBase = base; 136 glitch->fT = t; 137 glitch->fPt = pt; 138 } 139 140 void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin, 141 const SkOpPtT* coinSpan, const SkOpPtT* endSpan) { 142 SpanGlitch* glitch = recordCommon(type, stage); 143 glitch->fCoin = coin; 144 glitch->fCoinSpan = coinSpan; 145 glitch->fEndSpan = endSpan; 146 } 147 148 void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin, 149 const SkOpSpanBase* suspect) { 150 SpanGlitch* glitch = recordCommon(type, stage); 151 glitch->fSuspect = suspect; 152 glitch->fCoin = coin; 153 } 154 155 void record(GlitchType type, const char* stage, const SkOpPtT* ptTS, const SkOpPtT* ptTE, 156 const SkOpPtT* oPtTS, const SkOpPtT* oPtTE) { 157 SpanGlitch* glitch = recordCommon(type, stage); 158 glitch->fCoinSpan = ptTS; 159 glitch->fEndSpan = ptTE; 160 glitch->fOppSpan = oPtTS; 161 glitch->fOppEndSpan = oPtTE; 162 } 163 164 SkTDArray<SpanGlitch> fGlitches; 165 }; 166 167 void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) { 168 GlitchLog glitches; 169 const SkOpContour* contour = contourList; 170 const SkOpCoincidence* coincidence = contour->globalState()->coincidence(); 171 do { 172 contour->debugCheckHealth(id, &glitches); 173 contour->debugMissingCoincidence(id, &glitches, coincidence); 174 } while ((contour = contour->next())); 175 coincidence->debugFixAligned(id, &glitches); 176 coincidence->debugAddMissing(id, &glitches); 177 coincidence->debugExpand(id, &glitches); 178 coincidence->debugAddExpanded(id, &glitches); 179 coincidence->debugMark(id, &glitches); 180 unsigned mask = 0; 181 for (int index = 0; index < glitches.fGlitches.count(); ++index) { 182 const SpanGlitch& glitch = glitches.fGlitches[index]; 183 mask |= 1 << glitch.fType; 184 } 185 for (int index = 0; index < kGlitchType_Count; ++index) { 186 SkDebugf(mask & (1 << index) ? "x" : "-"); 187 } 188 SkDebugf(" %s\n", id); 189 } 190 #endif 191 192 #if defined SK_DEBUG || !FORCE_RELEASE 193 void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) { 194 size_t len = strlen(str); 195 bool num = false; 196 for (size_t idx = 0; idx < len; ++idx) { 197 if (num && str[idx] == 'e') { 198 if (len + 2 >= bufferLen) { 199 return; 200 } 201 memmove(&str[idx + 2], &str[idx + 1], len - idx); 202 str[idx] = '*'; 203 str[idx + 1] = '^'; 204 ++len; 205 } 206 num = str[idx] >= '0' && str[idx] <= '9'; 207 } 208 } 209 210 bool SkPathOpsDebug::ValidWind(int wind) { 211 return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF; 212 } 213 214 void SkPathOpsDebug::WindingPrintf(int wind) { 215 if (wind == SK_MinS32) { 216 SkDebugf("?"); 217 } else { 218 SkDebugf("%d", wind); 219 } 220 } 221 #endif // defined SK_DEBUG || !FORCE_RELEASE 222 223 224 #if DEBUG_SHOW_TEST_NAME 225 void* SkPathOpsDebug::CreateNameStr() { return new char[DEBUG_FILENAME_STRING_LENGTH]; } 226 227 void SkPathOpsDebug::DeleteNameStr(void* v) { delete[] reinterpret_cast<char*>(v); } 228 229 void SkPathOpsDebug::BumpTestName(char* test) { 230 char* num = test + strlen(test); 231 while (num[-1] >= '0' && num[-1] <= '9') { 232 --num; 233 } 234 if (num[0] == '\0') { 235 return; 236 } 237 int dec = atoi(num); 238 if (dec == 0) { 239 return; 240 } 241 ++dec; 242 SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec); 243 } 244 #endif 245 246 static void show_function_header(const char* functionName) { 247 SkDebugf("\nstatic void %s(skiatest::Reporter* reporter, const char* filename) {\n", functionName); 248 if (strcmp("skphealth_com76", functionName) == 0) { 249 SkDebugf("found it\n"); 250 } 251 } 252 253 static const char* gOpStrs[] = { 254 "kDifference_SkPathOp", 255 "kIntersect_SkPathOp", 256 "kUnion_SkPathOp", 257 "kXor_PathOp", 258 "kReverseDifference_SkPathOp", 259 }; 260 261 const char* SkPathOpsDebug::OpStr(SkPathOp op) { 262 return gOpStrs[op]; 263 } 264 265 static void show_op(SkPathOp op, const char* pathOne, const char* pathTwo) { 266 SkDebugf(" testPathOp(reporter, %s, %s, %s, filename);\n", pathOne, pathTwo, gOpStrs[op]); 267 SkDebugf("}\n"); 268 } 269 270 SK_DECLARE_STATIC_MUTEX(gTestMutex); 271 272 void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp, 273 const char* testName) { 274 SkAutoMutexAcquire ac(gTestMutex); 275 show_function_header(testName); 276 ShowOnePath(a, "path", true); 277 ShowOnePath(b, "pathB", true); 278 show_op(shapeOp, "path", "pathB"); 279 } 280 281 #include "SkPathOpsTypes.h" 282 #include "SkIntersectionHelper.h" 283 #include "SkIntersections.h" 284 285 #if DEBUG_T_SECT_LOOP_COUNT 286 void SkOpGlobalState::debugAddLoopCount(SkIntersections* i, const SkIntersectionHelper& wt, 287 const SkIntersectionHelper& wn) { 288 for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) { 289 SkIntersections::DebugLoop looper = (SkIntersections::DebugLoop) index; 290 if (fDebugLoopCount[index] >= i->debugLoopCount(looper)) { 291 continue; 292 } 293 fDebugLoopCount[index] = i->debugLoopCount(looper); 294 fDebugWorstVerb[index * 2] = wt.segment()->verb(); 295 fDebugWorstVerb[index * 2 + 1] = wn.segment()->verb(); 296 sk_bzero(&fDebugWorstPts[index * 8], sizeof(SkPoint) * 8); 297 memcpy(&fDebugWorstPts[index * 2 * 4], wt.pts(), 298 (SkPathOpsVerbToPoints(wt.segment()->verb()) + 1) * sizeof(SkPoint)); 299 memcpy(&fDebugWorstPts[(index * 2 + 1) * 4], wn.pts(), 300 (SkPathOpsVerbToPoints(wn.segment()->verb()) + 1) * sizeof(SkPoint)); 301 fDebugWorstWeight[index * 2] = wt.weight(); 302 fDebugWorstWeight[index * 2 + 1] = wn.weight(); 303 } 304 i->debugResetLoopCount(); 305 } 306 307 void SkOpGlobalState::debugDoYourWorst(SkOpGlobalState* local) { 308 for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) { 309 if (fDebugLoopCount[index] >= local->fDebugLoopCount[index]) { 310 continue; 311 } 312 fDebugLoopCount[index] = local->fDebugLoopCount[index]; 313 fDebugWorstVerb[index * 2] = local->fDebugWorstVerb[index * 2]; 314 fDebugWorstVerb[index * 2 + 1] = local->fDebugWorstVerb[index * 2 + 1]; 315 memcpy(&fDebugWorstPts[index * 2 * 4], &local->fDebugWorstPts[index * 2 * 4], 316 sizeof(SkPoint) * 8); 317 fDebugWorstWeight[index * 2] = local->fDebugWorstWeight[index * 2]; 318 fDebugWorstWeight[index * 2 + 1] = local->fDebugWorstWeight[index * 2 + 1]; 319 } 320 local->debugResetLoopCounts(); 321 } 322 323 static void dump_curve(SkPath::Verb verb, const SkPoint& pts, float weight) { 324 if (!verb) { 325 return; 326 } 327 const char* verbs[] = { "", "line", "quad", "conic", "cubic" }; 328 SkDebugf("%s: {{", verbs[verb]); 329 int ptCount = SkPathOpsVerbToPoints(verb); 330 for (int index = 0; index <= ptCount; ++index) { 331 SkDPoint::Dump((&pts)[index]); 332 if (index < ptCount - 1) { 333 SkDebugf(", "); 334 } 335 } 336 SkDebugf("}"); 337 if (weight != 1) { 338 SkDebugf(", "); 339 if (weight == floorf(weight)) { 340 SkDebugf("%.0f", weight); 341 } else { 342 SkDebugf("%1.9gf", weight); 343 } 344 } 345 SkDebugf("}\n"); 346 } 347 348 void SkOpGlobalState::debugLoopReport() { 349 const char* loops[] = { "iterations", "coinChecks", "perpCalcs" }; 350 SkDebugf("\n"); 351 for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) { 352 SkDebugf("%s: %d\n", loops[index], fDebugLoopCount[index]); 353 dump_curve(fDebugWorstVerb[index * 2], fDebugWorstPts[index * 2 * 4], 354 fDebugWorstWeight[index * 2]); 355 dump_curve(fDebugWorstVerb[index * 2 + 1], fDebugWorstPts[(index * 2 + 1) * 4], 356 fDebugWorstWeight[index * 2 + 1]); 357 } 358 } 359 360 void SkOpGlobalState::debugResetLoopCounts() { 361 sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount)); 362 sk_bzero(fDebugWorstVerb, sizeof(fDebugWorstVerb)); 363 sk_bzero(fDebugWorstPts, sizeof(fDebugWorstPts)); 364 sk_bzero(fDebugWorstWeight, sizeof(fDebugWorstWeight)); 365 } 366 #endif 367 368 #ifdef SK_DEBUG 369 bool SkOpGlobalState::debugRunFail() const { 370 #if DEBUG_VALIDATE 371 return FLAGS_runFail; 372 #else 373 return false; 374 #endif 375 } 376 #endif 377 378 #if DEBUG_T_SECT_LOOP_COUNT 379 void SkIntersections::debugBumpLoopCount(DebugLoop index) { 380 fDebugLoopCount[index]++; 381 } 382 383 int SkIntersections::debugLoopCount(DebugLoop index) const { 384 return fDebugLoopCount[index]; 385 } 386 387 void SkIntersections::debugResetLoopCount() { 388 sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount)); 389 } 390 #endif 391 392 #include "SkPathOpsCubic.h" 393 #include "SkPathOpsQuad.h" 394 395 SkDCubic SkDQuad::debugToCubic() const { 396 SkDCubic cubic; 397 cubic[0] = fPts[0]; 398 cubic[2] = fPts[1]; 399 cubic[3] = fPts[2]; 400 cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3; 401 cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3; 402 cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3; 403 cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3; 404 return cubic; 405 } 406 407 void SkDRect::debugInit() { 408 fLeft = fTop = fRight = fBottom = SK_ScalarNaN; 409 } 410 411 #include "SkOpAngle.h" 412 #include "SkOpSegment.h" 413 414 #if DEBUG_COINCIDENCE 415 void SkOpSegment::debugAddAlignIntersection(const char* id, SkPathOpsDebug::GlitchLog* log, 416 const SkOpPtT& endPtT, const SkPoint& oldPt, const SkOpContourHead* contourList) const { 417 const SkPoint& newPt = endPtT.fPt; 418 if (newPt == oldPt) { 419 return; 420 } 421 SkPoint line[2] = { newPt, oldPt }; 422 SkPathOpsBounds lineBounds; 423 lineBounds.setBounds(line, 2); 424 SkDLine aLine; 425 aLine.set(line); 426 const SkOpContour* current = contourList; 427 do { 428 if (!SkPathOpsBounds::Intersects(current->bounds(), lineBounds)) { 429 continue; 430 } 431 const SkOpSegment* segment = current->first(); 432 do { 433 if (!SkPathOpsBounds::Intersects(segment->bounds(), lineBounds)) { 434 continue; 435 } 436 if (newPt == segment->fPts[0]) { 437 continue; 438 } 439 if (newPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) { 440 continue; 441 } 442 if (oldPt == segment->fPts[0]) { 443 continue; 444 } 445 if (oldPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) { 446 continue; 447 } 448 if (endPtT.debugContains(segment)) { 449 continue; 450 } 451 SkIntersections i; 452 switch (segment->fVerb) { 453 case SkPath::kLine_Verb: { 454 SkDLine bLine; 455 bLine.set(segment->fPts); 456 i.intersect(bLine, aLine); 457 } break; 458 case SkPath::kQuad_Verb: { 459 SkDQuad bQuad; 460 bQuad.set(segment->fPts); 461 i.intersect(bQuad, aLine); 462 } break; 463 case SkPath::kConic_Verb: { 464 SkDConic bConic; 465 bConic.set(segment->fPts, segment->fWeight); 466 i.intersect(bConic, aLine); 467 } break; 468 case SkPath::kCubic_Verb: { 469 SkDCubic bCubic; 470 bCubic.set(segment->fPts); 471 i.intersect(bCubic, aLine); 472 } break; 473 default: 474 SkASSERT(0); 475 } 476 if (i.used()) { 477 SkASSERT(i.used() == 1); 478 SkASSERT(!zero_or_one(i[0][0])); 479 SkOpSpanBase* checkSpan = fHead.next(); 480 while (!checkSpan->final()) { 481 if (checkSpan->contains(segment)) { 482 goto nextSegment; 483 } 484 checkSpan = checkSpan->upCast()->next(); 485 } 486 log->record(kMissingIntersection_Glitch, id, checkSpan, segment, i[0][0], newPt); 487 } 488 nextSegment: 489 ; 490 } while ((segment = segment->next())); 491 } while ((current = current->next())); 492 } 493 494 bool SkOpSegment::debugAddMissing(double t, const SkOpSegment* opp) const { 495 const SkOpSpanBase* existing = nullptr; 496 const SkOpSpanBase* test = &fHead; 497 double testT; 498 do { 499 if ((testT = test->ptT()->fT) >= t) { 500 if (testT == t) { 501 existing = test; 502 } 503 break; 504 } 505 } while ((test = test->upCast()->next())); 506 return !existing || !existing->debugContains(opp); 507 } 508 509 void SkOpSegment::debugAlign(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { 510 const SkOpSpanBase* span = &fHead; 511 if (!span->aligned()) { 512 if (!span->debugAlignedEnd(0, fPts[0])) { 513 glitches->record(kUnalignedHead_Glitch, id, span); 514 } 515 } 516 while ((span = span->upCast()->next())) { 517 if (span == &fTail) { 518 break; 519 } 520 if (!span->aligned()) { 521 glitches->record(kUnaligned_Glitch, id, span); 522 } 523 } 524 if (!span->aligned()) { 525 span->debugAlignedEnd(1, fPts[SkPathOpsVerbToPoints(fVerb)]); 526 } 527 if (this->collapsed()) { 528 const SkOpSpan* span = &fHead; 529 do { 530 if (span->windValue()) { 531 glitches->record(kCollapsedWindValue_Glitch, id, span); 532 } 533 if (span->oppValue()) { 534 glitches->record(kCollapsedOppValue_Glitch, id, span); 535 } 536 if (!span->done()) { 537 glitches->record(kCollapsedDone_Glitch, id, span); 538 } 539 } while ((span = span->next()->upCastable())); 540 } 541 } 542 #endif 543 544 #if DEBUG_ANGLE 545 void SkOpSegment::debugCheckAngleCoin() const { 546 const SkOpSpanBase* base = &fHead; 547 const SkOpSpan* span; 548 do { 549 const SkOpAngle* angle = base->fromAngle(); 550 if (angle && angle->fCheckCoincidence) { 551 angle->debugCheckNearCoincidence(); 552 } 553 if (base->final()) { 554 break; 555 } 556 span = base->upCast(); 557 angle = span->toAngle(); 558 if (angle && angle->fCheckCoincidence) { 559 angle->debugCheckNearCoincidence(); 560 } 561 } while ((base = span->next())); 562 } 563 #endif 564 565 #if DEBUG_COINCIDENCE 566 // this mimics the order of the checks in handle coincidence 567 void SkOpSegment::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { 568 debugMoveMultiples(id, glitches); 569 debugFindCollapsed(id, glitches); 570 debugMoveNearby(id, glitches); 571 debugAlign(id, glitches); 572 debugAddAlignIntersections(id, glitches, this->globalState()->contourHead()); 573 574 } 575 576 void SkOpSegment::debugFindCollapsed(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { 577 if (fHead.contains(&fTail)) { 578 const SkOpSpan* span = this->head(); 579 bool missingDone = false; 580 do { 581 missingDone |= !span->done(); 582 } while ((span = span->next()->upCastable())); 583 if (missingDone) { 584 glitches->record(kMissingDone_Glitch, id, &fHead); 585 } 586 if (!fHead.debugAlignedEnd(0, fHead.pt())) { 587 glitches->record(kUnalignedHead_Glitch, id, &fHead); 588 } 589 if (!fTail.aligned()) { 590 glitches->record(kUnalignedTail_Glitch, id, &fTail); 591 } 592 } 593 } 594 #endif 595 596 SkOpAngle* SkOpSegment::debugLastAngle() { 597 SkOpAngle* result = nullptr; 598 SkOpSpan* span = this->head(); 599 do { 600 if (span->toAngle()) { 601 SkASSERT(!result); 602 result = span->toAngle(); 603 } 604 } while ((span = span->next()->upCastable())); 605 SkASSERT(result); 606 return result; 607 } 608 609 #if DEBUG_COINCIDENCE 610 void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log, 611 const SkOpCoincidence* coincidences) const { 612 if (this->verb() != SkPath::kLine_Verb) { 613 return; 614 } 615 if (this->done()) { 616 return; 617 } 618 const SkOpSpan* prior = nullptr; 619 const SkOpSpanBase* spanBase = &fHead; 620 do { 621 const SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT; 622 SkASSERT(ptT->span() == spanBase); 623 while ((ptT = ptT->next()) != spanStopPtT) { 624 if (ptT->deleted()) { 625 continue; 626 } 627 SkOpSegment* opp = ptT->span()->segment(); 628 // if (opp->verb() == SkPath::kLine_Verb) { 629 // continue; 630 // } 631 if (opp->done()) { 632 continue; 633 } 634 // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence 635 if (!opp->visited()) { 636 continue; 637 } 638 if (spanBase == &fHead) { 639 continue; 640 } 641 const SkOpSpan* span = spanBase->upCastable(); 642 // FIXME?: this assumes that if the opposite segment is coincident then no more 643 // coincidence needs to be detected. This may not be true. 644 if (span && span->segment() != opp && span->containsCoincidence(opp)) { 645 continue; 646 } 647 if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) { 648 continue; 649 } 650 const SkOpPtT* priorPtT = nullptr, * priorStopPtT; 651 // find prior span containing opp segment 652 const SkOpSegment* priorOpp = nullptr; 653 const SkOpSpan* priorTest = spanBase->prev(); 654 while (!priorOpp && priorTest) { 655 priorStopPtT = priorPtT = priorTest->ptT(); 656 while ((priorPtT = priorPtT->next()) != priorStopPtT) { 657 if (priorPtT->deleted()) { 658 continue; 659 } 660 SkOpSegment* segment = priorPtT->span()->segment(); 661 if (segment == opp) { 662 prior = priorTest; 663 priorOpp = opp; 664 break; 665 } 666 } 667 priorTest = priorTest->prev(); 668 } 669 if (!priorOpp) { 670 continue; 671 } 672 const SkOpPtT* oppStart = prior->ptT(); 673 const SkOpPtT* oppEnd = spanBase->ptT(); 674 bool swapped = priorPtT->fT > ptT->fT; 675 if (swapped) { 676 SkTSwap(priorPtT, ptT); 677 SkTSwap(oppStart, oppEnd); 678 } 679 bool flipped = oppStart->fT > oppEnd->fT; 680 bool coincident = false; 681 if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) { 682 goto swapBack; 683 } 684 if (opp->verb() == SkPath::kLine_Verb) { 685 coincident = (SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppStart->fPt) || 686 SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppEnd->fPt)) && 687 (SkDPoint::ApproximatelyEqual(ptT->fPt, oppStart->fPt) || 688 SkDPoint::ApproximatelyEqual(ptT->fPt, oppEnd->fPt)); 689 } 690 if (!coincident) { 691 coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000); 692 } 693 if (coincident) { 694 log->record(kMissingCoin_Glitch, id, priorPtT, ptT, oppStart, oppEnd); 695 } 696 swapBack: 697 if (swapped) { 698 SkTSwap(priorPtT, ptT); 699 } 700 } 701 } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next())); 702 } 703 704 void SkOpSegment::debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { 705 const SkOpSpanBase* test = &fHead; 706 do { 707 int addCount = test->spanAddsCount(); 708 SkASSERT(addCount >= 1); 709 if (addCount == 1) { 710 continue; 711 } 712 const SkOpPtT* startPtT = test->ptT(); 713 const SkOpPtT* testPtT = startPtT; 714 do { // iterate through all spans associated with start 715 const SkOpSpanBase* oppSpan = testPtT->span(); 716 if (oppSpan->spanAddsCount() == addCount) { 717 continue; 718 } 719 if (oppSpan->deleted()) { 720 continue; 721 } 722 const SkOpSegment* oppSegment = oppSpan->segment(); 723 if (oppSegment == this) { 724 continue; 725 } 726 // find range of spans to consider merging 727 const SkOpSpanBase* oppPrev = oppSpan; 728 const SkOpSpanBase* oppFirst = oppSpan; 729 while ((oppPrev = oppPrev->prev())) { 730 if (!roughly_equal(oppPrev->t(), oppSpan->t())) { 731 break; 732 } 733 if (oppPrev->spanAddsCount() == addCount) { 734 continue; 735 } 736 if (oppPrev->deleted()) { 737 continue; 738 } 739 oppFirst = oppPrev; 740 } 741 const SkOpSpanBase* oppNext = oppSpan; 742 const SkOpSpanBase* oppLast = oppSpan; 743 while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) { 744 if (!roughly_equal(oppNext->t(), oppSpan->t())) { 745 break; 746 } 747 if (oppNext->spanAddsCount() == addCount) { 748 continue; 749 } 750 if (oppNext->deleted()) { 751 continue; 752 } 753 oppLast = oppNext; 754 } 755 if (oppFirst == oppLast) { 756 continue; 757 } 758 const SkOpSpanBase* oppTest = oppFirst; 759 do { 760 if (oppTest == oppSpan) { 761 continue; 762 } 763 // check to see if the candidate meets specific criteria: 764 // it contains spans of segments in test's loop but not including 'this' 765 const SkOpPtT* oppStartPtT = oppTest->ptT(); 766 const SkOpPtT* oppPtT = oppStartPtT; 767 while ((oppPtT = oppPtT->next()) != oppStartPtT) { 768 const SkOpSegment* oppPtTSegment = oppPtT->segment(); 769 if (oppPtTSegment == this) { 770 goto tryNextSpan; 771 } 772 const SkOpPtT* matchPtT = startPtT; 773 do { 774 if (matchPtT->segment() == oppPtTSegment) { 775 goto foundMatch; 776 } 777 } while ((matchPtT = matchPtT->next()) != startPtT); 778 goto tryNextSpan; 779 foundMatch: // merge oppTest and oppSpan 780 if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) { 781 SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse 782 SkASSERT(oppSpan != &oppSegment->fTail); 783 glitches->record(kMoveMultiple_Glitch, id, oppTest, oppSpan); 784 } else { 785 glitches->record(kMoveMultiple_Glitch, id, oppSpan, oppTest); 786 } 787 goto checkNextSpan; 788 } 789 tryNextSpan: 790 ; 791 } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next())); 792 } while ((testPtT = testPtT->next()) != startPtT); 793 checkNextSpan: 794 ; 795 } while ((test = test->final() ? nullptr : test->upCast()->next())); 796 } 797 798 void SkOpSegment::debugMoveNearby(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { 799 const SkOpSpanBase* spanS = &fHead; 800 do { 801 const SkOpSpanBase* test = spanS->upCast()->next(); 802 const SkOpSpanBase* next; 803 if (spanS->contains(test)) { 804 if (!test->final()) { 805 glitches->record(kUndetachedSpan_Glitch, id, test, spanS); 806 } else if (spanS != &fHead) { 807 glitches->record(kUndetachedSpan_Glitch, id, spanS, test); 808 } 809 } 810 do { // iterate through all spans associated with start 811 const SkOpPtT* startBase = spanS->ptT(); 812 next = test->final() ? nullptr : test->upCast()->next(); 813 do { 814 const SkOpPtT* testBase = test->ptT(); 815 do { 816 if (startBase == testBase) { 817 goto checkNextSpan; 818 } 819 if (testBase->duplicate()) { 820 continue; 821 } 822 if (this->match(startBase, testBase->segment(), testBase->fT, testBase->fPt)) { 823 if (test == &this->fTail) { 824 if (spanS == &fHead) { 825 glitches->record(kCollapsedSpan_Glitch, id, spanS); 826 } else { 827 glitches->record(kUnmergedSpan_Glitch, id, &this->fTail, spanS); 828 } 829 } else { 830 glitches->record(kUnmergedSpan_Glitch, id, spanS, test); 831 goto checkNextSpan; 832 } 833 } 834 } while ((testBase = testBase->next()) != test->ptT()); 835 } while ((startBase = startBase->next()) != spanS->ptT()); 836 checkNextSpan: 837 ; 838 } while ((test = next)); 839 spanS = spanS->upCast()->next(); 840 } while (!spanS->final()); 841 } 842 #endif 843 844 void SkOpSegment::debugReset() { 845 this->init(this->fPts, this->fWeight, this->contour(), this->verb()); 846 } 847 848 #if DEBUG_ACTIVE_SPANS 849 void SkOpSegment::debugShowActiveSpans() const { 850 debugValidate(); 851 if (done()) { 852 return; 853 } 854 int lastId = -1; 855 double lastT = -1; 856 const SkOpSpan* span = &fHead; 857 do { 858 if (span->done()) { 859 continue; 860 } 861 if (lastId == this->debugID() && lastT == span->t()) { 862 continue; 863 } 864 lastId = this->debugID(); 865 lastT = span->t(); 866 SkDebugf("%s id=%d", __FUNCTION__, this->debugID()); 867 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 868 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { 869 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 870 } 871 if (SkPath::kConic_Verb == fVerb) { 872 SkDebugf(" %1.9gf", fWeight); 873 } 874 const SkOpPtT* ptT = span->ptT(); 875 SkDebugf(") t=%1.9g (%1.9g,%1.9g)", ptT->fT, ptT->fPt.fX, ptT->fPt.fY); 876 SkDebugf(" tEnd=%1.9g", span->next()->t()); 877 if (span->windSum() == SK_MinS32) { 878 SkDebugf(" windSum=?"); 879 } else { 880 SkDebugf(" windSum=%d", span->windSum()); 881 } 882 if (span->oppValue() && span->oppSum() == SK_MinS32) { 883 SkDebugf(" oppSum=?"); 884 } else if (span->oppValue() || span->oppSum() != SK_MinS32) { 885 SkDebugf(" oppSum=%d", span->oppSum()); 886 } 887 SkDebugf(" windValue=%d", span->windValue()); 888 if (span->oppValue() || span->oppSum() != SK_MinS32) { 889 SkDebugf(" oppValue=%d", span->oppValue()); 890 } 891 SkDebugf("\n"); 892 } while ((span = span->next()->upCastable())); 893 } 894 #endif 895 896 #if DEBUG_MARK_DONE 897 void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) { 898 const SkPoint& pt = span->ptT()->fPt; 899 SkDebugf("%s id=%d", fun, this->debugID()); 900 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 901 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { 902 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 903 } 904 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=", 905 span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t()); 906 if (winding == SK_MinS32) { 907 SkDebugf("?"); 908 } else { 909 SkDebugf("%d", winding); 910 } 911 SkDebugf(" windSum="); 912 if (span->windSum() == SK_MinS32) { 913 SkDebugf("?"); 914 } else { 915 SkDebugf("%d", span->windSum()); 916 } 917 SkDebugf(" windValue=%d\n", span->windValue()); 918 } 919 920 void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding, 921 int oppWinding) { 922 const SkPoint& pt = span->ptT()->fPt; 923 SkDebugf("%s id=%d", fun, this->debugID()); 924 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 925 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { 926 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 927 } 928 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=", 929 span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t(), winding, oppWinding); 930 if (winding == SK_MinS32) { 931 SkDebugf("?"); 932 } else { 933 SkDebugf("%d", winding); 934 } 935 SkDebugf(" newOppSum="); 936 if (oppWinding == SK_MinS32) { 937 SkDebugf("?"); 938 } else { 939 SkDebugf("%d", oppWinding); 940 } 941 SkDebugf(" oppSum="); 942 if (span->oppSum() == SK_MinS32) { 943 SkDebugf("?"); 944 } else { 945 SkDebugf("%d", span->oppSum()); 946 } 947 SkDebugf(" windSum="); 948 if (span->windSum() == SK_MinS32) { 949 SkDebugf("?"); 950 } else { 951 SkDebugf("%d", span->windSum()); 952 } 953 SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue()); 954 } 955 956 #endif 957 958 // loop looking for a pair of angle parts that are too close to be sorted 959 /* This is called after other more simple intersection and angle sorting tests have been exhausted. 960 This should be rarely called -- the test below is thorough and time consuming. 961 This checks the distance between start points; the distance between 962 */ 963 #if DEBUG_ANGLE 964 void SkOpAngle::debugCheckNearCoincidence() const { 965 const SkOpAngle* test = this; 966 do { 967 const SkOpSegment* testSegment = test->segment(); 968 double testStartT = test->start()->t(); 969 SkDPoint testStartPt = testSegment->dPtAtT(testStartT); 970 double testEndT = test->end()->t(); 971 SkDPoint testEndPt = testSegment->dPtAtT(testEndT); 972 double testLenSq = testStartPt.distanceSquared(testEndPt); 973 SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID()); 974 double testMidT = (testStartT + testEndT) / 2; 975 const SkOpAngle* next = test; 976 while ((next = next->fNext) != this) { 977 SkOpSegment* nextSegment = next->segment(); 978 double testMidDistSq = testSegment->distSq(testMidT, next); 979 double testEndDistSq = testSegment->distSq(testEndT, next); 980 double nextStartT = next->start()->t(); 981 SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT); 982 double distSq = testStartPt.distanceSquared(nextStartPt); 983 double nextEndT = next->end()->t(); 984 double nextMidT = (nextStartT + nextEndT) / 2; 985 double nextMidDistSq = nextSegment->distSq(nextMidT, test); 986 double nextEndDistSq = nextSegment->distSq(nextEndT, test); 987 SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq, 988 testSegment->debugID(), nextSegment->debugID()); 989 SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq); 990 SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq); 991 SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq); 992 SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq); 993 SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT); 994 double nextLenSq = nextStartPt.distanceSquared(nextEndPt); 995 SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq); 996 SkDebugf("\n"); 997 } 998 test = test->fNext; 999 } while (test->fNext != this); 1000 } 1001 #endif 1002 1003 #if DEBUG_ANGLE 1004 SkString SkOpAngle::debugPart() const { 1005 SkString result; 1006 switch (this->segment()->verb()) { 1007 case SkPath::kLine_Verb: 1008 result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fCurvePart), 1009 this->segment()->debugID()); 1010 break; 1011 case SkPath::kQuad_Verb: 1012 result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fCurvePart), 1013 this->segment()->debugID()); 1014 break; 1015 case SkPath::kConic_Verb: 1016 result.printf(CONIC_DEBUG_STR " id=%d", 1017 CONIC_DEBUG_DATA(fCurvePart, fCurvePart.fConic.fWeight), 1018 this->segment()->debugID()); 1019 break; 1020 case SkPath::kCubic_Verb: 1021 result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fCurvePart), 1022 this->segment()->debugID()); 1023 break; 1024 default: 1025 SkASSERT(0); 1026 } 1027 return result; 1028 } 1029 #endif 1030 1031 #if DEBUG_SORT 1032 void SkOpAngle::debugLoop() const { 1033 const SkOpAngle* first = this; 1034 const SkOpAngle* next = this; 1035 do { 1036 next->dumpOne(true); 1037 SkDebugf("\n"); 1038 next = next->fNext; 1039 } while (next && next != first); 1040 next = first; 1041 do { 1042 next->debugValidate(); 1043 next = next->fNext; 1044 } while (next && next != first); 1045 } 1046 #endif 1047 1048 void SkOpAngle::debugValidate() const { 1049 #if DEBUG_VALIDATE 1050 const SkOpAngle* first = this; 1051 const SkOpAngle* next = this; 1052 int wind = 0; 1053 int opp = 0; 1054 int lastXor = -1; 1055 int lastOppXor = -1; 1056 do { 1057 if (next->unorderable()) { 1058 return; 1059 } 1060 const SkOpSpan* minSpan = next->start()->starter(next->end()); 1061 if (minSpan->windValue() == SK_MinS32) { 1062 return; 1063 } 1064 bool op = next->segment()->operand(); 1065 bool isXor = next->segment()->isXor(); 1066 bool oppXor = next->segment()->oppXor(); 1067 SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(0, minSpan->windValue(), DEBUG_LIMIT_WIND_SUM)); 1068 SkASSERT(!DEBUG_LIMIT_WIND_SUM 1069 || between(-DEBUG_LIMIT_WIND_SUM, minSpan->oppValue(), DEBUG_LIMIT_WIND_SUM)); 1070 bool useXor = op ? oppXor : isXor; 1071 SkASSERT(lastXor == -1 || lastXor == (int) useXor); 1072 lastXor = (int) useXor; 1073 wind += next->debugSign() * (op ? minSpan->oppValue() : minSpan->windValue()); 1074 if (useXor) { 1075 wind &= 1; 1076 } 1077 useXor = op ? isXor : oppXor; 1078 SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor); 1079 lastOppXor = (int) useXor; 1080 opp += next->debugSign() * (op ? minSpan->windValue() : minSpan->oppValue()); 1081 if (useXor) { 1082 opp &= 1; 1083 } 1084 next = next->fNext; 1085 } while (next && next != first); 1086 SkASSERT(wind == 0 || !FLAGS_runFail); 1087 SkASSERT(opp == 0 || !FLAGS_runFail); 1088 #endif 1089 } 1090 1091 void SkOpAngle::debugValidateNext() const { 1092 #if !FORCE_RELEASE 1093 const SkOpAngle* first = this; 1094 const SkOpAngle* next = first; 1095 SkTDArray<const SkOpAngle*>(angles); 1096 do { 1097 // SkASSERT_RELEASE(next->fSegment->debugContains(next)); 1098 angles.push(next); 1099 next = next->next(); 1100 if (next == first) { 1101 break; 1102 } 1103 SkASSERT_RELEASE(!angles.contains(next)); 1104 if (!next) { 1105 return; 1106 } 1107 } while (true); 1108 #endif 1109 } 1110 1111 1112 #if DEBUG_COINCIDENCE 1113 void SkOpCoincidence::debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog* log) const { 1114 // for each coincident pair, match the spans 1115 // if the spans don't match, add the mssing pt to the segment and loop it in the opposite span 1116 const SkCoincidentSpans* coin = this->fHead; 1117 if (!coin) { 1118 coin = this->fTop; 1119 } 1120 if (!coin) { 1121 return; 1122 } 1123 do { 1124 const SkOpPtT* startPtT = coin->fCoinPtTStart; 1125 const SkOpPtT* oStartPtT = coin->fOppPtTStart; 1126 SkASSERT(startPtT->contains(oStartPtT)); 1127 SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd)); 1128 const SkOpSpanBase* start = startPtT->span(); 1129 const SkOpSpanBase* oStart = oStartPtT->span(); 1130 const SkOpSpanBase* end = coin->fCoinPtTEnd->span(); 1131 const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); 1132 const SkOpSpanBase* test = start->upCast()->next(); 1133 const SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()->next(); 1134 while (test != end || oTest != oEnd) { 1135 bool bumpTest = true; 1136 bool bumpOTest = true; 1137 if (!test->ptT()->contains(oTest->ptT())) { 1138 // use t ranges to guess which one is missing 1139 double startRange = coin->fCoinPtTEnd->fT - startPtT->fT; 1140 double startPart = (test->t() - startPtT->fT) / startRange; 1141 double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT; 1142 double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange; 1143 if (startPart == oStartPart) { 1144 // data is corrupt 1145 log->record(kAddCorruptCoin_Glitch, id, start, oStart); 1146 break; 1147 } 1148 if (startPart < oStartPart) { 1149 double newT = oStartPtT->fT + oStartRange * startPart; 1150 log->record(kAddExpandedCoin_Glitch, id, oStart, newT, test->pt()); 1151 bumpOTest = false; 1152 } else { 1153 double newT = startPtT->fT + startRange * oStartPart; 1154 log->record(kAddExpandedCoin_Glitch, id, start, newT, oTest->pt()); 1155 bumpTest = false; 1156 } 1157 } 1158 if (bumpTest && test != end) { 1159 test = test->upCast()->next(); 1160 } 1161 if (bumpOTest && oTest != oEnd) { 1162 oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next(); 1163 } 1164 } 1165 } while ((coin = coin->fNext)); 1166 } 1167 1168 static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd, 1169 const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) { 1170 double denom = overE->fT - overS->fT; 1171 double start = 0 < denom ? tStart : tEnd; 1172 double end = 0 < denom ? tEnd : tStart; 1173 double sRatio = (start - overS->fT) / denom; 1174 double eRatio = (end - overS->fT) / denom; 1175 *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio; 1176 *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio; 1177 } 1178 1179 bool SkOpCoincidence::debugAddIfMissing(const SkCoincidentSpans* outer, const SkOpPtT* over1s, 1180 const SkOpPtT* over1e) const { 1181 const SkCoincidentSpans* check = this->fTop; 1182 while (check) { 1183 if (check->fCoinPtTStart->span() == over1s->span() 1184 && check->fOppPtTStart->span() == outer->fOppPtTStart->span()) { 1185 SkASSERT(check->fCoinPtTEnd->span() == over1e->span() 1186 || !fDebugState->debugRunFail()); 1187 SkASSERT(check->fOppPtTEnd->span() == outer->fOppPtTEnd->span() 1188 || !fDebugState->debugRunFail()); 1189 return false; 1190 } 1191 if (check->fCoinPtTStart->span() == outer->fCoinPtTStart->span() 1192 && check->fOppPtTStart->span() == over1s->span()) { 1193 SkASSERT(check->fCoinPtTEnd->span() == outer->fCoinPtTEnd->span() 1194 || !fDebugState->debugRunFail()); 1195 SkASSERT(check->fOppPtTEnd->span() == over1e->span() 1196 || !fDebugState->debugRunFail()); 1197 return false; 1198 } 1199 check = check->fNext; 1200 } 1201 return true; 1202 } 1203 1204 bool SkOpCoincidence::debugAddIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, 1205 const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd, 1206 SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 1207 SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const { 1208 double coinTs, coinTe, oppTs, oppTe; 1209 t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe); 1210 t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe); 1211 const SkOpSegment* coinSeg = coinPtTStart->segment(); 1212 const SkOpSegment* oppSeg = oppPtTStart->segment(); 1213 SkASSERT(coinSeg != oppSeg); 1214 const SkCoincidentSpans* check = this->fTop; 1215 ; 1216 while (check) { 1217 const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment(); 1218 const SkOpSegment* checkOppSeg; 1219 if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) { 1220 goto next; 1221 } 1222 checkOppSeg = check->fOppPtTStart->segment(); 1223 if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) { 1224 goto next; 1225 } 1226 { 1227 int cTs = coinTs; 1228 int cTe = coinTe; 1229 int oTs = oppTs; 1230 int oTe = oppTe; 1231 if (checkCoinSeg != coinSeg) { 1232 SkASSERT(checkOppSeg != oppSeg); 1233 SkTSwap(cTs, oTs); 1234 SkTSwap(cTe, oTe); 1235 } 1236 int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT) 1237 + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT) 1238 + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT) 1239 + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT); 1240 // SkASSERT(tweenCount == 0 || tweenCount == 4); 1241 if (tweenCount) { 1242 return true; 1243 } 1244 } 1245 next: 1246 check = check->fNext; 1247 } 1248 if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) { 1249 SkTSwap(oppTs, oppTe); 1250 } 1251 if (coinTs > coinTe) { 1252 SkTSwap(coinTs, coinTe); 1253 SkTSwap(oppTs, oppTe); 1254 } 1255 bool cs = coinSeg->debugAddMissing(coinTs, oppSeg); 1256 bool ce = coinSeg->debugAddMissing(coinTe, oppSeg); 1257 if (cs == ce) { 1258 return false; 1259 } 1260 return true; 1261 } 1262 1263 void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* log) const { 1264 const SkCoincidentSpans* outer = fHead; 1265 if (!outer) { 1266 return; 1267 } 1268 do { 1269 // addifmissing can modify the list that this is walking 1270 // save head so that walker can iterate over old data unperturbed 1271 // addifmissing adds to head freely then add saved head in the end 1272 const SkOpSegment* outerCoin = outer->fCoinPtTStart->segment(); 1273 SkASSERT(outerCoin == outer->fCoinPtTEnd->segment()); 1274 const SkOpSegment* outerOpp = outer->fOppPtTStart->segment(); 1275 SkASSERT(outerOpp == outer->fOppPtTEnd->segment()); 1276 const SkCoincidentSpans* inner = outer; 1277 while ((inner = inner->fNext)) { 1278 double overS, overE; 1279 const SkOpSegment* innerCoin = inner->fCoinPtTStart->segment(); 1280 SkASSERT(innerCoin == inner->fCoinPtTEnd->segment()); 1281 const SkOpSegment* innerOpp = inner->fOppPtTStart->segment(); 1282 SkASSERT(innerOpp == inner->fOppPtTEnd->segment()); 1283 if (outerCoin == innerCoin 1284 && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, 1285 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { 1286 if (this->debugAddIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, 1287 inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, 1288 outer->fOppPtTStart, outer->fOppPtTEnd, 1289 inner->fOppPtTStart, inner->fOppPtTEnd)) { 1290 log->record(kAddMissingCoin_Glitch, id, outer, inner->fCoinPtTStart); 1291 } 1292 } else if (outerCoin == innerOpp 1293 && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, 1294 inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { 1295 if (this->debugAddIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, 1296 inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, 1297 outer->fOppPtTStart, outer->fOppPtTEnd, 1298 inner->fCoinPtTStart, inner->fCoinPtTEnd)) { 1299 log->record(kAddMissingCoin_Glitch, id, outer, inner->fOppPtTStart); 1300 } 1301 } else if (outerOpp == innerCoin 1302 && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, 1303 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { 1304 if (this->debugAddIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, 1305 inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, 1306 outer->fCoinPtTStart, outer->fCoinPtTEnd, 1307 inner->fOppPtTStart, inner->fOppPtTEnd)) { 1308 log->record(kAddMissingCoin_Glitch, id, outer, inner->fCoinPtTStart); 1309 } 1310 } else if (outerOpp == innerOpp 1311 && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, 1312 inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { 1313 if (this->debugAddIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, 1314 inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, 1315 outer->fCoinPtTStart, outer->fCoinPtTEnd, 1316 inner->fCoinPtTStart, inner->fCoinPtTEnd)) { 1317 log->record(kAddMissingCoin_Glitch, id, outer, inner->fOppPtTStart); 1318 } 1319 } else if (outerCoin != innerCoin) { 1320 // check to see if outer span overlaps the inner span 1321 // look for inner segment in pt-t list 1322 // if present, and if t values are in coincident range 1323 // add two pairs of new coincidence 1324 const SkOpPtT* testS = outer->fCoinPtTStart->debugContains(innerCoin); 1325 const SkOpPtT* testE = outer->fCoinPtTEnd->debugContains(innerCoin); 1326 if (testS && testS->fT >= inner->fCoinPtTStart->fT 1327 && testE && testE->fT <= inner->fCoinPtTEnd->fT 1328 && this->testForCoincidence(outer, testS, testE)) { 1329 if (this->debugAddIfMissing(outer, testS, testE)) { 1330 log->record(kAddMissingCoin_Glitch, id, outer, testS, testE); 1331 } 1332 } else { 1333 testS = inner->fCoinPtTStart->debugContains(outerCoin); 1334 testE = inner->fCoinPtTEnd->debugContains(outerCoin); 1335 if (testS && testS->fT >= outer->fCoinPtTStart->fT 1336 && testE && testE->fT <= outer->fCoinPtTEnd->fT 1337 && this->testForCoincidence(inner, testS, testE)) { 1338 if (this->debugAddIfMissing(inner, testS, testE)) { 1339 log->record(kAddMissingCoin_Glitch, id, inner, testS, testE); 1340 } 1341 } 1342 } 1343 } 1344 } 1345 } while ((outer = outer->fNext)); 1346 } 1347 1348 bool SkOpCoincidence::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const { 1349 const SkCoincidentSpans* coin = fHead; 1350 if (!coin) { 1351 return false; 1352 } 1353 bool expanded = false; 1354 do { 1355 const SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); 1356 const SkOpSpanBase* end = coin->fCoinPtTEnd->span(); 1357 const SkOpSegment* segment = coin->fCoinPtTStart->segment(); 1358 const SkOpSegment* oppSegment = coin->fOppPtTStart->segment(); 1359 const SkOpSpan* prev = start->prev(); 1360 if (prev && prev->debugContains(oppSegment)) { 1361 double midT = (prev->t() + start->t()) / 2; 1362 if (segment->isClose(midT, oppSegment)) { 1363 log->record(kExpandCoin_Glitch, id, coin, prev); 1364 } 1365 } 1366 SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next(); 1367 if (next && next->debugContains(oppSegment)) { 1368 double midT = (end->t() + next->t()) / 2; 1369 if (segment->isClose(midT, oppSegment)) { 1370 log->record(kExpandCoin_Glitch, id, coin, next); 1371 } 1372 } 1373 } while ((coin = coin->fNext)); 1374 return expanded; 1375 } 1376 1377 void SkOpCoincidence::debugFixAligned(const char* id, SkPathOpsDebug::GlitchLog* log) const { 1378 const SkCoincidentSpans* coin = fHead; 1379 if (!coin) { 1380 return; 1381 } 1382 do { 1383 if (coin->fCoinPtTStart->deleted()) { 1384 log->record(kDeletedCoin_Glitch, id, coin, coin->fCoinPtTStart); 1385 } 1386 if (coin->fCoinPtTEnd->deleted()) { 1387 log->record(kDeletedCoin_Glitch, id, coin, coin->fCoinPtTEnd); 1388 } 1389 if (coin->fOppPtTStart->deleted()) { 1390 log->record(kDeletedCoin_Glitch, id, coin, coin->fOppPtTStart); 1391 } 1392 if (coin->fOppPtTEnd->deleted()) { 1393 log->record(kDeletedCoin_Glitch, id, coin, coin->fOppPtTEnd); 1394 } 1395 } while ((coin = coin->fNext)); 1396 coin = fHead; 1397 do { 1398 if (coin->fCoinPtTStart->collapsed(coin->fCoinPtTEnd)) { 1399 log->record(kCollapsedCoin_Glitch, id, coin, coin->fCoinPtTStart); 1400 } 1401 if (coin->fOppPtTStart->collapsed(coin->fOppPtTEnd)) { 1402 log->record(kCollapsedCoin_Glitch, id, coin, coin->fOppPtTStart); 1403 } 1404 } while ((coin = coin->fNext)); 1405 } 1406 1407 void SkOpCoincidence::debugMark(const char* id, SkPathOpsDebug::GlitchLog* log) const { 1408 const SkCoincidentSpans* coin = fHead; 1409 if (!coin) { 1410 return; 1411 } 1412 do { 1413 const SkOpSpanBase* end = coin->fCoinPtTEnd->span(); 1414 const SkOpSpanBase* oldEnd = end; 1415 const SkOpSpan* start = coin->fCoinPtTStart->span()->debugStarter(&end); 1416 const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); 1417 const SkOpSpanBase* oOldEnd = oEnd; 1418 const SkOpSpanBase* oStart = coin->fOppPtTStart->span()->debugStarter(&oEnd); 1419 bool flipped = (end == oldEnd) != (oEnd == oOldEnd); 1420 if (flipped) { 1421 SkTSwap(oStart, oEnd); 1422 } 1423 const SkOpSpanBase* next = start; 1424 const SkOpSpanBase* oNext = oStart; 1425 do { 1426 next = next->upCast()->next(); 1427 oNext = flipped ? oNext->prev() : oNext->upCast()->next(); 1428 if (next == end || oNext == oEnd) { 1429 break; 1430 } 1431 if (!next->containsCoinEnd(oNext)) { 1432 log->record(kMarkCoinEnd_Glitch, id, next, oNext); 1433 } 1434 const SkOpSpan* nextSpan = next->upCast(); 1435 const SkOpSpan* oNextSpan = oNext->upCast(); 1436 if (!nextSpan->containsCoincidence(oNextSpan)) { 1437 log->record(kMarkCoinInsert_Glitch, id, nextSpan, oNextSpan); 1438 } 1439 } while (true); 1440 } while ((coin = coin->fNext)); 1441 } 1442 #endif 1443 1444 void SkOpCoincidence::debugShowCoincidence() const { 1445 SkCoincidentSpans* span = fHead; 1446 while (span) { 1447 SkDebugf("%s - id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__, 1448 span->fCoinPtTStart->segment()->debugID(), 1449 span->fCoinPtTStart->fT, span->fCoinPtTEnd->fT); 1450 SkDebugf("%s + id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__, 1451 span->fOppPtTStart->segment()->debugID(), 1452 span->fOppPtTStart->fT, span->fOppPtTEnd->fT); 1453 span = span->fNext; 1454 } 1455 } 1456 1457 #if DEBUG_COINCIDENCE 1458 void SkOpContour::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* log) const { 1459 const SkOpSegment* segment = &fHead; 1460 do { 1461 segment->debugCheckHealth(id, log); 1462 } while ((segment = segment->next())); 1463 } 1464 1465 void SkOpContour::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log, 1466 const SkOpCoincidence* coincidence) const { 1467 const SkOpSegment* segment = &fHead; 1468 do { 1469 segment->debugMissingCoincidence(id, log, coincidence); 1470 } while ((segment = segment->next())); 1471 } 1472 #endif 1473 1474 void SkOpSegment::debugValidate() const { 1475 #if DEBUG_VALIDATE 1476 const SkOpSpanBase* span = &fHead; 1477 double lastT = -1; 1478 const SkOpSpanBase* prev = nullptr; 1479 int count = 0; 1480 int done = 0; 1481 do { 1482 if (!span->final()) { 1483 ++count; 1484 done += span->upCast()->done() ? 1 : 0; 1485 } 1486 SkASSERT(span->segment() == this); 1487 SkASSERT(!prev || prev->upCast()->next() == span); 1488 SkASSERT(!prev || prev == span->prev()); 1489 prev = span; 1490 double t = span->ptT()->fT; 1491 SkASSERT(lastT < t); 1492 lastT = t; 1493 span->debugValidate(); 1494 } while (!span->final() && (span = span->upCast()->next())); 1495 SkASSERT(count == fCount); 1496 SkASSERT(done == fDoneCount); 1497 SkASSERT(count >= fDoneCount); 1498 SkASSERT(span->final()); 1499 span->debugValidate(); 1500 #endif 1501 } 1502 1503 bool SkOpSpanBase::debugAlignedEnd(double t, const SkPoint& pt) const { 1504 SkASSERT(zero_or_one(t)); 1505 const SkOpSegment* segment = this->segment(); 1506 SkASSERT(t ? segment->lastPt() == pt : segment->pts()[0] == pt); 1507 if (!debugAlignedInner()) { 1508 return false; 1509 } 1510 if ((t ? segment->lastPt() : segment->pts()[0]) != pt) { 1511 return false; 1512 } 1513 const SkOpPtT* ptT = &this->fPtT; 1514 SkASSERT(t == ptT->fT); 1515 SkASSERT(pt == ptT->fPt); 1516 const SkOpPtT* test = ptT, * stopPtT = ptT; 1517 while ((test = test->next()) != stopPtT) { 1518 const SkOpSegment* other = test->segment(); 1519 if (other == this->segment()) { 1520 continue; 1521 } 1522 if (!zero_or_one(test->fT)) { 1523 continue; 1524 } 1525 if ((test->fT ? other->lastPt() : other->pts()[0]) != pt) { 1526 return false; 1527 } 1528 } 1529 return this->fAligned; 1530 } 1531 1532 bool SkOpSpanBase::debugAlignedInner() const { 1533 // force the spans to share points and t values 1534 const SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT; 1535 const SkPoint& pt = ptT->fPt; 1536 do { 1537 if (ptT->fPt != pt) { 1538 return false; 1539 } 1540 const SkOpSpanBase* span = ptT->span(); 1541 const SkOpPtT* test = ptT; 1542 do { 1543 if ((test = test->next()) == stopPtT) { 1544 break; 1545 } 1546 if (span == test->span() && !span->segment()->ptsDisjoint(*ptT, *test)) { 1547 return false; 1548 } 1549 } while (true); 1550 } while ((ptT = ptT->next()) != stopPtT); 1551 return true; 1552 } 1553 1554 bool SkOpSpanBase::debugCoinEndLoopCheck() const { 1555 int loop = 0; 1556 const SkOpSpanBase* next = this; 1557 SkOpSpanBase* nextCoin; 1558 do { 1559 nextCoin = next->fCoinEnd; 1560 SkASSERT(nextCoin == this || nextCoin->fCoinEnd != nextCoin); 1561 for (int check = 1; check < loop - 1; ++check) { 1562 const SkOpSpanBase* checkCoin = this->fCoinEnd; 1563 const SkOpSpanBase* innerCoin = checkCoin; 1564 for (int inner = check + 1; inner < loop; ++inner) { 1565 innerCoin = innerCoin->fCoinEnd; 1566 if (checkCoin == innerCoin) { 1567 SkDebugf("*** bad coincident end loop ***\n"); 1568 return false; 1569 } 1570 } 1571 } 1572 ++loop; 1573 } while ((next = nextCoin) && next != this); 1574 return true; 1575 } 1576 1577 bool SkOpSpanBase::debugContains(const SkOpSegment* segment) const { 1578 const SkOpPtT* start = &fPtT; 1579 const SkOpPtT* walk = start; 1580 while ((walk = walk->next()) != start) { 1581 if (walk->segment() == segment) { 1582 return true; 1583 } 1584 } 1585 return false; 1586 } 1587 1588 const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const { 1589 const SkOpSpanBase* end = *endPtr; 1590 SkASSERT(this->segment() == end->segment()); 1591 const SkOpSpanBase* result; 1592 if (t() < end->t()) { 1593 result = this; 1594 } else { 1595 result = end; 1596 *endPtr = this; 1597 } 1598 return result->upCast(); 1599 } 1600 1601 void SkOpSpanBase::debugValidate() const { 1602 #if DEBUG_VALIDATE 1603 const SkOpPtT* ptT = &fPtT; 1604 SkASSERT(ptT->span() == this); 1605 do { 1606 // SkASSERT(SkDPoint::RoughlyEqual(fPtT.fPt, ptT->fPt)); 1607 ptT->debugValidate(); 1608 ptT = ptT->next(); 1609 } while (ptT != &fPtT); 1610 SkASSERT(this->debugCoinEndLoopCheck()); 1611 if (!this->final()) { 1612 SkASSERT(this->upCast()->debugCoinLoopCheck()); 1613 } 1614 if (fFromAngle) { 1615 fFromAngle->debugValidate(); 1616 } 1617 if (!this->final() && this->upCast()->toAngle()) { 1618 this->upCast()->toAngle()->debugValidate(); 1619 } 1620 #endif 1621 } 1622 1623 bool SkOpSpan::debugCoinLoopCheck() const { 1624 int loop = 0; 1625 const SkOpSpan* next = this; 1626 SkOpSpan* nextCoin; 1627 do { 1628 nextCoin = next->fCoincident; 1629 SkASSERT(nextCoin == this || nextCoin->fCoincident != nextCoin); 1630 for (int check = 1; check < loop - 1; ++check) { 1631 const SkOpSpan* checkCoin = this->fCoincident; 1632 const SkOpSpan* innerCoin = checkCoin; 1633 for (int inner = check + 1; inner < loop; ++inner) { 1634 innerCoin = innerCoin->fCoincident; 1635 if (checkCoin == innerCoin) { 1636 SkDebugf("*** bad coincident loop ***\n"); 1637 return false; 1638 } 1639 } 1640 } 1641 ++loop; 1642 } while ((next = nextCoin) && next != this); 1643 return true; 1644 } 1645 1646 // called only by test code 1647 int SkIntersections::debugCoincidentUsed() const { 1648 if (!fIsCoincident[0]) { 1649 SkASSERT(!fIsCoincident[1]); 1650 return 0; 1651 } 1652 int count = 0; 1653 SkDEBUGCODE(int count2 = 0;) 1654 for (int index = 0; index < fUsed; ++index) { 1655 if (fIsCoincident[0] & (1 << index)) { 1656 ++count; 1657 } 1658 #ifdef SK_DEBUG 1659 if (fIsCoincident[1] & (1 << index)) { 1660 ++count2; 1661 } 1662 #endif 1663 } 1664 SkASSERT(count == count2); 1665 return count; 1666 } 1667 1668 #include "SkOpContour.h" 1669 1670 bool SkOpPtT::debugContains(const SkOpPtT* check) const { 1671 SkASSERT(this != check); 1672 const SkOpPtT* ptT = this; 1673 int links = 0; 1674 do { 1675 ptT = ptT->next(); 1676 if (ptT == check) { 1677 return true; 1678 } 1679 ++links; 1680 const SkOpPtT* test = this; 1681 for (int index = 0; index < links; ++index) { 1682 if (ptT == test) { 1683 return false; 1684 } 1685 test = test->next(); 1686 } 1687 } while (true); 1688 } 1689 1690 const SkOpPtT* SkOpPtT::debugContains(const SkOpSegment* check) const { 1691 SkASSERT(this->segment() != check); 1692 const SkOpPtT* ptT = this; 1693 int links = 0; 1694 do { 1695 ptT = ptT->next(); 1696 if (ptT->segment() == check) { 1697 return ptT; 1698 } 1699 ++links; 1700 const SkOpPtT* test = this; 1701 for (int index = 0; index < links; ++index) { 1702 if (ptT == test) { 1703 return nullptr; 1704 } 1705 test = test->next(); 1706 } 1707 } while (true); 1708 } 1709 1710 int SkOpPtT::debugLoopLimit(bool report) const { 1711 int loop = 0; 1712 const SkOpPtT* next = this; 1713 do { 1714 for (int check = 1; check < loop - 1; ++check) { 1715 const SkOpPtT* checkPtT = this->fNext; 1716 const SkOpPtT* innerPtT = checkPtT; 1717 for (int inner = check + 1; inner < loop; ++inner) { 1718 innerPtT = innerPtT->fNext; 1719 if (checkPtT == innerPtT) { 1720 if (report) { 1721 SkDebugf("*** bad ptT loop ***\n"); 1722 } 1723 return loop; 1724 } 1725 } 1726 } 1727 // there's nothing wrong with extremely large loop counts -- but this may appear to hang 1728 // by taking a very long time to figure out that no loop entry is a duplicate 1729 // -- and it's likely that a large loop count is indicative of a bug somewhere 1730 if (++loop > 1000) { 1731 SkDebugf("*** loop count exceeds 1000 ***\n"); 1732 return 1000; 1733 } 1734 } while ((next = next->fNext) && next != this); 1735 return 0; 1736 } 1737 1738 void SkOpPtT::debugValidate() const { 1739 #if DEBUG_VALIDATE 1740 SkOpGlobalState::Phase phase = contour()->globalState()->phase(); 1741 if (phase == SkOpGlobalState::kIntersecting 1742 || phase == SkOpGlobalState::kFixWinding) { 1743 return; 1744 } 1745 SkASSERT(fNext); 1746 SkASSERT(fNext != this); 1747 SkASSERT(fNext->fNext); 1748 SkASSERT(debugLoopLimit(false) == 0); 1749 #endif 1750 } 1751 1752 static void output_scalar(SkScalar num) { 1753 if (num == (int) num) { 1754 SkDebugf("%d", (int) num); 1755 } else { 1756 SkString str; 1757 str.printf("%1.9g", num); 1758 int width = (int) str.size(); 1759 const char* cStr = str.c_str(); 1760 while (cStr[width - 1] == '0') { 1761 --width; 1762 } 1763 str.resize(width); 1764 SkDebugf("%sf", str.c_str()); 1765 } 1766 } 1767 1768 static void output_points(const SkPoint* pts, int count) { 1769 for (int index = 0; index < count; ++index) { 1770 output_scalar(pts[index].fX); 1771 SkDebugf(", "); 1772 output_scalar(pts[index].fY); 1773 if (index + 1 < count) { 1774 SkDebugf(", "); 1775 } 1776 } 1777 } 1778 1779 static void showPathContours(SkPath::RawIter& iter, const char* pathName) { 1780 uint8_t verb; 1781 SkPoint pts[4]; 1782 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 1783 switch (verb) { 1784 case SkPath::kMove_Verb: 1785 SkDebugf(" %s.moveTo(", pathName); 1786 output_points(&pts[0], 1); 1787 SkDebugf(");\n"); 1788 continue; 1789 case SkPath::kLine_Verb: 1790 SkDebugf(" %s.lineTo(", pathName); 1791 output_points(&pts[1], 1); 1792 SkDebugf(");\n"); 1793 break; 1794 case SkPath::kQuad_Verb: 1795 SkDebugf(" %s.quadTo(", pathName); 1796 output_points(&pts[1], 2); 1797 SkDebugf(");\n"); 1798 break; 1799 case SkPath::kConic_Verb: 1800 SkDebugf(" %s.conicTo(", pathName); 1801 output_points(&pts[1], 2); 1802 SkDebugf(", %1.9gf);\n", iter.conicWeight()); 1803 break; 1804 case SkPath::kCubic_Verb: 1805 SkDebugf(" %s.cubicTo(", pathName); 1806 output_points(&pts[1], 3); 1807 SkDebugf(");\n"); 1808 break; 1809 case SkPath::kClose_Verb: 1810 SkDebugf(" %s.close();\n", pathName); 1811 break; 1812 default: 1813 SkDEBUGFAIL("bad verb"); 1814 return; 1815 } 1816 } 1817 } 1818 1819 static const char* gFillTypeStr[] = { 1820 "kWinding_FillType", 1821 "kEvenOdd_FillType", 1822 "kInverseWinding_FillType", 1823 "kInverseEvenOdd_FillType" 1824 }; 1825 1826 void SkPathOpsDebug::ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration) { 1827 SkPath::RawIter iter(path); 1828 #define SUPPORT_RECT_CONTOUR_DETECTION 0 1829 #if SUPPORT_RECT_CONTOUR_DETECTION 1830 int rectCount = path.isRectContours() ? path.rectContours(nullptr, nullptr) : 0; 1831 if (rectCount > 0) { 1832 SkTDArray<SkRect> rects; 1833 SkTDArray<SkPath::Direction> directions; 1834 rects.setCount(rectCount); 1835 directions.setCount(rectCount); 1836 path.rectContours(rects.begin(), directions.begin()); 1837 for (int contour = 0; contour < rectCount; ++contour) { 1838 const SkRect& rect = rects[contour]; 1839 SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop, 1840 rect.fRight, rect.fBottom, directions[contour] == SkPath::kCCW_Direction 1841 ? "SkPath::kCCW_Direction" : "SkPath::kCW_Direction"); 1842 } 1843 return; 1844 } 1845 #endif 1846 SkPath::FillType fillType = path.getFillType(); 1847 SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType); 1848 if (includeDeclaration) { 1849 SkDebugf(" SkPath %s;\n", name); 1850 } 1851 SkDebugf(" %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[fillType]); 1852 iter.setPath(path); 1853 showPathContours(iter, name); 1854 } 1855
