SkPathOpsDebug.cpp revision 81a478ca6c36aac3e53ce0373a281ac8940f4780
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#undef FAIL_IF 16#define FAIL_IF(cond, coin) \ 17 do { if (cond) log->record(kAddExpandedFail_Glitch, id, coin); } while (false) 18 19#undef FAIL_WITH_NULL_IF 20#define FAIL_WITH_NULL_IF(cond, span) \ 21 do { if (cond) log->record(kAddExpandedFail_Glitch, id, span); } while (false) 22 23#undef RETURN_FALSE_IF 24#define RETURN_FALSE_IF(cond, span) \ 25 do { if (cond) log->record(kAddExpandedFail_Glitch, id, span); } while (false) 26 27class SkCoincidentSpans; 28 29#if DEBUG_VALIDATE 30extern bool FLAGS_runFail; 31#endif 32 33#if DEBUG_SORT 34int SkPathOpsDebug::gSortCountDefault = SK_MaxS32; 35int SkPathOpsDebug::gSortCount; 36#endif 37 38#if DEBUG_ACTIVE_OP 39const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"}; 40#endif 41 42#if defined SK_DEBUG || !FORCE_RELEASE 43 44const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"}; 45 46int SkPathOpsDebug::gContourID = 0; 47int SkPathOpsDebug::gSegmentID = 0; 48 49bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase* >& chaseArray, 50 const SkOpSpanBase* span) { 51 for (int index = 0; index < chaseArray.count(); ++index) { 52 const SkOpSpanBase* entry = chaseArray[index]; 53 if (entry == span) { 54 return true; 55 } 56 } 57 return false; 58} 59#endif 60 61#if DEBUG_COINCIDENCE_VERBOSE 62enum GlitchType { 63 kAddCorruptCoin_Glitch, 64 kAddExpandedCoin_Glitch, 65 kAddExpandedFail_Glitch, 66 kAddIfCollapsed_Glitch, 67 kAddIfMissingCoin_Glitch, 68 kAddMissingCoin_Glitch, 69 kAddMissingExtend_Glitch, 70 kAddOrOverlap_Glitch, 71 kCollapsedCoin_Glitch, 72 kCollapsedDone_Glitch, 73 kCollapsedOppValue_Glitch, 74 kCollapsedSpan_Glitch, 75 kCollapsedWindValue_Glitch, 76 kDeletedCoin_Glitch, 77 kExpandCoin_Glitch, 78 kMarkCoinEnd_Glitch, 79 kMarkCoinInsert_Glitch, 80 kMarkCoinMissing_Glitch, 81 kMarkCoinStart_Glitch, 82 kMergeContained_Glitch, 83 kMergeMatches_Glitch, 84 kMissingCoin_Glitch, 85 kMissingDone_Glitch, 86 kMissingIntersection_Glitch, 87 kMoveMultiple_Glitch, 88 kMoveNearbyClearAll_Glitch, 89 kMoveNearbyClearAll2_Glitch, 90 kMoveNearbyMerge_Glitch, 91 kMoveNearbyMergeFinal_Glitch, 92 kMoveNearbyRelease_Glitch, 93 kMoveNearbyReleaseFinal_Glitch, 94 kReleasedSpan_Glitch, 95 kUnaligned_Glitch, 96 kUnalignedHead_Glitch, 97 kUnalignedTail_Glitch, 98}; 99 100static const int kGlitchType_Count = kUnalignedTail_Glitch + 1; 101 102struct SpanGlitch { 103 const char* fStage; 104 const SkOpSpanBase* fBase; 105 const SkOpSpanBase* fSuspect; 106 const SkOpSegment* fSegment; 107 const SkOpSegment* fOppSegment; 108 const SkOpPtT* fCoinSpan; 109 const SkOpPtT* fEndSpan; 110 const SkOpPtT* fOppSpan; 111 const SkOpPtT* fOppEndSpan; 112 double fStartT; 113 double fEndT; 114 double fOppStartT; 115 double fOppEndT; 116 SkPoint fPt; 117 GlitchType fType; 118}; 119 120struct SkPathOpsDebug::GlitchLog { 121 SpanGlitch* recordCommon(GlitchType type, const char* stage) { 122 SpanGlitch* glitch = fGlitches.push(); 123 glitch->fStage = stage; 124 glitch->fBase = nullptr; 125 glitch->fSuspect = nullptr; 126 glitch->fSegment = nullptr; 127 glitch->fOppSegment = nullptr; 128 glitch->fCoinSpan = nullptr; 129 glitch->fEndSpan = nullptr; 130 glitch->fOppSpan = nullptr; 131 glitch->fOppEndSpan = nullptr; 132 glitch->fStartT = SK_ScalarNaN; 133 glitch->fEndT = SK_ScalarNaN; 134 glitch->fOppStartT = SK_ScalarNaN; 135 glitch->fOppEndT = SK_ScalarNaN; 136 glitch->fPt = { SK_ScalarNaN, SK_ScalarNaN }; 137 glitch->fType = type; 138 return glitch; 139 } 140 141 void record(GlitchType type, const char* stage, const SkOpSpanBase* base, 142 const SkOpSpanBase* suspect = NULL) { 143 SpanGlitch* glitch = recordCommon(type, stage); 144 glitch->fBase = base; 145 glitch->fSuspect = suspect; 146 } 147 148 void record(GlitchType type, const char* stage, const SkOpSpanBase* base, 149 const SkOpPtT* ptT) { 150 SpanGlitch* glitch = recordCommon(type, stage); 151 glitch->fBase = base; 152 glitch->fCoinSpan = ptT; 153 } 154 155 void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin, 156 const SkCoincidentSpans* opp = NULL) { 157 SpanGlitch* glitch = recordCommon(type, stage); 158 glitch->fCoinSpan = coin->coinPtTStart(); 159 glitch->fEndSpan = coin->coinPtTEnd(); 160 if (opp) { 161 glitch->fOppSpan = opp->coinPtTStart(); 162 glitch->fOppEndSpan = opp->coinPtTEnd(); 163 } 164 } 165 166 void record(GlitchType type, const char* stage, const SkOpSpanBase* base, 167 const SkOpSegment* seg, double t, SkPoint pt) { 168 SpanGlitch* glitch = recordCommon(type, stage); 169 glitch->fBase = base; 170 glitch->fSegment = seg; 171 glitch->fStartT = t; 172 glitch->fPt = pt; 173 } 174 175 void record(GlitchType type, const char* stage, const SkOpSpanBase* base, double t, 176 SkPoint pt) { 177 SpanGlitch* glitch = recordCommon(type, stage); 178 glitch->fBase = base; 179 glitch->fStartT = t; 180 glitch->fPt = pt; 181 } 182 183 void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin, 184 const SkOpPtT* coinSpan, const SkOpPtT* endSpan) { 185 SpanGlitch* glitch = recordCommon(type, stage); 186 glitch->fCoinSpan = coin->coinPtTStart(); 187 glitch->fEndSpan = coin->coinPtTEnd(); 188 glitch->fEndSpan = endSpan; 189 glitch->fOppSpan = coinSpan; 190 glitch->fOppEndSpan = endSpan; 191 } 192 193 void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin, 194 const SkOpSpanBase* base) { 195 SpanGlitch* glitch = recordCommon(type, stage); 196 glitch->fBase = base; 197 glitch->fCoinSpan = coin->coinPtTStart(); 198 glitch->fEndSpan = coin->coinPtTEnd(); 199 } 200 201 void record(GlitchType type, const char* stage, const SkOpPtT* ptTS, const SkOpPtT* ptTE, 202 const SkOpPtT* oPtTS, const SkOpPtT* oPtTE) { 203 SpanGlitch* glitch = recordCommon(type, stage); 204 glitch->fCoinSpan = ptTS; 205 glitch->fEndSpan = ptTE; 206 glitch->fOppSpan = oPtTS; 207 glitch->fOppEndSpan = oPtTE; 208 } 209 210 void record(GlitchType type, const char* stage, const SkOpSegment* seg, double startT, 211 double endT, const SkOpSegment* oppSeg, double oppStartT, double oppEndT) { 212 SpanGlitch* glitch = recordCommon(type, stage); 213 glitch->fSegment = seg; 214 glitch->fStartT = startT; 215 glitch->fEndT = endT; 216 glitch->fOppSegment = oppSeg; 217 glitch->fOppStartT = oppStartT; 218 glitch->fOppEndT = oppEndT; 219 } 220 221 void record(GlitchType type, const char* stage, const SkOpSegment* seg, 222 const SkOpSpan* span) { 223 SpanGlitch* glitch = recordCommon(type, stage); 224 glitch->fSegment = seg; 225 glitch->fBase = span; 226 } 227 228 void record(GlitchType type, const char* stage, double t, const SkOpSpanBase* span) { 229 SpanGlitch* glitch = recordCommon(type, stage); 230 glitch->fStartT = t; 231 glitch->fBase = span; 232 } 233 234 void record(GlitchType type, const char* stage, const SkOpSegment* seg) { 235 SpanGlitch* glitch = recordCommon(type, stage); 236 glitch->fSegment = seg; 237 } 238 239 void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin, 240 const SkOpPtT* ptT) { 241 SpanGlitch* glitch = recordCommon(type, stage); 242 glitch->fCoinSpan = coin->coinPtTStart(); 243 glitch->fEndSpan = ptT; 244 } 245 246 SkTDArray<SpanGlitch> fGlitches; 247}; 248#endif 249 250void SkPathOpsDebug::ShowActiveSpans(SkOpContourHead* contourList) { 251#if DEBUG_ACTIVE_SPANS 252 SkOpContour* contour = contourList; 253 do { 254 contour->debugShowActiveSpans(); 255 } while ((contour = contour->next())); 256#endif 257} 258 259#if DEBUG_COINCIDENCE 260void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) { 261 contourList->globalState()->debugSetCheckHealth(true); 262#if DEBUG_COINCIDENCE_VERBOSE 263 GlitchLog glitches; 264 const SkOpContour* contour = contourList; 265 const SkOpCoincidence* coincidence = contour->globalState()->coincidence(); 266 coincidence->debugCheckValid(id, &glitches); // don't call validate; spans may be inconsistent 267 do { 268 contour->debugCheckHealth(id, &glitches); 269 contour->debugMissingCoincidence(id, &glitches); 270 } while ((contour = contour->next())); 271 coincidence->debugRemoveCollapsed(id, &glitches); 272 bool added; 273 coincidence->debugAddMissing(id, &glitches, &added); 274 coincidence->debugExpand(id, &glitches); 275 coincidence->debugAddExpanded(id, &glitches); 276 coincidence->debugMark(id, &glitches); 277 coincidence->debugReorder(id, &glitches); 278 unsigned mask = 0; 279 for (int index = 0; index < glitches.fGlitches.count(); ++index) { 280 const SpanGlitch& glitch = glitches.fGlitches[index]; 281 mask |= 1 << glitch.fType; 282 } 283 for (int index = 0; index < kGlitchType_Count; ++index) { 284 SkDebugf(mask & (1 << index) ? "x" : "-"); 285 } 286 SkDebugf(" %s\n", id); 287 for (int index = 0; index < glitches.fGlitches.count(); ++index) { 288 const SpanGlitch& glitch = glitches.fGlitches[index]; 289 SkDebugf("%02d: ", index); 290 if (glitch.fBase) { 291 SkDebugf(" seg/base=%d/%d", glitch.fBase->segment()->debugID(), 292 glitch.fBase->debugID()); 293 } 294 if (glitch.fSuspect) { 295 SkDebugf(" seg/base=%d/%d", glitch.fSuspect->segment()->debugID(), 296 glitch.fSuspect->debugID()); 297 } 298 if (glitch.fSegment) { 299 SkDebugf(" segment=%d", glitch.fSegment->debugID()); 300 } 301 if (glitch.fCoinSpan) { 302 SkDebugf(" coinSeg/Span/PtT=%d/%d/%d", glitch.fCoinSpan->segment()->debugID(), 303 glitch.fCoinSpan->span()->debugID(), glitch.fCoinSpan->debugID()); 304 } 305 if (glitch.fEndSpan) { 306 SkDebugf(" endSpan=%d", glitch.fEndSpan->debugID()); 307 } 308 if (glitch.fOppSpan) { 309 SkDebugf(" oppSeg/Span/PtT=%d/%d/%d", glitch.fOppSpan->segment()->debugID(), 310 glitch.fOppSpan->span()->debugID(), glitch.fOppSpan->debugID()); 311 } 312 if (glitch.fOppEndSpan) { 313 SkDebugf(" oppEndSpan=%d", glitch.fOppEndSpan->debugID()); 314 } 315 if (!SkScalarIsNaN(glitch.fStartT)) { 316 SkDebugf(" startT=%g", glitch.fStartT); 317 } 318 if (!SkScalarIsNaN(glitch.fEndT)) { 319 SkDebugf(" endT=%g", glitch.fEndT); 320 } 321 if (glitch.fOppSegment) { 322 SkDebugf(" segment=%d", glitch.fOppSegment->debugID()); 323 } 324 if (!SkScalarIsNaN(glitch.fOppStartT)) { 325 SkDebugf(" oppStartT=%g", glitch.fOppStartT); 326 } 327 if (!SkScalarIsNaN(glitch.fOppEndT)) { 328 SkDebugf(" oppEndT=%g", glitch.fOppEndT); 329 } 330 if (!SkScalarIsNaN(glitch.fPt.fX) || !SkScalarIsNaN(glitch.fPt.fY)) { 331 SkDebugf(" pt=%g,%g", glitch.fPt.fX, glitch.fPt.fY); 332 } 333 switch (glitch.fType) { 334 case kAddCorruptCoin_Glitch: SkDebugf(" AddCorruptCoin"); break; 335 case kAddExpandedCoin_Glitch: SkDebugf(" AddExpandedCoin"); break; 336 case kAddExpandedFail_Glitch: SkDebugf(" AddExpandedFail"); break; 337 case kAddIfCollapsed_Glitch: SkDebugf(" AddIfCollapsed"); break;; break; 338 case kAddIfMissingCoin_Glitch: SkDebugf(" AddIfMissingCoin"); break; 339 case kAddMissingCoin_Glitch: SkDebugf(" AddMissingCoin"); break; 340 case kAddMissingExtend_Glitch: SkDebugf(" AddMissingExtend"); break; 341 case kAddOrOverlap_Glitch: SkDebugf(" AAddOrOverlap"); break; 342 case kCollapsedCoin_Glitch: SkDebugf(" CollapsedCoin"); break; 343 case kCollapsedDone_Glitch: SkDebugf(" CollapsedDone"); break; 344 case kCollapsedOppValue_Glitch: SkDebugf(" CollapsedOppValue"); break; 345 case kCollapsedSpan_Glitch: SkDebugf(" CollapsedSpan"); break; 346 case kCollapsedWindValue_Glitch: SkDebugf(" CollapsedWindValue"); break; 347 case kDeletedCoin_Glitch: SkDebugf(" DeletedCoin"); break; 348 case kExpandCoin_Glitch: SkDebugf(" ExpandCoin"); break; 349 case kMarkCoinEnd_Glitch: SkDebugf(" MarkCoinEnd"); break; 350 case kMarkCoinInsert_Glitch: SkDebugf(" MarkCoinInsert"); break; 351 case kMarkCoinMissing_Glitch: SkDebugf(" MarkCoinMissing"); break; 352 case kMarkCoinStart_Glitch: SkDebugf(" MarkCoinStart"); break; 353 case kMergeContained_Glitch: SkDebugf(" MergeContained"); break; 354 case kMergeMatches_Glitch: SkDebugf(" MergeMatches"); break; 355 case kMissingCoin_Glitch: SkDebugf(" MissingCoin"); break; 356 case kMissingDone_Glitch: SkDebugf(" MissingDone"); break; 357 case kMissingIntersection_Glitch: SkDebugf(" MissingIntersection"); break; 358 case kMoveMultiple_Glitch: SkDebugf(" MoveMultiple"); break; 359 case kMoveNearbyClearAll_Glitch: SkDebugf(" MoveNearbyClearAll"); break; 360 case kMoveNearbyClearAll2_Glitch: SkDebugf(" MoveNearbyClearAll2"); break; 361 case kMoveNearbyMerge_Glitch: SkDebugf(" MoveNearbyMerge"); break; 362 case kMoveNearbyMergeFinal_Glitch: SkDebugf(" MoveNearbyMergeFinal"); break; 363 case kMoveNearbyRelease_Glitch: SkDebugf(" MoveNearbyRelease"); break; 364 case kMoveNearbyReleaseFinal_Glitch: SkDebugf(" MoveNearbyReleaseFinal"); break; 365 case kReleasedSpan_Glitch: SkDebugf(" ReleasedSpan"); break; 366 case kUnaligned_Glitch: SkDebugf(" Unaligned"); break; 367 case kUnalignedHead_Glitch: SkDebugf(" UnalignedHead"); break; 368 case kUnalignedTail_Glitch: SkDebugf(" UnalignedTail"); break; 369 default: SkASSERT(0); 370 } 371 SkDebugf("\n"); 372 } 373 contourList->globalState()->debugSetCheckHealth(false); 374#if 0 && DEBUG_ACTIVE_SPANS 375 SkDebugf("active after %s:\n", id); 376 ShowActiveSpans(contourList); 377#endif 378#endif 379} 380#endif 381 382#if defined SK_DEBUG || !FORCE_RELEASE 383void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) { 384 size_t len = strlen(str); 385 bool num = false; 386 for (size_t idx = 0; idx < len; ++idx) { 387 if (num && str[idx] == 'e') { 388 if (len + 2 >= bufferLen) { 389 return; 390 } 391 memmove(&str[idx + 2], &str[idx + 1], len - idx); 392 str[idx] = '*'; 393 str[idx + 1] = '^'; 394 ++len; 395 } 396 num = str[idx] >= '0' && str[idx] <= '9'; 397 } 398} 399 400bool SkPathOpsDebug::ValidWind(int wind) { 401 return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF; 402} 403 404void SkPathOpsDebug::WindingPrintf(int wind) { 405 if (wind == SK_MinS32) { 406 SkDebugf("?"); 407 } else { 408 SkDebugf("%d", wind); 409 } 410} 411#endif // defined SK_DEBUG || !FORCE_RELEASE 412 413 414#if DEBUG_SHOW_TEST_NAME 415void* SkPathOpsDebug::CreateNameStr() { return new char[DEBUG_FILENAME_STRING_LENGTH]; } 416 417void SkPathOpsDebug::DeleteNameStr(void* v) { delete[] reinterpret_cast<char*>(v); } 418 419void SkPathOpsDebug::BumpTestName(char* test) { 420 char* num = test + strlen(test); 421 while (num[-1] >= '0' && num[-1] <= '9') { 422 --num; 423 } 424 if (num[0] == '\0') { 425 return; 426 } 427 int dec = atoi(num); 428 if (dec == 0) { 429 return; 430 } 431 ++dec; 432 SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec); 433} 434#endif 435 436static void show_function_header(const char* functionName) { 437 SkDebugf("\nstatic void %s(skiatest::Reporter* reporter, const char* filename) {\n", functionName); 438 if (strcmp("skphealth_com76", functionName) == 0) { 439 SkDebugf("found it\n"); 440 } 441} 442 443static const char* gOpStrs[] = { 444 "kDifference_SkPathOp", 445 "kIntersect_SkPathOp", 446 "kUnion_SkPathOp", 447 "kXOR_PathOp", 448 "kReverseDifference_SkPathOp", 449}; 450 451const char* SkPathOpsDebug::OpStr(SkPathOp op) { 452 return gOpStrs[op]; 453} 454 455static void show_op(SkPathOp op, const char* pathOne, const char* pathTwo) { 456 SkDebugf(" testPathOp(reporter, %s, %s, %s, filename);\n", pathOne, pathTwo, gOpStrs[op]); 457 SkDebugf("}\n"); 458} 459 460SK_DECLARE_STATIC_MUTEX(gTestMutex); 461 462void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp, 463 const char* testName) { 464 SkAutoMutexAcquire ac(gTestMutex); 465 show_function_header(testName); 466 ShowOnePath(a, "path", true); 467 ShowOnePath(b, "pathB", true); 468 show_op(shapeOp, "path", "pathB"); 469} 470 471#include "SkPathOpsTypes.h" 472#include "SkIntersectionHelper.h" 473#include "SkIntersections.h" 474 475#if DEBUG_T_SECT_LOOP_COUNT 476void SkOpGlobalState::debugAddLoopCount(SkIntersections* i, const SkIntersectionHelper& wt, 477 const SkIntersectionHelper& wn) { 478 for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) { 479 SkIntersections::DebugLoop looper = (SkIntersections::DebugLoop) index; 480 if (fDebugLoopCount[index] >= i->debugLoopCount(looper)) { 481 continue; 482 } 483 fDebugLoopCount[index] = i->debugLoopCount(looper); 484 fDebugWorstVerb[index * 2] = wt.segment()->verb(); 485 fDebugWorstVerb[index * 2 + 1] = wn.segment()->verb(); 486 sk_bzero(&fDebugWorstPts[index * 8], sizeof(SkPoint) * 8); 487 memcpy(&fDebugWorstPts[index * 2 * 4], wt.pts(), 488 (SkPathOpsVerbToPoints(wt.segment()->verb()) + 1) * sizeof(SkPoint)); 489 memcpy(&fDebugWorstPts[(index * 2 + 1) * 4], wn.pts(), 490 (SkPathOpsVerbToPoints(wn.segment()->verb()) + 1) * sizeof(SkPoint)); 491 fDebugWorstWeight[index * 2] = wt.weight(); 492 fDebugWorstWeight[index * 2 + 1] = wn.weight(); 493 } 494 i->debugResetLoopCount(); 495} 496 497void SkOpGlobalState::debugDoYourWorst(SkOpGlobalState* local) { 498 for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) { 499 if (fDebugLoopCount[index] >= local->fDebugLoopCount[index]) { 500 continue; 501 } 502 fDebugLoopCount[index] = local->fDebugLoopCount[index]; 503 fDebugWorstVerb[index * 2] = local->fDebugWorstVerb[index * 2]; 504 fDebugWorstVerb[index * 2 + 1] = local->fDebugWorstVerb[index * 2 + 1]; 505 memcpy(&fDebugWorstPts[index * 2 * 4], &local->fDebugWorstPts[index * 2 * 4], 506 sizeof(SkPoint) * 8); 507 fDebugWorstWeight[index * 2] = local->fDebugWorstWeight[index * 2]; 508 fDebugWorstWeight[index * 2 + 1] = local->fDebugWorstWeight[index * 2 + 1]; 509 } 510 local->debugResetLoopCounts(); 511} 512 513static void dump_curve(SkPath::Verb verb, const SkPoint& pts, float weight) { 514 if (!verb) { 515 return; 516 } 517 const char* verbs[] = { "", "line", "quad", "conic", "cubic" }; 518 SkDebugf("%s: {{", verbs[verb]); 519 int ptCount = SkPathOpsVerbToPoints(verb); 520 for (int index = 0; index <= ptCount; ++index) { 521 SkDPoint::Dump((&pts)[index]); 522 if (index < ptCount - 1) { 523 SkDebugf(", "); 524 } 525 } 526 SkDebugf("}"); 527 if (weight != 1) { 528 SkDebugf(", "); 529 if (weight == floorf(weight)) { 530 SkDebugf("%.0f", weight); 531 } else { 532 SkDebugf("%1.9gf", weight); 533 } 534 } 535 SkDebugf("}\n"); 536} 537 538void SkOpGlobalState::debugLoopReport() { 539 const char* loops[] = { "iterations", "coinChecks", "perpCalcs" }; 540 SkDebugf("\n"); 541 for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) { 542 SkDebugf("%s: %d\n", loops[index], fDebugLoopCount[index]); 543 dump_curve(fDebugWorstVerb[index * 2], fDebugWorstPts[index * 2 * 4], 544 fDebugWorstWeight[index * 2]); 545 dump_curve(fDebugWorstVerb[index * 2 + 1], fDebugWorstPts[(index * 2 + 1) * 4], 546 fDebugWorstWeight[index * 2 + 1]); 547 } 548} 549 550void SkOpGlobalState::debugResetLoopCounts() { 551 sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount)); 552 sk_bzero(fDebugWorstVerb, sizeof(fDebugWorstVerb)); 553 sk_bzero(fDebugWorstPts, sizeof(fDebugWorstPts)); 554 sk_bzero(fDebugWorstWeight, sizeof(fDebugWorstWeight)); 555} 556#endif 557 558#ifdef SK_DEBUG 559bool SkOpGlobalState::debugRunFail() const { 560#if DEBUG_VALIDATE 561 return FLAGS_runFail; 562#else 563 return false; 564#endif 565} 566#endif 567 568#if DEBUG_T_SECT_LOOP_COUNT 569void SkIntersections::debugBumpLoopCount(DebugLoop index) { 570 fDebugLoopCount[index]++; 571} 572 573int SkIntersections::debugLoopCount(DebugLoop index) const { 574 return fDebugLoopCount[index]; 575} 576 577void SkIntersections::debugResetLoopCount() { 578 sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount)); 579} 580#endif 581 582#include "SkPathOpsCubic.h" 583#include "SkPathOpsQuad.h" 584 585SkDCubic SkDQuad::debugToCubic() const { 586 SkDCubic cubic; 587 cubic[0] = fPts[0]; 588 cubic[2] = fPts[1]; 589 cubic[3] = fPts[2]; 590 cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3; 591 cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3; 592 cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3; 593 cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3; 594 return cubic; 595} 596 597void SkDRect::debugInit() { 598 fLeft = fTop = fRight = fBottom = SK_ScalarNaN; 599} 600 601#include "SkOpAngle.h" 602#include "SkOpSegment.h" 603 604#if DEBUG_COINCIDENCE_VERBOSE 605// commented-out lines keep this in sync with addT() 606 const SkOpPtT* SkOpSegment::debugAddT(double t, const char* id, SkPathOpsDebug::GlitchLog* log) const { 607 debugValidate(); 608 SkPoint pt = this->ptAtT(t); 609 const SkOpSpanBase* span = &fHead; 610 do { 611 const SkOpPtT* result = span->ptT(); 612 if (t == result->fT || this->match(result, this, t, pt)) { 613// span->bumpSpanAdds(); 614 return result; 615 } 616 if (t < result->fT) { 617 const SkOpSpan* prev = result->span()->prev(); 618 FAIL_WITH_NULL_IF(!prev, span); 619 // marks in global state that new op span has been allocated 620 this->globalState()->setAllocatedOpSpan(); 621// span->init(this, prev, t, pt); 622 this->debugValidate(); 623// #if DEBUG_ADD_T 624// SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, 625// span->segment()->debugID(), span->debugID()); 626// #endif 627// span->bumpSpanAdds(); 628 return nullptr; 629 } 630 FAIL_WITH_NULL_IF(span != &fTail, span); 631 } while ((span = span->upCast()->next())); 632 SkASSERT(0); 633 return nullptr; // we never get here, but need this to satisfy compiler 634} 635#endif 636 637#if DEBUG_ANGLE 638void SkOpSegment::debugCheckAngleCoin() const { 639 const SkOpSpanBase* base = &fHead; 640 const SkOpSpan* span; 641 do { 642 const SkOpAngle* angle = base->fromAngle(); 643 if (angle && angle->debugCheckCoincidence()) { 644 angle->debugCheckNearCoincidence(); 645 } 646 if (base->final()) { 647 break; 648 } 649 span = base->upCast(); 650 angle = span->toAngle(); 651 if (angle && angle->debugCheckCoincidence()) { 652 angle->debugCheckNearCoincidence(); 653 } 654 } while ((base = span->next())); 655} 656#endif 657 658#if DEBUG_COINCIDENCE_VERBOSE 659// this mimics the order of the checks in handle coincidence 660void SkOpSegment::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { 661 debugMoveMultiples(id, glitches); 662 debugMoveNearby(id, glitches); 663 debugMissingCoincidence(id, glitches); 664} 665 666// commented-out lines keep this in sync with clearAll() 667void SkOpSegment::debugClearAll(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { 668 const SkOpSpan* span = &fHead; 669 do { 670 this->debugClearOne(span, id, glitches); 671 } while ((span = span->next()->upCastable())); 672 this->globalState()->coincidence()->debugRelease(id, glitches, this); 673} 674 675// commented-out lines keep this in sync with clearOne() 676void SkOpSegment::debugClearOne(const SkOpSpan* span, const char* id, SkPathOpsDebug::GlitchLog* glitches) const { 677 if (span->windValue()) glitches->record(kCollapsedWindValue_Glitch, id, span); 678 if (span->oppValue()) glitches->record(kCollapsedOppValue_Glitch, id, span); 679 if (!span->done()) glitches->record(kCollapsedDone_Glitch, id, span); 680} 681#endif 682 683SkOpAngle* SkOpSegment::debugLastAngle() { 684 SkOpAngle* result = nullptr; 685 SkOpSpan* span = this->head(); 686 do { 687 if (span->toAngle()) { 688 SkASSERT(!result); 689 result = span->toAngle(); 690 } 691 } while ((span = span->next()->upCastable())); 692 SkASSERT(result); 693 return result; 694} 695 696#if DEBUG_COINCIDENCE 697// commented-out lines keep this in sync with ClearVisited 698void SkOpSegment::DebugClearVisited(const SkOpSpanBase* span) { 699 // reset visited flag back to false 700 do { 701 const SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; 702 while ((ptT = ptT->next()) != stopPtT) { 703 const SkOpSegment* opp = ptT->segment(); 704 opp->resetDebugVisited(); 705 } 706 } while (!span->final() && (span = span->upCast()->next())); 707} 708#endif 709 710#if DEBUG_COINCIDENCE_VERBOSE 711// commented-out lines keep this in sync with missingCoincidence() 712// look for pairs of undetected coincident curves 713// assumes that segments going in have visited flag clear 714// Even though pairs of curves correct detect coincident runs, a run may be missed 715// if the coincidence is a product of multiple intersections. For instance, given 716// curves A, B, and C: 717// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near 718// the end of C that the intersection is replaced with the end of C. 719// Even though A-B correctly do not detect an intersection at point 2, 720// the resulting run from point 1 to point 2 is coincident on A and B. 721void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log) const { 722 if (this->done()) { 723 return; 724 } 725 const SkOpSpan* prior = nullptr; 726 const SkOpSpanBase* spanBase = &fHead; 727// bool result = false; 728 do { 729 const SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT; 730 SkASSERT(ptT->span() == spanBase); 731 while ((ptT = ptT->next()) != spanStopPtT) { 732 if (ptT->deleted()) { 733 continue; 734 } 735 const SkOpSegment* opp = ptT->span()->segment(); 736 if (opp->done()) { 737 continue; 738 } 739 // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence 740 if (!opp->debugVisited()) { 741 continue; 742 } 743 if (spanBase == &fHead) { 744 continue; 745 } 746 if (ptT->segment() == this) { 747 continue; 748 } 749 const SkOpSpan* span = spanBase->upCastable(); 750 // FIXME?: this assumes that if the opposite segment is coincident then no more 751 // coincidence needs to be detected. This may not be true. 752 if (span && span->segment() != opp && span->containsCoincidence(opp)) { // debug has additional condition since it may be called before inner duplicate points have been deleted 753 continue; 754 } 755 if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) { // debug has additional condition since it may be called before inner duplicate points have been deleted 756 continue; 757 } 758 const SkOpPtT* priorPtT = nullptr, * priorStopPtT; 759 // find prior span containing opp segment 760 const SkOpSegment* priorOpp = nullptr; 761 const SkOpSpan* priorTest = spanBase->prev(); 762 while (!priorOpp && priorTest) { 763 priorStopPtT = priorPtT = priorTest->ptT(); 764 while ((priorPtT = priorPtT->next()) != priorStopPtT) { 765 if (priorPtT->deleted()) { 766 continue; 767 } 768 SkOpSegment* segment = priorPtT->span()->segment(); 769 if (segment == opp) { 770 prior = priorTest; 771 priorOpp = opp; 772 break; 773 } 774 } 775 priorTest = priorTest->prev(); 776 } 777 if (!priorOpp) { 778 continue; 779 } 780 if (priorPtT == ptT) { 781 continue; 782 } 783 const SkOpPtT* oppStart = prior->ptT(); 784 const SkOpPtT* oppEnd = spanBase->ptT(); 785 bool swapped = priorPtT->fT > ptT->fT; 786 if (swapped) { 787 SkTSwap(priorPtT, ptT); 788 SkTSwap(oppStart, oppEnd); 789 } 790 const SkOpCoincidence* coincidence = this->globalState()->coincidence(); 791 const SkOpPtT* rootPriorPtT = priorPtT->span()->ptT(); 792 const SkOpPtT* rootPtT = ptT->span()->ptT(); 793 const SkOpPtT* rootOppStart = oppStart->span()->ptT(); 794 const SkOpPtT* rootOppEnd = oppEnd->span()->ptT(); 795 if (coincidence->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) { 796 goto swapBack; 797 } 798 if (testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) { 799 // mark coincidence 800#if DEBUG_COINCIDENCE_VERBOSE 801// SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__, 802// rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(), 803// rootOppEnd->debugID()); 804#endif 805 log->record(kMissingCoin_Glitch, id, priorPtT, ptT, oppStart, oppEnd); 806 // coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd); 807 // } 808#if DEBUG_COINCIDENCE 809// SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd); 810#endif 811 // result = true; 812 } 813 swapBack: 814 if (swapped) { 815 SkTSwap(priorPtT, ptT); 816 } 817 } 818 } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next())); 819 DebugClearVisited(&fHead); 820 return; 821} 822 823// commented-out lines keep this in sync with moveMultiples() 824// if a span has more than one intersection, merge the other segments' span as needed 825void SkOpSegment::debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { 826 debugValidate(); 827 const SkOpSpanBase* test = &fHead; 828 do { 829 int addCount = test->spanAddsCount(); 830 SkASSERT(addCount >= 1); 831 if (addCount == 1) { 832 continue; 833 } 834 const SkOpPtT* startPtT = test->ptT(); 835 const SkOpPtT* testPtT = startPtT; 836 do { // iterate through all spans associated with start 837 const SkOpSpanBase* oppSpan = testPtT->span(); 838 if (oppSpan->spanAddsCount() == addCount) { 839 continue; 840 } 841 if (oppSpan->deleted()) { 842 continue; 843 } 844 const SkOpSegment* oppSegment = oppSpan->segment(); 845 if (oppSegment == this) { 846 continue; 847 } 848 // find range of spans to consider merging 849 const SkOpSpanBase* oppPrev = oppSpan; 850 const SkOpSpanBase* oppFirst = oppSpan; 851 while ((oppPrev = oppPrev->prev())) { 852 if (!roughly_equal(oppPrev->t(), oppSpan->t())) { 853 break; 854 } 855 if (oppPrev->spanAddsCount() == addCount) { 856 continue; 857 } 858 if (oppPrev->deleted()) { 859 continue; 860 } 861 oppFirst = oppPrev; 862 } 863 const SkOpSpanBase* oppNext = oppSpan; 864 const SkOpSpanBase* oppLast = oppSpan; 865 while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) { 866 if (!roughly_equal(oppNext->t(), oppSpan->t())) { 867 break; 868 } 869 if (oppNext->spanAddsCount() == addCount) { 870 continue; 871 } 872 if (oppNext->deleted()) { 873 continue; 874 } 875 oppLast = oppNext; 876 } 877 if (oppFirst == oppLast) { 878 continue; 879 } 880 const SkOpSpanBase* oppTest = oppFirst; 881 do { 882 if (oppTest == oppSpan) { 883 continue; 884 } 885 // check to see if the candidate meets specific criteria: 886 // it contains spans of segments in test's loop but not including 'this' 887 const SkOpPtT* oppStartPtT = oppTest->ptT(); 888 const SkOpPtT* oppPtT = oppStartPtT; 889 while ((oppPtT = oppPtT->next()) != oppStartPtT) { 890 const SkOpSegment* oppPtTSegment = oppPtT->segment(); 891 if (oppPtTSegment == this) { 892 goto tryNextSpan; 893 } 894 const SkOpPtT* matchPtT = startPtT; 895 do { 896 if (matchPtT->segment() == oppPtTSegment) { 897 goto foundMatch; 898 } 899 } while ((matchPtT = matchPtT->next()) != startPtT); 900 goto tryNextSpan; 901 foundMatch: // merge oppTest and oppSpan 902 oppSegment->debugValidate(); 903 oppTest->debugMergeMatches(id, glitches, oppSpan); 904 oppTest->debugAddOpp(id, glitches, oppSpan); 905 oppSegment->debugValidate(); 906 goto checkNextSpan; 907 } 908 tryNextSpan: 909 ; 910 } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next())); 911 } while ((testPtT = testPtT->next()) != startPtT); 912checkNextSpan: 913 ; 914 } while ((test = test->final() ? nullptr : test->upCast()->next())); 915 debugValidate(); 916 return; 917} 918 919// commented-out lines keep this in sync with moveNearby() 920// Move nearby t values and pts so they all hang off the same span. Alignment happens later. 921void SkOpSegment::debugMoveNearby(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { 922 debugValidate(); 923 // release undeleted spans pointing to this seg that are linked to the primary span 924 const SkOpSpanBase* spanBase = &fHead; 925 do { 926 const SkOpPtT* ptT = spanBase->ptT(); 927 const SkOpPtT* headPtT = ptT; 928 while ((ptT = ptT->next()) != headPtT) { 929 const SkOpSpanBase* test = ptT->span(); 930 if (ptT->segment() == this && !ptT->deleted() && test != spanBase 931 && test->ptT() == ptT) { 932 if (test->final()) { 933 if (spanBase == &fHead) { 934 glitches->record(kMoveNearbyClearAll_Glitch, id, this); 935// return; 936 } 937 glitches->record(kMoveNearbyReleaseFinal_Glitch, id, spanBase, ptT); 938 } else if (test->prev()) { 939 glitches->record(kMoveNearbyRelease_Glitch, id, test, headPtT); 940 } 941// break; 942 } 943 } 944 spanBase = spanBase->upCast()->next(); 945 } while (!spanBase->final()); 946 947 // This loop looks for adjacent spans which are near by 948 spanBase = &fHead; 949 do { // iterate through all spans associated with start 950 const SkOpSpanBase* test = spanBase->upCast()->next(); 951 if (this->spansNearby(spanBase, test)) { 952 if (test->final()) { 953 if (spanBase->prev()) { 954 glitches->record(kMoveNearbyMergeFinal_Glitch, id, test); 955 } else { 956 glitches->record(kMoveNearbyClearAll2_Glitch, id, this); 957 // return 958 } 959 } else { 960 glitches->record(kMoveNearbyMerge_Glitch, id, spanBase); 961 } 962 } 963 spanBase = test; 964 } while (!spanBase->final()); 965 debugValidate(); 966} 967#endif 968 969void SkOpSegment::debugReset() { 970 this->init(this->fPts, this->fWeight, this->contour(), this->verb()); 971} 972 973#if DEBUG_COINCIDENCE_ORDER 974void SkOpSegment::debugSetCoinT(int index, SkScalar t) const { 975 if (fDebugBaseMax < 0 || fDebugBaseIndex == index) { 976 fDebugBaseIndex = index; 977 fDebugBaseMin = SkTMin(t, fDebugBaseMin); 978 fDebugBaseMax = SkTMax(t, fDebugBaseMax); 979 return; 980 } 981 SkASSERT(fDebugBaseMin >= t || t >= fDebugBaseMax); 982 if (fDebugLastMax < 0 || fDebugLastIndex == index) { 983 fDebugLastIndex = index; 984 fDebugLastMin = SkTMin(t, fDebugLastMin); 985 fDebugLastMax = SkTMax(t, fDebugLastMax); 986 return; 987 } 988 SkASSERT(fDebugLastMin >= t || t >= fDebugLastMax); 989 SkASSERT((t - fDebugBaseMin > 0) == (fDebugLastMin - fDebugBaseMin > 0)); 990} 991#endif 992 993#if DEBUG_ACTIVE_SPANS 994void SkOpSegment::debugShowActiveSpans() const { 995 debugValidate(); 996 if (done()) { 997 return; 998 } 999 int lastId = -1; 1000 double lastT = -1; 1001 const SkOpSpan* span = &fHead; 1002 do { 1003 if (span->done()) { 1004 continue; 1005 } 1006 if (lastId == this->debugID() && lastT == span->t()) { 1007 continue; 1008 } 1009 lastId = this->debugID(); 1010 lastT = span->t(); 1011 SkDebugf("%s id=%d", __FUNCTION__, this->debugID()); 1012 // since endpoints may have be adjusted, show actual computed curves 1013 SkDCurve curvePart; 1014 this->subDivide(span, span->next(), &curvePart); 1015 const SkDPoint* pts = curvePart.fCubic.fPts; 1016 SkDebugf(" (%1.9g,%1.9g", pts[0].fX, pts[0].fY); 1017 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { 1018 SkDebugf(" %1.9g,%1.9g", pts[vIndex].fX, pts[vIndex].fY); 1019 } 1020 if (SkPath::kConic_Verb == fVerb) { 1021 SkDebugf(" %1.9gf", curvePart.fConic.fWeight); 1022 } 1023 SkDebugf(") t=%1.9g tEnd=%1.9g", span->t(), span->next()->t()); 1024 if (span->windSum() == SK_MinS32) { 1025 SkDebugf(" windSum=?"); 1026 } else { 1027 SkDebugf(" windSum=%d", span->windSum()); 1028 } 1029 if (span->oppValue() && span->oppSum() == SK_MinS32) { 1030 SkDebugf(" oppSum=?"); 1031 } else if (span->oppValue() || span->oppSum() != SK_MinS32) { 1032 SkDebugf(" oppSum=%d", span->oppSum()); 1033 } 1034 SkDebugf(" windValue=%d", span->windValue()); 1035 if (span->oppValue() || span->oppSum() != SK_MinS32) { 1036 SkDebugf(" oppValue=%d", span->oppValue()); 1037 } 1038 SkDebugf("\n"); 1039 } while ((span = span->next()->upCastable())); 1040} 1041#endif 1042 1043#if DEBUG_MARK_DONE 1044void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) { 1045 const SkPoint& pt = span->ptT()->fPt; 1046 SkDebugf("%s id=%d", fun, this->debugID()); 1047 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 1048 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { 1049 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 1050 } 1051 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=", 1052 span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t()); 1053 if (winding == SK_MinS32) { 1054 SkDebugf("?"); 1055 } else { 1056 SkDebugf("%d", winding); 1057 } 1058 SkDebugf(" windSum="); 1059 if (span->windSum() == SK_MinS32) { 1060 SkDebugf("?"); 1061 } else { 1062 SkDebugf("%d", span->windSum()); 1063 } 1064 SkDebugf(" windValue=%d\n", span->windValue()); 1065} 1066 1067void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding, 1068 int oppWinding) { 1069 const SkPoint& pt = span->ptT()->fPt; 1070 SkDebugf("%s id=%d", fun, this->debugID()); 1071 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 1072 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { 1073 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 1074 } 1075 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=", 1076 span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t(), winding, oppWinding); 1077 if (winding == SK_MinS32) { 1078 SkDebugf("?"); 1079 } else { 1080 SkDebugf("%d", winding); 1081 } 1082 SkDebugf(" newOppSum="); 1083 if (oppWinding == SK_MinS32) { 1084 SkDebugf("?"); 1085 } else { 1086 SkDebugf("%d", oppWinding); 1087 } 1088 SkDebugf(" oppSum="); 1089 if (span->oppSum() == SK_MinS32) { 1090 SkDebugf("?"); 1091 } else { 1092 SkDebugf("%d", span->oppSum()); 1093 } 1094 SkDebugf(" windSum="); 1095 if (span->windSum() == SK_MinS32) { 1096 SkDebugf("?"); 1097 } else { 1098 SkDebugf("%d", span->windSum()); 1099 } 1100 SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue()); 1101} 1102 1103#endif 1104 1105// loop looking for a pair of angle parts that are too close to be sorted 1106/* This is called after other more simple intersection and angle sorting tests have been exhausted. 1107 This should be rarely called -- the test below is thorough and time consuming. 1108 This checks the distance between start points; the distance between 1109*/ 1110#if DEBUG_ANGLE 1111void SkOpAngle::debugCheckNearCoincidence() const { 1112 const SkOpAngle* test = this; 1113 do { 1114 const SkOpSegment* testSegment = test->segment(); 1115 double testStartT = test->start()->t(); 1116 SkDPoint testStartPt = testSegment->dPtAtT(testStartT); 1117 double testEndT = test->end()->t(); 1118 SkDPoint testEndPt = testSegment->dPtAtT(testEndT); 1119 double testLenSq = testStartPt.distanceSquared(testEndPt); 1120 SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID()); 1121 double testMidT = (testStartT + testEndT) / 2; 1122 const SkOpAngle* next = test; 1123 while ((next = next->fNext) != this) { 1124 SkOpSegment* nextSegment = next->segment(); 1125 double testMidDistSq = testSegment->distSq(testMidT, next); 1126 double testEndDistSq = testSegment->distSq(testEndT, next); 1127 double nextStartT = next->start()->t(); 1128 SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT); 1129 double distSq = testStartPt.distanceSquared(nextStartPt); 1130 double nextEndT = next->end()->t(); 1131 double nextMidT = (nextStartT + nextEndT) / 2; 1132 double nextMidDistSq = nextSegment->distSq(nextMidT, test); 1133 double nextEndDistSq = nextSegment->distSq(nextEndT, test); 1134 SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq, 1135 testSegment->debugID(), nextSegment->debugID()); 1136 SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq); 1137 SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq); 1138 SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq); 1139 SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq); 1140 SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT); 1141 double nextLenSq = nextStartPt.distanceSquared(nextEndPt); 1142 SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq); 1143 SkDebugf("\n"); 1144 } 1145 test = test->fNext; 1146 } while (test->fNext != this); 1147} 1148#endif 1149 1150#if DEBUG_ANGLE 1151SkString SkOpAngle::debugPart() const { 1152 SkString result; 1153 switch (this->segment()->verb()) { 1154 case SkPath::kLine_Verb: 1155 result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fCurvePart), 1156 this->segment()->debugID()); 1157 break; 1158 case SkPath::kQuad_Verb: 1159 result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fCurvePart), 1160 this->segment()->debugID()); 1161 break; 1162 case SkPath::kConic_Verb: 1163 result.printf(CONIC_DEBUG_STR " id=%d", 1164 CONIC_DEBUG_DATA(fCurvePart, fCurvePart.fConic.fWeight), 1165 this->segment()->debugID()); 1166 break; 1167 case SkPath::kCubic_Verb: 1168 result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fCurvePart), 1169 this->segment()->debugID()); 1170 break; 1171 default: 1172 SkASSERT(0); 1173 } 1174 return result; 1175} 1176#endif 1177 1178#if DEBUG_SORT 1179void SkOpAngle::debugLoop() const { 1180 const SkOpAngle* first = this; 1181 const SkOpAngle* next = this; 1182 do { 1183 next->dumpOne(true); 1184 SkDebugf("\n"); 1185 next = next->fNext; 1186 } while (next && next != first); 1187 next = first; 1188 do { 1189 next->debugValidate(); 1190 next = next->fNext; 1191 } while (next && next != first); 1192} 1193#endif 1194 1195void SkOpAngle::debugValidate() const { 1196#if DEBUG_COINCIDENCE 1197 if (this->globalState()->debugCheckHealth()) { 1198 return; 1199 } 1200#endif 1201#if DEBUG_VALIDATE 1202 const SkOpAngle* first = this; 1203 const SkOpAngle* next = this; 1204 int wind = 0; 1205 int opp = 0; 1206 int lastXor = -1; 1207 int lastOppXor = -1; 1208 do { 1209 if (next->unorderable()) { 1210 return; 1211 } 1212 const SkOpSpan* minSpan = next->start()->starter(next->end()); 1213 if (minSpan->windValue() == SK_MinS32) { 1214 return; 1215 } 1216 bool op = next->segment()->operand(); 1217 bool isXor = next->segment()->isXor(); 1218 bool oppXor = next->segment()->oppXor(); 1219 SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(0, minSpan->windValue(), DEBUG_LIMIT_WIND_SUM)); 1220 SkASSERT(!DEBUG_LIMIT_WIND_SUM 1221 || between(-DEBUG_LIMIT_WIND_SUM, minSpan->oppValue(), DEBUG_LIMIT_WIND_SUM)); 1222 bool useXor = op ? oppXor : isXor; 1223 SkASSERT(lastXor == -1 || lastXor == (int) useXor); 1224 lastXor = (int) useXor; 1225 wind += next->debugSign() * (op ? minSpan->oppValue() : minSpan->windValue()); 1226 if (useXor) { 1227 wind &= 1; 1228 } 1229 useXor = op ? isXor : oppXor; 1230 SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor); 1231 lastOppXor = (int) useXor; 1232 opp += next->debugSign() * (op ? minSpan->windValue() : minSpan->oppValue()); 1233 if (useXor) { 1234 opp &= 1; 1235 } 1236 next = next->fNext; 1237 } while (next && next != first); 1238 SkASSERT(wind == 0 || !FLAGS_runFail); 1239 SkASSERT(opp == 0 || !FLAGS_runFail); 1240#endif 1241} 1242 1243void SkOpAngle::debugValidateNext() const { 1244#if !FORCE_RELEASE 1245 const SkOpAngle* first = this; 1246 const SkOpAngle* next = first; 1247 SkTDArray<const SkOpAngle*>(angles); 1248 do { 1249// SkASSERT_RELEASE(next->fSegment->debugContains(next)); 1250 angles.push(next); 1251 next = next->next(); 1252 if (next == first) { 1253 break; 1254 } 1255 SkASSERT_RELEASE(!angles.contains(next)); 1256 if (!next) { 1257 return; 1258 } 1259 } while (true); 1260#endif 1261} 1262 1263#ifdef SK_DEBUG 1264void SkCoincidentSpans::debugStartCheck(const SkOpSpanBase* outer, const SkOpSpanBase* over, 1265 const SkOpGlobalState* debugState) const { 1266 SkASSERT(coinPtTEnd()->span() == over || !debugState->debugRunFail()); 1267 SkASSERT(oppPtTEnd()->span() == outer || !debugState->debugRunFail()); 1268} 1269#endif 1270 1271#if DEBUG_COINCIDENCE_VERBOSE 1272/* Commented-out lines keep this in sync with expand */ 1273// expand the range by checking adjacent spans for coincidence 1274bool SkCoincidentSpans::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const { 1275 bool expanded = false; 1276 const SkOpSegment* segment = coinPtTStart()->segment(); 1277 const SkOpSegment* oppSegment = oppPtTStart()->segment(); 1278 do { 1279 const SkOpSpan* start = coinPtTStart()->span()->upCast(); 1280 const SkOpSpan* prev = start->prev(); 1281 const SkOpPtT* oppPtT; 1282 if (!prev || !(oppPtT = prev->contains(oppSegment))) { 1283 break; 1284 } 1285 double midT = (prev->t() + start->t()) / 2; 1286 if (!segment->isClose(midT, oppSegment)) { 1287 break; 1288 } 1289 if (log) log->record(kExpandCoin_Glitch, id, this, prev->ptT(), oppPtT); 1290 expanded = true; 1291 } while (false); // actual continues while expansion is possible 1292 do { 1293 const SkOpSpanBase* end = coinPtTEnd()->span(); 1294 SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next(); 1295 if (next && next->deleted()) { 1296 break; 1297 } 1298 const SkOpPtT* oppPtT; 1299 if (!next || !(oppPtT = next->contains(oppSegment))) { 1300 break; 1301 } 1302 double midT = (end->t() + next->t()) / 2; 1303 if (!segment->isClose(midT, oppSegment)) { 1304 break; 1305 } 1306 if (log) log->record(kExpandCoin_Glitch, id, this, next->ptT(), oppPtT); 1307 expanded = true; 1308 } while (false); // actual continues while expansion is possible 1309 return expanded; 1310} 1311 1312/* Commented-out lines keep this in sync with addExpanded */ 1313// for each coincident pair, match the spans 1314// if the spans don't match, add the mssing pt to the segment and loop it in the opposite span 1315void SkOpCoincidence::debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog* log) const { 1316 const SkCoincidentSpans* coin = this->fHead; 1317 if (!coin) { 1318 return; 1319 } 1320 do { 1321 const SkOpPtT* startPtT = coin->coinPtTStart(); 1322 const SkOpPtT* oStartPtT = coin->oppPtTStart(); 1323 SkASSERT(startPtT->contains(oStartPtT)); 1324 SkASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd())); 1325 const SkOpSpanBase* start = startPtT->span(); 1326 const SkOpSpanBase* oStart = oStartPtT->span(); 1327 const SkOpSpanBase* end = coin->coinPtTEnd()->span(); 1328 const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span(); 1329 FAIL_IF(oEnd->deleted(), coin); 1330 FAIL_IF(!start->upCastable(), coin); 1331 const SkOpSpanBase* test = start->upCast()->next(); 1332 const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next(); 1333 if (!oTest) { 1334 return; 1335 } 1336 while (test != end || oTest != oEnd) { 1337 if (!test->ptT()->contains(oTest->segment()) 1338 || !oTest->ptT()->contains(start->segment())) { 1339 // use t ranges to guess which one is missing 1340 double startRange = coin->coinPtTEnd()->fT - startPtT->fT; 1341 FAIL_IF(!startRange, coin); 1342 double startPart = (test->t() - startPtT->fT) / startRange; 1343 double oStartRange = coin->oppPtTEnd()->fT - oStartPtT->fT; 1344 FAIL_IF(!oStartRange, coin); 1345 double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange; 1346 FAIL_IF(startPart == oStartPart, coin); 1347 bool startOver = false; 1348 if (startPart < oStartPart) 1349 log->record(kAddExpandedCoin_Glitch, id, // strange debug formatting lines up with original 1350 oStartPtT->fT + oStartRange * startPart, test); 1351 else log->record(kAddExpandedCoin_Glitch, id, 1352 startPtT->fT + startRange * oStartPart, oTest); 1353 if (false) { 1354 SkASSERT(0); 1355 return; 1356 } 1357 if (startOver) { 1358 test = start; 1359 oTest = oStart; 1360 } 1361 } 1362 if (test != end) { 1363 if (!test->upCastable()) { 1364 return; 1365 } 1366 test = test->upCast()->next(); 1367 } 1368 if (oTest != oEnd) { 1369 oTest = coin->flipped() ? oTest->prev() : oTest->upCast()->next(); 1370 if (!oTest) { 1371 return; 1372 } 1373 } 1374 } 1375 } while ((coin = coin->next())); 1376 return; 1377} 1378 1379/* Commented-out lines keep this in sync with addIfMissing() */ 1380void SkOpCoincidence::debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* outer, const SkOpPtT* over1s, 1381 const SkOpPtT* over1e) const { 1382// SkASSERT(fTop); 1383 if (fTop && alreadyAdded(fTop, outer, over1s, over1e)) { // in debug, fTop may be null 1384 return; 1385 } 1386 if (fHead && alreadyAdded(fHead, outer, over1s, over1e)) { 1387 return; 1388 } 1389 log->record(kAddIfMissingCoin_Glitch, id, outer->coinPtTStart(), outer->coinPtTEnd(), over1s, over1e); 1390 this->debugValidate(); 1391 return; 1392} 1393 1394/* Commented-out lines keep this in sync addIfMissing() */ 1395// note that over1s, over1e, over2s, over2e are ordered 1396void SkOpCoincidence::debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpPtT* over1s, const SkOpPtT* over2s, 1397 double tStart, double tEnd, const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, bool* added, 1398 const SkOpPtT* over1e, const SkOpPtT* over2e) const { 1399 SkASSERT(tStart < tEnd); 1400 SkASSERT(over1s->fT < over1e->fT); 1401 SkASSERT(between(over1s->fT, tStart, over1e->fT)); 1402 SkASSERT(between(over1s->fT, tEnd, over1e->fT)); 1403 SkASSERT(over2s->fT < over2e->fT); 1404 SkASSERT(between(over2s->fT, tStart, over2e->fT)); 1405 SkASSERT(between(over2s->fT, tEnd, over2e->fT)); 1406 SkASSERT(over1s->segment() == over1e->segment()); 1407 SkASSERT(over2s->segment() == over2e->segment()); 1408 SkASSERT(over1s->segment() == over2s->segment()); 1409 SkASSERT(over1s->segment() != coinSeg); 1410 SkASSERT(over1s->segment() != oppSeg); 1411 SkASSERT(coinSeg != oppSeg); 1412 double coinTs, coinTe, oppTs, oppTe; 1413 coinTs = TRange(over1s, tStart, coinSeg SkDEBUGPARAMS(over1e)); 1414 coinTe = TRange(over1s, tEnd, coinSeg SkDEBUGPARAMS(over1e)); 1415 if (coinSeg->collapsed(coinTs, coinTe)) { 1416 return log->record(kAddIfCollapsed_Glitch, id, coinSeg); 1417 } 1418 oppTs = TRange(over2s, tStart, oppSeg SkDEBUGPARAMS(over2e)); 1419 oppTe = TRange(over2s, tEnd, oppSeg SkDEBUGPARAMS(over2e)); 1420 if (oppSeg->collapsed(oppTs, oppTe)) { 1421 return log->record(kAddIfCollapsed_Glitch, id, oppSeg); 1422 } 1423 if (coinTs > coinTe) { 1424 SkTSwap(coinTs, coinTe); 1425 SkTSwap(oppTs, oppTe); 1426 } 1427 return this->debugAddOrOverlap(id, log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added 1428 ); 1429} 1430 1431/* Commented-out lines keep this in sync addOrOverlap() */ 1432// If this is called by addEndMovedSpans(), a returned false propogates out to an abort. 1433// If this is called by AddIfMissing(), a returned false indicates there was nothing to add 1434void SkOpCoincidence::debugAddOrOverlap(const char* id, SkPathOpsDebug::GlitchLog* log, 1435 const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, 1436 double coinTs, double coinTe, double oppTs, double oppTe, bool* added) const { 1437 SkTDArray<SkCoincidentSpans*> overlaps; 1438 SkASSERT(!fTop); // this is (correctly) reversed in addifMissing() 1439 if (fTop && !this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, 1440 &overlaps)) { 1441 return; 1442 } 1443 if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs, 1444 coinTe, oppTs, oppTe, &overlaps)) { 1445 return; 1446 } 1447 const SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr; 1448 for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing 1449 const SkCoincidentSpans* test = overlaps[index]; 1450 if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) { 1451 log->record(kAddOrOverlap_Glitch, id, overlap, test->coinPtTStart()); 1452 } 1453 if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) { 1454 log->record(kAddOrOverlap_Glitch, id, overlap, test->coinPtTEnd()); 1455 } 1456 if (overlap->flipped() 1457 ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT 1458 : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) { 1459 log->record(kAddOrOverlap_Glitch, id, overlap, test->oppPtTStart()); 1460 } 1461 if (overlap->flipped() 1462 ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT 1463 : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) { 1464 log->record(kAddOrOverlap_Glitch, id, overlap, test->oppPtTEnd()); 1465 } 1466 if (!fHead) { this->debugRelease(id, log, fHead, test); 1467 this->debugRelease(id, log, fTop, test); 1468 } 1469 } 1470 const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg); 1471 const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg); 1472 RETURN_FALSE_IF(overlap && cs && ce && overlap->contains(cs, ce), coinSeg); 1473 RETURN_FALSE_IF(cs != ce || !cs, coinSeg); 1474 const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg); 1475 const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg); 1476 RETURN_FALSE_IF(overlap && os && oe && overlap->contains(os, oe), oppSeg); 1477 SkASSERT(true || !cs || !cs->deleted()); 1478 SkASSERT(true || !os || !os->deleted()); 1479 SkASSERT(true || !ce || !ce->deleted()); 1480 SkASSERT(true || !oe || !oe->deleted()); 1481 const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr; 1482 const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr; 1483 RETURN_FALSE_IF(csExisting && csExisting == ceExisting, coinSeg); 1484 RETURN_FALSE_IF(csExisting && (csExisting == ce || 1485 csExisting->contains(ceExisting ? ceExisting : ce)), coinSeg); 1486 RETURN_FALSE_IF(ceExisting && (ceExisting == cs || 1487 ceExisting->contains(csExisting ? csExisting : cs)), coinSeg); 1488 const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr; 1489 const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr; 1490 RETURN_FALSE_IF(osExisting && osExisting == oeExisting, oppSeg); 1491 RETURN_FALSE_IF(osExisting && (osExisting == oe || 1492 osExisting->contains(oeExisting ? oeExisting : oe)), oppSeg); 1493 RETURN_FALSE_IF(oeExisting && (oeExisting == os || 1494 oeExisting->contains(osExisting ? osExisting : os)), oppSeg); 1495 bool csDeleted = false, osDeleted = false, ceDeleted = false, oeDeleted = false; 1496 this->debugValidate(); 1497 if (!cs || !os) { 1498 if (!cs) 1499 cs = coinSeg->debugAddT(coinTs, id, log); 1500 if (!os) 1501 os = oppSeg->debugAddT(oppTs, id, log); 1502// RETURN_FALSE_IF(callerAborts, !csWritable || !osWritable); 1503 if (cs && os) cs->span()->debugAddOpp(id, log, os->span()); 1504// cs = csWritable; 1505// os = osWritable->active(); 1506 RETURN_FALSE_IF((ce && ce->deleted()) || (oe && oe->deleted()), coinSeg); 1507 } 1508 if (!ce || !oe) { 1509 if (!ce) 1510 ce = coinSeg->debugAddT(coinTe, id, log); 1511 if (!oe) 1512 oe = oppSeg->debugAddT(oppTe, id, log); 1513 if (ce && oe) ce->span()->debugAddOpp(id, log, oe->span()); 1514// ce = ceWritable; 1515// oe = oeWritable; 1516 } 1517 this->debugValidate(); 1518 RETURN_FALSE_IF(csDeleted, coinSeg); 1519 RETURN_FALSE_IF(osDeleted, oppSeg); 1520 RETURN_FALSE_IF(ceDeleted, coinSeg); 1521 RETURN_FALSE_IF(oeDeleted, oppSeg); 1522 RETURN_FALSE_IF(!cs || !ce || cs == ce || cs->contains(ce) || !os || !oe || os == oe || os->contains(oe), coinSeg); 1523 bool result = true; 1524 if (overlap) { 1525 if (overlap->coinPtTStart()->segment() == coinSeg) { 1526 log->record(kAddMissingExtend_Glitch, id, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe); 1527 } else { 1528 if (oppTs > oppTe) { 1529 SkTSwap(coinTs, coinTe); 1530 SkTSwap(oppTs, oppTe); 1531 } 1532 log->record(kAddMissingExtend_Glitch, id, oppSeg, oppTs, oppTe, coinSeg, coinTs, coinTe); 1533 } 1534#if 0 && DEBUG_COINCIDENCE_VERBOSE 1535 if (result) { 1536 overlap->debugShow(); 1537 } 1538#endif 1539 } else { 1540 log->record(kAddMissingCoin_Glitch, id, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe); 1541#if 0 && DEBUG_COINCIDENCE_VERBOSE 1542 fHead->debugShow(); 1543#endif 1544 } 1545 this->debugValidate(); 1546 return (void) result; 1547} 1548 1549// Extra commented-out lines keep this in sync with addMissing() 1550/* detects overlaps of different coincident runs on same segment */ 1551/* does not detect overlaps for pairs without any segments in common */ 1552// returns true if caller should loop again 1553void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* log, bool* added) const { 1554 const SkCoincidentSpans* outer = fHead; 1555 if (!outer) { 1556 return; 1557 } 1558 // bool added = false; 1559 // fTop = outer; 1560 // fHead = nullptr; 1561 do { 1562 // addifmissing can modify the list that this is walking 1563 // save head so that walker can iterate over old data unperturbed 1564 // addifmissing adds to head freely then add saved head in the end 1565 const SkOpPtT* ocs = outer->coinPtTStart(); 1566 SkASSERT(!ocs->deleted()); 1567 const SkOpSegment* outerCoin = ocs->segment(); 1568 SkASSERT(!outerCoin->done()); // if it's done, should have already been removed from list 1569 const SkOpPtT* oos = outer->oppPtTStart(); 1570 SkASSERT(!oos->deleted()); 1571 const SkOpSegment* outerOpp = oos->segment(); 1572 SkASSERT(!outerOpp->done()); 1573// SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin); 1574// SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp); 1575 const SkCoincidentSpans* inner = outer; 1576 while ((inner = inner->next())) { 1577 this->debugValidate(); 1578 double overS, overE; 1579 const SkOpPtT* ics = inner->coinPtTStart(); 1580 SkASSERT(!ics->deleted()); 1581 const SkOpSegment* innerCoin = ics->segment(); 1582 SkASSERT(!innerCoin->done()); 1583 const SkOpPtT* ios = inner->oppPtTStart(); 1584 SkASSERT(!ios->deleted()); 1585 const SkOpSegment* innerOpp = ios->segment(); 1586 SkASSERT(!innerOpp->done()); 1587// SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin); 1588// SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp); 1589 if (outerCoin == innerCoin) { 1590 const SkOpPtT* oce = outer->coinPtTEnd(); 1591 SkASSERT(!oce->deleted()); 1592 const SkOpPtT* ice = inner->coinPtTEnd(); 1593 SkASSERT(!ice->deleted()); 1594 if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) { 1595 this->debugAddIfMissing(id, log, ocs->starter(oce), ics->starter(ice), 1596 overS, overE, outerOpp, innerOpp, added, 1597 ocs->debugEnder(oce), 1598 ics->debugEnder(ice)); 1599 } 1600 } else if (outerCoin == innerOpp) { 1601 const SkOpPtT* oce = outer->coinPtTEnd(); 1602 SkASSERT(!oce->deleted()); 1603 const SkOpPtT* ioe = inner->oppPtTEnd(); 1604 SkASSERT(!ioe->deleted()); 1605 if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) { 1606 this->debugAddIfMissing(id, log, ocs->starter(oce), ios->starter(ioe), 1607 overS, overE, outerOpp, innerCoin, added, 1608 ocs->debugEnder(oce), 1609 ios->debugEnder(ioe)); 1610 } 1611 } else if (outerOpp == innerCoin) { 1612 const SkOpPtT* ooe = outer->oppPtTEnd(); 1613 SkASSERT(!ooe->deleted()); 1614 const SkOpPtT* ice = inner->coinPtTEnd(); 1615 SkASSERT(!ice->deleted()); 1616 SkASSERT(outerCoin != innerOpp); 1617 if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) { 1618 this->debugAddIfMissing(id, log, oos->starter(ooe), ics->starter(ice), 1619 overS, overE, outerCoin, innerOpp, added, 1620 oos->debugEnder(ooe), 1621 ics->debugEnder(ice)); 1622 } 1623 } else if (outerOpp == innerOpp) { 1624 const SkOpPtT* ooe = outer->oppPtTEnd(); 1625 SkASSERT(!ooe->deleted()); 1626 const SkOpPtT* ioe = inner->oppPtTEnd(); 1627 SkASSERT(!ioe->deleted()); 1628 SkASSERT(outerCoin != innerCoin); 1629 if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) { 1630 this->debugAddIfMissing(id, log, oos->starter(ooe), ios->starter(ioe), 1631 overS, overE, outerCoin, innerCoin, added, 1632 oos->debugEnder(ooe), 1633 ios->debugEnder(ioe)); 1634 } 1635 } 1636 this->debugValidate(); 1637 } 1638 } while ((outer = outer->next())); 1639 // this->restoreHead(); 1640 return; 1641} 1642 1643// Commented-out lines keep this in sync with release() 1644void SkOpCoincidence::debugRelease(const char* id, SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* coin, const SkCoincidentSpans* remove) const { 1645 const SkCoincidentSpans* head = coin; 1646 const SkCoincidentSpans* prev = nullptr; 1647 const SkCoincidentSpans* next; 1648 do { 1649 next = coin->next(); 1650 if (coin == remove) { 1651 if (prev) { 1652// prev->setNext(next); 1653 } else if (head == fHead) { 1654// fHead = next; 1655 } else { 1656// fTop = next; 1657 } 1658 log->record(kReleasedSpan_Glitch, id, coin); 1659 } 1660 prev = coin; 1661 } while ((coin = next)); 1662 return; 1663} 1664 1665void SkOpCoincidence::debugRelease(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSegment* deleted) const { 1666 const SkCoincidentSpans* coin = fHead; 1667 if (!coin) { 1668 return; 1669 } 1670 do { 1671 if (coin->coinPtTStart()->segment() == deleted 1672 || coin->coinPtTEnd()->segment() == deleted 1673 || coin->oppPtTStart()->segment() == deleted 1674 || coin->oppPtTEnd()->segment() == deleted) { 1675 log->record(kReleasedSpan_Glitch, id, coin); 1676 } 1677 } while ((coin = coin->next())); 1678} 1679 1680 1681// Commented-out lines keep this in sync with reorder() 1682// iterate through all coincident pairs, looking for ranges greater than 1 1683// if found, see if the opposite pair can match it -- which may require 1684// reordering the ptT pairs 1685void SkOpCoincidence::debugReorder(const char* id, SkPathOpsDebug::GlitchLog* log) const { 1686 const SkCoincidentSpans* coin = fHead; 1687 if (!coin) { 1688 return; 1689 } 1690 do { 1691 // most commonly, concidence are one span long; check for that first 1692 int intervals = coin->spanCount(); 1693 if (intervals <= 0) { 1694 return; 1695 } 1696 if (1 == intervals) { 1697#if DEBUG_COINCIDENCE_VERBOSE 1698 // SkASSERT(!coin->debugExpand(nullptr, nullptr)); 1699#endif 1700 continue; 1701 } 1702 coin->debugExpand(id, log); 1703 if (coin->spanCount() <= 0) { 1704 return; 1705 } 1706 // check to see if every span in coin has a mate in opp 1707 const SkOpSpan* start = coin->coinPtTStart()->span()->upCast(); 1708 bool flipped = coin->flipped(); 1709 const SkOpSpanBase* oppStartBase = coin->oppPtTStart()->span(); 1710 const SkOpSpan* oppStart = flipped ? oppStartBase->prev() : oppStartBase->upCast(); 1711 SkDebugf("", start, oppStart); 1712 } while ((coin = coin->next())); 1713 return; 1714} 1715 1716// Commented-out lines keep this in sync with expand() 1717// expand the range by checking adjacent spans for coincidence 1718bool SkOpCoincidence::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const { 1719 const SkCoincidentSpans* coin = fHead; 1720 if (!coin) { 1721 return false; 1722 } 1723 bool expanded = false; 1724 do { 1725 if (coin->debugExpand(id, log)) { 1726 // check to see if multiple spans expanded so they are now identical 1727 const SkCoincidentSpans* test = fHead; 1728 do { 1729 if (coin == test) { 1730 continue; 1731 } 1732 if (coin->coinPtTStart() == test->coinPtTStart() 1733 && coin->oppPtTStart() == test->oppPtTStart()) { 1734 if (log) log->record(kExpandCoin_Glitch, id, fHead, test->coinPtTStart()); 1735 break; 1736 } 1737 } while ((test = test->next())); 1738 expanded = true; 1739 } 1740 } while ((coin = coin->next())); 1741 return expanded; 1742} 1743 1744// Commented-out lines keep this in sync with removeCollapsed() 1745void SkOpCoincidence::debugRemoveCollapsed(const char* id, SkPathOpsDebug::GlitchLog* log) const { 1746 const SkCoincidentSpans* coin = fHead; 1747 if (!coin) { 1748 return; 1749 } 1750 // SkCoincidentSpans** priorPtr = &fHead; 1751 do { 1752 if (coin->coinPtTStart() == coin->coinPtTEnd()) { 1753 return; 1754 } 1755 if (coin->oppPtTStart() == coin->oppPtTEnd()) { 1756 return; 1757 } 1758 if (coin->coinPtTStart()->collapsed(coin->coinPtTEnd())) { 1759 log->record(kCollapsedCoin_Glitch, id, coin); 1760// continue; 1761 } 1762 if (coin->oppPtTStart()->collapsed(coin->oppPtTEnd())) { 1763 log->record(kCollapsedCoin_Glitch, id, coin, coin); 1764// continue; 1765 } 1766 // priorPtr = &coin->nextPtr(); 1767 } while ((coin = coin->next())); 1768 return; 1769} 1770 1771// Commented-out lines keep this in sync with mark() 1772/* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */ 1773void SkOpCoincidence::debugMark(const char* id, SkPathOpsDebug::GlitchLog* log) const { 1774 const SkCoincidentSpans* coin = fHead; 1775 if (!coin) { 1776 return; 1777 } 1778 do { 1779 if (!coin->coinPtTStartWritable()->span()->upCastable()) { 1780 return; 1781 } 1782 const SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast(); 1783// SkASSERT(start->deleted()); 1784 const SkOpSpanBase* end = coin->coinPtTEndWritable()->span(); 1785// SkASSERT(end->deleted()); 1786 const SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span(); 1787// SkASSERT(oStart->deleted()); 1788 const SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span(); 1789// SkASSERT(oEnd->deleted()); 1790 bool flipped = coin->flipped(); 1791 if (flipped) { 1792 SkTSwap(oStart, oEnd); 1793 } 1794 /* coin and opp spans may not match up. Mark the ends, and then let the interior 1795 get marked as many times as the spans allow */ 1796 start->debugInsertCoincidence(id, log, oStart->upCast()); 1797 end->debugInsertCoinEnd(id, log, oEnd); 1798 const SkOpSegment* segment = start->segment(); 1799 const SkOpSegment* oSegment = oStart->segment(); 1800 const SkOpSpanBase* next = start; 1801 const SkOpSpanBase* oNext = oStart; 1802 while ((next = next->upCast()->next()) != end) { 1803 if (!next->upCastable()) { 1804 return; 1805 } 1806 if (next->upCast()->debugInsertCoincidence(id, log, oSegment, flipped), false) { 1807 return; 1808 } 1809 } 1810 while ((oNext = oNext->upCast()->next()) != oEnd) { 1811 if (!oNext->upCastable()) { 1812 return; 1813 } 1814 if (oNext->upCast()->debugInsertCoincidence(id, log, segment, flipped), false) { 1815 return; 1816 } 1817 } 1818 } while ((coin = coin->next())); 1819 return; 1820} 1821#endif 1822 1823#if DEBUG_COINCIDENCE_VERBOSE 1824// Commented-out lines keep this in sync with markCollapsed() 1825void SkOpCoincidence::debugMarkCollapsed(const char* id, SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* coin, const SkOpPtT* test) const { 1826 const SkCoincidentSpans* head = coin; 1827 while (coin) { 1828 if (coin->collapsed(test)) { 1829 if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) { 1830 log->record(kCollapsedCoin_Glitch, id, coin); 1831 } 1832 if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) { 1833 log->record(kCollapsedCoin_Glitch, id, coin); 1834 } 1835 this->debugRelease(id, log, head, coin); 1836 } 1837 coin = coin->next(); 1838 } 1839} 1840 1841// Commented-out lines keep this in sync with markCollapsed() 1842void SkOpCoincidence::debugMarkCollapsed(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpPtT* test) const { 1843 this->debugMarkCollapsed(id, log, fHead, test); 1844 this->debugMarkCollapsed(id, log, fTop, test); 1845} 1846#endif 1847 1848void SkCoincidentSpans::debugShow() const { 1849 SkDebugf("%s - id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__, 1850 coinPtTStart()->segment()->debugID(), 1851 coinPtTStart()->fT, coinPtTEnd()->fT); 1852 SkDebugf("%s + id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__, 1853 oppPtTStart()->segment()->debugID(), 1854 oppPtTStart()->fT, oppPtTEnd()->fT); 1855} 1856 1857void SkOpCoincidence::debugShowCoincidence() const { 1858#if DEBUG_COINCIDENCE 1859 const SkCoincidentSpans* span = fHead; 1860 while (span) { 1861 span->debugShow(); 1862 span = span->next(); 1863 } 1864#endif 1865} 1866 1867#if DEBUG_COINCIDENCE 1868static void DebugValidate(const SkOpSpanBase* next, const SkOpSpanBase* end, 1869 double oStart, double oEnd, const SkOpSegment* oSegment, 1870 const char* id, SkPathOpsDebug::GlitchLog* log) { 1871 SkASSERT(next != end); 1872 SkASSERT(!next->contains(end) || log); 1873 if (next->t() > end->t()) { 1874 SkTSwap(next, end); 1875 } 1876 do { 1877 const SkOpPtT* ptT = next->ptT(); 1878 int index = 0; 1879 bool somethingBetween; 1880 do { 1881 ++index; 1882 ptT = ptT->next(); 1883 const SkOpPtT* checkPtT = next->ptT(); 1884 if (ptT == checkPtT) { 1885 break; 1886 } 1887 bool looped = false; 1888 for (int check = 0; check < index; ++check) { 1889 if ((looped = checkPtT == ptT)) { 1890 break; 1891 } 1892 checkPtT = checkPtT->next(); 1893 } 1894 if (looped) { 1895 SkASSERT(0); 1896 break; 1897 } 1898 if (ptT->deleted()) { 1899 continue; 1900 } 1901 if (ptT->segment() != oSegment) { 1902 continue; 1903 } 1904 somethingBetween |= between(oStart, ptT->fT, oEnd); 1905 } while (true); 1906 SkASSERT(somethingBetween); 1907 } while (next != end && (next = next->upCast()->next())); 1908} 1909 1910static void DebugCheckOverlap(const SkCoincidentSpans* test, const SkCoincidentSpans* list, 1911 const char* id, SkPathOpsDebug::GlitchLog* log) { 1912 if (!list) { 1913 return; 1914 } 1915 const SkOpSegment* coinSeg = test->coinPtTStart()->segment(); 1916 SkASSERT(coinSeg == test->coinPtTEnd()->segment()); 1917 const SkOpSegment* oppSeg = test->oppPtTStart()->segment(); 1918 SkASSERT(oppSeg == test->oppPtTEnd()->segment()); 1919 SkASSERT(coinSeg != test->oppPtTStart()->segment()); 1920 SkDEBUGCODE(double tcs = test->coinPtTStart()->fT); 1921 SkASSERT(between(0, tcs, 1)); 1922 SkDEBUGCODE(double tce = test->coinPtTEnd()->fT); 1923 SkASSERT(between(0, tce, 1)); 1924 SkASSERT(tcs < tce); 1925 double tos = test->oppPtTStart()->fT; 1926 SkASSERT(between(0, tos, 1)); 1927 double toe = test->oppPtTEnd()->fT; 1928 SkASSERT(between(0, toe, 1)); 1929 SkASSERT(tos != toe); 1930 if (tos > toe) { 1931 SkTSwap(tos, toe); 1932 } 1933 do { 1934 double lcs, lce, los, loe; 1935 if (coinSeg == list->coinPtTStart()->segment()) { 1936 if (oppSeg != list->oppPtTStart()->segment()) { 1937 continue; 1938 } 1939 lcs = list->coinPtTStart()->fT; 1940 lce = list->coinPtTEnd()->fT; 1941 los = list->oppPtTStart()->fT; 1942 loe = list->oppPtTEnd()->fT; 1943 if (los > loe) { 1944 SkTSwap(los, loe); 1945 } 1946 } else if (coinSeg == list->oppPtTStart()->segment()) { 1947 if (oppSeg != list->coinPtTStart()->segment()) { 1948 continue; 1949 } 1950 lcs = list->oppPtTStart()->fT; 1951 lce = list->oppPtTEnd()->fT; 1952 if (lcs > lce) { 1953 SkTSwap(lcs, lce); 1954 } 1955 los = list->coinPtTStart()->fT; 1956 loe = list->coinPtTEnd()->fT; 1957 } else { 1958 continue; 1959 } 1960 SkASSERT(tce < lcs || lce < tcs); 1961 SkASSERT(toe < los || loe < tos); 1962 } while ((list = list->next())); 1963} 1964 1965 1966static void DebugCheckOverlapTop(const SkCoincidentSpans* head, const SkCoincidentSpans* opt, 1967 const char* id, SkPathOpsDebug::GlitchLog* log) { 1968 // check for overlapping coincident spans 1969 const SkCoincidentSpans* test = head; 1970 while (test) { 1971 const SkCoincidentSpans* next = test->next(); 1972 DebugCheckOverlap(test, next, id, log); 1973 DebugCheckOverlap(test, opt, id, log); 1974 test = next; 1975 } 1976} 1977 1978static void DebugValidate(const SkCoincidentSpans* head, const SkCoincidentSpans* opt, 1979 const char* id, SkPathOpsDebug::GlitchLog* log) { 1980 // look for pts inside coincident spans that are not inside the opposite spans 1981 const SkCoincidentSpans* coin = head; 1982 while (coin) { 1983 SkASSERT(SkOpCoincidence::Ordered(coin->coinPtTStart()->segment(), 1984 coin->oppPtTStart()->segment())); 1985 SkASSERT(coin->coinPtTStart()->span()->ptT() == coin->coinPtTStart()); 1986 SkASSERT(coin->coinPtTEnd()->span()->ptT() == coin->coinPtTEnd()); 1987 SkASSERT(coin->oppPtTStart()->span()->ptT() == coin->oppPtTStart()); 1988 SkASSERT(coin->oppPtTEnd()->span()->ptT() == coin->oppPtTEnd()); 1989 DebugValidate(coin->coinPtTStart()->span(), coin->coinPtTEnd()->span(), 1990 coin->oppPtTStart()->fT, coin->oppPtTEnd()->fT, coin->oppPtTStart()->segment(), 1991 id, log); 1992 DebugValidate(coin->oppPtTStart()->span(), coin->oppPtTEnd()->span(), 1993 coin->coinPtTStart()->fT, coin->coinPtTEnd()->fT, coin->coinPtTStart()->segment(), 1994 id, log); 1995 coin = coin->next(); 1996 } 1997 DebugCheckOverlapTop(head, opt, id, log); 1998} 1999#endif 2000 2001void SkOpCoincidence::debugValidate() const { 2002#if DEBUG_COINCIDENCE 2003 // if (fGlobalState->debugCheckHealth()) { 2004// return; 2005// } 2006 DebugValidate(fHead, fTop, nullptr, nullptr); 2007 DebugValidate(fTop, nullptr, nullptr, nullptr); 2008#endif 2009} 2010 2011#if DEBUG_COINCIDENCE_VERBOSE 2012void SkOpCoincidence::debugCheckValid(const char* id, SkPathOpsDebug::GlitchLog* log) const { 2013 DebugValidate(fHead, fTop, id, log); 2014 DebugValidate(fTop, nullptr, id, log); 2015} 2016#endif 2017 2018#if DEBUG_COINCIDENCE_VERBOSE 2019void SkOpContour::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* log) const { 2020 const SkOpSegment* segment = &fHead; 2021 do { 2022 segment->debugCheckHealth(id, log); 2023 } while ((segment = segment->next())); 2024} 2025 2026// commmented-out lines keep this aligned with missingCoincidence() 2027void SkOpContour::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log) const { 2028// SkASSERT(fCount > 0); 2029 const SkOpSegment* segment = &fHead; 2030// bool result = false; 2031 do { 2032 if (fState->angleCoincidence()) { 2033// #if DEBUG_ANGLE 2034// segment->debugCheckAngleCoin(); 2035// #endif 2036 } else if (segment->debugMissingCoincidence(id, log), false) { 2037// result = true; 2038// see FIXME in missingCoincidence() 2039// 2040// 2041// 2042 // continue; 2043 } 2044 segment = segment->next(); 2045 } while (segment); 2046 return; 2047} 2048#endif 2049 2050#if DEBUG_COINCIDENCE_ORDER 2051void SkOpSegment::debugResetCoinT() const { 2052 fDebugBaseIndex = -1; 2053 fDebugBaseMin = 1; 2054 fDebugBaseMax = -1; 2055 fDebugLastIndex = -1; 2056 fDebugLastMin = 1; 2057 fDebugLastMax = -1; 2058} 2059#endif 2060 2061void SkOpSegment::debugValidate() const { 2062#if DEBUG_COINCIDENCE_ORDER 2063 { 2064 const SkOpSpanBase* span = &fHead; 2065 do { 2066 span->debugResetCoinT(); 2067 } while (!span->final() && (span = span->upCast()->next())); 2068 span = &fHead; 2069 int index = 0; 2070 do { 2071 span->debugSetCoinT(index++); 2072 } while (!span->final() && (span = span->upCast()->next())); 2073 } 2074#endif 2075#if DEBUG_COINCIDENCE 2076 if (this->globalState()->debugCheckHealth()) { 2077 return; 2078 } 2079#endif 2080#if DEBUG_VALIDATE 2081 const SkOpSpanBase* span = &fHead; 2082 double lastT = -1; 2083 const SkOpSpanBase* prev = nullptr; 2084 int count = 0; 2085 int done = 0; 2086 do { 2087 if (!span->final()) { 2088 ++count; 2089 done += span->upCast()->done() ? 1 : 0; 2090 } 2091 SkASSERT(span->segment() == this); 2092 SkASSERT(!prev || prev->upCast()->next() == span); 2093 SkASSERT(!prev || prev == span->prev()); 2094 prev = span; 2095 double t = span->ptT()->fT; 2096 SkASSERT(lastT < t); 2097 lastT = t; 2098 span->debugValidate(); 2099 } while (!span->final() && (span = span->upCast()->next())); 2100 SkASSERT(count == fCount); 2101 SkASSERT(done == fDoneCount); 2102 SkASSERT(count >= fDoneCount); 2103 SkASSERT(span->final()); 2104 span->debugValidate(); 2105#endif 2106} 2107 2108#if DEBUG_COINCIDENCE_VERBOSE 2109 2110// Commented-out lines keep this in sync with addOpp() 2111void SkOpSpanBase::debugAddOpp(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* opp) const { 2112 const SkOpPtT* oppPrev = this->ptT()->oppPrev(opp->ptT()); 2113 if (!oppPrev) { 2114 return; 2115 } 2116 this->debugMergeMatches(id, log, opp); 2117 this->ptT()->debugAddOpp(opp->ptT(), oppPrev); 2118 this->debugCheckForCollapsedCoincidence(id, log); 2119} 2120 2121// Commented-out lines keep this in sync with checkForCollapsedCoincidence() 2122void SkOpSpanBase::debugCheckForCollapsedCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log) const { 2123 const SkOpCoincidence* coins = this->globalState()->coincidence(); 2124 if (coins->isEmpty()) { 2125 return; 2126 } 2127// the insert above may have put both ends of a coincident run in the same span 2128// for each coincident ptT in loop; see if its opposite in is also in the loop 2129// this implementation is the motivation for marking that a ptT is referenced by a coincident span 2130 const SkOpPtT* head = this->ptT(); 2131 const SkOpPtT* test = head; 2132 do { 2133 if (!test->coincident()) { 2134 continue; 2135 } 2136 coins->debugMarkCollapsed(id, log, test); 2137 } while ((test = test->next()) != head); 2138} 2139#endif 2140 2141bool SkOpSpanBase::debugCoinEndLoopCheck() const { 2142 int loop = 0; 2143 const SkOpSpanBase* next = this; 2144 SkOpSpanBase* nextCoin; 2145 do { 2146 nextCoin = next->fCoinEnd; 2147 SkASSERT(nextCoin == this || nextCoin->fCoinEnd != nextCoin); 2148 for (int check = 1; check < loop - 1; ++check) { 2149 const SkOpSpanBase* checkCoin = this->fCoinEnd; 2150 const SkOpSpanBase* innerCoin = checkCoin; 2151 for (int inner = check + 1; inner < loop; ++inner) { 2152 innerCoin = innerCoin->fCoinEnd; 2153 if (checkCoin == innerCoin) { 2154 SkDebugf("*** bad coincident end loop ***\n"); 2155 return false; 2156 } 2157 } 2158 } 2159 ++loop; 2160 } while ((next = nextCoin) && next != this); 2161 return true; 2162} 2163 2164#if DEBUG_COINCIDENCE_VERBOSE 2165// Commented-out lines keep this in sync with insertCoinEnd() 2166void SkOpSpanBase::debugInsertCoinEnd(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* coin) const { 2167 if (containsCoinEnd(coin)) { 2168// SkASSERT(coin->containsCoinEnd(this)); 2169 return; 2170 } 2171 debugValidate(); 2172// SkASSERT(this != coin); 2173 log->record(kMarkCoinEnd_Glitch, id, this, coin); 2174// coin->fCoinEnd = this->fCoinEnd; 2175// this->fCoinEnd = coinNext; 2176 debugValidate(); 2177} 2178 2179// Commented-out lines keep this in sync with mergeContained() 2180void SkOpSpanBase::debugMergeContained(const char* id, SkPathOpsDebug::GlitchLog* log, const SkPathOpsBounds& bounds, bool* deleted) const { 2181 // while adjacent spans' points are contained by the bounds, merge them 2182 const SkOpSpanBase* prev = this; 2183 const SkOpSegment* seg = this->segment(); 2184 while ((prev = prev->prev()) && bounds.contains(prev->pt()) && !seg->ptsDisjoint(prev, this)) { 2185 if (prev->prev()) { 2186 log->record(kMergeContained_Glitch, id, this, prev); 2187 } else if (this->final()) { 2188 log->record(kMergeContained_Glitch, id, this, prev); 2189 // return; 2190 } else { 2191 log->record(kMergeContained_Glitch, id, prev, this); 2192 } 2193 } 2194 const SkOpSpanBase* current = this; 2195 const SkOpSpanBase* next = this; 2196 while (next->upCastable() && (next = next->upCast()->next()) 2197 && bounds.contains(next->pt()) && !seg->ptsDisjoint(this, next)) { 2198 if (!current->prev() && next->final()) { 2199 log->record(kMergeContained_Glitch, id, next, current); 2200 current = next; 2201 } 2202 if (current->prev()) { 2203 log->record(kMergeContained_Glitch, id, next, current); 2204 current = next; 2205 } else { 2206 log->record(kMergeContained_Glitch, id, next, current); 2207 current = next; 2208 } 2209 } 2210#if DEBUG_COINCIDENCE 2211 // this->globalState()->coincidence()->debugValidate(); 2212#endif 2213} 2214 2215// Commented-out lines keep this in sync with mergeMatches() 2216// Look to see if pt-t linked list contains same segment more than once 2217// if so, and if each pt-t is directly pointed to by spans in that segment, 2218// merge them 2219// keep the points, but remove spans so that the segment doesn't have 2 or more 2220// spans pointing to the same pt-t loop at different loop elements 2221void SkOpSpanBase::debugMergeMatches(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* opp) const { 2222 const SkOpPtT* test = &fPtT; 2223 const SkOpPtT* testNext; 2224 const SkOpPtT* stop = test; 2225 do { 2226 testNext = test->next(); 2227 if (test->deleted()) { 2228 continue; 2229 } 2230 const SkOpSpanBase* testBase = test->span(); 2231 SkASSERT(testBase->ptT() == test); 2232 const SkOpSegment* segment = test->segment(); 2233 if (segment->done()) { 2234 continue; 2235 } 2236 const SkOpPtT* inner = opp->ptT(); 2237 const SkOpPtT* innerStop = inner; 2238 do { 2239 if (inner->segment() != segment) { 2240 continue; 2241 } 2242 if (inner->deleted()) { 2243 continue; 2244 } 2245 const SkOpSpanBase* innerBase = inner->span(); 2246 SkASSERT(innerBase->ptT() == inner); 2247 // when the intersection is first detected, the span base is marked if there are 2248 // more than one point in the intersection. 2249// if (!innerBase->hasMultipleHint() && !testBase->hasMultipleHint()) { 2250 if (!zero_or_one(inner->fT)) { 2251 log->record(kMergeMatches_Glitch, id, innerBase, test); 2252 } else { 2253 SkASSERT(inner->fT != test->fT); 2254 if (!zero_or_one(test->fT)) { 2255 log->record(kMergeMatches_Glitch, id, testBase, inner); 2256 } else { 2257 log->record(kMergeMatches_Glitch, id, segment); 2258// SkDEBUGCODE(testBase->debugSetDeleted()); 2259// test->setDeleted(); 2260// SkDEBUGCODE(innerBase->debugSetDeleted()); 2261// inner->setDeleted(); 2262 } 2263 } 2264#ifdef SK_DEBUG // assert if another undeleted entry points to segment 2265 const SkOpPtT* debugInner = inner; 2266 while ((debugInner = debugInner->next()) != innerStop) { 2267 if (debugInner->segment() != segment) { 2268 continue; 2269 } 2270 if (debugInner->deleted()) { 2271 continue; 2272 } 2273 SkOPASSERT(0); 2274 } 2275#endif 2276 break; 2277// } 2278 break; 2279 } while ((inner = inner->next()) != innerStop); 2280 } while ((test = testNext) != stop); 2281 this->debugCheckForCollapsedCoincidence(id, log); 2282} 2283 2284#endif 2285 2286void SkOpSpanBase::debugResetCoinT() const { 2287#if DEBUG_COINCIDENCE_ORDER 2288 const SkOpPtT* ptT = &fPtT; 2289 do { 2290 ptT->debugResetCoinT(); 2291 ptT = ptT->next(); 2292 } while (ptT != &fPtT); 2293#endif 2294} 2295 2296void SkOpSpanBase::debugSetCoinT(int index) const { 2297#if DEBUG_COINCIDENCE_ORDER 2298 const SkOpPtT* ptT = &fPtT; 2299 do { 2300 if (!ptT->deleted()) { 2301 ptT->debugSetCoinT(index); 2302 } 2303 ptT = ptT->next(); 2304 } while (ptT != &fPtT); 2305#endif 2306} 2307 2308const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const { 2309 const SkOpSpanBase* end = *endPtr; 2310 SkASSERT(this->segment() == end->segment()); 2311 const SkOpSpanBase* result; 2312 if (t() < end->t()) { 2313 result = this; 2314 } else { 2315 result = end; 2316 *endPtr = this; 2317 } 2318 return result->upCast(); 2319} 2320 2321void SkOpSpanBase::debugValidate() const { 2322#if DEBUG_COINCIDENCE 2323 if (this->globalState()->debugCheckHealth()) { 2324 return; 2325 } 2326#endif 2327#if DEBUG_VALIDATE 2328 const SkOpPtT* ptT = &fPtT; 2329 SkASSERT(ptT->span() == this); 2330 do { 2331// SkASSERT(SkDPoint::RoughlyEqual(fPtT.fPt, ptT->fPt)); 2332 ptT->debugValidate(); 2333 ptT = ptT->next(); 2334 } while (ptT != &fPtT); 2335 SkASSERT(this->debugCoinEndLoopCheck()); 2336 if (!this->final()) { 2337 SkASSERT(this->upCast()->debugCoinLoopCheck()); 2338 } 2339 if (fFromAngle) { 2340 fFromAngle->debugValidate(); 2341 } 2342 if (!this->final() && this->upCast()->toAngle()) { 2343 this->upCast()->toAngle()->debugValidate(); 2344 } 2345#endif 2346} 2347 2348bool SkOpSpan::debugCoinLoopCheck() const { 2349 int loop = 0; 2350 const SkOpSpan* next = this; 2351 SkOpSpan* nextCoin; 2352 do { 2353 nextCoin = next->fCoincident; 2354 SkASSERT(nextCoin == this || nextCoin->fCoincident != nextCoin); 2355 for (int check = 1; check < loop - 1; ++check) { 2356 const SkOpSpan* checkCoin = this->fCoincident; 2357 const SkOpSpan* innerCoin = checkCoin; 2358 for (int inner = check + 1; inner < loop; ++inner) { 2359 innerCoin = innerCoin->fCoincident; 2360 if (checkCoin == innerCoin) { 2361 SkDebugf("*** bad coincident loop ***\n"); 2362 return false; 2363 } 2364 } 2365 } 2366 ++loop; 2367 } while ((next = nextCoin) && next != this); 2368 return true; 2369} 2370 2371#if DEBUG_COINCIDENCE_VERBOSE 2372// Commented-out lines keep this in sync with insertCoincidence() in header 2373void SkOpSpan::debugInsertCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpan* coin) const { 2374 if (containsCoincidence(coin)) { 2375// SkASSERT(coin->containsCoincidence(this)); 2376 return; 2377 } 2378 debugValidate(); 2379// SkASSERT(this != coin); 2380 log->record(kMarkCoinStart_Glitch, id, this, coin); 2381// coin->fCoincident = this->fCoincident; 2382// this->fCoincident = coinNext; 2383 debugValidate(); 2384} 2385 2386// Commented-out lines keep this in sync with insertCoincidence() 2387void SkOpSpan::debugInsertCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSegment* segment, bool flipped) const { 2388 if (this->containsCoincidence(segment)) { 2389 return; 2390 } 2391 const SkOpPtT* next = &fPtT; 2392 while ((next = next->next()) != &fPtT) { 2393 if (next->segment() == segment) { 2394 log->record(kMarkCoinInsert_Glitch, id, flipped ? next->span()->prev() : next->span()); 2395 return; 2396 } 2397 } 2398#if DEBUG_COINCIDENCE 2399 log->record(kMarkCoinMissing_Glitch, id, segment, this); 2400#endif 2401} 2402#endif 2403 2404// called only by test code 2405int SkIntersections::debugCoincidentUsed() const { 2406 if (!fIsCoincident[0]) { 2407 SkASSERT(!fIsCoincident[1]); 2408 return 0; 2409 } 2410 int count = 0; 2411 SkDEBUGCODE(int count2 = 0;) 2412 for (int index = 0; index < fUsed; ++index) { 2413 if (fIsCoincident[0] & (1 << index)) { 2414 ++count; 2415 } 2416#ifdef SK_DEBUG 2417 if (fIsCoincident[1] & (1 << index)) { 2418 ++count2; 2419 } 2420#endif 2421 } 2422 SkASSERT(count == count2); 2423 return count; 2424} 2425 2426#include "SkOpContour.h" 2427 2428// Commented-out lines keep this in sync with addOpp() 2429void SkOpPtT::debugAddOpp(const SkOpPtT* opp, const SkOpPtT* oppPrev) const { 2430 SkDEBUGCODE(const SkOpPtT* oldNext = this->fNext); 2431 SkASSERT(this != opp); 2432// this->fNext = opp; 2433 SkASSERT(oppPrev != oldNext); 2434// oppPrev->fNext = oldNext; 2435} 2436 2437bool SkOpPtT::debugContains(const SkOpPtT* check) const { 2438 SkASSERT(this != check); 2439 const SkOpPtT* ptT = this; 2440 int links = 0; 2441 do { 2442 ptT = ptT->next(); 2443 if (ptT == check) { 2444 return true; 2445 } 2446 ++links; 2447 const SkOpPtT* test = this; 2448 for (int index = 0; index < links; ++index) { 2449 if (ptT == test) { 2450 return false; 2451 } 2452 test = test->next(); 2453 } 2454 } while (true); 2455} 2456 2457const SkOpPtT* SkOpPtT::debugContains(const SkOpSegment* check) const { 2458 SkASSERT(this->segment() != check); 2459 const SkOpPtT* ptT = this; 2460 int links = 0; 2461 do { 2462 ptT = ptT->next(); 2463 if (ptT->segment() == check) { 2464 return ptT; 2465 } 2466 ++links; 2467 const SkOpPtT* test = this; 2468 for (int index = 0; index < links; ++index) { 2469 if (ptT == test) { 2470 return nullptr; 2471 } 2472 test = test->next(); 2473 } 2474 } while (true); 2475} 2476 2477const SkOpPtT* SkOpPtT::debugEnder(const SkOpPtT* end) const { 2478 return fT < end->fT ? end : this; 2479} 2480 2481int SkOpPtT::debugLoopLimit(bool report) const { 2482 int loop = 0; 2483 const SkOpPtT* next = this; 2484 do { 2485 for (int check = 1; check < loop - 1; ++check) { 2486 const SkOpPtT* checkPtT = this->fNext; 2487 const SkOpPtT* innerPtT = checkPtT; 2488 for (int inner = check + 1; inner < loop; ++inner) { 2489 innerPtT = innerPtT->fNext; 2490 if (checkPtT == innerPtT) { 2491 if (report) { 2492 SkDebugf("*** bad ptT loop ***\n"); 2493 } 2494 return loop; 2495 } 2496 } 2497 } 2498 // there's nothing wrong with extremely large loop counts -- but this may appear to hang 2499 // by taking a very long time to figure out that no loop entry is a duplicate 2500 // -- and it's likely that a large loop count is indicative of a bug somewhere 2501 if (++loop > 1000) { 2502 SkDebugf("*** loop count exceeds 1000 ***\n"); 2503 return 1000; 2504 } 2505 } while ((next = next->fNext) && next != this); 2506 return 0; 2507} 2508 2509const SkOpPtT* SkOpPtT::debugOppPrev(const SkOpPtT* opp) const { 2510 return this->oppPrev(const_cast<SkOpPtT*>(opp)); 2511} 2512 2513void SkOpPtT::debugResetCoinT() const { 2514#if DEBUG_COINCIDENCE_ORDER 2515 this->segment()->debugResetCoinT(); 2516#endif 2517} 2518 2519void SkOpPtT::debugSetCoinT(int index) const { 2520#if DEBUG_COINCIDENCE_ORDER 2521 this->segment()->debugSetCoinT(index, fT); 2522#endif 2523} 2524 2525void SkOpPtT::debugValidate() const { 2526#if DEBUG_COINCIDENCE 2527 if (this->globalState()->debugCheckHealth()) { 2528 return; 2529 } 2530#endif 2531#if DEBUG_VALIDATE 2532 SkOpGlobalState::Phase phase = contour()->globalState()->phase(); 2533 if (phase == SkOpGlobalState::kIntersecting 2534 || phase == SkOpGlobalState::kFixWinding) { 2535 return; 2536 } 2537 SkASSERT(fNext); 2538 SkASSERT(fNext != this); 2539 SkASSERT(fNext->fNext); 2540 SkASSERT(debugLoopLimit(false) == 0); 2541#endif 2542} 2543 2544static void output_scalar(SkScalar num) { 2545 if (num == (int) num) { 2546 SkDebugf("%d", (int) num); 2547 } else { 2548 SkString str; 2549 str.printf("%1.9g", num); 2550 int width = (int) str.size(); 2551 const char* cStr = str.c_str(); 2552 while (cStr[width - 1] == '0') { 2553 --width; 2554 } 2555 str.resize(width); 2556 SkDebugf("%sf", str.c_str()); 2557 } 2558} 2559 2560static void output_points(const SkPoint* pts, int count) { 2561 for (int index = 0; index < count; ++index) { 2562 output_scalar(pts[index].fX); 2563 SkDebugf(", "); 2564 output_scalar(pts[index].fY); 2565 if (index + 1 < count) { 2566 SkDebugf(", "); 2567 } 2568 } 2569} 2570 2571static void showPathContours(SkPath::RawIter& iter, const char* pathName) { 2572 uint8_t verb; 2573 SkPoint pts[4]; 2574 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 2575 switch (verb) { 2576 case SkPath::kMove_Verb: 2577 SkDebugf(" %s.moveTo(", pathName); 2578 output_points(&pts[0], 1); 2579 SkDebugf(");\n"); 2580 continue; 2581 case SkPath::kLine_Verb: 2582 SkDebugf(" %s.lineTo(", pathName); 2583 output_points(&pts[1], 1); 2584 SkDebugf(");\n"); 2585 break; 2586 case SkPath::kQuad_Verb: 2587 SkDebugf(" %s.quadTo(", pathName); 2588 output_points(&pts[1], 2); 2589 SkDebugf(");\n"); 2590 break; 2591 case SkPath::kConic_Verb: 2592 SkDebugf(" %s.conicTo(", pathName); 2593 output_points(&pts[1], 2); 2594 SkDebugf(", %1.9gf);\n", iter.conicWeight()); 2595 break; 2596 case SkPath::kCubic_Verb: 2597 SkDebugf(" %s.cubicTo(", pathName); 2598 output_points(&pts[1], 3); 2599 SkDebugf(");\n"); 2600 break; 2601 case SkPath::kClose_Verb: 2602 SkDebugf(" %s.close();\n", pathName); 2603 break; 2604 default: 2605 SkDEBUGFAIL("bad verb"); 2606 return; 2607 } 2608 } 2609} 2610 2611static const char* gFillTypeStr[] = { 2612 "kWinding_FillType", 2613 "kEvenOdd_FillType", 2614 "kInverseWinding_FillType", 2615 "kInverseEvenOdd_FillType" 2616}; 2617 2618void SkPathOpsDebug::ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration) { 2619 SkPath::RawIter iter(path); 2620#define SUPPORT_RECT_CONTOUR_DETECTION 0 2621#if SUPPORT_RECT_CONTOUR_DETECTION 2622 int rectCount = path.isRectContours() ? path.rectContours(nullptr, nullptr) : 0; 2623 if (rectCount > 0) { 2624 SkTDArray<SkRect> rects; 2625 SkTDArray<SkPath::Direction> directions; 2626 rects.setCount(rectCount); 2627 directions.setCount(rectCount); 2628 path.rectContours(rects.begin(), directions.begin()); 2629 for (int contour = 0; contour < rectCount; ++contour) { 2630 const SkRect& rect = rects[contour]; 2631 SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop, 2632 rect.fRight, rect.fBottom, directions[contour] == SkPath::kCCW_Direction 2633 ? "SkPath::kCCW_Direction" : "SkPath::kCW_Direction"); 2634 } 2635 return; 2636 } 2637#endif 2638 SkPath::FillType fillType = path.getFillType(); 2639 SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType); 2640 if (includeDeclaration) { 2641 SkDebugf(" SkPath %s;\n", name); 2642 } 2643 SkDebugf(" %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[fillType]); 2644 iter.setPath(path); 2645 showPathContours(iter, name); 2646} 2647