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 "SkGeometry.h"
9 #include "SkPointPriv.h"
10 #include "SkRandom.h"
11 #include "Test.h"
12
13 #include <array>
14 #include <numeric>
15
nearly_equal(const SkPoint & a,const SkPoint & b)16 static bool nearly_equal(const SkPoint& a, const SkPoint& b) {
17 return SkScalarNearlyEqual(a.fX, b.fX) && SkScalarNearlyEqual(a.fY, b.fY);
18 }
19
testChopCubic(skiatest::Reporter * reporter)20 static void testChopCubic(skiatest::Reporter* reporter) {
21 /*
22 Inspired by this test, which used to assert that the tValues had dups
23
24 <path stroke="#202020" d="M0,0 C0,0 1,1 2190,5130 C2190,5070 2220,5010 2205,4980" />
25 */
26 const SkPoint src[] = {
27 { SkIntToScalar(2190), SkIntToScalar(5130) },
28 { SkIntToScalar(2190), SkIntToScalar(5070) },
29 { SkIntToScalar(2220), SkIntToScalar(5010) },
30 { SkIntToScalar(2205), SkIntToScalar(4980) },
31 };
32 SkPoint dst[13];
33 SkScalar tValues[3];
34 // make sure we don't assert internally
35 int count = SkChopCubicAtMaxCurvature(src, dst, tValues);
36 if (false) { // avoid bit rot, suppress warning
37 REPORTER_ASSERT(reporter, count);
38 }
39 // Make sure src and dst can be the same pointer.
40 SkPoint pts[7];
41 for (int i = 0; i < 7; ++i) {
42 pts[i].set(i, i);
43 }
44 SkChopCubicAt(pts, pts, .5f);
45 for (int i = 0; i < 7; ++i) {
46 REPORTER_ASSERT(reporter, pts[i].fX == pts[i].fY);
47 REPORTER_ASSERT(reporter, pts[i].fX == i * .5f);
48 }
49 }
50
check_pairs(skiatest::Reporter * reporter,int index,SkScalar t,const char name[],SkScalar x0,SkScalar y0,SkScalar x1,SkScalar y1)51 static void check_pairs(skiatest::Reporter* reporter, int index, SkScalar t, const char name[],
52 SkScalar x0, SkScalar y0, SkScalar x1, SkScalar y1) {
53 bool eq = SkScalarNearlyEqual(x0, x1) && SkScalarNearlyEqual(y0, y1);
54 if (!eq) {
55 SkDebugf("%s [%d %g] p0 [%10.8f %10.8f] p1 [%10.8f %10.8f]\n",
56 name, index, t, x0, y0, x1, y1);
57 REPORTER_ASSERT(reporter, eq);
58 }
59 }
60
test_evalquadat(skiatest::Reporter * reporter)61 static void test_evalquadat(skiatest::Reporter* reporter) {
62 SkRandom rand;
63 for (int i = 0; i < 1000; ++i) {
64 SkPoint pts[3];
65 for (int j = 0; j < 3; ++j) {
66 pts[j].set(rand.nextSScalar1() * 100, rand.nextSScalar1() * 100);
67 }
68 const SkScalar dt = SK_Scalar1 / 128;
69 SkScalar t = dt;
70 for (int j = 1; j < 128; ++j) {
71 SkPoint r0;
72 SkEvalQuadAt(pts, t, &r0);
73 SkPoint r1 = SkEvalQuadAt(pts, t);
74 check_pairs(reporter, i, t, "quad-pos", r0.fX, r0.fY, r1.fX, r1.fY);
75
76 SkVector v0;
77 SkEvalQuadAt(pts, t, nullptr, &v0);
78 SkVector v1 = SkEvalQuadTangentAt(pts, t);
79 check_pairs(reporter, i, t, "quad-tan", v0.fX, v0.fY, v1.fX, v1.fY);
80
81 t += dt;
82 }
83 }
84 }
85
test_conic_eval_pos(skiatest::Reporter * reporter,const SkConic & conic,SkScalar t)86 static void test_conic_eval_pos(skiatest::Reporter* reporter, const SkConic& conic, SkScalar t) {
87 SkPoint p0, p1;
88 conic.evalAt(t, &p0, nullptr);
89 p1 = conic.evalAt(t);
90 check_pairs(reporter, 0, t, "conic-pos", p0.fX, p0.fY, p1.fX, p1.fY);
91 }
92
test_conic_eval_tan(skiatest::Reporter * reporter,const SkConic & conic,SkScalar t)93 static void test_conic_eval_tan(skiatest::Reporter* reporter, const SkConic& conic, SkScalar t) {
94 SkVector v0, v1;
95 conic.evalAt(t, nullptr, &v0);
96 v1 = conic.evalTangentAt(t);
97 check_pairs(reporter, 0, t, "conic-tan", v0.fX, v0.fY, v1.fX, v1.fY);
98 }
99
test_conic(skiatest::Reporter * reporter)100 static void test_conic(skiatest::Reporter* reporter) {
101 SkRandom rand;
102 for (int i = 0; i < 1000; ++i) {
103 SkPoint pts[3];
104 for (int j = 0; j < 3; ++j) {
105 pts[j].set(rand.nextSScalar1() * 100, rand.nextSScalar1() * 100);
106 }
107 for (int k = 0; k < 10; ++k) {
108 SkScalar w = rand.nextUScalar1() * 2;
109 SkConic conic(pts, w);
110
111 const SkScalar dt = SK_Scalar1 / 128;
112 SkScalar t = dt;
113 for (int j = 1; j < 128; ++j) {
114 test_conic_eval_pos(reporter, conic, t);
115 test_conic_eval_tan(reporter, conic, t);
116 t += dt;
117 }
118 }
119 }
120 }
121
test_quad_tangents(skiatest::Reporter * reporter)122 static void test_quad_tangents(skiatest::Reporter* reporter) {
123 SkPoint pts[] = {
124 {10, 20}, {10, 20}, {20, 30},
125 {10, 20}, {15, 25}, {20, 30},
126 {10, 20}, {20, 30}, {20, 30},
127 };
128 int count = (int) SK_ARRAY_COUNT(pts) / 3;
129 for (int index = 0; index < count; ++index) {
130 SkConic conic(&pts[index * 3], 0.707f);
131 SkVector start = SkEvalQuadTangentAt(&pts[index * 3], 0);
132 SkVector mid = SkEvalQuadTangentAt(&pts[index * 3], .5f);
133 SkVector end = SkEvalQuadTangentAt(&pts[index * 3], 1);
134 REPORTER_ASSERT(reporter, start.fX && start.fY);
135 REPORTER_ASSERT(reporter, mid.fX && mid.fY);
136 REPORTER_ASSERT(reporter, end.fX && end.fY);
137 REPORTER_ASSERT(reporter, SkScalarNearlyZero(start.cross(mid)));
138 REPORTER_ASSERT(reporter, SkScalarNearlyZero(mid.cross(end)));
139 }
140 }
141
test_conic_tangents(skiatest::Reporter * reporter)142 static void test_conic_tangents(skiatest::Reporter* reporter) {
143 SkPoint pts[] = {
144 { 10, 20}, {10, 20}, {20, 30},
145 { 10, 20}, {15, 25}, {20, 30},
146 { 10, 20}, {20, 30}, {20, 30}
147 };
148 int count = (int) SK_ARRAY_COUNT(pts) / 3;
149 for (int index = 0; index < count; ++index) {
150 SkConic conic(&pts[index * 3], 0.707f);
151 SkVector start = conic.evalTangentAt(0);
152 SkVector mid = conic.evalTangentAt(.5f);
153 SkVector end = conic.evalTangentAt(1);
154 REPORTER_ASSERT(reporter, start.fX && start.fY);
155 REPORTER_ASSERT(reporter, mid.fX && mid.fY);
156 REPORTER_ASSERT(reporter, end.fX && end.fY);
157 REPORTER_ASSERT(reporter, SkScalarNearlyZero(start.cross(mid)));
158 REPORTER_ASSERT(reporter, SkScalarNearlyZero(mid.cross(end)));
159 }
160 }
161
test_this_conic_to_quad(skiatest::Reporter * r,const SkPoint pts[3],SkScalar w)162 static void test_this_conic_to_quad(skiatest::Reporter* r, const SkPoint pts[3], SkScalar w) {
163 SkAutoConicToQuads quadder;
164 const SkPoint* qpts = quadder.computeQuads(pts, w, 0.25);
165 const int qcount = quadder.countQuads();
166 const int pcount = qcount * 2 + 1;
167
168 REPORTER_ASSERT(r, SkPointPriv::AreFinite(qpts, pcount));
169 }
170
171 /**
172 * We need to ensure that when a conic is approximated by quads, that we always return finite
173 * values in the quads.
174 *
175 * Inspired by crbug_627414
176 */
test_conic_to_quads(skiatest::Reporter * reporter)177 static void test_conic_to_quads(skiatest::Reporter* reporter) {
178 const SkPoint triples[] = {
179 { 0, 0 }, { 1, 0 }, { 1, 1 },
180 { 0, 0 }, { 3.58732e-43f, 2.72084f }, { 3.00392f, 3.00392f },
181 { 0, 0 }, { 100000, 0 }, { 100000, 100000 },
182 { 0, 0 }, { 1e30f, 0 }, { 1e30f, 1e30f },
183 };
184 const int N = sizeof(triples) / sizeof(SkPoint);
185
186 for (int i = 0; i < N; i += 3) {
187 const SkPoint* pts = &triples[i];
188
189 SkRect bounds;
190 bounds.set(pts, 3);
191
192 SkScalar w = 1e30f;
193 do {
194 w *= 2;
195 test_this_conic_to_quad(reporter, pts, w);
196 } while (SkScalarIsFinite(w));
197 test_this_conic_to_quad(reporter, pts, SK_ScalarNaN);
198 }
199 }
200
test_cubic_tangents(skiatest::Reporter * reporter)201 static void test_cubic_tangents(skiatest::Reporter* reporter) {
202 SkPoint pts[] = {
203 { 10, 20}, {10, 20}, {20, 30}, {30, 40},
204 { 10, 20}, {15, 25}, {20, 30}, {30, 40},
205 { 10, 20}, {20, 30}, {30, 40}, {30, 40},
206 };
207 int count = (int) SK_ARRAY_COUNT(pts) / 4;
208 for (int index = 0; index < count; ++index) {
209 SkConic conic(&pts[index * 3], 0.707f);
210 SkVector start, mid, end;
211 SkEvalCubicAt(&pts[index * 4], 0, nullptr, &start, nullptr);
212 SkEvalCubicAt(&pts[index * 4], .5f, nullptr, &mid, nullptr);
213 SkEvalCubicAt(&pts[index * 4], 1, nullptr, &end, nullptr);
214 REPORTER_ASSERT(reporter, start.fX && start.fY);
215 REPORTER_ASSERT(reporter, mid.fX && mid.fY);
216 REPORTER_ASSERT(reporter, end.fX && end.fY);
217 REPORTER_ASSERT(reporter, SkScalarNearlyZero(start.cross(mid)));
218 REPORTER_ASSERT(reporter, SkScalarNearlyZero(mid.cross(end)));
219 }
220 }
221
check_cubic_type(skiatest::Reporter * reporter,const std::array<SkPoint,4> & bezierPoints,SkCubicType expectedType,bool undefined=false)222 static void check_cubic_type(skiatest::Reporter* reporter,
223 const std::array<SkPoint, 4>& bezierPoints, SkCubicType expectedType,
224 bool undefined = false) {
225 // Classify the cubic even if the results will be undefined: check for crashes and asserts.
226 SkCubicType actualType = SkClassifyCubic(bezierPoints.data());
227 if (!undefined) {
228 REPORTER_ASSERT(reporter, actualType == expectedType);
229 }
230 }
231
check_cubic_around_rect(skiatest::Reporter * reporter,float x1,float y1,float x2,float y2,bool undefined=false)232 static void check_cubic_around_rect(skiatest::Reporter* reporter,
233 float x1, float y1, float x2, float y2,
234 bool undefined = false) {
235 static constexpr SkCubicType expectations[24] = {
236 SkCubicType::kLoop,
237 SkCubicType::kCuspAtInfinity,
238 SkCubicType::kLocalCusp,
239 SkCubicType::kLocalCusp,
240 SkCubicType::kCuspAtInfinity,
241 SkCubicType::kLoop,
242 SkCubicType::kCuspAtInfinity,
243 SkCubicType::kLoop,
244 SkCubicType::kCuspAtInfinity,
245 SkCubicType::kLoop,
246 SkCubicType::kLocalCusp,
247 SkCubicType::kLocalCusp,
248 SkCubicType::kLocalCusp,
249 SkCubicType::kLocalCusp,
250 SkCubicType::kLoop,
251 SkCubicType::kCuspAtInfinity,
252 SkCubicType::kLoop,
253 SkCubicType::kCuspAtInfinity,
254 SkCubicType::kLoop,
255 SkCubicType::kCuspAtInfinity,
256 SkCubicType::kLocalCusp,
257 SkCubicType::kLocalCusp,
258 SkCubicType::kCuspAtInfinity,
259 SkCubicType::kLoop,
260 };
261 SkPoint points[] = {{x1, y1}, {x2, y1}, {x2, y2}, {x1, y2}};
262 std::array<SkPoint, 4> bezier;
263 for (int i=0; i < 4; ++i) {
264 bezier[0] = points[i];
265 for (int j=0; j < 3; ++j) {
266 int jidx = (j < i) ? j : j+1;
267 bezier[1] = points[jidx];
268 for (int k=0, kidx=0; k < 2; ++k, ++kidx) {
269 for (int n = 0; n < 2; ++n) {
270 kidx = (kidx == i || kidx == jidx) ? kidx+1 : kidx;
271 }
272 bezier[2] = points[kidx];
273 for (int l = 0; l < 4; ++l) {
274 if (l != i && l != jidx && l != kidx) {
275 bezier[3] = points[l];
276 break;
277 }
278 }
279 check_cubic_type(reporter, bezier, expectations[i*6 + j*2 + k], undefined);
280 }
281 }
282 }
283 for (int i=0; i < 4; ++i) {
284 bezier[0] = points[i];
285 for (int j=0; j < 3; ++j) {
286 int jidx = (j < i) ? j : j+1;
287 bezier[1] = points[jidx];
288 bezier[2] = points[jidx];
289 for (int k=0, kidx=0; k < 2; ++k, ++kidx) {
290 for (int n = 0; n < 2; ++n) {
291 kidx = (kidx == i || kidx == jidx) ? kidx+1 : kidx;
292 }
293 bezier[3] = points[kidx];
294 check_cubic_type(reporter, bezier, SkCubicType::kSerpentine, undefined);
295 }
296 }
297 }
298 }
299
test_classify_cubic(skiatest::Reporter * reporter)300 static void test_classify_cubic(skiatest::Reporter* reporter) {
301 check_cubic_type(reporter, {{{149.325f, 107.705f}, {149.325f, 103.783f},
302 {151.638f, 100.127f}, {156.263f, 96.736f}}},
303 SkCubicType::kSerpentine);
304 check_cubic_type(reporter, {{{225.694f, 223.15f}, {209.831f, 224.837f},
305 {195.994f, 230.237f}, {184.181f, 239.35f}}},
306 SkCubicType::kSerpentine);
307 check_cubic_type(reporter, {{{4.873f, 5.581f}, {5.083f, 5.2783f},
308 {5.182f, 4.8593f}, {5.177f, 4.3242f}}},
309 SkCubicType::kSerpentine);
310 check_cubic_around_rect(reporter, 0, 0, 1, 1);
311 check_cubic_around_rect(reporter,
312 -std::numeric_limits<float>::max(),
313 -std::numeric_limits<float>::max(),
314 +std::numeric_limits<float>::max(),
315 +std::numeric_limits<float>::max());
316 check_cubic_around_rect(reporter, 1, 1,
317 +std::numeric_limits<float>::min(),
318 +std::numeric_limits<float>::max());
319 check_cubic_around_rect(reporter,
320 -std::numeric_limits<float>::min(),
321 -std::numeric_limits<float>::min(),
322 +std::numeric_limits<float>::min(),
323 +std::numeric_limits<float>::min());
324 check_cubic_around_rect(reporter, +1, -std::numeric_limits<float>::min(), -1, -1);
325 check_cubic_around_rect(reporter,
326 -std::numeric_limits<float>::infinity(),
327 -std::numeric_limits<float>::infinity(),
328 +std::numeric_limits<float>::infinity(),
329 +std::numeric_limits<float>::infinity(),
330 true);
331 check_cubic_around_rect(reporter, 0, 0, 1, +std::numeric_limits<float>::infinity(), true);
332 check_cubic_around_rect(reporter,
333 -std::numeric_limits<float>::quiet_NaN(),
334 -std::numeric_limits<float>::quiet_NaN(),
335 +std::numeric_limits<float>::quiet_NaN(),
336 +std::numeric_limits<float>::quiet_NaN(),
337 true);
338 check_cubic_around_rect(reporter, 0, 0, 1, +std::numeric_limits<float>::quiet_NaN(), true);
339 }
340
test_cubic_cusps(skiatest::Reporter * reporter)341 static void test_cubic_cusps(skiatest::Reporter* reporter) {
342 std::array<SkPoint, 4> noCusps[] = {
343 {{{0, 0}, {1, 1}, {2, 2}, {3, 3}}},
344 {{{0, 0}, {1, 0}, {1, 1}, {0, 1}}},
345 {{{0, 0}, {1, 0}, {2, 1}, {2, 2}}},
346 {{{0, 0}, {1, 0}, {1, 1}, {2, 1}}},
347 };
348 for (auto noCusp : noCusps) {
349 REPORTER_ASSERT(reporter, SkFindCubicCusp(noCusp.data()) < 0);
350 }
351 std::array<SkPoint, 4> cusps[] = {
352 {{{0, 0}, {1, 1}, {1, 0}, {0, 1}}},
353 {{{0, 0}, {1, 1}, {0, 1}, {1, 0}}},
354 {{{0, 1}, {1, 0}, {0, 0}, {1, 1}}},
355 {{{0, 1}, {1, 0}, {1, 1}, {0, 0}}},
356 };
357 for (auto cusp : cusps) {
358 REPORTER_ASSERT(reporter, SkFindCubicCusp(cusp.data()) > 0);
359 }
360 }
361
DEF_TEST(Geometry,reporter)362 DEF_TEST(Geometry, reporter) {
363 SkPoint pts[5];
364
365 pts[0].set(0, 0);
366 pts[1].set(100, 50);
367 pts[2].set(0, 100);
368
369 int count = SkChopQuadAtMaxCurvature(pts, pts); // Ensure src and dst can be the same pointer.
370 REPORTER_ASSERT(reporter, count == 1 || count == 2);
371
372 pts[0].set(0, 0);
373 pts[1].set(3, 0);
374 pts[2].set(3, 3);
375 SkConvertQuadToCubic(pts, pts);
376 const SkPoint cubic[] = {
377 { 0, 0, }, { 2, 0, }, { 3, 1, }, { 3, 3 },
378 };
379 for (int i = 0; i < 4; ++i) {
380 REPORTER_ASSERT(reporter, nearly_equal(cubic[i], pts[i]));
381 }
382
383 testChopCubic(reporter);
384 test_evalquadat(reporter);
385 test_conic(reporter);
386 test_cubic_tangents(reporter);
387 test_quad_tangents(reporter);
388 test_conic_tangents(reporter);
389 test_conic_to_quads(reporter);
390 test_classify_cubic(reporter);
391 test_cubic_cusps(reporter);
392 }
393