diff options
author | 2018-05-29 11:50:41 -0400 | |
---|---|---|
committer | 2018-05-29 17:10:16 +0000 | |
commit | bfb2a05af105f452a0f369e39dae05f9224dfa19 (patch) | |
tree | 9e78935c2c58d962eb473fef5aa1ddbd47c48071 /src | |
parent | 36be574e7bd5eb8bb41e2a0a15085e27b340cf4d (diff) |
GrTessellator: fix for ping-pong split fuzzer hang.
Change 3b5a3fa8b1c11d4bd4499b040311f4c3553ebf8c introduced support for
splitting on out-of-range intersections. However, this is only necessary
for correctness when the edge is nearly-flat (the top and bottom
points only differ by 1/2 machine epsilon in the primary sort criterion).
In other cases, it can cause repeated splitting and re-merging of edges,
as the intersection code (being approximate and not exact) may produce a
ping-pong set of intersections.
The fix is to support out-of-range intersections only if they differ by
1/2 machine epsilon. This also generalizes the
out_of_range_and_collinear() check, so it was removed.
Bug: 838978
Change-Id: I134f7eff3f15707e0d68de11c55f7fadce4ff8e7
Reviewed-on: https://skia-review.googlesource.com/130448
Reviewed-by: Robert Phillips <robertphillips@google.com>
Commit-Queue: Stephen White <senorblanco@chromium.org>
Diffstat (limited to 'src')
-rw-r--r-- | src/gpu/GrTessellator.cpp | 43 |
1 files changed, 20 insertions, 23 deletions
diff --git a/src/gpu/GrTessellator.cpp b/src/gpu/GrTessellator.cpp index 4d3c1eb0ee..d69833df2e 100644 --- a/src/gpu/GrTessellator.cpp +++ b/src/gpu/GrTessellator.cpp @@ -1131,17 +1131,6 @@ void merge_vertices(Vertex* src, Vertex* dst, VertexList* mesh, Comparator& c, mesh->remove(src); } -bool out_of_range_and_collinear(const SkPoint& p, Edge* edge, Comparator& c) { - if (c.sweep_lt(p, edge->fTop->fPoint) && - !Line(p, edge->fBottom->fPoint).dist(edge->fTop->fPoint)) { - return true; - } else if (c.sweep_lt(edge->fBottom->fPoint, p) && - !Line(edge->fTop->fPoint, p).dist(edge->fBottom->fPoint)) { - return true; - } - return false; -} - Vertex* create_sorted_vertex(const SkPoint& p, uint8_t alpha, VertexList* mesh, Vertex* reference, Comparator& c, SkArenaAlloc& alloc) { Vertex* prevV = reference; @@ -1174,6 +1163,12 @@ Vertex* create_sorted_vertex(const SkPoint& p, uint8_t alpha, VertexList* mesh, return v; } +bool nearly_flat(Comparator& c, Edge* edge) { + SkPoint diff = edge->fBottom->fPoint - edge->fTop->fPoint; + float primaryDiff = c.fDirection == Comparator::Direction::kHorizontal ? diff.fX : diff.fY; + return fabs(primaryDiff) < std::numeric_limits<float>::epsilon(); +} + bool check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current, VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) { if (!edge || !other) { @@ -1182,13 +1177,7 @@ bool check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Vert SkPoint p; uint8_t alpha; if (edge->intersect(*other, &p, &alpha) && p.isFinite()) { - // Ignore any out-of-range intersections which are also collinear, - // since the resulting edges would cancel each other out by merging. - if (out_of_range_and_collinear(p, edge, c) || - out_of_range_and_collinear(p, other, c)) { - return false; - } - Vertex* v; + Vertex* v = nullptr; LOG("found intersection, pt is %g, %g\n", p.fX, p.fY); Vertex* top = *current; // If the intersection point is above the current vertex, rewind to the vertex above the @@ -1196,15 +1185,23 @@ bool check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Vert while (top && c.sweep_lt(p, top->fPoint)) { top = top->fPrev; } - if (p == edge->fTop->fPoint) { + if (p == edge->fTop->fPoint || + (c.sweep_lt(p, edge->fTop->fPoint) && !nearly_flat(c, edge))) { v = edge->fTop; - } else if (p == edge->fBottom->fPoint) { + } + if (p == edge->fBottom->fPoint || + (c.sweep_lt(edge->fBottom->fPoint, p) && !nearly_flat(c, edge))) { v = edge->fBottom; - } else if (p == other->fTop->fPoint) { + } + if (p == other->fTop->fPoint || + (c.sweep_lt(p, other->fTop->fPoint) && !nearly_flat(c, other))) { v = other->fTop; - } else if (p == other->fBottom->fPoint) { + } + if (p == other->fBottom->fPoint || + (c.sweep_lt(other->fBottom->fPoint, p) && !nearly_flat(c, other))) { v = other->fBottom; - } else { + } + if (!v) { v = create_sorted_vertex(p, alpha, mesh, top, c, alloc); if (edge->fTop->fPartner) { Line line1 = edge->fLine; |