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