OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 #include "SkAddIntersections.h" | 7 #include "SkAddIntersections.h" |
8 #include "SkOpEdgeBuilder.h" | 8 #include "SkOpEdgeBuilder.h" |
9 #include "SkPathOpsCommon.h" | 9 #include "SkPathOpsCommon.h" |
10 #include "SkPathWriter.h" | 10 #include "SkPathWriter.h" |
(...skipping 143 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
154 *chase->append() = span; | 154 *chase->append() = span; |
155 #endif | 155 #endif |
156 return last->segment(); | 156 return last->segment(); |
157 } | 157 } |
158 if (done) { | 158 if (done) { |
159 continue; | 159 continue; |
160 } | 160 } |
161 if (!sortable) { | 161 if (!sortable) { |
162 continue; | 162 continue; |
163 } | 163 } |
164 // find first angle, initialize winding to computed fWindSum | 164 // find first angle, initialize winding to computed wind sum |
165 const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex); | 165 const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex); |
166 const SkOpAngle* firstAngle; | 166 const SkOpAngle* firstAngle; |
167 SkDEBUGCODE(firstAngle = angle); | 167 SkDEBUGCODE(firstAngle = angle); |
168 SkDEBUGCODE(bool loop = false); | 168 SkDEBUGCODE(bool loop = false); |
169 int winding; | 169 int winding; |
170 do { | 170 do { |
171 angle = angle->next(); | 171 angle = angle->next(); |
172 SkASSERT(angle != firstAngle || !loop); | 172 SkASSERT(angle != firstAngle || !loop); |
173 SkDEBUGCODE(loop |= angle == firstAngle); | 173 SkDEBUGCODE(loop |= angle == firstAngle); |
174 segment = angle->segment(); | 174 segment = angle->segment(); |
(...skipping 26 matching lines...) Expand all Loading... |
201 *endIndex = angle->end(); | 201 *endIndex = angle->end(); |
202 int lesser = SkMin32(*tIndex, *endIndex); | 202 int lesser = SkMin32(*tIndex, *endIndex); |
203 const SkOpSpan& nextSpan = segment->span(lesser); | 203 const SkOpSpan& nextSpan = segment->span(lesser); |
204 if (!nextSpan.fDone) { | 204 if (!nextSpan.fDone) { |
205 // FIXME: this be wrong? assign startWinding if edge is in | 205 // FIXME: this be wrong? assign startWinding if edge is in |
206 // same direction. If the direction is opposite, winding to | 206 // same direction. If the direction is opposite, winding to |
207 // assign is flipped sign or +/- 1? | 207 // assign is flipped sign or +/- 1? |
208 if (SkOpSegment::UseInnerWinding(maxWinding, winding)) { | 208 if (SkOpSegment::UseInnerWinding(maxWinding, winding)) { |
209 maxWinding = winding; | 209 maxWinding = winding; |
210 } | 210 } |
211 (void) segment->markAndChaseWinding(angle, maxWinding, 0); | 211 // allowed to do nothing |
| 212 (void) segment->markAndChaseWinding(angle, maxWinding, 0, NULL); |
212 break; | 213 break; |
213 } | 214 } |
214 } | 215 } |
215 *chase->insert(0) = span; | 216 *chase->insert(0) = span; |
216 return segment; | 217 return segment; |
217 } | 218 } |
218 return NULL; | 219 return NULL; |
219 } | 220 } |
220 | 221 |
221 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY | 222 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY |
(...skipping 86 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
308 } | 309 } |
309 SkOpSegment* nonVertical = contour->nonVerticalSegment(index, endIndex); | 310 SkOpSegment* nonVertical = contour->nonVerticalSegment(index, endIndex); |
310 if (nonVertical) { | 311 if (nonVertical) { |
311 *current = nonVertical; | 312 *current = nonVertical; |
312 return; | 313 return; |
313 } | 314 } |
314 } | 315 } |
315 return; | 316 return; |
316 } | 317 } |
317 | 318 |
| 319 struct SortableTop { // error if local in pre-C++11 |
| 320 SkOpSegment* fSegment; |
| 321 int fIndex; |
| 322 int fEndIndex; |
| 323 }; |
| 324 |
318 SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, | 325 SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, |
319 SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexP
tr, | 326 SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexP
tr, |
320 int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool*
onlyVertical, | 327 int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool*
onlyVertical, |
321 bool firstPass) { | 328 bool firstPass) { |
322 SkOpSegment* current = findTopSegment(contourList, indexPtr, endIndexPtr, to
pLeft, unsortable, | 329 SkOpSegment* current = findTopSegment(contourList, indexPtr, endIndexPtr, to
pLeft, unsortable, |
323 done, firstPass); | 330 done, firstPass); |
324 if (!current) { | 331 if (!current) { |
325 return NULL; | 332 return NULL; |
326 } | 333 } |
327 const int startIndex = *indexPtr; | 334 const int startIndex = *indexPtr; |
(...skipping 21 matching lines...) Expand all Loading... |
349 return current; | 356 return current; |
350 } | 357 } |
351 int contourWinding; | 358 int contourWinding; |
352 int oppContourWinding = 0; | 359 int oppContourWinding = 0; |
353 // the simple upward projection of the unresolved points hit unsortable angl
es | 360 // the simple upward projection of the unresolved points hit unsortable angl
es |
354 // shoot rays at right angles to the segment to find its winding, ignoring a
ngle cases | 361 // shoot rays at right angles to the segment to find its winding, ignoring a
ngle cases |
355 bool tryAgain; | 362 bool tryAgain; |
356 double tHit; | 363 double tHit; |
357 SkScalar hitDx = 0; | 364 SkScalar hitDx = 0; |
358 SkScalar hitOppDx = 0; | 365 SkScalar hitOppDx = 0; |
| 366 // keep track of subsequent returns to detect infinite loops |
| 367 SkTDArray<SortableTop> sortableTops; |
359 do { | 368 do { |
360 // if current is vertical, find another candidate which is not | 369 // if current is vertical, find another candidate which is not |
361 // if only remaining candidates are vertical, then they can be marked do
ne | 370 // if only remaining candidates are vertical, then they can be marked do
ne |
362 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >=
0); | 371 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >=
0); |
363 skipVertical(contourList, ¤t, indexPtr, endIndexPtr); | 372 skipVertical(contourList, ¤t, indexPtr, endIndexPtr); |
364 SkASSERT(current); // FIXME: if null, all remaining are vertical | 373 SkASSERT(current); // FIXME: if null, all remaining are vertical |
365 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >=
0); | 374 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >=
0); |
366 tryAgain = false; | 375 tryAgain = false; |
367 contourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endI
ndexPtr, &tHit, | 376 contourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endI
ndexPtr, &tHit, |
368 &hitDx, &tryAgain, onlyVertical, false); | 377 &hitDx, &tryAgain, onlyVertical, false); |
| 378 if (tryAgain) { |
| 379 bool giveUp = false; |
| 380 int count = sortableTops.count(); |
| 381 for (int index = 0; index < count; ++index) { |
| 382 const SortableTop& prev = sortableTops[index]; |
| 383 if (giveUp) { |
| 384 prev.fSegment->markDoneFinal(prev.fIndex); |
| 385 } else if (prev.fSegment == current |
| 386 && (prev.fIndex == *indexPtr || prev.fEndIndex == *endIn
dexPtr)) { |
| 387 // remaining edges are non-vertical and cannot have their wi
nding computed |
| 388 // mark them as done and return, and hope that assembly can
fill the holes |
| 389 giveUp = true; |
| 390 index = -1; |
| 391 } |
| 392 } |
| 393 if (giveUp) { |
| 394 *done = true; |
| 395 return NULL; |
| 396 } |
| 397 } |
| 398 SortableTop* sortableTop = sortableTops.append(); |
| 399 sortableTop->fSegment = current; |
| 400 sortableTop->fIndex = *indexPtr; |
| 401 sortableTop->fEndIndex = *endIndexPtr; |
| 402 #if DEBUG_SORT |
| 403 SkDebugf("%s current=%d index=%d endIndex=%d tHit=%1.9g hitDx=%1.9g try=
%d vert=%d\n", |
| 404 __FUNCTION__, current->debugID(), *indexPtr, *endIndexPtr, tHit,
hitDx, tryAgain, |
| 405 *onlyVertical); |
| 406 #endif |
369 if (*onlyVertical) { | 407 if (*onlyVertical) { |
370 return current; | 408 return current; |
371 } | 409 } |
372 if (tryAgain) { | 410 if (tryAgain) { |
373 continue; | 411 continue; |
374 } | 412 } |
375 if (angleIncludeType < SkOpAngle::kBinarySingle) { | 413 if (angleIncludeType < SkOpAngle::kBinarySingle) { |
376 break; | 414 break; |
377 } | 415 } |
378 oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, e
ndIndexPtr, &tHit, | 416 oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, e
ndIndexPtr, &tHit, |
379 &hitOppDx, &tryAgain, NULL, true); | 417 &hitOppDx, &tryAgain, NULL, true); |
380 } while (tryAgain); | 418 } while (tryAgain); |
381 current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, o
ppContourWinding, | 419 bool success = current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWi
nding, hitDx, |
382 hitOppDx); | 420 oppContourWinding, hitOppDx); |
383 if (current->done()) { | 421 if (current->done()) { |
384 return NULL; | 422 return NULL; |
| 423 } else if (!success) { // check if the span has a valid winding |
| 424 int min = SkTMin(*indexPtr, *endIndexPtr); |
| 425 const SkOpSpan& span = current->span(min); |
| 426 if (span.fWindSum == SK_MinS32) { |
| 427 return NULL; |
| 428 } |
385 } | 429 } |
386 return current; | 430 return current; |
387 } | 431 } |
388 | 432 |
389 static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) { | 433 static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) { |
390 int contourCount = (*contourList).count(); | 434 int contourCount = (*contourList).count(); |
391 for (int cTest = 0; cTest < contourCount; ++cTest) { | 435 for (int cTest = 0; cTest < contourCount; ++cTest) { |
392 SkOpContour* contour = (*contourList)[cTest]; | 436 SkOpContour* contour = (*contourList)[cTest]; |
393 if (!contour->calcAngles()) { | 437 if (!contour->calcAngles()) { |
394 return false; | 438 return false; |
395 } | 439 } |
396 } | 440 } |
397 return true; | 441 return true; |
398 } | 442 } |
399 | 443 |
400 static void checkDuplicates(SkTArray<SkOpContour*, true>* contourList) { | 444 static void checkDuplicates(SkTArray<SkOpContour*, true>* contourList) { |
401 int contourCount = (*contourList).count(); | 445 int contourCount = (*contourList).count(); |
402 for (int cTest = 0; cTest < contourCount; ++cTest) { | 446 for (int cTest = 0; cTest < contourCount; ++cTest) { |
403 SkOpContour* contour = (*contourList)[cTest]; | 447 SkOpContour* contour = (*contourList)[cTest]; |
404 contour->checkDuplicates(); | 448 contour->checkDuplicates(); |
405 } | 449 } |
406 } | 450 } |
407 | 451 |
408 static void checkEnds(SkTArray<SkOpContour*, true>* contourList) { | 452 static bool checkEnds(SkTArray<SkOpContour*, true>* contourList) { |
409 // it's hard to determine if the end of a cubic or conic nearly intersects a
nother curve. | 453 // it's hard to determine if the end of a cubic or conic nearly intersects a
nother curve. |
410 // instead, look to see if the connecting curve intersected at that same end
. | 454 // instead, look to see if the connecting curve intersected at that same end
. |
411 int contourCount = (*contourList).count(); | 455 int contourCount = (*contourList).count(); |
412 for (int cTest = 0; cTest < contourCount; ++cTest) { | 456 for (int cTest = 0; cTest < contourCount; ++cTest) { |
413 SkOpContour* contour = (*contourList)[cTest]; | 457 SkOpContour* contour = (*contourList)[cTest]; |
414 contour->checkEnds(); | 458 if (!contour->checkEnds()) { |
| 459 return false; |
| 460 } |
415 } | 461 } |
| 462 return true; |
416 } | 463 } |
417 | 464 |
418 static bool checkMultiples(SkTArray<SkOpContour*, true>* contourList) { | 465 static bool checkMultiples(SkTArray<SkOpContour*, true>* contourList) { |
419 bool hasMultiples = false; | 466 bool hasMultiples = false; |
420 int contourCount = (*contourList).count(); | 467 int contourCount = (*contourList).count(); |
421 for (int cTest = 0; cTest < contourCount; ++cTest) { | 468 for (int cTest = 0; cTest < contourCount; ++cTest) { |
422 SkOpContour* contour = (*contourList)[cTest]; | 469 SkOpContour* contour = (*contourList)[cTest]; |
423 contour->checkMultiples(); | 470 contour->checkMultiples(); |
424 hasMultiples |= contour->hasMultiples(); | 471 hasMultiples |= contour->hasMultiples(); |
425 } | 472 } |
(...skipping 273 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
699 #if DEBUG_SHOW_WINDING | 746 #if DEBUG_SHOW_WINDING |
700 SkOpContour::debugShowWindingValues(contourList); | 747 SkOpContour::debugShowWindingValues(contourList); |
701 #endif | 748 #endif |
702 if (!CoincidenceCheck(contourList, total)) { | 749 if (!CoincidenceCheck(contourList, total)) { |
703 return false; | 750 return false; |
704 } | 751 } |
705 #if DEBUG_SHOW_WINDING | 752 #if DEBUG_SHOW_WINDING |
706 SkOpContour::debugShowWindingValues(contourList); | 753 SkOpContour::debugShowWindingValues(contourList); |
707 #endif | 754 #endif |
708 fixOtherTIndex(contourList); | 755 fixOtherTIndex(contourList); |
709 checkEnds(contourList); // check if connecting curve intersected at the sam
e end | 756 if (!checkEnds(contourList)) { // check if connecting curve intersected at
the same end |
| 757 return false; |
| 758 } |
710 bool hasM = checkMultiples(contourList); // check if intersections agree on
t and point values | 759 bool hasM = checkMultiples(contourList); // check if intersections agree on
t and point values |
711 SkTDArray<SkOpSegment::AlignedSpan> aligned; | 760 SkTDArray<SkOpSegment::AlignedSpan> aligned; |
712 if (hasM) { | 761 if (hasM) { |
713 alignMultiples(contourList, &aligned); // align pairs of identical poin
ts | 762 alignMultiples(contourList, &aligned); // align pairs of identical poin
ts |
714 alignCoincidence(contourList, aligned); | 763 alignCoincidence(contourList, aligned); |
715 } | 764 } |
716 checkDuplicates(contourList); // check if spans have the same number on the
other end | 765 checkDuplicates(contourList); // check if spans have the same number on the
other end |
717 checkTiny(contourList); // if pair have the same end points, mark them as p
arallel | 766 checkTiny(contourList); // if pair have the same end points, mark them as p
arallel |
718 checkSmall(contourList); // a pair of curves with a small span may turn int
o coincident lines | 767 checkSmall(contourList); // a pair of curves with a small span may turn int
o coincident lines |
719 joinCoincidence(contourList); // join curves that connect to a coincident p
air | 768 joinCoincidence(contourList); // join curves that connect to a coincident p
air |
720 sortSegments(contourList); | 769 sortSegments(contourList); |
721 if (!calcAngles(contourList)) { | 770 if (!calcAngles(contourList)) { |
722 return false; | 771 return false; |
723 } | 772 } |
724 sortAngles(contourList); | 773 sortAngles(contourList); |
725 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY | 774 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY |
726 DebugShowActiveSpans(*contourList); | 775 DebugShowActiveSpans(*contourList); |
727 #endif | 776 #endif |
728 return true; | 777 return true; |
729 } | 778 } |
OLD | NEW |