From ddab2276cb09d0c74018af45184ae93138e3230b Mon Sep 17 00:00:00 2001 From: "tomhudson@google.com" Date: Wed, 8 Jun 2011 14:46:28 +0000 Subject: 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 --- tests/PathCoverageTest.cpp | 129 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 129 insertions(+) create mode 100644 tests/PathCoverageTest.cpp (limited to 'tests/PathCoverageTest.cpp') diff --git a/tests/PathCoverageTest.cpp b/tests/PathCoverageTest.cpp new file mode 100644 index 0000000000..8676029b33 --- /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) -- cgit v1.2.3