GrTessellator: always rewind to edge top when splitting.
In some cases, a split edge may go out-of-order with a neighbouring edge
which has already been removed from the active edge list.
The only way to be sure is to always rewind to the edge top.
This may have performance implications for paths with many (hundreds) of
self-intersections. We'll have to watch the bots carefully.
Bug: 966274, 966364.
Change-Id: I5a1b7abe9baa7fc279cbf7d1dfa258dcdaa35f11
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/217637
Reviewed-by: Robert Phillips <robertphillips@google.com>
Commit-Queue: Stephen White <senorblanco@chromium.org>
diff --git a/src/gpu/GrTessellator.cpp b/src/gpu/GrTessellator.cpp
index 88049c8..19c2447 100644
--- a/src/gpu/GrTessellator.cpp
+++ b/src/gpu/GrTessellator.cpp
@@ -62,9 +62,8 @@
* neighbouring edges at the top or bottom vertex. This is handled by merging the
* edges (merge_collinear_edges()).
* B) Intersections may cause an edge to violate the left-to-right ordering of the
- * active edge list. This is handled by detecting potential violations and rewinding
- * the active edge list to the vertex before they occur (rewind() during merging,
- * rewind_if_necessary() during splitting).
+ * active edge list. This is handled during merging or splitting by rewind()ing the
+ * active edge list to the vertex before potential violations occur.
*
* The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and
* Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it
@@ -326,11 +325,10 @@
* An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
* "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
* Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
- * point). For speed, that case is only tested by the callers that require it (e.g.,
- * rewind_if_necessary()). Edges also handle checking for intersection with other edges.
- * Currently, this converts the edges to the parametric form, in order to avoid doing a division
- * until an intersection has been confirmed. This is slightly slower in the "found" case, but
- * a lot faster in the "not found" case.
+ * point). For speed, that case is only tested by the callers that require it. Edges also handle
+ * checking for intersection with other edges. Currently, this converts the edges to the
+ * parametric form, in order to avoid doing a division until an intersection has been confirmed.
+ * This is slightly slower in the "found" case, but a lot faster in the "not found" case.
*
* The coefficients of the line equation stored in double precision to avoid catastrphic
* cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is
@@ -999,49 +997,12 @@
*current = v;
}
-void rewind_if_necessary(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c) {
- if (!activeEdges || !current) {
- return;
- }
- Vertex* top = edge->fTop;
- Vertex* bottom = edge->fBottom;
- if (edge->fLeft) {
- Vertex* leftTop = edge->fLeft->fTop;
- Vertex* leftBottom = edge->fLeft->fBottom;
- if (c.sweep_lt(leftTop->fPoint, top->fPoint) && !edge->fLeft->isLeftOf(top)) {
- rewind(activeEdges, current, leftTop, c);
- } else if (c.sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(leftTop)) {
- rewind(activeEdges, current, top, c);
- } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) &&
- !edge->fLeft->isLeftOf(bottom)) {
- rewind(activeEdges, current, leftTop, c);
- } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) {
- rewind(activeEdges, current, top, c);
- }
- }
- if (edge->fRight) {
- Vertex* rightTop = edge->fRight->fTop;
- Vertex* rightBottom = edge->fRight->fBottom;
- if (c.sweep_lt(rightTop->fPoint, top->fPoint) && !edge->fRight->isRightOf(top)) {
- rewind(activeEdges, current, rightTop, c);
- } else if (c.sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(rightTop)) {
- rewind(activeEdges, current, top, c);
- } else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) &&
- !edge->fRight->isRightOf(bottom)) {
- rewind(activeEdges, current, rightTop, c);
- } else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) &&
- !edge->isLeftOf(rightBottom)) {
- rewind(activeEdges, current, top, c);
- }
- }
-}
-
void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c) {
remove_edge_below(edge);
edge->fTop = v;
edge->recompute();
insert_edge_below(edge, v, c);
- rewind_if_necessary(edge, activeEdges, current, c);
+ rewind(activeEdges, current, edge->fTop, c);
merge_collinear_edges(edge, activeEdges, current, c);
}
@@ -1050,7 +1011,7 @@
edge->fBottom = v;
edge->recompute();
insert_edge_above(edge, v, c);
- rewind_if_necessary(edge, activeEdges, current, c);
+ rewind(activeEdges, current, edge->fTop, c);
merge_collinear_edges(edge, activeEdges, current, c);
}