Improve tessellating path rasterizer performance on dashed paths.

src/gpu/GrTessellatingPathRenderer.cpp

 /*
  * Copyright 2015 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "GrTessellatingPathRenderer.h"
 
 #include "GrBatch.h"
@@ skipping 187 matching lines @@
     data = emit_vertex(v2, data);
     data = emit_vertex(v0, data);
 #else
     data = emit_vertex(v0, data);
     data = emit_vertex(v1, data);
     data = emit_vertex(v2, data);
 #endif
     return data;
 }
 
+struct EdgeList {
+    EdgeList() : fHead(NULL), fTail(NULL) {}
+    Edge* fHead;
+    Edge* fTail;
+};
+
 /**
  * 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 which require it (e.g.,
  * cleanup_active_edges()). 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.
  *
@@ skipping 69 matching lines @@
         if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNumer > denom)
                         : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNumer < denom)) {
             return false;
         }
         double s = sNumer / denom;
         SkASSERT(s >= 0.0 && s <= 1.0);
         p->fX = SkDoubleToScalar(fTop->fPoint.fX + s * fDX);
         p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fDY);
         return true;
     }
-    bool isActive(Edge** activeEdges) const {
-        return activeEdges && (fLeft || fRight || *activeEdges == this);
+    bool isActive(EdgeList* activeEdges) const {
+        return activeEdges && (fLeft || fRight || activeEdges->fHead == this);
     }
 };
 
 /***************************************************************************************/
 
 struct Poly {
     Poly(int winding)
         : fWinding(winding)
         , fHead(NULL)
         , fTail(NULL)
@@ skipping 318 matching lines @@
     }
 }
 
 Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator& c) {
     int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
     Vertex* top = winding < 0 ? next : prev;
     Vertex* bottom = winding < 0 ? prev : next;
     return ALLOC_NEW(Edge, (top, bottom, winding), alloc);
 }
 
-void remove_edge(Edge* edge, Edge** head) {
+void remove_edge(Edge* edge, EdgeList* edges) {
     LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
-    SkASSERT(edge->isActive(head));
-    remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, head, NULL);
+    SkASSERT(edge->isActive(edges));
+    remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges->fTail);
 }
 
-void insert_edge(Edge* edge, Edge* prev, Edge** head) {
+void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) {
     LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
-    SkASSERT(!edge->isActive(head));
-    Edge* next = prev ? prev->fRight : *head;
-    insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, head, NULL);
+    SkASSERT(!edge->isActive(edges));
+    Edge* next = prev ? prev->fRight : edges->fHead;
+    insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, &edges->fTail);
 }
 
-void find_enclosing_edges(Vertex* v, Edge* head, Edge** left, Edge** right) {
+void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) {
     if (v->fFirstEdgeAbove) {
         *left = v->fFirstEdgeAbove->fLeft;
         *right = v->fLastEdgeAbove->fRight;
         return;
     }
-    Edge* prev = NULL;
-    Edge* next;
-    for (next = head; next != NULL; next = next->fRight) {
-        if (next->isRightOf(v)) {
+    Edge* next = NULL;
+    Edge* prev;
+    for (prev = edges->fTail; prev != NULL; prev = prev->fLeft) {
+        if (prev->isLeftOf(v)) {
             break;
         }
-        prev = next;
+        next = prev;
     }
     *left = prev;
     *right = next;
     return;
 }
 
-void find_enclosing_edges(Edge* edge, Edge* head, Comparator& c, Edge** left, Edge** right) {
+void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** left, Edge** right) {
     Edge* prev = NULL;
     Edge* next;
-    for (next = head; next != NULL; next = next->fRight) {
+    for (next = edges->fHead; next != NULL; next = next->fRight) {
         if ((c.sweep_gt(edge->fTop->fPoint, next->fTop->fPoint) && next->isRightOf(edge->fTop)) ||
             (c.sweep_gt(next->fTop->fPoint, edge->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;
     return;
 }
 
-void fix_active_state(Edge* edge, Edge** activeEdges, Comparator& c) {
+void fix_active_state(Edge* edge, EdgeList* activeEdges, Comparator& c) {
     if (edge->isActive(activeEdges)) {
         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);
+        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_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {
         return;
     }
     LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
@@ skipping 34 matching lines @@
         edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
 }
 
 void remove_edge_below(Edge* edge) {
     LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
         edge->fTop->fID);
     remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
         edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
 }
 
-void erase_edge_if_zero_winding(Edge* edge, Edge** head) {
+void erase_edge_if_zero_winding(Edge* edge, EdgeList* edges) {
     if (edge->fWinding != 0) {
         return;
     }
     LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID);
     remove_edge_above(edge);
     remove_edge_below(edge);
-    if (edge->isActive(head)) {
-        remove_edge(edge, head);
+    if (edge->isActive(edges)) {
+        remove_edge(edge, edges);
     }
 }
 
-void merge_collinear_edges(Edge* edge, Edge** activeEdges, Comparator& c);
+void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c);
 
-void set_top(Edge* edge, Vertex* v, Edge** activeEdges, Comparator& c) {
+void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, 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);
 }
 
-void set_bottom(Edge* edge, Vertex* v, Edge** activeEdges, Comparator& c) {
+void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, 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);
 }
 
-void merge_edges_above(Edge* edge, Edge* other, Edge** activeEdges, Comparator& c) {
+void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, 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);
         other->fWinding += edge->fWinding;
         erase_edge_if_zero_winding(other, activeEdges);
         edge->fWinding = 0;
         erase_edge_if_zero_winding(edge, activeEdges);
     } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
         other->fWinding += edge->fWinding;
         erase_edge_if_zero_winding(other, activeEdges);
         set_bottom(edge, other->fTop, activeEdges, c);
     } else {
         edge->fWinding += other->fWinding;
         erase_edge_if_zero_winding(edge, activeEdges);
         set_bottom(other, edge->fTop, activeEdges, c);
     }
 }
 
-void merge_edges_below(Edge* edge, Edge* other, Edge** activeEdges, Comparator& c) {
+void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, 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);
         other->fWinding += edge->fWinding;
         erase_edge_if_zero_winding(other, activeEdges);
         edge->fWinding = 0;
         erase_edge_if_zero_winding(edge, activeEdges);
     } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
         edge->fWinding += other->fWinding;
         erase_edge_if_zero_winding(edge, activeEdges);
         set_top(other, edge->fBottom, activeEdges, c);
     } else {
         other->fWinding += edge->fWinding;
         erase_edge_if_zero_winding(other, activeEdges);
         set_top(edge, other->fBottom, activeEdges, c);
     }
 }
 
-void merge_collinear_edges(Edge* edge, Edge** activeEdges, Comparator& c) {
+void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c) {
     if (edge->fPrevEdgeAbove && (edge->fTop == edge->fPrevEdgeAbove->fTop ||
                                  !edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) {
         merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges, c);
     } else if (edge->fNextEdgeAbove && (edge->fTop == edge->fNextEdgeAbove->fTop ||
                                         !edge->isLeftOf(edge->fNextEdgeAbove->fTop))) {
         merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges, c);
     }
     if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom ||
                                  !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom))) {
         merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, c);
     } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->fBottom ||
                                         !edge->isLeftOf(edge->fNextEdgeBelow->fBottom))) {
         merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, c);
     }
 }
 
-void split_edge(Edge* edge, Vertex* v, Edge** activeEdges, Comparator& c, SkChunkAlloc& alloc);
+void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkChunkAlloc& alloc);
 
-void cleanup_active_edges(Edge* edge, Edge** activeEdges, Comparator& c, SkChunkAlloc& alloc) {
+void cleanup_active_edges(Edge* edge, EdgeList* activeEdges, Comparator& c, SkChunkAlloc& 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_gt(top->fPoint, leftTop->fPoint) && !edge->fLeft->isLeftOf(top)) {
             split_edge(edge->fLeft, edge->fTop, activeEdges, c, alloc);
         } else if (c.sweep_gt(leftTop->fPoint, top->fPoint) && !edge->isRightOf(leftTop)) {
             split_edge(edge, leftTop, activeEdges, c, alloc);
         } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) &&
@@ skipping 13 matching lines @@
         } 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, Edge** activeEdges, Comparator& c, SkChunkAlloc& alloc) {
+void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkChunkAlloc& 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);
     if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) {
         set_top(edge, v, activeEdges, c);
     } else if (c.sweep_gt(v->fPoint, edge->fBottom->fPoint)) {
         set_bottom(edge, v, activeEdges, c);
     } else {
         Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), alloc);
         insert_edge_below(newEdge, v, c);
@@ skipping 14 matching lines @@
         edge = next;
     }
     for (Edge* edge = src->fFirstEdgeBelow; edge;) {
         Edge* next = edge->fNextEdgeBelow;
         set_top(edge, dst, NULL, c);
         edge = next;
     }
     remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, NULL);
 }
 
-Vertex* check_for_intersection(Edge* edge, Edge* other, Edge** activeEdges, Comparator& c,
+Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c,
                                SkChunkAlloc& alloc) {
     SkPoint p;
     if (!edge || !other) {
         return NULL;
     }
     if (edge->intersect(*other, &p)) {
         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);
@@ skipping 183 matching lines @@
     if (b) {
         append_vertex_list(b, &head, &tail);
     }
     return head;
 }
 
 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges.
 
 void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) {
     LOG("simplifying complex polygons\n");
-    Edge* activeEdges = NULL;
+    EdgeList activeEdges;
     for (Vertex* v = vertices; v != NULL; v = v->fNext) {
         if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
             continue;
         }
 #if LOGGING_ENABLED
         LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
 #endif
         Edge* leftEnclosingEdge = NULL;
         Edge* rightEnclosingEdge = NULL;
         bool restartChecks;
         do {
             restartChecks = false;
-            find_enclosing_edges(v, activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
+            find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
             if (v->fFirstEdgeBelow) {
                 for (Edge* edge = v->fFirstEdgeBelow; edge != NULL; edge = edge->fNextEdgeBelow) {
                     if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, c, alloc)) {
                         restartChecks = true;
                         break;
                     }
                     if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, c, alloc)) {
                         restartChecks = true;
                         break;
                     }
@@ skipping 18 matching lines @@
             leftEdge = e;
         }
         v->fProcessed = true;
     }
 }
 
 // Stage 5: Tessellate the simplified mesh into monotone polygons.
 
 Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) {
     LOG("tessellating simple polygons\n");
-    Edge* activeEdges = NULL;
+    EdgeList activeEdges;
     Poly* polys = NULL;
     for (Vertex* v = vertices; v != NULL; v = v->fNext) {
         if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
             continue;
         }
 #if LOGGING_ENABLED
         LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
 #endif
         Edge* leftEnclosingEdge = NULL;
         Edge* rightEnclosingEdge = NULL;
-        find_enclosing_edges(v, activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
+        find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
         Poly* leftPoly = NULL;
         Poly* rightPoly = NULL;
         if (v->fFirstEdgeAbove) {
             leftPoly = v->fFirstEdgeAbove->fLeftPoly;
             rightPoly = v->fLastEdgeAbove->fRightPoly;
         } else {
             leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : NULL;
             rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : NULL;
         }
 #if LOGGING_ENABLED
@@ skipping 73 matching lines @@
                 if (winding != 0) {
                     Poly* poly = new_poly(&polys, v, winding, alloc);
                     leftEdge->fRightPoly = rightEdge->fLeftPoly = poly;
                 }
                 leftEdge = rightEdge;
             }
             v->fLastEdgeBelow->fRightPoly = rightPoly;
         }
 #if LOGGING_ENABLED
         LOG("\nactive edges:\n");
-        for (Edge* e = activeEdges; e != NULL; e = e->fRight) {
+        for (Edge* e = activeEdges->fHead; e != NULL; e = e->fRight) {
             LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
                 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1);
         }
 #endif
     }
     return polys;
 }
 
 // This is a driver function which calls stages 2-5 in turn.
 
@@ skipping 222 matching lines @@
     SkMatrix vmi;
     if (!viewM.invert(&vmi)) {
         return false;
     }
     vmi.mapRect(&clipBounds);
     SkAutoTUnref<GrBatch> batch(TessellatingPathBatch::Create(color, path, viewM, clipBounds));
     target->drawBatch(pipelineBuilder, batch);
 
     return true;
 }