1 /* 2 * Copyright 2013 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 #include "SkIntersections.h" 8 #include "SkOpContour.h" 9 #include "SkPathWriter.h" 10 #include "SkTSort.h" 11 12 bool SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex, 13 const SkIntersections& ts, bool swap) { 14 SkPoint pt0 = ts.pt(0).asSkPoint(); 15 SkPoint pt1 = ts.pt(1).asSkPoint(); 16 if (pt0 == pt1) { 17 // FIXME: one could imagine a case where it would be incorrect to ignore this 18 // suppose two self-intersecting cubics overlap to be coincident -- 19 // this needs to check that by some measure the t values are far enough apart 20 // or needs to check to see if the self-intersection bit was set on the cubic segment 21 return false; 22 } 23 SkCoincidence& coincidence = fCoincidences.push_back(); 24 coincidence.fOther = other; 25 coincidence.fSegments[0] = index; 26 coincidence.fSegments[1] = otherIndex; 27 coincidence.fTs[swap][0] = ts[0][0]; 28 coincidence.fTs[swap][1] = ts[0][1]; 29 coincidence.fTs[!swap][0] = ts[1][0]; 30 coincidence.fTs[!swap][1] = ts[1][1]; 31 coincidence.fPts[swap][0] = pt0; 32 coincidence.fPts[swap][1] = pt1; 33 bool nearStart = ts.nearlySame(0); 34 bool nearEnd = ts.nearlySame(1); 35 coincidence.fPts[!swap][0] = nearStart ? ts.pt2(0).asSkPoint() : pt0; 36 coincidence.fPts[!swap][1] = nearEnd ? ts.pt2(1).asSkPoint() : pt1; 37 coincidence.fNearly[0] = nearStart; 38 coincidence.fNearly[1] = nearEnd; 39 return true; 40 } 41 42 SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) { 43 int segmentCount = fSortedSegments.count(); 44 SkASSERT(segmentCount > 0); 45 for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) { 46 SkOpSegment* testSegment = fSortedSegments[sortedIndex]; 47 if (testSegment->done()) { 48 continue; 49 } 50 *start = *end = 0; 51 while (testSegment->nextCandidate(start, end)) { 52 if (!testSegment->isVertical(*start, *end)) { 53 return testSegment; 54 } 55 } 56 } 57 return NULL; 58 } 59 60 // if one is very large the smaller may have collapsed to nothing 61 static void bump_out_close_span(double* startTPtr, double* endTPtr) { 62 double startT = *startTPtr; 63 double endT = *endTPtr; 64 if (approximately_negative(endT - startT)) { 65 if (endT <= 1 - FLT_EPSILON) { 66 *endTPtr += FLT_EPSILON; 67 SkASSERT(*endTPtr <= 1); 68 } else { 69 *startTPtr -= FLT_EPSILON; 70 SkASSERT(*startTPtr >= 0); 71 } 72 } 73 } 74 75 // first pass, add missing T values 76 // second pass, determine winding values of overlaps 77 void SkOpContour::addCoincidentPoints() { 78 int count = fCoincidences.count(); 79 for (int index = 0; index < count; ++index) { 80 SkCoincidence& coincidence = fCoincidences[index]; 81 int thisIndex = coincidence.fSegments[0]; 82 SkOpSegment& thisOne = fSegments[thisIndex]; 83 SkOpContour* otherContour = coincidence.fOther; 84 int otherIndex = coincidence.fSegments[1]; 85 SkOpSegment& other = otherContour->fSegments[otherIndex]; 86 if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) { 87 // OPTIMIZATION: remove from array 88 continue; 89 } 90 #if DEBUG_CONCIDENT 91 thisOne.debugShowTs("-"); 92 other.debugShowTs("o"); 93 #endif 94 double startT = coincidence.fTs[0][0]; 95 double endT = coincidence.fTs[0][1]; 96 bool startSwapped, oStartSwapped, cancelers; 97 if ((cancelers = startSwapped = startT > endT)) { 98 SkTSwap(startT, endT); 99 } 100 bump_out_close_span(&startT, &endT); 101 SkASSERT(!approximately_negative(endT - startT)); 102 double oStartT = coincidence.fTs[1][0]; 103 double oEndT = coincidence.fTs[1][1]; 104 if ((oStartSwapped = oStartT > oEndT)) { 105 SkTSwap(oStartT, oEndT); 106 cancelers ^= true; 107 } 108 bump_out_close_span(&oStartT, &oEndT); 109 SkASSERT(!approximately_negative(oEndT - oStartT)); 110 const SkPoint& startPt = coincidence.fPts[0][startSwapped]; 111 if (cancelers) { 112 // make sure startT and endT have t entries 113 if (startT > 0 || oEndT < 1 114 || thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) { 115 thisOne.addTPair(startT, &other, oEndT, true, startPt, 116 coincidence.fPts[1][startSwapped]); 117 } 118 const SkPoint& oStartPt = coincidence.fPts[1][oStartSwapped]; 119 if (oStartT > 0 || endT < 1 120 || thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) { 121 other.addTPair(oStartT, &thisOne, endT, true, oStartPt, 122 coincidence.fPts[0][oStartSwapped]); 123 } 124 } else { 125 if (startT > 0 || oStartT > 0 126 || thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) { 127 thisOne.addTPair(startT, &other, oStartT, true, startPt, 128 coincidence.fPts[1][startSwapped]); 129 } 130 const SkPoint& oEndPt = coincidence.fPts[1][!oStartSwapped]; 131 if (endT < 1 || oEndT < 1 132 || thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) { 133 other.addTPair(oEndT, &thisOne, endT, true, oEndPt, 134 coincidence.fPts[0][!oStartSwapped]); 135 } 136 } 137 #if DEBUG_CONCIDENT 138 thisOne.debugShowTs("+"); 139 other.debugShowTs("o"); 140 #endif 141 } 142 // if there are multiple pairs of coincidence that share an edge, see if the opposite 143 // are also coincident 144 for (int index = 0; index < count - 1; ++index) { 145 const SkCoincidence& coincidence = fCoincidences[index]; 146 int thisIndex = coincidence.fSegments[0]; 147 SkOpContour* otherContour = coincidence.fOther; 148 int otherIndex = coincidence.fSegments[1]; 149 for (int idx2 = 1; idx2 < count; ++idx2) { 150 const SkCoincidence& innerCoin = fCoincidences[idx2]; 151 int innerThisIndex = innerCoin.fSegments[0]; 152 if (thisIndex == innerThisIndex) { 153 checkCoincidentPair(coincidence, 1, innerCoin, 1, false); 154 } 155 if (this == otherContour && otherIndex == innerThisIndex) { 156 checkCoincidentPair(coincidence, 0, innerCoin, 1, false); 157 } 158 SkOpContour* innerOtherContour = innerCoin.fOther; 159 innerThisIndex = innerCoin.fSegments[1]; 160 if (this == innerOtherContour && thisIndex == innerThisIndex) { 161 checkCoincidentPair(coincidence, 1, innerCoin, 0, false); 162 } 163 if (otherContour == innerOtherContour && otherIndex == innerThisIndex) { 164 checkCoincidentPair(coincidence, 0, innerCoin, 0, false); 165 } 166 } 167 } 168 } 169 170 bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex, 171 const SkIntersections& ts, int ptIndex, bool swap) { 172 SkPoint pt0 = ts.pt(ptIndex).asSkPoint(); 173 SkPoint pt1 = ts.pt(ptIndex + 1).asSkPoint(); 174 if (SkDPoint::ApproximatelyEqual(pt0, pt1)) { 175 // FIXME: one could imagine a case where it would be incorrect to ignore this 176 // suppose two self-intersecting cubics overlap to form a partial coincidence -- 177 // although it isn't clear why the regular coincidence could wouldn't pick this up 178 // this is exceptional enough to ignore for now 179 return false; 180 } 181 SkCoincidence& coincidence = fPartialCoincidences.push_back(); 182 coincidence.fOther = other; 183 coincidence.fSegments[0] = index; 184 coincidence.fSegments[1] = otherIndex; 185 coincidence.fTs[swap][0] = ts[0][ptIndex]; 186 coincidence.fTs[swap][1] = ts[0][ptIndex + 1]; 187 coincidence.fTs[!swap][0] = ts[1][ptIndex]; 188 coincidence.fTs[!swap][1] = ts[1][ptIndex + 1]; 189 coincidence.fPts[0][0] = coincidence.fPts[1][0] = pt0; 190 coincidence.fPts[0][1] = coincidence.fPts[1][1] = pt1; 191 coincidence.fNearly[0] = 0; 192 coincidence.fNearly[1] = 0; 193 return true; 194 } 195 196 void SkOpContour::align(const SkOpSegment::AlignedSpan& aligned, bool swap, 197 SkCoincidence* coincidence) { 198 for (int idx2 = 0; idx2 < 2; ++idx2) { 199 if (coincidence->fPts[0][idx2] == aligned.fOldPt 200 && coincidence->fTs[swap][idx2] == aligned.fOldT) { 201 SkASSERT(SkDPoint::RoughlyEqual(coincidence->fPts[0][idx2], aligned.fPt)); 202 coincidence->fPts[0][idx2] = aligned.fPt; 203 SkASSERT(way_roughly_equal(coincidence->fTs[swap][idx2], aligned.fT)); 204 coincidence->fTs[swap][idx2] = aligned.fT; 205 } 206 } 207 } 208 209 void SkOpContour::alignCoincidence(const SkOpSegment::AlignedSpan& aligned, 210 SkTArray<SkCoincidence, true>* coincidences) { 211 int count = coincidences->count(); 212 for (int index = 0; index < count; ++index) { 213 SkCoincidence& coincidence = (*coincidences)[index]; 214 int thisIndex = coincidence.fSegments[0]; 215 const SkOpSegment* thisOne = &fSegments[thisIndex]; 216 const SkOpContour* otherContour = coincidence.fOther; 217 int otherIndex = coincidence.fSegments[1]; 218 const SkOpSegment* other = &otherContour->fSegments[otherIndex]; 219 if (thisOne == aligned.fOther1 && other == aligned.fOther2) { 220 align(aligned, false, &coincidence); 221 } else if (thisOne == aligned.fOther2 && other == aligned.fOther1) { 222 align(aligned, true, &coincidence); 223 } 224 } 225 } 226 227 void SkOpContour::alignTPt(int segmentIndex, const SkOpContour* other, int otherIndex, 228 bool swap, int tIndex, SkIntersections* ts, SkPoint* point) const { 229 int zeroPt; 230 if ((zeroPt = alignT(swap, tIndex, ts)) >= 0) { 231 alignPt(segmentIndex, point, zeroPt); 232 } 233 if ((zeroPt = other->alignT(!swap, tIndex, ts)) >= 0) { 234 other->alignPt(otherIndex, point, zeroPt); 235 } 236 } 237 238 void SkOpContour::alignPt(int index, SkPoint* point, int zeroPt) const { 239 const SkOpSegment& segment = fSegments[index]; 240 if (0 == zeroPt) { 241 *point = segment.pts()[0]; 242 } else { 243 *point = segment.pts()[SkPathOpsVerbToPoints(segment.verb())]; 244 } 245 } 246 247 int SkOpContour::alignT(bool swap, int tIndex, SkIntersections* ts) const { 248 double tVal = (*ts)[swap][tIndex]; 249 if (tVal != 0 && precisely_zero(tVal)) { 250 ts->set(swap, tIndex, 0); 251 return 0; 252 } 253 if (tVal != 1 && precisely_equal(tVal, 1)) { 254 ts->set(swap, tIndex, 1); 255 return 1; 256 } 257 return -1; 258 } 259 260 bool SkOpContour::calcAngles() { 261 int segmentCount = fSegments.count(); 262 for (int test = 0; test < segmentCount; ++test) { 263 if (!fSegments[test].calcAngles()) { 264 return false; 265 } 266 } 267 return true; 268 } 269 270 bool SkOpContour::calcCoincidentWinding() { 271 int count = fCoincidences.count(); 272 #if DEBUG_CONCIDENT 273 if (count > 0) { 274 SkDebugf("%s count=%d\n", __FUNCTION__, count); 275 } 276 #endif 277 for (int index = 0; index < count; ++index) { 278 SkCoincidence& coincidence = fCoincidences[index]; 279 if (!calcCommonCoincidentWinding(coincidence)) { 280 return false; 281 } 282 } 283 return true; 284 } 285 286 void SkOpContour::calcPartialCoincidentWinding() { 287 int count = fPartialCoincidences.count(); 288 #if DEBUG_CONCIDENT 289 if (count > 0) { 290 SkDebugf("%s count=%d\n", __FUNCTION__, count); 291 } 292 #endif 293 for (int index = 0; index < count; ++index) { 294 SkCoincidence& coincidence = fPartialCoincidences[index]; 295 calcCommonCoincidentWinding(coincidence); 296 } 297 // if there are multiple pairs of partial coincidence that share an edge, see if the opposite 298 // are also coincident 299 for (int index = 0; index < count - 1; ++index) { 300 const SkCoincidence& coincidence = fPartialCoincidences[index]; 301 int thisIndex = coincidence.fSegments[0]; 302 SkOpContour* otherContour = coincidence.fOther; 303 int otherIndex = coincidence.fSegments[1]; 304 for (int idx2 = 1; idx2 < count; ++idx2) { 305 const SkCoincidence& innerCoin = fPartialCoincidences[idx2]; 306 int innerThisIndex = innerCoin.fSegments[0]; 307 if (thisIndex == innerThisIndex) { 308 checkCoincidentPair(coincidence, 1, innerCoin, 1, true); 309 } 310 if (this == otherContour && otherIndex == innerThisIndex) { 311 checkCoincidentPair(coincidence, 0, innerCoin, 1, true); 312 } 313 SkOpContour* innerOtherContour = innerCoin.fOther; 314 innerThisIndex = innerCoin.fSegments[1]; 315 if (this == innerOtherContour && thisIndex == innerThisIndex) { 316 checkCoincidentPair(coincidence, 1, innerCoin, 0, true); 317 } 318 if (otherContour == innerOtherContour && otherIndex == innerThisIndex) { 319 checkCoincidentPair(coincidence, 0, innerCoin, 0, true); 320 } 321 } 322 } 323 } 324 325 void SkOpContour::checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx, 326 const SkCoincidence& twoCoin, int twoIdx, bool partial) { 327 SkASSERT((oneIdx ? this : oneCoin.fOther) == (twoIdx ? this : twoCoin.fOther)); 328 SkASSERT(oneCoin.fSegments[!oneIdx] == twoCoin.fSegments[!twoIdx]); 329 // look for common overlap 330 double min = SK_ScalarMax; 331 double max = SK_ScalarMin; 332 double min1 = oneCoin.fTs[!oneIdx][0]; 333 double max1 = oneCoin.fTs[!oneIdx][1]; 334 double min2 = twoCoin.fTs[!twoIdx][0]; 335 double max2 = twoCoin.fTs[!twoIdx][1]; 336 bool cancelers = (min1 < max1) != (min2 < max2); 337 if (min1 > max1) { 338 SkTSwap(min1, max1); 339 } 340 if (min2 > max2) { 341 SkTSwap(min2, max2); 342 } 343 if (between(min1, min2, max1)) { 344 min = min2; 345 } 346 if (between(min1, max2, max1)) { 347 max = max2; 348 } 349 if (between(min2, min1, max2)) { 350 min = SkTMin(min, min1); 351 } 352 if (between(min2, max1, max2)) { 353 max = SkTMax(max, max1); 354 } 355 if (min >= max) { 356 return; // no overlap 357 } 358 // look to see if opposite are different segments 359 int seg1Index = oneCoin.fSegments[oneIdx]; 360 int seg2Index = twoCoin.fSegments[twoIdx]; 361 if (seg1Index == seg2Index) { 362 return; 363 } 364 SkOpContour* contour1 = oneIdx ? oneCoin.fOther : this; 365 SkOpContour* contour2 = twoIdx ? twoCoin.fOther : this; 366 SkOpSegment* segment1 = &contour1->fSegments[seg1Index]; 367 SkOpSegment* segment2 = &contour2->fSegments[seg2Index]; 368 // find opposite t value ranges corresponding to reference min/max range 369 const SkOpContour* refContour = oneIdx ? this : oneCoin.fOther; 370 const int refSegIndex = oneCoin.fSegments[!oneIdx]; 371 const SkOpSegment* refSegment = &refContour->fSegments[refSegIndex]; 372 int seg1Start = segment1->findOtherT(min, refSegment); 373 int seg1End = segment1->findOtherT(max, refSegment); 374 int seg2Start = segment2->findOtherT(min, refSegment); 375 int seg2End = segment2->findOtherT(max, refSegment); 376 // if the opposite pairs already contain min/max, we're done 377 if (seg1Start >= 0 && seg1End >= 0 && seg2Start >= 0 && seg2End >= 0) { 378 return; 379 } 380 double loEnd = SkTMin(min1, min2); 381 double hiEnd = SkTMax(max1, max2); 382 // insert the missing coincident point(s) 383 double missingT1 = -1; 384 double otherT1 = -1; 385 if (seg1Start < 0) { 386 if (seg2Start < 0) { 387 return; 388 } 389 missingT1 = segment1->calcMissingTStart(refSegment, loEnd, min, max, hiEnd, 390 segment2, seg1End); 391 if (missingT1 < 0) { 392 return; 393 } 394 const SkOpSpan* missingSpan = &segment2->span(seg2Start); 395 otherT1 = missingSpan->fT; 396 } else if (seg2Start < 0) { 397 SkASSERT(seg1Start >= 0); 398 missingT1 = segment2->calcMissingTStart(refSegment, loEnd, min, max, hiEnd, 399 segment1, seg2End); 400 if (missingT1 < 0) { 401 return; 402 } 403 const SkOpSpan* missingSpan = &segment1->span(seg1Start); 404 otherT1 = missingSpan->fT; 405 } 406 SkPoint missingPt1; 407 SkOpSegment* addTo1 = NULL; 408 SkOpSegment* addOther1 = seg1Start < 0 ? segment2 : segment1; 409 int minTIndex = refSegment->findExactT(min, addOther1); 410 SkASSERT(minTIndex >= 0); 411 if (missingT1 >= 0) { 412 missingPt1 = refSegment->span(minTIndex).fPt; 413 addTo1 = seg1Start < 0 ? segment1 : segment2; 414 } 415 double missingT2 = -1; 416 double otherT2 = -1; 417 if (seg1End < 0) { 418 if (seg2End < 0) { 419 return; 420 } 421 missingT2 = segment1->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd, 422 segment2, seg1Start); 423 if (missingT2 < 0) { 424 return; 425 } 426 const SkOpSpan* missingSpan = &segment2->span(seg2End); 427 otherT2 = missingSpan->fT; 428 } else if (seg2End < 0) { 429 SkASSERT(seg1End >= 0); 430 missingT2 = segment2->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd, 431 segment1, seg2Start); 432 if (missingT2 < 0) { 433 return; 434 } 435 const SkOpSpan* missingSpan = &segment1->span(seg1End); 436 otherT2 = missingSpan->fT; 437 } 438 SkPoint missingPt2; 439 SkOpSegment* addTo2 = NULL; 440 SkOpSegment* addOther2 = seg1End < 0 ? segment2 : segment1; 441 int maxTIndex = refSegment->findExactT(max, addOther2); 442 SkASSERT(maxTIndex >= 0); 443 if (missingT2 >= 0) { 444 missingPt2 = refSegment->span(maxTIndex).fPt; 445 addTo2 = seg1End < 0 ? segment1 : segment2; 446 } 447 if (missingT1 >= 0) { 448 addTo1->pinT(missingPt1, &missingT1); 449 addTo1->addTPair(missingT1, addOther1, otherT1, false, missingPt1); 450 } else { 451 SkASSERT(minTIndex >= 0); 452 missingPt1 = refSegment->span(minTIndex).fPt; 453 } 454 if (missingT2 >= 0) { 455 addTo2->pinT(missingPt2, &missingT2); 456 addTo2->addTPair(missingT2, addOther2, otherT2, false, missingPt2); 457 } else { 458 SkASSERT(minTIndex >= 0); 459 missingPt2 = refSegment->span(maxTIndex).fPt; 460 } 461 if (!partial) { 462 return; 463 } 464 if (cancelers) { 465 if (missingT1 >= 0) { 466 if (addTo1->reversePoints(missingPt1, missingPt2)) { 467 SkTSwap(missingPt1, missingPt2); 468 } 469 addTo1->addTCancel(missingPt1, missingPt2, addOther1); 470 } else { 471 if (addTo2->reversePoints(missingPt1, missingPt2)) { 472 SkTSwap(missingPt1, missingPt2); 473 } 474 addTo2->addTCancel(missingPt1, missingPt2, addOther2); 475 } 476 } else if (missingT1 >= 0) { 477 SkAssertResult(addTo1->addTCoincident(missingPt1, missingPt2, 478 addTo1 == addTo2 ? missingT2 : otherT2, addOther1)); 479 } else { 480 SkAssertResult(addTo2->addTCoincident(missingPt2, missingPt1, 481 addTo2 == addTo1 ? missingT1 : otherT1, addOther2)); 482 } 483 } 484 485 void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) { 486 int count = coincidences.count(); 487 #if DEBUG_CONCIDENT 488 if (count > 0) { 489 SkDebugf("%s count=%d\n", __FUNCTION__, count); 490 } 491 #endif 492 // look for a lineup where the partial implies another adjoining coincidence 493 for (int index = 0; index < count; ++index) { 494 const SkCoincidence& coincidence = coincidences[index]; 495 int thisIndex = coincidence.fSegments[0]; 496 SkOpSegment& thisOne = fSegments[thisIndex]; 497 if (thisOne.done()) { 498 continue; 499 } 500 SkOpContour* otherContour = coincidence.fOther; 501 int otherIndex = coincidence.fSegments[1]; 502 SkOpSegment& other = otherContour->fSegments[otherIndex]; 503 if (other.done()) { 504 continue; 505 } 506 double startT = coincidence.fTs[0][0]; 507 double endT = coincidence.fTs[0][1]; 508 if (startT == endT) { // this can happen in very large compares 509 continue; 510 } 511 double oStartT = coincidence.fTs[1][0]; 512 double oEndT = coincidence.fTs[1][1]; 513 if (oStartT == oEndT) { 514 continue; 515 } 516 bool swapStart = startT > endT; 517 bool swapOther = oStartT > oEndT; 518 const SkPoint* startPt = &coincidence.fPts[0][0]; 519 const SkPoint* endPt = &coincidence.fPts[0][1]; 520 if (swapStart) { 521 SkTSwap(startT, endT); 522 SkTSwap(oStartT, oEndT); 523 SkTSwap(startPt, endPt); 524 } 525 bool cancel = swapOther != swapStart; 526 int step = swapStart ? -1 : 1; 527 int oStep = swapOther ? -1 : 1; 528 double oMatchStart = cancel ? oEndT : oStartT; 529 if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) { 530 bool added = false; 531 if (oMatchStart != 0) { 532 const SkPoint& oMatchStartPt = cancel ? *endPt : *startPt; 533 added = thisOne.joinCoincidence(&other, oMatchStart, oMatchStartPt, oStep, cancel); 534 } 535 if (!cancel && startT != 0 && !added) { 536 (void) other.joinCoincidence(&thisOne, startT, *startPt, step, cancel); 537 } 538 } 539 double oMatchEnd = cancel ? oStartT : oEndT; 540 if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) { 541 bool added = false; 542 if (cancel && endT != 1 && !added) { 543 (void) other.joinCoincidence(&thisOne, endT, *endPt, -step, cancel); 544 } 545 } 546 } 547 } 548 549 bool SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) { 550 if (coincidence.fNearly[0] && coincidence.fNearly[1]) { 551 return true; 552 } 553 int thisIndex = coincidence.fSegments[0]; 554 SkOpSegment& thisOne = fSegments[thisIndex]; 555 if (thisOne.done()) { 556 return true; 557 } 558 SkOpContour* otherContour = coincidence.fOther; 559 int otherIndex = coincidence.fSegments[1]; 560 SkOpSegment& other = otherContour->fSegments[otherIndex]; 561 if (other.done()) { 562 return true; 563 } 564 double startT = coincidence.fTs[0][0]; 565 double endT = coincidence.fTs[0][1]; 566 const SkPoint* startPt = &coincidence.fPts[0][0]; 567 const SkPoint* endPt = &coincidence.fPts[0][1]; 568 bool cancelers; 569 if ((cancelers = startT > endT)) { 570 SkTSwap<double>(startT, endT); 571 SkTSwap<const SkPoint*>(startPt, endPt); 572 } 573 bump_out_close_span(&startT, &endT); 574 SkASSERT(!approximately_negative(endT - startT)); 575 double oStartT = coincidence.fTs[1][0]; 576 double oEndT = coincidence.fTs[1][1]; 577 if (oStartT > oEndT) { 578 SkTSwap<double>(oStartT, oEndT); 579 cancelers ^= true; 580 } 581 bump_out_close_span(&oStartT, &oEndT); 582 SkASSERT(!approximately_negative(oEndT - oStartT)); 583 bool success = true; 584 if (cancelers) { 585 thisOne.addTCancel(*startPt, *endPt, &other); 586 } else { 587 success = thisOne.addTCoincident(*startPt, *endPt, endT, &other); 588 } 589 #if DEBUG_CONCIDENT 590 thisOne.debugShowTs("p"); 591 other.debugShowTs("o"); 592 #endif 593 return success; 594 } 595 596 void SkOpContour::resolveNearCoincidence() { 597 int count = fCoincidences.count(); 598 for (int index = 0; index < count; ++index) { 599 SkCoincidence& coincidence = fCoincidences[index]; 600 if (!coincidence.fNearly[0] || !coincidence.fNearly[1]) { 601 continue; 602 } 603 int thisIndex = coincidence.fSegments[0]; 604 SkOpSegment& thisOne = fSegments[thisIndex]; 605 SkOpContour* otherContour = coincidence.fOther; 606 int otherIndex = coincidence.fSegments[1]; 607 SkOpSegment& other = otherContour->fSegments[otherIndex]; 608 if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) { 609 // OPTIMIZATION: remove from coincidence array 610 continue; 611 } 612 #if DEBUG_CONCIDENT 613 thisOne.debugShowTs("-"); 614 other.debugShowTs("o"); 615 #endif 616 double startT = coincidence.fTs[0][0]; 617 double endT = coincidence.fTs[0][1]; 618 bool cancelers; 619 if ((cancelers = startT > endT)) { 620 SkTSwap<double>(startT, endT); 621 } 622 if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing 623 if (endT <= 1 - FLT_EPSILON) { 624 endT += FLT_EPSILON; 625 SkASSERT(endT <= 1); 626 } else { 627 startT -= FLT_EPSILON; 628 SkASSERT(startT >= 0); 629 } 630 } 631 SkASSERT(!approximately_negative(endT - startT)); 632 double oStartT = coincidence.fTs[1][0]; 633 double oEndT = coincidence.fTs[1][1]; 634 if (oStartT > oEndT) { 635 SkTSwap<double>(oStartT, oEndT); 636 cancelers ^= true; 637 } 638 SkASSERT(!approximately_negative(oEndT - oStartT)); 639 if (cancelers) { 640 thisOne.blindCancel(coincidence, &other); 641 } else { 642 thisOne.blindCoincident(coincidence, &other); 643 } 644 } 645 } 646 647 void SkOpContour::sortAngles() { 648 int segmentCount = fSegments.count(); 649 for (int test = 0; test < segmentCount; ++test) { 650 fSegments[test].sortAngles(); 651 } 652 } 653 654 void SkOpContour::sortSegments() { 655 int segmentCount = fSegments.count(); 656 fSortedSegments.push_back_n(segmentCount); 657 for (int test = 0; test < segmentCount; ++test) { 658 fSortedSegments[test] = &fSegments[test]; 659 } 660 SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1); 661 fFirstSorted = 0; 662 } 663 664 void SkOpContour::toPath(SkPathWriter* path) const { 665 int segmentCount = fSegments.count(); 666 const SkPoint& pt = fSegments.front().pts()[0]; 667 path->deferredMove(pt); 668 for (int test = 0; test < segmentCount; ++test) { 669 fSegments[test].addCurveTo(0, 1, path, true); 670 } 671 path->close(); 672 } 673 674 void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY, 675 SkOpSegment** topStart) { 676 int segmentCount = fSortedSegments.count(); 677 SkASSERT(segmentCount > 0); 678 int sortedIndex = fFirstSorted; 679 fDone = true; // may be cleared below 680 for ( ; sortedIndex < segmentCount; ++sortedIndex) { 681 SkOpSegment* testSegment = fSortedSegments[sortedIndex]; 682 if (testSegment->done()) { 683 if (sortedIndex == fFirstSorted) { 684 ++fFirstSorted; 685 } 686 continue; 687 } 688 fDone = false; 689 SkPoint testXY = testSegment->activeLeftTop(NULL); 690 if (*topStart) { 691 if (testXY.fY < topLeft.fY) { 692 continue; 693 } 694 if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) { 695 continue; 696 } 697 if (bestXY->fY < testXY.fY) { 698 continue; 699 } 700 if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) { 701 continue; 702 } 703 } 704 *topStart = testSegment; 705 *bestXY = testXY; 706 } 707 } 708 709 SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) { 710 int segmentCount = fSegments.count(); 711 for (int test = 0; test < segmentCount; ++test) { 712 SkOpSegment* testSegment = &fSegments[test]; 713 if (testSegment->done()) { 714 continue; 715 } 716 testSegment->undoneSpan(start, end); 717 return testSegment; 718 } 719 return NULL; 720 } 721 722 #if DEBUG_SHOW_WINDING 723 int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) { 724 int count = fSegments.count(); 725 int sum = 0; 726 for (int index = 0; index < count; ++index) { 727 sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest); 728 } 729 // SkDebugf("%s sum=%d\n", __FUNCTION__, sum); 730 return sum; 731 } 732 733 void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) { 734 // int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13; 735 // int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16; 736 int ofInterest = 1 << 5 | 1 << 8; 737 int total = 0; 738 int index; 739 for (index = 0; index < contourList.count(); ++index) { 740 total += contourList[index]->segments().count(); 741 } 742 int sum = 0; 743 for (index = 0; index < contourList.count(); ++index) { 744 sum += contourList[index]->debugShowWindingValues(total, ofInterest); 745 } 746 // SkDebugf("%s total=%d\n", __FUNCTION__, sum); 747 } 748 #endif 749 750 void SkOpContour::setBounds() { 751 int count = fSegments.count(); 752 if (count == 0) { 753 SkDebugf("%s empty contour\n", __FUNCTION__); 754 SkASSERT(0); 755 // FIXME: delete empty contour? 756 return; 757 } 758 fBounds = fSegments.front().bounds(); 759 for (int index = 1; index < count; ++index) { 760 fBounds.add(fSegments[index].bounds()); 761 } 762 } 763
