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 wind sum | 164 // find first angle, initialize winding to computed fWindSum |
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 // allowed to do nothing | 211 (void) segment->markAndChaseWinding(angle, maxWinding, 0); |
212 (void) segment->markAndChaseWinding(angle, maxWinding, 0, NULL); | |
213 break; | 212 break; |
214 } | 213 } |
215 } | 214 } |
216 *chase->insert(0) = span; | 215 *chase->insert(0) = span; |
217 return segment; | 216 return segment; |
218 } | 217 } |
219 return NULL; | 218 return NULL; |
220 } | 219 } |
221 | 220 |
222 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY | 221 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY |
(...skipping 86 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
309 } | 308 } |
310 SkOpSegment* nonVertical = contour->nonVerticalSegment(index, endIndex); | 309 SkOpSegment* nonVertical = contour->nonVerticalSegment(index, endIndex); |
311 if (nonVertical) { | 310 if (nonVertical) { |
312 *current = nonVertical; | 311 *current = nonVertical; |
313 return; | 312 return; |
314 } | 313 } |
315 } | 314 } |
316 return; | 315 return; |
317 } | 316 } |
318 | 317 |
319 struct SortableTop { // error if local in pre-C++11 | |
320 SkOpSegment* fSegment; | |
321 int fIndex; | |
322 int fEndIndex; | |
323 }; | |
324 | |
325 SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, | 318 SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, |
326 SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexP
tr, | 319 SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexP
tr, |
327 int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool*
onlyVertical, | 320 int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool*
onlyVertical, |
328 bool firstPass) { | 321 bool firstPass) { |
329 SkOpSegment* current = findTopSegment(contourList, indexPtr, endIndexPtr, to
pLeft, unsortable, | 322 SkOpSegment* current = findTopSegment(contourList, indexPtr, endIndexPtr, to
pLeft, unsortable, |
330 done, firstPass); | 323 done, firstPass); |
331 if (!current) { | 324 if (!current) { |
332 return NULL; | 325 return NULL; |
333 } | 326 } |
334 const int startIndex = *indexPtr; | 327 const int startIndex = *indexPtr; |
(...skipping 21 matching lines...) Expand all Loading... |
356 return current; | 349 return current; |
357 } | 350 } |
358 int contourWinding; | 351 int contourWinding; |
359 int oppContourWinding = 0; | 352 int oppContourWinding = 0; |
360 // the simple upward projection of the unresolved points hit unsortable angl
es | 353 // the simple upward projection of the unresolved points hit unsortable angl
es |
361 // shoot rays at right angles to the segment to find its winding, ignoring a
ngle cases | 354 // shoot rays at right angles to the segment to find its winding, ignoring a
ngle cases |
362 bool tryAgain; | 355 bool tryAgain; |
363 double tHit; | 356 double tHit; |
364 SkScalar hitDx = 0; | 357 SkScalar hitDx = 0; |
365 SkScalar hitOppDx = 0; | 358 SkScalar hitOppDx = 0; |
366 // keep track of subsequent returns to detect infinite loops | |
367 SkTDArray<SortableTop> sortableTops; | |
368 do { | 359 do { |
369 // if current is vertical, find another candidate which is not | 360 // if current is vertical, find another candidate which is not |
370 // if only remaining candidates are vertical, then they can be marked do
ne | 361 // if only remaining candidates are vertical, then they can be marked do
ne |
371 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >=
0); | 362 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >=
0); |
372 skipVertical(contourList, ¤t, indexPtr, endIndexPtr); | 363 skipVertical(contourList, ¤t, indexPtr, endIndexPtr); |
373 SkASSERT(current); // FIXME: if null, all remaining are vertical | 364 SkASSERT(current); // FIXME: if null, all remaining are vertical |
374 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >=
0); | 365 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >=
0); |
375 tryAgain = false; | 366 tryAgain = false; |
376 contourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endI
ndexPtr, &tHit, | 367 contourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endI
ndexPtr, &tHit, |
377 &hitDx, &tryAgain, onlyVertical, false); | 368 &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 | |
407 if (*onlyVertical) { | 369 if (*onlyVertical) { |
408 return current; | 370 return current; |
409 } | 371 } |
410 if (tryAgain) { | 372 if (tryAgain) { |
411 continue; | 373 continue; |
412 } | 374 } |
413 if (angleIncludeType < SkOpAngle::kBinarySingle) { | 375 if (angleIncludeType < SkOpAngle::kBinarySingle) { |
414 break; | 376 break; |
415 } | 377 } |
416 oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, e
ndIndexPtr, &tHit, | 378 oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, e
ndIndexPtr, &tHit, |
417 &hitOppDx, &tryAgain, NULL, true); | 379 &hitOppDx, &tryAgain, NULL, true); |
418 } while (tryAgain); | 380 } while (tryAgain); |
419 bool success = current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWi
nding, hitDx, | 381 current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, o
ppContourWinding, |
420 oppContourWinding, hitOppDx); | 382 hitOppDx); |
421 if (current->done()) { | 383 if (current->done()) { |
422 return NULL; | 384 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 } | |
429 } | 385 } |
430 return current; | 386 return current; |
431 } | 387 } |
432 | 388 |
433 static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) { | 389 static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) { |
434 int contourCount = (*contourList).count(); | 390 int contourCount = (*contourList).count(); |
435 for (int cTest = 0; cTest < contourCount; ++cTest) { | 391 for (int cTest = 0; cTest < contourCount; ++cTest) { |
436 SkOpContour* contour = (*contourList)[cTest]; | 392 SkOpContour* contour = (*contourList)[cTest]; |
437 if (!contour->calcAngles()) { | 393 if (!contour->calcAngles()) { |
438 return false; | 394 return false; |
439 } | 395 } |
440 } | 396 } |
441 return true; | 397 return true; |
442 } | 398 } |
443 | 399 |
444 static void checkDuplicates(SkTArray<SkOpContour*, true>* contourList) { | 400 static void checkDuplicates(SkTArray<SkOpContour*, true>* contourList) { |
445 int contourCount = (*contourList).count(); | 401 int contourCount = (*contourList).count(); |
446 for (int cTest = 0; cTest < contourCount; ++cTest) { | 402 for (int cTest = 0; cTest < contourCount; ++cTest) { |
447 SkOpContour* contour = (*contourList)[cTest]; | 403 SkOpContour* contour = (*contourList)[cTest]; |
448 contour->checkDuplicates(); | 404 contour->checkDuplicates(); |
449 } | 405 } |
450 } | 406 } |
451 | 407 |
452 static bool checkEnds(SkTArray<SkOpContour*, true>* contourList) { | 408 static void checkEnds(SkTArray<SkOpContour*, true>* contourList) { |
453 // it's hard to determine if the end of a cubic or conic nearly intersects a
nother curve. | 409 // it's hard to determine if the end of a cubic or conic nearly intersects a
nother curve. |
454 // instead, look to see if the connecting curve intersected at that same end
. | 410 // instead, look to see if the connecting curve intersected at that same end
. |
455 int contourCount = (*contourList).count(); | 411 int contourCount = (*contourList).count(); |
456 for (int cTest = 0; cTest < contourCount; ++cTest) { | 412 for (int cTest = 0; cTest < contourCount; ++cTest) { |
457 SkOpContour* contour = (*contourList)[cTest]; | 413 SkOpContour* contour = (*contourList)[cTest]; |
458 if (!contour->checkEnds()) { | 414 contour->checkEnds(); |
459 return false; | |
460 } | |
461 } | 415 } |
462 return true; | |
463 } | 416 } |
464 | 417 |
465 static bool checkMultiples(SkTArray<SkOpContour*, true>* contourList) { | 418 static bool checkMultiples(SkTArray<SkOpContour*, true>* contourList) { |
466 bool hasMultiples = false; | 419 bool hasMultiples = false; |
467 int contourCount = (*contourList).count(); | 420 int contourCount = (*contourList).count(); |
468 for (int cTest = 0; cTest < contourCount; ++cTest) { | 421 for (int cTest = 0; cTest < contourCount; ++cTest) { |
469 SkOpContour* contour = (*contourList)[cTest]; | 422 SkOpContour* contour = (*contourList)[cTest]; |
470 contour->checkMultiples(); | 423 contour->checkMultiples(); |
471 hasMultiples |= contour->hasMultiples(); | 424 hasMultiples |= contour->hasMultiples(); |
472 } | 425 } |
(...skipping 273 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
746 #if DEBUG_SHOW_WINDING | 699 #if DEBUG_SHOW_WINDING |
747 SkOpContour::debugShowWindingValues(contourList); | 700 SkOpContour::debugShowWindingValues(contourList); |
748 #endif | 701 #endif |
749 if (!CoincidenceCheck(contourList, total)) { | 702 if (!CoincidenceCheck(contourList, total)) { |
750 return false; | 703 return false; |
751 } | 704 } |
752 #if DEBUG_SHOW_WINDING | 705 #if DEBUG_SHOW_WINDING |
753 SkOpContour::debugShowWindingValues(contourList); | 706 SkOpContour::debugShowWindingValues(contourList); |
754 #endif | 707 #endif |
755 fixOtherTIndex(contourList); | 708 fixOtherTIndex(contourList); |
756 if (!checkEnds(contourList)) { // check if connecting curve intersected at
the same end | 709 checkEnds(contourList); // check if connecting curve intersected at the sam
e end |
757 return false; | |
758 } | |
759 bool hasM = checkMultiples(contourList); // check if intersections agree on
t and point values | 710 bool hasM = checkMultiples(contourList); // check if intersections agree on
t and point values |
760 SkTDArray<SkOpSegment::AlignedSpan> aligned; | 711 SkTDArray<SkOpSegment::AlignedSpan> aligned; |
761 if (hasM) { | 712 if (hasM) { |
762 alignMultiples(contourList, &aligned); // align pairs of identical poin
ts | 713 alignMultiples(contourList, &aligned); // align pairs of identical poin
ts |
763 alignCoincidence(contourList, aligned); | 714 alignCoincidence(contourList, aligned); |
764 } | 715 } |
765 checkDuplicates(contourList); // check if spans have the same number on the
other end | 716 checkDuplicates(contourList); // check if spans have the same number on the
other end |
766 checkTiny(contourList); // if pair have the same end points, mark them as p
arallel | 717 checkTiny(contourList); // if pair have the same end points, mark them as p
arallel |
767 checkSmall(contourList); // a pair of curves with a small span may turn int
o coincident lines | 718 checkSmall(contourList); // a pair of curves with a small span may turn int
o coincident lines |
768 joinCoincidence(contourList); // join curves that connect to a coincident p
air | 719 joinCoincidence(contourList); // join curves that connect to a coincident p
air |
769 sortSegments(contourList); | 720 sortSegments(contourList); |
770 if (!calcAngles(contourList)) { | 721 if (!calcAngles(contourList)) { |
771 return false; | 722 return false; |
772 } | 723 } |
773 sortAngles(contourList); | 724 sortAngles(contourList); |
774 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY | 725 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY |
775 DebugShowActiveSpans(*contourList); | 726 DebugShowActiveSpans(*contourList); |
776 #endif | 727 #endif |
777 return true; | 728 return true; |
778 } | 729 } |
OLD | NEW |