1 /*
2 * Copyright 2015 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 "tests/Test.h"
9
10 #include "include/core/SkPath.h"
11 #include "include/effects/SkGradientShader.h"
12 #include "include/gpu/GrDirectContext.h"
13 #include "src/gpu/GrDirectContextPriv.h"
14 #include "src/gpu/GrEagerVertexAllocator.h"
15 #include "src/gpu/GrStyle.h"
16 #include "src/gpu/effects/GrPorterDuffXferProcessor.h"
17 #include "src/gpu/geometry/GrInnerFanTriangulator.h"
18 #include "src/gpu/geometry/GrStyledShape.h"
19 #include "src/shaders/SkShaderBase.h"
20 #include "tools/ToolUtils.h"
21 #include <map>
22
23 /*
24 * These tests pass by not crashing, hanging or asserting in Debug.
25 */
26
27 using CreatePathFn = SkPath(*)();
28
29 CreatePathFn kNonEdgeAAPaths[] = {
30 // Tests active edges made inactive by splitting.
31 // Also tests active edge list forced into an invalid ordering by
32 // splitting (mopped up in cleanup_active_edges()).
__anonb55218fc0102() 33 []() -> SkPath {
34 SkPath path;
35 path.moveTo(229.127044677734375f, 67.34100341796875f);
36 path.lineTo(187.8097381591796875f, -6.7729740142822265625f);
37 path.lineTo(171.411407470703125f, 50.94266510009765625f);
38 path.lineTo(245.5253753662109375f, 9.6253643035888671875f);
39 path.moveTo(208.4683990478515625f, 30.284009933471679688f);
40 path.lineTo(171.411407470703125f, 50.94266510009765625f);
41 path.lineTo(187.8097381591796875f, -6.7729740142822265625f);
42 return path;
43 },
44
45 // Intersections which fall exactly on the current vertex, and require
46 // a restart of the intersection checking.
__anonb55218fc0202() 47 []() -> SkPath {
48 SkPath path;
49 path.moveTo(314.483551025390625f, 486.246002197265625f);
50 path.lineTo(385.41949462890625f, 532.8087158203125f);
51 path.lineTo(373.232879638671875f, 474.05938720703125f);
52 path.lineTo(326.670166015625f, 544.995361328125f);
53 path.moveTo(349.951507568359375f, 509.52734375f);
54 path.lineTo(373.232879638671875f, 474.05938720703125f);
55 path.lineTo(385.41949462890625f, 532.8087158203125f);
56 return path;
57 },
58
59 // Tests active edges which are removed by splitting.
__anonb55218fc0302() 60 []() -> SkPath {
61 SkPath path;
62 path.moveTo(343.107391357421875f, 613.62176513671875f);
63 path.lineTo(426.632415771484375f, 628.5740966796875f);
64 path.lineTo(392.3460693359375f, 579.33544921875f);
65 path.lineTo(377.39373779296875f, 662.86041259765625f);
66 path.moveTo(384.869873046875f, 621.097900390625f);
67 path.lineTo(392.3460693359375f, 579.33544921875f);
68 path.lineTo(426.632415771484375f, 628.5740966796875f);
69 return path;
70 },
71
72 // Collinear edges merged in set_top().
73 // Also, an intersection between left and right enclosing edges which
74 // falls above the current vertex.
__anonb55218fc0402() 75 []() -> SkPath {
76 SkPath path;
77 path.moveTo(545.95751953125f, 791.69854736328125f);
78 path.lineTo(612.05816650390625f, 738.494140625f);
79 path.lineTo(552.4056396484375f, 732.0460205078125f);
80 path.lineTo(605.61004638671875f, 798.14666748046875f);
81 path.moveTo(579.00787353515625f, 765.0963134765625f);
82 path.lineTo(552.4056396484375f, 732.0460205078125f);
83 path.lineTo(612.05816650390625f, 738.494140625f);
84 return path;
85 },
86
87 // Tests active edges which are made inactive by set_top().
__anonb55218fc0502() 88 []() -> SkPath {
89 SkPath path;
90 path.moveTo(819.2725830078125f, 751.77447509765625f);
91 path.lineTo(820.70904541015625f, 666.933837890625f);
92 path.lineTo(777.57049560546875f, 708.63592529296875f);
93 path.lineTo(862.4111328125f, 710.0723876953125f);
94 path.moveTo(819.99078369140625f, 709.3541259765625f);
95 path.lineTo(777.57049560546875f, 708.63592529296875f);
96 path.lineTo(820.70904541015625f, 666.933837890625f);
97 return path;
98 },
99
__anonb55218fc0602() 100 []() -> SkPath {
101 SkPath path;
102 path.moveTo(823.33209228515625f, 749.052734375f);
103 path.lineTo(823.494873046875f, 664.20013427734375f);
104 path.lineTo(780.9871826171875f, 706.5450439453125f);
105 path.lineTo(865.8397216796875f, 706.70782470703125f);
106 path.moveTo(823.4134521484375f, 706.6263427734375f);
107 path.lineTo(780.9871826171875f, 706.5450439453125f);
108 path.lineTo(823.494873046875f, 664.20013427734375f);
109 return path;
110 },
111
__anonb55218fc0702() 112 []() -> SkPath {
113 SkPath path;
114 path.moveTo(954.862548828125f, 562.8349609375f);
115 path.lineTo(899.32818603515625f, 498.679443359375f);
116 path.lineTo(895.017578125f, 558.52435302734375f);
117 path.lineTo(959.17315673828125f, 502.990081787109375f);
118 path.moveTo(927.0953369140625f, 530.7572021484375f);
119 path.lineTo(895.017578125f, 558.52435302734375f);
120 path.lineTo(899.32818603515625f, 498.679443359375f);
121 return path;
122 },
123
__anonb55218fc0802() 124 []() -> SkPath {
125 SkPath path;
126 path.moveTo(958.5330810546875f, 547.35516357421875f);
127 path.lineTo(899.93109130859375f, 485.989013671875f);
128 path.lineTo(898.54901123046875f, 545.97308349609375f);
129 path.lineTo(959.9151611328125f, 487.37109375f);
130 path.moveTo(929.2320556640625f, 516.67205810546875f);
131 path.lineTo(898.54901123046875f, 545.97308349609375f);
132 path.lineTo(899.93109130859375f, 485.989013671875f);
133 return path;
134 },
135
__anonb55218fc0902() 136 []() -> SkPath {
137 SkPath path;
138 path.moveTo(389.8609619140625f, 369.326873779296875f);
139 path.lineTo(470.6290283203125f, 395.33697509765625f);
140 path.lineTo(443.250030517578125f, 341.9478759765625f);
141 path.lineTo(417.239959716796875f, 422.7159423828125f);
142 path.moveTo(430.244964599609375f, 382.3319091796875f);
143 path.lineTo(443.250030517578125f, 341.9478759765625f);
144 path.lineTo(470.6290283203125f, 395.33697509765625f);
145 return path;
146 },
147
__anonb55218fc0a02() 148 []() -> SkPath {
149 SkPath path;
150 path.moveTo(20, 20);
151 path.lineTo(50, 80);
152 path.lineTo(20, 80);
153 path.moveTo(80, 50);
154 path.lineTo(50, 50);
155 path.lineTo(20, 50);
156 return path;
157 },
158
__anonb55218fc0b02() 159 []() -> SkPath {
160 SkPath path;
161 path.moveTo(257.19439697265625f, 320.876617431640625f);
162 path.lineTo(190.113037109375f, 320.58978271484375f);
163 path.lineTo(203.64404296875f, 293.8145751953125f);
164 path.moveTo(203.357177734375f, 360.896026611328125f);
165 path.lineTo(216.88824462890625f, 334.120819091796875f);
166 path.lineTo(230.41925048828125f, 307.345611572265625f);
167 return path;
168 },
169
170 // A degenerate segments case, where both upper and lower segments of
171 // a split edge must remain active.
__anonb55218fc0c02() 172 []() -> SkPath {
173 SkPath path;
174 path.moveTo(231.9331207275390625f, 306.2012939453125f);
175 path.lineTo(191.4859161376953125f, 306.04547119140625f);
176 path.lineTo(231.0659332275390625f, 300.2642822265625f);
177 path.moveTo(189.946807861328125f, 302.072265625f);
178 path.lineTo(179.79705810546875f, 294.859771728515625f);
179 path.lineTo(191.0016021728515625f, 296.165679931640625f);
180 path.moveTo(150.8942108154296875f, 304.900146484375f);
181 path.lineTo(179.708892822265625f, 297.849029541015625f);
182 path.lineTo(190.4742279052734375f, 299.11895751953125f);
183 return path;
184 },
185
186 // Handle the case where edge.dist(edge.fTop) != 0.0.
__anonb55218fc0d02() 187 []() -> SkPath {
188 SkPath path;
189 path.moveTo( 0.0f, 400.0f);
190 path.lineTo( 138.0f, 202.0f);
191 path.lineTo( 0.0f, 202.0f);
192 path.moveTo( 12.62693023681640625f, 250.57464599609375f);
193 path.lineTo( 8.13896942138671875f, 254.556884765625f);
194 path.lineTo(-18.15641021728515625f, 220.40203857421875f);
195 path.lineTo(-15.986493110656738281f, 219.6513519287109375f);
196 path.moveTo( 36.931194305419921875f, 282.485504150390625f);
197 path.lineTo( 15.617521286010742188f, 261.2901611328125f);
198 path.lineTo( 10.3829498291015625f, 252.565765380859375f);
199 path.lineTo(-16.165292739868164062f, 222.646026611328125f);
200 return path;
201 },
202
203 // A degenerate segments case which exercises inactive edges being
204 // made active by splitting.
__anonb55218fc0e02() 205 []() -> SkPath {
206 SkPath path;
207 path.moveTo(690.62127685546875f, 509.25555419921875f);
208 path.lineTo(99.336181640625f, 511.71405029296875f);
209 path.lineTo(708.362548828125f, 512.4349365234375f);
210 path.lineTo(729.9940185546875f, 516.3114013671875f);
211 path.lineTo(738.708984375f, 518.76995849609375f);
212 path.lineTo(678.3463134765625f, 510.0819091796875f);
213 path.lineTo(681.21795654296875f, 504.81378173828125f);
214 path.moveTo(758.52764892578125f, 521.55963134765625f);
215 path.lineTo(719.1549072265625f, 514.50372314453125f);
216 path.lineTo(689.59063720703125f, 512.0628662109375f);
217 path.lineTo(679.78216552734375f, 507.447845458984375f);
218 return path;
219 },
220
221 // Tests vertices which become "orphaned" (ie., no connected edges)
222 // after simplification.
__anonb55218fc0f02() 223 []() -> SkPath {
224 SkPath path;
225 path.moveTo(217.326019287109375f, 166.4752960205078125f);
226 path.lineTo(226.279266357421875f, 170.929473876953125f);
227 path.lineTo(234.3973388671875f, 177.0623626708984375f);
228 path.lineTo(262.0921630859375f, 188.746124267578125f);
229 path.moveTo(196.23638916015625f, 174.0722198486328125f);
230 path.lineTo(416.15277099609375f, 180.138214111328125f);
231 path.lineTo(192.651947021484375f, 304.0228271484375f);
232 return path;
233 },
234
__anonb55218fc1002() 235 []() -> SkPath {
236 SkPath path;
237 path.moveTo( 0.0f, 0.0f);
238 path.lineTo(10000.0f, 0.0f);
239 path.lineTo( 0.0f, -1.0f);
240 path.lineTo(10000.0f, 0.000001f);
241 path.lineTo( 0.0f, -30.0f);
242 return path;
243 },
244
245 // Reduction of Nebraska-StateSeal.svg. Floating point error causes the
246 // same edge to be added to more than one poly on the same side.
__anonb55218fc1102() 247 []() -> SkPath {
248 SkPath path;
249 path.moveTo(170.8199920654296875, 491.86700439453125);
250 path.lineTo(173.7649993896484375, 489.7340087890625);
251 path.lineTo(174.1450958251953125, 498.545989990234375);
252 path.lineTo( 171.998992919921875, 500.88201904296875);
253 path.moveTo(168.2922515869140625, 498.66265869140625);
254 path.lineTo(169.8589935302734375, 497.94500732421875);
255 path.lineTo( 172, 500.88299560546875);
256 path.moveTo( 169.555267333984375, 490.70111083984375);
257 path.lineTo(173.7649993896484375, 489.7340087890625);
258 path.lineTo( 170.82000732421875, 491.86700439453125);
259 return path;
260 },
261
262 // A shape with a vertex collinear to the right hand edge.
263 // This messes up find_enclosing_edges.
__anonb55218fc1202() 264 []() -> SkPath {
265 SkPath path;
266 path.moveTo(80, 20);
267 path.lineTo(80, 60);
268 path.lineTo(20, 60);
269 path.moveTo(80, 50);
270 path.lineTo(80, 80);
271 path.lineTo(20, 80);
272 return path;
273 },
274
275 // Exercises the case where an edge becomes collinear with *two* of its
276 // adjacent neighbour edges after splitting.
277 // This is a reduction from
278 // http://mooooo.ooo/chebyshev-sine-approximation/horner_ulp.svg
__anonb55218fc1302() 279 []() -> SkPath {
280 SkPath path;
281 path.moveTo( 351.99298095703125, 348.23046875);
282 path.lineTo( 351.91876220703125, 347.33984375);
283 path.lineTo( 351.91876220703125, 346.1953125);
284 path.lineTo( 351.90313720703125, 347.734375);
285 path.lineTo( 351.90313720703125, 346.1328125);
286 path.lineTo( 351.87579345703125, 347.93359375);
287 path.lineTo( 351.87579345703125, 345.484375);
288 path.lineTo( 351.86407470703125, 347.7890625);
289 path.lineTo( 351.86407470703125, 346.2109375);
290 path.lineTo( 351.84844970703125, 347.63763427734375);
291 path.lineTo( 351.84454345703125, 344.19232177734375);
292 path.lineTo( 351.78204345703125, 346.9483642578125);
293 path.lineTo( 351.758636474609375, 347.18310546875);
294 path.lineTo( 351.75469970703125, 346.75);
295 path.lineTo( 351.75469970703125, 345.46875);
296 path.lineTo( 352.5546875, 345.46875);
297 path.lineTo( 352.55078125, 347.01953125);
298 path.lineTo( 351.75079345703125, 347.02313232421875);
299 path.lineTo( 351.74688720703125, 346.15203857421875);
300 path.lineTo( 351.74688720703125, 347.646148681640625);
301 path.lineTo( 352.5390625, 346.94140625);
302 path.lineTo( 351.73907470703125, 346.94268798828125);
303 path.lineTo( 351.73516845703125, 344.48565673828125);
304 path.lineTo( 352.484375, 346.73828125);
305 path.lineTo( 351.68438720703125, 346.7401123046875);
306 path.lineTo( 352.4765625, 346.546875);
307 path.lineTo( 351.67657470703125, 346.54937744140625);
308 path.lineTo( 352.47265625, 346.75390625);
309 path.lineTo( 351.67266845703125, 346.756622314453125);
310 path.lineTo( 351.66876220703125, 345.612091064453125);
311 return path;
312 },
313
314 // A path which contains out-of-range colinear intersections.
__anonb55218fc1402() 315 []() -> SkPath {
316 SkPath path;
317 path.moveTo( 0, 63.39080047607421875);
318 path.lineTo(-0.70804601907730102539, 63.14350128173828125);
319 path.lineTo(-7.8608899287380243391e-17, 64.14080047607421875);
320 path.moveTo( 0, 64.14080047607421875);
321 path.lineTo(44.285900115966796875, 64.14080047607421875);
322 path.lineTo( 0, 62.64080047607421875);
323 path.moveTo(21.434900283813476562, -0.24732701480388641357);
324 path.lineTo(-0.70804601907730102539, 63.14350128173828125);
325 path.lineTo(0.70804601907730102539, 63.6381988525390625);
326 return path;
327 },
328
329 // A path which results in infs and nans when conics are converted to quads.
__anonb55218fc1502() 330 []() -> SkPath {
331 SkPath path;
332 path.moveTo(-2.20883e+37f, -1.02892e+37f);
333 path.conicTo(-2.00958e+38f, -9.36107e+37f, -1.7887e+38f, -8.33215e+37f, 0.707107f);
334 path.conicTo(-1.56782e+38f, -7.30323e+37f, 2.20883e+37f, 1.02892e+37f, 0.707107f);
335 path.conicTo(2.00958e+38f, 9.36107e+37f, 1.7887e+38f, 8.33215e+37f, 0.707107f);
336 path.conicTo(1.56782e+38f, 7.30323e+37f, -2.20883e+37f, -1.02892e+37f, 0.707107f);
337 return path;
338 },
339
340 // A quad which generates a huge number of points (>2B) when uniformly
341 // linearized. This should not hang or OOM.
__anonb55218fc1602() 342 []() -> SkPath {
343 SkPath path;
344 path.moveTo(10, 0);
345 path.lineTo(0, 0);
346 path.quadTo(10, 0, 0, 8315084722602508288);
347 return path;
348 },
349
350 // A path which hangs during simplification. It produces an edge which is
351 // to the left of its own endpoints, which causes an infinite loop in the
352 // right-enclosing-edge splitting.
__anonb55218fc1702() 353 []() -> SkPath {
354 SkPath path;
355 path.moveTo(0.75001740455627441406, 23.051967620849609375);
356 path.lineTo(5.8471612930297851562, 22.731662750244140625);
357 path.lineTo(10.749670028686523438, 22.253145217895507812);
358 path.lineTo(13.115868568420410156, 22.180681228637695312);
359 path.lineTo(15.418928146362304688, 22.340015411376953125);
360 path.lineTo( 17.654022216796875, 22.82159423828125);
361 path.lineTo(19.81632232666015625, 23.715869903564453125);
362 path.lineTo(40, 0);
363 path.lineTo(5.5635203441547955577e-15, 0);
364 path.lineTo(5.5635203441547955577e-15, 47);
365 path.lineTo(-1.4210854715202003717e-14, 21.713298797607421875);
366 path.lineTo(0.75001740455627441406, 21.694292068481445312);
367 path.lineTo(0.75001740455627441406, 23.051967620849609375);
368 return path;
369 },
370
371 // Reduction from skbug.com/7911 that causes a crash due to splitting a
372 // zombie edge.
__anonb55218fc1802() 373 []() -> SkPath {
374 SkPath path;
375 path.moveTo( 0, 1.0927740941146660348e+24);
376 path.lineTo(2.9333931225865729333e+32, 16476101);
377 path.lineTo(1.0927731573659435417e+24, 1.0927740941146660348e+24);
378 path.lineTo(1.0927740941146660348e+24, 3.7616281094287041715e-37);
379 path.lineTo(1.0927740941146660348e+24, 1.0927740941146660348e+24);
380 path.lineTo(1.3061803026169399536e-33, 1.0927740941146660348e+24);
381 path.lineTo(4.7195362919941370727e-16, -8.4247545146051822591e+32);
382 return path;
383 },
384
385 // From crbug.com/844873. Crashes trying to merge a zombie edge.
__anonb55218fc1902() 386 []() -> SkPath {
387 SkPath path;
388 path.moveTo( 316.000579833984375, -4338355948977389568);
389 path.lineTo(1.5069369808623501312e+20, 75180972320904708096.0);
390 path.lineTo(1.5069369808623501312e+20, 75180972320904708096.0);
391 path.lineTo( 771.21014404296875, -4338355948977389568.0);
392 path.lineTo( 316.000579833984375, -4338355948977389568.0);
393 path.moveTo( 354.208984375, -4338355948977389568.0);
394 path.lineTo( 773.00177001953125, -4338355948977389568.0);
395 path.lineTo(1.5069369808623501312e+20, 75180972320904708096.0);
396 path.lineTo(1.5069369808623501312e+20, 75180972320904708096.0);
397 path.lineTo( 354.208984375, -4338355948977389568.0);
398 return path;
399 },
400
401 // From crbug.com/844873. Hangs repeatedly splitting alternate vertices.
__anonb55218fc1a02() 402 []() -> SkPath {
403 SkPath path;
404 path.moveTo(10, -1e+20f);
405 path.lineTo(11, 25000);
406 path.lineTo(10, 25000);
407 path.lineTo(11, 25010);
408 return path;
409 },
410
411 // Reduction from circular_arcs_stroke_and_fill_round GM which
412 // repeatedly splits on the opposite edge from case 34 above.
__anonb55218fc1b02() 413 []() -> SkPath {
414 SkPath path;
415 path.moveTo( 16.25, 26.495191574096679688);
416 path.lineTo(32.420825958251953125, 37.377376556396484375);
417 path.lineTo(25.176382064819335938, 39.31851959228515625);
418 path.moveTo( 20, 20);
419 path.lineTo(28.847436904907226562, 37.940830230712890625);
420 path.lineTo(25.17638397216796875, 39.31851959228515625);
421 return path;
422 },
423
424 // Reduction from crbug.com/843135 where an intersection is found
425 // below the bottom of both intersected edges.
__anonb55218fc1c02() 426 []() -> SkPath {
427 SkPath path;
428 path.moveTo(-2791476679359332352, 2608107002026524672);
429 path.lineTo( 0, 11.95427703857421875);
430 path.lineTo(-2781824066779086848, 2599088532777598976);
431 path.lineTo( -7772.6875, 7274);
432 return path;
433 },
434
435 // Reduction from crbug.com/843135. Exercises a case where an intersection is missed.
436 // This causes bad ordering in the active edge list.
__anonb55218fc1d02() 437 []() -> SkPath {
438 SkPath path;
439 path.moveTo(-1.0662557646016024569e+23, 9.9621425197286319718e+22);
440 path.lineTo( -121806400, 113805032);
441 path.lineTo( -120098872, 112209680);
442 path.lineTo( 6.2832999862817380468e-36, 2.9885697364807128906);
443 return path;
444 },
445
446 // Reduction from crbug.com/851409. Exercises collinear last vertex.
__anonb55218fc1e02() 447 []() -> SkPath {
448 SkPath path;
449 path.moveTo(2072553216, 0);
450 path.lineTo(2072553216, 1);
451 path.lineTo(2072553472, -13.5);
452 path.lineTo(2072553216, 0);
453 path.lineTo(2072553472, -6.5);
454 return path;
455 },
456
457 // Another reduction from crbug.com/851409. Exercises two sequential collinear edges.
__anonb55218fc1f02() 458 []() -> SkPath {
459 SkPath path;
460 path.moveTo(2072553216, 0);
461 path.lineTo(2072553216, 1);
462 path.lineTo(2072553472, -13);
463 path.lineTo(2072553216, 0);
464 path.lineTo(2072553472, -6);
465 path.lineTo(2072553472, -13);
466 return path;
467 },
468
469 // Reduction from crbug.com/860655. Cause is three collinear edges discovered during
470 // sanitize_contours pass, before the vertices have been found coincident.
__anonb55218fc2002() 471 []() -> SkPath {
472 SkPath path;
473 path.moveTo( 32572426382475264, -3053391034974208);
474 path.lineTo( 521289856, -48865776);
475 path.lineTo( 130322464, -12215873);
476 path.moveTo( 32572426382475264, -3053391034974208);
477 path.lineTo( 521289856, -48865776);
478 path.lineTo( 130322464, -12215873);
479 path.moveTo( 32572426382475264, -3053391034974208);
480 path.lineTo( 32114477642022912, -3010462031544320);
481 path.lineTo( 32111784697528320, -3010209702215680);
482 return path;
483 },
484 };
485
486 #if SK_GPU_V1
487 #include "src/gpu/ops/TriangulatingPathRenderer.h"
488 #include "src/gpu/v1/SurfaceDrawContext_v1.h"
489
490 // A simple concave path. Test this with a non-invertible matrix.
create_path_17()491 static SkPath create_path_17() {
492 SkPath path;
493 path.moveTo(20, 20);
494 path.lineTo(80, 20);
495 path.lineTo(30, 30);
496 path.lineTo(20, 80);
497 return path;
498 }
499
500 // An intersection above the first vertex in the mesh.
501 // Reduction from http://crbug.com/730687
create_path_20()502 static SkPath create_path_20() {
503 SkPath path;
504 path.moveTo( 2822128.5, 235.026336669921875);
505 path.lineTo( 2819349.25, 235.3623504638671875);
506 path.lineTo( -340558688, 23.83478546142578125);
507 path.lineTo( -340558752, 25.510419845581054688);
508 path.lineTo( -340558720, 27.18605804443359375);
509 return path;
510 }
511
512 // An intersection whose result is NaN (due to rounded-to-inf endpoint).
create_path_21()513 static SkPath create_path_21() {
514 SkPath path;
515 path.moveTo(1.7889142061167663539e+38, 39338463358011572224.0);
516 path.lineTo( 1647.4193115234375, -522.603515625);
517 path.lineTo( 1677.74560546875, -529.0028076171875);
518 path.lineTo( 1678.29541015625, -528.7847900390625);
519 path.lineTo( 1637.5167236328125, -519.79266357421875);
520 path.lineTo( 1647.4193115234375, -522.603515625);
521 return path;
522 }
523
524 // An edge collapse event which also collapses a neighbour, requiring
525 // its event to be removed.
create_path_25()526 static SkPath create_path_25() {
527 SkPath path;
528 path.moveTo( 43.44110107421875, 148.15106201171875);
529 path.lineTo( 44.64471435546875, 148.16748046875);
530 path.lineTo( 46.35009765625, 147.403076171875);
531 path.lineTo( 46.45404052734375, 148.34906005859375);
532 path.lineTo( 45.0400390625, 148.54205322265625);
533 path.lineTo( 44.624053955078125, 148.9810791015625);
534 path.lineTo( 44.59405517578125, 149.16107177734375);
535 path.lineTo( 44.877044677734375, 149.62005615234375);
536 path.lineTo(144.373016357421875, 68.8070068359375);
537 return path;
538 }
539
540 // An edge collapse event causes an edge to become collinear, requiring
541 // its event to be removed.
create_path_26()542 static SkPath create_path_26() {
543 SkPath path;
544 path.moveTo( 43.44110107421875, 148.15106201171875);
545 path.lineTo( 44.64471435546875, 148.16748046875);
546 path.lineTo( 46.35009765625, 147.403076171875);
547 path.lineTo( 46.45404052734375, 148.34906005859375);
548 path.lineTo( 45.0400390625, 148.54205322265625);
549 path.lineTo( 44.624053955078125, 148.9810791015625);
550 path.lineTo( 44.59405517578125, 149.16107177734375);
551 path.lineTo( 44.877044677734375, 149.62005615234375);
552 path.lineTo(144.373016357421875, 68.8070068359375);
553 return path;
554 }
555
556 // A path which results in non-finite points when stroked and bevelled for AA.
create_path_27()557 static SkPath create_path_27() {
558 SkPath path;
559 path.moveTo(8.5027233009104409507e+37, 1.7503381025241130639e+37);
560 path.lineTo(7.0923661737711584874e+37, 1.4600074517285415699e+37);
561 path.lineTo(7.0848733446033294691e+37, 1.4584649744781838604e+37);
562 path.lineTo(-2.0473916115129349496e+37, -4.2146796450364162012e+36);
563 path.lineTo(2.0473912312177548811e+37, 4.2146815465123165435e+36);
564 return path;
565 }
566
567 // AA stroking this path produces intersection failures on bevelling.
568 // This should skip the point, but not assert.
create_path_28()569 static SkPath create_path_28() {
570 SkPath path;
571 path.moveTo(-7.5952312625177475154e+21, -2.6819185100266674911e+24);
572 path.lineTo( 1260.3787841796875, 1727.7947998046875);
573 path.lineTo( 1260.5567626953125, 1728.0386962890625);
574 path.lineTo(1.1482511310557754163e+21, 4.054538502765980051e+23);
575 path.lineTo(-7.5952312625177475154e+21, -2.6819185100266674911e+24);
576 return path;
577 }
578
579 // A path with vertices which become infinite on AA stroking. Should not crash or assert.
create_path_31()580 static SkPath create_path_31() {
581 SkPath path;
582 path.moveTo(2.0257809259190991347e+36, -1244080640);
583 path.conicTo(2.0257809259190991347e+36, -1244080640,
584 2.0257809259190991347e+36, 0.10976474732160568237, 0.70710676908493041992);
585 path.lineTo(-10036566016, -1954718402215936);
586 path.conicTo(-1.1375507718551896064e+20, -1954721086570496,
587 10036566016, -1954721086570496, 0.70710676908493041992);
588 return path;
589 }
590
591 // Reduction from crbug.com/851914.
create_path_38()592 static SkPath create_path_38() {
593 SkPath path;
594 path.moveTo(14.400531768798828125, 17.711114883422851562);
595 path.lineTo(14.621990203857421875, 171563104293879808);
596 path.lineTo(14.027951240539550781, 872585759381520384);
597 path.lineTo( 14.0216827392578125, 872665817571917824);
598 path.lineTo(7.699314117431640625, -3417320793833472);
599 path.moveTo(11.606547355651855469, 17.40966796875);
600 path.lineTo( 7642114886926860288, 21.08358001708984375);
601 path.lineTo(11.606547355651855469, 21.08358001708984375);
602 return path;
603 }
604
605 // Reduction from crbug.com/860453. Tests a case where a "missing" intersection
606 // requires the active edge list to go out-of-order.
create_path_41()607 static SkPath create_path_41() {
608 SkPath path;
609 path.moveTo(72154931603311689728.0, 330.95965576171875);
610 path.lineTo(24053266013925408768.0, 78.11376953125);
611 path.lineTo(1.2031099003292404941e+20, 387.168731689453125);
612 path.lineTo(68859835992355373056.0, 346.55047607421875);
613 path.lineTo(76451708695451009024.0, 337.780029296875);
614 path.moveTo(-20815817797613387776.0, 18065700622522384384.0);
615 path.lineTo(-72144121204987396096.0, 142.855804443359375);
616 path.lineTo(72144121204987396096.0, 325.184783935546875);
617 path.lineTo(1.2347242901040791552e+20, 18065700622522384384.0);
618 return path;
619 }
620
621 // Reduction from crbug.com/866319. Cause is edges that are collinear when tested from
622 // one side, but non-collinear when tested from the other.
create_path_43()623 static SkPath create_path_43() {
624 SkPath path;
625 path.moveTo( 307316821852160, -28808363114496);
626 path.lineTo( 307165222928384, -28794154909696);
627 path.lineTo( 307013691113472, -28779948802048);
628 path.lineTo( 306862159298560, -28765744791552);
629 path.lineTo( 306870313025536, -28766508154880);
630 path.lineTo( 307049695019008, -28783327313920);
631 path.lineTo( 307408660332544, -28816974020608);
632 return path;
633 }
634
635 // Reduction from crbug.com/966696
create_path_44()636 static SkPath create_path_44() {
637 SkPath path;
638 path.moveTo(114.4606170654296875, 186.443878173828125);
639 path.lineTo( 91.5394744873046875, 185.4189453125);
640 path.lineTo(306.45538330078125, 3203.986083984375);
641 path.moveTo(16276206965409972224.0, 815.59393310546875);
642 path.lineTo(-3.541605062372533207e+20, 487.7236328125);
643 path.lineTo(-3.541605062372533207e+20, 168.204071044921875);
644 path.lineTo(16276206965409972224.0, 496.07427978515625);
645 path.moveTo(-3.541605062372533207e+20, 167.00958251953125);
646 path.lineTo(-3.541605062372533207e+20, 488.32086181640625);
647 path.lineTo(16276206965409972224.0, 816.78839111328125);
648 path.lineTo(16276206965409972224.0, 495.47705078125);
649 return path;
650 }
651
652 // Reduction from crbug.com/966274.
create_path_45()653 static SkPath create_path_45() {
654 SkPath path;
655 path.moveTo( 706471854080, 379003666432);
656 path.lineTo( 706503180288, 379020443648);
657 path.lineTo( 706595717120, 379070087168);
658 path.lineTo( 706626060288, 379086372864);
659 path.lineTo( 706656141312, 379102527488);
660 path.lineTo( 706774171648, 379165835264);
661 path.lineTo( 706803073024, 379181334528);
662 path.lineTo( 706831712256, 379196702720);
663 path.lineTo( 706860154880, 379211939840);
664 path.lineTo( 706888335360, 379227078656);
665 path.lineTo( 706916253696, 379242053632);
666 path.lineTo( 706956820480, 379263811584);
667 path.lineTo( 706929098752, 379248934912);
668 path.lineTo( 706901114880, 379233927168);
669 path.lineTo( 706872934400, 379218821120);
670 path.lineTo( 706844491776, 379203551232);
671 path.lineTo( 706815787008, 379188183040);
672 path.lineTo( 706786885632, 379172651008);
673 path.lineTo( 706757722112, 379156987904);
674 path.lineTo( 706728296448, 379141226496);
675 path.lineTo( 706698608640, 379125301248);
676 path.lineTo( 706668724224, 379109244928);
677 path.lineTo( 706638577664, 379093090304);
678 path.lineTo( 706608168960, 379076771840);
679 path.lineTo( 706484174848, 379010252800);
680 return path;
681 }
682
683 // Reduction from crbug.com/969359. Inf generated by intersections
684 // causes NaN in subsequent intersections, leading to assert or hang.
685
create_path_46()686 static SkPath create_path_46() {
687 SkPath path;
688 path.moveTo(1.0321827899075254821e+37, -5.1199920965387697886e+37);
689 path.lineTo(-1.0321827899075254821e+37, 5.1199920965387697886e+37);
690 path.lineTo(-1.0425214946728668754e+37, 4.5731834042267216669e+37);
691 path.moveTo(-9.5077331762291841872e+36, 8.1304868292377430302e+37);
692 path.lineTo(9.5077331762291841872e+36, -8.1304868292377430302e+37);
693 path.lineTo(1.0795449417808426232e+37, 1.2246856113744539311e+37);
694 path.moveTo(-165.8018341064453125, -44.859375);
695 path.lineTo(-9.558702871563160835e+36, -7.9814405281448285475e+37);
696 path.lineTo(-9.4147814283168490381e+36, -8.3935116522790983488e+37);
697 return path;
698 }
699
create_linear_gradient_processor(GrRecordingContext * rContext)700 static std::unique_ptr<GrFragmentProcessor> create_linear_gradient_processor(
701 GrRecordingContext* rContext) {
702
703 SkPoint pts[2] = { {0, 0}, {1, 1} };
704 SkColor colors[2] = { SK_ColorGREEN, SK_ColorBLUE };
705 sk_sp<SkShader> shader = SkGradientShader::MakeLinear(
706 pts, colors, nullptr, SK_ARRAY_COUNT(colors), SkTileMode::kClamp);
707 GrColorInfo colorInfo(GrColorType::kRGBA_8888, kPremul_SkAlphaType, nullptr);
708 SkSimpleMatrixProvider matrixProvider(SkMatrix::I());
709 return as_SB(shader)->asFragmentProcessor({rContext, matrixProvider, &colorInfo});
710 }
711
test_path(GrRecordingContext * rContext,skgpu::v1::SurfaceDrawContext * sdc,const SkPath & path,const SkMatrix & matrix=SkMatrix::I (),GrAAType aaType=GrAAType::kNone,std::unique_ptr<GrFragmentProcessor> fp=nullptr)712 static void test_path(GrRecordingContext* rContext,
713 skgpu::v1::SurfaceDrawContext* sdc,
714 const SkPath& path,
715 const SkMatrix& matrix = SkMatrix::I(),
716 GrAAType aaType = GrAAType::kNone,
717 std::unique_ptr<GrFragmentProcessor> fp = nullptr) {
718 skgpu::v1::TriangulatingPathRenderer pr;
719 pr.setMaxVerbCount(100);
720
721 GrPaint paint;
722 paint.setXPFactory(GrPorterDuffXPFactory::Get(SkBlendMode::kSrc));
723 if (fp) {
724 paint.setColorFragmentProcessor(std::move(fp));
725 }
726
727 SkIRect clipConservativeBounds = SkIRect::MakeWH(sdc->width(), sdc->height());
728 GrStyle style(SkStrokeRec::kFill_InitStyle);
729 GrStyledShape shape(path, style);
730 skgpu::v1::PathRenderer::DrawPathArgs args{rContext,
731 std::move(paint),
732 &GrUserStencilSettings::kUnused,
733 sdc,
734 nullptr,
735 &clipConservativeBounds,
736 &matrix,
737 &shape,
738 aaType,
739 false};
740 pr.drawPath(args);
741 }
742
DEF_GPUTEST_FOR_ALL_CONTEXTS(TriangulatingPathRendererTests,reporter,ctxInfo)743 DEF_GPUTEST_FOR_ALL_CONTEXTS(TriangulatingPathRendererTests, reporter, ctxInfo) {
744 auto ctx = ctxInfo.directContext();
745 auto sdc = skgpu::v1::SurfaceDrawContext::Make(
746 ctx, GrColorType::kRGBA_8888, nullptr, SkBackingFit::kApprox, {800, 800},
747 SkSurfaceProps(), 1, GrMipmapped::kNo, GrProtected::kNo, kTopLeft_GrSurfaceOrigin);
748 if (!sdc) {
749 return;
750 }
751
752 ctx->flushAndSubmit();
753 // Adding discard to appease vulkan validation warning about loading uninitialized data on draw
754 sdc->discard();
755
756 for (CreatePathFn createPath : kNonEdgeAAPaths) {
757 test_path(ctx, sdc.get(), createPath());
758 }
759 SkMatrix nonInvertibleMatrix = SkMatrix::Scale(0, 0);
760 std::unique_ptr<GrFragmentProcessor> fp(create_linear_gradient_processor(ctx));
761 test_path(ctx, sdc.get(), create_path_17(), nonInvertibleMatrix, GrAAType::kCoverage,
762 std::move(fp));
763 test_path(ctx, sdc.get(), create_path_20(), SkMatrix(), GrAAType::kCoverage);
764 test_path(ctx, sdc.get(), create_path_21(), SkMatrix(), GrAAType::kCoverage);
765 test_path(ctx, sdc.get(), create_path_25(), SkMatrix(), GrAAType::kCoverage);
766 test_path(ctx, sdc.get(), create_path_26(), SkMatrix(), GrAAType::kCoverage);
767 test_path(ctx, sdc.get(), create_path_27(), SkMatrix(), GrAAType::kCoverage);
768 test_path(ctx, sdc.get(), create_path_28(), SkMatrix(), GrAAType::kCoverage);
769 test_path(ctx, sdc.get(), create_path_31(), SkMatrix(), GrAAType::kCoverage);
770 test_path(ctx, sdc.get(), create_path_38(), SkMatrix(), GrAAType::kCoverage);
771 test_path(ctx, sdc.get(), create_path_41(), SkMatrix(), GrAAType::kCoverage);
772 test_path(ctx, sdc.get(), create_path_43(), SkMatrix(), GrAAType::kCoverage);
773 test_path(ctx, sdc.get(), create_path_44(), SkMatrix(), GrAAType::kCoverage);
774 test_path(ctx, sdc.get(), create_path_45(), SkMatrix(), GrAAType::kCoverage);
775 test_path(ctx, sdc.get(), create_path_46(), SkMatrix(), GrAAType::kCoverage);
776 }
777
778 #endif // SK_GPU_V1
779
780 namespace {
781
782 class SimpleVertexAllocator : public GrEagerVertexAllocator {
783 public:
lock(size_t stride,int eagerCount)784 void* lock(size_t stride, int eagerCount) override {
785 SkASSERT(!fPoints);
786 SkASSERT(stride == sizeof(SkPoint));
787 fPoints.reset(eagerCount);
788 return fPoints;
789 }
unlock(int actualCount)790 void unlock(int actualCount) override {}
operator [](int idx) const791 SkPoint operator[](int idx) const { return fPoints[idx]; }
792 SkAutoTMalloc<SkPoint> fPoints;
793 };
794
795 } // namespace
796
797 struct Edge {
reverseEdge798 Edge reverse() const { return {fP1, fP0}; }
799 SkPoint fP0, fP1;
800 };
801
operator <(const Edge & a,const Edge & b)802 static bool operator<(const Edge& a, const Edge& b) {
803 if (a.fP0.fX != b.fP0.fX) {
804 return a.fP0.fX < b.fP0.fX;
805 }
806 if (a.fP0.fY != b.fP0.fY) {
807 return a.fP0.fY < b.fP0.fY;
808 }
809 if (a.fP1.fX != b.fP1.fX) {
810 return a.fP1.fX < b.fP1.fX;
811 }
812 if (a.fP1.fY != b.fP1.fY) {
813 return a.fP1.fY < b.fP1.fY;
814 }
815 return false;
816 }
817
818 using EdgeMap = std::map<Edge, int>;
819
add_edge(EdgeMap & edgeMap,SkPoint p0,SkPoint p1)820 static void add_edge(EdgeMap& edgeMap, SkPoint p0, SkPoint p1) {
821 Edge edge{p0, p1};
822 // First check if this edge already exists in reverse.
823 auto reverseIter = edgeMap.find(edge.reverse());
824 if (reverseIter != edgeMap.end()) {
825 --reverseIter->second;
826 } else {
827 ++edgeMap[edge];
828 }
829 }
830
add_tri_edges(skiatest::Reporter * r,EdgeMap & edgeMap,const SkPoint pts[3])831 static void add_tri_edges(skiatest::Reporter* r, EdgeMap& edgeMap, const SkPoint pts[3]) {
832 for (int i = 0; i < 3; ++i) {
833 SkPoint p0=pts[i], p1=pts[(i+1)%3];
834 // The triangulator shouldn't output degenerate triangles.
835 REPORTER_ASSERT(r, p0 != p1);
836 add_edge(edgeMap, p0, p1);
837 }
838 }
839
simplify(const EdgeMap & edges,SkPathFillType fillType)840 static EdgeMap simplify(const EdgeMap& edges, SkPathFillType fillType) {
841 // Prune out the edges whose count went to zero, and reverse the edges whose count is negative.
842 EdgeMap simplifiedEdges;
843 for (auto [edge, count] : edges) {
844 // We should only have one ordering of any given edge.
845 SkASSERT(edges.find(edge.reverse()) == edges.end());
846 if (fillType == SkPathFillType::kEvenOdd) {
847 count = abs(count) & 1;
848 }
849 if (count > 0) {
850 simplifiedEdges[edge] = count;
851 } else if (count < 0) {
852 simplifiedEdges[edge.reverse()] = -count;
853 }
854 }
855 return simplifiedEdges;
856 }
857
verify_simple_inner_polygons(skiatest::Reporter * r,const char * shapeName,SkPath path)858 static void verify_simple_inner_polygons(skiatest::Reporter* r, const char* shapeName,
859 SkPath path) {
860 for (auto fillType : {SkPathFillType::kWinding}) {
861 path.setFillType(fillType);
862 SkArenaAlloc arena(GrTriangulator::kArenaDefaultChunkSize);
863 GrInnerFanTriangulator::BreadcrumbTriangleList breadcrumbs;
864 SimpleVertexAllocator vertexAlloc;
865 int vertexCount;
866 {
867 bool isLinear;
868 GrInnerFanTriangulator triangulator(path, &arena);
869 vertexCount = triangulator.pathToTriangles(&vertexAlloc, &breadcrumbs, &isLinear);
870 }
871
872 // Count up all the triangulated edges.
873 EdgeMap trianglePlusBreadcrumbEdges;
874 for (int i = 0; i < vertexCount; i += 3) {
875 add_tri_edges(r, trianglePlusBreadcrumbEdges, vertexAlloc.fPoints.data() + i);
876 }
877 // Count up all the breadcrumb edges.
878 int breadcrumbCount = 0;
879 for (const auto* node = breadcrumbs.head(); node; node = node->fNext) {
880 add_tri_edges(r, trianglePlusBreadcrumbEdges, node->fPts);
881 ++breadcrumbCount;
882 }
883 REPORTER_ASSERT(r, breadcrumbCount == breadcrumbs.count());
884 // The triangulated + breadcrumb edges should cancel out to the inner polygon edges.
885 trianglePlusBreadcrumbEdges = simplify(trianglePlusBreadcrumbEdges, path.getFillType());
886
887 // Build the inner polygon edges.
888 EdgeMap innerFanEdges;
889 SkPoint startPoint{}, lastPoint{};
890 for (auto [verb, pts, w] : SkPathPriv::Iterate(path)) {
891 switch (verb) {
892 case SkPathVerb::kMove:
893 if (lastPoint != startPoint) {
894 add_edge(innerFanEdges, lastPoint, startPoint);
895 }
896 lastPoint = startPoint = pts[0];
897 continue;
898 case SkPathVerb::kClose:
899 lastPoint = startPoint;
900 break;
901 case SkPathVerb::kLine:
902 lastPoint = pts[1];
903 break;
904 case SkPathVerb::kQuad:
905 case SkPathVerb::kConic:
906 lastPoint = pts[2];
907 break;
908 case SkPathVerb::kCubic:
909 lastPoint = pts[3];
910 break;
911 }
912 if (pts[0] != lastPoint) {
913 add_edge(innerFanEdges, pts[0], lastPoint);
914 }
915 }
916 if (lastPoint != startPoint) {
917 add_edge(innerFanEdges, lastPoint, startPoint);
918 }
919 innerFanEdges = simplify(innerFanEdges, path.getFillType());
920
921 // The triangulated + breadcrumb edges should cancel out to the inner polygon edges. First
922 // verify that every inner polygon edge can be found in the triangulation.
923 for (auto [edge, count] : innerFanEdges) {
924 auto it = trianglePlusBreadcrumbEdges.find(edge);
925 if (it != trianglePlusBreadcrumbEdges.end()) {
926 it->second -= count;
927 if (it->second == 0) {
928 trianglePlusBreadcrumbEdges.erase(it);
929 }
930 continue;
931 }
932 it = trianglePlusBreadcrumbEdges.find(edge.reverse());
933 if (it != trianglePlusBreadcrumbEdges.end()) {
934 it->second += count;
935 if (it->second == 0) {
936 trianglePlusBreadcrumbEdges.erase(it);
937 }
938 continue;
939 }
940 ERRORF(r, "error: %s: edge [%g,%g]:[%g,%g] not found in triangulation.",
941 shapeName, edge.fP0.fX, edge.fP0.fY, edge.fP1.fX, edge.fP1.fY);
942 return;
943 }
944 // Now verify that there are no spurious edges in the triangulation.
945 //
946 // NOTE: The triangulator's definition of wind isn't always correct for edges that run
947 // exactly parallel to the sweep (either vertical or horizontal edges). This doesn't
948 // actually matter though because T-junction artifacts don't happen on axis-aligned edges.
949 // Tolerate spurious edges that (1) come in pairs of 2, and (2) are either exactly
950 // horizontal or exactly vertical exclusively.
951 bool hasSpuriousHorz=false, hasSpuriousVert=false;
952 for (auto [edge, count] : trianglePlusBreadcrumbEdges) {
953 if (count % 2 == 0) {
954 if (edge.fP0.fX == edge.fP1.fX && !hasSpuriousVert) {
955 hasSpuriousHorz = true;
956 continue;
957 }
958 if (edge.fP0.fY == edge.fP1.fY && !hasSpuriousHorz) {
959 hasSpuriousVert = true;
960 continue;
961 }
962 }
963 ERRORF(r, "error: %s: spurious edge [%g,%g]:[%g,%g] found in triangulation.",
964 shapeName, edge.fP0.fX, edge.fP0.fY, edge.fP1.fX, edge.fP1.fY);
965 return;
966 }
967 }
968 }
969
DEF_TEST(GrInnerFanTriangulator,r)970 DEF_TEST(GrInnerFanTriangulator, r) {
971 verify_simple_inner_polygons(r, "simple triangle", SkPath().lineTo(1,0).lineTo(0,1));
972 verify_simple_inner_polygons(r, "simple square", SkPath().lineTo(1,0).lineTo(1,1).lineTo(0,1));
973 verify_simple_inner_polygons(r, "concave polygon", SkPath()
974 .lineTo(1,0).lineTo(.5f,.5f).lineTo(1,1).lineTo(0,1));
975 verify_simple_inner_polygons(r, "double wound triangle", SkPath()
976 .lineTo(1,0).lineTo(0,1).lineTo(0,0).lineTo(1,0).lineTo(0,1));
977 verify_simple_inner_polygons(r, "self-intersecting bowtie", SkPath()
978 .lineTo(1,0).lineTo(0,1).lineTo(1,1));
979 verify_simple_inner_polygons(r, "asymmetrical bowtie", SkPath()
980 .lineTo(1,0).lineTo(0,1).lineTo(.1f,-.1f));
981 verify_simple_inner_polygons(r, "bowtie with extremely small section", SkPath()
982 .lineTo(1,0).lineTo(0,1).lineTo(1e-6f,-1e-6f));
983 verify_simple_inner_polygons(r, "intersecting squares", SkPath()
984 .lineTo(1,0).lineTo(1,1).lineTo(0,1)
985 .moveTo(.5f,.5f).lineTo(1.5f,.5f).lineTo(1.5f,1.5f).lineTo(.5f,1.5f).close());
986 verify_simple_inner_polygons(r, "6-point \"Star of David\"", SkPath()
987 .moveTo(cosf(-SK_ScalarPI/3), sinf(-SK_ScalarPI/3))
988 .lineTo(cosf(SK_ScalarPI/3), sinf(SK_ScalarPI/3))
989 .lineTo(cosf(SK_ScalarPI), sinf(SK_ScalarPI))
990 .moveTo(cosf(0), sinf(0))
991 .lineTo(cosf(2*SK_ScalarPI/3), sinf(2*SK_ScalarPI/3))
992 .lineTo(cosf(-2*SK_ScalarPI/3), sinf(-2*SK_ScalarPI/3)));
993 verify_simple_inner_polygons(r, "double wound \"Star of David\"", SkPath()
994 .moveTo(cosf(-SK_ScalarPI/3), sinf(-SK_ScalarPI/3))
995 .lineTo(cosf(SK_ScalarPI/3), sinf(SK_ScalarPI/3))
996 .lineTo(cosf(SK_ScalarPI), sinf(SK_ScalarPI))
997 .lineTo(cosf(-SK_ScalarPI/3), sinf(-SK_ScalarPI/3))
998 .lineTo(cosf(SK_ScalarPI/3), sinf(SK_ScalarPI/3))
999 .lineTo(cosf(SK_ScalarPI), sinf(SK_ScalarPI))
1000 .moveTo(cosf(0), sinf(0))
1001 .lineTo(cosf(2*SK_ScalarPI/3), sinf(2*SK_ScalarPI/3))
1002 .lineTo(cosf(-2*SK_ScalarPI/3), sinf(-2*SK_ScalarPI/3)));
1003 verify_simple_inner_polygons(r, "5-point star", ToolUtils::make_star(SkRect::MakeWH(100, 200)));
1004 verify_simple_inner_polygons(r, "\"pointy\" intersecting triangles", SkPath()
1005 .moveTo(0,-100).lineTo(-1e-6f,100).lineTo(1e-6f,100)
1006 .moveTo(-100,0).lineTo(100,1e-6f).lineTo(100,-1e-6f));
1007 verify_simple_inner_polygons(r, "overlapping rects with vertical collinear edges", SkPath()
1008 .moveTo(0,0).lineTo(0,2).lineTo(1,2).lineTo(1,0)
1009 .moveTo(0,1).lineTo(0,3).lineTo(1,3).lineTo(1,1));
1010 verify_simple_inner_polygons(r, "overlapping rects with horizontal collinear edges", SkPath()
1011 .lineTo(2,0).lineTo(2,1).lineTo(0,1)
1012 .moveTo(1,0).lineTo(3,0).lineTo(3,1).lineTo(1,1).close());
1013 for (int i = 0; i < (int)SK_ARRAY_COUNT(kNonEdgeAAPaths); ++i) {
1014 verify_simple_inner_polygons(r, SkStringPrintf("kNonEdgeAAPaths[%i]", i).c_str(),
1015 kNonEdgeAAPaths[i]());
1016 }
1017 SkRandom rand;
1018 for (int i = 0; i < 50; ++i) {
1019 auto randomPath = SkPath().moveTo(rand.nextF(), rand.nextF());
1020 for (int j = 0; j < i; ++j) {
1021 randomPath.lineTo(rand.nextF(), rand.nextF());
1022 }
1023 verify_simple_inner_polygons(r, SkStringPrintf("random_path_%i", i).c_str(), randomPath);
1024 }
1025 }
1026
