Treat cubics with absolutely or relatively small A as quadratics
This gives us more precision on smaller roots, since we typically
ignore the giant root anyway.
The problem we were seeing was a cubic formula would have actual
roots like:
x = -0.95
x = 0.95
x = 2e9
The cubic solver we have (in SkCubics.cpp *and* SkPathOpsCubic.cpp)
would return two roots like
x = -0.001
x = 2e9
due to floating point imprecision (the two small roots would get
squooshed together).
SkCubics::RootsValidT would identify the root within
range of [0, 1] to be just 0 (via some clamping), then
SkGeometry.cpp would chop the cubic at t = 0. (very far
off the correct spot).
This caused issues places that depended on that
chop being precise.
The quadratic solution in this case yielded much more accurate
roots (but did not yield the big root, which was ignored anyway)
and let the chopping happen at the right spot.
Why did this not happen with the older cubic solving formula,
which was also incorrect?
The HorizontalIntersection (and vertical) had a fallback
binary search if the returned root was not actually zero. [1]
A follow-on CL will add that fallback, but hopefully many
cases can be fixed by treating the line as a quadratic because
that is almost certainly faster than the binary search.
[1] https://github.com/google/skia/blob/46572b4d445f41943059d0e377afc6d6748cd5ca/src/pathops/SkDCubicLineIntersection.cpp#L182-L186
Change-Id: I89a2f6c6f13aedb8e686045384c52bf66cf3c263
Bug: oss-fuzz:55680, oss-fuzz:55625
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/640418
Commit-Queue: Kevin Lubick <kjlubick@google.com>
Reviewed-by: Brian Osman <brianosman@google.com>
Reviewed-by: Michael Ludwig <michaelludwig@google.com>
3 files changed