Change tessellator sweep direction to depend on path aspect ratio.

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 49 matching lines @@
  * Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it
  * currently uses a linked list for the active edge list, rather than a 2-3 tree as the
  * paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and removal also
  * become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N)
  * insertions and removals was greater than the cost of infrequent O(N) lookups with the
  * linked list implementation. With the latter, all removals are O(1), and most insertions
  * are O(1), since we know the adjacent edge in the active edge list based on the topology.
  * Only type 2 vertices (see paper) require the O(N) lookups, and these are much less
  * frequent. There may be other data structures worth investigating, however.
  *
- * Note that there is a compile-time flag (SWEEP_IN_X) which changes the orientation of the
- * line sweep algorithms. When SWEEP_IN_X is unset, we sort vertices based on increasing
- * Y coordinate, and secondarily by increasing X coordinate. When SWEEP_IN_X is set, we sort by
- * increasing X coordinate, but secondarily by *decreasing* Y coordinate. This is so that the
- * "left" and "right" orientation in the code remains correct (edges to the left are increasing
- * in Y; edges to the right are decreasing in Y). That is, the setting rotates 90 degrees
- * counterclockwise, rather that transposing.
- *
- * The choice is arbitrary, but most test cases are wider than they are tall, so the
- * default is to sweep in X. In the future, we may want to make this a runtime parameter
- * and base it on the aspect ratio of the clip bounds.
+ * Note that the orientation of the line sweep algorithms is determined by the aspect ratio of the
+ * path bounds. When the path is taller than it is wide, we sort vertices based on increasing Y
+ * coordinate, and secondarily by increasing X coordinate. When the path is wider than it is tall,
+ * we sort by increasing X coordinate, but secondarily by *decreasing* Y coordinate. This is so
+ * that the "left" and "right" orientation in the code remains correct (edges to the left are
+ * increasing in Y; edges to the right are decreasing in Y). That is, the setting rotates 90
+ * degrees counterclockwise, rather that transposing.
  */
 #define LOGGING_ENABLED 0
 #define WIREFRAME 0
-#define SWEEP_IN_X 1
 
 #if LOGGING_ENABLED
 #define LOG printf
 #else
 #define LOG(...)
 #endif
 
 #define ALLOC_NEW(Type, args, alloc) \
     SkNEW_PLACEMENT_ARGS(alloc.allocThrow(sizeof(Type)), Type, args)
 
@@ skipping 63 matching lines @@
     Edge*   fFirstEdgeBelow;  // Linked list of edges below this vertex.
     Edge*   fLastEdgeBelow;   // "
     bool    fProcessed;       // Has this vertex been seen in simplify()?
 #if LOGGING_ENABLED
     float   fID;              // Identifier used for logging.
 #endif
 };
 
 /***************************************************************************************/
 
-bool sweep_lt(const SkPoint& a, const SkPoint& b) {
-#if SWEEP_IN_X
+typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b);
+
+struct Comparator {
+    CompareFunc sweep_lt;
+    CompareFunc sweep_gt;
+};
+
+bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) {
     return a.fX == b.fX ? a.fY > b.fY : a.fX < b.fX;
-#else
-    return a.fY == b.fY ? a.fX < b.fX : a.fY < b.fY;
-#endif
 }
 
-bool sweep_gt(const SkPoint& a, const SkPoint& b) {
-#if SWEEP_IN_X
+bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) {
+    return a.fY == b.fY ? a.fX < b.fX : a.fY < b.fY;
+}
+
+bool sweep_gt_horiz(const SkPoint& a, const SkPoint& b) {
     return a.fX == b.fX ? a.fY < b.fY : a.fX > b.fX;
-#else
+}
+
+bool sweep_gt_vert(const SkPoint& a, const SkPoint& b) {
     return a.fY == b.fY ? a.fX > b.fX : a.fY > b.fY;
-#endif
 }
 
 inline void* emit_vertex(Vertex* v, void* data) {
     SkPoint* d = static_cast<SkPoint*>(data);
     *d++ = v->fPoint;
     return d;
 }
 
 void* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, void* data) {
 #if WIREFRAME
@@ skipping 426 matching lines @@
         case SkPath::kInverseWinding_FillType:
             return winding == 1;
         case SkPath::kInverseEvenOdd_FillType:
             return (winding & 1) == 1;
         default:
             SkASSERT(false);
             return false;
     }
 }
 
-Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc) {
-    int winding = sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
+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) {
     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);
 }
@@ skipping 17 matching lines @@
         if (next->isRightOf(v)) {
             break;
         }
         prev = next;
     }
     *left = prev;
     *right = next;
     return;
 }
 
-void find_enclosing_edges(Edge* edge, Edge* head, Edge** left, Edge** right) {
+void find_enclosing_edges(Edge* edge, Edge* head, Comparator& c, Edge** left, Edge** right) {
     Edge* prev = NULL;
     Edge* next;
     for (next = head; next != NULL; next = next->fRight) {
-        if ((sweep_gt(edge->fTop->fPoint, next->fTop->fPoint) && next->isRightOf(edge->fTop)) ||
-            (sweep_gt(next->fTop->fPoint, edge->fTop->fPoint) && edge->isLeftOf(next->fTop)) ||
-            (sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) &&
+        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)) ||
-            (sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) &&
+            (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) {
+void fix_active_state(Edge* edge, Edge** 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, &left, &right);
+        find_enclosing_edges(edge, *activeEdges, c, &left, &right);
         insert_edge(edge, left, activeEdges);
     }
 }
 
-void insert_edge_above(Edge* edge, Vertex* v) {
+void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) {
     if (edge->fTop->fPoint == edge->fBottom->fPoint ||
-        sweep_gt(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);
     Edge* prev = NULL;
     Edge* next;
     for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) {
         if (next->isRightOf(edge->fTop)) {
             break;
         }
         prev = next;
     }
     insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
         edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);
 }
 
-void insert_edge_below(Edge* edge, Vertex* v) {
+void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) {
     if (edge->fTop->fPoint == edge->fBottom->fPoint ||
-        sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {
+        c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {
         return;
     }
     LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
     Edge* prev = NULL;
     Edge* next;
     for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) {
         if (next->isRightOf(edge->fBottom)) {
             break;
         }
         prev = next;
@@ skipping 21 matching lines @@
         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);
     }
 }
 
-void merge_collinear_edges(Edge* edge, Edge** activeEdges);
+void merge_collinear_edges(Edge* edge, Edge** activeEdges, Comparator& c);
 
-void set_top(Edge* edge, Vertex* v, Edge** activeEdges) {
+void set_top(Edge* edge, Vertex* v, Edge** activeEdges, Comparator& c) {
     remove_edge_below(edge);
     edge->fTop = v;
     edge->recompute();
-    insert_edge_below(edge, v);
-    fix_active_state(edge, activeEdges);
-    merge_collinear_edges(edge, activeEdges);
+    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) {
+void set_bottom(Edge* edge, Vertex* v, Edge** activeEdges, Comparator& c) {
     remove_edge_above(edge);
     edge->fBottom = v;
     edge->recompute();
-    insert_edge_above(edge, v);
-    fix_active_state(edge, activeEdges);
-    merge_collinear_edges(edge, activeEdges);
+    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) {
+void merge_edges_above(Edge* edge, Edge* other, Edge** 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 (sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
+    } 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);
+        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);
+        set_bottom(other, edge->fTop, activeEdges, c);
     }
 }
 
-void merge_edges_below(Edge* edge, Edge* other, Edge** activeEdges) {
+void merge_edges_below(Edge* edge, Edge* other, Edge** 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 (sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
+    } 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);
+        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);
+        set_top(edge, other->fBottom, activeEdges, c);
     }
 }
 
-void merge_collinear_edges(Edge* edge, Edge** activeEdges) {
+void merge_collinear_edges(Edge* edge, Edge** activeEdges, Comparator& c) {
     if (edge->fPrevEdgeAbove && (edge->fTop == edge->fPrevEdgeAbove->fTop ||
                                  !edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) {
-        merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges);
+        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);
+        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);
+        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);
+        merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, c);
     }
 }
 
-void split_edge(Edge* edge, Vertex* v, Edge** activeEdges, SkChunkAlloc& alloc);
+void split_edge(Edge* edge, Vertex* v, Edge** activeEdges, Comparator& c, SkChunkAlloc& alloc);
 
-void cleanup_active_edges(Edge* edge, Edge** activeEdges, SkChunkAlloc& alloc) {
+void cleanup_active_edges(Edge* edge, Edge** 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 (sweep_gt(top->fPoint, leftTop->fPoint) && !edge->fLeft->isLeftOf(top)) {
-            split_edge(edge->fLeft, edge->fTop, activeEdges, alloc);
-        } else if (sweep_gt(leftTop->fPoint, top->fPoint) && !edge->isRightOf(leftTop)) {
-            split_edge(edge, leftTop, activeEdges, alloc);
-        } else if (sweep_lt(bottom->fPoint, leftBottom->fPoint) && !edge->fLeft->isLeftOf(bottom)) {
-            split_edge(edge->fLeft, bottom, activeEdges, alloc);
-        } else if (sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) {
-            split_edge(edge, leftBottom, activeEdges, alloc);
+        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) &&
+                   !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 (sweep_gt(top->fPoint, rightTop->fPoint) && !edge->fRight->isRightOf(top)) {
-            split_edge(edge->fRight, top, activeEdges, alloc);
-        } else if (sweep_gt(rightTop->fPoint, top->fPoint) && !edge->isLeftOf(rightTop)) {
-            split_edge(edge, rightTop, activeEdges, alloc);
-        } else if (sweep_lt(bottom->fPoint, rightBottom->fPoint) &&
+        if (c.sweep_gt(top->fPoint, rightTop->fPoint) && !edge->fRight->isRightOf(top)) {
+            split_edge(edge->fRight, top, activeEdges, c, alloc);
+        } else if (c.sweep_gt(rightTop->fPoint, top->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, alloc);
-        } else if (sweep_lt(rightBottom->fPoint, bottom->fPoint) &&
+            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, alloc);
+            split_edge(edge, rightBottom, activeEdges, c, alloc);
         }
     }
 }
 
-void split_edge(Edge* edge, Vertex* v, Edge** activeEdges, SkChunkAlloc& alloc) {
+void split_edge(Edge* edge, Vertex* v, Edge** 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 (sweep_lt(v->fPoint, edge->fTop->fPoint)) {
-        set_top(edge, v, activeEdges);
-    } else if (sweep_gt(v->fPoint, edge->fBottom->fPoint)) {
-        set_bottom(edge, v, activeEdges);
+    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);
-        insert_edge_above(newEdge, edge->fBottom);
-        set_bottom(edge, v, activeEdges);
-        cleanup_active_edges(edge, activeEdges, alloc);
-        fix_active_state(newEdge, activeEdges);
-        merge_collinear_edges(newEdge, activeEdges);
+        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);
     }
 }
 
-void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, SkChunkAlloc& alloc) {
+void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, Comparator& c, SkChunkAlloc& alloc) {
     LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX, src->fPoint.fY,
         src->fID, dst->fID);
     for (Edge* edge = src->fFirstEdgeAbove; edge;) {
         Edge* next = edge->fNextEdgeAbove;
-        set_bottom(edge, dst, NULL);
+        set_bottom(edge, dst, NULL, c);
         edge = next;
     }
     for (Edge* edge = src->fFirstEdgeBelow; edge;) {
         Edge* next = edge->fNextEdgeBelow;
-        set_top(edge, dst, NULL);
+        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, SkChunkAlloc& alloc) {
+Vertex* check_for_intersection(Edge* edge, Edge* other, Edge** 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 || sweep_lt(p, edge->fTop->fPoint)) {
-            split_edge(other, edge->fTop, activeEdges, alloc);
+        if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) {
+            split_edge(other, edge->fTop, activeEdges, c, alloc);
             v = edge->fTop;
-        } else if (p == edge->fBottom->fPoint || sweep_gt(p, edge->fBottom->fPoint)) {
-            split_edge(other, edge->fBottom, activeEdges, alloc);
+        } else if (p == edge->fBottom->fPoint || c.sweep_gt(p, edge->fBottom->fPoint)) {
+            split_edge(other, edge->fBottom, activeEdges, c, alloc);
             v = edge->fBottom;
-        } else if (p == other->fTop->fPoint || sweep_lt(p, other->fTop->fPoint)) {
-            split_edge(edge, other->fTop, activeEdges, alloc);
+        } else if (p == other->fTop->fPoint || c.sweep_lt(p, other->fTop->fPoint)) {
+            split_edge(edge, other->fTop, activeEdges, c, alloc);
             v = other->fTop;
-        } else if (p == other->fBottom->fPoint || sweep_gt(p, other->fBottom->fPoint)) {
-            split_edge(edge, other->fBottom, activeEdges, alloc);
+        } else if (p == other->fBottom->fPoint || c.sweep_gt(p, other->fBottom->fPoint)) {
+            split_edge(edge, other->fBottom, activeEdges, c, alloc);
             v = other->fBottom;
         } else {
             Vertex* nextV = edge->fTop;
-            while (sweep_lt(p, nextV->fPoint)) {
+            while (c.sweep_lt(p, nextV->fPoint)) {
                 nextV = nextV->fPrev;
             }
-            while (sweep_lt(nextV->fPoint, p)) {
+            while (c.sweep_lt(nextV->fPoint, p)) {
                 nextV = nextV->fNext;
             }
             Vertex* prevV = nextV->fPrev;
             if (coincident(prevV->fPoint, p)) {
                 v = prevV;
             } else if (coincident(nextV->fPoint, p)) {
                 v = nextV;
             } else {
                 v = ALLOC_NEW(Vertex, (p), alloc);
                 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;
 #endif
                 v->fPrev = prevV;
                 v->fNext = nextV;
                 prevV->fNext = v;
                 nextV->fPrev = v;
             }
-            split_edge(edge, v, activeEdges, alloc);
-            split_edge(other, v, activeEdges, alloc);
+            split_edge(edge, v, activeEdges, c, alloc);
+            split_edge(other, v, activeEdges, c, alloc);
         }
         return v;
     }
     return NULL;
 }
 
 void sanitize_contours(Vertex** contours, int contourCnt) {
     for (int i = 0; i < contourCnt; ++i) {
         SkASSERT(contours[i]);
         for (Vertex* v = contours[i];;) {
@@ skipping 10 matching lines @@
                 }
                 v = v->fPrev;
             } else {
                 v = v->fNext;
                 if (v == contours[i]) break;
             }
         }
     }
 }
 
-void merge_coincident_vertices(Vertex** vertices, SkChunkAlloc& alloc) {
+void merge_coincident_vertices(Vertex** vertices, Comparator& c, SkChunkAlloc& alloc) {
     for (Vertex* v = (*vertices)->fNext; v != NULL; v = v->fNext) {
-        if (sweep_lt(v->fPoint, v->fPrev->fPoint)) {
+        if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) {
             v->fPoint = v->fPrev->fPoint;
         }
         if (coincident(v->fPrev->fPoint, v->fPoint)) {
-            merge_vertices(v->fPrev, v, vertices, alloc);
+            merge_vertices(v->fPrev, v, vertices, c, alloc);
         }
     }
 }
 
 // Stage 2: convert the contours to a mesh of edges connecting the vertices.
 
-Vertex* build_edges(Vertex** contours, int contourCnt, SkChunkAlloc& alloc) {
+Vertex* build_edges(Vertex** contours, int contourCnt, Comparator& c, SkChunkAlloc& alloc) {
     Vertex* vertices = NULL;
     Vertex* prev = NULL;
     for (int i = 0; i < contourCnt; ++i) {
         for (Vertex* v = contours[i]; v != NULL;) {
             Vertex* vNext = v->fNext;
-            Edge* edge = new_edge(v->fPrev, v, alloc);
+            Edge* edge = new_edge(v->fPrev, v, alloc, c);
             if (edge->fWinding > 0) {
-                insert_edge_below(edge, v->fPrev);
-                insert_edge_above(edge, v);
+                insert_edge_below(edge, v->fPrev, c);
+                insert_edge_above(edge, v, c);
             } else {
-                insert_edge_below(edge, v);
-                insert_edge_above(edge, v->fPrev);
+                insert_edge_below(edge, v, c);
+                insert_edge_above(edge, v->fPrev, c);
             }
-            merge_collinear_edges(edge, NULL);
+            merge_collinear_edges(edge, NULL, c);
             if (prev) {
                 prev->fNext = v;
                 v->fPrev = prev;
             } else {
                 vertices = v;
             }
             prev = v;
             v = vNext;
             if (v == contours[i]) break;
         }
     }
     if (prev) {
         prev->fNext = vertices->fPrev = NULL;
     }
     return vertices;
 }
 
-// Stage 3: sort the vertices by increasing Y (or X if SWEEP_IN_X is on).
+// Stage 3: sort the vertices by increasing sweep direction.
 
-Vertex* sorted_merge(Vertex* a, Vertex* b);
+Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c);
 
 void front_back_split(Vertex* v, Vertex** pFront, Vertex** pBack) {
     Vertex* fast;
     Vertex* slow;
     if (!v || !v->fNext) {
         *pFront = v;
         *pBack = NULL;
     } else {
         slow = v;
         fast = v->fNext;
 
         while (fast != NULL) {
             fast = fast->fNext;
             if (fast != NULL) {
                 slow = slow->fNext;
                 fast = fast->fNext;
             }
         }
 
         *pFront = v;
         *pBack = slow->fNext;
         slow->fNext->fPrev = NULL;
         slow->fNext = NULL;
     }
 }
 
-void merge_sort(Vertex** head) {
+void merge_sort(Vertex** head, Comparator& c) {
     if (!*head || !(*head)->fNext) {
         return;
     }
 
     Vertex* a;
     Vertex* b;
     front_back_split(*head, &a, &b);
 
-    merge_sort(&a);
-    merge_sort(&b);
+    merge_sort(&a, c);
+    merge_sort(&b, c);
 
-    *head = sorted_merge(a, b);
+    *head = sorted_merge(a, b, c);
 }
 
 inline void append_vertex(Vertex* v, Vertex** head, Vertex** tail) {
     insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, NULL, head, tail);
 }
 
 inline void append_vertex_list(Vertex* v, Vertex** head, Vertex** tail) {
     insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, v->fNext, head, tail);
 }
 
-Vertex* sorted_merge(Vertex* a, Vertex* b) {
+Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c) {
     Vertex* head = NULL;
     Vertex* tail = NULL;
 
     while (a && b) {
-        if (sweep_lt(a->fPoint, b->fPoint)) {
+        if (c.sweep_lt(a->fPoint, b->fPoint)) {
             Vertex* next = a->fNext;
             append_vertex(a, &head, &tail);
             a = next;
         } else {
             Vertex* next = b->fNext;
             append_vertex(b, &head, &tail);
             b = next;
         }
     }
     if (a) {
         append_vertex_list(a, &head, &tail);
     }
     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, SkChunkAlloc& alloc) {
+void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) {
     LOG("simplifying complex polygons\n");
     Edge* activeEdges = 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;
         bool restartChecks;
         do {
             restartChecks = false;
             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, alloc)) {
+                    if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, c, alloc)) {
                         restartChecks = true;
                         break;
                     }
-                    if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, alloc)) {
+                    if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, c, alloc)) {
                         restartChecks = true;
                         break;
                     }
                 }
             } else {
                 if (Vertex* pv = check_for_intersection(leftEnclosingEdge, rightEnclosingEdge,
-                                                        &activeEdges, alloc)) {
-                    if (sweep_lt(pv->fPoint, v->fPoint)) {
+                                                        &activeEdges, c, alloc)) {
+                    if (c.sweep_lt(pv->fPoint, v->fPoint)) {
                         v = pv;
                     }
                     restartChecks = true;
                 }
 
             }
         } while (restartChecks);
         for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
             remove_edge(e, &activeEdges);
         }
@@ skipping 119 matching lines @@
             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.
 
-Poly* contours_to_polys(Vertex** contours, int contourCnt, SkChunkAlloc& alloc) {
+Poly* contours_to_polys(Vertex** contours, int contourCnt, Comparator& c, SkChunkAlloc& alloc) {
 #if LOGGING_ENABLED
     for (int i = 0; i < contourCnt; ++i) {
         Vertex* v = contours[i];
         SkASSERT(v);
         LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
         for (v = v->fNext; v != contours[i]; v = v->fNext) {
             LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
         }
     }
 #endif
     sanitize_contours(contours, contourCnt);
-    Vertex* vertices = build_edges(contours, contourCnt, alloc);
+    Vertex* vertices = build_edges(contours, contourCnt, c, alloc);
     if (!vertices) {
         return NULL;
     }
 
     // Sort vertices in Y (secondarily in X).
-    merge_sort(&vertices);
-    merge_coincident_vertices(&vertices, alloc);
+    merge_sort(&vertices, c);
+    merge_coincident_vertices(&vertices, c, alloc);
 #if LOGGING_ENABLED
     for (Vertex* v = vertices; v != NULL; v = v->fNext) {
         static float gID = 0.0f;
         v->fID = gID++;
     }
 #endif
-    simplify(vertices, alloc);
+    simplify(vertices, c, alloc);
     return tessellate(vertices, alloc);
 }
 
 // Stage 6: Triangulate the monotone polygons into a vertex buffer.
 
 void* polys_to_triangles(Poly* polys, SkPath::FillType fillType, void* data) {
     void* d = data;
     for (Poly* poly = polys; poly; poly = poly->fNext) {
         if (apply_fill_type(fillType, poly->fWinding)) {
             d = poly->emit(d);
@@ skipping 50 matching lines @@
         // Handle any color overrides
         if (init.fColorIgnored) {
             fColor = GrColor_ILLEGAL;
         } else if (GrColor_ILLEGAL != init.fOverrideColor) {
             fColor = init.fOverrideColor;
         }
         fPipelineInfo = init;
     }
 
     void generateGeometry(GrBatchTarget* batchTarget, const GrPipeline* pipeline) override {
-        SkScalar tol = GrPathUtils::scaleToleranceToSrc(SK_Scalar1, fViewMatrix, fPath.getBounds());
+        SkRect pathBounds = fPath.getBounds();
+        Comparator c;
+        if (pathBounds.width() > pathBounds.height()) {
+            c.sweep_lt = sweep_lt_horiz;
+            c.sweep_gt = sweep_gt_horiz;
+        } else {
+            c.sweep_lt = sweep_lt_vert;
+            c.sweep_gt = sweep_gt_vert;
+        }
+        SkScalar tol = GrPathUtils::scaleToleranceToSrc(SK_Scalar1, fViewMatrix, pathBounds);
         int contourCnt;
         int maxPts = GrPathUtils::worstCasePointCount(fPath, &contourCnt, tol);
         if (maxPts <= 0) {
             return;
         }
         if (maxPts > ((int)SK_MaxU16 + 1)) {
             SkDebugf("Path not rendered, too many verts (%d)\n", maxPts);
             return;
         }
         SkPath::FillType fillType = fPath.getFillType();
@@ skipping 10 matching lines @@
 
         SkAutoTDeleteArray<Vertex*> contours(SkNEW_ARRAY(Vertex *, contourCnt));
 
         // For the initial size of the chunk allocator, estimate based on the point count:
         // one vertex per point for the initial passes, plus two for the vertices in the
         // resulting Polys, since the same point may end up in two Polys.  Assume minimal
         // connectivity of one Edge per Vertex (will grow for intersections).
         SkChunkAlloc alloc(maxPts * (3 * sizeof(Vertex) + sizeof(Edge)));
         path_to_contours(fPath, tol, fClipBounds, contours.get(), alloc);
         Poly* polys;
-        polys = contours_to_polys(contours.get(), contourCnt, alloc);
+        polys = contours_to_polys(contours.get(), contourCnt, c, alloc);
         int count = 0;
         for (Poly* poly = polys; poly; poly = poly->fNext) {
             if (apply_fill_type(fillType, poly->fWinding) && poly->fCount >= 3) {
                 count += (poly->fCount - 2) * (WIREFRAME ? 6 : 3);
             }
         }
         if (0 == count) {
             return;
         }
 
@@ skipping 74 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;
 }