Remove tolerance form SkClassifyCubic
It's too inexact as-is. If the caller wants tolerance they can do
their own with knowledge of the pixel grid. The homogeneous math
is stable with infinities so it's really unnecessary here.
Bug: skia:7073
Change-Id: I4dc34ad96b859a138714b6d4f8804fec4f89f17a
Reviewed-on: https://skia-review.googlesource.com/51182
Commit-Queue: Chris Dalton <csmartdalton@google.com>
Reviewed-by: Greg Daniel <egdaniel@google.com>
diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp
index 4a2e9cc..caae839 100644
--- a/src/core/SkGeometry.cpp
+++ b/src/core/SkGeometry.cpp
@@ -601,19 +601,14 @@
// d1 = d2 = 0, d3 != 0 Quadratic
// d1 = d2 = d3 = 0 Line or Point
static SkCubicType classify_cubic(const double d[4], double t[2], double s[2]) {
- // Check for degenerate cubics (quadratics, lines, and points).
- // This also attempts to detect near-quadratics in a resolution independent fashion, however it
- // is still up to the caller to check for almost-linear curves if needed.
- if (fabs(d[1]) + fabs(d[2]) <= fabs(d[3]) * 1e-3) {
- if (t && s) {
- t[0] = t[1] = 1;
- s[0] = s[1] = 0; // infinity
- }
- return 0 == d[3] ? SkCubicType::kLineOrPoint : SkCubicType::kQuadratic;
- }
-
if (0 == d[1]) {
- SkASSERT(0 != d[2]); // captured in check for degeneracy above.
+ if (0 == d[2]) {
+ if (t && s) {
+ t[0] = t[1] = 1;
+ s[0] = s[1] = 0; // infinity
+ }
+ return 0 == d[3] ? SkCubicType::kLineOrPoint : SkCubicType::kQuadratic;
+ }
if (t && s) {
t[0] = d[3];
s[0] = 3 * d[2];
diff --git a/src/gpu/ccpr/GrCCPRGeometry.cpp b/src/gpu/ccpr/GrCCPRGeometry.cpp
index 5446408..bbf5e4f 100644
--- a/src/gpu/ccpr/GrCCPRGeometry.cpp
+++ b/src/gpu/ccpr/GrCCPRGeometry.cpp
@@ -106,11 +106,21 @@
return;
}
+ this->appendMonotonicQuadratics(p0, p1, p2);
+}
+
+inline void GrCCPRGeometry::appendMonotonicQuadratics(const Sk2f& p0, const Sk2f& p1,
+ const Sk2f& p2, bool allowChop) {
+ SkASSERT(fPoints.back() == SkPoint::Make(p0[0], p0[1]));
Sk2f tan0 = p1 - p0;
Sk2f tan1 = p2 - p1;
+
// This should almost always be this case for well-behaved curves in the real world.
- if (is_convex_curve_monotonic(p0, tan0, p2, tan1)) {
- this->appendMonotonicQuadratic(p1, p2);
+ if (!allowChop || is_convex_curve_monotonic(p0, tan0, p2, tan1)) {
+ p1.store(&fPoints.push_back());
+ p2.store(&fPoints.push_back());
+ fVerbs.push_back(Verb::kMonotonicQuadraticTo);
+ ++fCurrContourTallies.fQuadratics;
return;
}
@@ -138,15 +148,12 @@
Sk2f p12 = SkNx_fma(t, tan1, p1);
Sk2f p012 = lerp(p01, p12, t);
- this->appendMonotonicQuadratic(p01, p012);
- this->appendMonotonicQuadratic(p12, p2);
-}
-
-inline void GrCCPRGeometry::appendMonotonicQuadratic(const Sk2f& p1, const Sk2f& p2) {
- p1.store(&fPoints.push_back());
+ p01.store(&fPoints.push_back());
+ p012.store(&fPoints.push_back());
+ p12.store(&fPoints.push_back());
p2.store(&fPoints.push_back());
- fVerbs.push_back(Verb::kMonotonicQuadraticTo);
- ++fCurrContourTallies.fQuadratics;
+ fVerbs.push_back_n(2, Verb::kMonotonicQuadraticTo);
+ fCurrContourTallies.fQuadratics += 2;
}
using ExcludedTerm = GrPathUtils::ExcludedTerm;
@@ -252,6 +259,30 @@
}
}
+static inline Sk2f first_unless_nearly_zero(const Sk2f& a, const Sk2f& b) {
+ Sk2f aa = a*a;
+ aa += SkNx_shuffle<1,0>(aa);
+ SkASSERT(aa[0] == aa[1]);
+
+ Sk2f bb = b*b;
+ bb += SkNx_shuffle<1,0>(bb);
+ SkASSERT(bb[0] == bb[1]);
+
+ return (aa > bb * SK_ScalarNearlyZero).thenElse(a, b);
+}
+
+static inline bool is_cubic_nearly_quadratic(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
+ const Sk2f& p3, Sk2f& tan0, Sk2f& tan3, Sk2f& c) {
+ tan0 = first_unless_nearly_zero(p1 - p0, p2 - p0);
+ tan3 = first_unless_nearly_zero(p3 - p2, p3 - p1);
+
+ Sk2f c1 = SkNx_fma(Sk2f(1.5f), tan0, p0);
+ Sk2f c2 = SkNx_fma(Sk2f(-1.5f), tan3, p3);
+ c = (c1 + c2) * .5f; // Hopefully optimized out if not used?
+
+ return ((c1 - c2).abs() <= 1).allTrue();
+}
+
void GrCCPRGeometry::cubicTo(const SkPoint& devP1, const SkPoint& devP2, const SkPoint& devP3,
float inflectPad, float loopIntersectPad) {
SkASSERT(fBuildingContour);
@@ -273,23 +304,20 @@
return;
}
- double tt[2], ss[2];
- fCurrCubicType = SkClassifyCubic(devPts, tt, ss);
- if (SkCubicIsDegenerate(fCurrCubicType)) {
- // Allow one subdivision in case the curve is quadratic, but not monotonic.
- this->appendCubicApproximation(p0, p1, p2, p3, /*maxSubdivisions=*/1);
+ // Also detect near-quadratics ahead of time.
+ Sk2f tan0, tan3, c;
+ if (is_cubic_nearly_quadratic(p0, p1, p2, p3, tan0, tan3, c)) {
+ this->appendMonotonicQuadratics(p0, c, p3);
return;
}
+ double tt[2], ss[2];
+ fCurrCubicType = SkClassifyCubic(devPts, tt, ss);
+ SkASSERT(!SkCubicIsDegenerate(fCurrCubicType)); // Should have been caught above.
+
SkMatrix CIT;
ExcludedTerm skipTerm = GrPathUtils::calcCubicInverseTransposePowerBasisMatrix(devPts, &CIT);
- if (ExcludedTerm::kNonInvertible == skipTerm) {
- // This could technically also happen if the curve were a quadratic, but SkClassifyCubic
- // should have detected that case already with tolerance.
- p3.store(&fPoints.push_back());
- fVerbs.push_back(Verb::kLineTo);
- return;
- }
+ SkASSERT(ExcludedTerm::kNonInvertible != skipTerm); // Should have been caught above.
SkASSERT(0 == CIT[6]);
SkASSERT(0 == CIT[7]);
SkASSERT(1 == CIT[8]);
@@ -427,18 +455,6 @@
&GrCCPRGeometry::appendMonotonicCubics>(abcd2, bcd2, cd2, p3, (T3-T2) / (1-T2));
}
-static inline Sk2f first_unless_nearly_zero(const Sk2f& a, const Sk2f& b) {
- Sk2f aa = a*a;
- aa += SkNx_shuffle<1,0>(aa);
- SkASSERT(aa[0] == aa[1]);
-
- Sk2f bb = b*b;
- bb += SkNx_shuffle<1,0>(bb);
- SkASSERT(bb[0] == bb[1]);
-
- return (aa > bb * SK_ScalarNearlyZero).thenElse(a, b);
-}
-
template<GrCCPRGeometry::AppendCubicFn AppendLeftRight>
inline void GrCCPRGeometry::chopCubicAtMidTangent(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
const Sk2f& p3, const Sk2f& tan0,
@@ -490,6 +506,7 @@
void GrCCPRGeometry::appendMonotonicCubics(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
const Sk2f& p3, int maxSubdivisions) {
+ SkASSERT(maxSubdivisions >= 0);
if ((p0 == p3).allTrue()) {
return;
}
@@ -521,6 +538,7 @@
void GrCCPRGeometry::appendCubicApproximation(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
const Sk2f& p3, int maxSubdivisions) {
+ SkASSERT(maxSubdivisions >= 0);
if ((p0 == p3).allTrue()) {
return;
}
@@ -535,25 +553,15 @@
return;
}
- Sk2f tan0 = first_unless_nearly_zero(p1 - p0, p2 - p0);
- Sk2f tan3 = first_unless_nearly_zero(p3 - p2, p3 - p1);
-
- Sk2f c1 = SkNx_fma(Sk2f(1.5f), tan0, p0);
- Sk2f c2 = SkNx_fma(Sk2f(-1.5f), tan3, p3);
-
- if (maxSubdivisions) {
- bool nearlyQuadratic = ((c1 - c2).abs() <= 1).allTrue();
-
- if (!nearlyQuadratic || !is_convex_curve_monotonic(p0, tan0, p3, tan3)) {
- this->chopCubicAtMidTangent<&GrCCPRGeometry::appendCubicApproximation>(p0, p1, p2, p3,
- tan0, tan3,
- maxSubdivisions-1);
- return;
- }
+ Sk2f tan0, tan3, c;
+ if (!is_cubic_nearly_quadratic(p0, p1, p2, p3, tan0, tan3, c) && maxSubdivisions) {
+ this->chopCubicAtMidTangent<&GrCCPRGeometry::appendCubicApproximation>(p0, p1, p2, p3,
+ tan0, tan3,
+ maxSubdivisions - 1);
+ return;
}
- SkASSERT(fPoints.back() == SkPoint::Make(p0[0], p0[1]));
- this->appendMonotonicQuadratic((c1 + c2) * .5f, p3);
+ this->appendMonotonicQuadratics(p0, c, p3, SkToBool(maxSubdivisions));
}
GrCCPRGeometry::PrimitiveTallies GrCCPRGeometry::endContour() {
diff --git a/src/gpu/ccpr/GrCCPRGeometry.h b/src/gpu/ccpr/GrCCPRGeometry.h
index ee06f78..1cb4719 100644
--- a/src/gpu/ccpr/GrCCPRGeometry.h
+++ b/src/gpu/ccpr/GrCCPRGeometry.h
@@ -93,7 +93,8 @@
PrimitiveTallies endContour(); // Returns the numbers of primitives needed to draw the contour.
private:
- inline void appendMonotonicQuadratic(const Sk2f& p1, const Sk2f& p2);
+ inline void appendMonotonicQuadratics(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
+ bool allowChop = true);
using AppendCubicFn = void(GrCCPRGeometry::*)(const Sk2f& p0, const Sk2f& p1,
const Sk2f& p2, const Sk2f& p3,
diff --git a/tests/GeometryTest.cpp b/tests/GeometryTest.cpp
index 4d955b5..ad3a6b4 100644
--- a/tests/GeometryTest.cpp
+++ b/tests/GeometryTest.cpp
@@ -215,10 +215,10 @@
static void test_classify_cubic(skiatest::Reporter* reporter) {
check_cubic_type(reporter, {{{149.325f, 107.705f}, {149.325f, 103.783f},
{151.638f, 100.127f}, {156.263f, 96.736f}}},
- SkCubicType::kQuadratic);
+ SkCubicType::kSerpentine);
check_cubic_type(reporter, {{{225.694f, 223.15f}, {209.831f, 224.837f},
{195.994f, 230.237f}, {184.181f, 239.35f}}},
- SkCubicType::kQuadratic);
+ SkCubicType::kSerpentine);
check_cubic_type(reporter, {{{4.873f, 5.581f}, {5.083f, 5.2783f},
{5.182f, 4.8593f}, {5.177f, 4.3242f}}},
SkCubicType::kSerpentine);