diff options
author | Stephen White <senorblanco@chromium.org> | 2018-06-08 12:18:22 -0400 |
---|---|---|
committer | Skia Commit-Bot <skia-commit-bot@chromium.org> | 2018-06-08 18:26:05 +0000 |
commit | 89042d5f13a56d6b663657aa58f17593123a344e (patch) | |
tree | d8f7d2c1fc042601a1bbac9f37fe90fcf0c8e3a7 | |
parent | 894e346fcca2aca83299ab2c9558b33bd2661ed8 (diff) |
GrTessellator: catch missing intersections.
Sometimes the intersection check will miss an intersection (because
floating point). This can leave the active edge list in an invalid
state, where an edge pair is incorrectly ordered. The fix is to test
for edge crossings after testing for intersections, and split the
edges manually. This extra check may result in a performance hit, so
we'll have to watch the perf bots carefully.
Bug: 843135
Change-Id: If50320413026be503cdb2d33e6c97f620e4d51a9
Reviewed-on: https://skia-review.googlesource.com/133400
Reviewed-by: Robert Phillips <robertphillips@google.com>
Commit-Queue: Stephen White <senorblanco@chromium.org>
-rw-r--r-- | src/gpu/GrTessellator.cpp | 72 | ||||
-rw-r--r-- | tests/TessellatingPathRendererTests.cpp | 12 |
2 files changed, 80 insertions, 4 deletions
diff --git a/src/gpu/GrTessellator.cpp b/src/gpu/GrTessellator.cpp index 9369d70c30..449d00841f 100644 --- a/src/gpu/GrTessellator.cpp +++ b/src/gpu/GrTessellator.cpp @@ -1074,10 +1074,10 @@ void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, SkASSERT(!edge->fNextEdgeBelow || edge->fNextEdgeBelow->isRightOf(edge->fBottom)); } -void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c, +bool split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c, SkArenaAlloc& alloc) { if (!edge->fTop || !edge->fBottom || v == edge->fTop || v == edge->fBottom) { - return; + return false; } LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n", edge->fTop->fID, edge->fBottom->fID, @@ -1102,6 +1102,32 @@ void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, insert_edge_below(newEdge, top, c); insert_edge_above(newEdge, bottom, c); merge_collinear_edges(newEdge, activeEdges, current, c); + return true; +} + +bool intersect_edge_pair(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current, Comparator& c, SkArenaAlloc& alloc) { + if (!left->fTop || !left->fBottom || !right->fTop || !right->fBottom) { + return false; + } + if (c.sweep_lt(left->fTop->fPoint, right->fTop->fPoint)) { + if (!left->isLeftOf(right->fTop)) { + return split_edge(left, right->fTop, activeEdges, current, c, alloc); + } + } else { + if (!right->isRightOf(left->fTop)) { + return split_edge(right, left->fTop, activeEdges, current, c, alloc); + } + } + if (c.sweep_lt(right->fBottom->fPoint, left->fBottom->fPoint)) { + if (!left->isLeftOf(right->fBottom)) { + return split_edge(left, right->fBottom, activeEdges, current, c, alloc); + } + } else { + if (!right->isRightOf(left->fBottom)) { + return split_edge(right, left->fBottom, activeEdges, current, c, alloc); + } + } + return false; } Edge* connect(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkArenaAlloc& alloc, @@ -1237,7 +1263,7 @@ bool check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Vert v->fAlpha = SkTMax(v->fAlpha, alpha); return true; } - return false; + return intersect_edge_pair(edge, other, activeEdges, current, c, alloc); } void sanitize_contours(VertexList* contours, int contourCnt, bool approximate) { @@ -1400,6 +1426,41 @@ void dump_mesh(const VertexList& mesh) { #endif } +#ifdef SK_DEBUG +void validate_edge_pair(Edge* left, Edge* right, Comparator& c) { + if (!left || !right) { + return; + } + if (left->fTop == right->fTop) { + SkASSERT(left->isLeftOf(right->fBottom)); + SkASSERT(right->isRightOf(left->fBottom)); + } else if (c.sweep_lt(left->fTop->fPoint, right->fTop->fPoint)) { + SkASSERT(left->isLeftOf(right->fTop)); + } else { + SkASSERT(right->isRightOf(left->fTop)); + } + if (left->fBottom == right->fBottom) { + SkASSERT(left->isLeftOf(right->fTop)); + SkASSERT(right->isRightOf(left->fTop)); + } else if (c.sweep_lt(right->fBottom->fPoint, left->fBottom->fPoint)) { + SkASSERT(left->isLeftOf(right->fBottom)); + } else { + SkASSERT(right->isRightOf(left->fBottom)); + } +} + +void validate_edge_list(EdgeList* edges, Comparator& c) { + Edge* left = edges->fHead; + if (!left) { + return; + } + for (Edge* right = left->fRight; right; right = right->fRight) { + validate_edge_pair(left, right, c); + left = right; + } +} +#endif + // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges. bool simplify(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) { @@ -1421,7 +1482,7 @@ bool simplify(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) { v->fRightEnclosingEdge = rightEnclosingEdge; if (v->fFirstEdgeBelow) { for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) { - if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, &v, mesh, c, + if (check_for_intersection(leftEnclosingEdge, edge, &activeEdges, &v, mesh, c, alloc)) { restartChecks = true; break; @@ -1441,6 +1502,9 @@ bool simplify(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) { } found = found || restartChecks; } while (restartChecks); +#ifdef SK_DEBUG + validate_edge_list(&activeEdges, c); +#endif for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { remove_edge(e, &activeEdges); } diff --git a/tests/TessellatingPathRendererTests.cpp b/tests/TessellatingPathRendererTests.cpp index 6ab76b0d88..6f2d8963dc 100644 --- a/tests/TessellatingPathRendererTests.cpp +++ b/tests/TessellatingPathRendererTests.cpp @@ -535,6 +535,17 @@ static SkPath create_path_36() { return path; } +// Reduction from crbug.com/843135. Exercises a case where an intersection is missed. +// This causes bad ordering in the active edge list. +static SkPath create_path_37() { + SkPath path; + path.moveTo(-1.0662557646016024569e+23, 9.9621425197286319718e+22); + path.lineTo( -121806400, 113805032); + path.lineTo( -120098872, 112209680); + path.lineTo( 6.2832999862817380468e-36, 2.9885697364807128906); + return path; +} + static std::unique_ptr<GrFragmentProcessor> create_linear_gradient_processor(GrContext* ctx) { SkPoint pts[2] = { {0, 0}, {1, 1} }; @@ -631,4 +642,5 @@ DEF_GPUTEST_FOR_ALL_CONTEXTS(TessellatingPathRendererTests, reporter, ctxInfo) { test_path(ctx, rtc.get(), create_path_34()); test_path(ctx, rtc.get(), create_path_35()); test_path(ctx, rtc.get(), create_path_36()); + test_path(ctx, rtc.get(), create_path_37()); } |