Add test cases in preparation for porting binary search cubic solution
One fix to oss-fuzz:55680 [1] was to fallback to quadratics more
aggressively. tdenniston@ noted that we might need to fallback
from quadratics to linear in a similar fashion.
See the new test case in "two roots one small one big (and ignored)"
and subsequent implementation in SkQuads.cpp.
To be even more careful, we need to verify that returned
cubic roots are valid, and if they are not, find something
that is. The previous PathOps code used a binary search
to do this.
In order to port that, I added some tests for the existing
behavior, see CubicChopTest.cpp for those.
The algorithm [2] finds the extrema (local minima and maxima)
of the polynomial and then uses those to find the intersection with
the requested horizontal (or vertical) line.
A follow-on CL will add implementations of these in src/base
which will also pass these tests.
Suggested Review order:
- CubicRootsTest.cpp and SkQuads.cpp to see fallback-to-linear
test and algorithm (and fix for a divide by zero UBSAN bug)
- SkBezierCurves.* to see new helper for evaluating a Bezier
Cubic at a given point (implementation from SkDCubic::ptAtT)
- BezierCurveTest.cpp to see new tests for EvalAt (and moved
polynomial tests from CubicChopTest.cpp)
- tests/CubicChopTest.cpp for tests of SkDCubic::FindExtrema,
SkDCubic::findInflections, and SkDCubic::searchRoots.
Notice one test case I found fails with the current
algorithm (!).
[1] https://skia-review.googlesource.com/c/skia/+/640418
[2] https://github.com/google/skia/blob/dc6cc023adbfec496e4dfdcbc38022c4079c2d0b/src/pathops/SkDCubicLineIntersection.cpp#L184-L185
Change-Id: I19945cd94e7f3f5c22d42a15a7bbc4662295d1d4
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/640678
Reviewed-by: Michael Ludwig <michaelludwig@google.com>
13 files changed