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