Move tessellation-specific functions out of GrPathUtils
Bug: skia:12524
Change-Id: I2664c8ea707a40724bcf916e907fe28d1fa276d6
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/474357
Reviewed-by: Michael Ludwig <michaelludwig@google.com>
Commit-Queue: Chris Dalton <csmartdalton@google.com>
diff --git a/bench/FindCubicConvex180ChopsBench.cpp b/bench/FindCubicConvex180ChopsBench.cpp
new file mode 100644
index 0000000..78e7d42
--- /dev/null
+++ b/bench/FindCubicConvex180ChopsBench.cpp
@@ -0,0 +1,40 @@
+/*
+ * Copyright 2020 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "bench/Benchmark.h"
+#include "src/gpu/tessellate/Tessellation.h"
+
+class FindCubicConvex180ChopsBench : public Benchmark {
+public:
+ FindCubicConvex180ChopsBench(const std::array<SkPoint,4>& pts, const char* suffix) : fPts(pts) {
+ fName.printf("FindCubicConvex180Chops%s", suffix);
+ }
+
+private:
+ const char* onGetName() override { return fName.c_str(); }
+ bool isSuitableFor(Backend backend) final { return backend == kNonRendering_Backend; }
+ void onDraw(int loops, SkCanvas*) final {
+ float T[2] = {0};
+ bool areCusps;
+ int iters = 50000 * loops;
+ for (int i = 0; i < iters; ++i) {
+ int count = skgpu::FindCubicConvex180Chops(fPts.data(), T, &areCusps);
+ if (T[0] == 200.7f) {
+ // This will never happen. Pretend to use the result to keep the compiler honest.
+ SkDebugf("%i%f%f", count, T[0], T[1]);
+ }
+ }
+ }
+
+ SkString fName;
+ std::array<SkPoint,4> fPts;
+};
+
+DEF_BENCH(return new FindCubicConvex180ChopsBench({{{0,0}, {100,0}, {50,100}, {100,100}}},
+ "_inflect1");)
+DEF_BENCH(return new FindCubicConvex180ChopsBench({{{0,0}, {50,0}, {100,50}, {100,100}}},
+ "_loop");)
diff --git a/bench/GrPathUtilsBench.cpp b/bench/GrPathUtilsBench.cpp
deleted file mode 100644
index 6e28a2e..0000000
--- a/bench/GrPathUtilsBench.cpp
+++ /dev/null
@@ -1,38 +0,0 @@
-/*
- * Copyright 2020 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#include "bench/Benchmark.h"
-#include "src/gpu/geometry/GrPathUtils.h"
-
-class FindCubicConvex180Chops : public Benchmark {
-public:
- FindCubicConvex180Chops(const std::array<SkPoint,4>& pts, const char* suffix) : fPts(pts) {
- fName.printf("GrPathUtils_findCubicConvex180Chops%s", suffix);
- }
-
-private:
- const char* onGetName() override { return fName.c_str(); }
- bool isSuitableFor(Backend backend) final { return backend == kNonRendering_Backend; }
- void onDraw(int loops, SkCanvas*) final {
- float T[2] = {0};
- bool areCusps;
- int iters = 50000 * loops;
- for (int i = 0; i < iters; ++i) {
- int count = GrPathUtils::findCubicConvex180Chops(fPts.data(), T, &areCusps);
- if (T[0] == 200.7f) {
- // This will never happen. Pretend to use the result to keep the compiler honest.
- SkDebugf("%i%f%f", count, T[0], T[1]);
- }
- }
- }
-
- SkString fName;
- std::array<SkPoint,4> fPts;
-};
-
-DEF_BENCH(return new FindCubicConvex180Chops({{{0,0}, {100,0}, {50,100}, {100,100}}}, "_inflect1");)
-DEF_BENCH(return new FindCubicConvex180Chops({{{0,0}, {50,0}, {100,50}, {100,100}}}, "_loop");)
diff --git a/gn/bench.gni b/gn/bench.gni
index 76da063..6372521 100644
--- a/gn/bench.gni
+++ b/gn/bench.gni
@@ -44,6 +44,7 @@
"$_bench/EncodeBench.cpp",
"$_bench/FSRectBench.cpp",
"$_bench/FilteringBench.cpp",
+ "$_bench/FindCubicConvex180ChopsBench.cpp",
"$_bench/FontCacheBench.cpp",
"$_bench/GMBench.cpp",
"$_bench/GameBench.cpp",
@@ -51,7 +52,6 @@
"$_bench/GlyphQuadFillBench.cpp",
"$_bench/GrMemoryPoolBench.cpp",
"$_bench/GrMipmapBench.cpp",
- "$_bench/GrPathUtilsBench.cpp",
"$_bench/GrQuadBench.cpp",
"$_bench/GrResourceCacheBench.cpp",
"$_bench/GradientBench.cpp",
diff --git a/gn/tests.gni b/gn/tests.gni
index c01c3d7..1985933 100644
--- a/gn/tests.gni
+++ b/gn/tests.gni
@@ -72,6 +72,7 @@
"$_tests/F16StagesTest.cpp",
"$_tests/FakeStreams.h",
"$_tests/FillPathTest.cpp",
+ "$_tests/FindCubicConvex180ChopsTest.cpp",
"$_tests/FitsInTest.cpp",
"$_tests/FlattenDrawableTest.cpp",
"$_tests/FlattenableFactoryToName.cpp",
@@ -98,7 +99,6 @@
"$_tests/GrFinishedFlushTest.cpp",
"$_tests/GrMemoryPoolTest.cpp",
"$_tests/GrOpListFlushTest.cpp",
- "$_tests/GrPathUtilsTest.cpp",
"$_tests/GrPorterDuffTest.cpp",
"$_tests/GrQuadBufferTest.cpp",
"$_tests/GrQuadCropTest.cpp",
diff --git a/src/gpu/geometry/GrPathUtils.cpp b/src/gpu/geometry/GrPathUtils.cpp
index 9e0bd7f..c68f53d 100644
--- a/src/gpu/geometry/GrPathUtils.cpp
+++ b/src/gpu/geometry/GrPathUtils.cpp
@@ -549,140 +549,3 @@
convert_noninflect_cubic_to_quads_with_constraint(cubic, tolSqd, dir, quads);
}
}
-
-int GrPathUtils::findCubicConvex180Chops(const SkPoint pts[], float T[2], bool* areCusps) {
- using grvx::float2;
- SkASSERT(pts);
- SkASSERT(T);
- SkASSERT(areCusps);
-
- // If a chop falls within a distance of "kEpsilon" from 0 or 1, throw it out. Tangents become
- // unstable when we chop too close to the boundary. This works out because the tessellation
- // shaders don't allow more than 2^10 parametric segments, and they snap the beginning and
- // ending edges at 0 and 1. So if we overstep an inflection or point of 180-degree rotation by a
- // fraction of a tessellation segment, it just gets snapped.
- constexpr static float kEpsilon = 1.f / (1 << 11);
- // Floating-point representation of "1 - 2*kEpsilon".
- constexpr static uint32_t kIEEE_one_minus_2_epsilon = (127 << 23) - 2 * (1 << (24 - 11));
- // Unfortunately we don't have a way to static_assert this, but we can runtime assert that the
- // kIEEE_one_minus_2_epsilon bits are correct.
- SkASSERT(sk_bit_cast<float>(kIEEE_one_minus_2_epsilon) == 1 - 2*kEpsilon);
-
- float2 p0 = skvx::bit_pun<float2>(pts[0]);
- float2 p1 = skvx::bit_pun<float2>(pts[1]);
- float2 p2 = skvx::bit_pun<float2>(pts[2]);
- float2 p3 = skvx::bit_pun<float2>(pts[3]);
-
- // Find the cubic's power basis coefficients. These define the bezier curve as:
- //
- // |T^3|
- // Cubic(T) = x,y = |A 3B 3C| * |T^2| + P0
- // |. . .| |T |
- //
- // And the tangent direction (scaled by a uniform 1/3) will be:
- //
- // |T^2|
- // Tangent_Direction(T) = dx,dy = |A 2B C| * |T |
- // |. . .| |1 |
- //
- float2 C = p1 - p0;
- float2 D = p2 - p1;
- float2 E = p3 - p0;
- float2 B = D - C;
- float2 A = -3*D + E;
-
- // Now find the cubic's inflection function. There are inflections where F' x F'' == 0.
- // We formulate this as a quadratic equation: F' x F'' == aT^2 + bT + c == 0.
- // See: https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
- // NOTE: We only need the roots, so a uniform scale factor does not affect the solution.
- float a = grvx::cross(A,B);
- float b = grvx::cross(A,C);
- float c = grvx::cross(B,C);
- float b_over_minus_2 = -.5f * b;
- float discr_over_4 = b_over_minus_2*b_over_minus_2 - a*c;
-
- // If -cuspThreshold <= discr_over_4 <= cuspThreshold, it means the two roots are within
- // kEpsilon of one another (in parametric space). This is close enough for our purposes to
- // consider them a single cusp.
- float cuspThreshold = a * (kEpsilon/2);
- cuspThreshold *= cuspThreshold;
-
- if (discr_over_4 < -cuspThreshold) {
- // The curve does not inflect or cusp. This means it might rotate more than 180 degrees
- // instead. Chop were rotation == 180 deg. (This is the 2nd root where the tangent is
- // parallel to tan0.)
- //
- // Tangent_Direction(T) x tan0 == 0
- // (AT^2 x tan0) + (2BT x tan0) + (C x tan0) == 0
- // (A x C)T^2 + (2B x C)T + (C x C) == 0 [[because tan0 == P1 - P0 == C]]
- // bT^2 + 2cT + 0 == 0 [[because A x C == b, B x C == c]]
- // T = [0, -2c/b]
- //
- // NOTE: if C == 0, then C != tan0. But this is fine because the curve is definitely
- // convex-180 if any points are colocated, and T[0] will equal NaN which returns 0 chops.
- *areCusps = false;
- float root = sk_ieee_float_divide(c, b_over_minus_2);
- // Is "root" inside the range [kEpsilon, 1 - kEpsilon)?
- if (sk_bit_cast<uint32_t>(root - kEpsilon) < kIEEE_one_minus_2_epsilon) {
- T[0] = root;
- return 1;
- }
- return 0;
- }
-
- *areCusps = (discr_over_4 <= cuspThreshold);
- if (*areCusps) {
- // The two roots are close enough that we can consider them a single cusp.
- if (a != 0 || b_over_minus_2 != 0 || c != 0) {
- // Pick the average of both roots.
- float root = sk_ieee_float_divide(b_over_minus_2, a);
- // Is "root" inside the range [kEpsilon, 1 - kEpsilon)?
- if (sk_bit_cast<uint32_t>(root - kEpsilon) < kIEEE_one_minus_2_epsilon) {
- T[0] = root;
- return 1;
- }
- return 0;
- }
-
- // The curve is a flat line. The standard inflection function doesn't detect cusps from flat
- // lines. Find cusps by searching instead for points where the tangent is perpendicular to
- // tan0. This will find any cusp point.
- //
- // dot(tan0, Tangent_Direction(T)) == 0
- //
- // |T^2|
- // tan0 * |A 2B C| * |T | == 0
- // |. . .| |1 |
- //
- float2 tan0 = skvx::if_then_else(C != 0, C, p2 - p0);
- a = grvx::dot(tan0, A);
- b_over_minus_2 = -grvx::dot(tan0, B);
- c = grvx::dot(tan0, C);
- discr_over_4 = std::max(b_over_minus_2*b_over_minus_2 - a*c, 0.f);
- }
-
- // Solve our quadratic equation to find where to chop. See the quadratic formula from
- // Numerical Recipes in C.
- float q = sqrtf(discr_over_4);
- q = copysignf(q, b_over_minus_2);
- q = q + b_over_minus_2;
- float2 roots = float2{q,c} / float2{a,q};
-
- auto inside = (roots > kEpsilon) & (roots < (1 - kEpsilon));
- if (inside[0]) {
- if (inside[1] && roots[0] != roots[1]) {
- if (roots[0] > roots[1]) {
- roots = skvx::shuffle<1,0>(roots); // Sort.
- }
- roots.store(T);
- return 2;
- }
- T[0] = roots[0];
- return 1;
- }
- if (inside[1]) {
- T[0] = roots[1];
- return 1;
- }
- return 0;
-}
diff --git a/src/gpu/geometry/GrPathUtils.h b/src/gpu/geometry/GrPathUtils.h
index c9ccc21..24ae1bb 100644
--- a/src/gpu/geometry/GrPathUtils.h
+++ b/src/gpu/geometry/GrPathUtils.h
@@ -133,53 +133,6 @@
SkPathFirstDirection dir,
SkTArray<SkPoint, true>* quads);
-// Converts the given line to a cubic bezier.
-// NOTE: This method interpolates at 1/3 and 2/3, but if suitable in context, the cubic
-// {p0, p0, p1, p1} may also work.
-inline void writeLineAsCubic(SkPoint startPt, SkPoint endPt, skgpu::VertexWriter* writer) {
- using grvx::float2, skvx::bit_pun;
- float2 p0 = bit_pun<float2>(startPt);
- float2 p1 = bit_pun<float2>(endPt);
- float2 v = (p1 - p0) * (1/3.f);
- *writer << p0 << (p0 + v) << (p1 - v) << p1;
-}
-
-// Converts the given quadratic bezier to a cubic.
-inline void writeQuadAsCubic(const SkPoint p[3], skgpu::VertexWriter* writer) {
- using grvx::float2, skvx::bit_pun;
- float2 p0 = bit_pun<float2>(p[0]);
- float2 p1 = bit_pun<float2>(p[1]);
- float2 p2 = bit_pun<float2>(p[2]);
- float2 c = p1 * (2/3.f);
- *writer << p0 << (p0*(1/3.f) + c) << (p2 * (1/3.f) + c) << p2;
-}
-inline void convertQuadToCubic(const SkPoint p[3], SkPoint out[4]) {
- skgpu::VertexWriter writer(out);
- writeQuadAsCubic(p, &writer);
-}
-
-// Finds 0, 1, or 2 T values at which to chop the given curve in order to guarantee the resulting
-// cubics are convex and rotate no more than 180 degrees.
-//
-// - If the cubic is "serpentine", then the T values are any inflection points in [0 < T < 1].
-// - If the cubic is linear, then the T values are any 180-degree cusp points in [0 < T < 1].
-// - Otherwise the T value is the point at which rotation reaches 180 degrees, iff in [0 < T < 1].
-//
-// 'areCusps' is set to true if the chop point occurred at a cusp (within tolerance), or if the chop
-// point(s) occurred at 180-degree turnaround points on a degenerate flat line.
-int findCubicConvex180Chops(const SkPoint[], float T[2], bool* areCusps);
-
-// Returns true if the given conic (or quadratic) has a cusp point. The w value is not necessary in
-// determining this. If there is a cusp, it can be found at the midtangent.
-inline bool conicHasCusp(const SkPoint p[3]) {
- SkVector a = p[1] - p[0];
- SkVector b = p[2] - p[1];
- // A conic of any class can only have a cusp if it is a degenerate flat line with a 180 degree
- // turnarund. To detect this, the beginning and ending tangents must be parallel
- // (a.cross(b) == 0) and pointing in opposite directions (a.dot(b) < 0).
- return a.cross(b) == 0 && a.dot(b) < 0;
-}
-
} // namespace GrPathUtils
#endif
diff --git a/src/gpu/tessellate/PatchWriter.h b/src/gpu/tessellate/PatchWriter.h
index 780293a..4f2c01d 100644
--- a/src/gpu/tessellate/PatchWriter.h
+++ b/src/gpu/tessellate/PatchWriter.h
@@ -182,6 +182,9 @@
// Converts a quadratic to a cubic when being output via '<<' to a VertexWriter.
struct QuadToCubic {
+ QuadToCubic(float2 p0, float2 p1, float2 p2) : fP0(p0), fP1(p1), fP2(p2) {}
+ QuadToCubic(const SkPoint p[3])
+ : QuadToCubic(float2::Load(p), float2::Load(p+1), float2::Load(p+2)) {}
float2 fP0, fP1, fP2;
};
@@ -191,6 +194,11 @@
return vertexWriter << p0 << mix(float4(p0,p2), p1.xyxy(), 2/3.f) << p2;
}
+SK_MAYBE_UNUSED SK_ALWAYS_INLINE VertexWriter& operator<<(VertexWriter&& vertexWriter,
+ const QuadToCubic& quadratic) {
+ return vertexWriter << quadratic;
+}
+
SK_MAYBE_UNUSED SK_ALWAYS_INLINE void operator<<(
PatchWriter& w, MiddleOutPolygonTriangulator::PoppedTriangleStack&& stack) {
for (auto [p0, p1, p2] : stack) {
diff --git a/src/gpu/tessellate/PathCurveTessellator.cpp b/src/gpu/tessellate/PathCurveTessellator.cpp
index aae0ac1..4feea87 100644
--- a/src/gpu/tessellate/PathCurveTessellator.cpp
+++ b/src/gpu/tessellate/PathCurveTessellator.cpp
@@ -7,7 +7,6 @@
#include "src/gpu/tessellate/PathCurveTessellator.h"
-#include "src/gpu/geometry/GrPathUtils.h"
#include "src/gpu/tessellate/AffineMatrix.h"
#include "src/gpu/tessellate/MiddleOutPolygonTriangulator.h"
#include "src/gpu/tessellate/PatchWriter.h"
diff --git a/src/gpu/tessellate/StrokeFixedCountTessellator.cpp b/src/gpu/tessellate/StrokeFixedCountTessellator.cpp
index c160e08..d5312f3 100644
--- a/src/gpu/tessellate/StrokeFixedCountTessellator.cpp
+++ b/src/gpu/tessellate/StrokeFixedCountTessellator.cpp
@@ -8,7 +8,6 @@
#include "src/gpu/tessellate/StrokeFixedCountTessellator.h"
#include "src/core/SkGeometry.h"
-#include "src/gpu/geometry/GrPathUtils.h"
#include "src/gpu/tessellate/PatchWriter.h"
#include "src/gpu/tessellate/StrokeIterator.h"
#include "src/gpu/tessellate/WangsFormula.h"
@@ -56,7 +55,7 @@
return;
}
SkPoint cubic[4];
- GrPathUtils::convertQuadToCubic(p, cubic);
+ VertexWriter(cubic) << QuadToCubic(p);
SkPoint endControlPoint = cubic[2];
this->writeStroke(cubic, endControlPoint, GrTessellationShader::kCubicCurveType);
fMaxParametricSegments_pow4 = std::max(numParametricSegments_pow4,
@@ -259,7 +258,7 @@
instanceWriter.lineTo(p[0], p[1]);
break;
case Verb::kQuad:
- if (GrPathUtils::conicHasCusp(p)) {
+ if (ConicHasCusp(p)) {
// The cusp is always at the midtandent.
SkPoint cusp = SkEvalQuadAt(p, SkFindQuadMidTangent(p));
instanceWriter.writeCircle(cusp);
@@ -271,7 +270,7 @@
}
break;
case Verb::kConic:
- if (GrPathUtils::conicHasCusp(p)) {
+ if (ConicHasCusp(p)) {
// The cusp is always at the midtandent.
SkConic conic(p, strokeIter.w());
SkPoint cusp = conic.evalAt(conic.findMidTangent());
@@ -287,7 +286,7 @@
SkPoint chops[10];
float T[2];
bool areCusps;
- numChops = GrPathUtils::findCubicConvex180Chops(p, T, &areCusps);
+ numChops = FindCubicConvex180Chops(p, T, &areCusps);
if (numChops == 0) {
instanceWriter.cubicConvex180To(p);
} else if (numChops == 1) {
diff --git a/src/gpu/tessellate/StrokeHardwareTessellator.cpp b/src/gpu/tessellate/StrokeHardwareTessellator.cpp
index ba3e3fa..1189ab1 100644
--- a/src/gpu/tessellate/StrokeHardwareTessellator.cpp
+++ b/src/gpu/tessellate/StrokeHardwareTessellator.cpp
@@ -7,8 +7,8 @@
#include "src/gpu/tessellate/StrokeHardwareTessellator.h"
+#include "src/core/SkGeometry.h"
#include "src/core/SkPathPriv.h"
-#include "src/gpu/geometry/GrPathUtils.h"
#include "src/gpu/tessellate/PatchWriter.h"
#include "src/gpu/tessellate/WangsFormula.h"
#include "src/gpu/tessellate/shaders/GrTessellationShader.h"
@@ -163,7 +163,7 @@
SkPoint chops[10];
float chopT[2];
bool areCusps;
- int numChops = GrPathUtils::findCubicConvex180Chops(p, chopT, &areCusps);
+ int numChops = FindCubicConvex180Chops(p, chopT, &areCusps);
if (numChops == 0) {
// The curve is already convex and rotates no more than 180 degrees.
this->internalCubicConvex180PatchesTo(fStrokeJoinType, p);
@@ -349,7 +349,7 @@
// Convert to a patch.
SkPoint asPatch[4];
if (w == 1) {
- GrPathUtils::convertQuadToCubic(p, asPatch);
+ VertexWriter(asPatch) << QuadToCubic(p);
} else {
GrTessellationShader::WriteConicPatch(p, w, asPatch);
}
@@ -634,7 +634,7 @@
float2 p2 = skvx::bit_pun<float2>(p[2]);
float2 p3 = skvx::bit_pun<float2>(p[3]);
- // See GrPathUtils::findCubicConvex180Chops() for the math.
+ // See FindCubicConvex180Chops() for the math.
float2 C = p1 - p0;
float2 D = p2 - p1;
float2 E = p3 - p0;
@@ -747,7 +747,7 @@
hwPatchWriter.writeLineTo(p[0], p[2]);
continue;
}
- if (GrPathUtils::conicHasCusp(p)) {
+ if (ConicHasCusp(p)) {
// Cusps are rare, but the tessellation shader can't handle them. Chop the
// curve into segments that the shader can handle.
SkPoint cusp = SkEvalQuadAt(p, SkFindQuadMidTangent(p));
@@ -767,7 +767,7 @@
// Write it out directly.
prevJoinFitsInPatch = hwPatchWriter.stroke180FitsInPatch_withJoin(
numParametricSegments_pow4);
- GrPathUtils::convertQuadToCubic(p, scratchPts);
+ VertexWriter(scratchPts) << QuadToCubic(p);
patchPts = scratchPts;
endControlPoint = patchPts[2];
break;
@@ -782,7 +782,7 @@
hwPatchWriter.writeLineTo(p[0], p[2]);
continue;
}
- if (GrPathUtils::conicHasCusp(p)) {
+ if (ConicHasCusp(p)) {
// Cusps are rare, but the tessellation shader can't handle them. Chop the
// curve into segments that the shader can handle.
SkConic conic(p, *w);
diff --git a/src/gpu/tessellate/Tessellation.cpp b/src/gpu/tessellate/Tessellation.cpp
index cf5c4e3..18abf6e 100644
--- a/src/gpu/tessellate/Tessellation.cpp
+++ b/src/gpu/tessellate/Tessellation.cpp
@@ -10,6 +10,7 @@
#include "include/core/SkPath.h"
#include "src/core/SkGeometry.h"
#include "src/core/SkPathPriv.h"
+#include "src/core/SkUtils.h"
#include "src/gpu/BufferWriter.h"
#include "src/gpu/tessellate/CullTest.h"
#include "src/gpu/tessellate/MiddleOutPolygonTriangulator.h"
@@ -191,4 +192,139 @@
return chopper.path();
}
+int FindCubicConvex180Chops(const SkPoint pts[], float T[2], bool* areCusps) {
+ SkASSERT(pts);
+ SkASSERT(T);
+ SkASSERT(areCusps);
+
+ // If a chop falls within a distance of "kEpsilon" from 0 or 1, throw it out. Tangents become
+ // unstable when we chop too close to the boundary. This works out because the tessellation
+ // shaders don't allow more than 2^10 parametric segments, and they snap the beginning and
+ // ending edges at 0 and 1. So if we overstep an inflection or point of 180-degree rotation by a
+ // fraction of a tessellation segment, it just gets snapped.
+ constexpr static float kEpsilon = 1.f / (1 << 11);
+ // Floating-point representation of "1 - 2*kEpsilon".
+ constexpr static uint32_t kIEEE_one_minus_2_epsilon = (127 << 23) - 2 * (1 << (24 - 11));
+ // Unfortunately we don't have a way to static_assert this, but we can runtime assert that the
+ // kIEEE_one_minus_2_epsilon bits are correct.
+ SkASSERT(sk_bit_cast<float>(kIEEE_one_minus_2_epsilon) == 1 - 2*kEpsilon);
+
+ float2 p0 = skvx::bit_pun<float2>(pts[0]);
+ float2 p1 = skvx::bit_pun<float2>(pts[1]);
+ float2 p2 = skvx::bit_pun<float2>(pts[2]);
+ float2 p3 = skvx::bit_pun<float2>(pts[3]);
+
+ // Find the cubic's power basis coefficients. These define the bezier curve as:
+ //
+ // |T^3|
+ // Cubic(T) = x,y = |A 3B 3C| * |T^2| + P0
+ // |. . .| |T |
+ //
+ // And the tangent direction (scaled by a uniform 1/3) will be:
+ //
+ // |T^2|
+ // Tangent_Direction(T) = dx,dy = |A 2B C| * |T |
+ // |. . .| |1 |
+ //
+ float2 C = p1 - p0;
+ float2 D = p2 - p1;
+ float2 E = p3 - p0;
+ float2 B = D - C;
+ float2 A = -3*D + E;
+
+ // Now find the cubic's inflection function. There are inflections where F' x F'' == 0.
+ // We formulate this as a quadratic equation: F' x F'' == aT^2 + bT + c == 0.
+ // See: https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
+ // NOTE: We only need the roots, so a uniform scale factor does not affect the solution.
+ float a = cross(A,B);
+ float b = cross(A,C);
+ float c = cross(B,C);
+ float b_over_minus_2 = -.5f * b;
+ float discr_over_4 = b_over_minus_2*b_over_minus_2 - a*c;
+
+ // If -cuspThreshold <= discr_over_4 <= cuspThreshold, it means the two roots are within
+ // kEpsilon of one another (in parametric space). This is close enough for our purposes to
+ // consider them a single cusp.
+ float cuspThreshold = a * (kEpsilon/2);
+ cuspThreshold *= cuspThreshold;
+
+ if (discr_over_4 < -cuspThreshold) {
+ // The curve does not inflect or cusp. This means it might rotate more than 180 degrees
+ // instead. Chop were rotation == 180 deg. (This is the 2nd root where the tangent is
+ // parallel to tan0.)
+ //
+ // Tangent_Direction(T) x tan0 == 0
+ // (AT^2 x tan0) + (2BT x tan0) + (C x tan0) == 0
+ // (A x C)T^2 + (2B x C)T + (C x C) == 0 [[because tan0 == P1 - P0 == C]]
+ // bT^2 + 2cT + 0 == 0 [[because A x C == b, B x C == c]]
+ // T = [0, -2c/b]
+ //
+ // NOTE: if C == 0, then C != tan0. But this is fine because the curve is definitely
+ // convex-180 if any points are colocated, and T[0] will equal NaN which returns 0 chops.
+ *areCusps = false;
+ float root = sk_ieee_float_divide(c, b_over_minus_2);
+ // Is "root" inside the range [kEpsilon, 1 - kEpsilon)?
+ if (sk_bit_cast<uint32_t>(root - kEpsilon) < kIEEE_one_minus_2_epsilon) {
+ T[0] = root;
+ return 1;
+ }
+ return 0;
+ }
+
+ *areCusps = (discr_over_4 <= cuspThreshold);
+ if (*areCusps) {
+ // The two roots are close enough that we can consider them a single cusp.
+ if (a != 0 || b_over_minus_2 != 0 || c != 0) {
+ // Pick the average of both roots.
+ float root = sk_ieee_float_divide(b_over_minus_2, a);
+ // Is "root" inside the range [kEpsilon, 1 - kEpsilon)?
+ if (sk_bit_cast<uint32_t>(root - kEpsilon) < kIEEE_one_minus_2_epsilon) {
+ T[0] = root;
+ return 1;
+ }
+ return 0;
+ }
+
+ // The curve is a flat line. The standard inflection function doesn't detect cusps from flat
+ // lines. Find cusps by searching instead for points where the tangent is perpendicular to
+ // tan0. This will find any cusp point.
+ //
+ // dot(tan0, Tangent_Direction(T)) == 0
+ //
+ // |T^2|
+ // tan0 * |A 2B C| * |T | == 0
+ // |. . .| |1 |
+ //
+ float2 tan0 = skvx::if_then_else(C != 0, C, p2 - p0);
+ a = dot(tan0, A);
+ b_over_minus_2 = -dot(tan0, B);
+ c = dot(tan0, C);
+ discr_over_4 = std::max(b_over_minus_2*b_over_minus_2 - a*c, 0.f);
+ }
+
+ // Solve our quadratic equation to find where to chop. See the quadratic formula from
+ // Numerical Recipes in C.
+ float q = sqrtf(discr_over_4);
+ q = copysignf(q, b_over_minus_2);
+ q = q + b_over_minus_2;
+ float2 roots = float2{q,c} / float2{a,q};
+
+ auto inside = (roots > kEpsilon) & (roots < (1 - kEpsilon));
+ if (inside[0]) {
+ if (inside[1] && roots[0] != roots[1]) {
+ if (roots[0] > roots[1]) {
+ roots = skvx::shuffle<1,0>(roots); // Sort.
+ }
+ roots.store(T);
+ return 2;
+ }
+ T[0] = roots[0];
+ return 1;
+ }
+ if (inside[1]) {
+ T[0] = roots[1];
+ return 1;
+ }
+ return 0;
+}
} // namespace skgpu
diff --git a/src/gpu/tessellate/Tessellation.h b/src/gpu/tessellate/Tessellation.h
index 127d28d..d1e52e2 100644
--- a/src/gpu/tessellate/Tessellation.h
+++ b/src/gpu/tessellate/Tessellation.h
@@ -140,6 +140,28 @@
const SkMatrix&,
const SkRect& viewport);
+// Finds 0, 1, or 2 T values at which to chop the given curve in order to guarantee the resulting
+// cubics are convex and rotate no more than 180 degrees.
+//
+// - If the cubic is "serpentine", then the T values are any inflection points in [0 < T < 1].
+// - If the cubic is linear, then the T values are any 180-degree cusp points in [0 < T < 1].
+// - Otherwise the T value is the point at which rotation reaches 180 degrees, iff in [0 < T < 1].
+//
+// 'areCusps' is set to true if the chop point occurred at a cusp (within tolerance), or if the chop
+// point(s) occurred at 180-degree turnaround points on a degenerate flat line.
+int FindCubicConvex180Chops(const SkPoint[], float T[2], bool* areCusps);
+
+// Returns true if the given conic (or quadratic) has a cusp point. The w value is not necessary in
+// determining this. If there is a cusp, it can be found at the midtangent.
+inline bool ConicHasCusp(const SkPoint p[3]) {
+ SkVector a = p[1] - p[0];
+ SkVector b = p[2] - p[1];
+ // A conic of any class can only have a cusp if it is a degenerate flat line with a 180 degree
+ // turnarund. To detect this, the beginning and ending tangents must be parallel
+ // (a.cross(b) == 0) and pointing in opposite directions (a.dot(b) < 0).
+ return a.cross(b) == 0 && a.dot(b) < 0;
+}
+
} // namespace skgpu
#endif // tessellate_Tessellation_DEFINED
diff --git a/tests/GrPathUtilsTest.cpp b/tests/FindCubicConvex180ChopsTest.cpp
similarity index 73%
rename from tests/GrPathUtilsTest.cpp
rename to tests/FindCubicConvex180ChopsTest.cpp
index 7fd0dc4..955d07f 100644
--- a/tests/GrPathUtilsTest.cpp
+++ b/tests/FindCubicConvex180ChopsTest.cpp
@@ -7,9 +7,11 @@
#include "include/utils/SkRandom.h"
#include "src/core/SkGeometry.h"
-#include "src/gpu/geometry/GrPathUtils.h"
+#include "src/gpu/tessellate/Tessellation.h"
#include "tests/Test.h"
+namespace skgpu {
+
static bool is_linear(SkPoint p0, SkPoint p1, SkPoint p2) {
return SkScalarNearlyZero((p0 - p1).cross(p2 - p1));
}
@@ -22,9 +24,9 @@
bool areCusps = false;
float inflectT[2], convex180T[2];
if (int inflectN = SkFindCubicInflections(p, inflectT)) {
- // The curve has inflections. findCubicConvex180Chops should return the inflection
+ // The curve has inflections. FindCubicConvex180Chops should return the inflection
// points.
- int convex180N = GrPathUtils::findCubicConvex180Chops(p, convex180T, &areCusps);
+ int convex180N = FindCubicConvex180Chops(p, convex180T, &areCusps);
REPORTER_ASSERT(r, inflectN == convex180N);
if (!areCusps) {
REPORTER_ASSERT(r, inflectN == 1 ||
@@ -35,7 +37,7 @@
}
} else {
float totalRotation = SkMeasureNonInflectCubicRotation(p);
- int convex180N = GrPathUtils::findCubicConvex180Chops(p, convex180T, &areCusps);
+ int convex180N = FindCubicConvex180Chops(p, convex180T, &areCusps);
SkPoint chops[10];
SkChopCubicAt(p, chops, convex180T, convex180N);
float radsSum = 0;
@@ -65,7 +67,7 @@
}
}
-DEF_TEST(GrPathUtils_findCubicConvex180Chops, r) {
+DEF_TEST(FindCubicConvex180Chops, r) {
// Test all combinations of corners from the square [0,0,1,1]. This covers every cubic type as
// well as a wide variety of special cases for cusps, lines, loops, and inflections.
for (int i = 0; i < (1 << 8); ++i) {
@@ -89,11 +91,11 @@
SkPoint quad[4] = {{0,0}, {2,2}, {4,2}, {6,0}};
float T[2];
bool areCusps;
- REPORTER_ASSERT(r, GrPathUtils::findCubicConvex180Chops(quad, T, &areCusps) == 0);
+ REPORTER_ASSERT(r, FindCubicConvex180Chops(quad, T, &areCusps) == 0);
// Now test that cusps and near-cusps get flagged as cusps.
SkPoint cusp[4] = {{0,0}, {1,1}, {1,0}, {0,1}};
- REPORTER_ASSERT(r, GrPathUtils::findCubicConvex180Chops(cusp, T, &areCusps) == 1);
+ REPORTER_ASSERT(r, FindCubicConvex180Chops(cusp, T, &areCusps) == 1);
REPORTER_ASSERT(r, areCusps == true);
// Find the height of the right side of "cusp" at which the distance between its inflection
@@ -110,33 +112,14 @@
// Ensure two inflection points barely more than kEpsilon apart do not get flagged as cusps.
cusp[1].fY = (float)(1 - 1.1 * dy);
cusp[2].fY = (float)(0 + 1.1 * dy);
- REPORTER_ASSERT(r, GrPathUtils::findCubicConvex180Chops(cusp, T, &areCusps) == 2);
+ REPORTER_ASSERT(r, FindCubicConvex180Chops(cusp, T, &areCusps) == 2);
REPORTER_ASSERT(r, areCusps == false);
// Ensure two inflection points barely less than kEpsilon apart do get flagged as cusps.
cusp[1].fY = (float)(1 - .9 * dy);
cusp[2].fY = (float)(0 + .9 * dy);
- REPORTER_ASSERT(r, GrPathUtils::findCubicConvex180Chops(cusp, T, &areCusps) == 1);
+ REPORTER_ASSERT(r, FindCubicConvex180Chops(cusp, T, &areCusps) == 1);
REPORTER_ASSERT(r, areCusps == true);
}
-DEF_TEST(GrPathUtils_convertToCubic, r) {
- SkPoint cubic[4];
- skgpu::VertexWriter cubicWriter(cubic);
- GrPathUtils::writeLineAsCubic({0,0}, {3,6}, &cubicWriter);
- REPORTER_ASSERT(r, cubic[0] == SkPoint::Make(0,0));
- REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[1].fX, 1));
- REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[1].fY, 2));
- REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[2].fX, 2));
- REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[2].fY, 4));
- REPORTER_ASSERT(r, cubic[3] == SkPoint::Make(3,6));
-
- SkPoint quad[3] = {{0,0}, {3,3}, {6,0}};
- GrPathUtils::convertQuadToCubic(quad, cubic);
- REPORTER_ASSERT(r, cubic[0] == SkPoint::Make(0,0));
- REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[1].fX, 2));
- REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[1].fY, 2));
- REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[2].fX, 4));
- REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[2].fY, 2));
- REPORTER_ASSERT(r, cubic[3] == SkPoint::Make(6,0));
-}
+} // namespace skgpu
