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 "SkOpCoincidence.h" | 8 #include "SkOpCoincidence.h" |
9 #include "SkOpEdgeBuilder.h" | 9 #include "SkOpEdgeBuilder.h" |
10 #include "SkPathOpsCommon.h" | 10 #include "SkPathOpsCommon.h" |
(...skipping 376 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
387 #endif | 387 #endif |
388 } | 388 } |
389 | 389 |
390 static void align(SkOpContourHead* contourList) { | 390 static void align(SkOpContourHead* contourList) { |
391 SkOpContour* contour = contourList; | 391 SkOpContour* contour = contourList; |
392 do { | 392 do { |
393 contour->align(); | 393 contour->align(); |
394 } while ((contour = contour->next())); | 394 } while ((contour = contour->next())); |
395 } | 395 } |
396 | 396 |
| 397 static void addAlignIntersections(SkOpContourHead* contourList, SkChunkAlloc* al
locator) { |
| 398 SkOpContour* contour = contourList; |
| 399 do { |
| 400 contour->addAlignIntersections(contourList, allocator); |
| 401 } while ((contour = contour->next())); |
| 402 } |
| 403 |
397 static void calcAngles(SkOpContourHead* contourList, SkChunkAlloc* allocator) { | 404 static void calcAngles(SkOpContourHead* contourList, SkChunkAlloc* allocator) { |
398 SkOpContour* contour = contourList; | 405 SkOpContour* contour = contourList; |
399 do { | 406 do { |
400 contour->calcAngles(allocator); | 407 contour->calcAngles(allocator); |
401 } while ((contour = contour->next())); | 408 } while ((contour = contour->next())); |
402 } | 409 } |
403 | 410 |
404 static void missingCoincidence(SkOpContourHead* contourList, | 411 static bool missingCoincidence(SkOpContourHead* contourList, |
405 SkOpCoincidence* coincidence, SkChunkAlloc* allocator) { | 412 SkOpCoincidence* coincidence, SkChunkAlloc* allocator) { |
406 SkOpContour* contour = contourList; | 413 SkOpContour* contour = contourList; |
| 414 bool result = false; |
407 do { | 415 do { |
408 contour->missingCoincidence(coincidence, allocator); | 416 result |= contour->missingCoincidence(coincidence, allocator); |
409 } while ((contour = contour->next())); | 417 } while ((contour = contour->next())); |
| 418 return result; |
410 } | 419 } |
411 | 420 |
412 static void moveMultiples(SkOpContourHead* contourList) { | 421 static void moveMultiples(SkOpContourHead* contourList) { |
413 SkOpContour* contour = contourList; | 422 SkOpContour* contour = contourList; |
414 do { | 423 do { |
415 contour->moveMultiples(); | 424 contour->moveMultiples(); |
416 } while ((contour = contour->next())); | 425 } while ((contour = contour->next())); |
417 } | 426 } |
418 | 427 |
419 static void moveNearby(SkOpContourHead* contourList) { | 428 static void moveNearby(SkOpContourHead* contourList) { |
(...skipping 11 matching lines...) Expand all Loading... |
431 } | 440 } |
432 | 441 |
433 bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidenc
e, | 442 bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidenc
e, |
434 SkChunkAlloc* allocator) { | 443 SkChunkAlloc* allocator) { |
435 SkOpGlobalState* globalState = contourList->globalState(); | 444 SkOpGlobalState* globalState = contourList->globalState(); |
436 // combine t values when multiple intersections occur on some segments but n
ot others | 445 // combine t values when multiple intersections occur on some segments but n
ot others |
437 moveMultiples(contourList); | 446 moveMultiples(contourList); |
438 // move t values and points together to eliminate small/tiny gaps | 447 // move t values and points together to eliminate small/tiny gaps |
439 moveNearby(contourList); | 448 moveNearby(contourList); |
440 align(contourList); // give all span members common values | 449 align(contourList); // give all span members common values |
| 450 coincidence->fixAligned(); // aligning may have marked a coincidence pt-t d
eleted |
441 #if DEBUG_VALIDATE | 451 #if DEBUG_VALIDATE |
442 globalState->setPhase(SkOpGlobalState::kIntersecting); | 452 globalState->setPhase(SkOpGlobalState::kIntersecting); |
443 #endif | 453 #endif |
| 454 // look for intersections on line segments formed by moving end points |
| 455 addAlignIntersections(contourList, allocator); |
444 coincidence->addMissing(allocator); | 456 coincidence->addMissing(allocator); |
445 #if DEBUG_VALIDATE | 457 #if DEBUG_VALIDATE |
446 globalState->setPhase(SkOpGlobalState::kWalking); | 458 globalState->setPhase(SkOpGlobalState::kWalking); |
447 #endif | 459 #endif |
448 coincidence->expand(); // check to see if, loosely, coincident ranges may b
e expanded | 460 // check to see if, loosely, coincident ranges may be expanded |
| 461 if (coincidence->expand()) { |
| 462 coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globa
lState)); |
| 463 } |
| 464 // the expanded ranges may not align -- add the missing spans |
449 coincidence->mark(); // mark spans of coincident segments as coincident | 465 coincidence->mark(); // mark spans of coincident segments as coincident |
450 missingCoincidence(contourList, coincidence, allocator); // look for coinci
dence missed earlier | 466 // look for coincidence missed earlier |
451 if (!coincidence->apply()) { // adjust the winding value to account for coi
ncident edges | 467 if (missingCoincidence(contourList, coincidence, allocator)) { |
452 return false; | 468 (void) coincidence->expand(); |
| 469 coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globa
lState)); |
| 470 coincidence->mark(); |
453 } | 471 } |
| 472 SkOpCoincidence overlaps; |
| 473 do { |
| 474 SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps; |
| 475 if (!pairs->apply()) { // adjust the winding value to account for coinc
ident edges |
| 476 return false; |
| 477 } |
| 478 // For each coincident pair that overlaps another, when the receivers (t
he 1st of the pair) |
| 479 // are different, construct a new pair to resolve their mutual span |
| 480 pairs->findOverlaps(&overlaps, allocator); |
| 481 } while (!overlaps.isEmpty()); |
454 calcAngles(contourList, allocator); | 482 calcAngles(contourList, allocator); |
455 sortAngles(contourList); | 483 sortAngles(contourList); |
456 if (globalState->angleCoincidence()) { | 484 if (globalState->angleCoincidence()) { |
457 missingCoincidence(contourList, coincidence, allocator); | 485 (void) missingCoincidence(contourList, coincidence, allocator); |
458 if (!coincidence->apply()) { | 486 if (!coincidence->apply()) { |
459 return false; | 487 return false; |
460 } | 488 } |
461 } | 489 } |
462 #if DEBUG_ACTIVE_SPANS | 490 #if DEBUG_ACTIVE_SPANS |
463 coincidence->debugShowCoincidence(); | 491 coincidence->debugShowCoincidence(); |
464 DebugShowActiveSpans(contourList); | 492 DebugShowActiveSpans(contourList); |
465 #endif | 493 #endif |
466 return true; | 494 return true; |
467 } | 495 } |
OLD | NEW |