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 "SkIntersections.h" 8 #include "SkOpSegment.h" 9 #include "SkPathWriter.h" 10 #include "SkTSort.h" 11 12 #define F (false) // discard the edge 13 #define T (true) // keep the edge 14 15 static const bool gUnaryActiveEdge[2][2] = { 16 // from=0 from=1 17 // to=0,1 to=0,1 18 {F, T}, {T, F}, 19 }; 20 21 static const bool gActiveEdge[kXOR_PathOp + 1][2][2][2][2] = { 22 // miFrom=0 miFrom=1 23 // miTo=0 miTo=1 miTo=0 miTo=1 24 // suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1 25 // suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 26 {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su 27 {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su 28 {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su 29 {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su 30 }; 31 32 #undef F 33 #undef T 34 35 enum { kOutsideTrackedTCount = 16 }; // FIXME: determine what this should be 36 37 // OPTIMIZATION: does the following also work, and is it any faster? 38 // return outerWinding * innerWinding > 0 39 // || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) 40 bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) { 41 SkASSERT(outerWinding != SK_MaxS32); 42 SkASSERT(innerWinding != SK_MaxS32); 43 int absOut = abs(outerWinding); 44 int absIn = abs(innerWinding); 45 bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; 46 return result; 47 } 48 49 bool SkOpSegment::activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles) { 50 if (activeAngleInner(index, done, angles)) { 51 return true; 52 } 53 int lesser = index; 54 while (--lesser >= 0 && equalPoints(index, lesser)) { 55 if (activeAngleOther(lesser, done, angles)) { 56 return true; 57 } 58 } 59 lesser = index; 60 do { 61 if (activeAngleOther(index, done, angles)) { 62 return true; 63 } 64 } while (++index < fTs.count() && equalPoints(index, lesser)); 65 return false; 66 } 67 68 bool SkOpSegment::activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles) { 69 SkOpSpan* span = &fTs[index]; 70 SkOpSegment* other = span->fOther; 71 int oIndex = span->fOtherIndex; 72 return other->activeAngleInner(oIndex, done, angles); 73 } 74 75 bool SkOpSegment::activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles) { 76 int next = nextExactSpan(index, 1); 77 if (next > 0) { 78 SkOpSpan& upSpan = fTs[index]; 79 if (upSpan.fWindValue || upSpan.fOppValue) { 80 addAngle(angles, index, next); 81 if (upSpan.fDone || upSpan.fUnsortableEnd) { 82 (*done)++; 83 } else if (upSpan.fWindSum != SK_MinS32) { 84 return true; 85 } 86 } else if (!upSpan.fDone) { 87 upSpan.fDone = true; 88 fDoneSpans++; 89 } 90 } 91 int prev = nextExactSpan(index, -1); 92 // edge leading into junction 93 if (prev >= 0) { 94 SkOpSpan& downSpan = fTs[prev]; 95 if (downSpan.fWindValue || downSpan.fOppValue) { 96 addAngle(angles, index, prev); 97 if (downSpan.fDone) { 98 (*done)++; 99 } else if (downSpan.fWindSum != SK_MinS32) { 100 return true; 101 } 102 } else if (!downSpan.fDone) { 103 downSpan.fDone = true; 104 fDoneSpans++; 105 } 106 } 107 return false; 108 } 109 110 SkPoint SkOpSegment::activeLeftTop(bool onlySortable, int* firstT) const { 111 SkASSERT(!done()); 112 SkPoint topPt = {SK_ScalarMax, SK_ScalarMax}; 113 int count = fTs.count(); 114 // see if either end is not done since we want smaller Y of the pair 115 bool lastDone = true; 116 bool lastUnsortable = false; 117 double lastT = -1; 118 for (int index = 0; index < count; ++index) { 119 const SkOpSpan& span = fTs[index]; 120 if (onlySortable && (span.fUnsortableStart || lastUnsortable)) { 121 goto next; 122 } 123 if (span.fDone && lastDone) { 124 goto next; 125 } 126 if (approximately_negative(span.fT - lastT)) { 127 goto next; 128 } 129 { 130 const SkPoint& xy = xyAtT(&span); 131 if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) { 132 topPt = xy; 133 if (firstT) { 134 *firstT = index; 135 } 136 } 137 if (fVerb != SkPath::kLine_Verb && !lastDone) { 138 SkPoint curveTop = (*CurveTop[SkPathOpsVerbToPoints(fVerb)])(fPts, lastT, span.fT); 139 if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY 140 && topPt.fX > curveTop.fX)) { 141 topPt = curveTop; 142 if (firstT) { 143 *firstT = index; 144 } 145 } 146 } 147 lastT = span.fT; 148 } 149 next: 150 lastDone = span.fDone; 151 lastUnsortable = span.fUnsortableEnd; 152 } 153 return topPt; 154 } 155 156 bool SkOpSegment::activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op) { 157 int sumMiWinding = updateWinding(endIndex, index); 158 int sumSuWinding = updateOppWinding(endIndex, index); 159 if (fOperand) { 160 SkTSwap<int>(sumMiWinding, sumSuWinding); 161 } 162 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 163 return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &sumSuWinding, 164 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 165 } 166 167 bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op, 168 int* sumMiWinding, int* sumSuWinding, 169 int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) { 170 setUpWindings(index, endIndex, sumMiWinding, sumSuWinding, 171 maxWinding, sumWinding, oppMaxWinding, oppSumWinding); 172 bool miFrom; 173 bool miTo; 174 bool suFrom; 175 bool suTo; 176 if (operand()) { 177 miFrom = (*oppMaxWinding & xorMiMask) != 0; 178 miTo = (*oppSumWinding & xorMiMask) != 0; 179 suFrom = (*maxWinding & xorSuMask) != 0; 180 suTo = (*sumWinding & xorSuMask) != 0; 181 } else { 182 miFrom = (*maxWinding & xorMiMask) != 0; 183 miTo = (*sumWinding & xorMiMask) != 0; 184 suFrom = (*oppMaxWinding & xorSuMask) != 0; 185 suTo = (*oppSumWinding & xorSuMask) != 0; 186 } 187 bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo]; 188 #if DEBUG_ACTIVE_OP 189 SkDebugf("%s op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", __FUNCTION__, 190 kPathOpStr[op], miFrom, miTo, suFrom, suTo, result); 191 #endif 192 return result; 193 } 194 195 bool SkOpSegment::activeWinding(int index, int endIndex) { 196 int sumWinding = updateWinding(endIndex, index); 197 int maxWinding; 198 return activeWinding(index, endIndex, &maxWinding, &sumWinding); 199 } 200 201 bool SkOpSegment::activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding) { 202 setUpWinding(index, endIndex, maxWinding, sumWinding); 203 bool from = *maxWinding != 0; 204 bool to = *sumWinding != 0; 205 bool result = gUnaryActiveEdge[from][to]; 206 return result; 207 } 208 209 void SkOpSegment::addAngle(SkTArray<SkOpAngle, true>* anglesPtr, int start, int end) const { 210 SkASSERT(start != end); 211 SkOpAngle& angle = anglesPtr->push_back(); 212 #if 0 && DEBUG_ANGLE // computed pt and actual pt may differ by more than approx eq 213 SkTArray<SkOpAngle, true>& angles = *anglesPtr; 214 if (angles.count() > 1) { 215 const SkOpSegment* aSeg = angles[0].segment(); 216 int aStart = angles[0].start(); 217 if (!aSeg->fTs[aStart].fTiny) { 218 const SkPoint& angle0Pt = aSeg->xyAtT(aStart); 219 SkDPoint newPt = (*CurveDPointAtT[SkPathOpsVerbToPoints(aSeg->fVerb)])(aSeg->fPts, 220 aSeg->fTs[aStart].fT); 221 #if ONE_OFF_DEBUG 222 SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g)\n", __FUNCTION__, 223 aSeg->fTs[aStart].fT, newPt.fX, newPt.fY, angle0Pt.fX, angle0Pt.fY); 224 #endif 225 SkASSERT(newPt.approximatelyEqual(angle0Pt)); 226 } 227 } 228 #endif 229 angle.set(this, start, end); 230 } 231 232 void SkOpSegment::addCancelOutsides(double tStart, double oStart, SkOpSegment* other, double oEnd) { 233 int tIndex = -1; 234 int tCount = fTs.count(); 235 int oIndex = -1; 236 int oCount = other->fTs.count(); 237 do { 238 ++tIndex; 239 } while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tCount); 240 int tIndexStart = tIndex; 241 do { 242 ++oIndex; 243 } while (!approximately_negative(oStart - other->fTs[oIndex].fT) && oIndex < oCount); 244 int oIndexStart = oIndex; 245 double nextT; 246 do { 247 nextT = fTs[++tIndex].fT; 248 } while (nextT < 1 && approximately_negative(nextT - tStart)); 249 double oNextT; 250 do { 251 oNextT = other->fTs[++oIndex].fT; 252 } while (oNextT < 1 && approximately_negative(oNextT - oStart)); 253 // at this point, spans before and after are at: 254 // fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex] 255 // if tIndexStart == 0, no prior span 256 // if nextT == 1, no following span 257 258 // advance the span with zero winding 259 // if the following span exists (not past the end, non-zero winding) 260 // connect the two edges 261 if (!fTs[tIndexStart].fWindValue) { 262 if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) { 263 #if DEBUG_CONCIDENT 264 SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 265 __FUNCTION__, fID, other->fID, tIndexStart - 1, 266 fTs[tIndexStart].fT, xyAtT(tIndexStart).fX, 267 xyAtT(tIndexStart).fY); 268 #endif 269 addTPair(fTs[tIndexStart].fT, other, other->fTs[oIndex].fT, false, 270 fTs[tIndexStart].fPt); 271 } 272 if (nextT < 1 && fTs[tIndex].fWindValue) { 273 #if DEBUG_CONCIDENT 274 SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 275 __FUNCTION__, fID, other->fID, tIndex, 276 fTs[tIndex].fT, xyAtT(tIndex).fX, 277 xyAtT(tIndex).fY); 278 #endif 279 addTPair(fTs[tIndex].fT, other, other->fTs[oIndexStart].fT, false, fTs[tIndex].fPt); 280 } 281 } else { 282 SkASSERT(!other->fTs[oIndexStart].fWindValue); 283 if (oIndexStart > 0 && other->fTs[oIndexStart - 1].fWindValue) { 284 #if DEBUG_CONCIDENT 285 SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 286 __FUNCTION__, fID, other->fID, oIndexStart - 1, 287 other->fTs[oIndexStart].fT, other->xyAtT(oIndexStart).fX, 288 other->xyAtT(oIndexStart).fY); 289 other->debugAddTPair(other->fTs[oIndexStart].fT, *this, fTs[tIndex].fT); 290 #endif 291 } 292 if (oNextT < 1 && other->fTs[oIndex].fWindValue) { 293 #if DEBUG_CONCIDENT 294 SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 295 __FUNCTION__, fID, other->fID, oIndex, 296 other->fTs[oIndex].fT, other->xyAtT(oIndex).fX, 297 other->xyAtT(oIndex).fY); 298 other->debugAddTPair(other->fTs[oIndex].fT, *this, fTs[tIndexStart].fT); 299 #endif 300 } 301 } 302 } 303 304 void SkOpSegment::addCoinOutsides(const SkTArray<double, true>& outsideTs, SkOpSegment* other, 305 double oEnd) { 306 // walk this to outsideTs[0] 307 // walk other to outsideTs[1] 308 // if either is > 0, add a pointer to the other, copying adjacent winding 309 int tIndex = -1; 310 int oIndex = -1; 311 double tStart = outsideTs[0]; 312 double oStart = outsideTs[1]; 313 do { 314 ++tIndex; 315 } while (!approximately_negative(tStart - fTs[tIndex].fT)); 316 SkPoint ptStart = fTs[tIndex].fPt; 317 do { 318 ++oIndex; 319 } while (!approximately_negative(oStart - other->fTs[oIndex].fT)); 320 if (tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) { 321 addTPair(tStart, other, oStart, false, ptStart); 322 } 323 tStart = fTs[tIndex].fT; 324 oStart = other->fTs[oIndex].fT; 325 do { 326 double nextT; 327 do { 328 nextT = fTs[++tIndex].fT; 329 } while (approximately_negative(nextT - tStart)); 330 tStart = nextT; 331 ptStart = fTs[tIndex].fPt; 332 do { 333 nextT = other->fTs[++oIndex].fT; 334 } while (approximately_negative(nextT - oStart)); 335 oStart = nextT; 336 if (tStart == 1 && oStart == 1 && fOperand == other->fOperand) { 337 break; 338 } 339 addTPair(tStart, other, oStart, false, ptStart); 340 } while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart)); 341 } 342 343 void SkOpSegment::addCubic(const SkPoint pts[4], bool operand, bool evenOdd) { 344 init(pts, SkPath::kCubic_Verb, operand, evenOdd); 345 fBounds.setCubicBounds(pts); 346 } 347 348 void SkOpSegment::addCurveTo(int start, int end, SkPathWriter* path, bool active) const { 349 SkPoint edge[4]; 350 const SkPoint* ePtr; 351 int lastT = fTs.count() - 1; 352 if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) { 353 ePtr = fPts; 354 } else { 355 // OPTIMIZE? if not active, skip remainder and return xyAtT(end) 356 subDivide(start, end, edge); 357 ePtr = edge; 358 } 359 if (active) { 360 bool reverse = ePtr == fPts && start != 0; 361 if (reverse) { 362 path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]); 363 switch (fVerb) { 364 case SkPath::kLine_Verb: 365 path->deferredLine(ePtr[0]); 366 break; 367 case SkPath::kQuad_Verb: 368 path->quadTo(ePtr[1], ePtr[0]); 369 break; 370 case SkPath::kCubic_Verb: 371 path->cubicTo(ePtr[2], ePtr[1], ePtr[0]); 372 break; 373 default: 374 SkASSERT(0); 375 } 376 // return ePtr[0]; 377 } else { 378 path->deferredMoveLine(ePtr[0]); 379 switch (fVerb) { 380 case SkPath::kLine_Verb: 381 path->deferredLine(ePtr[1]); 382 break; 383 case SkPath::kQuad_Verb: 384 path->quadTo(ePtr[1], ePtr[2]); 385 break; 386 case SkPath::kCubic_Verb: 387 path->cubicTo(ePtr[1], ePtr[2], ePtr[3]); 388 break; 389 default: 390 SkASSERT(0); 391 } 392 } 393 } 394 // return ePtr[SkPathOpsVerbToPoints(fVerb)]; 395 } 396 397 void SkOpSegment::addLine(const SkPoint pts[2], bool operand, bool evenOdd) { 398 init(pts, SkPath::kLine_Verb, operand, evenOdd); 399 fBounds.set(pts, 2); 400 } 401 402 // add 2 to edge or out of range values to get T extremes 403 void SkOpSegment::addOtherT(int index, double otherT, int otherIndex) { 404 SkOpSpan& span = fTs[index]; 405 if (precisely_zero(otherT)) { 406 otherT = 0; 407 } else if (precisely_equal(otherT, 1)) { 408 otherT = 1; 409 } 410 span.fOtherT = otherT; 411 span.fOtherIndex = otherIndex; 412 } 413 414 void SkOpSegment::addQuad(const SkPoint pts[3], bool operand, bool evenOdd) { 415 init(pts, SkPath::kQuad_Verb, operand, evenOdd); 416 fBounds.setQuadBounds(pts); 417 } 418 419 // Defer all coincident edge processing until 420 // after normal intersections have been computed 421 422 // no need to be tricky; insert in normal T order 423 // resolve overlapping ts when considering coincidence later 424 425 // add non-coincident intersection. Resulting edges are sorted in T. 426 int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { 427 if (precisely_zero(newT)) { 428 newT = 0; 429 } else if (precisely_equal(newT, 1)) { 430 newT = 1; 431 } 432 // FIXME: in the pathological case where there is a ton of intercepts, 433 // binary search? 434 int insertedAt = -1; 435 size_t tCount = fTs.count(); 436 for (size_t index = 0; index < tCount; ++index) { 437 // OPTIMIZATION: if there are three or more identical Ts, then 438 // the fourth and following could be further insertion-sorted so 439 // that all the edges are clockwise or counterclockwise. 440 // This could later limit segment tests to the two adjacent 441 // neighbors, although it doesn't help with determining which 442 // circular direction to go in. 443 if (newT < fTs[index].fT) { 444 insertedAt = index; 445 break; 446 } 447 } 448 SkOpSpan* span; 449 if (insertedAt >= 0) { 450 span = fTs.insert(insertedAt); 451 } else { 452 insertedAt = tCount; 453 span = fTs.append(); 454 } 455 span->fT = newT; 456 span->fOther = other; 457 span->fPt = pt; 458 #if 0 459 // cubics, for instance, may not be exact enough to satisfy this check (e.g., cubicOp69d) 460 SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX) 461 && approximately_equal(xyAtT(newT).fY, pt.fY)); 462 #endif 463 span->fWindSum = SK_MinS32; 464 span->fOppSum = SK_MinS32; 465 span->fWindValue = 1; 466 span->fOppValue = 0; 467 span->fTiny = false; 468 span->fLoop = false; 469 if ((span->fDone = newT == 1)) { 470 ++fDoneSpans; 471 } 472 span->fUnsortableStart = false; 473 span->fUnsortableEnd = false; 474 int less = -1; 475 while (&span[less + 1] - fTs.begin() > 0 && xyAtT(&span[less]) == xyAtT(span)) { 476 if (span[less].fDone) { 477 break; 478 } 479 double tInterval = newT - span[less].fT; 480 if (precisely_negative(tInterval)) { 481 break; 482 } 483 if (fVerb == SkPath::kCubic_Verb) { 484 double tMid = newT - tInterval / 2; 485 SkDPoint midPt = dcubic_xy_at_t(fPts, tMid); 486 if (!midPt.approximatelyEqual(xyAtT(span))) { 487 break; 488 } 489 } 490 span[less].fTiny = true; 491 span[less].fDone = true; 492 if (approximately_negative(newT - span[less].fT)) { 493 if (approximately_greater_than_one(newT)) { 494 SkASSERT(&span[less] - fTs.begin() < fTs.count()); 495 span[less].fUnsortableStart = true; 496 if (&span[less - 1] - fTs.begin() >= 0) { 497 span[less - 1].fUnsortableEnd = true; 498 } 499 } 500 if (approximately_less_than_zero(span[less].fT)) { 501 SkASSERT(&span[less + 1] - fTs.begin() < fTs.count()); 502 SkASSERT(&span[less] - fTs.begin() >= 0); 503 span[less + 1].fUnsortableStart = true; 504 span[less].fUnsortableEnd = true; 505 } 506 } 507 ++fDoneSpans; 508 --less; 509 } 510 int more = 1; 511 while (fTs.end() - &span[more - 1] > 1 && xyAtT(&span[more]) == xyAtT(span)) { 512 if (span[more - 1].fDone) { 513 break; 514 } 515 double tEndInterval = span[more].fT - newT; 516 if (precisely_negative(tEndInterval)) { 517 break; 518 } 519 if (fVerb == SkPath::kCubic_Verb) { 520 double tMid = newT - tEndInterval / 2; 521 SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid); 522 if (!midEndPt.approximatelyEqual(xyAtT(span))) { 523 break; 524 } 525 } 526 span[more - 1].fTiny = true; 527 span[more - 1].fDone = true; 528 if (approximately_negative(span[more].fT - newT)) { 529 if (approximately_greater_than_one(span[more].fT)) { 530 span[more + 1].fUnsortableStart = true; 531 span[more].fUnsortableEnd = true; 532 } 533 if (approximately_less_than_zero(newT)) { 534 span[more].fUnsortableStart = true; 535 span[more - 1].fUnsortableEnd = true; 536 } 537 } 538 ++fDoneSpans; 539 ++more; 540 } 541 return insertedAt; 542 } 543 544 // set spans from start to end to decrement by one 545 // note this walks other backwards 546 // FIXME: there's probably an edge case that can be constructed where 547 // two span in one segment are separated by float epsilon on one span but 548 // not the other, if one segment is very small. For this 549 // case the counts asserted below may or may not be enough to separate the 550 // spans. Even if the counts work out, what if the spans aren't correctly 551 // sorted? It feels better in such a case to match the span's other span 552 // pointer since both coincident segments must contain the same spans. 553 // FIXME? It seems that decrementing by one will fail for complex paths that 554 // have three or more coincident edges. Shouldn't this subtract the difference 555 // between the winding values? 556 void SkOpSegment::addTCancel(double startT, double endT, SkOpSegment* other, 557 double oStartT, double oEndT) { 558 SkASSERT(!approximately_negative(endT - startT)); 559 SkASSERT(!approximately_negative(oEndT - oStartT)); 560 bool binary = fOperand != other->fOperand; 561 int index = 0; 562 while (!approximately_negative(startT - fTs[index].fT)) { 563 ++index; 564 } 565 int oIndex = other->fTs.count(); 566 while (approximately_positive(other->fTs[--oIndex].fT - oEndT)) 567 ; 568 double tRatio = (oEndT - oStartT) / (endT - startT); 569 SkOpSpan* test = &fTs[index]; 570 SkOpSpan* oTest = &other->fTs[oIndex]; 571 SkSTArray<kOutsideTrackedTCount, double, true> outsideTs; 572 SkSTArray<kOutsideTrackedTCount, double, true> oOutsideTs; 573 do { 574 bool decrement = test->fWindValue && oTest->fWindValue; 575 bool track = test->fWindValue || oTest->fWindValue; 576 bool bigger = test->fWindValue >= oTest->fWindValue; 577 double testT = test->fT; 578 double oTestT = oTest->fT; 579 SkOpSpan* span = test; 580 do { 581 if (decrement) { 582 if (binary && bigger) { 583 span->fOppValue--; 584 } else { 585 decrementSpan(span); 586 } 587 } else if (track && span->fT < 1 && oTestT < 1) { 588 TrackOutside(&outsideTs, span->fT, oTestT); 589 } 590 span = &fTs[++index]; 591 } while (approximately_negative(span->fT - testT)); 592 SkOpSpan* oSpan = oTest; 593 double otherTMatchStart = oEndT - (span->fT - startT) * tRatio; 594 double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio; 595 SkDEBUGCODE(int originalWindValue = oSpan->fWindValue); 596 while (approximately_negative(otherTMatchStart - oSpan->fT) 597 && !approximately_negative(otherTMatchEnd - oSpan->fT)) { 598 #ifdef SK_DEBUG 599 SkASSERT(originalWindValue == oSpan->fWindValue); 600 #endif 601 if (decrement) { 602 if (binary && !bigger) { 603 oSpan->fOppValue--; 604 } else { 605 other->decrementSpan(oSpan); 606 } 607 } else if (track && oSpan->fT < 1 && testT < 1) { 608 TrackOutside(&oOutsideTs, oSpan->fT, testT); 609 } 610 if (!oIndex) { 611 break; 612 } 613 oSpan = &other->fTs[--oIndex]; 614 } 615 test = span; 616 oTest = oSpan; 617 } while (!approximately_negative(endT - test->fT)); 618 SkASSERT(!oIndex || approximately_negative(oTest->fT - oStartT)); 619 // FIXME: determine if canceled edges need outside ts added 620 if (!done() && outsideTs.count()) { 621 double tStart = outsideTs[0]; 622 double oStart = outsideTs[1]; 623 addCancelOutsides(tStart, oStart, other, oEndT); 624 int count = outsideTs.count(); 625 if (count > 2) { 626 double tStart = outsideTs[count - 2]; 627 double oStart = outsideTs[count - 1]; 628 addCancelOutsides(tStart, oStart, other, oEndT); 629 } 630 } 631 if (!other->done() && oOutsideTs.count()) { 632 double tStart = oOutsideTs[0]; 633 double oStart = oOutsideTs[1]; 634 other->addCancelOutsides(tStart, oStart, this, endT); 635 } 636 } 637 638 int SkOpSegment::addSelfT(SkOpSegment* other, const SkPoint& pt, double newT) { 639 int result = addT(other, pt, newT); 640 SkOpSpan* span = &fTs[result]; 641 span->fLoop = true; 642 return result; 643 } 644 645 int SkOpSegment::addUnsortableT(SkOpSegment* other, bool start, const SkPoint& pt, double newT) { 646 int result = addT(other, pt, newT); 647 SkOpSpan* span = &fTs[result]; 648 if (start) { 649 if (result > 0) { 650 span[result - 1].fUnsortableEnd = true; 651 } 652 span[result].fUnsortableStart = true; 653 } else { 654 span[result].fUnsortableEnd = true; 655 if (result + 1 < fTs.count()) { 656 span[result + 1].fUnsortableStart = true; 657 } 658 } 659 return result; 660 } 661 662 int SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool opp, int index, 663 SkTArray<double, true>* outsideTs) { 664 int oWindValue = oTest.fWindValue; 665 int oOppValue = oTest.fOppValue; 666 if (opp) { 667 SkTSwap<int>(oWindValue, oOppValue); 668 } 669 SkOpSpan* const test = &fTs[index]; 670 SkOpSpan* end = test; 671 const double oStartT = oTest.fT; 672 do { 673 if (bumpSpan(end, oWindValue, oOppValue)) { 674 TrackOutside(outsideTs, end->fT, oStartT); 675 } 676 end = &fTs[++index]; 677 } while (approximately_negative(end->fT - test->fT)); 678 return index; 679 } 680 681 // because of the order in which coincidences are resolved, this and other 682 // may not have the same intermediate points. Compute the corresponding 683 // intermediate T values (using this as the master, other as the follower) 684 // and walk other conditionally -- hoping that it catches up in the end 685 int SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, double oEndT, int& oIndex, 686 SkTArray<double, true>* oOutsideTs) { 687 SkOpSpan* const oTest = &fTs[oIndex]; 688 SkOpSpan* oEnd = oTest; 689 const double startT = test.fT; 690 const double oStartT = oTest->fT; 691 while (!approximately_negative(oEndT - oEnd->fT) 692 && approximately_negative(oEnd->fT - oStartT)) { 693 zeroSpan(oEnd); 694 TrackOutside(oOutsideTs, oEnd->fT, startT); 695 oEnd = &fTs[++oIndex]; 696 } 697 return oIndex; 698 } 699 700 // FIXME: need to test this case: 701 // contourA has two segments that are coincident 702 // contourB has two segments that are coincident in the same place 703 // each ends up with +2/0 pairs for winding count 704 // since logic below doesn't transfer count (only increments/decrements) can this be 705 // resolved to +4/0 ? 706 707 // set spans from start to end to increment the greater by one and decrement 708 // the lesser 709 void SkOpSegment::addTCoincident(double startT, double endT, SkOpSegment* other, double oStartT, 710 double oEndT) { 711 SkASSERT(!approximately_negative(endT - startT)); 712 SkASSERT(!approximately_negative(oEndT - oStartT)); 713 bool opp = fOperand ^ other->fOperand; 714 int index = 0; 715 while (!approximately_negative(startT - fTs[index].fT)) { 716 ++index; 717 } 718 int oIndex = 0; 719 while (!approximately_negative(oStartT - other->fTs[oIndex].fT)) { 720 ++oIndex; 721 } 722 SkOpSpan* test = &fTs[index]; 723 SkOpSpan* oTest = &other->fTs[oIndex]; 724 SkSTArray<kOutsideTrackedTCount, double, true> outsideTs; 725 SkSTArray<kOutsideTrackedTCount, double, true> oOutsideTs; 726 do { 727 // if either span has an opposite value and the operands don't match, resolve first 728 // SkASSERT(!test->fDone || !oTest->fDone); 729 if (test->fDone || oTest->fDone) { 730 index = advanceCoincidentThis(oTest, opp, index); 731 oIndex = other->advanceCoincidentOther(test, oEndT, oIndex); 732 } else { 733 index = bumpCoincidentThis(*oTest, opp, index, &outsideTs); 734 oIndex = other->bumpCoincidentOther(*test, oEndT, oIndex, &oOutsideTs); 735 } 736 test = &fTs[index]; 737 oTest = &other->fTs[oIndex]; 738 } while (!approximately_negative(endT - test->fT)); 739 SkASSERT(approximately_negative(oTest->fT - oEndT)); 740 SkASSERT(approximately_negative(oEndT - oTest->fT)); 741 if (!done() && outsideTs.count()) { 742 addCoinOutsides(outsideTs, other, oEndT); 743 } 744 if (!other->done() && oOutsideTs.count()) { 745 other->addCoinOutsides(oOutsideTs, this, endT); 746 } 747 } 748 749 // FIXME: this doesn't prevent the same span from being added twice 750 // fix in caller, SkASSERT here? 751 void SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, 752 const SkPoint& pt) { 753 int tCount = fTs.count(); 754 for (int tIndex = 0; tIndex < tCount; ++tIndex) { 755 const SkOpSpan& span = fTs[tIndex]; 756 if (!approximately_negative(span.fT - t)) { 757 break; 758 } 759 if (approximately_negative(span.fT - t) && span.fOther == other 760 && approximately_equal(span.fOtherT, otherT)) { 761 #if DEBUG_ADD_T_PAIR 762 SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n", 763 __FUNCTION__, fID, t, other->fID, otherT); 764 #endif 765 return; 766 } 767 } 768 #if DEBUG_ADD_T_PAIR 769 SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n", 770 __FUNCTION__, fID, t, other->fID, otherT); 771 #endif 772 int insertedAt = addT(other, pt, t); 773 int otherInsertedAt = other->addT(this, pt, otherT); 774 addOtherT(insertedAt, otherT, otherInsertedAt); 775 other->addOtherT(otherInsertedAt, t, insertedAt); 776 matchWindingValue(insertedAt, t, borrowWind); 777 other->matchWindingValue(otherInsertedAt, otherT, borrowWind); 778 } 779 780 void SkOpSegment::addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const { 781 // add edge leading into junction 782 int min = SkMin32(end, start); 783 if (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0) { 784 addAngle(angles, end, start); 785 } 786 // add edge leading away from junction 787 int step = SkSign32(end - start); 788 int tIndex = nextExactSpan(end, step); 789 min = SkMin32(end, tIndex); 790 if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0)) { 791 addAngle(angles, end, tIndex); 792 } 793 } 794 795 int SkOpSegment::advanceCoincidentThis(const SkOpSpan* oTest, bool opp, int index) { 796 SkOpSpan* const test = &fTs[index]; 797 SkOpSpan* end; 798 do { 799 end = &fTs[++index]; 800 } while (approximately_negative(end->fT - test->fT)); 801 return index; 802 } 803 804 int SkOpSegment::advanceCoincidentOther(const SkOpSpan* test, double oEndT, int oIndex) { 805 SkOpSpan* const oTest = &fTs[oIndex]; 806 SkOpSpan* oEnd = oTest; 807 const double oStartT = oTest->fT; 808 while (!approximately_negative(oEndT - oEnd->fT) 809 && approximately_negative(oEnd->fT - oStartT)) { 810 oEnd = &fTs[++oIndex]; 811 } 812 return oIndex; 813 } 814 815 bool SkOpSegment::betweenTs(int lesser, double testT, int greater) const { 816 if (lesser > greater) { 817 SkTSwap<int>(lesser, greater); 818 } 819 return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT); 820 } 821 822 void SkOpSegment::buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const { 823 double referenceT = fTs[index].fT; 824 int lesser = index; 825 while (--lesser >= 0 && (includeOpp || fTs[lesser].fOther->fOperand == fOperand) 826 && precisely_negative(referenceT - fTs[lesser].fT)) { 827 buildAnglesInner(lesser, angles); 828 } 829 do { 830 buildAnglesInner(index, angles); 831 } while (++index < fTs.count() && (includeOpp || fTs[index].fOther->fOperand == fOperand) 832 && precisely_negative(fTs[index].fT - referenceT)); 833 } 834 835 void SkOpSegment::buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const { 836 const SkOpSpan* span = &fTs[index]; 837 SkOpSegment* other = span->fOther; 838 // if there is only one live crossing, and no coincidence, continue 839 // in the same direction 840 // if there is coincidence, the only choice may be to reverse direction 841 // find edge on either side of intersection 842 int oIndex = span->fOtherIndex; 843 // if done == -1, prior span has already been processed 844 int step = 1; 845 int next = other->nextExactSpan(oIndex, step); 846 if (next < 0) { 847 step = -step; 848 next = other->nextExactSpan(oIndex, step); 849 } 850 // add candidate into and away from junction 851 other->addTwoAngles(next, oIndex, angles); 852 } 853 854 int SkOpSegment::computeSum(int startIndex, int endIndex, bool binary) { 855 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; 856 addTwoAngles(startIndex, endIndex, &angles); 857 buildAngles(endIndex, &angles, false); 858 // OPTIMIZATION: check all angles to see if any have computed wind sum 859 // before sorting (early exit if none) 860 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; 861 // FIXME?: Not sure if this sort must be ordered or if the relaxed ordering is OK ... 862 bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind); 863 #if DEBUG_SORT 864 sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0, sortable); 865 #endif 866 if (!sortable) { 867 return SK_MinS32; 868 } 869 int angleCount = angles.count(); 870 const SkOpAngle* angle; 871 const SkOpSegment* base; 872 int winding; 873 int oWinding; 874 int firstIndex = 0; 875 do { 876 angle = sorted[firstIndex]; 877 base = angle->segment(); 878 winding = base->windSum(angle); 879 if (winding != SK_MinS32) { 880 oWinding = base->oppSum(angle); 881 break; 882 } 883 if (++firstIndex == angleCount) { 884 return SK_MinS32; 885 } 886 } while (true); 887 // turn winding into contourWinding 888 int spanWinding = base->spanSign(angle); 889 bool inner = UseInnerWinding(winding + spanWinding, winding); 890 #if DEBUG_WINDING 891 SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__, 892 spanWinding, winding, angle->sign(), inner, 893 inner ? winding + spanWinding : winding); 894 #endif 895 if (inner) { 896 winding += spanWinding; 897 } 898 #if DEBUG_SORT 899 base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding, sortable); 900 #endif 901 int nextIndex = firstIndex + 1; 902 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 903 winding -= base->spanSign(angle); 904 oWinding -= base->oppSign(angle); 905 do { 906 if (nextIndex == angleCount) { 907 nextIndex = 0; 908 } 909 angle = sorted[nextIndex]; 910 SkOpSegment* segment = angle->segment(); 911 bool opp = base->fOperand ^ segment->fOperand; 912 int maxWinding, oMaxWinding; 913 int spanSign = segment->spanSign(angle); 914 int oppoSign = segment->oppSign(angle); 915 if (opp) { 916 oMaxWinding = oWinding; 917 oWinding -= spanSign; 918 maxWinding = winding; 919 if (oppoSign) { 920 winding -= oppoSign; 921 } 922 } else { 923 maxWinding = winding; 924 winding -= spanSign; 925 oMaxWinding = oWinding; 926 if (oppoSign) { 927 oWinding -= oppoSign; 928 } 929 } 930 if (segment->windSum(angle) == SK_MinS32) { 931 if (opp) { 932 if (UseInnerWinding(oMaxWinding, oWinding)) { 933 oMaxWinding = oWinding; 934 } 935 if (oppoSign && UseInnerWinding(maxWinding, winding)) { 936 maxWinding = winding; 937 } 938 #ifdef SK_DEBUG 939 SkASSERT(abs(maxWinding) <= gDebugMaxWindSum); 940 SkASSERT(abs(oMaxWinding) <= gDebugMaxWindSum); 941 #endif 942 (void) segment->markAndChaseWinding(angle, oMaxWinding, maxWinding); 943 } else { 944 if (UseInnerWinding(maxWinding, winding)) { 945 maxWinding = winding; 946 } 947 if (oppoSign && UseInnerWinding(oMaxWinding, oWinding)) { 948 oMaxWinding = oWinding; 949 } 950 #ifdef SK_DEBUG 951 SkASSERT(abs(maxWinding) <= gDebugMaxWindSum); 952 SkASSERT(abs(binary ? oMaxWinding : 0) <= gDebugMaxWindSum); 953 #endif 954 (void) segment->markAndChaseWinding(angle, maxWinding, 955 binary ? oMaxWinding : 0); 956 } 957 } 958 } while (++nextIndex != lastIndex); 959 int minIndex = SkMin32(startIndex, endIndex); 960 return windSum(minIndex); 961 } 962 963 int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, 964 bool* hitSomething, double mid, bool opp, bool current) const { 965 SkScalar bottom = fBounds.fBottom; 966 int bestTIndex = -1; 967 if (bottom <= *bestY) { 968 return bestTIndex; 969 } 970 SkScalar top = fBounds.fTop; 971 if (top >= basePt.fY) { 972 return bestTIndex; 973 } 974 if (fBounds.fLeft > basePt.fX) { 975 return bestTIndex; 976 } 977 if (fBounds.fRight < basePt.fX) { 978 return bestTIndex; 979 } 980 if (fBounds.fLeft == fBounds.fRight) { 981 // if vertical, and directly above test point, wait for another one 982 return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex; 983 } 984 // intersect ray starting at basePt with edge 985 SkIntersections intersections; 986 // OPTIMIZE: use specialty function that intersects ray with curve, 987 // returning t values only for curve (we don't care about t on ray) 988 int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)]) 989 (fPts, top, bottom, basePt.fX, false); 990 if (pts == 0 || (current && pts == 1)) { 991 return bestTIndex; 992 } 993 if (current) { 994 SkASSERT(pts > 1); 995 int closestIdx = 0; 996 double closest = fabs(intersections[0][0] - mid); 997 for (int idx = 1; idx < pts; ++idx) { 998 double test = fabs(intersections[0][idx] - mid); 999 if (closest > test) { 1000 closestIdx = idx; 1001 closest = test; 1002 } 1003 } 1004 intersections.quickRemoveOne(closestIdx, --pts); 1005 } 1006 double bestT = -1; 1007 for (int index = 0; index < pts; ++index) { 1008 double foundT = intersections[0][index]; 1009 if (approximately_less_than_zero(foundT) 1010 || approximately_greater_than_one(foundT)) { 1011 continue; 1012 } 1013 SkScalar testY = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fY; 1014 if (approximately_negative(testY - *bestY) 1015 || approximately_negative(basePt.fY - testY)) { 1016 continue; 1017 } 1018 if (pts > 1 && fVerb == SkPath::kLine_Verb) { 1019 return SK_MinS32; // if the intersection is edge on, wait for another one 1020 } 1021 if (fVerb > SkPath::kLine_Verb) { 1022 SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fX; 1023 if (approximately_zero(dx)) { 1024 return SK_MinS32; // hit vertical, wait for another one 1025 } 1026 } 1027 *bestY = testY; 1028 bestT = foundT; 1029 } 1030 if (bestT < 0) { 1031 return bestTIndex; 1032 } 1033 SkASSERT(bestT >= 0); 1034 SkASSERT(bestT <= 1); 1035 int start; 1036 int end = 0; 1037 do { 1038 start = end; 1039 end = nextSpan(start, 1); 1040 } while (fTs[end].fT < bestT); 1041 // FIXME: see next candidate for a better pattern to find the next start/end pair 1042 while (start + 1 < end && fTs[start].fDone) { 1043 ++start; 1044 } 1045 if (!isCanceled(start)) { 1046 *hitT = bestT; 1047 bestTIndex = start; 1048 *hitSomething = true; 1049 } 1050 return bestTIndex; 1051 } 1052 1053 void SkOpSegment::decrementSpan(SkOpSpan* span) { 1054 SkASSERT(span->fWindValue > 0); 1055 if (--(span->fWindValue) == 0) { 1056 if (!span->fOppValue && !span->fDone) { 1057 span->fDone = true; 1058 ++fDoneSpans; 1059 } 1060 } 1061 } 1062 1063 bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) { 1064 SkASSERT(!span->fDone); 1065 span->fWindValue += windDelta; 1066 SkASSERT(span->fWindValue >= 0); 1067 span->fOppValue += oppDelta; 1068 SkASSERT(span->fOppValue >= 0); 1069 if (fXor) { 1070 span->fWindValue &= 1; 1071 } 1072 if (fOppXor) { 1073 span->fOppValue &= 1; 1074 } 1075 if (!span->fWindValue && !span->fOppValue) { 1076 span->fDone = true; 1077 ++fDoneSpans; 1078 return true; 1079 } 1080 return false; 1081 } 1082 1083 // look to see if the curve end intersects an intermediary that intersects the other 1084 void SkOpSegment::checkEnds() { 1085 debugValidate(); 1086 SkTDArray<SkOpSpan> missingSpans; 1087 int count = fTs.count(); 1088 for (int index = 0; index < count; ++index) { 1089 const SkOpSpan& span = fTs[index]; 1090 const SkOpSegment* other = span.fOther; 1091 const SkOpSpan* otherSpan = &other->fTs[span.fOtherIndex]; 1092 double otherT = otherSpan->fT; 1093 if (otherT != 0 && otherT != 1) { 1094 continue; 1095 } 1096 int peekStart = span.fOtherIndex; 1097 while (peekStart > 0) { 1098 const SkOpSpan* peeker = &other->fTs[peekStart - 1]; 1099 if (peeker->fT != otherT) { 1100 break; 1101 } 1102 --peekStart; 1103 } 1104 int otherLast = other->fTs.count() - 1; 1105 int peekLast = span.fOtherIndex; 1106 while (peekLast < otherLast) { 1107 const SkOpSpan* peeker = &other->fTs[peekLast + 1]; 1108 if (peeker->fT != otherT) { 1109 break; 1110 } 1111 ++peekLast; 1112 } 1113 if (peekStart == peekLast) { 1114 continue; 1115 } 1116 double t = span.fT; 1117 int tStart = index; 1118 while (tStart > 0 && t == fTs[tStart - 1].fT) { 1119 --tStart; 1120 } 1121 int tLast = index; 1122 int last = count - 1; 1123 while (tLast < last && t == fTs[tLast + 1].fT) { 1124 ++tLast; 1125 } 1126 for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) { 1127 if (peekIndex == span.fOtherIndex) { 1128 continue; 1129 } 1130 const SkOpSpan& peekSpan = other->fTs[peekIndex]; 1131 SkOpSegment* match = peekSpan.fOther; 1132 const double matchT = peekSpan.fOtherT; 1133 for (int tIndex = tStart; tIndex <= tLast; ++tIndex) { 1134 const SkOpSpan& tSpan = fTs[tIndex]; 1135 if (tSpan.fOther == match && tSpan.fOtherT == matchT) { 1136 goto nextPeeker; 1137 } 1138 } 1139 // this segment is missing a entry that the other contains 1140 // remember so we can add the missing one and recompute the indices 1141 SkOpSpan* missing = missingSpans.append(); 1142 missing->fT = t; 1143 missing->fOther = match; 1144 missing->fOtherT = matchT; 1145 missing->fPt = peekSpan.fPt; 1146 } 1147 nextPeeker: 1148 ; 1149 } 1150 int missingCount = missingSpans.count(); 1151 if (missingCount == 0) { 1152 return; 1153 } 1154 debugValidate(); 1155 for (int index = 0; index < missingCount; ++index) { 1156 const SkOpSpan& missing = missingSpans[index]; 1157 addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt); 1158 } 1159 fixOtherTIndex(); 1160 for (int index = 0; index < missingCount; ++index) { 1161 const SkOpSpan& missing = missingSpans[index]; 1162 missing.fOther->fixOtherTIndex(); 1163 } 1164 debugValidate(); 1165 } 1166 1167 bool SkOpSegment::equalPoints(int greaterTIndex, int lesserTIndex) { 1168 SkASSERT(greaterTIndex >= lesserTIndex); 1169 double greaterT = fTs[greaterTIndex].fT; 1170 double lesserT = fTs[lesserTIndex].fT; 1171 if (greaterT == lesserT) { 1172 return true; 1173 } 1174 if (!approximately_negative(greaterT - lesserT)) { 1175 return false; 1176 } 1177 return xyAtT(greaterTIndex) == xyAtT(lesserTIndex); 1178 } 1179 1180 /* 1181 The M and S variable name parts stand for the operators. 1182 Mi stands for Minuend (see wiki subtraction, analogous to difference) 1183 Su stands for Subtrahend 1184 The Opp variable name part designates that the value is for the Opposite operator. 1185 Opposite values result from combining coincident spans. 1186 */ 1187 SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd, 1188 bool* unsortable, SkPathOp op, const int xorMiMask, 1189 const int xorSuMask) { 1190 const int startIndex = *nextStart; 1191 const int endIndex = *nextEnd; 1192 SkASSERT(startIndex != endIndex); 1193 SkDEBUGCODE(const int count = fTs.count()); 1194 SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0); 1195 const int step = SkSign32(endIndex - startIndex); 1196 const int end = nextExactSpan(startIndex, step); 1197 SkASSERT(end >= 0); 1198 SkOpSpan* endSpan = &fTs[end]; 1199 SkOpSegment* other; 1200 if (isSimple(end)) { 1201 // mark the smaller of startIndex, endIndex done, and all adjacent 1202 // spans with the same T value (but not 'other' spans) 1203 #if DEBUG_WINDING 1204 SkDebugf("%s simple\n", __FUNCTION__); 1205 #endif 1206 int min = SkMin32(startIndex, endIndex); 1207 if (fTs[min].fDone) { 1208 return NULL; 1209 } 1210 markDoneBinary(min); 1211 other = endSpan->fOther; 1212 *nextStart = endSpan->fOtherIndex; 1213 double startT = other->fTs[*nextStart].fT; 1214 *nextEnd = *nextStart; 1215 do { 1216 *nextEnd += step; 1217 } 1218 while (precisely_zero(startT - other->fTs[*nextEnd].fT)); 1219 SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count()); 1220 if (other->isTiny(SkMin32(*nextStart, *nextEnd))) { 1221 *unsortable = true; 1222 return NULL; 1223 } 1224 return other; 1225 } 1226 // more than one viable candidate -- measure angles to find best 1227 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; 1228 SkASSERT(startIndex - endIndex != 0); 1229 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 1230 addTwoAngles(startIndex, end, &angles); 1231 buildAngles(end, &angles, true); 1232 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; 1233 bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind); 1234 int angleCount = angles.count(); 1235 int firstIndex = findStartingEdge(sorted, startIndex, end); 1236 SkASSERT(firstIndex >= 0); 1237 #if DEBUG_SORT 1238 debugShowSort(__FUNCTION__, sorted, firstIndex, sortable); 1239 #endif 1240 if (!sortable) { 1241 *unsortable = true; 1242 return NULL; 1243 } 1244 SkASSERT(sorted[firstIndex]->segment() == this); 1245 #if DEBUG_WINDING 1246 SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex, 1247 sorted[firstIndex]->sign()); 1248 #endif 1249 int sumMiWinding = updateWinding(endIndex, startIndex); 1250 int sumSuWinding = updateOppWinding(endIndex, startIndex); 1251 if (operand()) { 1252 SkTSwap<int>(sumMiWinding, sumSuWinding); 1253 } 1254 int nextIndex = firstIndex + 1; 1255 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 1256 const SkOpAngle* foundAngle = NULL; 1257 bool foundDone = false; 1258 // iterate through the angle, and compute everyone's winding 1259 SkOpSegment* nextSegment; 1260 int activeCount = 0; 1261 do { 1262 SkASSERT(nextIndex != firstIndex); 1263 if (nextIndex == angleCount) { 1264 nextIndex = 0; 1265 } 1266 const SkOpAngle* nextAngle = sorted[nextIndex]; 1267 nextSegment = nextAngle->segment(); 1268 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 1269 bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(), 1270 nextAngle->end(), op, &sumMiWinding, &sumSuWinding, 1271 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 1272 if (activeAngle) { 1273 ++activeCount; 1274 if (!foundAngle || (foundDone && activeCount & 1)) { 1275 if (nextSegment->isTiny(nextAngle)) { 1276 *unsortable = true; 1277 return NULL; 1278 } 1279 foundAngle = nextAngle; 1280 foundDone = nextSegment->done(nextAngle) && !nextSegment->isTiny(nextAngle); 1281 } 1282 } 1283 if (nextSegment->done()) { 1284 continue; 1285 } 1286 if (nextSegment->windSum(nextAngle) != SK_MinS32) { 1287 continue; 1288 } 1289 SkOpSpan* last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, 1290 oppSumWinding, activeAngle, nextAngle); 1291 if (last) { 1292 *chase->append() = last; 1293 #if DEBUG_WINDING 1294 SkDebugf("%s chase.append id=%d\n", __FUNCTION__, 1295 last->fOther->fTs[last->fOtherIndex].fOther->debugID()); 1296 #endif 1297 } 1298 } while (++nextIndex != lastIndex); 1299 markDoneBinary(SkMin32(startIndex, endIndex)); 1300 if (!foundAngle) { 1301 return NULL; 1302 } 1303 *nextStart = foundAngle->start(); 1304 *nextEnd = foundAngle->end(); 1305 nextSegment = foundAngle->segment(); 1306 1307 #if DEBUG_WINDING 1308 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 1309 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 1310 #endif 1311 return nextSegment; 1312 } 1313 1314 SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, 1315 int* nextEnd, bool* unsortable) { 1316 const int startIndex = *nextStart; 1317 const int endIndex = *nextEnd; 1318 SkASSERT(startIndex != endIndex); 1319 SkDEBUGCODE(const int count = fTs.count()); 1320 SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0); 1321 const int step = SkSign32(endIndex - startIndex); 1322 const int end = nextExactSpan(startIndex, step); 1323 SkASSERT(end >= 0); 1324 SkOpSpan* endSpan = &fTs[end]; 1325 SkOpSegment* other; 1326 if (isSimple(end)) { 1327 // mark the smaller of startIndex, endIndex done, and all adjacent 1328 // spans with the same T value (but not 'other' spans) 1329 #if DEBUG_WINDING 1330 SkDebugf("%s simple\n", __FUNCTION__); 1331 #endif 1332 int min = SkMin32(startIndex, endIndex); 1333 if (fTs[min].fDone) { 1334 return NULL; 1335 } 1336 markDoneUnary(min); 1337 other = endSpan->fOther; 1338 *nextStart = endSpan->fOtherIndex; 1339 double startT = other->fTs[*nextStart].fT; 1340 *nextEnd = *nextStart; 1341 do { 1342 *nextEnd += step; 1343 } 1344 while (precisely_zero(startT - other->fTs[*nextEnd].fT)); 1345 SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count()); 1346 return other; 1347 } 1348 // more than one viable candidate -- measure angles to find best 1349 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; 1350 SkASSERT(startIndex - endIndex != 0); 1351 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 1352 addTwoAngles(startIndex, end, &angles); 1353 buildAngles(end, &angles, true); 1354 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; 1355 bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind); 1356 int angleCount = angles.count(); 1357 int firstIndex = findStartingEdge(sorted, startIndex, end); 1358 SkASSERT(firstIndex >= 0); 1359 #if DEBUG_SORT 1360 debugShowSort(__FUNCTION__, sorted, firstIndex, sortable); 1361 #endif 1362 if (!sortable) { 1363 *unsortable = true; 1364 return NULL; 1365 } 1366 SkASSERT(sorted[firstIndex]->segment() == this); 1367 #if DEBUG_WINDING 1368 SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex, 1369 sorted[firstIndex]->sign()); 1370 #endif 1371 int sumWinding = updateWinding(endIndex, startIndex); 1372 int nextIndex = firstIndex + 1; 1373 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 1374 const SkOpAngle* foundAngle = NULL; 1375 bool foundDone = false; 1376 // iterate through the angle, and compute everyone's winding 1377 SkOpSegment* nextSegment; 1378 int activeCount = 0; 1379 do { 1380 SkASSERT(nextIndex != firstIndex); 1381 if (nextIndex == angleCount) { 1382 nextIndex = 0; 1383 } 1384 const SkOpAngle* nextAngle = sorted[nextIndex]; 1385 nextSegment = nextAngle->segment(); 1386 int maxWinding; 1387 bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(), 1388 &maxWinding, &sumWinding); 1389 if (activeAngle) { 1390 ++activeCount; 1391 if (!foundAngle || (foundDone && activeCount & 1)) { 1392 if (nextSegment->isTiny(nextAngle)) { 1393 *unsortable = true; 1394 return NULL; 1395 } 1396 foundAngle = nextAngle; 1397 foundDone = nextSegment->done(nextAngle); 1398 } 1399 } 1400 if (nextSegment->done()) { 1401 continue; 1402 } 1403 if (nextSegment->windSum(nextAngle) != SK_MinS32) { 1404 continue; 1405 } 1406 SkOpSpan* last = nextSegment->markAngle(maxWinding, sumWinding, activeAngle, nextAngle); 1407 if (last) { 1408 *chase->append() = last; 1409 #if DEBUG_WINDING 1410 SkDebugf("%s chase.append id=%d\n", __FUNCTION__, 1411 last->fOther->fTs[last->fOtherIndex].fOther->debugID()); 1412 #endif 1413 } 1414 } while (++nextIndex != lastIndex); 1415 markDoneUnary(SkMin32(startIndex, endIndex)); 1416 if (!foundAngle) { 1417 return NULL; 1418 } 1419 *nextStart = foundAngle->start(); 1420 *nextEnd = foundAngle->end(); 1421 nextSegment = foundAngle->segment(); 1422 #if DEBUG_WINDING 1423 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 1424 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 1425 #endif 1426 return nextSegment; 1427 } 1428 1429 SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsortable) { 1430 const int startIndex = *nextStart; 1431 const int endIndex = *nextEnd; 1432 SkASSERT(startIndex != endIndex); 1433 SkDEBUGCODE(int count = fTs.count()); 1434 SkASSERT(startIndex < endIndex ? startIndex < count - 1 1435 : startIndex > 0); 1436 int step = SkSign32(endIndex - startIndex); 1437 int end = nextExactSpan(startIndex, step); 1438 SkASSERT(end >= 0); 1439 SkOpSpan* endSpan = &fTs[end]; 1440 SkOpSegment* other; 1441 if (isSimple(end)) { 1442 #if DEBUG_WINDING 1443 SkDebugf("%s simple\n", __FUNCTION__); 1444 #endif 1445 int min = SkMin32(startIndex, endIndex); 1446 if (fTs[min].fDone) { 1447 return NULL; 1448 } 1449 markDone(min, 1); 1450 other = endSpan->fOther; 1451 *nextStart = endSpan->fOtherIndex; 1452 double startT = other->fTs[*nextStart].fT; 1453 // FIXME: I don't know why the logic here is difference from the winding case 1454 SkDEBUGCODE(bool firstLoop = true;) 1455 if ((approximately_less_than_zero(startT) && step < 0) 1456 || (approximately_greater_than_one(startT) && step > 0)) { 1457 step = -step; 1458 SkDEBUGCODE(firstLoop = false;) 1459 } 1460 do { 1461 *nextEnd = *nextStart; 1462 do { 1463 *nextEnd += step; 1464 } 1465 while (precisely_zero(startT - other->fTs[*nextEnd].fT)); 1466 if (other->fTs[SkMin32(*nextStart, *nextEnd)].fWindValue) { 1467 break; 1468 } 1469 #ifdef SK_DEBUG 1470 SkASSERT(firstLoop); 1471 #endif 1472 SkDEBUGCODE(firstLoop = false;) 1473 step = -step; 1474 } while (true); 1475 SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count()); 1476 return other; 1477 } 1478 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; 1479 SkASSERT(startIndex - endIndex != 0); 1480 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 1481 addTwoAngles(startIndex, end, &angles); 1482 buildAngles(end, &angles, false); 1483 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; 1484 bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind); 1485 if (!sortable) { 1486 *unsortable = true; 1487 #if DEBUG_SORT 1488 debugShowSort(__FUNCTION__, sorted, findStartingEdge(sorted, startIndex, end), 0, 0, 1489 sortable); 1490 #endif 1491 return NULL; 1492 } 1493 int angleCount = angles.count(); 1494 int firstIndex = findStartingEdge(sorted, startIndex, end); 1495 SkASSERT(firstIndex >= 0); 1496 #if DEBUG_SORT 1497 debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0, sortable); 1498 #endif 1499 SkASSERT(sorted[firstIndex]->segment() == this); 1500 int nextIndex = firstIndex + 1; 1501 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 1502 const SkOpAngle* foundAngle = NULL; 1503 bool foundDone = false; 1504 SkOpSegment* nextSegment; 1505 int activeCount = 0; 1506 do { 1507 SkASSERT(nextIndex != firstIndex); 1508 if (nextIndex == angleCount) { 1509 nextIndex = 0; 1510 } 1511 const SkOpAngle* nextAngle = sorted[nextIndex]; 1512 nextSegment = nextAngle->segment(); 1513 ++activeCount; 1514 if (!foundAngle || (foundDone && activeCount & 1)) { 1515 if (nextSegment->isTiny(nextAngle)) { 1516 *unsortable = true; 1517 return NULL; 1518 } 1519 foundAngle = nextAngle; 1520 foundDone = nextSegment->done(nextAngle); 1521 } 1522 if (nextSegment->done()) { 1523 continue; 1524 } 1525 } while (++nextIndex != lastIndex); 1526 markDone(SkMin32(startIndex, endIndex), 1); 1527 if (!foundAngle) { 1528 return NULL; 1529 } 1530 *nextStart = foundAngle->start(); 1531 *nextEnd = foundAngle->end(); 1532 nextSegment = foundAngle->segment(); 1533 #if DEBUG_WINDING 1534 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 1535 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 1536 #endif 1537 return nextSegment; 1538 } 1539 1540 int SkOpSegment::findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end) { 1541 int angleCount = sorted.count(); 1542 int firstIndex = -1; 1543 for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 1544 const SkOpAngle* angle = sorted[angleIndex]; 1545 if (angle->segment() == this && angle->start() == end && 1546 angle->end() == start) { 1547 firstIndex = angleIndex; 1548 break; 1549 } 1550 } 1551 return firstIndex; 1552 } 1553 1554 // FIXME: this is tricky code; needs its own unit test 1555 // note that fOtherIndex isn't computed yet, so it can't be used here 1556 void SkOpSegment::findTooCloseToCall() { 1557 int count = fTs.count(); 1558 if (count < 3) { // require t=0, x, 1 at minimum 1559 return; 1560 } 1561 int matchIndex = 0; 1562 int moCount; 1563 SkOpSpan* match; 1564 SkOpSegment* mOther; 1565 do { 1566 match = &fTs[matchIndex]; 1567 mOther = match->fOther; 1568 // FIXME: allow quads, cubics to be near coincident? 1569 if (mOther->fVerb == SkPath::kLine_Verb) { 1570 moCount = mOther->fTs.count(); 1571 if (moCount >= 3) { 1572 break; 1573 } 1574 } 1575 if (++matchIndex >= count) { 1576 return; 1577 } 1578 } while (true); // require t=0, x, 1 at minimum 1579 // OPTIMIZATION: defer matchPt until qualifying toCount is found? 1580 const SkPoint* matchPt = &xyAtT(match); 1581 // look for a pair of nearby T values that map to the same (x,y) value 1582 // if found, see if the pair of other segments share a common point. If 1583 // so, the span from here to there is coincident. 1584 for (int index = matchIndex + 1; index < count; ++index) { 1585 SkOpSpan* test = &fTs[index]; 1586 if (test->fDone) { 1587 continue; 1588 } 1589 SkOpSegment* tOther = test->fOther; 1590 if (tOther->fVerb != SkPath::kLine_Verb) { 1591 continue; // FIXME: allow quads, cubics to be near coincident? 1592 } 1593 int toCount = tOther->fTs.count(); 1594 if (toCount < 3) { // require t=0, x, 1 at minimum 1595 continue; 1596 } 1597 const SkPoint* testPt = &xyAtT(test); 1598 if (*matchPt != *testPt) { 1599 matchIndex = index; 1600 moCount = toCount; 1601 match = test; 1602 mOther = tOther; 1603 matchPt = testPt; 1604 continue; 1605 } 1606 int moStart = -1; 1607 int moEnd = -1; 1608 double moStartT = 0; 1609 double moEndT = 0; 1610 for (int moIndex = 0; moIndex < moCount; ++moIndex) { 1611 SkOpSpan& moSpan = mOther->fTs[moIndex]; 1612 if (moSpan.fDone) { 1613 continue; 1614 } 1615 if (moSpan.fOther == this) { 1616 if (moSpan.fOtherT == match->fT) { 1617 moStart = moIndex; 1618 moStartT = moSpan.fT; 1619 } 1620 continue; 1621 } 1622 if (moSpan.fOther == tOther) { 1623 if (tOther->windValueAt(moSpan.fOtherT) == 0) { 1624 moStart = -1; 1625 break; 1626 } 1627 SkASSERT(moEnd == -1); 1628 moEnd = moIndex; 1629 moEndT = moSpan.fT; 1630 } 1631 } 1632 if (moStart < 0 || moEnd < 0) { 1633 continue; 1634 } 1635 // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test 1636 if (approximately_equal(moStartT, moEndT)) { 1637 continue; 1638 } 1639 int toStart = -1; 1640 int toEnd = -1; 1641 double toStartT = 0; 1642 double toEndT = 0; 1643 for (int toIndex = 0; toIndex < toCount; ++toIndex) { 1644 SkOpSpan& toSpan = tOther->fTs[toIndex]; 1645 if (toSpan.fDone) { 1646 continue; 1647 } 1648 if (toSpan.fOther == this) { 1649 if (toSpan.fOtherT == test->fT) { 1650 toStart = toIndex; 1651 toStartT = toSpan.fT; 1652 } 1653 continue; 1654 } 1655 if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) { 1656 if (mOther->windValueAt(toSpan.fOtherT) == 0) { 1657 moStart = -1; 1658 break; 1659 } 1660 SkASSERT(toEnd == -1); 1661 toEnd = toIndex; 1662 toEndT = toSpan.fT; 1663 } 1664 } 1665 // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test 1666 if (toStart <= 0 || toEnd <= 0) { 1667 continue; 1668 } 1669 if (approximately_equal(toStartT, toEndT)) { 1670 continue; 1671 } 1672 // test to see if the segment between there and here is linear 1673 if (!mOther->isLinear(moStart, moEnd) 1674 || !tOther->isLinear(toStart, toEnd)) { 1675 continue; 1676 } 1677 bool flipped = (moStart - moEnd) * (toStart - toEnd) < 1; 1678 if (flipped) { 1679 mOther->addTCancel(moStartT, moEndT, tOther, toEndT, toStartT); 1680 } else { 1681 mOther->addTCoincident(moStartT, moEndT, tOther, toStartT, toEndT); 1682 } 1683 } 1684 } 1685 1686 // FIXME: either: 1687 // a) mark spans with either end unsortable as done, or 1688 // b) rewrite findTop / findTopSegment / findTopContour to iterate further 1689 // when encountering an unsortable span 1690 1691 // OPTIMIZATION : for a pair of lines, can we compute points at T (cached) 1692 // and use more concise logic like the old edge walker code? 1693 // FIXME: this needs to deal with coincident edges 1694 SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsortable, 1695 bool onlySortable) { 1696 // iterate through T intersections and return topmost 1697 // topmost tangent from y-min to first pt is closer to horizontal 1698 SkASSERT(!done()); 1699 int firstT = -1; 1700 /* SkPoint topPt = */ activeLeftTop(onlySortable, &firstT); 1701 if (firstT < 0) { 1702 *unsortable = true; 1703 firstT = 0; 1704 while (fTs[firstT].fDone) { 1705 SkASSERT(firstT < fTs.count()); 1706 ++firstT; 1707 } 1708 *tIndexPtr = firstT; 1709 *endIndexPtr = nextExactSpan(firstT, 1); 1710 return this; 1711 } 1712 // sort the edges to find the leftmost 1713 int step = 1; 1714 int end = nextSpan(firstT, step); 1715 if (end == -1) { 1716 step = -1; 1717 end = nextSpan(firstT, step); 1718 SkASSERT(end != -1); 1719 } 1720 // if the topmost T is not on end, or is three-way or more, find left 1721 // look for left-ness from tLeft to firstT (matching y of other) 1722 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; 1723 SkASSERT(firstT - end != 0); 1724 addTwoAngles(end, firstT, &angles); 1725 buildAngles(firstT, &angles, true); 1726 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; 1727 bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMayBeUnordered_SortAngleKind); 1728 int first = SK_MaxS32; 1729 SkScalar top = SK_ScalarMax; 1730 int count = sorted.count(); 1731 for (int index = 0; index < count; ++index) { 1732 const SkOpAngle* angle = sorted[index]; 1733 SkOpSegment* next = angle->segment(); 1734 SkPathOpsBounds bounds; 1735 next->subDivideBounds(angle->end(), angle->start(), &bounds); 1736 if (approximately_greater(top, bounds.fTop)) { 1737 top = bounds.fTop; 1738 first = index; 1739 } 1740 } 1741 SkASSERT(first < SK_MaxS32); 1742 #if DEBUG_SORT // || DEBUG_SWAP_TOP 1743 sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0, sortable); 1744 #endif 1745 if (onlySortable && !sortable) { 1746 *unsortable = true; 1747 return NULL; 1748 } 1749 // skip edges that have already been processed 1750 firstT = first - 1; 1751 SkOpSegment* leftSegment; 1752 do { 1753 if (++firstT == count) { 1754 firstT = 0; 1755 } 1756 const SkOpAngle* angle = sorted[firstT]; 1757 SkASSERT(!onlySortable || !angle->unsortable()); 1758 leftSegment = angle->segment(); 1759 *tIndexPtr = angle->end(); 1760 *endIndexPtr = angle->start(); 1761 } while (leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fDone); 1762 if (leftSegment->verb() >= SkPath::kQuad_Verb) { 1763 const int tIndex = *tIndexPtr; 1764 const int endIndex = *endIndexPtr; 1765 if (!leftSegment->clockwise(tIndex, endIndex)) { 1766 bool swap = !leftSegment->monotonicInY(tIndex, endIndex) 1767 && !leftSegment->serpentine(tIndex, endIndex); 1768 #if DEBUG_SWAP_TOP 1769 SkDebugf("%s swap=%d serpentine=%d containedByEnds=%d monotonic=%d\n", __FUNCTION__, 1770 swap, 1771 leftSegment->serpentine(tIndex, endIndex), 1772 leftSegment->controlsContainedByEnds(tIndex, endIndex), 1773 leftSegment->monotonicInY(tIndex, endIndex)); 1774 #endif 1775 if (swap) { 1776 // FIXME: I doubt it makes sense to (necessarily) swap if the edge was not the first 1777 // sorted but merely the first not already processed (i.e., not done) 1778 SkTSwap(*tIndexPtr, *endIndexPtr); 1779 } 1780 } 1781 } 1782 SkASSERT(!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fTiny); 1783 return leftSegment; 1784 } 1785 1786 // FIXME: not crazy about this 1787 // when the intersections are performed, the other index is into an 1788 // incomplete array. As the array grows, the indices become incorrect 1789 // while the following fixes the indices up again, it isn't smart about 1790 // skipping segments whose indices are already correct 1791 // assuming we leave the code that wrote the index in the first place 1792 void SkOpSegment::fixOtherTIndex() { 1793 int iCount = fTs.count(); 1794 for (int i = 0; i < iCount; ++i) { 1795 SkOpSpan& iSpan = fTs[i]; 1796 double oT = iSpan.fOtherT; 1797 SkOpSegment* other = iSpan.fOther; 1798 int oCount = other->fTs.count(); 1799 SkDEBUGCODE(iSpan.fOtherIndex = -1); 1800 for (int o = 0; o < oCount; ++o) { 1801 SkOpSpan& oSpan = other->fTs[o]; 1802 if (oT == oSpan.fT && this == oSpan.fOther && oSpan.fOtherT == iSpan.fT) { 1803 iSpan.fOtherIndex = o; 1804 oSpan.fOtherIndex = i; 1805 break; 1806 } 1807 } 1808 SkASSERT(iSpan.fOtherIndex >= 0); 1809 } 1810 } 1811 1812 void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) { 1813 fDoneSpans = 0; 1814 fOperand = operand; 1815 fXor = evenOdd; 1816 fPts = pts; 1817 fVerb = verb; 1818 } 1819 1820 void SkOpSegment::initWinding(int start, int end) { 1821 int local = spanSign(start, end); 1822 int oppLocal = oppSign(start, end); 1823 (void) markAndChaseWinding(start, end, local, oppLocal); 1824 // OPTIMIZATION: the reverse mark and chase could skip the first marking 1825 (void) markAndChaseWinding(end, start, local, oppLocal); 1826 } 1827 1828 /* 1829 when we start with a vertical intersect, we try to use the dx to determine if the edge is to 1830 the left or the right of vertical. This determines if we need to add the span's 1831 sign or not. However, this isn't enough. 1832 If the supplied sign (winding) is zero, then we didn't hit another vertical span, so dx is needed. 1833 If there was a winding, then it may or may not need adjusting. If the span the winding was borrowed 1834 from has the same x direction as this span, the winding should change. If the dx is opposite, then 1835 the same winding is shared by both. 1836 */ 1837 void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, 1838 int oppWind, SkScalar hitOppDx) { 1839 SkASSERT(hitDx || !winding); 1840 SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX; 1841 SkASSERT(dx); 1842 int windVal = windValue(SkMin32(start, end)); 1843 #if DEBUG_WINDING_AT_T 1844 SkDebugf("%s oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, winding, 1845 hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal); 1846 #endif 1847 if (!winding) { 1848 winding = dx < 0 ? windVal : -windVal; 1849 } else if (winding * dx < 0) { 1850 int sideWind = winding + (dx < 0 ? windVal : -windVal); 1851 if (abs(winding) < abs(sideWind)) { 1852 winding = sideWind; 1853 } 1854 } 1855 #if DEBUG_WINDING_AT_T 1856 SkDebugf(" winding=%d\n", winding); 1857 #endif 1858 SkDEBUGCODE(int oppLocal = oppSign(start, end)); 1859 SkASSERT(hitOppDx || !oppWind || !oppLocal); 1860 int oppWindVal = oppValue(SkMin32(start, end)); 1861 if (!oppWind) { 1862 oppWind = dx < 0 ? oppWindVal : -oppWindVal; 1863 } else if (hitOppDx * dx >= 0) { 1864 int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal); 1865 if (abs(oppWind) < abs(oppSideWind)) { 1866 oppWind = oppSideWind; 1867 } 1868 } 1869 (void) markAndChaseWinding(start, end, winding, oppWind); 1870 } 1871 1872 bool SkOpSegment::isLinear(int start, int end) const { 1873 if (fVerb == SkPath::kLine_Verb) { 1874 return true; 1875 } 1876 if (fVerb == SkPath::kQuad_Verb) { 1877 SkDQuad qPart = SkDQuad::SubDivide(fPts, fTs[start].fT, fTs[end].fT); 1878 return qPart.isLinear(0, 2); 1879 } else { 1880 SkASSERT(fVerb == SkPath::kCubic_Verb); 1881 SkDCubic cPart = SkDCubic::SubDivide(fPts, fTs[start].fT, fTs[end].fT); 1882 return cPart.isLinear(0, 3); 1883 } 1884 } 1885 1886 // OPTIMIZE: successive calls could start were the last leaves off 1887 // or calls could specialize to walk forwards or backwards 1888 bool SkOpSegment::isMissing(double startT) const { 1889 size_t tCount = fTs.count(); 1890 for (size_t index = 0; index < tCount; ++index) { 1891 if (approximately_zero(startT - fTs[index].fT)) { 1892 return false; 1893 } 1894 } 1895 return true; 1896 } 1897 1898 bool SkOpSegment::isSimple(int end) const { 1899 int count = fTs.count(); 1900 if (count == 2) { 1901 return true; 1902 } 1903 double t = fTs[end].fT; 1904 if (approximately_less_than_zero(t)) { 1905 return !approximately_less_than_zero(fTs[1].fT); 1906 } 1907 if (approximately_greater_than_one(t)) { 1908 return !approximately_greater_than_one(fTs[count - 2].fT); 1909 } 1910 return false; 1911 } 1912 1913 // this span is excluded by the winding rule -- chase the ends 1914 // as long as they are unambiguous to mark connections as done 1915 // and give them the same winding value 1916 SkOpSpan* SkOpSegment::markAndChaseDone(int index, int endIndex, int winding) { 1917 int step = SkSign32(endIndex - index); 1918 int min = SkMin32(index, endIndex); 1919 markDone(min, winding); 1920 SkOpSpan* last; 1921 SkOpSegment* other = this; 1922 while ((other = other->nextChase(&index, step, &min, &last))) { 1923 other->markDone(min, winding); 1924 } 1925 return last; 1926 } 1927 1928 SkOpSpan* SkOpSegment::markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding) { 1929 int index = angle->start(); 1930 int endIndex = angle->end(); 1931 int step = SkSign32(endIndex - index); 1932 int min = SkMin32(index, endIndex); 1933 markDoneBinary(min, winding, oppWinding); 1934 SkOpSpan* last; 1935 SkOpSegment* other = this; 1936 while ((other = other->nextChase(&index, step, &min, &last))) { 1937 other->markDoneBinary(min, winding, oppWinding); 1938 } 1939 return last; 1940 } 1941 1942 SkOpSpan* SkOpSegment::markAndChaseDoneBinary(int index, int endIndex) { 1943 int step = SkSign32(endIndex - index); 1944 int min = SkMin32(index, endIndex); 1945 markDoneBinary(min); 1946 SkOpSpan* last; 1947 SkOpSegment* other = this; 1948 while ((other = other->nextChase(&index, step, &min, &last))) { 1949 if (other->done()) { 1950 return NULL; 1951 } 1952 other->markDoneBinary(min); 1953 } 1954 return last; 1955 } 1956 1957 SkOpSpan* SkOpSegment::markAndChaseDoneUnary(int index, int endIndex) { 1958 int step = SkSign32(endIndex - index); 1959 int min = SkMin32(index, endIndex); 1960 markDoneUnary(min); 1961 SkOpSpan* last; 1962 SkOpSegment* other = this; 1963 while ((other = other->nextChase(&index, step, &min, &last))) { 1964 if (other->done()) { 1965 return NULL; 1966 } 1967 other->markDoneUnary(min); 1968 } 1969 return last; 1970 } 1971 1972 SkOpSpan* SkOpSegment::markAndChaseDoneUnary(const SkOpAngle* angle, int winding) { 1973 int index = angle->start(); 1974 int endIndex = angle->end(); 1975 return markAndChaseDone(index, endIndex, winding); 1976 } 1977 1978 SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, const int winding) { 1979 int index = angle->start(); 1980 int endIndex = angle->end(); 1981 int step = SkSign32(endIndex - index); 1982 int min = SkMin32(index, endIndex); 1983 markWinding(min, winding); 1984 SkOpSpan* last; 1985 SkOpSegment* other = this; 1986 while ((other = other->nextChase(&index, step, &min, &last))) { 1987 if (other->fTs[min].fWindSum != SK_MinS32) { 1988 SkASSERT(other->fTs[min].fWindSum == winding); 1989 return NULL; 1990 } 1991 other->markWinding(min, winding); 1992 } 1993 return last; 1994 } 1995 1996 SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) { 1997 int min = SkMin32(index, endIndex); 1998 int step = SkSign32(endIndex - index); 1999 markWinding(min, winding, oppWinding); 2000 SkOpSpan* last; 2001 SkOpSegment* other = this; 2002 while ((other = other->nextChase(&index, step, &min, &last))) { 2003 if (other->fTs[min].fWindSum != SK_MinS32) { 2004 SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop); 2005 return NULL; 2006 } 2007 other->markWinding(min, winding, oppWinding); 2008 } 2009 return last; 2010 } 2011 2012 SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding) { 2013 int start = angle->start(); 2014 int end = angle->end(); 2015 return markAndChaseWinding(start, end, winding, oppWinding); 2016 } 2017 2018 SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, bool activeAngle, 2019 const SkOpAngle* angle) { 2020 SkASSERT(angle->segment() == this); 2021 if (UseInnerWinding(maxWinding, sumWinding)) { 2022 maxWinding = sumWinding; 2023 } 2024 SkOpSpan* last; 2025 if (activeAngle) { 2026 last = markAndChaseWinding(angle, maxWinding); 2027 } else { 2028 last = markAndChaseDoneUnary(angle, maxWinding); 2029 } 2030 return last; 2031 } 2032 2033 SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding, 2034 int oppSumWinding, bool activeAngle, const SkOpAngle* angle) { 2035 SkASSERT(angle->segment() == this); 2036 if (UseInnerWinding(maxWinding, sumWinding)) { 2037 maxWinding = sumWinding; 2038 } 2039 if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) { 2040 oppMaxWinding = oppSumWinding; 2041 } 2042 SkOpSpan* last; 2043 if (activeAngle) { 2044 last = markAndChaseWinding(angle, maxWinding, oppMaxWinding); 2045 } else { 2046 last = markAndChaseDoneBinary(angle, maxWinding, oppMaxWinding); 2047 } 2048 return last; 2049 } 2050 2051 // FIXME: this should also mark spans with equal (x,y) 2052 // This may be called when the segment is already marked done. While this 2053 // wastes time, it shouldn't do any more than spin through the T spans. 2054 // OPTIMIZATION: abort on first done found (assuming that this code is 2055 // always called to mark segments done). 2056 void SkOpSegment::markDone(int index, int winding) { 2057 // SkASSERT(!done()); 2058 SkASSERT(winding); 2059 double referenceT = fTs[index].fT; 2060 int lesser = index; 2061 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 2062 markOneDone(__FUNCTION__, lesser, winding); 2063 } 2064 do { 2065 markOneDone(__FUNCTION__, index, winding); 2066 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 2067 } 2068 2069 void SkOpSegment::markDoneBinary(int index, int winding, int oppWinding) { 2070 // SkASSERT(!done()); 2071 SkASSERT(winding || oppWinding); 2072 double referenceT = fTs[index].fT; 2073 int lesser = index; 2074 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 2075 markOneDoneBinary(__FUNCTION__, lesser, winding, oppWinding); 2076 } 2077 do { 2078 markOneDoneBinary(__FUNCTION__, index, winding, oppWinding); 2079 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 2080 } 2081 2082 void SkOpSegment::markDoneBinary(int index) { 2083 double referenceT = fTs[index].fT; 2084 int lesser = index; 2085 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 2086 markOneDoneBinary(__FUNCTION__, lesser); 2087 } 2088 do { 2089 markOneDoneBinary(__FUNCTION__, index); 2090 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 2091 } 2092 2093 void SkOpSegment::markDoneUnary(int index) { 2094 double referenceT = fTs[index].fT; 2095 int lesser = index; 2096 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 2097 markOneDoneUnary(__FUNCTION__, lesser); 2098 } 2099 do { 2100 markOneDoneUnary(__FUNCTION__, index); 2101 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 2102 } 2103 2104 void SkOpSegment::markOneDone(const char* funName, int tIndex, int winding) { 2105 SkOpSpan* span = markOneWinding(funName, tIndex, winding); 2106 if (!span) { 2107 return; 2108 } 2109 span->fDone = true; 2110 fDoneSpans++; 2111 } 2112 2113 void SkOpSegment::markOneDoneBinary(const char* funName, int tIndex) { 2114 SkOpSpan* span = verifyOneWinding(funName, tIndex); 2115 if (!span) { 2116 return; 2117 } 2118 span->fDone = true; 2119 fDoneSpans++; 2120 } 2121 2122 void SkOpSegment::markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding) { 2123 SkOpSpan* span = markOneWinding(funName, tIndex, winding, oppWinding); 2124 if (!span) { 2125 return; 2126 } 2127 span->fDone = true; 2128 fDoneSpans++; 2129 } 2130 2131 void SkOpSegment::markOneDoneUnary(const char* funName, int tIndex) { 2132 SkOpSpan* span = verifyOneWindingU(funName, tIndex); 2133 if (!span) { 2134 return; 2135 } 2136 span->fDone = true; 2137 fDoneSpans++; 2138 } 2139 2140 SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding) { 2141 SkOpSpan& span = fTs[tIndex]; 2142 if (span.fDone) { 2143 return NULL; 2144 } 2145 #if DEBUG_MARK_DONE 2146 debugShowNewWinding(funName, span, winding); 2147 #endif 2148 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 2149 #ifdef SK_DEBUG 2150 SkASSERT(abs(winding) <= gDebugMaxWindSum); 2151 #endif 2152 span.fWindSum = winding; 2153 return &span; 2154 } 2155 2156 SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding, 2157 int oppWinding) { 2158 SkOpSpan& span = fTs[tIndex]; 2159 if (span.fDone) { 2160 return NULL; 2161 } 2162 #if DEBUG_MARK_DONE 2163 debugShowNewWinding(funName, span, winding, oppWinding); 2164 #endif 2165 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 2166 #ifdef SK_DEBUG 2167 SkASSERT(abs(winding) <= gDebugMaxWindSum); 2168 #endif 2169 span.fWindSum = winding; 2170 SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding); 2171 #ifdef SK_DEBUG 2172 SkASSERT(abs(oppWinding) <= gDebugMaxWindSum); 2173 #endif 2174 span.fOppSum = oppWinding; 2175 return &span; 2176 } 2177 2178 // from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order 2179 bool SkOpSegment::clockwise(int tStart, int tEnd) const { 2180 SkASSERT(fVerb != SkPath::kLine_Verb); 2181 SkPoint edge[4]; 2182 subDivide(tStart, tEnd, edge); 2183 int points = SkPathOpsVerbToPoints(fVerb); 2184 double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY); 2185 if (fVerb == SkPath::kCubic_Verb) { 2186 SkScalar lesser = SkTMin<SkScalar>(edge[0].fY, edge[3].fY); 2187 if (edge[1].fY < lesser && edge[2].fY < lesser) { 2188 SkDLine tangent1 = {{ {edge[0].fX, edge[0].fY}, {edge[1].fX, edge[1].fY} }}; 2189 SkDLine tangent2 = {{ {edge[2].fX, edge[2].fY}, {edge[3].fX, edge[3].fY} }}; 2190 if (SkIntersections::Test(tangent1, tangent2)) { 2191 SkPoint topPt = cubic_top(fPts, fTs[tStart].fT, fTs[tEnd].fT); 2192 sum += (topPt.fX - edge[0].fX) * (topPt.fY + edge[0].fY); 2193 sum += (edge[3].fX - topPt.fX) * (edge[3].fY + topPt.fY); 2194 return sum <= 0; 2195 } 2196 } 2197 } 2198 for (int idx = 0; idx < points; ++idx){ 2199 sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY); 2200 } 2201 return sum <= 0; 2202 } 2203 2204 bool SkOpSegment::monotonicInY(int tStart, int tEnd) const { 2205 if (fVerb == SkPath::kLine_Verb) { 2206 return false; 2207 } 2208 if (fVerb == SkPath::kQuad_Verb) { 2209 SkDQuad dst = SkDQuad::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT); 2210 return dst.monotonicInY(); 2211 } 2212 SkASSERT(fVerb == SkPath::kCubic_Verb); 2213 SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT); 2214 return dst.monotonicInY(); 2215 } 2216 2217 bool SkOpSegment::serpentine(int tStart, int tEnd) const { 2218 if (fVerb != SkPath::kCubic_Verb) { 2219 return false; 2220 } 2221 SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT); 2222 return dst.serpentine(); 2223 } 2224 2225 SkOpSpan* SkOpSegment::verifyOneWinding(const char* funName, int tIndex) { 2226 SkOpSpan& span = fTs[tIndex]; 2227 if (span.fDone) { 2228 return NULL; 2229 } 2230 #if DEBUG_MARK_DONE 2231 debugShowNewWinding(funName, span, span.fWindSum, span.fOppSum); 2232 #endif 2233 SkASSERT(span.fWindSum != SK_MinS32); 2234 SkASSERT(span.fOppSum != SK_MinS32); 2235 return &span; 2236 } 2237 2238 SkOpSpan* SkOpSegment::verifyOneWindingU(const char* funName, int tIndex) { 2239 SkOpSpan& span = fTs[tIndex]; 2240 if (span.fDone) { 2241 return NULL; 2242 } 2243 #if DEBUG_MARK_DONE 2244 debugShowNewWinding(funName, span, span.fWindSum); 2245 #endif 2246 SkASSERT(span.fWindSum != SK_MinS32); 2247 return &span; 2248 } 2249 2250 // note that just because a span has one end that is unsortable, that's 2251 // not enough to mark it done. The other end may be sortable, allowing the 2252 // span to be added. 2253 // FIXME: if abs(start - end) > 1, mark intermediates as unsortable on both ends 2254 void SkOpSegment::markUnsortable(int start, int end) { 2255 SkOpSpan* span = &fTs[start]; 2256 if (start < end) { 2257 #if DEBUG_UNSORTABLE 2258 debugShowNewWinding(__FUNCTION__, *span, 0); 2259 #endif 2260 span->fUnsortableStart = true; 2261 } else { 2262 --span; 2263 #if DEBUG_UNSORTABLE 2264 debugShowNewWinding(__FUNCTION__, *span, 0); 2265 #endif 2266 span->fUnsortableEnd = true; 2267 } 2268 if (!span->fUnsortableStart || !span->fUnsortableEnd || span->fDone) { 2269 return; 2270 } 2271 span->fDone = true; 2272 fDoneSpans++; 2273 } 2274 2275 void SkOpSegment::markWinding(int index, int winding) { 2276 // SkASSERT(!done()); 2277 SkASSERT(winding); 2278 double referenceT = fTs[index].fT; 2279 int lesser = index; 2280 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 2281 markOneWinding(__FUNCTION__, lesser, winding); 2282 } 2283 do { 2284 markOneWinding(__FUNCTION__, index, winding); 2285 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 2286 } 2287 2288 void SkOpSegment::markWinding(int index, int winding, int oppWinding) { 2289 // SkASSERT(!done()); 2290 SkASSERT(winding || oppWinding); 2291 double referenceT = fTs[index].fT; 2292 int lesser = index; 2293 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 2294 markOneWinding(__FUNCTION__, lesser, winding, oppWinding); 2295 } 2296 do { 2297 markOneWinding(__FUNCTION__, index, winding, oppWinding); 2298 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); 2299 } 2300 2301 void SkOpSegment::matchWindingValue(int tIndex, double t, bool borrowWind) { 2302 int nextDoorWind = SK_MaxS32; 2303 int nextOppWind = SK_MaxS32; 2304 if (tIndex > 0) { 2305 const SkOpSpan& below = fTs[tIndex - 1]; 2306 if (approximately_negative(t - below.fT)) { 2307 nextDoorWind = below.fWindValue; 2308 nextOppWind = below.fOppValue; 2309 } 2310 } 2311 if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) { 2312 const SkOpSpan& above = fTs[tIndex + 1]; 2313 if (approximately_negative(above.fT - t)) { 2314 nextDoorWind = above.fWindValue; 2315 nextOppWind = above.fOppValue; 2316 } 2317 } 2318 if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) { 2319 const SkOpSpan& below = fTs[tIndex - 1]; 2320 nextDoorWind = below.fWindValue; 2321 nextOppWind = below.fOppValue; 2322 } 2323 if (nextDoorWind != SK_MaxS32) { 2324 SkOpSpan& newSpan = fTs[tIndex]; 2325 newSpan.fWindValue = nextDoorWind; 2326 newSpan.fOppValue = nextOppWind; 2327 if (!nextDoorWind && !nextOppWind && !newSpan.fDone) { 2328 newSpan.fDone = true; 2329 ++fDoneSpans; 2330 } 2331 } 2332 } 2333 2334 // return span if when chasing, two or more radiating spans are not done 2335 // OPTIMIZATION: ? multiple spans is detected when there is only one valid 2336 // candidate and the remaining spans have windValue == 0 (canceled by 2337 // coincidence). The coincident edges could either be removed altogether, 2338 // or this code could be more complicated in detecting this case. Worth it? 2339 bool SkOpSegment::multipleSpans(int end) const { 2340 return end > 0 && end < fTs.count() - 1; 2341 } 2342 2343 bool SkOpSegment::nextCandidate(int* start, int* end) const { 2344 while (fTs[*end].fDone) { 2345 if (fTs[*end].fT == 1) { 2346 return false; 2347 } 2348 ++(*end); 2349 } 2350 *start = *end; 2351 *end = nextExactSpan(*start, 1); 2352 return true; 2353 } 2354 2355 SkOpSegment* SkOpSegment::nextChase(int* index, const int step, int* min, SkOpSpan** last) { 2356 int end = nextExactSpan(*index, step); 2357 SkASSERT(end >= 0); 2358 if (multipleSpans(end)) { 2359 *last = &fTs[end]; 2360 return NULL; 2361 } 2362 const SkOpSpan& endSpan = fTs[end]; 2363 SkOpSegment* other = endSpan.fOther; 2364 *index = endSpan.fOtherIndex; 2365 SkASSERT(*index >= 0); 2366 int otherEnd = other->nextExactSpan(*index, step); 2367 SkASSERT(otherEnd >= 0); 2368 *min = SkMin32(*index, otherEnd); 2369 if (other->fTs[*min].fTiny) { 2370 *last = NULL; 2371 return NULL; 2372 } 2373 return other; 2374 } 2375 2376 // This has callers for two different situations: one establishes the end 2377 // of the current span, and one establishes the beginning of the next span 2378 // (thus the name). When this is looking for the end of the current span, 2379 // coincidence is found when the beginning Ts contain -step and the end 2380 // contains step. When it is looking for the beginning of the next, the 2381 // first Ts found can be ignored and the last Ts should contain -step. 2382 // OPTIMIZATION: probably should split into two functions 2383 int SkOpSegment::nextSpan(int from, int step) const { 2384 const SkOpSpan& fromSpan = fTs[from]; 2385 int count = fTs.count(); 2386 int to = from; 2387 while (step > 0 ? ++to < count : --to >= 0) { 2388 const SkOpSpan& span = fTs[to]; 2389 if (approximately_zero(span.fT - fromSpan.fT)) { 2390 continue; 2391 } 2392 return to; 2393 } 2394 return -1; 2395 } 2396 2397 // FIXME 2398 // this returns at any difference in T, vs. a preset minimum. It may be 2399 // that all callers to nextSpan should use this instead. 2400 // OPTIMIZATION splitting this into separate loops for up/down steps 2401 // would allow using precisely_negative instead of precisely_zero 2402 int SkOpSegment::nextExactSpan(int from, int step) const { 2403 const SkOpSpan& fromSpan = fTs[from]; 2404 int count = fTs.count(); 2405 int to = from; 2406 while (step > 0 ? ++to < count : --to >= 0) { 2407 const SkOpSpan& span = fTs[to]; 2408 if (precisely_zero(span.fT - fromSpan.fT)) { 2409 continue; 2410 } 2411 return to; 2412 } 2413 return -1; 2414 } 2415 2416 void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding, 2417 int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) { 2418 int deltaSum = spanSign(index, endIndex); 2419 int oppDeltaSum = oppSign(index, endIndex); 2420 if (operand()) { 2421 *maxWinding = *sumSuWinding; 2422 *sumWinding = *sumSuWinding -= deltaSum; 2423 *oppMaxWinding = *sumMiWinding; 2424 *oppSumWinding = *sumMiWinding -= oppDeltaSum; 2425 } else { 2426 *maxWinding = *sumMiWinding; 2427 *sumWinding = *sumMiWinding -= deltaSum; 2428 *oppMaxWinding = *sumSuWinding; 2429 *oppSumWinding = *sumSuWinding -= oppDeltaSum; 2430 } 2431 } 2432 2433 // This marks all spans unsortable so that this info is available for early 2434 // exclusion in find top and others. This could be optimized to only mark 2435 // adjacent spans that unsortable. However, this makes it difficult to later 2436 // determine starting points for edge detection in find top and the like. 2437 bool SkOpSegment::SortAngles(const SkTArray<SkOpAngle, true>& angles, 2438 SkTArray<SkOpAngle*, true>* angleList, 2439 SortAngleKind orderKind) { 2440 bool sortable = true; 2441 int angleCount = angles.count(); 2442 int angleIndex; 2443 // FIXME: caller needs to use SkTArray constructor with reserve count 2444 // angleList->setReserve(angleCount); 2445 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 2446 const SkOpAngle& angle = angles[angleIndex]; 2447 angleList->push_back(const_cast<SkOpAngle*>(&angle)); 2448 #if DEBUG_ANGLE 2449 (*(angleList->end() - 1))->setID(angleIndex); 2450 #endif 2451 sortable &= !(angle.unsortable() || (orderKind == kMustBeOrdered_SortAngleKind 2452 && angle.unorderable())); 2453 } 2454 if (sortable) { 2455 SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1); 2456 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 2457 if (angles[angleIndex].unsortable() || (orderKind == kMustBeOrdered_SortAngleKind 2458 && angles[angleIndex].unorderable())) { 2459 sortable = false; 2460 break; 2461 } 2462 } 2463 } 2464 if (!sortable) { 2465 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 2466 const SkOpAngle& angle = angles[angleIndex]; 2467 angle.segment()->markUnsortable(angle.start(), angle.end()); 2468 } 2469 } 2470 return sortable; 2471 } 2472 2473 // return true if midpoints were computed 2474 bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const { 2475 SkASSERT(start != end); 2476 edge[0] = fTs[start].fPt; 2477 int points = SkPathOpsVerbToPoints(fVerb); 2478 edge[points] = fTs[end].fPt; 2479 if (fVerb == SkPath::kLine_Verb) { 2480 return false; 2481 } 2482 double startT = fTs[start].fT; 2483 double endT = fTs[end].fT; 2484 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { 2485 // don't compute midpoints if we already have them 2486 if (fVerb == SkPath::kQuad_Verb) { 2487 edge[1] = fPts[1]; 2488 return false; 2489 } 2490 SkASSERT(fVerb == SkPath::kCubic_Verb); 2491 if (start < end) { 2492 edge[1] = fPts[1]; 2493 edge[2] = fPts[2]; 2494 return false; 2495 } 2496 edge[1] = fPts[2]; 2497 edge[2] = fPts[1]; 2498 return false; 2499 } 2500 const SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[points].fX, edge[points].fY }}; 2501 if (fVerb == SkPath::kQuad_Verb) { 2502 edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint(); 2503 } else { 2504 SkASSERT(fVerb == SkPath::kCubic_Verb); 2505 SkDPoint ctrl[2]; 2506 SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl); 2507 edge[1] = ctrl[0].asSkPoint(); 2508 edge[2] = ctrl[1].asSkPoint(); 2509 } 2510 return true; 2511 } 2512 2513 // return true if midpoints were computed 2514 bool SkOpSegment::subDivide(int start, int end, SkDCubic* result) const { 2515 SkASSERT(start != end); 2516 (*result)[0].set(fTs[start].fPt); 2517 int points = SkPathOpsVerbToPoints(fVerb); 2518 (*result)[points].set(fTs[end].fPt); 2519 if (fVerb == SkPath::kLine_Verb) { 2520 return false; 2521 } 2522 double startT = fTs[start].fT; 2523 double endT = fTs[end].fT; 2524 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { 2525 // don't compute midpoints if we already have them 2526 if (fVerb == SkPath::kQuad_Verb) { 2527 (*result)[1].set(fPts[1]); 2528 return false; 2529 } 2530 SkASSERT(fVerb == SkPath::kCubic_Verb); 2531 if (start < end) { 2532 (*result)[1].set(fPts[1]); 2533 (*result)[2].set(fPts[2]); 2534 return false; 2535 } 2536 (*result)[1].set(fPts[2]); 2537 (*result)[2].set(fPts[1]); 2538 return false; 2539 } 2540 if (fVerb == SkPath::kQuad_Verb) { 2541 (*result)[1] = SkDQuad::SubDivide(fPts, (*result)[0], (*result)[2], startT, endT); 2542 } else { 2543 SkASSERT(fVerb == SkPath::kCubic_Verb); 2544 SkDCubic::SubDivide(fPts, (*result)[0], (*result)[3], startT, endT, &(*result)[1]); 2545 } 2546 return true; 2547 } 2548 2549 void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const { 2550 SkPoint edge[4]; 2551 subDivide(start, end, edge); 2552 (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge); 2553 } 2554 2555 bool SkOpSegment::isTiny(const SkOpAngle* angle) const { 2556 int start = angle->start(); 2557 int end = angle->end(); 2558 const SkOpSpan& mSpan = fTs[SkMin32(start, end)]; 2559 return mSpan.fTiny; 2560 } 2561 2562 bool SkOpSegment::isTiny(int index) const { 2563 return fTs[index].fTiny; 2564 } 2565 2566 void SkOpSegment::TrackOutside(SkTArray<double, true>* outsideTs, double end, double start) { 2567 int outCount = outsideTs->count(); 2568 if (outCount == 0 || !approximately_negative(end - (*outsideTs)[outCount - 2])) { 2569 outsideTs->push_back(end); 2570 outsideTs->push_back(start); 2571 } 2572 } 2573 2574 void SkOpSegment::undoneSpan(int* start, int* end) { 2575 size_t tCount = fTs.count(); 2576 size_t index; 2577 for (index = 0; index < tCount; ++index) { 2578 if (!fTs[index].fDone) { 2579 break; 2580 } 2581 } 2582 SkASSERT(index < tCount - 1); 2583 *start = index; 2584 double startT = fTs[index].fT; 2585 while (approximately_negative(fTs[++index].fT - startT)) 2586 SkASSERT(index < tCount); 2587 SkASSERT(index < tCount); 2588 *end = index; 2589 } 2590 2591 int SkOpSegment::updateOppWinding(int index, int endIndex) const { 2592 int lesser = SkMin32(index, endIndex); 2593 int oppWinding = oppSum(lesser); 2594 int oppSpanWinding = oppSign(index, endIndex); 2595 if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding) 2596 && oppWinding != SK_MaxS32) { 2597 oppWinding -= oppSpanWinding; 2598 } 2599 return oppWinding; 2600 } 2601 2602 int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const { 2603 int startIndex = angle->start(); 2604 int endIndex = angle->end(); 2605 return updateOppWinding(endIndex, startIndex); 2606 } 2607 2608 int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const { 2609 int startIndex = angle->start(); 2610 int endIndex = angle->end(); 2611 return updateOppWinding(startIndex, endIndex); 2612 } 2613 2614 int SkOpSegment::updateWinding(int index, int endIndex) const { 2615 int lesser = SkMin32(index, endIndex); 2616 int winding = windSum(lesser); 2617 int spanWinding = spanSign(index, endIndex); 2618 if (winding && UseInnerWinding(winding - spanWinding, winding) && winding != SK_MaxS32) { 2619 winding -= spanWinding; 2620 } 2621 return winding; 2622 } 2623 2624 int SkOpSegment::updateWinding(const SkOpAngle* angle) const { 2625 int startIndex = angle->start(); 2626 int endIndex = angle->end(); 2627 return updateWinding(endIndex, startIndex); 2628 } 2629 2630 int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) const { 2631 int startIndex = angle->start(); 2632 int endIndex = angle->end(); 2633 return updateWinding(startIndex, endIndex); 2634 } 2635 2636 int SkOpSegment::windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const { 2637 if (approximately_zero(tHit - t(tIndex))) { // if we hit the end of a span, disregard 2638 return SK_MinS32; 2639 } 2640 int winding = crossOpp ? oppSum(tIndex) : windSum(tIndex); 2641 SkASSERT(winding != SK_MinS32); 2642 int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex); 2643 #if DEBUG_WINDING_AT_T 2644 SkDebugf("%s oldWinding=%d windValue=%d", __FUNCTION__, winding, windVal); 2645 #endif 2646 // see if a + change in T results in a +/- change in X (compute x'(T)) 2647 *dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX; 2648 if (fVerb > SkPath::kLine_Verb && approximately_zero(*dx)) { 2649 *dx = fPts[2].fX - fPts[1].fX - *dx; 2650 } 2651 if (*dx == 0) { 2652 #if DEBUG_WINDING_AT_T 2653 SkDebugf(" dx=0 winding=SK_MinS32\n"); 2654 #endif 2655 return SK_MinS32; 2656 } 2657 if (windVal < 0) { // reverse sign if opp contour traveled in reverse 2658 *dx = -*dx; 2659 } 2660 if (winding * *dx > 0) { // if same signs, result is negative 2661 winding += *dx > 0 ? -windVal : windVal; 2662 } 2663 #if DEBUG_WINDING_AT_T 2664 SkDebugf(" dx=%c winding=%d\n", *dx > 0 ? '+' : '-', winding); 2665 #endif 2666 return winding; 2667 } 2668 2669 int SkOpSegment::windSum(const SkOpAngle* angle) const { 2670 int start = angle->start(); 2671 int end = angle->end(); 2672 int index = SkMin32(start, end); 2673 return windSum(index); 2674 } 2675 2676 int SkOpSegment::windValue(const SkOpAngle* angle) const { 2677 int start = angle->start(); 2678 int end = angle->end(); 2679 int index = SkMin32(start, end); 2680 return windValue(index); 2681 } 2682 2683 int SkOpSegment::windValueAt(double t) const { 2684 int count = fTs.count(); 2685 for (int index = 0; index < count; ++index) { 2686 if (fTs[index].fT == t) { 2687 return fTs[index].fWindValue; 2688 } 2689 } 2690 SkASSERT(0); 2691 return 0; 2692 } 2693 2694 void SkOpSegment::zeroSpan(SkOpSpan* span) { 2695 SkASSERT(span->fWindValue > 0 || span->fOppValue != 0); 2696 span->fWindValue = 0; 2697 span->fOppValue = 0; 2698 SkASSERT(!span->fDone); 2699 span->fDone = true; 2700 ++fDoneSpans; 2701 } 2702 2703 #if DEBUG_SWAP_TOP 2704 bool SkOpSegment::controlsContainedByEnds(int tStart, int tEnd) const { 2705 if (fVerb != SkPath::kCubic_Verb) { 2706 return false; 2707 } 2708 SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT); 2709 return dst.controlsContainedByEnds(); 2710 } 2711 #endif 2712 2713 #if DEBUG_CONCIDENT 2714 // SkASSERT if pair has not already been added 2715 void SkOpSegment::debugAddTPair(double t, const SkOpSegment& other, double otherT) const { 2716 for (int i = 0; i < fTs.count(); ++i) { 2717 if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) { 2718 return; 2719 } 2720 } 2721 SkASSERT(0); 2722 } 2723 #endif 2724 2725 #if DEBUG_CONCIDENT 2726 void SkOpSegment::debugShowTs() const { 2727 SkDebugf("%s id=%d", __FUNCTION__, fID); 2728 int lastWind = -1; 2729 int lastOpp = -1; 2730 double lastT = -1; 2731 int i; 2732 for (i = 0; i < fTs.count(); ++i) { 2733 bool change = lastT != fTs[i].fT || lastWind != fTs[i].fWindValue 2734 || lastOpp != fTs[i].fOppValue; 2735 if (change && lastWind >= 0) { 2736 SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]", 2737 lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp); 2738 } 2739 if (change) { 2740 SkDebugf(" [o=%d", fTs[i].fOther->fID); 2741 lastWind = fTs[i].fWindValue; 2742 lastOpp = fTs[i].fOppValue; 2743 lastT = fTs[i].fT; 2744 } else { 2745 SkDebugf(",%d", fTs[i].fOther->fID); 2746 } 2747 } 2748 if (i <= 0) { 2749 return; 2750 } 2751 SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]", 2752 lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp); 2753 if (fOperand) { 2754 SkDebugf(" operand"); 2755 } 2756 if (done()) { 2757 SkDebugf(" done"); 2758 } 2759 SkDebugf("\n"); 2760 } 2761 #endif 2762 2763 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY 2764 void SkOpSegment::debugShowActiveSpans() const { 2765 debugValidate(); 2766 if (done()) { 2767 return; 2768 } 2769 #if DEBUG_ACTIVE_SPANS_SHORT_FORM 2770 int lastId = -1; 2771 double lastT = -1; 2772 #endif 2773 for (int i = 0; i < fTs.count(); ++i) { 2774 if (fTs[i].fDone) { 2775 continue; 2776 } 2777 SkASSERT(i < fTs.count() - 1); 2778 #if DEBUG_ACTIVE_SPANS_SHORT_FORM 2779 if (lastId == fID && lastT == fTs[i].fT) { 2780 continue; 2781 } 2782 lastId = fID; 2783 lastT = fTs[i].fT; 2784 #endif 2785 SkDebugf("%s id=%d", __FUNCTION__, fID); 2786 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 2787 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { 2788 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 2789 } 2790 const SkOpSpan* span = &fTs[i]; 2791 SkDebugf(") t=%1.9g (%1.9g,%1.9g)", span->fT, xAtT(span), yAtT(span)); 2792 int iEnd = i + 1; 2793 while (fTs[iEnd].fT < 1 && approximately_equal(fTs[i].fT, fTs[iEnd].fT)) { 2794 ++iEnd; 2795 } 2796 SkDebugf(" tEnd=%1.9g", fTs[iEnd].fT); 2797 const SkOpSegment* other = fTs[i].fOther; 2798 SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=", 2799 other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex); 2800 if (fTs[i].fWindSum == SK_MinS32) { 2801 SkDebugf("?"); 2802 } else { 2803 SkDebugf("%d", fTs[i].fWindSum); 2804 } 2805 SkDebugf(" windValue=%d oppValue=%d\n", fTs[i].fWindValue, fTs[i].fOppValue); 2806 } 2807 } 2808 #endif 2809 2810 2811 #if DEBUG_MARK_DONE || DEBUG_UNSORTABLE 2812 void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding) { 2813 const SkPoint& pt = xyAtT(&span); 2814 SkDebugf("%s id=%d", fun, fID); 2815 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 2816 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { 2817 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 2818 } 2819 SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther-> 2820 fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]); 2821 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d windSum=", 2822 span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY, 2823 (&span)[1].fT, winding); 2824 if (span.fWindSum == SK_MinS32) { 2825 SkDebugf("?"); 2826 } else { 2827 SkDebugf("%d", span.fWindSum); 2828 } 2829 SkDebugf(" windValue=%d\n", span.fWindValue); 2830 } 2831 2832 void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, 2833 int oppWinding) { 2834 const SkPoint& pt = xyAtT(&span); 2835 SkDebugf("%s id=%d", fun, fID); 2836 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 2837 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { 2838 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 2839 } 2840 SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther-> 2841 fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]); 2842 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d newOppSum=%d oppSum=", 2843 span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY, 2844 (&span)[1].fT, winding, oppWinding); 2845 if (span.fOppSum == SK_MinS32) { 2846 SkDebugf("?"); 2847 } else { 2848 SkDebugf("%d", span.fOppSum); 2849 } 2850 SkDebugf(" windSum="); 2851 if (span.fWindSum == SK_MinS32) { 2852 SkDebugf("?"); 2853 } else { 2854 SkDebugf("%d", span.fWindSum); 2855 } 2856 SkDebugf(" windValue=%d\n", span.fWindValue); 2857 } 2858 #endif 2859 2860 #if DEBUG_SORT || DEBUG_SWAP_TOP 2861 void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, 2862 int first, const int contourWinding, 2863 const int oppContourWinding, bool sortable) const { 2864 if (--gDebugSortCount < 0) { 2865 return; 2866 } 2867 SkASSERT(angles[first]->segment() == this); 2868 SkASSERT(!sortable || angles.count() > 1); 2869 int lastSum = contourWinding; 2870 int oppLastSum = oppContourWinding; 2871 const SkOpAngle* firstAngle = angles[first]; 2872 int windSum = lastSum - spanSign(firstAngle); 2873 int oppoSign = oppSign(firstAngle); 2874 int oppWindSum = oppLastSum - oppoSign; 2875 #define WIND_AS_STRING(x) char x##Str[12]; if (!valid_wind(x)) strcpy(x##Str, "?"); \ 2876 else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x) 2877 WIND_AS_STRING(contourWinding); 2878 WIND_AS_STRING(oppContourWinding); 2879 SkDebugf("%s %s contourWinding=%s oppContourWinding=%s sign=%d\n", fun, __FUNCTION__, 2880 contourWindingStr, oppContourWindingStr, spanSign(angles[first])); 2881 int index = first; 2882 bool firstTime = true; 2883 do { 2884 const SkOpAngle& angle = *angles[index]; 2885 const SkOpSegment& segment = *angle.segment(); 2886 int start = angle.start(); 2887 int end = angle.end(); 2888 const SkOpSpan& sSpan = segment.fTs[start]; 2889 const SkOpSpan& eSpan = segment.fTs[end]; 2890 const SkOpSpan& mSpan = segment.fTs[SkMin32(start, end)]; 2891 bool opp = segment.fOperand ^ fOperand; 2892 if (!firstTime) { 2893 oppoSign = segment.oppSign(&angle); 2894 if (opp) { 2895 oppLastSum = oppWindSum; 2896 oppWindSum -= segment.spanSign(&angle); 2897 if (oppoSign) { 2898 lastSum = windSum; 2899 windSum -= oppoSign; 2900 } 2901 } else { 2902 lastSum = windSum; 2903 windSum -= segment.spanSign(&angle); 2904 if (oppoSign) { 2905 oppLastSum = oppWindSum; 2906 oppWindSum -= oppoSign; 2907 } 2908 } 2909 } 2910 SkDebugf("%s [%d] %s", __FUNCTION__, index, 2911 angle.unsortable() ? "*** UNSORTABLE *** " : ""); 2912 #if DEBUG_SORT_COMPACT 2913 SkDebugf("id=%d %s start=%d (%1.9g,%1.9g) end=%d (%1.9g,%1.9g)", 2914 segment.fID, kLVerbStr[SkPathOpsVerbToPoints(segment.fVerb)], 2915 start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end, 2916 segment.xAtT(&eSpan), segment.yAtT(&eSpan)); 2917 #else 2918 switch (segment.fVerb) { 2919 case SkPath::kLine_Verb: 2920 SkDebugf(LINE_DEBUG_STR, LINE_DEBUG_DATA(segment.fPts)); 2921 break; 2922 case SkPath::kQuad_Verb: 2923 SkDebugf(QUAD_DEBUG_STR, QUAD_DEBUG_DATA(segment.fPts)); 2924 break; 2925 case SkPath::kCubic_Verb: 2926 SkDebugf(CUBIC_DEBUG_STR, CUBIC_DEBUG_DATA(segment.fPts)); 2927 break; 2928 default: 2929 SkASSERT(0); 2930 } 2931 SkDebugf(" tStart=%1.9g tEnd=%1.9g", sSpan.fT, eSpan.fT); 2932 #endif 2933 SkDebugf(" sign=%d windValue=%d windSum=", angle.sign(), mSpan.fWindValue); 2934 winding_printf(mSpan.fWindSum); 2935 int last, wind; 2936 if (opp) { 2937 last = oppLastSum; 2938 wind = oppWindSum; 2939 } else { 2940 last = lastSum; 2941 wind = windSum; 2942 } 2943 bool useInner = valid_wind(last) && valid_wind(wind) && UseInnerWinding(last, wind); 2944 WIND_AS_STRING(last); 2945 WIND_AS_STRING(wind); 2946 WIND_AS_STRING(lastSum); 2947 WIND_AS_STRING(oppLastSum); 2948 WIND_AS_STRING(windSum); 2949 WIND_AS_STRING(oppWindSum); 2950 #undef WIND_AS_STRING 2951 if (!oppoSign) { 2952 SkDebugf(" %s->%s (max=%s)", lastStr, windStr, useInner ? windStr : lastStr); 2953 } else { 2954 SkDebugf(" %s->%s (%s->%s)", lastStr, windStr, opp ? lastSumStr : oppLastSumStr, 2955 opp ? windSumStr : oppWindSumStr); 2956 } 2957 SkDebugf(" done=%d tiny=%d opp=%d\n", mSpan.fDone, mSpan.fTiny, opp); 2958 #if 0 && DEBUG_ANGLE 2959 angle.debugShow(segment.xyAtT(&sSpan)); 2960 #endif 2961 ++index; 2962 if (index == angles.count()) { 2963 index = 0; 2964 } 2965 if (firstTime) { 2966 firstTime = false; 2967 } 2968 } while (index != first); 2969 } 2970 2971 void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, 2972 int first, bool sortable) { 2973 const SkOpAngle* firstAngle = angles[first]; 2974 const SkOpSegment* segment = firstAngle->segment(); 2975 int winding = segment->updateWinding(firstAngle); 2976 int oppWinding = segment->updateOppWinding(firstAngle); 2977 debugShowSort(fun, angles, first, winding, oppWinding, sortable); 2978 } 2979 2980 #endif 2981 2982 #if DEBUG_SHOW_WINDING 2983 int SkOpSegment::debugShowWindingValues(int slotCount, int ofInterest) const { 2984 if (!(1 << fID & ofInterest)) { 2985 return 0; 2986 } 2987 int sum = 0; 2988 SkTArray<char, true> slots(slotCount * 2); 2989 memset(slots.begin(), ' ', slotCount * 2); 2990 for (int i = 0; i < fTs.count(); ++i) { 2991 // if (!(1 << fTs[i].fOther->fID & ofInterest)) { 2992 // continue; 2993 // } 2994 sum += fTs[i].fWindValue; 2995 slots[fTs[i].fOther->fID - 1] = as_digit(fTs[i].fWindValue); 2996 sum += fTs[i].fOppValue; 2997 slots[slotCount + fTs[i].fOther->fID - 1] = as_digit(fTs[i].fOppValue); 2998 } 2999 SkDebugf("%s id=%2d %.*s | %.*s\n", __FUNCTION__, fID, slotCount, slots.begin(), slotCount, 3000 slots.begin() + slotCount); 3001 return sum; 3002 } 3003 #endif 3004 3005 void SkOpSegment::debugValidate() const { 3006 #if DEBUG_VALIDATE 3007 int count = fTs.count(); 3008 SkASSERT(count >= 2); 3009 SkASSERT(fTs[0].fT == 0); 3010 SkASSERT(fTs[count - 1].fT == 1); 3011 int done = 0; 3012 double t = -1; 3013 for (int i = 0; i < count; ++i) { 3014 const SkOpSpan& span = fTs[i]; 3015 SkASSERT(t <= span.fT); 3016 t = span.fT; 3017 int otherIndex = span.fOtherIndex; 3018 const SkOpSegment* other = span.fOther; 3019 const SkOpSpan& otherSpan = other->fTs[otherIndex]; 3020 SkASSERT(otherSpan.fPt == span.fPt); 3021 SkASSERT(otherSpan.fOtherT == t); 3022 SkASSERT(&fTs[i] == &otherSpan.fOther->fTs[otherSpan.fOtherIndex]); 3023 done += span.fDone; 3024 } 3025 SkASSERT(done == fDoneSpans); 3026 #endif 3027 } 3028