Duplicates code from GrPathUtils to verify that an approximation for the number
of points in a quadratic curve is within +/- 2x the value determined by the
previous expensive method.
Running a similar approximation method on the Guimark2 HTML5 Charting demo drops
the share of time spent in SkPoint::distanceToLineSegmentBetweenSqd() from 4.57%
to under 0.6%, although SkPath::Iter::next(), SkPath::lineTo(), and
GrPathUtils::quadraticPointCount() all increase a bit.
Using a similar approximation method for SampleSlides.cpp produces visually
reasonable results. Without a relevant gm (it looks like gm/pathfill.cpp doesn't
have explicit quadratics?) I'm not sure how to get a better output quality
test.
We could avoid code duplication by:
- have two implementations in GrPathUtils (computedQuadraticPointCount() &
estimatedQuadraticPointCount() are my working titles)
- use a #define to select between them at compile time
- expose both of them in the header file for this test to access
git-svn-id: http://skia.googlecode.com/svn/trunk@1540 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/tests/PathCoverageTest.cpp b/tests/PathCoverageTest.cpp
new file mode 100644
index 0000000..8676029
--- /dev/null
+++ b/tests/PathCoverageTest.cpp
@@ -0,0 +1,129 @@
+#include "SkPoint.h"
+#include "SkScalar.h"
+#include "Test.h"
+
+/*
+ Duplicates lots of code from gpu/src/GrPathUtils.cpp
+ It'd be nice not to do so, but that code's set up currently to only have a single implementation.
+*/
+
+#define MAX_COEFF_SHIFT 6
+static const uint32_t MAX_POINTS_PER_CURVE = 1 << MAX_COEFF_SHIFT;
+
+static inline int cheap_distance(SkScalar dx, SkScalar dy) {
+ int idx = SkAbs32(SkScalarRound(dx));
+ int idy = SkAbs32(SkScalarRound(dy));
+ if (idx > idy) {
+ idx += idy >> 1;
+ } else {
+ idx = idy + (idx >> 1);
+ }
+ return idx;
+}
+
+static inline int diff_to_shift(SkScalar dx, SkScalar dy) {
+ int dist = cheap_distance(dx, dy);
+ return (32 - SkCLZ(dist));
+}
+
+uint32_t estimatedQuadraticPointCount(const SkPoint points[], SkScalar tol) {
+ int shift = diff_to_shift(points[1].fX * 2 - points[2].fX - points[0].fX,
+ points[1].fY * 2 - points[2].fY - points[0].fY);
+ SkASSERT(shift >= 0);
+ //SkDebugf("Quad shift %d;", shift);
+ // bias to more closely approximate exact value, then clamp to zero
+ shift -= 2;
+ shift &= ~(shift>>31);
+
+ if (shift > MAX_COEFF_SHIFT) {
+ shift = MAX_COEFF_SHIFT;
+ }
+ uint32_t count = 1 << shift;
+ //SkDebugf(" biased shift %d, scale %u\n", shift, count);
+ return count;
+}
+
+uint32_t computedQuadraticPointCount(const SkPoint points[], SkScalar tol) {
+ SkScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]);
+ if (d < tol) {
+ return 1;
+ } else {
+ int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol)));
+ uint32_t count = SkMinScalar(SkNextPow2(temp), MAX_POINTS_PER_CURVE);
+ return count;
+ }
+}
+
+// Curve from samplecode/SampleSlides.cpp
+static const int gXY[] = {
+ 4, 0, 0, -4, 8, -4, 12, 0, 8, 4, 0, 4
+};
+
+static const int gSawtooth[] = {
+ 0, 0, 10, 10, 20, 20, 30, 10, 40, 0, 50, -10, 60, -20, 70, -10, 80, 0
+};
+
+static const int gOvalish[] = {
+ 0, 0, 5, 15, 20, 20, 35, 15, 40, 0
+};
+
+static const int gSharpSawtooth[] = {
+ 0, 0, 1, 10, 2, 0, 3, -10, 4, 0
+};
+
+// Curve crosses back over itself around 0,10
+static const int gRibbon[] = {
+ -4, 0, 4, 20, 0, 25, -4, 20, 4, 0
+};
+
+static bool one_d_pe(const int* array, const unsigned int count,
+ skiatest::Reporter* reporter) {
+ SkPoint path [3];
+ path[1] = SkPoint::Make(SkIntToScalar(array[0]), SkIntToScalar(array[1]));
+ path[2] = SkPoint::Make(SkIntToScalar(array[2]), SkIntToScalar(array[3]));
+ int numErrors = 0;
+ for (unsigned i = 4; i < (count); i += 2) {
+ path[0] = path[1];
+ path[1] = path[2];
+ path[2] = SkPoint::Make(SkIntToScalar(array[i]),
+ SkIntToScalar(array[i+1]));
+ uint32_t computedCount =
+ computedQuadraticPointCount(path, SkIntToScalar(1));
+ uint32_t estimatedCount =
+ estimatedQuadraticPointCount(path, SkIntToScalar(1));
+ // Allow estimated to be off by a factor of two, but no more.
+ if ((estimatedCount > 2 * computedCount) ||
+ (computedCount > estimatedCount * 2)) {
+ SkString errorDescription;
+ errorDescription.printf(
+ "Curve from %.2f %.2f through %.2f %.2f to %.2f %.2f "
+ "computes %d, estimates %d\n",
+ path[0].fX, path[0].fY, path[1].fX, path[1].fY,
+ path[2].fX, path[2].fY, computedCount, estimatedCount);
+ numErrors++;
+ reporter->reportFailed(errorDescription);
+ }
+ }
+
+ if (numErrors > 0)
+ printf("%d curve segments differ\n", numErrors);
+ return (numErrors == 0);
+}
+
+
+
+static void TestQuadPointCount(skiatest::Reporter* reporter) {
+ one_d_pe(gXY, SK_ARRAY_COUNT(gXY), reporter);
+ one_d_pe(gSawtooth, SK_ARRAY_COUNT(gSawtooth), reporter);
+ one_d_pe(gOvalish, SK_ARRAY_COUNT(gOvalish), reporter);
+ one_d_pe(gSharpSawtooth, SK_ARRAY_COUNT(gSharpSawtooth), reporter);
+ one_d_pe(gRibbon, SK_ARRAY_COUNT(gRibbon), reporter);
+}
+
+static void TestPathCoverage(skiatest::Reporter* reporter) {
+ TestQuadPointCount(reporter);
+
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("PathCoverage", PathCoverageTestClass, TestPathCoverage)