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