Use Wang's formula for quadratic and cubic point counts
- most of the small diffs are because I moved GrWangsFormula.h out
of the tessellate/ directory and into the geometry/ directory since
it's more general than HW tessellation.
The previous implementation was based on the heuristic that the distance
from the true curve to the line segment would be divided by 4 every time
the curve was recursively subdivided. This was a reasonable
approximation if the curve had balanced curvature on both sides of the
split. However, in the case of the new GM's curve, the left half was
already very linear and the right half had much higher curves.
This lead to the approximation reporting fewer points than required.
Theoretically, those few points that weren't utilized by the left half
of the curve could have been made available to the right half, but the
implementation of that would be tricky.
Instead, it now uses Wang's formula to compute the number of points.
Since recursive subdivision leads to linearly spaced samples assuming it
can't stop early, this point count represents a valid upper bound on
what's needed. It also then ensures both left and right halves of a
curve have the point counts they might need w/o updating the
generation implementations. However, since the recursive point
generation exits once each section has reached the error tolerance, in
scenarios where the prior approximation was reasonable, we'll end up
using fewer points than reported by Wang's. Hopefully that means there
is negligible performance regression since we won't be increasing
vertex counts by that much (except where needed for correctness).
Bug: skia:11886
Change-Id: Iba39dbe4de82011775524583efd461b10c9259fe
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/405197
Reviewed-by: Chris Dalton <csmartdalton@google.com>
Reviewed-by: Brian Salomon <bsalomon@google.com>
Commit-Queue: Michael Ludwig <michaelludwig@google.com>
diff --git a/bench/TessellateBench.cpp b/bench/TessellateBench.cpp
index 62e0e19..83fcb3b 100644
--- a/bench/TessellateBench.cpp
+++ b/bench/TessellateBench.cpp
@@ -10,13 +10,13 @@
#include "src/core/SkPathPriv.h"
#include "src/gpu/GrDirectContextPriv.h"
#include "src/gpu/GrOpFlushState.h"
+#include "src/gpu/geometry/GrWangsFormula.h"
#include "src/gpu/mock/GrMockOpTarget.h"
#include "src/gpu/tessellate/GrMiddleOutPolygonTriangulator.h"
#include "src/gpu/tessellate/GrPathTessellator.h"
#include "src/gpu/tessellate/GrStrokeFixedCountTessellator.h"
#include "src/gpu/tessellate/GrStrokeHardwareTessellator.h"
#include "src/gpu/tessellate/GrStrokeIndirectTessellator.h"
-#include "src/gpu/tessellate/GrWangsFormula.h"
#include "tools/ToolUtils.h"
#include <vector>
diff --git a/gm/pathfill.cpp b/gm/pathfill.cpp
index 059862b..e7dd478 100644
--- a/gm/pathfill.cpp
+++ b/gm/pathfill.cpp
@@ -704,3 +704,13 @@
canvas->scale(2, 2);
canvas->drawPath(path, paint);
}
+
+DEF_SIMPLE_GM(path_skbug_11886, canvas, 256, 256) {
+ SkPoint m = {0.f, 770.f};
+ SkPath path;
+ path.moveTo(m);
+ path.cubicTo(m + SkPoint{0.f, 1.f}, m + SkPoint{20.f, -750.f}, m + SkPoint{83.f, -746.f});
+ SkPaint paint;
+ paint.setAntiAlias(true);
+ canvas->drawPath(path, paint);
+}
diff --git a/gn/gpu.gni b/gn/gpu.gni
index ba69292..b2fbc8e 100644
--- a/gn/gpu.gni
+++ b/gn/gpu.gni
@@ -367,6 +367,7 @@
"$_src/gpu/geometry/GrShape.h",
"$_src/gpu/geometry/GrStyledShape.cpp",
"$_src/gpu/geometry/GrStyledShape.h",
+ "$_src/gpu/geometry/GrWangsFormula.h",
"$_src/gpu/ops/GrAAConvexPathRenderer.cpp",
"$_src/gpu/ops/GrAAConvexPathRenderer.h",
"$_src/gpu/ops/GrAAConvexTessellator.cpp",
@@ -482,7 +483,6 @@
"$_src/gpu/tessellate/GrTessellationPathRenderer.cpp",
"$_src/gpu/tessellate/GrTessellationPathRenderer.h",
"$_src/gpu/tessellate/GrVectorXform.h",
- "$_src/gpu/tessellate/GrWangsFormula.h",
# text
"$_src/gpu/text/GrAtlasManager.cpp",
diff --git a/samplecode/SampleTessellatedWedge.cpp b/samplecode/SampleTessellatedWedge.cpp
index cbd874d..bb40896 100644
--- a/samplecode/SampleTessellatedWedge.cpp
+++ b/samplecode/SampleTessellatedWedge.cpp
@@ -19,8 +19,8 @@
#include "src/gpu/GrMemoryPool.h"
#include "src/gpu/GrRecordingContextPriv.h"
#include "src/gpu/GrSurfaceDrawContext.h"
+#include "src/gpu/geometry/GrWangsFormula.h"
#include "src/gpu/tessellate/GrPathStencilFillOp.h"
-#include "src/gpu/tessellate/GrWangsFormula.h"
static float kConicWeight = .5;
diff --git a/src/gpu/geometry/GrPathUtils.cpp b/src/gpu/geometry/GrPathUtils.cpp
index 453ea16..3df73b1 100644
--- a/src/gpu/geometry/GrPathUtils.cpp
+++ b/src/gpu/geometry/GrPathUtils.cpp
@@ -11,8 +11,23 @@
#include "src/core/SkMathPriv.h"
#include "src/core/SkPointPriv.h"
#include "src/core/SkUtils.h"
+#include "src/gpu/geometry/GrWangsFormula.h"
-static const SkScalar gMinCurveTol = 0.0001f;
+static const SkScalar kMinCurveTol = 0.0001f;
+
+static float tolerance_to_wangs_precision(float srcTol) {
+ // You should have called scaleToleranceToSrc, which guarantees this
+ SkASSERT(srcTol >= kMinCurveTol);
+
+ // The GrPathUtil API defines tolerance as the max distance the linear segment can be from
+ // the real curve. Wang's formula guarantees the linear segments will be within 1/precision
+ // of the true curve, so precision = 1/srcTol
+ return 1.f / srcTol;
+}
+
+uint32_t max_bezier_vertices(uint32_t chopCount) {
+ return std::min(1 << chopCount, GrPathUtils::kMaxPointsPerCurve);
+}
SkScalar GrPathUtils::scaleToleranceToSrc(SkScalar devTol,
const SkMatrix& viewM,
@@ -40,41 +55,15 @@
} else {
srcTol = devTol / stretch;
}
- if (srcTol < gMinCurveTol) {
- srcTol = gMinCurveTol;
+ if (srcTol < kMinCurveTol) {
+ srcTol = kMinCurveTol;
}
return srcTol;
}
uint32_t GrPathUtils::quadraticPointCount(const SkPoint points[], SkScalar tol) {
- // You should have called scaleToleranceToSrc, which guarantees this
- SkASSERT(tol >= gMinCurveTol);
-
- SkScalar d = SkPointPriv::DistanceToLineSegmentBetween(points[1], points[0], points[2]);
- if (!SkScalarIsFinite(d)) {
- return kMaxPointsPerCurve;
- } else if (d <= tol) {
- return 1;
- } else {
- // Each time we subdivide, d should be cut in 4. So we need to
- // subdivide x = log4(d/tol) times. x subdivisions creates 2^(x)
- // points.
- // 2^(log4(x)) = sqrt(x);
- SkScalar divSqrt = SkScalarSqrt(d / tol);
- if (((SkScalar)SK_MaxS32) <= divSqrt) {
- return kMaxPointsPerCurve;
- } else {
- int temp = SkScalarCeilToInt(divSqrt);
- int pow2 = GrNextPow2(temp);
- // Because of NaNs & INFs we can wind up with a degenerate temp
- // such that pow2 comes out negative. Also, our point generator
- // will always output at least one pt.
- if (pow2 < 1) {
- pow2 = 1;
- }
- return std::min(pow2, kMaxPointsPerCurve);
- }
- }
+ return max_bezier_vertices(GrWangsFormula::quadratic_log2(
+ tolerance_to_wangs_precision(tol), points));
}
uint32_t GrPathUtils::generateQuadraticPoints(const SkPoint& p0,
@@ -102,35 +91,9 @@
return a + b;
}
-uint32_t GrPathUtils::cubicPointCount(const SkPoint points[],
- SkScalar tol) {
- // You should have called scaleToleranceToSrc, which guarantees this
- SkASSERT(tol >= gMinCurveTol);
-
- SkScalar d = std::max(
- SkPointPriv::DistanceToLineSegmentBetweenSqd(points[1], points[0], points[3]),
- SkPointPriv::DistanceToLineSegmentBetweenSqd(points[2], points[0], points[3]));
- d = SkScalarSqrt(d);
- if (!SkScalarIsFinite(d)) {
- return kMaxPointsPerCurve;
- } else if (d <= tol) {
- return 1;
- } else {
- SkScalar divSqrt = SkScalarSqrt(d / tol);
- if (((SkScalar)SK_MaxS32) <= divSqrt) {
- return kMaxPointsPerCurve;
- } else {
- int temp = SkScalarCeilToInt(SkScalarSqrt(d / tol));
- int pow2 = GrNextPow2(temp);
- // Because of NaNs & INFs we can wind up with a degenerate temp
- // such that pow2 comes out negative. Also, our point generator
- // will always output at least one pt.
- if (pow2 < 1) {
- pow2 = 1;
- }
- return std::min(pow2, kMaxPointsPerCurve);
- }
- }
+uint32_t GrPathUtils::cubicPointCount(const SkPoint points[], SkScalar tol) {
+ return max_bezier_vertices(GrWangsFormula::cubic_log2(
+ tolerance_to_wangs_precision(tol), points));
}
uint32_t GrPathUtils::generateCubicPoints(const SkPoint& p0,
diff --git a/src/gpu/geometry/GrPathUtils.h b/src/gpu/geometry/GrPathUtils.h
index fdbd45c..fd68f78 100644
--- a/src/gpu/geometry/GrPathUtils.h
+++ b/src/gpu/geometry/GrPathUtils.h
@@ -21,14 +21,28 @@
*/
namespace GrPathUtils {
+// When tessellating curved paths into linear segments, this defines the maximum distance in screen
+// space which a segment may deviate from the mathematically correct value. Above this value, the
+// segment will be subdivided.
+// This value was chosen to approximate the supersampling accuracy of the raster path (16 samples,
+// or one quarter pixel).
+static const SkScalar kDefaultTolerance = SkDoubleToScalar(0.25);
+
+// We guarantee that no quad or cubic will ever produce more than this many points
+static const int kMaxPointsPerCurve = 1 << 10;
+
// Very small tolerances will be increased to a minimum threshold value, to avoid division problems
// in subsequent math.
SkScalar scaleToleranceToSrc(SkScalar devTol,
const SkMatrix& viewM,
const SkRect& pathBounds);
+// Returns the maximum number of vertices required when using a recursive chopping algorithm to
+// linearize the quadratic Bezier (e.g. generateQuadraticPoints below) to the given error tolerance.
+// This is a power of two and will not exceed kMaxPointsPerCurve.
uint32_t quadraticPointCount(const SkPoint points[], SkScalar tol);
+// Returns the number of points actually written to 'points', will be <= to 'pointsLeft'
uint32_t generateQuadraticPoints(const SkPoint& p0,
const SkPoint& p1,
const SkPoint& p2,
@@ -36,8 +50,12 @@
SkPoint** points,
uint32_t pointsLeft);
+// Returns the maximum number of vertices required when using a recursive chopping algorithm to
+// linearize the cubic Bezier (e.g. generateQuadraticPoints below) to the given error tolerance.
+// This is a power of two and will not exceed kMaxPointsPerCurve.
uint32_t cubicPointCount(const SkPoint points[], SkScalar tol);
+// Returns the number of points actually written to 'points', will be <= to 'pointsLeft'
uint32_t generateCubicPoints(const SkPoint& p0,
const SkPoint& p1,
const SkPoint& p2,
@@ -114,16 +132,6 @@
SkPathFirstDirection dir,
SkTArray<SkPoint, true>* quads);
-// When tessellating curved paths into linear segments, this defines the maximum distance in screen
-// space which a segment may deviate from the mathematically correct value. Above this value, the
-// segment will be subdivided.
-// This value was chosen to approximate the supersampling accuracy of the raster path (16 samples,
-// or one quarter pixel).
-static const SkScalar kDefaultTolerance = SkDoubleToScalar(0.25);
-
-// We guarantee that no quad or cubic will ever produce more than this many points
-static const int kMaxPointsPerCurve = 1 << 10;
-
// 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.
diff --git a/src/gpu/tessellate/GrWangsFormula.h b/src/gpu/geometry/GrWangsFormula.h
similarity index 100%
rename from src/gpu/tessellate/GrWangsFormula.h
rename to src/gpu/geometry/GrWangsFormula.h
diff --git a/src/gpu/tessellate/GrPathTessellator.cpp b/src/gpu/tessellate/GrPathTessellator.cpp
index 573a0c1..24db640 100644
--- a/src/gpu/tessellate/GrPathTessellator.cpp
+++ b/src/gpu/tessellate/GrPathTessellator.cpp
@@ -10,10 +10,10 @@
#include "src/gpu/GrEagerVertexAllocator.h"
#include "src/gpu/GrGpu.h"
#include "src/gpu/geometry/GrPathUtils.h"
+#include "src/gpu/geometry/GrWangsFormula.h"
#include "src/gpu/tessellate/GrMiddleOutPolygonTriangulator.h"
#include "src/gpu/tessellate/GrMidpointContourParser.h"
#include "src/gpu/tessellate/GrStencilPathShader.h"
-#include "src/gpu/tessellate/GrWangsFormula.h"
GrPathIndirectTessellator::GrPathIndirectTessellator(const SkMatrix& viewMatrix, const SkPath& path,
DrawInnerFan drawInnerFan)
diff --git a/src/gpu/tessellate/GrStrokeFixedCountTessellator.cpp b/src/gpu/tessellate/GrStrokeFixedCountTessellator.cpp
index 8b3e39f..3374ffe 100644
--- a/src/gpu/tessellate/GrStrokeFixedCountTessellator.cpp
+++ b/src/gpu/tessellate/GrStrokeFixedCountTessellator.cpp
@@ -9,8 +9,8 @@
#include "src/core/SkGeometry.h"
#include "src/gpu/geometry/GrPathUtils.h"
+#include "src/gpu/geometry/GrWangsFormula.h"
#include "src/gpu/tessellate/GrStrokeIterator.h"
-#include "src/gpu/tessellate/GrWangsFormula.h"
namespace {
diff --git a/src/gpu/tessellate/GrStrokeHardwareTessellator.cpp b/src/gpu/tessellate/GrStrokeHardwareTessellator.cpp
index e86a4ef..d9d3ca1 100644
--- a/src/gpu/tessellate/GrStrokeHardwareTessellator.cpp
+++ b/src/gpu/tessellate/GrStrokeHardwareTessellator.cpp
@@ -11,7 +11,7 @@
#include "src/gpu/GrRecordingContextPriv.h"
#include "src/gpu/GrVx.h"
#include "src/gpu/geometry/GrPathUtils.h"
-#include "src/gpu/tessellate/GrWangsFormula.h"
+#include "src/gpu/geometry/GrWangsFormula.h"
namespace {
diff --git a/src/gpu/tessellate/GrStrokeIndirectTessellator.cpp b/src/gpu/tessellate/GrStrokeIndirectTessellator.cpp
index 06e8d90..593b38f 100644
--- a/src/gpu/tessellate/GrStrokeIndirectTessellator.cpp
+++ b/src/gpu/tessellate/GrStrokeIndirectTessellator.cpp
@@ -13,9 +13,9 @@
#include "src/gpu/GrVertexWriter.h"
#include "src/gpu/GrVx.h"
#include "src/gpu/geometry/GrPathUtils.h"
+#include "src/gpu/geometry/GrWangsFormula.h"
#include "src/gpu/tessellate/GrStrokeIterator.h"
#include "src/gpu/tessellate/GrStrokeTessellateShader.h"
-#include "src/gpu/tessellate/GrWangsFormula.h"
namespace {
diff --git a/src/gpu/tessellate/GrStrokeTessellateShader.cpp b/src/gpu/tessellate/GrStrokeTessellateShader.cpp
index 16b64ec..2dd543a 100644
--- a/src/gpu/tessellate/GrStrokeTessellateShader.cpp
+++ b/src/gpu/tessellate/GrStrokeTessellateShader.cpp
@@ -7,12 +7,12 @@
#include "src/gpu/tessellate/GrStrokeTessellateShader.h"
+#include "src/gpu/geometry/GrWangsFormula.h"
#include "src/gpu/glsl/GrGLSLFragmentShaderBuilder.h"
#include "src/gpu/glsl/GrGLSLGeometryProcessor.h"
#include "src/gpu/glsl/GrGLSLVarying.h"
#include "src/gpu/glsl/GrGLSLVertexGeoBuilder.h"
#include "src/gpu/tessellate/GrStrokeTessellator.h"
-#include "src/gpu/tessellate/GrWangsFormula.h"
// The built-in atan() is undefined when x==0. This method relieves that restriction, but also can
// return values larger than 2*PI. This shouldn't matter for our purposes.
diff --git a/src/gpu/tessellate/GrTessellationPathRenderer.cpp b/src/gpu/tessellate/GrTessellationPathRenderer.cpp
index 106efd2..8fbe6c9 100644
--- a/src/gpu/tessellate/GrTessellationPathRenderer.cpp
+++ b/src/gpu/tessellate/GrTessellationPathRenderer.cpp
@@ -15,12 +15,12 @@
#include "src/gpu/GrRecordingContextPriv.h"
#include "src/gpu/GrSurfaceDrawContext.h"
#include "src/gpu/geometry/GrStyledShape.h"
+#include "src/gpu/geometry/GrWangsFormula.h"
#include "src/gpu/ops/GrFillRectOp.h"
#include "src/gpu/tessellate/GrDrawAtlasPathOp.h"
#include "src/gpu/tessellate/GrPathInnerTriangulateOp.h"
#include "src/gpu/tessellate/GrPathStencilFillOp.h"
#include "src/gpu/tessellate/GrStrokeTessellateOp.h"
-#include "src/gpu/tessellate/GrWangsFormula.h"
constexpr static SkISize kAtlasInitialSize{512, 512};
constexpr static int kMaxAtlasSize = 2048;
diff --git a/tests/StrokeIndirectTest.cpp b/tests/StrokeIndirectTest.cpp
index 0d3a6b0..39dd0be 100644
--- a/tests/StrokeIndirectTest.cpp
+++ b/tests/StrokeIndirectTest.cpp
@@ -10,11 +10,11 @@
#include "include/private/SkFloatingPoint.h"
#include "src/core/SkGeometry.h"
#include "src/gpu/geometry/GrPathUtils.h"
+#include "src/gpu/geometry/GrWangsFormula.h"
#include "src/gpu/mock/GrMockOpTarget.h"
#include "src/gpu/tessellate/GrStrokeIndirectTessellator.h"
#include "src/gpu/tessellate/GrStrokeTessellateShader.h"
#include "src/gpu/tessellate/GrTessellationPathRenderer.h"
-#include "src/gpu/tessellate/GrWangsFormula.h"
static sk_sp<GrDirectContext> make_mock_context() {
GrMockOptions mockOptions;
diff --git a/tests/WangsFormulaTest.cpp b/tests/WangsFormulaTest.cpp
index 6d3bdff..768480c 100644
--- a/tests/WangsFormulaTest.cpp
+++ b/tests/WangsFormulaTest.cpp
@@ -7,7 +7,7 @@
#include "include/utils/SkRandom.h"
#include "src/core/SkGeometry.h"
-#include "src/gpu/tessellate/GrWangsFormula.h"
+#include "src/gpu/geometry/GrWangsFormula.h"
#include "tests/Test.h"
constexpr static int kPrecision = 4; // 1/4 pixel max error.
