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 */ 8 #include "SkMath.h" 9 #include "SkPoint.h" 10 #include "SkScalar.h" 11 #include "Test.h" 12 13 /* 14 Duplicates lots of code from gpu/src/GrPathUtils.cpp 15 It'd be nice not to do so, but that code's set up currently to only have 16 a single implementation. 17 */ 18 19 // Sk uses 6, Gr (implicitly) used 10, both apparently arbitrarily. 20 #define MAX_COEFF_SHIFT 6 21 static const uint32_t MAX_POINTS_PER_CURVE = 1 << MAX_COEFF_SHIFT; 22 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. 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 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); 42 } 43 44 static inline SkScalar compute_distance(const SkPoint points[]) { 45 return points[1].distanceToLineSegmentBetween(points[0], points[2]); 46 } 47 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); 53 if (shift > MAX_COEFF_SHIFT) { 54 shift = MAX_COEFF_SHIFT; 55 } 56 return 1 << shift; 57 } 58 59 static inline uint32_t compute_pointCount(SkScalar d, SkScalar tol) { 60 if (d < tol) { 61 return 1; 62 } else { 63 int temp = SkScalarCeilToInt(SkScalarSqrt(SkScalarDiv(d, tol))); 64 uint32_t count = SkMin32(SkNextPow2(temp), MAX_POINTS_PER_CURVE); 65 return count; 66 } 67 } 68 69 static uint32_t quadraticPointCount_EE(const SkPoint points[]) { 70 int distance = estimate_distance(points); 71 return estimate_pointCount(distance); 72 } 73 74 static uint32_t quadraticPointCount_EC(const SkPoint points[], SkScalar tol) { 75 int distance = estimate_distance(points); 76 return compute_pointCount(SkIntToScalar(distance), tol); 77 } 78 79 static uint32_t quadraticPointCount_CE(const SkPoint points[]) { 80 SkScalar distance = compute_distance(points); 81 return estimate_pointCount(SkScalarRound(distance)); 82 } 83 84 static uint32_t quadraticPointCount_CC(const SkPoint points[], SkScalar tol) { 85 SkScalar distance = compute_distance(points); 86 return compute_pointCount(distance, tol); 87 } 88 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; 117 for (unsigned i = 4; i < count; i += 2) { 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 = 123 quadraticPointCount_CC(path, SkIntToScalar(1)); 124 uint32_t estimatedCount = 125 quadraticPointCount_EE(path); 126 127 if (false) { // avoid bit rot, suppress warning 128 computedCount = 129 quadraticPointCount_EC(path, SkIntToScalar(1)); 130 estimatedCount = 131 quadraticPointCount_CE(path); 132 } 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) { 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); 145 numErrors++; 146 reporter->reportFailed(errorDescription); 147 } 148 } 149 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) 170
