epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 1 | |
| 2 | /* |
| 3 | * Copyright 2011 Google Inc. |
| 4 | * |
| 5 | * Use of this source code is governed by a BSD-style license that can be |
| 6 | * found in the LICENSE file. |
| 7 | */ |
tomhudson@google.com | 889bd8b | 2011-09-27 17:38:17 +0000 | [diff] [blame] | 8 | #include "SkMath.h" |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 9 | #include "SkPoint.h" |
| 10 | #include "SkScalar.h" |
| 11 | #include "Test.h" |
| 12 | |
| 13 | /* |
| 14 | Duplicates lots of code from gpu/src/GrPathUtils.cpp |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 15 | It'd be nice not to do so, but that code's set up currently to only have |
| 16 | a single implementation. |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 17 | */ |
| 18 | |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 19 | // Sk uses 6, Gr (implicitly) used 10, both apparently arbitrarily. |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 20 | #define MAX_COEFF_SHIFT 6 |
| 21 | static const uint32_t MAX_POINTS_PER_CURVE = 1 << MAX_COEFF_SHIFT; |
| 22 | |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 23 | // max + 0.5 min has error [0.0, 0.12] |
| 24 | // max + 0.375 min has error [-.03, 0.07] |
| 25 | // 0.96043387 max + 0.397824735 min has error [-.06, +.05] |
| 26 | // For determining the maximum possible number of points to use in |
| 27 | // drawing a quadratic, we want to err on the high side. |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 28 | static inline int cheap_distance(SkScalar dx, SkScalar dy) { |
| 29 | int idx = SkAbs32(SkScalarRound(dx)); |
| 30 | int idy = SkAbs32(SkScalarRound(dy)); |
| 31 | if (idx > idy) { |
| 32 | idx += idy >> 1; |
| 33 | } else { |
| 34 | idx = idy + (idx >> 1); |
| 35 | } |
| 36 | return idx; |
| 37 | } |
| 38 | |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 39 | static inline int estimate_distance(const SkPoint points[]) { |
| 40 | return cheap_distance(points[1].fX * 2 - points[2].fX - points[0].fX, |
| 41 | points[1].fY * 2 - points[2].fY - points[0].fY); |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 42 | } |
| 43 | |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 44 | static inline SkScalar compute_distance(const SkPoint points[]) { |
| 45 | return points[1].distanceToLineSegmentBetween(points[0], points[2]); |
| 46 | } |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 47 | |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 48 | static inline uint32_t estimate_pointCount(int distance) { |
| 49 | // Includes -2 bias because this estimator runs 4x high? |
| 50 | int shift = 30 - SkCLZ(distance); |
| 51 | // Clamp to zero if above subtraction went negative. |
| 52 | shift &= ~(shift>>31); |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 53 | if (shift > MAX_COEFF_SHIFT) { |
| 54 | shift = MAX_COEFF_SHIFT; |
| 55 | } |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 56 | return 1 << shift; |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 57 | } |
| 58 | |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 59 | static inline uint32_t compute_pointCount(SkScalar d, SkScalar tol) { |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 60 | if (d < tol) { |
| 61 | return 1; |
| 62 | } else { |
robertphillips@google.com | 6853e80 | 2012-04-16 15:50:18 +0000 | [diff] [blame] | 63 | int temp = SkScalarCeilToInt(SkScalarSqrt(SkScalarDiv(d, tol))); |
| 64 | uint32_t count = SkMin32(SkNextPow2(temp), MAX_POINTS_PER_CURVE); |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 65 | return count; |
| 66 | } |
| 67 | } |
| 68 | |
caryclark@google.com | 42639cd | 2012-06-06 12:03:39 +0000 | [diff] [blame] | 69 | static uint32_t quadraticPointCount_EE(const SkPoint points[], SkScalar tol) { |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 70 | int distance = estimate_distance(points); |
| 71 | return estimate_pointCount(distance); |
| 72 | } |
| 73 | |
caryclark@google.com | 42639cd | 2012-06-06 12:03:39 +0000 | [diff] [blame] | 74 | static uint32_t quadraticPointCount_EC(const SkPoint points[], SkScalar tol) { |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 75 | int distance = estimate_distance(points); |
| 76 | return compute_pointCount(SkIntToScalar(distance), tol); |
| 77 | } |
| 78 | |
caryclark@google.com | 42639cd | 2012-06-06 12:03:39 +0000 | [diff] [blame] | 79 | static uint32_t quadraticPointCount_CE(const SkPoint points[], SkScalar tol) { |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 80 | SkScalar distance = compute_distance(points); |
| 81 | return estimate_pointCount(SkScalarRound(distance)); |
| 82 | } |
| 83 | |
caryclark@google.com | 42639cd | 2012-06-06 12:03:39 +0000 | [diff] [blame] | 84 | static uint32_t quadraticPointCount_CC(const SkPoint points[], SkScalar tol) { |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 85 | SkScalar distance = compute_distance(points); |
| 86 | return compute_pointCount(distance, tol); |
| 87 | } |
| 88 | |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 89 | // Curve from samplecode/SampleSlides.cpp |
| 90 | static const int gXY[] = { |
| 91 | 4, 0, 0, -4, 8, -4, 12, 0, 8, 4, 0, 4 |
| 92 | }; |
| 93 | |
| 94 | static const int gSawtooth[] = { |
| 95 | 0, 0, 10, 10, 20, 20, 30, 10, 40, 0, 50, -10, 60, -20, 70, -10, 80, 0 |
| 96 | }; |
| 97 | |
| 98 | static const int gOvalish[] = { |
| 99 | 0, 0, 5, 15, 20, 20, 35, 15, 40, 0 |
| 100 | }; |
| 101 | |
| 102 | static const int gSharpSawtooth[] = { |
| 103 | 0, 0, 1, 10, 2, 0, 3, -10, 4, 0 |
| 104 | }; |
| 105 | |
| 106 | // Curve crosses back over itself around 0,10 |
| 107 | static const int gRibbon[] = { |
| 108 | -4, 0, 4, 20, 0, 25, -4, 20, 4, 0 |
| 109 | }; |
| 110 | |
| 111 | static bool one_d_pe(const int* array, const unsigned int count, |
| 112 | skiatest::Reporter* reporter) { |
| 113 | SkPoint path [3]; |
| 114 | path[1] = SkPoint::Make(SkIntToScalar(array[0]), SkIntToScalar(array[1])); |
| 115 | path[2] = SkPoint::Make(SkIntToScalar(array[2]), SkIntToScalar(array[3])); |
| 116 | int numErrors = 0; |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 117 | for (unsigned i = 4; i < count; i += 2) { |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 118 | path[0] = path[1]; |
| 119 | path[1] = path[2]; |
| 120 | path[2] = SkPoint::Make(SkIntToScalar(array[i]), |
| 121 | SkIntToScalar(array[i+1])); |
| 122 | uint32_t computedCount = |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 123 | quadraticPointCount_CC(path, SkIntToScalar(1)); |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 124 | uint32_t estimatedCount = |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 125 | quadraticPointCount_EE(path, SkIntToScalar(1)); |
caryclark@google.com | 42639cd | 2012-06-06 12:03:39 +0000 | [diff] [blame] | 126 | |
| 127 | if (false) { // avoid bit rot, suppress warning |
| 128 | computedCount = |
| 129 | quadraticPointCount_EC(path, SkIntToScalar(1)); |
| 130 | estimatedCount = |
| 131 | quadraticPointCount_CE(path, SkIntToScalar(1)); |
| 132 | } |
tomhudson@google.com | fc1539a | 2011-06-24 15:43:24 +0000 | [diff] [blame] | 133 | // Allow estimated to be high by a factor of two, but no less than |
| 134 | // the computed value. |
| 135 | bool isAccurate = (estimatedCount >= computedCount) && |
| 136 | (estimatedCount <= 2 * computedCount); |
| 137 | |
| 138 | if (!isAccurate) { |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 139 | SkString errorDescription; |
| 140 | errorDescription.printf( |
| 141 | "Curve from %.2f %.2f through %.2f %.2f to %.2f %.2f " |
| 142 | "computes %d, estimates %d\n", |
| 143 | path[0].fX, path[0].fY, path[1].fX, path[1].fY, |
| 144 | path[2].fX, path[2].fY, computedCount, estimatedCount); |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 145 | numErrors++; |
| 146 | reporter->reportFailed(errorDescription); |
| 147 | } |
| 148 | } |
| 149 | |
tomhudson@google.com | ddab227 | 2011-06-08 14:46:28 +0000 | [diff] [blame] | 150 | return (numErrors == 0); |
| 151 | } |
| 152 | |
| 153 | |
| 154 | |
| 155 | static void TestQuadPointCount(skiatest::Reporter* reporter) { |
| 156 | one_d_pe(gXY, SK_ARRAY_COUNT(gXY), reporter); |
| 157 | one_d_pe(gSawtooth, SK_ARRAY_COUNT(gSawtooth), reporter); |
| 158 | one_d_pe(gOvalish, SK_ARRAY_COUNT(gOvalish), reporter); |
| 159 | one_d_pe(gSharpSawtooth, SK_ARRAY_COUNT(gSharpSawtooth), reporter); |
| 160 | one_d_pe(gRibbon, SK_ARRAY_COUNT(gRibbon), reporter); |
| 161 | } |
| 162 | |
| 163 | static void TestPathCoverage(skiatest::Reporter* reporter) { |
| 164 | TestQuadPointCount(reporter); |
| 165 | |
| 166 | } |
| 167 | |
| 168 | #include "TestClassDef.h" |
| 169 | DEFINE_TESTCLASS("PathCoverage", PathCoverageTestClass, TestPathCoverage) |