When solving the cubic line intersection directly fails, use binary search as a fallback.
The cubic line intersection math empirically works 99.99% of the time (fails 3100 out of 1B random tests) but when it fails, an intersection may be missed altogether.
The binary search is may not find a solution if the cubic line failed to find any solutions at all, but so far that case hasn't arisen.
BUG=skia:2504
TBR=reed@google.com
Author: caryclark@google.com
Review URL: https://codereview.chromium.org/266063003
git-svn-id: http://skia.googlecode.com/svn/trunk@14614 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp
index a89604f..9d70d58 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -9,9 +9,58 @@
#include "SkPathOpsLine.h"
#include "SkPathOpsQuad.h"
#include "SkPathOpsRect.h"
+#include "SkTSort.h"
const int SkDCubic::gPrecisionUnit = 256; // FIXME: test different values in test framework
+// give up when changing t no longer moves point
+// also, copy point rather than recompute it when it does change
+double SkDCubic::binarySearch(double min, double max, double axisIntercept,
+ SearchAxis xAxis) const {
+ double t = (min + max) / 2;
+ double step = (t - min) / 2;
+ SkDPoint cubicAtT = ptAtT(t);
+ double calcPos = (&cubicAtT.fX)[xAxis];
+ double calcDist = calcPos - axisIntercept;
+ do {
+ double priorT = t - step;
+ SkASSERT(priorT >= min);
+ SkDPoint lessPt = ptAtT(priorT);
+ if (approximately_equal(lessPt.fX, cubicAtT.fX)
+ && approximately_equal(lessPt.fY, cubicAtT.fY)) {
+ return -1; // binary search found no point at this axis intercept
+ }
+ double lessDist = (&lessPt.fX)[xAxis] - axisIntercept;
+#if DEBUG_CUBIC_BINARY_SEARCH
+ SkDebugf("t=%1.9g calc=%1.9g dist=%1.9g step=%1.9g less=%1.9g\n", t, calcPos, calcDist,
+ step, lessDist);
+#endif
+ double lastStep = step;
+ step /= 2;
+ if (calcDist > 0 ? calcDist > lessDist : calcDist < lessDist) {
+ t = priorT;
+ } else {
+ double nextT = t + lastStep;
+ SkASSERT(nextT <= max);
+ SkDPoint morePt = ptAtT(nextT);
+ if (approximately_equal(morePt.fX, cubicAtT.fX)
+ && approximately_equal(morePt.fY, cubicAtT.fY)) {
+ return -1; // binary search found no point at this axis intercept
+ }
+ double moreDist = (&morePt.fX)[xAxis] - axisIntercept;
+ if (calcDist > 0 ? calcDist <= moreDist : calcDist >= moreDist) {
+ continue;
+ }
+ t = nextT;
+ }
+ SkDPoint testAtT = ptAtT(t);
+ cubicAtT = testAtT;
+ calcPos = (&cubicAtT.fX)[xAxis];
+ calcDist = calcPos - axisIntercept;
+ } while (!approximately_equal(calcPos, axisIntercept));
+ return t;
+}
+
// FIXME: cache keep the bounds and/or precision with the caller?
double SkDCubic::calcPrecision() const {
SkDRect dRect;
@@ -93,6 +142,27 @@
&& between(fPts[0].fY, fPts[2].fY, fPts[3].fY);
}
+int SkDCubic::searchRoots(double extremeTs[6], int extrema, double axisIntercept,
+ SearchAxis xAxis, double* validRoots) const {
+ extrema += findInflections(&extremeTs[extrema]);
+ extremeTs[extrema++] = 0;
+ extremeTs[extrema] = 1;
+ SkTQSort(extremeTs, extremeTs + extrema);
+ int validCount = 0;
+ for (int index = 0; index < extrema; ) {
+ double min = extremeTs[index];
+ double max = extremeTs[++index];
+ if (min == max) {
+ continue;
+ }
+ double newT = binarySearch(min, max, axisIntercept, xAxis);
+ if (newT >= 0) {
+ validRoots[validCount++] = newT;
+ }
+ }
+ return validCount;
+}
+
bool SkDCubic::serpentine() const {
#if 0 // FIXME: enabling this fixes cubicOp114 but breaks cubicOp58d and cubicOp53d
double tValues[2];
@@ -210,7 +280,7 @@
}
r = A - adiv3;
*roots++ = r;
- if (AlmostDequalUlps(R2, Q3)) {
+ if (AlmostDequalUlps((double) R2, (double) Q3)) {
r = -A / 2 - adiv3;
if (!AlmostDequalUlps(s[0], r)) {
*roots++ = r;