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