1 #include "SkPoint.h"
2 #include "SkScalar.h"
3 #include "Test.h"
4
5 /*
6 Duplicates lots of code from gpu/src/GrPathUtils.cpp
7 It'd be nice not to do so, but that code's set up currently to only have a single implementation.
8 */
9
10 #define MAX_COEFF_SHIFT 6
11 static const uint32_t MAX_POINTS_PER_CURVE = 1 << MAX_COEFF_SHIFT;
12
cheap_distance(SkScalar dx,SkScalar dy)13 static inline int cheap_distance(SkScalar dx, SkScalar dy) {
14 int idx = SkAbs32(SkScalarRound(dx));
15 int idy = SkAbs32(SkScalarRound(dy));
16 if (idx > idy) {
17 idx += idy >> 1;
18 } else {
19 idx = idy + (idx >> 1);
20 }
21 return idx;
22 }
23
diff_to_shift(SkScalar dx,SkScalar dy)24 static inline int diff_to_shift(SkScalar dx, SkScalar dy) {
25 int dist = cheap_distance(dx, dy);
26 return (32 - SkCLZ(dist));
27 }
28
estimatedQuadraticPointCount(const SkPoint points[],SkScalar tol)29 uint32_t estimatedQuadraticPointCount(const SkPoint points[], SkScalar tol) {
30 int shift = diff_to_shift(points[1].fX * 2 - points[2].fX - points[0].fX,
31 points[1].fY * 2 - points[2].fY - points[0].fY);
32 SkASSERT(shift >= 0);
33 //SkDebugf("Quad shift %d;", shift);
34 // bias to more closely approximate exact value, then clamp to zero
35 shift -= 2;
36 shift &= ~(shift>>31);
37
38 if (shift > MAX_COEFF_SHIFT) {
39 shift = MAX_COEFF_SHIFT;
40 }
41 uint32_t count = 1 << shift;
42 //SkDebugf(" biased shift %d, scale %u\n", shift, count);
43 return count;
44 }
45
computedQuadraticPointCount(const SkPoint points[],SkScalar tol)46 uint32_t computedQuadraticPointCount(const SkPoint points[], SkScalar tol) {
47 SkScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]);
48 if (d < tol) {
49 return 1;
50 } else {
51 int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol)));
52 uint32_t count = SkMinScalar(SkNextPow2(temp), MAX_POINTS_PER_CURVE);
53 return count;
54 }
55 }
56
57 // Curve from samplecode/SampleSlides.cpp
58 static const int gXY[] = {
59 4, 0, 0, -4, 8, -4, 12, 0, 8, 4, 0, 4
60 };
61
62 static const int gSawtooth[] = {
63 0, 0, 10, 10, 20, 20, 30, 10, 40, 0, 50, -10, 60, -20, 70, -10, 80, 0
64 };
65
66 static const int gOvalish[] = {
67 0, 0, 5, 15, 20, 20, 35, 15, 40, 0
68 };
69
70 static const int gSharpSawtooth[] = {
71 0, 0, 1, 10, 2, 0, 3, -10, 4, 0
72 };
73
74 // Curve crosses back over itself around 0,10
75 static const int gRibbon[] = {
76 -4, 0, 4, 20, 0, 25, -4, 20, 4, 0
77 };
78
one_d_pe(const int * array,const unsigned int count,skiatest::Reporter * reporter)79 static bool one_d_pe(const int* array, const unsigned int count,
80 skiatest::Reporter* reporter) {
81 SkPoint path [3];
82 path[1] = SkPoint::Make(SkIntToScalar(array[0]), SkIntToScalar(array[1]));
83 path[2] = SkPoint::Make(SkIntToScalar(array[2]), SkIntToScalar(array[3]));
84 int numErrors = 0;
85 for (unsigned i = 4; i < (count); i += 2) {
86 path[0] = path[1];
87 path[1] = path[2];
88 path[2] = SkPoint::Make(SkIntToScalar(array[i]),
89 SkIntToScalar(array[i+1]));
90 uint32_t computedCount =
91 computedQuadraticPointCount(path, SkIntToScalar(1));
92 uint32_t estimatedCount =
93 estimatedQuadraticPointCount(path, SkIntToScalar(1));
94 // Allow estimated to be off by a factor of two, but no more.
95 if ((estimatedCount > 2 * computedCount) ||
96 (computedCount > estimatedCount * 2)) {
97 SkString errorDescription;
98 errorDescription.printf(
99 "Curve from %.2f %.2f through %.2f %.2f to %.2f %.2f "
100 "computes %d, estimates %d\n",
101 path[0].fX, path[0].fY, path[1].fX, path[1].fY,
102 path[2].fX, path[2].fY, computedCount, estimatedCount);
103 numErrors++;
104 reporter->reportFailed(errorDescription);
105 }
106 }
107
108 if (numErrors > 0)
109 printf("%d curve segments differ\n", numErrors);
110 return (numErrors == 0);
111 }
112
113
114
TestQuadPointCount(skiatest::Reporter * reporter)115 static void TestQuadPointCount(skiatest::Reporter* reporter) {
116 one_d_pe(gXY, SK_ARRAY_COUNT(gXY), reporter);
117 one_d_pe(gSawtooth, SK_ARRAY_COUNT(gSawtooth), reporter);
118 one_d_pe(gOvalish, SK_ARRAY_COUNT(gOvalish), reporter);
119 one_d_pe(gSharpSawtooth, SK_ARRAY_COUNT(gSharpSawtooth), reporter);
120 one_d_pe(gRibbon, SK_ARRAY_COUNT(gRibbon), reporter);
121 }
122
TestPathCoverage(skiatest::Reporter * reporter)123 static void TestPathCoverage(skiatest::Reporter* reporter) {
124 TestQuadPointCount(reporter);
125
126 }
127
128 #include "TestClassDef.h"
129 DEFINE_TESTCLASS("PathCoverage", PathCoverageTestClass, TestPathCoverage)
130