Enabling clip stack flattening exercises path ops.
Iterating through the 903K skps that represent the
imagable 1M top web pages triggers a number of
bugs, some of which are addressed here.
Some web pages trigger intersecting cubic
representations of arc with their conic
counterparts. This exposed a flaw in coincident
detection that caused an infinite loop. The loop
alternatively extended the coincident section and,
determining the that the bounds of the curve pairs
did not overlap, deleted the extension.
Track the number of times the coincident detection
is called, and if it exceeds an empirically found
limit, assume that the curves are coincident and
force it to be so.
The loop count limit can be determined by enabling
DEBUG_T_SECT_LOOP_COUNT and running all tests. The
largest count is reported on completion.
Another class of bugs was caused by concident
detection duplicating nearly identical points that
had been merged earlier. To track these bugs, the
'handle coincidence' code was duplicated as a
const debug variety that reported if one of a
dozen or so irregularities are present; then it is
easier to see when a block of code that fixes one
irregularity regresses another.
Creating the debug const code version exposed some
non-debug code that could be const, and some that
was experimental and could be removed. Set
DEBUG_COINCIDENCE to track coincidence health and
handling.
For running on Chrome, DEBUG_VERIFY checks the
result of pathops against the same operation
using SkRegion to verify that the results are
nearly the same.
When visualizing the pathops work using
tools/pathops_visualizer.htm, set
DEBUG_DUMP_ALIGNMENT to see the curves after
they've been aligned for coincidence.
Other bugs fixed include detecting when a
section of a pair of curves have devolved into
lines and are coincident.
TBR=reed@google.com
Review URL: https://codereview.chromium.org/1394503003
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index 58bcacd..0060db2 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -450,42 +450,70 @@
SkChunkAlloc* allocator) {
SkOpGlobalState* globalState = contourList->globalState();
// combine t values when multiple intersections occur on some segments but not others
+ DEBUG_COINCIDENCE_HEALTH(contourList, "start");
moveMultiples(contourList);
+ DEBUG_COINCIDENCE_HEALTH(contourList, "moveMultiples");
findCollapsed(contourList);
+ DEBUG_COINCIDENCE_HEALTH(contourList, "findCollapsed");
// move t values and points together to eliminate small/tiny gaps
moveNearby(contourList);
+ DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby");
align(contourList); // give all span members common values
+ DEBUG_COINCIDENCE_HEALTH(contourList, "align");
coincidence->fixAligned(); // aligning may have marked a coincidence pt-t deleted
+ DEBUG_COINCIDENCE_HEALTH(contourList, "fixAligned");
#if DEBUG_VALIDATE
globalState->setPhase(SkOpGlobalState::kIntersecting);
#endif
// look for intersections on line segments formed by moving end points
addAlignIntersections(contourList, allocator);
- coincidence->addMissing(allocator);
+ DEBUG_COINCIDENCE_HEALTH(contourList, "addAlignIntersections");
+ if (coincidence->addMissing(allocator)) {
+ DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing");
+ moveNearby(contourList);
+ DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby2");
+ align(contourList); // give all span members common values
+ DEBUG_COINCIDENCE_HEALTH(contourList, "align2");
+ coincidence->fixAligned(); // aligning may have marked a coincidence pt-t deleted
+ DEBUG_COINCIDENCE_HEALTH(contourList, "fixAligned2");
+ }
#if DEBUG_VALIDATE
globalState->setPhase(SkOpGlobalState::kWalking);
#endif
// check to see if, loosely, coincident ranges may be expanded
if (coincidence->expand()) {
- coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globalState));
+ DEBUG_COINCIDENCE_HEALTH(contourList, "expand1");
+ if (!coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globalState))) {
+ return false;
+ }
}
+ DEBUG_COINCIDENCE_HEALTH(contourList, "expand2");
// the expanded ranges may not align -- add the missing spans
coincidence->mark(); // mark spans of coincident segments as coincident
+ DEBUG_COINCIDENCE_HEALTH(contourList, "mark1");
// look for coincidence missed earlier
if (missingCoincidence(contourList, coincidence, allocator)) {
+ DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence1");
(void) coincidence->expand();
- coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globalState));
+ DEBUG_COINCIDENCE_HEALTH(contourList, "expand3");
+ if (!coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globalState))) {
+ return false;
+ }
+ DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded2");
coincidence->mark();
}
+ DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence2");
SkOpCoincidence overlaps;
do {
SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps;
if (!pairs->apply()) { // adjust the winding value to account for coincident edges
return false;
}
+ DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->apply");
// For each coincident pair that overlaps another, when the receivers (the 1st of the pair)
// are different, construct a new pair to resolve their mutual span
pairs->findOverlaps(&overlaps, allocator);
+ DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->findOverlaps");
} while (!overlaps.isEmpty());
calcAngles(contourList, allocator);
sortAngles(contourList);