Fix nearly flat edge detection in GrTriangulator
Adds a GM reproducing triangulator failure. The stroker generated
geometry shown in the GM had two edges intersecting on the inner
contour. One of the edges was practically vertical, such that its top
and bottom vertices X coordinates differed by 1ulp (approx 4.8e-7 when
x = 7.5). The intersection was computed correctly in double but then
clamped to exactly 7.5 when stored back in float at (7.5, ~11), which
is still a reasonable intersection point along the edge represented
by (7.5,0) to (7.5000048,~68).
However, with a sorting direction of horizontal for the vertices,
vertices are sorted on increasing x and then *decreasing* y. The
computed intersection is then technically above the edge's top
vertex. In the original code, the edge was not considered flat, so
it assumes that the intersection vertex is below the top vertex
and above the bottom vertex.
The issue was with the nearly_flat function only checking the difference
against machine epsilon without taking the magnitude of the vertices
into account. However, just changing nearly_flat to use ulp instead of
epsilon led to infinite recursion and asserts on a number of tests due
to inaccuracies in edge intersection tests. To address these issues,
I reworked clamp() to work on X and Y independently, which avoids the
need to check nearly_flat entirely. Additionally, edge intersection
detects when it might be inaccurate due to really large vertex coords
and recursively splits to reject false positives.
Bug: skia:12244
Change-Id: I9a92a163e8c53af799332f1f9369fccd3a9fbf31
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/432196
Commit-Queue: Michael Ludwig <michaelludwig@google.com>
Reviewed-by: Robert Phillips <robertphillips@google.com>
3 files changed