Replace Pathops in Geometry::ChopMonoCubic implementation
This uses code in base instead, breaking the connection between
SkPath and Pathops.
This extracts one more function into SkBezierCurves.h, one
that converts between the control points and the polynomial.
It also adds a test comparing that functionality to the
Pathops one. We might be able to, in a follow-up CL, replace
SkDCubic::Coefficients with SkBezierCubic::ConvertToPolynomial.
Change-Id: I65e2b692c63a8c647ac48552008424ef1ea5d737
Bug: skia:13983
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/633458
Reviewed-by: Michael Ludwig <michaelludwig@google.com>
Commit-Queue: Kevin Lubick <kjlubick@google.com>
diff --git a/BUILD.gn b/BUILD.gn
index 2391736..ecd3084 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -1669,9 +1669,13 @@
sources += skia_pathops_public
sources += [
"src/base/SkArenaAlloc.cpp",
+ "src/base/SkBezierCurves.cpp",
"src/base/SkContainers.cpp",
+ "src/base/SkCubics.cpp",
+ "src/base/SkFloatingPoint.cpp",
"src/base/SkMalloc.cpp",
"src/base/SkMathPriv.cpp",
+ "src/base/SkQuads.cpp",
"src/base/SkSafeMath.cpp",
"src/base/SkSemaphore.cpp",
"src/base/SkTDArray.cpp",
diff --git a/src/base/SkBezierCurves.cpp b/src/base/SkBezierCurves.cpp
index 95679b8..afb2a24 100644
--- a/src/base/SkBezierCurves.cpp
+++ b/src/base/SkBezierCurves.cpp
@@ -56,3 +56,22 @@
alpha_X(3) /*= beta_X(0) */ = interpolate(alpha_X(2), beta_X(1), t);
alpha_Y(3) /*= beta_Y(0) */ = interpolate(alpha_Y(2), beta_Y(1), t);
}
+
+std::array<double, 4> SkBezierCubic::ConvertToPolynomial(const double curve[8], bool yValues) {
+ const double* offset_curve = yValues ? curve + 1 : curve;
+ const auto P = [&offset_curve](size_t n) { return offset_curve[2*n]; };
+ // A cubic Bézier curve is interpolated as follows:
+ // c(t) = (1 - t)^3 P_0 + 3t(1 - t)^2 P_1 + 3t^2 (1 - t) P_2 + t^3 P_3
+ // = (-P_0 + 3P_1 + -3P_2 + P_3) t^3 + (3P_0 - 6P_1 + 3P_2) t^2 +
+ // (-3P_0 + 3P_1) t + P_0
+ // Where P_N is the Nth point. The second step expands the polynomial and groups
+ // by powers of t. The desired output is a cubic formula, so we just need to
+ // combine the appropriate points to make the coefficients.
+ std::array<double, 4> results;
+ results[0] = -P(0) + 3*P(1) - 3*P(2) + P(3);
+ results[1] = 3*P(0) - 6*P(1) + 3*P(2);
+ results[2] = -3*P(0) + 3*P(1);
+ results[3] = P(0);
+ return results;
+}
+
diff --git a/src/base/SkBezierCurves.h b/src/base/SkBezierCurves.h
index c2e8b84..c0bdf67 100644
--- a/src/base/SkBezierCurves.h
+++ b/src/base/SkBezierCurves.h
@@ -7,6 +7,8 @@
#ifndef SkBezierCurves_DEFINED
#define SkBezierCurves_DEFINED
+#include <array>
+
/**
* Utilities for dealing with cubic Bézier curves. These have a start XY
* point, an end XY point, and two control XY points in between. They take
@@ -21,8 +23,8 @@
class SkBezierCubic {
public:
/**
- * Splits the provided curve at the location t, resulting in two
- * bezier curves that share a point (the end point from curve 1
+ * Splits the provided Bézier curve at the location t, resulting in two
+ * Bézier curves that share a point (the end point from curve 1
* and the start point from curve 2 are the same).
*
* t must be in the interval [0, 1].
@@ -33,6 +35,17 @@
*/
static void Subdivide(const double curve[8], double t,
double twoCurves[14]);
+
+ /**
+ * Converts the provided Bézier curve into the the equivalent cubic
+ * f(t) = A*t^3 + B*t^2 + C*t + D
+ * where f(t) will represent Y coordinates over time if yValues is
+ * true and the X coordinates if yValues is false.
+ *
+ * In effect, this turns the control points into an actual line, representing
+ * the x or y values.
+ */
+ static std::array<double, 4> ConvertToPolynomial(const double curve[8], bool yValues);
};
#endif
diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp
index 9d68032..068a852 100644
--- a/src/core/SkGeometry.cpp
+++ b/src/core/SkGeometry.cpp
@@ -14,9 +14,9 @@
#include "include/private/base/SkTPin.h"
#include "include/private/base/SkTo.h"
#include "include/private/base/SkVx.h"
+#include "src/base/SkBezierCurves.h"
+#include "src/base/SkCubics.h"
#include "src/core/SkPointPriv.h"
-#include "src/pathops/SkPathOpsCubic.h"
-#include "src/pathops/SkPathOpsPoint.h"
#include <algorithm>
#include <array>
@@ -1146,29 +1146,51 @@
return -1;
}
-typedef int (SkDCubic::*InterceptProc)(double intercept, double roots[3]) const;
-static bool cubic_dchop_at_intercept(const SkPoint src[4], SkScalar intercept, SkPoint dst[7],
- InterceptProc method) {
- SkDCubic cubic;
- double roots[3];
- int count = (cubic.set(src).*method)(intercept, roots);
- if (count > 0) {
- SkDCubicPair pair = cubic.chopAt(roots[0]);
- for (int i = 0; i < 7; ++i) {
- dst[i] = pair.pts[i].asSkPoint();
+
+static bool first_axis_intersection(const double coefficients[4], bool yDirection,
+ double axisIntercept, double* solution) {
+ auto [A, B, C, D] = SkBezierCubic::ConvertToPolynomial(coefficients, yDirection);
+ D -= axisIntercept;
+ double roots[3] = {0, 0, 0};
+ int count = SkCubics::RootsValidT(A, B, C, D, roots);
+ if (count == 0) {
+ return false;
+ }
+ *solution = roots[0];
+ return true;
+}
+
+bool SkChopMonoCubicAtY(const SkPoint src[4], SkScalar y, SkPoint dst[7]) {
+ double coefficients[8] = {src[0].fX, src[0].fY, src[1].fX, src[1].fY,
+ src[2].fX, src[2].fY, src[3].fX, src[3].fY};
+ double solution = 0;
+ if (first_axis_intersection(coefficients, true, y, &solution)) {
+ double cubicPair[14];
+ SkBezierCubic::Subdivide(coefficients, solution, cubicPair);
+ for (int i = 0; i < 7; i ++) {
+ dst[i].fX = sk_double_to_float(cubicPair[i*2]);
+ dst[i].fY = sk_double_to_float(cubicPair[i*2 + 1]);
}
return true;
}
return false;
}
-bool SkChopMonoCubicAtY(const SkPoint src[4], SkScalar y, SkPoint dst[7]) {
- return cubic_dchop_at_intercept(src, y, dst, &SkDCubic::horizontalIntersect);
-}
-
bool SkChopMonoCubicAtX(const SkPoint src[4], SkScalar x, SkPoint dst[7]) {
- return cubic_dchop_at_intercept(src, x, dst, &SkDCubic::verticalIntersect);
+ double coefficients[8] = {src[0].fX, src[0].fY, src[1].fX, src[1].fY,
+ src[2].fX, src[2].fY, src[3].fX, src[3].fY};
+ double solution = 0;
+ if (first_axis_intersection(coefficients, false, x, &solution)) {
+ double cubicPair[14];
+ SkBezierCubic::Subdivide(coefficients, solution, cubicPair);
+ for (int i = 0; i < 7; i ++) {
+ dst[i].fX = sk_double_to_float(cubicPair[i*2]);
+ dst[i].fY = sk_double_to_float(cubicPair[i*2 + 1]);
+ }
+ return true;
+ }
+ return false;
}
///////////////////////////////////////////////////////////////////////////////
diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp
index 3434a7a..b83b599 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -129,6 +129,7 @@
return dst;
}
+// TODO(skbug.com/14063) deduplicate this with SkBezierCubic::ConvertToPolynomial
void SkDCubic::Coefficients(const double* src, double* A, double* B, double* C, double* D) {
*A = src[6]; // d
*B = src[4] * 3; // 3*c
diff --git a/tests/CubicChopTest.cpp b/tests/CubicChopTest.cpp
index ed2fe77..c534267 100644
--- a/tests/CubicChopTest.cpp
+++ b/tests/CubicChopTest.cpp
@@ -202,3 +202,48 @@
{ 3.00000000000000, 13.00000000000000 }}
);
}
+
+static void testConvertToPolynomial(skiatest::Reporter* reporter, std::string name,
+ SkSpan<const DoublePoint> curveInputs, bool yValues,
+ double expectedA, double expectedB,
+ double expectedC, double expectedD) {
+ skiatest::ReporterContext subtest(reporter, name);
+ REPORTER_ASSERT(reporter, curveInputs.size() == 4,
+ "Invalid test case. Need 4 points (start, control, control, end)");
+
+ {
+ skiatest::ReporterContext subsubtest(reporter, "Pathops Implementation");
+ const double* input = &curveInputs[0].x;
+ if (yValues) {
+ input = &curveInputs[0].y;
+ }
+ double A, B, C, D;
+ SkDCubic::Coefficients(input, &A, &B, &C, &D);
+
+ REPORTER_ASSERT(reporter, nearly_equal(expectedA, A), "%f != %f", expectedA, A);
+ REPORTER_ASSERT(reporter, nearly_equal(expectedB, B), "%f != %f", expectedB, B);
+ REPORTER_ASSERT(reporter, nearly_equal(expectedC, C), "%f != %f", expectedC, C);
+ REPORTER_ASSERT(reporter, nearly_equal(expectedD, D), "%f != %f", expectedD, D);
+ }
+ {
+ skiatest::ReporterContext subsubtest(reporter, "SkBezierCurve Implementation");
+ const double* input = &curveInputs[0].x;
+ auto [A, B, C, D] = SkBezierCubic::ConvertToPolynomial(input, yValues);
+
+ REPORTER_ASSERT(reporter, nearly_equal(expectedA, A), "%f != %f", expectedA, A);
+ REPORTER_ASSERT(reporter, nearly_equal(expectedB, B), "%f != %f", expectedB, B);
+ REPORTER_ASSERT(reporter, nearly_equal(expectedC, C), "%f != %f", expectedC, C);
+ REPORTER_ASSERT(reporter, nearly_equal(expectedD, D), "%f != %f", expectedD, D);
+ }
+}
+
+DEF_TEST(BezierCurvesToPolynomials, reporter) {
+ testConvertToPolynomial(reporter, "Arbitrary control points X direction",
+ {{1, 2}, {-3, 4}, {5, -6}, {7, 8}}, false, /*=yValues*/
+ -18, 36, -12, 1
+ );
+ testConvertToPolynomial(reporter, "Arbitrary control points Y direction",
+ {{1, 2}, {-3, 4}, {5, -6}, {7, 8}}, true, /*=yValues*/
+ 36, -36, 6, 2
+ );
+}
