GrTessellator: fix for collinear edge merging.

In some cases, two edges can be collinear when tested on one side
(e.g., left top vs right edge), but non-collinear when tested on the
other (e.g., right top vs left edge). We were actually merging based
on one criterion, but assserting based on the other.

The safest fix is to merge if either condition is true, and then
assert that both conditions are false.

Bug: 866319
Change-Id: Ia1be330caf62f6d7961746752f73993ca098d0a3
Reviewed-on: https://skia-review.googlesource.com/143501
Reviewed-by: Robert Phillips <robertphillips@google.com>
Commit-Queue: Stephen White <senorblanco@chromium.org>

2 files changed, 39 insertions, 14 deletions

diff --git a/src/gpu/GrTessellator.cpp b/src/gpu/GrTessellator.cpp
index 944471a076..72a3bc8bf1 100644
--- a/src/gpu/GrTessellator.cpp
+++ b/src/gpu/GrTessellator.cpp
@@ -1051,30 +1051,40 @@ void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex**
     }
 }
 
+bool top_collinear(Edge* left, Edge* right) {
+    if (!left || !right) {
+        return false;
+    }
+    return left->fTop->fPoint == right->fTop->fPoint ||
+           !left->isLeftOf(right->fTop) || !right->isRightOf(left->fTop);
+}
+
+bool bottom_collinear(Edge* left, Edge* right) {
+    if (!left || !right) {
+        return false;
+    }
+    return left->fBottom->fPoint == right->fBottom->fPoint ||
+           !left->isLeftOf(right->fBottom) || !right->isRightOf(left->fBottom);
+}
+
 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c) {
     for (;;) {
-        const SkPoint& top = edge->fTop->fPoint;
-        const SkPoint& bottom = edge->fBottom->fPoint;
-        if (edge->fPrevEdgeAbove && (edge->fPrevEdgeAbove->fTop->fPoint == top ||
-                                     !edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) {
+        if (top_collinear(edge->fPrevEdgeAbove, edge)) {
             merge_edges_above(edge->fPrevEdgeAbove, edge, activeEdges, current, c);
-        } else if (edge->fNextEdgeAbove && (edge->fNextEdgeAbove->fTop->fPoint == top ||
-                                            !edge->isLeftOf(edge->fNextEdgeAbove->fTop))) {
+        } else if (top_collinear(edge, edge->fNextEdgeAbove)) {
             merge_edges_above(edge->fNextEdgeAbove, edge, activeEdges, current, c);
-        } else if (edge->fPrevEdgeBelow && (edge->fPrevEdgeBelow->fBottom->fPoint == bottom ||
-                                     !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom))) {
+        } else if (bottom_collinear(edge->fPrevEdgeBelow, edge)) {
             merge_edges_below(edge->fPrevEdgeBelow, edge, activeEdges, current, c);
-        } else if (edge->fNextEdgeBelow && (edge->fNextEdgeBelow->fBottom->fPoint == bottom ||
-                                            !edge->isLeftOf(edge->fNextEdgeBelow->fBottom))) {
+        } else if (bottom_collinear(edge, edge->fNextEdgeBelow)) {
             merge_edges_below(edge->fNextEdgeBelow, edge, activeEdges, current, c);
         } else {
             break;
         }
     }
-    SkASSERT(!edge->fPrevEdgeAbove || edge->fPrevEdgeAbove->isLeftOf(edge->fTop));
-    SkASSERT(!edge->fPrevEdgeBelow || edge->fPrevEdgeBelow->isLeftOf(edge->fBottom));
-    SkASSERT(!edge->fNextEdgeAbove || edge->fNextEdgeAbove->isRightOf(edge->fTop));
-    SkASSERT(!edge->fNextEdgeBelow || edge->fNextEdgeBelow->isRightOf(edge->fBottom));
+    SkASSERT(!top_collinear(edge->fPrevEdgeAbove, edge));
+    SkASSERT(!top_collinear(edge, edge->fNextEdgeAbove));
+    SkASSERT(!bottom_collinear(edge->fPrevEdgeBelow, edge));
+    SkASSERT(!bottom_collinear(edge, edge->fNextEdgeBelow));
 }
 
 bool split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c,
diff --git a/tests/TessellatingPathRendererTests.cpp b/tests/TessellatingPathRendererTests.cpp
index ae20171b04..6b1f29fc80 100644
--- a/tests/TessellatingPathRendererTests.cpp
+++ b/tests/TessellatingPathRendererTests.cpp
@@ -616,6 +616,20 @@ static SkPath create_path_42() {
     return path;
 }
 
+// Reduction from crbug.com/866319. Cause is edges that are collinear when tested from
+// one side, but non-collinear when tested from the other.
+static SkPath create_path_43() {
+    SkPath path;
+    path.moveTo(     307316821852160,      -28808363114496);
+    path.lineTo(     307165222928384,      -28794154909696);
+    path.lineTo(     307013691113472,      -28779948802048);
+    path.lineTo(     306862159298560,      -28765744791552);
+    path.lineTo(     306870313025536,      -28766508154880);
+    path.lineTo(     307049695019008,      -28783327313920);
+    path.lineTo(     307408660332544,      -28816974020608);
+    return path;
+}
+
 static std::unique_ptr<GrFragmentProcessor> create_linear_gradient_processor(GrContext* ctx) {
 
     SkPoint pts[2] = { {0, 0}, {1, 1} };
@@ -718,4 +732,5 @@ DEF_GPUTEST_FOR_ALL_CONTEXTS(TessellatingPathRendererTests, reporter, ctxInfo) {
     test_path(ctx, rtc.get(), create_path_40());
     test_path(ctx, rtc.get(), create_path_41(), SkMatrix(), GrAAType::kCoverage);
     test_path(ctx, rtc.get(), create_path_42());
+    test_path(ctx, rtc.get(), create_path_43(), SkMatrix(), GrAAType::kCoverage);
 }