1 /* 2 * Copyright 2012 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 #include "SkOpCoincidence.h" 8 #include "SkOpContour.h" 9 #include "SkOpSegment.h" 10 #include "SkPathWriter.h" 11 12 /* 13 After computing raw intersections, post process all segments to: 14 - find small collections of points that can be collapsed to a single point 15 - find missing intersections to resolve differences caused by different algorithms 16 17 Consider segments containing tiny or small intervals. Consider coincident segments 18 because coincidence finds intersections through distance measurement that non-coincident 19 intersection tests cannot. 20 */ 21 22 #define F (false) // discard the edge 23 #define T (true) // keep the edge 24 25 static const bool gUnaryActiveEdge[2][2] = { 26 // from=0 from=1 27 // to=0,1 to=0,1 28 {F, T}, {T, F}, 29 }; 30 31 static const bool gActiveEdge[kXOR_SkPathOp + 1][2][2][2][2] = { 32 // miFrom=0 miFrom=1 33 // miTo=0 miTo=1 miTo=0 miTo=1 34 // suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1 35 // suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 36 {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su 37 {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su 38 {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su 39 {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su 40 }; 41 42 #undef F 43 #undef T 44 45 SkOpAngle* SkOpSegment::activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr, 46 SkOpSpanBase** endPtr, bool* done) { 47 if (SkOpAngle* result = activeAngleInner(start, startPtr, endPtr, done)) { 48 return result; 49 } 50 if (SkOpAngle* result = activeAngleOther(start, startPtr, endPtr, done)) { 51 return result; 52 } 53 return nullptr; 54 } 55 56 SkOpAngle* SkOpSegment::activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr, 57 SkOpSpanBase** endPtr, bool* done) { 58 SkOpSpan* upSpan = start->upCastable(); 59 if (upSpan) { 60 if (upSpan->windValue() || upSpan->oppValue()) { 61 SkOpSpanBase* next = upSpan->next(); 62 if (!*endPtr) { 63 *startPtr = start; 64 *endPtr = next; 65 } 66 if (!upSpan->done()) { 67 if (upSpan->windSum() != SK_MinS32) { 68 return spanToAngle(start, next); 69 } 70 *done = false; 71 } 72 } else { 73 SkASSERT(upSpan->done()); 74 } 75 } 76 SkOpSpan* downSpan = start->prev(); 77 // edge leading into junction 78 if (downSpan) { 79 if (downSpan->windValue() || downSpan->oppValue()) { 80 if (!*endPtr) { 81 *startPtr = start; 82 *endPtr = downSpan; 83 } 84 if (!downSpan->done()) { 85 if (downSpan->windSum() != SK_MinS32) { 86 return spanToAngle(start, downSpan); 87 } 88 *done = false; 89 } 90 } else { 91 SkASSERT(downSpan->done()); 92 } 93 } 94 return nullptr; 95 } 96 97 SkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr, 98 SkOpSpanBase** endPtr, bool* done) { 99 SkOpPtT* oPtT = start->ptT()->next(); 100 SkOpSegment* other = oPtT->segment(); 101 SkOpSpanBase* oSpan = oPtT->span(); 102 return other->activeAngleInner(oSpan, startPtr, endPtr, done); 103 } 104 105 bool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask, 106 SkPathOp op) { 107 int sumMiWinding = this->updateWinding(end, start); 108 int sumSuWinding = this->updateOppWinding(end, start); 109 #if DEBUG_LIMIT_WIND_SUM 110 SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM); 111 SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM); 112 #endif 113 if (this->operand()) { 114 SkTSwap<int>(sumMiWinding, sumSuWinding); 115 } 116 return this->activeOp(xorMiMask, xorSuMask, start, end, op, &sumMiWinding, &sumSuWinding); 117 } 118 119 bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, 120 SkPathOp op, int* sumMiWinding, int* sumSuWinding) { 121 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 122 this->setUpWindings(start, end, sumMiWinding, sumSuWinding, 123 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 124 bool miFrom; 125 bool miTo; 126 bool suFrom; 127 bool suTo; 128 if (operand()) { 129 miFrom = (oppMaxWinding & xorMiMask) != 0; 130 miTo = (oppSumWinding & xorMiMask) != 0; 131 suFrom = (maxWinding & xorSuMask) != 0; 132 suTo = (sumWinding & xorSuMask) != 0; 133 } else { 134 miFrom = (maxWinding & xorMiMask) != 0; 135 miTo = (sumWinding & xorMiMask) != 0; 136 suFrom = (oppMaxWinding & xorSuMask) != 0; 137 suTo = (oppSumWinding & xorSuMask) != 0; 138 } 139 bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo]; 140 #if DEBUG_ACTIVE_OP 141 SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", 142 __FUNCTION__, debugID(), start->t(), end->t(), 143 SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result); 144 #endif 145 return result; 146 } 147 148 bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end) { 149 int sumWinding = updateWinding(end, start); 150 return activeWinding(start, end, &sumWinding); 151 } 152 153 bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding) { 154 int maxWinding; 155 setUpWinding(start, end, &maxWinding, sumWinding); 156 bool from = maxWinding != 0; 157 bool to = *sumWinding != 0; 158 bool result = gUnaryActiveEdge[from][to]; 159 return result; 160 } 161 162 void SkOpSegment::addAlignIntersection(SkOpPtT& endPtT, SkPoint& oldPt, 163 SkOpContourHead* contourList, SkChunkAlloc* allocator) { 164 const SkPoint& newPt = endPtT.fPt; 165 if (newPt == oldPt) { 166 return; 167 } 168 SkPoint line[2] = { newPt, oldPt }; 169 SkPathOpsBounds lineBounds; 170 lineBounds.setBounds(line, 2); 171 SkDLine aLine; 172 aLine.set(line); 173 SkOpContour* current = contourList; 174 do { 175 if (!SkPathOpsBounds::Intersects(current->bounds(), lineBounds)) { 176 continue; 177 } 178 SkOpSegment* segment = current->first(); 179 do { 180 if (!SkPathOpsBounds::Intersects(segment->bounds(), lineBounds)) { 181 continue; 182 } 183 if (newPt == segment->fPts[0]) { 184 continue; 185 } 186 if (newPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) { 187 continue; 188 } 189 if (oldPt == segment->fPts[0]) { 190 continue; 191 } 192 if (oldPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) { 193 continue; 194 } 195 if (endPtT.contains(segment)) { 196 continue; 197 } 198 SkIntersections i; 199 switch (segment->fVerb) { 200 case SkPath::kLine_Verb: { 201 SkDLine bLine; 202 bLine.set(segment->fPts); 203 i.intersect(bLine, aLine); 204 } break; 205 case SkPath::kQuad_Verb: { 206 SkDQuad bQuad; 207 bQuad.set(segment->fPts); 208 i.intersect(bQuad, aLine); 209 } break; 210 case SkPath::kConic_Verb: { 211 SkDConic bConic; 212 bConic.set(segment->fPts, segment->fWeight); 213 i.intersect(bConic, aLine); 214 } break; 215 case SkPath::kCubic_Verb: { 216 SkDCubic bCubic; 217 bCubic.set(segment->fPts); 218 i.intersect(bCubic, aLine); 219 } break; 220 default: 221 SkASSERT(0); 222 } 223 if (i.used()) { 224 SkASSERT(i.used() == 1); 225 SkASSERT(!zero_or_one(i[0][0])); 226 SkOpSpanBase* checkSpan = fHead.next(); 227 while (!checkSpan->final()) { 228 if (checkSpan->contains(segment)) { 229 goto nextSegment; 230 } 231 checkSpan = checkSpan->upCast()->next(); 232 } 233 SkOpPtT* ptT = segment->addT(i[0][0], SkOpSegment::kAllowAlias, allocator); 234 ptT->fPt = newPt; 235 endPtT.addOpp(ptT); 236 } 237 nextSegment: 238 ; 239 } while ((segment = segment->next())); 240 } while ((current = current->next())); 241 } 242 243 bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, 244 SkPathWriter* path) const { 245 if (start->starter(end)->alreadyAdded()) { 246 return false; 247 } 248 SkOpCurve edge; 249 const SkPoint* ePtr; 250 SkScalar eWeight; 251 if ((start == &fHead && end == &fTail) || (start == &fTail && end == &fHead)) { 252 ePtr = fPts; 253 eWeight = fWeight; 254 } else { 255 // OPTIMIZE? if not active, skip remainder and return xyAtT(end) 256 subDivide(start, end, &edge); 257 ePtr = edge.fPts; 258 eWeight = edge.fWeight; 259 } 260 bool reverse = ePtr == fPts && start != &fHead; 261 if (reverse) { 262 path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]); 263 switch (fVerb) { 264 case SkPath::kLine_Verb: 265 path->deferredLine(ePtr[0]); 266 break; 267 case SkPath::kQuad_Verb: 268 path->quadTo(ePtr[1], ePtr[0]); 269 break; 270 case SkPath::kConic_Verb: 271 path->conicTo(ePtr[1], ePtr[0], eWeight); 272 break; 273 case SkPath::kCubic_Verb: 274 path->cubicTo(ePtr[2], ePtr[1], ePtr[0]); 275 break; 276 default: 277 SkASSERT(0); 278 } 279 } else { 280 path->deferredMoveLine(ePtr[0]); 281 switch (fVerb) { 282 case SkPath::kLine_Verb: 283 path->deferredLine(ePtr[1]); 284 break; 285 case SkPath::kQuad_Verb: 286 path->quadTo(ePtr[1], ePtr[2]); 287 break; 288 case SkPath::kConic_Verb: 289 path->conicTo(ePtr[1], ePtr[2], eWeight); 290 break; 291 case SkPath::kCubic_Verb: 292 path->cubicTo(ePtr[1], ePtr[2], ePtr[3]); 293 break; 294 default: 295 SkASSERT(0); 296 } 297 } 298 return true; 299 } 300 301 SkOpPtT* SkOpSegment::addMissing(double t, SkOpSegment* opp, SkChunkAlloc* allocator) { 302 SkOpSpanBase* existing = nullptr; 303 SkOpSpanBase* test = &fHead; 304 double testT; 305 do { 306 if ((testT = test->ptT()->fT) >= t) { 307 if (testT == t) { 308 existing = test; 309 } 310 break; 311 } 312 } while ((test = test->upCast()->next())); 313 SkOpPtT* result; 314 if (existing && existing->contains(opp)) { 315 result = existing->ptT(); 316 } else { 317 result = this->addT(t, SkOpSegment::kNoAlias, allocator); 318 } 319 SkASSERT(result); 320 return result; 321 } 322 323 SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* allocator) { 324 debugValidate(); 325 SkPoint pt = this->ptAtT(t); 326 SkOpSpanBase* span = &fHead; 327 do { 328 SkOpPtT* result = span->ptT(); 329 SkOpPtT* loop; 330 bool duplicatePt; 331 if (t == result->fT) { 332 goto bumpSpan; 333 } 334 if (this->match(result, this, t, pt)) { 335 // see if any existing alias matches segment, pt, and t 336 loop = result->next(); 337 duplicatePt = false; 338 while (loop != result) { 339 bool ptMatch = loop->fPt == pt; 340 if (loop->segment() == this && loop->fT == t && ptMatch) { 341 goto bumpSpan; 342 } 343 duplicatePt |= ptMatch; 344 loop = loop->next(); 345 } 346 if (kNoAlias == allowAlias) { 347 bumpSpan: 348 span->bumpSpanAdds(); 349 return result; 350 } 351 SkOpPtT* alias = SkOpTAllocator<SkOpPtT>::Allocate(allocator); 352 alias->init(result->span(), t, pt, duplicatePt); 353 result->insert(alias); 354 result->span()->unaligned(); 355 this->debugValidate(); 356 #if DEBUG_ADD_T 357 SkDebugf("%s alias t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, 358 alias->segment()->debugID(), alias->span()->debugID()); 359 #endif 360 span->bumpSpanAdds(); 361 return alias; 362 } 363 if (t < result->fT) { 364 SkOpSpan* prev = result->span()->prev(); 365 if (!prev) { 366 return nullptr; 367 } 368 SkOpSpan* span = insert(prev, allocator); 369 span->init(this, prev, t, pt); 370 this->debugValidate(); 371 #if DEBUG_ADD_T 372 SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, 373 span->segment()->debugID(), span->debugID()); 374 #endif 375 span->bumpSpanAdds(); 376 return span->ptT(); 377 } 378 SkASSERT(span != &fTail); 379 } while ((span = span->upCast()->next())); 380 SkASSERT(0); 381 return nullptr; 382 } 383 384 // choose a solitary t and pt value; remove aliases; align the opposite ends 385 void SkOpSegment::align() { 386 debugValidate(); 387 SkOpSpanBase* span = &fHead; 388 if (!span->aligned()) { 389 span->alignEnd(0, fPts[0]); 390 } 391 while ((span = span->upCast()->next())) { 392 if (span == &fTail) { 393 break; 394 } 395 span->align(); 396 } 397 if (!span->aligned()) { 398 span->alignEnd(1, fPts[SkPathOpsVerbToPoints(fVerb)]); 399 } 400 if (this->collapsed()) { 401 SkOpSpan* span = &fHead; 402 do { 403 span->setWindValue(0); 404 span->setOppValue(0); 405 this->markDone(span); 406 } while ((span = span->next()->upCastable())); 407 } 408 debugValidate(); 409 } 410 411 void SkOpSegment::calcAngles(SkChunkAlloc* allocator) { 412 bool activePrior = !fHead.isCanceled(); 413 if (activePrior && !fHead.simple()) { 414 addStartSpan(allocator); 415 } 416 SkOpSpan* prior = &fHead; 417 SkOpSpanBase* spanBase = fHead.next(); 418 while (spanBase != &fTail) { 419 if (activePrior) { 420 SkOpAngle* priorAngle = SkOpTAllocator<SkOpAngle>::Allocate(allocator); 421 priorAngle->set(spanBase, prior); 422 spanBase->setFromAngle(priorAngle); 423 } 424 SkOpSpan* span = spanBase->upCast(); 425 bool active = !span->isCanceled(); 426 SkOpSpanBase* next = span->next(); 427 if (active) { 428 SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator); 429 angle->set(span, next); 430 span->setToAngle(angle); 431 } 432 activePrior = active; 433 prior = span; 434 spanBase = next; 435 } 436 if (activePrior && !fTail.simple()) { 437 addEndSpan(allocator); 438 } 439 } 440 441 bool SkOpSegment::collapsed() const { 442 return fVerb == SkPath::kLine_Verb && fHead.pt() == fTail.pt(); 443 } 444 445 void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, 446 SkOpAngle::IncludeType includeType) { 447 SkOpSegment* baseSegment = baseAngle->segment(); 448 int sumMiWinding = baseSegment->updateWindingReverse(baseAngle); 449 int sumSuWinding; 450 bool binary = includeType >= SkOpAngle::kBinarySingle; 451 if (binary) { 452 sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle); 453 if (baseSegment->operand()) { 454 SkTSwap<int>(sumMiWinding, sumSuWinding); 455 } 456 } 457 SkOpSegment* nextSegment = nextAngle->segment(); 458 int maxWinding, sumWinding; 459 SkOpSpanBase* last; 460 if (binary) { 461 int oppMaxWinding, oppSumWinding; 462 nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, 463 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 464 last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, 465 nextAngle); 466 } else { 467 nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, 468 &maxWinding, &sumWinding); 469 last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); 470 } 471 nextAngle->setLastMarked(last); 472 } 473 474 void SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle, 475 SkOpAngle::IncludeType includeType) { 476 SkOpSegment* baseSegment = baseAngle->segment(); 477 int sumMiWinding = baseSegment->updateWinding(baseAngle); 478 int sumSuWinding; 479 bool binary = includeType >= SkOpAngle::kBinarySingle; 480 if (binary) { 481 sumSuWinding = baseSegment->updateOppWinding(baseAngle); 482 if (baseSegment->operand()) { 483 SkTSwap<int>(sumMiWinding, sumSuWinding); 484 } 485 } 486 SkOpSegment* nextSegment = nextAngle->segment(); 487 int maxWinding, sumWinding; 488 SkOpSpanBase* last; 489 if (binary) { 490 int oppMaxWinding, oppSumWinding; 491 nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, 492 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 493 last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, 494 nextAngle); 495 } else { 496 nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, 497 &maxWinding, &sumWinding); 498 last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); 499 } 500 nextAngle->setLastMarked(last); 501 } 502 503 // at this point, the span is already ordered, or unorderable 504 int SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end, 505 SkOpAngle::IncludeType includeType) { 506 SkASSERT(includeType != SkOpAngle::kUnaryXor); 507 SkOpAngle* firstAngle = this->spanToAngle(end, start); 508 if (nullptr == firstAngle || nullptr == firstAngle->next()) { 509 return SK_NaN32; 510 } 511 // if all angles have a computed winding, 512 // or if no adjacent angles are orderable, 513 // or if adjacent orderable angles have no computed winding, 514 // there's nothing to do 515 // if two orderable angles are adjacent, and both are next to orderable angles, 516 // and one has winding computed, transfer to the other 517 SkOpAngle* baseAngle = nullptr; 518 bool tryReverse = false; 519 // look for counterclockwise transfers 520 SkOpAngle* angle = firstAngle->previous(); 521 SkOpAngle* next = angle->next(); 522 firstAngle = next; 523 do { 524 SkOpAngle* prior = angle; 525 angle = next; 526 next = angle->next(); 527 SkASSERT(prior->next() == angle); 528 SkASSERT(angle->next() == next); 529 if (prior->unorderable() || angle->unorderable() || next->unorderable()) { 530 baseAngle = nullptr; 531 continue; 532 } 533 int testWinding = angle->starter()->windSum(); 534 if (SK_MinS32 != testWinding) { 535 baseAngle = angle; 536 tryReverse = true; 537 continue; 538 } 539 if (baseAngle) { 540 ComputeOneSum(baseAngle, angle, includeType); 541 baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; 542 } 543 } while (next != firstAngle); 544 if (baseAngle && SK_MinS32 == firstAngle->starter()->windSum()) { 545 firstAngle = baseAngle; 546 tryReverse = true; 547 } 548 if (tryReverse) { 549 baseAngle = nullptr; 550 SkOpAngle* prior = firstAngle; 551 do { 552 angle = prior; 553 prior = angle->previous(); 554 SkASSERT(prior->next() == angle); 555 next = angle->next(); 556 if (prior->unorderable() || angle->unorderable() || next->unorderable()) { 557 baseAngle = nullptr; 558 continue; 559 } 560 int testWinding = angle->starter()->windSum(); 561 if (SK_MinS32 != testWinding) { 562 baseAngle = angle; 563 continue; 564 } 565 if (baseAngle) { 566 ComputeOneSumReverse(baseAngle, angle, includeType); 567 baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; 568 } 569 } while (prior != firstAngle); 570 } 571 return start->starter(end)->windSum(); 572 } 573 574 void SkOpSegment::detach(const SkOpSpan* span) { 575 if (span->done()) { 576 --fDoneCount; 577 } 578 --fCount; 579 SkASSERT(fCount >= fDoneCount); 580 } 581 582 double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const { 583 SkDPoint testPt = this->dPtAtT(t); 584 SkDLine testPerp = {{ testPt, testPt }}; 585 SkDVector slope = this->dSlopeAtT(t); 586 testPerp[1].fX += slope.fY; 587 testPerp[1].fY -= slope.fX; 588 SkIntersections i; 589 const SkOpSegment* oppSegment = oppAngle->segment(); 590 (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i); 591 double closestDistSq = SK_ScalarInfinity; 592 for (int index = 0; index < i.used(); ++index) { 593 if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) { 594 continue; 595 } 596 double testDistSq = testPt.distanceSquared(i.pt(index)); 597 if (closestDistSq > testDistSq) { 598 closestDistSq = testDistSq; 599 } 600 } 601 return closestDistSq; 602 } 603 604 void SkOpSegment::findCollapsed() { 605 if (fHead.contains(&fTail)) { 606 markAllDone(); 607 // move start and end to the same point 608 fHead.alignEnd(0, fHead.pt()); 609 fTail.setAligned(); 610 } 611 } 612 613 /* 614 The M and S variable name parts stand for the operators. 615 Mi stands for Minuend (see wiki subtraction, analogous to difference) 616 Su stands for Subtrahend 617 The Opp variable name part designates that the value is for the Opposite operator. 618 Opposite values result from combining coincident spans. 619 */ 620 SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, 621 SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask) { 622 SkOpSpanBase* start = *nextStart; 623 SkOpSpanBase* end = *nextEnd; 624 SkASSERT(start != end); 625 int step = start->step(end); 626 SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 627 if (other) { 628 // mark the smaller of startIndex, endIndex done, and all adjacent 629 // spans with the same T value (but not 'other' spans) 630 #if DEBUG_WINDING 631 SkDebugf("%s simple\n", __FUNCTION__); 632 #endif 633 SkOpSpan* startSpan = start->starter(end); 634 if (startSpan->done()) { 635 return nullptr; 636 } 637 markDone(startSpan); 638 *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 639 return other; 640 } 641 SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 642 SkASSERT(endNear == end); // is this ever not end? 643 SkASSERT(endNear); 644 SkASSERT(start != endNear); 645 SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 646 // more than one viable candidate -- measure angles to find best 647 int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp); 648 bool sortable = calcWinding != SK_NaN32; 649 if (!sortable) { 650 *unsortable = true; 651 markDone(start->starter(end)); 652 return nullptr; 653 } 654 SkOpAngle* angle = this->spanToAngle(end, start); 655 if (angle->unorderable()) { 656 *unsortable = true; 657 markDone(start->starter(end)); 658 return nullptr; 659 } 660 #if DEBUG_SORT 661 SkDebugf("%s\n", __FUNCTION__); 662 angle->debugLoop(); 663 #endif 664 int sumMiWinding = updateWinding(end, start); 665 if (sumMiWinding == SK_MinS32) { 666 *unsortable = true; 667 markDone(start->starter(end)); 668 return nullptr; 669 } 670 int sumSuWinding = updateOppWinding(end, start); 671 if (operand()) { 672 SkTSwap<int>(sumMiWinding, sumSuWinding); 673 } 674 SkOpAngle* nextAngle = angle->next(); 675 const SkOpAngle* foundAngle = nullptr; 676 bool foundDone = false; 677 // iterate through the angle, and compute everyone's winding 678 SkOpSegment* nextSegment; 679 int activeCount = 0; 680 do { 681 nextSegment = nextAngle->segment(); 682 bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(), 683 nextAngle->end(), op, &sumMiWinding, &sumSuWinding); 684 if (activeAngle) { 685 ++activeCount; 686 if (!foundAngle || (foundDone && activeCount & 1)) { 687 foundAngle = nextAngle; 688 foundDone = nextSegment->done(nextAngle); 689 } 690 } 691 if (nextSegment->done()) { 692 continue; 693 } 694 if (!activeAngle) { 695 (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); 696 } 697 SkOpSpanBase* last = nextAngle->lastMarked(); 698 if (last) { 699 SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); 700 *chase->append() = last; 701 #if DEBUG_WINDING 702 SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, 703 last->segment()->debugID(), last->debugID()); 704 if (!last->final()) { 705 SkDebugf(" windSum=%d", last->upCast()->windSum()); 706 } 707 SkDebugf("\n"); 708 #endif 709 } 710 } while ((nextAngle = nextAngle->next()) != angle); 711 start->segment()->markDone(start->starter(end)); 712 if (!foundAngle) { 713 return nullptr; 714 } 715 *nextStart = foundAngle->start(); 716 *nextEnd = foundAngle->end(); 717 nextSegment = foundAngle->segment(); 718 #if DEBUG_WINDING 719 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 720 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 721 #endif 722 return nextSegment; 723 } 724 725 SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase, 726 SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) { 727 SkOpSpanBase* start = *nextStart; 728 SkOpSpanBase* end = *nextEnd; 729 SkASSERT(start != end); 730 int step = start->step(end); 731 SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 732 if (other) { 733 // mark the smaller of startIndex, endIndex done, and all adjacent 734 // spans with the same T value (but not 'other' spans) 735 #if DEBUG_WINDING 736 SkDebugf("%s simple\n", __FUNCTION__); 737 #endif 738 SkOpSpan* startSpan = start->starter(end); 739 if (startSpan->done()) { 740 return nullptr; 741 } 742 markDone(startSpan); 743 *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 744 return other; 745 } 746 SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 747 SkASSERT(endNear == end); // is this ever not end? 748 SkASSERT(endNear); 749 SkASSERT(start != endNear); 750 SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 751 // more than one viable candidate -- measure angles to find best 752 int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding); 753 bool sortable = calcWinding != SK_NaN32; 754 if (!sortable) { 755 *unsortable = true; 756 markDone(start->starter(end)); 757 return nullptr; 758 } 759 SkOpAngle* angle = this->spanToAngle(end, start); 760 if (angle->unorderable()) { 761 *unsortable = true; 762 markDone(start->starter(end)); 763 return nullptr; 764 } 765 #if DEBUG_SORT 766 SkDebugf("%s\n", __FUNCTION__); 767 angle->debugLoop(); 768 #endif 769 int sumWinding = updateWinding(end, start); 770 SkOpAngle* nextAngle = angle->next(); 771 const SkOpAngle* foundAngle = nullptr; 772 bool foundDone = false; 773 // iterate through the angle, and compute everyone's winding 774 SkOpSegment* nextSegment; 775 int activeCount = 0; 776 do { 777 nextSegment = nextAngle->segment(); 778 bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(), 779 &sumWinding); 780 if (activeAngle) { 781 ++activeCount; 782 if (!foundAngle || (foundDone && activeCount & 1)) { 783 foundAngle = nextAngle; 784 foundDone = nextSegment->done(nextAngle); 785 } 786 } 787 if (nextSegment->done()) { 788 continue; 789 } 790 if (!activeAngle) { 791 (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); 792 } 793 SkOpSpanBase* last = nextAngle->lastMarked(); 794 if (last) { 795 SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); 796 *chase->append() = last; 797 #if DEBUG_WINDING 798 SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, 799 last->segment()->debugID(), last->debugID()); 800 if (!last->final()) { 801 SkDebugf(" windSum=%d", last->upCast()->windSum()); 802 } 803 SkDebugf("\n"); 804 #endif 805 } 806 } while ((nextAngle = nextAngle->next()) != angle); 807 start->segment()->markDone(start->starter(end)); 808 if (!foundAngle) { 809 return nullptr; 810 } 811 *nextStart = foundAngle->start(); 812 *nextEnd = foundAngle->end(); 813 nextSegment = foundAngle->segment(); 814 #if DEBUG_WINDING 815 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 816 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 817 #endif 818 return nextSegment; 819 } 820 821 SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, 822 bool* unsortable) { 823 SkOpSpanBase* start = *nextStart; 824 SkOpSpanBase* end = *nextEnd; 825 SkASSERT(start != end); 826 int step = start->step(end); 827 SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 828 if (other) { 829 // mark the smaller of startIndex, endIndex done, and all adjacent 830 // spans with the same T value (but not 'other' spans) 831 #if DEBUG_WINDING 832 SkDebugf("%s simple\n", __FUNCTION__); 833 #endif 834 SkOpSpan* startSpan = start->starter(end); 835 if (startSpan->done()) { 836 return nullptr; 837 } 838 markDone(startSpan); 839 *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 840 return other; 841 } 842 SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \ 843 : (*nextStart)->prev()); 844 SkASSERT(endNear == end); // is this ever not end? 845 SkASSERT(endNear); 846 SkASSERT(start != endNear); 847 SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 848 SkOpAngle* angle = this->spanToAngle(end, start); 849 if (!angle || angle->unorderable()) { 850 *unsortable = true; 851 markDone(start->starter(end)); 852 return nullptr; 853 } 854 #if DEBUG_SORT 855 SkDebugf("%s\n", __FUNCTION__); 856 angle->debugLoop(); 857 #endif 858 SkOpAngle* nextAngle = angle->next(); 859 const SkOpAngle* foundAngle = nullptr; 860 bool foundDone = false; 861 // iterate through the angle, and compute everyone's winding 862 SkOpSegment* nextSegment; 863 int activeCount = 0; 864 do { 865 nextSegment = nextAngle->segment(); 866 ++activeCount; 867 if (!foundAngle || (foundDone && activeCount & 1)) { 868 foundAngle = nextAngle; 869 if (!(foundDone = nextSegment->done(nextAngle))) { 870 break; 871 } 872 } 873 nextAngle = nextAngle->next(); 874 } while (nextAngle != angle); 875 start->segment()->markDone(start->starter(end)); 876 if (!foundAngle) { 877 return nullptr; 878 } 879 *nextStart = foundAngle->start(); 880 *nextEnd = foundAngle->end(); 881 nextSegment = foundAngle->segment(); 882 #if DEBUG_WINDING 883 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 884 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 885 #endif 886 return nextSegment; 887 } 888 889 SkOpGlobalState* SkOpSegment::globalState() const { 890 return contour()->globalState(); 891 } 892 893 void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) { 894 fContour = contour; 895 fNext = nullptr; 896 fOriginal[0] = pts[0]; 897 fOriginal[1] = pts[SkPathOpsVerbToPoints(verb)]; 898 fPts = pts; 899 fWeight = weight; 900 fVerb = verb; 901 fCount = 0; 902 fDoneCount = 0; 903 fVisited = false; 904 SkOpSpan* zeroSpan = &fHead; 905 zeroSpan->init(this, nullptr, 0, fPts[0]); 906 SkOpSpanBase* oneSpan = &fTail; 907 zeroSpan->setNext(oneSpan); 908 oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]); 909 SkDEBUGCODE(fID = globalState()->nextSegmentID()); 910 } 911 912 bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const { 913 SkDPoint cPt = this->dPtAtT(t); 914 SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t); 915 SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }}; 916 SkIntersections i; 917 (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i); 918 int used = i.used(); 919 for (int index = 0; index < used; ++index) { 920 if (cPt.roughlyEqual(i.pt(index))) { 921 return true; 922 } 923 } 924 return false; 925 } 926 927 bool SkOpSegment::isXor() const { 928 return fContour->isXor(); 929 } 930 931 void SkOpSegment::markAllDone() { 932 SkOpSpan* span = this->head(); 933 do { 934 this->markDone(span); 935 } while ((span = span->next()->upCastable())); 936 } 937 938 SkOpSpanBase* SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end) { 939 int step = start->step(end); 940 SkOpSpan* minSpan = start->starter(end); 941 markDone(minSpan); 942 SkOpSpanBase* last = nullptr; 943 SkOpSegment* other = this; 944 while ((other = other->nextChase(&start, &step, &minSpan, &last))) { 945 if (other->done()) { 946 SkASSERT(!last); 947 break; 948 } 949 other->markDone(minSpan); 950 } 951 return last; 952 } 953 954 bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding, 955 SkOpSpanBase** lastPtr) { 956 SkOpSpan* spanStart = start->starter(end); 957 int step = start->step(end); 958 bool success = markWinding(spanStart, winding); 959 SkOpSpanBase* last = nullptr; 960 SkOpSegment* other = this; 961 while ((other = other->nextChase(&start, &step, &spanStart, &last))) { 962 if (spanStart->windSum() != SK_MinS32) { 963 SkASSERT(spanStart->windSum() == winding); 964 SkASSERT(!last); 965 break; 966 } 967 (void) other->markWinding(spanStart, winding); 968 } 969 if (lastPtr) { 970 *lastPtr = last; 971 } 972 return success; 973 } 974 975 bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, 976 int winding, int oppWinding, SkOpSpanBase** lastPtr) { 977 SkOpSpan* spanStart = start->starter(end); 978 int step = start->step(end); 979 bool success = markWinding(spanStart, winding, oppWinding); 980 SkOpSpanBase* last = nullptr; 981 SkOpSegment* other = this; 982 while ((other = other->nextChase(&start, &step, &spanStart, &last))) { 983 if (spanStart->windSum() != SK_MinS32) { 984 if (this->operand() == other->operand()) { 985 if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) { 986 this->globalState()->setWindingFailed(); 987 return false; 988 } 989 } else { 990 SkASSERT(spanStart->windSum() == oppWinding); 991 SkASSERT(spanStart->oppSum() == winding); 992 } 993 SkASSERT(!last); 994 break; 995 } 996 if (this->operand() == other->operand()) { 997 (void) other->markWinding(spanStart, winding, oppWinding); 998 } else { 999 (void) other->markWinding(spanStart, oppWinding, winding); 1000 } 1001 } 1002 if (lastPtr) { 1003 *lastPtr = last; 1004 } 1005 return success; 1006 } 1007 1008 SkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) { 1009 SkASSERT(angle->segment() == this); 1010 if (UseInnerWinding(maxWinding, sumWinding)) { 1011 maxWinding = sumWinding; 1012 } 1013 SkOpSpanBase* last; 1014 (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, &last); 1015 #if DEBUG_WINDING 1016 if (last) { 1017 SkDebugf("%s last seg=%d span=%d", __FUNCTION__, 1018 last->segment()->debugID(), last->debugID()); 1019 if (!last->final()) { 1020 SkDebugf(" windSum="); 1021 SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); 1022 } 1023 SkDebugf("\n"); 1024 } 1025 #endif 1026 return last; 1027 } 1028 1029 SkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding, 1030 int oppSumWinding, const SkOpAngle* angle) { 1031 SkASSERT(angle->segment() == this); 1032 if (UseInnerWinding(maxWinding, sumWinding)) { 1033 maxWinding = sumWinding; 1034 } 1035 if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) { 1036 oppMaxWinding = oppSumWinding; 1037 } 1038 SkOpSpanBase* last = nullptr; 1039 // caller doesn't require that this marks anything 1040 (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, &last); 1041 #if DEBUG_WINDING 1042 if (last) { 1043 SkDebugf("%s last segment=%d span=%d", __FUNCTION__, 1044 last->segment()->debugID(), last->debugID()); 1045 if (!last->final()) { 1046 SkDebugf(" windSum="); 1047 SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); 1048 } 1049 SkDebugf(" \n"); 1050 } 1051 #endif 1052 return last; 1053 } 1054 1055 void SkOpSegment::markDone(SkOpSpan* span) { 1056 SkASSERT(this == span->segment()); 1057 if (span->done()) { 1058 return; 1059 } 1060 #if DEBUG_MARK_DONE 1061 debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum()); 1062 #endif 1063 span->setDone(true); 1064 ++fDoneCount; 1065 debugValidate(); 1066 } 1067 1068 bool SkOpSegment::markWinding(SkOpSpan* span, int winding) { 1069 SkASSERT(this == span->segment()); 1070 SkASSERT(winding); 1071 if (span->done()) { 1072 return false; 1073 } 1074 #if DEBUG_MARK_DONE 1075 debugShowNewWinding(__FUNCTION__, span, winding); 1076 #endif 1077 span->setWindSum(winding); 1078 debugValidate(); 1079 return true; 1080 } 1081 1082 bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) { 1083 SkASSERT(this == span->segment()); 1084 SkASSERT(winding || oppWinding); 1085 if (span->done()) { 1086 return false; 1087 } 1088 #if DEBUG_MARK_DONE 1089 debugShowNewWinding(__FUNCTION__, span, winding, oppWinding); 1090 #endif 1091 span->setWindSum(winding); 1092 span->setOppSum(oppWinding); 1093 debugValidate(); 1094 return true; 1095 } 1096 1097 bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT, 1098 const SkPoint& testPt) const { 1099 const SkOpSegment* baseParent = base->segment(); 1100 if (this == baseParent && this == testParent && precisely_equal(base->fT, testT)) { 1101 return true; 1102 } 1103 if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) { 1104 return false; 1105 } 1106 return !this->ptsDisjoint(base->fT, base->fPt, testT, testPt); 1107 } 1108 1109 static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) { 1110 if (last) { 1111 *last = endSpan; 1112 } 1113 return nullptr; 1114 } 1115 1116 SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr, 1117 SkOpSpanBase** last) const { 1118 SkOpSpanBase* origStart = *startPtr; 1119 int step = *stepPtr; 1120 SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev(); 1121 SkASSERT(endSpan); 1122 SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle(); 1123 SkOpSpanBase* foundSpan; 1124 SkOpSpanBase* otherEnd; 1125 SkOpSegment* other; 1126 if (angle == nullptr) { 1127 if (endSpan->t() != 0 && endSpan->t() != 1) { 1128 return nullptr; 1129 } 1130 SkOpPtT* otherPtT = endSpan->ptT()->next(); 1131 other = otherPtT->segment(); 1132 foundSpan = otherPtT->span(); 1133 otherEnd = step > 0 ? foundSpan->upCast()->next() : foundSpan->prev(); 1134 } else { 1135 int loopCount = angle->loopCount(); 1136 if (loopCount > 2) { 1137 return set_last(last, endSpan); 1138 } 1139 const SkOpAngle* next = angle->next(); 1140 if (nullptr == next) { 1141 return nullptr; 1142 } 1143 #if DEBUG_WINDING 1144 if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor() 1145 && !next->segment()->contour()->isXor()) { 1146 SkDebugf("%s mismatched signs\n", __FUNCTION__); 1147 } 1148 #endif 1149 other = next->segment(); 1150 foundSpan = endSpan = next->start(); 1151 otherEnd = next->end(); 1152 } 1153 int foundStep = foundSpan->step(otherEnd); 1154 if (*stepPtr != foundStep) { 1155 return set_last(last, endSpan); 1156 } 1157 SkASSERT(*startPtr); 1158 if (!otherEnd) { 1159 return nullptr; 1160 } 1161 // SkASSERT(otherEnd >= 0); 1162 SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast(); 1163 SkOpSpan* foundMin = foundSpan->starter(otherEnd); 1164 if (foundMin->windValue() != origMin->windValue() 1165 || foundMin->oppValue() != origMin->oppValue()) { 1166 return set_last(last, endSpan); 1167 } 1168 *startPtr = foundSpan; 1169 *stepPtr = foundStep; 1170 if (minPtr) { 1171 *minPtr = foundMin; 1172 } 1173 return other; 1174 } 1175 1176 static void clear_visited(SkOpSpanBase* span) { 1177 // reset visited flag back to false 1178 do { 1179 SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; 1180 while ((ptT = ptT->next()) != stopPtT) { 1181 SkOpSegment* opp = ptT->segment(); 1182 opp->resetVisited(); 1183 } 1184 } while (!span->final() && (span = span->upCast()->next())); 1185 } 1186 1187 // look for pairs of undetected coincident curves 1188 // assumes that segments going in have visited flag clear 1189 // curve/curve intersection should now do a pretty good job of finding coincident runs so 1190 // this may be only be necessary for line/curve pairs -- so skip unless this is a line and the 1191 // the opp is not a line 1192 bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) { 1193 if (this->verb() != SkPath::kLine_Verb) { 1194 return false; 1195 } 1196 if (this->done()) { 1197 return false; 1198 } 1199 SkOpSpan* prior = nullptr; 1200 SkOpSpanBase* spanBase = &fHead; 1201 do { 1202 SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT; 1203 SkASSERT(ptT->span() == spanBase); 1204 while ((ptT = ptT->next()) != spanStopPtT) { 1205 if (ptT->deleted()) { 1206 continue; 1207 } 1208 SkOpSegment* opp = ptT->span()->segment(); 1209 // if (opp->verb() == SkPath::kLine_Verb) { 1210 // continue; 1211 // } 1212 if (opp->done()) { 1213 continue; 1214 } 1215 // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence 1216 if (!opp->visited()) { 1217 continue; 1218 } 1219 if (spanBase == &fHead) { 1220 continue; 1221 } 1222 SkOpSpan* span = spanBase->upCastable(); 1223 // FIXME?: this assumes that if the opposite segment is coincident then no more 1224 // coincidence needs to be detected. This may not be true. 1225 if (span && span->containsCoincidence(opp)) { 1226 continue; 1227 } 1228 if (spanBase->segment() == opp) { 1229 continue; 1230 } 1231 if (spanBase->containsCoinEnd(opp)) { 1232 continue; 1233 } 1234 SkOpPtT* priorPtT = nullptr, * priorStopPtT; 1235 // find prior span containing opp segment 1236 SkOpSegment* priorOpp = nullptr; 1237 SkOpSpan* priorTest = spanBase->prev(); 1238 while (!priorOpp && priorTest) { 1239 priorStopPtT = priorPtT = priorTest->ptT(); 1240 while ((priorPtT = priorPtT->next()) != priorStopPtT) { 1241 if (priorPtT->deleted()) { 1242 continue; 1243 } 1244 SkOpSegment* segment = priorPtT->span()->segment(); 1245 if (segment == opp) { 1246 prior = priorTest; 1247 priorOpp = opp; 1248 break; 1249 } 1250 } 1251 priorTest = priorTest->prev(); 1252 } 1253 if (!priorOpp) { 1254 continue; 1255 } 1256 if (priorPtT == ptT) { 1257 continue; 1258 } 1259 SkOpPtT* oppStart = prior->ptT(); 1260 SkOpPtT* oppEnd = spanBase->ptT(); 1261 bool swapped = priorPtT->fT > ptT->fT; 1262 if (swapped) { 1263 SkTSwap(priorPtT, ptT); 1264 SkTSwap(oppStart, oppEnd); 1265 } 1266 bool flipped = oppStart->fT > oppEnd->fT; 1267 bool coincident = false; 1268 if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) { 1269 goto swapBack; 1270 } 1271 if (opp->verb() == SkPath::kLine_Verb) { 1272 coincident = (SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppStart->fPt) || 1273 SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppEnd->fPt)) && 1274 (SkDPoint::ApproximatelyEqual(ptT->fPt, oppStart->fPt) || 1275 SkDPoint::ApproximatelyEqual(ptT->fPt, oppEnd->fPt)); 1276 } 1277 if (!coincident) { 1278 coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000); 1279 } 1280 if (coincident) { 1281 // mark coincidence 1282 if (!coincidences->extend(priorPtT, ptT, oppStart, oppEnd) 1283 && !coincidences->extend(oppStart, oppEnd, priorPtT, ptT)) { 1284 coincidences->add(priorPtT, ptT, oppStart, oppEnd, allocator); 1285 } 1286 clear_visited(&fHead); 1287 return true; 1288 } 1289 swapBack: 1290 if (swapped) { 1291 SkTSwap(priorPtT, ptT); 1292 } 1293 } 1294 } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next())); 1295 clear_visited(&fHead); 1296 return false; 1297 } 1298 1299 // if a span has more than one intersection, merge the other segments' span as needed 1300 bool SkOpSegment::moveMultiples() { 1301 debugValidate(); 1302 SkOpSpanBase* test = &fHead; 1303 do { 1304 int addCount = test->spanAddsCount(); 1305 if (addCount < 1) { 1306 return false; 1307 } 1308 if (addCount == 1) { 1309 continue; 1310 } 1311 SkOpPtT* startPtT = test->ptT(); 1312 SkOpPtT* testPtT = startPtT; 1313 do { // iterate through all spans associated with start 1314 SkOpSpanBase* oppSpan = testPtT->span(); 1315 if (oppSpan->spanAddsCount() == addCount) { 1316 continue; 1317 } 1318 if (oppSpan->deleted()) { 1319 continue; 1320 } 1321 SkOpSegment* oppSegment = oppSpan->segment(); 1322 if (oppSegment == this) { 1323 continue; 1324 } 1325 // find range of spans to consider merging 1326 SkOpSpanBase* oppPrev = oppSpan; 1327 SkOpSpanBase* oppFirst = oppSpan; 1328 while ((oppPrev = oppPrev->prev())) { 1329 if (!roughly_equal(oppPrev->t(), oppSpan->t())) { 1330 break; 1331 } 1332 if (oppPrev->spanAddsCount() == addCount) { 1333 continue; 1334 } 1335 if (oppPrev->deleted()) { 1336 continue; 1337 } 1338 oppFirst = oppPrev; 1339 } 1340 SkOpSpanBase* oppNext = oppSpan; 1341 SkOpSpanBase* oppLast = oppSpan; 1342 while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) { 1343 if (!roughly_equal(oppNext->t(), oppSpan->t())) { 1344 break; 1345 } 1346 if (oppNext->spanAddsCount() == addCount) { 1347 continue; 1348 } 1349 if (oppNext->deleted()) { 1350 continue; 1351 } 1352 oppLast = oppNext; 1353 } 1354 if (oppFirst == oppLast) { 1355 continue; 1356 } 1357 SkOpSpanBase* oppTest = oppFirst; 1358 do { 1359 if (oppTest == oppSpan) { 1360 continue; 1361 } 1362 // check to see if the candidate meets specific criteria: 1363 // it contains spans of segments in test's loop but not including 'this' 1364 SkOpPtT* oppStartPtT = oppTest->ptT(); 1365 SkOpPtT* oppPtT = oppStartPtT; 1366 while ((oppPtT = oppPtT->next()) != oppStartPtT) { 1367 SkOpSegment* oppPtTSegment = oppPtT->segment(); 1368 if (oppPtTSegment == this) { 1369 goto tryNextSpan; 1370 } 1371 SkOpPtT* matchPtT = startPtT; 1372 do { 1373 if (matchPtT->segment() == oppPtTSegment) { 1374 goto foundMatch; 1375 } 1376 } while ((matchPtT = matchPtT->next()) != startPtT); 1377 goto tryNextSpan; 1378 foundMatch: // merge oppTest and oppSpan 1379 oppSegment->debugValidate(); 1380 if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) { 1381 SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse 1382 SkASSERT(oppSpan != &oppSegment->fTail); 1383 oppTest->merge(oppSpan->upCast()); 1384 } else { 1385 oppSpan->merge(oppTest->upCast()); 1386 } 1387 oppSegment->debugValidate(); 1388 goto checkNextSpan; 1389 } 1390 tryNextSpan: 1391 ; 1392 } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next())); 1393 } while ((testPtT = testPtT->next()) != startPtT); 1394 checkNextSpan: 1395 ; 1396 } while ((test = test->final() ? nullptr : test->upCast()->next())); 1397 debugValidate(); 1398 return true; 1399 } 1400 1401 // Move nearby t values and pts so they all hang off the same span. Alignment happens later. 1402 void SkOpSegment::moveNearby() { 1403 debugValidate(); 1404 SkOpSpanBase* spanS = &fHead; 1405 do { 1406 SkOpSpanBase* test = spanS->upCast()->next(); 1407 SkOpSpanBase* next; 1408 if (spanS->contains(test)) { 1409 if (!test->final()) { 1410 test->upCast()->detach(spanS->ptT()); 1411 continue; 1412 } else if (spanS != &fHead) { 1413 spanS->upCast()->detach(test->ptT()); 1414 spanS = test; 1415 continue; 1416 } 1417 } 1418 do { // iterate through all spans associated with start 1419 SkOpPtT* startBase = spanS->ptT(); 1420 next = test->final() ? nullptr : test->upCast()->next(); 1421 do { 1422 SkOpPtT* testBase = test->ptT(); 1423 do { 1424 if (startBase == testBase) { 1425 goto checkNextSpan; 1426 } 1427 if (testBase->duplicate()) { 1428 continue; 1429 } 1430 if (this->match(startBase, testBase->segment(), testBase->fT, testBase->fPt)) { 1431 if (test == &this->fTail) { 1432 if (spanS == &fHead) { 1433 debugValidate(); 1434 return; // if this span has collapsed, remove it from parent 1435 } 1436 this->fTail.merge(spanS->upCast()); 1437 debugValidate(); 1438 return; 1439 } 1440 spanS->merge(test->upCast()); 1441 goto checkNextSpan; 1442 } 1443 } while ((testBase = testBase->next()) != test->ptT()); 1444 } while ((startBase = startBase->next()) != spanS->ptT()); 1445 checkNextSpan: 1446 ; 1447 } while ((test = next)); 1448 spanS = spanS->upCast()->next(); 1449 } while (!spanS->final()); 1450 debugValidate(); 1451 } 1452 1453 bool SkOpSegment::operand() const { 1454 return fContour->operand(); 1455 } 1456 1457 bool SkOpSegment::oppXor() const { 1458 return fContour->oppXor(); 1459 } 1460 1461 bool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const { 1462 if (fVerb == SkPath::kLine_Verb) { 1463 return false; 1464 } 1465 // quads (and cubics) can loop back to nearly a line so that an opposite curve 1466 // hits in two places with very different t values. 1467 // OPTIMIZATION: curves could be preflighted so that, for example, something like 1468 // 'controls contained by ends' could avoid this check for common curves 1469 // 'ends are extremes in x or y' is cheaper to compute and real-world common 1470 // on the other hand, the below check is relatively inexpensive 1471 double midT = (t1 + t2) / 2; 1472 SkPoint midPt = this->ptAtT(midT); 1473 double seDistSq = SkTMax(pt1.distanceToSqd(pt2) * 2, FLT_EPSILON * 2); 1474 return midPt.distanceToSqd(pt1) > seDistSq || midPt.distanceToSqd(pt2) > seDistSq; 1475 } 1476 1477 void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 1478 int* maxWinding, int* sumWinding) { 1479 int deltaSum = SpanSign(start, end); 1480 *maxWinding = *sumMiWinding; 1481 *sumWinding = *sumMiWinding -= deltaSum; 1482 SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); 1483 } 1484 1485 void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 1486 int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding, 1487 int* oppSumWinding) { 1488 int deltaSum = SpanSign(start, end); 1489 int oppDeltaSum = OppSign(start, end); 1490 if (operand()) { 1491 *maxWinding = *sumSuWinding; 1492 *sumWinding = *sumSuWinding -= deltaSum; 1493 *oppMaxWinding = *sumMiWinding; 1494 *oppSumWinding = *sumMiWinding -= oppDeltaSum; 1495 } else { 1496 *maxWinding = *sumMiWinding; 1497 *sumWinding = *sumMiWinding -= deltaSum; 1498 *oppMaxWinding = *sumSuWinding; 1499 *oppSumWinding = *sumSuWinding -= oppDeltaSum; 1500 } 1501 SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); 1502 SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM); 1503 } 1504 1505 void SkOpSegment::sortAngles() { 1506 SkOpSpanBase* span = &this->fHead; 1507 do { 1508 SkOpAngle* fromAngle = span->fromAngle(); 1509 SkOpAngle* toAngle = span->final() ? nullptr : span->upCast()->toAngle(); 1510 if (!fromAngle && !toAngle) { 1511 continue; 1512 } 1513 #if DEBUG_ANGLE 1514 bool wroteAfterHeader = false; 1515 #endif 1516 SkOpAngle* baseAngle = fromAngle; 1517 if (fromAngle && toAngle) { 1518 #if DEBUG_ANGLE 1519 SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(), 1520 span->debugID()); 1521 wroteAfterHeader = true; 1522 #endif 1523 fromAngle->insert(toAngle); 1524 } else if (!fromAngle) { 1525 baseAngle = toAngle; 1526 } 1527 SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; 1528 do { 1529 SkOpSpanBase* oSpan = ptT->span(); 1530 if (oSpan == span) { 1531 continue; 1532 } 1533 SkOpAngle* oAngle = oSpan->fromAngle(); 1534 if (oAngle) { 1535 #if DEBUG_ANGLE 1536 if (!wroteAfterHeader) { 1537 SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), 1538 span->t(), span->debugID()); 1539 wroteAfterHeader = true; 1540 } 1541 #endif 1542 if (!oAngle->loopContains(baseAngle)) { 1543 baseAngle->insert(oAngle); 1544 } 1545 } 1546 if (!oSpan->final()) { 1547 oAngle = oSpan->upCast()->toAngle(); 1548 if (oAngle) { 1549 #if DEBUG_ANGLE 1550 if (!wroteAfterHeader) { 1551 SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), 1552 span->t(), span->debugID()); 1553 wroteAfterHeader = true; 1554 } 1555 #endif 1556 if (!oAngle->loopContains(baseAngle)) { 1557 baseAngle->insert(oAngle); 1558 } 1559 } 1560 } 1561 } while ((ptT = ptT->next()) != stopPtT); 1562 if (baseAngle->loopCount() == 1) { 1563 span->setFromAngle(nullptr); 1564 if (toAngle) { 1565 span->upCast()->setToAngle(nullptr); 1566 } 1567 baseAngle = nullptr; 1568 } 1569 #if DEBUG_SORT 1570 SkASSERT(!baseAngle || baseAngle->loopCount() > 1); 1571 #endif 1572 } while (!span->final() && (span = span->upCast()->next())); 1573 } 1574 1575 // return true if midpoints were computed 1576 bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, 1577 SkOpCurve* edge) const { 1578 SkASSERT(start != end); 1579 const SkOpPtT& startPtT = *start->ptT(); 1580 const SkOpPtT& endPtT = *end->ptT(); 1581 SkDEBUGCODE(edge->fVerb = fVerb); 1582 edge->fPts[0] = startPtT.fPt; 1583 int points = SkPathOpsVerbToPoints(fVerb); 1584 edge->fPts[points] = endPtT.fPt; 1585 edge->fWeight = 1; 1586 if (fVerb == SkPath::kLine_Verb) { 1587 return false; 1588 } 1589 double startT = startPtT.fT; 1590 double endT = endPtT.fT; 1591 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { 1592 // don't compute midpoints if we already have them 1593 if (fVerb == SkPath::kQuad_Verb) { 1594 edge->fPts[1] = fPts[1]; 1595 return false; 1596 } 1597 if (fVerb == SkPath::kConic_Verb) { 1598 edge->fPts[1] = fPts[1]; 1599 edge->fWeight = fWeight; 1600 return false; 1601 } 1602 SkASSERT(fVerb == SkPath::kCubic_Verb); 1603 if (start < end) { 1604 edge->fPts[1] = fPts[1]; 1605 edge->fPts[2] = fPts[2]; 1606 return false; 1607 } 1608 edge->fPts[1] = fPts[2]; 1609 edge->fPts[2] = fPts[1]; 1610 return false; 1611 } 1612 const SkDPoint sub[2] = {{ edge->fPts[0].fX, edge->fPts[0].fY}, 1613 {edge->fPts[points].fX, edge->fPts[points].fY }}; 1614 if (fVerb == SkPath::kQuad_Verb) { 1615 edge->fPts[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint(); 1616 } else if (fVerb == SkPath::kConic_Verb) { 1617 edge->fPts[1] = SkDConic::SubDivide(fPts, fWeight, sub[0], sub[1], 1618 startT, endT, &edge->fWeight).asSkPoint(); 1619 } else { 1620 SkASSERT(fVerb == SkPath::kCubic_Verb); 1621 SkDPoint ctrl[2]; 1622 SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl); 1623 edge->fPts[1] = ctrl[0].asSkPoint(); 1624 edge->fPts[2] = ctrl[1].asSkPoint(); 1625 } 1626 return true; 1627 } 1628 1629 bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, 1630 SkDCurve* edge) const { 1631 SkASSERT(start != end); 1632 const SkOpPtT& startPtT = *start->ptT(); 1633 const SkOpPtT& endPtT = *end->ptT(); 1634 SkDEBUGCODE(edge->fVerb = fVerb); 1635 edge->fCubic[0].set(startPtT.fPt); 1636 int points = SkPathOpsVerbToPoints(fVerb); 1637 edge->fCubic[points].set(endPtT.fPt); 1638 if (fVerb == SkPath::kLine_Verb) { 1639 return false; 1640 } 1641 double startT = startPtT.fT; 1642 double endT = endPtT.fT; 1643 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { 1644 // don't compute midpoints if we already have them 1645 if (fVerb == SkPath::kQuad_Verb) { 1646 edge->fLine[1].set(fPts[1]); 1647 return false; 1648 } 1649 if (fVerb == SkPath::kConic_Verb) { 1650 edge->fConic[1].set(fPts[1]); 1651 edge->fConic.fWeight = fWeight; 1652 return false; 1653 } 1654 SkASSERT(fVerb == SkPath::kCubic_Verb); 1655 if (startT == 0) { 1656 edge->fCubic[1].set(fPts[1]); 1657 edge->fCubic[2].set(fPts[2]); 1658 return false; 1659 } 1660 edge->fCubic[1].set(fPts[2]); 1661 edge->fCubic[2].set(fPts[1]); 1662 return false; 1663 } 1664 if (fVerb == SkPath::kQuad_Verb) { 1665 edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT); 1666 } else if (fVerb == SkPath::kConic_Verb) { 1667 edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2], 1668 startT, endT, &edge->fConic.fWeight); 1669 } else { 1670 SkASSERT(fVerb == SkPath::kCubic_Verb); 1671 SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]); 1672 } 1673 return true; 1674 } 1675 1676 bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT, 1677 const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp, 1678 SkScalar flatnessLimit) const { 1679 // average t, find mid pt 1680 double midT = (prior->t() + spanBase->t()) / 2; 1681 SkPoint midPt = this->ptAtT(midT); 1682 bool coincident = true; 1683 // if the mid pt is not near either end pt, project perpendicular through opp seg 1684 if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt) 1685 && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) { 1686 coincident = false; 1687 SkIntersections i; 1688 SkVector dxdy = (*CurveSlopeAtT[fVerb])(this->pts(), this->weight(), midT); 1689 SkDLine ray = {{{midPt.fX, midPt.fY}, 1690 {(double) midPt.fX + dxdy.fY, (double) midPt.fY - dxdy.fX}}}; 1691 (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), ray, &i); 1692 // measure distance and see if it's small enough to denote coincidence 1693 for (int index = 0; index < i.used(); ++index) { 1694 SkDPoint oppPt = i.pt(index); 1695 if (oppPt.approximatelyEqual(midPt)) { 1696 SkVector oppDxdy = (*CurveSlopeAtT[opp->verb()])(opp->pts(), 1697 opp->weight(), i[index][0]); 1698 oppDxdy.normalize(); 1699 dxdy.normalize(); 1700 SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILON); 1701 coincident |= flatness < flatnessLimit; 1702 } 1703 } 1704 } 1705 return coincident; 1706 } 1707 1708 void SkOpSegment::undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end) { 1709 SkOpSpan* span = this->head(); 1710 do { 1711 if (!span->done()) { 1712 break; 1713 } 1714 } while ((span = span->next()->upCastable())); 1715 SkASSERT(span); 1716 *start = span; 1717 *end = span->next(); 1718 } 1719 1720 int SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const { 1721 const SkOpSpan* lesser = start->starter(end); 1722 int oppWinding = lesser->oppSum(); 1723 int oppSpanWinding = SkOpSegment::OppSign(start, end); 1724 if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding) 1725 && oppWinding != SK_MaxS32) { 1726 oppWinding -= oppSpanWinding; 1727 } 1728 return oppWinding; 1729 } 1730 1731 int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const { 1732 const SkOpSpanBase* startSpan = angle->start(); 1733 const SkOpSpanBase* endSpan = angle->end(); 1734 return updateOppWinding(endSpan, startSpan); 1735 } 1736 1737 int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const { 1738 const SkOpSpanBase* startSpan = angle->start(); 1739 const SkOpSpanBase* endSpan = angle->end(); 1740 return updateOppWinding(startSpan, endSpan); 1741 } 1742 1743 int SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) { 1744 SkOpSpan* lesser = start->starter(end); 1745 int winding = lesser->windSum(); 1746 if (winding == SK_MinS32) { 1747 winding = lesser->computeWindSum(); 1748 } 1749 if (winding == SK_MinS32) { 1750 return winding; 1751 } 1752 int spanWinding = SkOpSegment::SpanSign(start, end); 1753 if (winding && UseInnerWinding(winding - spanWinding, winding) 1754 && winding != SK_MaxS32) { 1755 winding -= spanWinding; 1756 } 1757 return winding; 1758 } 1759 1760 int SkOpSegment::updateWinding(SkOpAngle* angle) { 1761 SkOpSpanBase* startSpan = angle->start(); 1762 SkOpSpanBase* endSpan = angle->end(); 1763 return updateWinding(endSpan, startSpan); 1764 } 1765 1766 int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) { 1767 SkOpSpanBase* startSpan = angle->start(); 1768 SkOpSpanBase* endSpan = angle->end(); 1769 return updateWinding(startSpan, endSpan); 1770 } 1771 1772 // OPTIMIZATION: does the following also work, and is it any faster? 1773 // return outerWinding * innerWinding > 0 1774 // || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) 1775 bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) { 1776 SkASSERT(outerWinding != SK_MaxS32); 1777 SkASSERT(innerWinding != SK_MaxS32); 1778 int absOut = SkTAbs(outerWinding); 1779 int absIn = SkTAbs(innerWinding); 1780 bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; 1781 return result; 1782 } 1783 1784 int SkOpSegment::windSum(const SkOpAngle* angle) const { 1785 const SkOpSpan* minSpan = angle->start()->starter(angle->end()); 1786 return minSpan->windSum(); 1787 } 1788
