GrTessellator: implement out-of-range splitting and AEL rewinding.

Due to floating point inaccuracy, when intersecting edges, the
intersection point may fall above one of the edges' top vertices
or below one of the bottom vertices.  In these cases, we were simply
splitting one edge on the relevant endpoint of the other edge. This
is incorrect if the intersection is far from the endpoint (e.g.,
the test case in the linked bug, where one of the intersected edges
is near-horizontal but the intersection falls below both of its
endpoints, in the middle of the edge.)

The correct solution is to split both edges as normal, and take care
to produce edges with the correct ordering where the intersection is
above or below an edge. However, since the new vertex may be above
the current vertex, simply restarting intersection checks at the
current vertex won't work. We need to process the intersection
vertex before the current one.

This introduces another problem: unlike all other splitting modes
(which always shorten edges), splitting an edge above the top or 
below the bottom can lengthen it, causing it to violate the AEL 
with an adjacent edge which then shortens it back to the original 
point (in cleanup_active_edges()). Since the splitting and merging 
code can't agree, we loop forever.

Instead of simply fusing neighboring edges in cleanup_active_edges(), 
the proper fix to this problem is to detect the AEL violation and 
rewind all processing to the vertex above it. For performance, we 
only rewind when we detect that a split edge is no longer ordered 
within the mesh (merge_enclosing_edges()) or within the the AEL 
(rewind_if_necessary()).  We also store the enclosing edges of each 
vertex, which allows us to rewind quickly, since we know exactly which 
edges need to be added/removed from the AEL.

cleanup_active_edges(), fix_active_state() and Vertex::fProcessed have
been removed. In their place are rewind_active_edges() and 
rewind_if_necessary(), which uses the same logic as 
cleanup_active_edges() but uses it to know when to rewind.

Bug: skia:5026
Change-Id: I3638a429f5428498d6df6bb7b98c67374dc291aa
Reviewed-on: https://skia-review.googlesource.com/18900
Reviewed-by: Brian Salomon <bsalomon@google.com>
Commit-Queue: Stephen White <senorblanco@chromium.org>

1 files changed, 173 insertions, 167 deletions

diff --git a/src/gpu/GrTessellator.cpp b/src/gpu/GrTessellator.cpp
index de14afe40e..6e9665f7c7 100644
--- a/src/gpu/GrTessellator.cpp
+++ b/src/gpu/GrTessellator.cpp
@@ -50,17 +50,15 @@
  * line-sweep algorithm, but due to floating point inaccuracy, the intersection points are
  * not exact and may violate the mesh topology or active edge list ordering. We
  * accommodate this by adjusting the topology of the mesh and AEL to match the intersection
- * points. This occurs in three ways:
+ * points. This occurs in two ways:
  *
  * A) Intersections may cause a shortened edge to no longer be ordered with respect to its
  *    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 splitting the neighbour edge on the
- *    intersected vertex (cleanup_active_edges()).
- * C) Shortening an edge may cause an active edge to become inactive or an inactive edge
- *    to become active. This is handled by removing or inserting the edge in the active
- *    edge list (fix_active_state()).
+ *    active edge list. This is handled by detecting potential violati0ns and rewinding
+ *    the active edge list to the vertex before they occur (rewind() during merging,
+ *    rewind_if_necessary() during splitting).
  *
  * 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
@@ -145,25 +143,26 @@ struct Vertex {
     : fPoint(point), fPrev(nullptr), fNext(nullptr)
     , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr)
     , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr)
+    , fLeftEnclosingEdge(nullptr), fRightEnclosingEdge(nullptr)
     , fPartner(nullptr)
-    , fProcessed(false)
     , fAlpha(alpha)
 #if LOGGING_ENABLED
     , fID (-1.0f)
 #endif
     {}
-    SkPoint fPoint;           // Vertex position
-    Vertex* fPrev;            // Linked list of contours, then Y-sorted vertices.
-    Vertex* fNext;            // "
-    Edge*   fFirstEdgeAbove;  // Linked list of edges above this vertex.
-    Edge*   fLastEdgeAbove;   // "
-    Edge*   fFirstEdgeBelow;  // Linked list of edges below this vertex.
-    Edge*   fLastEdgeBelow;   // "
-    Vertex* fPartner;         // Corresponding inner or outer vertex (for AA).
-    bool    fProcessed;       // Has this vertex been seen in simplify()?
+    SkPoint fPoint;               // Vertex position
+    Vertex* fPrev;                // Linked list of contours, then Y-sorted vertices.
+    Vertex* fNext;                // "
+    Edge*   fFirstEdgeAbove;      // Linked list of edges above this vertex.
+    Edge*   fLastEdgeAbove;       // "
+    Edge*   fFirstEdgeBelow;      // Linked list of edges below this vertex.
+    Edge*   fLastEdgeBelow;       // "
+    Edge*   fLeftEnclosingEdge;   // Nearest edge in the AEL left of this vertex.
+    Edge*   fRightEnclosingEdge;  // Nearest edge in the AEL right of this vertex.
+    Vertex* fPartner;             // Corresponding inner or outer vertex (for AA).
     uint8_t fAlpha;
 #if LOGGING_ENABLED
-    float   fID;              // Identifier used for logging.
+    float   fID;                  // Identifier used for logging.
 #endif
 };
 
@@ -312,7 +311,7 @@ struct Line {
  * "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.,
- * cleanup_active_edges()). Edges also handle checking for intersection with other edges.
+ * 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.
@@ -808,40 +807,6 @@ void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right)
     *right = next;
 }
 
-void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** left, Edge** right) {
-    Edge* prev = nullptr;
-    Edge* next;
-    for (next = edges->fHead; next != nullptr; next = next->fRight) {
-        if ((c.sweep_lt(next->fTop->fPoint, edge->fTop->fPoint) && next->isRightOf(edge->fTop)) ||
-            (c.sweep_lt(edge->fTop->fPoint, next->fTop->fPoint) && edge->isLeftOf(next->fTop)) ||
-            (c.sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) &&
-             next->isRightOf(edge->fBottom)) ||
-            (c.sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) &&
-             edge->isLeftOf(next->fBottom))) {
-            break;
-        }
-        prev = next;
-    }
-    *left = prev;
-    *right = next;
-}
-
-void fix_active_state(Edge* edge, EdgeList* activeEdges, Comparator& c) {
-    if (!activeEdges) {
-        return;
-    }
-    if (activeEdges->contains(edge)) {
-        if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) {
-            remove_edge(edge, activeEdges);
-        }
-    } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) {
-        Edge* left;
-        Edge* right;
-        find_enclosing_edges(edge, activeEdges, c, &left, &right);
-        insert_edge(edge, left, activeEdges);
-    }
-}
-
 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) {
     if (edge->fTop->fPoint == edge->fBottom->fPoint ||
         c.sweep_lt(edge->fBottom->fPoint, edge->fTop->fPoint)) {
@@ -898,80 +863,137 @@ void disconnect(Edge* edge)
     remove_edge_below(edge);
 }
 
-void erase_edge(Edge* edge, EdgeList* edges) {
-    LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID);
-    disconnect(edge);
-    if (edges && edges->contains(edge)) {
-        remove_edge(edge, edges);
+void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c);
+
+void rewind(EdgeList* activeEdges, Vertex** current, Vertex* dst, Comparator& c) {
+    if (!current || *current == dst || c.sweep_lt((*current)->fPoint, dst->fPoint)) {
+        return;
     }
+    Vertex* v = *current;
+    LOG("rewinding active edges from vertex %g to vertex %g\n", v->fID, dst->fID);
+    while (v != dst) {
+        v = v->fPrev;
+        for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
+            remove_edge(e, activeEdges);
+        }
+        Edge* leftEdge = v->fLeftEnclosingEdge;
+        for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
+            insert_edge(e, leftEdge, activeEdges);
+            leftEdge = e;
+        }
+    }
+    *current = v;
 }
 
-void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c);
+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, Comparator& 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);
-    fix_active_state(edge, activeEdges, c);
-    merge_collinear_edges(edge, activeEdges, c);
+    rewind_if_necessary(edge, activeEdges, current, c);
+    merge_collinear_edges(edge, activeEdges, current, c);
 }
 
-void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) {
+void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c) {
     remove_edge_above(edge);
     edge->fBottom = v;
     edge->recompute();
     insert_edge_above(edge, v, c);
-    fix_active_state(edge, activeEdges, c);
-    merge_collinear_edges(edge, activeEdges, c);
+    rewind_if_necessary(edge, activeEdges, current, c);
+    merge_collinear_edges(edge, activeEdges, current, c);
 }
 
-void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c) {
+void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
+                       Comparator& c) {
     if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {
         LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n",
             edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
             edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
+        rewind(activeEdges, current, edge->fTop, c);
         other->fWinding += edge->fWinding;
-        erase_edge(edge, activeEdges);
+        disconnect(edge);
     } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
+        rewind(activeEdges, current, edge->fTop, c);
         other->fWinding += edge->fWinding;
-        set_bottom(edge, other->fTop, activeEdges, c);
+        set_bottom(edge, other->fTop, activeEdges, current, c);
     } else {
+        rewind(activeEdges, current, other->fTop, c);
         edge->fWinding += other->fWinding;
-        set_bottom(other, edge->fTop, activeEdges, c);
+        set_bottom(other, edge->fTop, activeEdges, current, c);
     }
 }
 
-void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c) {
+void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
+                       Comparator& c) {
     if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {
         LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n",
             edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
             edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
+        rewind(activeEdges, current, edge->fTop, c);
         other->fWinding += edge->fWinding;
-        erase_edge(edge, activeEdges);
+        disconnect(edge);
     } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
+        rewind(activeEdges, current, other->fTop, c);
         edge->fWinding += other->fWinding;
-        set_top(other, edge->fBottom, activeEdges, c);
+        set_top(other, edge->fBottom, activeEdges, current, c);
     } else {
+        rewind(activeEdges, current, edge->fTop, c);
         other->fWinding += edge->fWinding;
-        set_top(edge, other->fBottom, activeEdges, c);
+        set_top(edge, other->fBottom, activeEdges, current, c);
     }
 }
 
-void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c) {
+void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c) {
     for (;;) {
         if (edge->fPrevEdgeAbove && (edge->fTop == edge->fPrevEdgeAbove->fTop ||
                                      !edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) {
-            merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges, c);
+            merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges, current, c);
         } else if (edge->fNextEdgeAbove && (edge->fTop == edge->fNextEdgeAbove->fTop ||
                                             !edge->isLeftOf(edge->fNextEdgeAbove->fTop))) {
-            merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges, c);
+            merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges, current, c);
         } else if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom ||
                                      !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom))) {
-            merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, c);
+            merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, current, c);
         } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->fBottom ||
                                             !edge->isLeftOf(edge->fNextEdgeBelow->fBottom))) {
-            merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, c);
+            merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, current, c);
         } else {
             break;
         }
@@ -982,59 +1004,30 @@ void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c) {
     SkASSERT(!edge->fNextEdgeBelow || edge->fNextEdgeBelow->isRightOf(edge->fBottom));
 }
 
-void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkArenaAlloc& alloc);
-
-void cleanup_active_edges(Edge* edge, EdgeList* activeEdges, Comparator& c, SkArenaAlloc& alloc) {
-    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)) {
-            split_edge(edge->fLeft, edge->fTop, activeEdges, c, alloc);
-        } else if (c.sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(leftTop)) {
-            split_edge(edge, leftTop, activeEdges, c, alloc);
-        } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) &&
-                   !edge->fLeft->isLeftOf(bottom)) {
-            split_edge(edge->fLeft, bottom, activeEdges, c, alloc);
-        } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) {
-            split_edge(edge, leftBottom, activeEdges, c, alloc);
-        }
-    }
-    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)) {
-            split_edge(edge->fRight, top, activeEdges, c, alloc);
-        } else if (c.sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(rightTop)) {
-            split_edge(edge, rightTop, activeEdges, c, alloc);
-        } else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) &&
-                   !edge->fRight->isRightOf(bottom)) {
-            split_edge(edge->fRight, bottom, activeEdges, c, alloc);
-        } else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) &&
-                   !edge->isLeftOf(rightBottom)) {
-            split_edge(edge, rightBottom, activeEdges, c, alloc);
-        }
-    }
-}
-
-void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkArenaAlloc& alloc) {
+void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c,
+                SkArenaAlloc& alloc) {
     LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
         edge->fTop->fID, edge->fBottom->fID,
         v->fID, v->fPoint.fX, v->fPoint.fY);
+    Vertex* top;
+    Vertex* bottom;
     if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) {
-        set_top(edge, v, activeEdges, c);
+        top = v;
+        bottom = edge->fTop;
+        set_top(edge, v, activeEdges, current, c);
     } else if (c.sweep_lt(edge->fBottom->fPoint, v->fPoint)) {
-        set_bottom(edge, v, activeEdges, c);
+        top = edge->fBottom;
+        bottom = v;
+        set_bottom(edge, v, activeEdges, current, c);
     } else {
-        Edge* newEdge = alloc.make<Edge>(v, edge->fBottom, edge->fWinding, edge->fType);
-        insert_edge_below(newEdge, v, c);
-        insert_edge_above(newEdge, edge->fBottom, c);
-        set_bottom(edge, v, activeEdges, c);
-        cleanup_active_edges(edge, activeEdges, c, alloc);
-        fix_active_state(newEdge, activeEdges, c);
-        merge_collinear_edges(newEdge, activeEdges, c);
+        top = v;
+        bottom = edge->fBottom;
+        set_bottom(edge, v, activeEdges, current, c);
     }
+    Edge* newEdge = alloc.make<Edge>(top, bottom, edge->fWinding, edge->fType);
+    insert_edge_below(newEdge, top, c);
+    insert_edge_above(newEdge, bottom, c);
+    merge_collinear_edges(newEdge, activeEdges, current, c);
 }
 
 Edge* connect(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkArenaAlloc& alloc,
@@ -1043,7 +1036,7 @@ Edge* connect(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkAren
     insert_edge_below(edge, edge->fTop, c);
     insert_edge_above(edge, edge->fBottom, c);
     edge->fWinding *= winding_scale;
-    merge_collinear_edges(edge, nullptr, c);
+    merge_collinear_edges(edge, nullptr, nullptr, c);
     return edge;
 }
 
@@ -1057,12 +1050,12 @@ void merge_vertices(Vertex* src, Vertex* dst, VertexList* mesh, Comparator& c,
     }
     for (Edge* edge = src->fFirstEdgeAbove; edge;) {
         Edge* next = edge->fNextEdgeAbove;
-        set_bottom(edge, dst, nullptr, c);
+        set_bottom(edge, dst, nullptr, nullptr, c);
         edge = next;
     }
     for (Edge* edge = src->fFirstEdgeBelow; edge;) {
         Edge* next = edge->fNextEdgeBelow;
-        set_top(edge, dst, nullptr, c);
+        set_top(edge, dst, nullptr, nullptr, c);
         edge = next;
     }
     mesh->remove(src);
@@ -1079,61 +1072,69 @@ uint8_t max_edge_alpha(Edge* a, Edge* b) {
     }
 }
 
-Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c,
-                               SkArenaAlloc& alloc) {
+bool check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
+                            Comparator& c, SkArenaAlloc& alloc) {
     if (!edge || !other) {
-        return nullptr;
+        return false;
     }
     SkPoint p;
     uint8_t alpha;
     if (edge->intersect(*other, &p, &alpha)) {
         Vertex* v;
         LOG("found intersection, pt is %g, %g\n", p.fX, p.fY);
-        if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) {
-            split_edge(other, edge->fTop, activeEdges, c, alloc);
+        Vertex* top = *current;
+        // If the intersection point is above the current vertex, rewind to the vertex above the
+        // intersection.
+        while (c.sweep_lt(p, top->fPoint) && top->fPrev) {
+            top = top->fPrev;
+        }
+        rewind(activeEdges, current, top, c);
+        if (p == edge->fTop->fPoint) {
+            split_edge(other, edge->fTop, activeEdges, current, c, alloc);
             v = edge->fTop;
-        } else if (p == edge->fBottom->fPoint || c.sweep_lt(edge->fBottom->fPoint, p)) {
-            split_edge(other, edge->fBottom, activeEdges, c, alloc);
+        } else if (p == edge->fBottom->fPoint) {
+            split_edge(other, edge->fBottom, activeEdges, current, c, alloc);
             v = edge->fBottom;
-        } else if (p == other->fTop->fPoint || c.sweep_lt(p, other->fTop->fPoint)) {
-            split_edge(edge, other->fTop, activeEdges, c, alloc);
+        } else if (p == other->fTop->fPoint) {
+            split_edge(edge, other->fTop, activeEdges, current, c, alloc);
             v = other->fTop;
-        } else if (p == other->fBottom->fPoint || c.sweep_lt(other->fBottom->fPoint, p)) {
-            split_edge(edge, other->fBottom, activeEdges, c, alloc);
+        } else if (p == other->fBottom->fPoint) {
+            split_edge(edge, other->fBottom, activeEdges, current, c, alloc);
             v = other->fBottom;
         } else {
-            Vertex* nextV = edge->fTop;
-            while (c.sweep_lt(p, nextV->fPoint)) {
-                nextV = nextV->fPrev;
-            }
-            while (c.sweep_lt(nextV->fPoint, p)) {
+            Vertex* prevV = top;
+            Vertex* nextV = top->fNext;
+            while (nextV && c.sweep_lt(nextV->fPoint, p)) {
+                prevV = nextV;
                 nextV = nextV->fNext;
             }
-            Vertex* prevV = nextV->fPrev;
-            if (coincident(prevV->fPoint, p)) {
+            if (prevV && coincident(prevV->fPoint, p)) {
                 v = prevV;
-            } else if (coincident(nextV->fPoint, p)) {
+            } else if (nextV && coincident(nextV->fPoint, p)) {
                 v = nextV;
             } else {
                 v = alloc.make<Vertex>(p, alpha);
-                LOG("inserting between %g (%g, %g) and %g (%g, %g)\n",
-                    prevV->fID, prevV->fPoint.fX, prevV->fPoint.fY,
-                    nextV->fID, nextV->fPoint.fX, nextV->fPoint.fY);
 #if LOGGING_ENABLED
-                v->fID = (nextV->fID + prevV->fID) * 0.5f;
+                float prevID = prevV ? prevV->fID : 0.0f;
+                float nextID = nextV ? nextV->fID : prevV->fID + 1.0f;
+                v->fID = (prevID + nextID) * 0.5f;
 #endif
                 v->fPrev = prevV;
                 v->fNext = nextV;
-                prevV->fNext = v;
-                nextV->fPrev = v;
+                if (prevV) {
+                    prevV->fNext = v;
+                }
+                if (nextV) {
+                    nextV->fPrev = v;
+                }
             }
-            split_edge(edge, v, activeEdges, c, alloc);
-            split_edge(other, v, activeEdges, c, alloc);
+            split_edge(edge, v, activeEdges, current, c, alloc);
+            split_edge(other, v, activeEdges, current, c, alloc);
         }
         v->fAlpha = SkTMax(v->fAlpha, alpha);
-        return v;
+        return true;
     }
-    return nullptr;
+    return false;
 }
 
 void sanitize_contours(VertexList* contours, int contourCnt, bool approximate) {
@@ -1224,6 +1225,12 @@ void sorted_merge(VertexList* front, VertexList* back, VertexList* result, Compa
     } else {
         sorted_merge<sweep_lt_vert>(front, back, result);
     }
+#if LOGGING_ENABLED
+    float id = 0.0f;
+    for (Vertex* v = result->fHead; v; v = v->fNext) {
+        v->fID = id++;
+    }
+#endif
 }
 
 // Stage 3: sort the vertices by increasing sweep direction.
@@ -1265,37 +1272,37 @@ void simplify(const VertexList& vertices, Comparator& c, SkArenaAlloc& alloc) {
         if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
             continue;
         }
-#if LOGGING_ENABLED
-        LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
-#endif
         Edge* leftEnclosingEdge;
         Edge* rightEnclosingEdge;
         bool restartChecks;
         do {
+            LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
             restartChecks = false;
             find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
             if (rightEnclosingEdge && !rightEnclosingEdge->isRightOf(v)) {
-                split_edge(rightEnclosingEdge, v, &activeEdges, c, alloc);
+                split_edge(rightEnclosingEdge, v, &activeEdges, &v, c, alloc);
                 restartChecks = true;
                 continue;
             }
+            SkASSERT(!rightEnclosingEdge || rightEnclosingEdge->isRightOf(v));
+            v->fLeftEnclosingEdge = leftEnclosingEdge;
+            v->fRightEnclosingEdge = rightEnclosingEdge;
             if (v->fFirstEdgeBelow) {
                 for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) {
-                    if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, c, alloc)) {
+                    if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, &v, c,
+                                               alloc)) {
                         restartChecks = true;
                         break;
                     }
-                    if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, c, alloc)) {
+                    if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, &v, c,
+                                               alloc)) {
                         restartChecks = true;
                         break;
                     }
                 }
             } else {
-                if (Vertex* pv = check_for_intersection(leftEnclosingEdge, rightEnclosingEdge,
-                                                        &activeEdges, c, alloc)) {
-                    if (c.sweep_lt(pv->fPoint, v->fPoint)) {
-                        v = pv;
-                    }
+                if (check_for_intersection(leftEnclosingEdge, rightEnclosingEdge,
+                                           &activeEdges, &v, c, alloc)) {
                     restartChecks = true;
                 }
 
@@ -1315,7 +1322,6 @@ void simplify(const VertexList& vertices, Comparator& c, SkArenaAlloc& alloc) {
             insert_edge(e, leftEdge, &activeEdges);
             leftEdge = e;
         }
-        v->fProcessed = true;
     }
 }