Flutter Engine
The Flutter Engine
PathOpsCubicIntersectionTest.cpp
Go to the documentation of this file.
1/*
2 * Copyright 2012 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#include "include/core/SkPoint.h"
8#include "include/core/SkScalar.h"
9#include "include/core/SkTypes.h"
10#include "include/private/base/SkDebug.h"
11#include "src/core/SkGeometry.h"
12#include "src/pathops/SkIntersections.h"
13#include "src/pathops/SkPathOpsCubic.h"
14#include "src/pathops/SkPathOpsDebug.h"
15#include "src/pathops/SkPathOpsPoint.h"
16#include "src/pathops/SkPathOpsRect.h"
17#include "src/pathops/SkPathOpsTypes.h"
18#include "src/pathops/SkReduceOrder.h"
19#include "tests/PathOpsCubicIntersectionTestData.h"
20#include "tests/PathOpsTestCommon.h"
21#include "tests/Test.h"
22
23#include <array>
24#include <cstdlib>
25
26using namespace PathOpsCubicIntersectionTestData;
27
28static constexpr int kFirstCubicIntersectionTest = 9;
29
30static void standardTestCases(skiatest::Reporter* reporter) {
31 for (size_t index = kFirstCubicIntersectionTest; index < tests_count; ++index) {
32 int iIndex = static_cast<int>(index);
33 const CubicPts& cubic1 = tests[index][0];
34 const CubicPts& cubic2 = tests[index][1];
35 SkDCubic c1, c2;
36 c1.debugSet(cubic1.fPts);
37 c2.debugSet(cubic2.fPts);
38 SkReduceOrder reduce1, reduce2;
39 int order1 = reduce1.reduce(c1, SkReduceOrder::kNo_Quadratics);
40 int order2 = reduce2.reduce(c2, SkReduceOrder::kNo_Quadratics);
41 const bool showSkipped = false;
42 if (order1 < 4) {
43 if (showSkipped) {
44 SkDebugf("%s [%d] cubic1 order=%d\n", __FUNCTION__, iIndex, order1);
45 }
46 continue;
47 }
48 if (order2 < 4) {
49 if (showSkipped) {
50 SkDebugf("%s [%d] cubic2 order=%d\n", __FUNCTION__, iIndex, order2);
51 }
52 continue;
53 }
54 SkIntersections tIntersections;
55 tIntersections.intersect(c1, c2);
56 if (!tIntersections.used()) {
57 if (showSkipped) {
58 SkDebugf("%s [%d] no intersection\n", __FUNCTION__, iIndex);
59 }
60 continue;
61 }
62 if (tIntersections.isCoincident(0)) {
63 if (showSkipped) {
64 SkDebugf("%s [%d] coincident\n", __FUNCTION__, iIndex);
65 }
66 continue;
67 }
68 for (int pt = 0; pt < tIntersections.used(); ++pt) {
69 double tt1 = tIntersections[0][pt];
70 SkDPoint xy1 = c1.ptAtT(tt1);
71 double tt2 = tIntersections[1][pt];
72 SkDPoint xy2 = c2.ptAtT(tt2);
73 if (!xy1.approximatelyEqual(xy2)) {
74 SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n",
75 __FUNCTION__, (int)index, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY);
76 }
77 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
78 }
79 reporter->bumpTestCount();
80 }
81}
82
83static const CubicPts testSet[] = {
84// FIXME: uncommenting these two will cause this to fail
85// this results in two curves very nearly but not exactly coincident
86#if 0
87{{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306},
88 {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}},
89{{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826},
90 {75.3863417, 18.24489}}},
91#endif
92
93{{{0, 0}, {0, 1}, {1, 1}, {1, 0}}},
94{{{1, 0}, {0, 0}, {0, 1}, {1, 1}}},
95
96{{{0, 1}, {4, 5}, {1, 0}, {5, 3}}},
97{{{0, 1}, {3, 5}, {1, 0}, {5, 4}}},
98
99{{{0, 1}, {1, 6}, {1, 0}, {1, 0}}},
100{{{0, 1}, {0, 1}, {1, 0}, {6, 1}}},
101
102{{{0, 1}, {3, 4}, {1, 0}, {5, 1}}},
103{{{0, 1}, {1, 5}, {1, 0}, {4, 3}}},
104
105{{{0, 1}, {1, 2}, {1, 0}, {6, 1}}},
106{{{0, 1}, {1, 6}, {1, 0}, {2, 1}}},
107
108{{{0, 1}, {0, 5}, {1, 0}, {4, 0}}},
109{{{0, 1}, {0, 4}, {1, 0}, {5, 0}}},
110
111{{{0, 1}, {3, 4}, {1, 0}, {3, 0}}},
112{{{0, 1}, {0, 3}, {1, 0}, {4, 3}}},
113
114{{{0, 0}, {1, 2}, {3, 4}, {4, 4}}},
115{{{0, 0}, {1, 2}, {3, 4}, {4, 4}}},
116{{{4, 4}, {3, 4}, {1, 2}, {0, 0}}},
117
118{{{0, 1}, {2, 3}, {1, 0}, {1, 0}}},
119{{{0, 1}, {0, 1}, {1, 0}, {3, 2}}},
120
121{{{0, 2}, {0, 1}, {1, 0}, {1, 0}}},
122{{{0, 1}, {0, 1}, {2, 0}, {1, 0}}},
123
124{{{0, 1}, {0, 2}, {1, 0}, {1, 0}}},
125{{{0, 1}, {0, 1}, {1, 0}, {2, 0}}},
126
127{{{0, 1}, {1, 6}, {1, 0}, {2, 0}}},
128{{{0, 1}, {0, 2}, {1, 0}, {6, 1}}},
129
130{{{0, 1}, {5, 6}, {1, 0}, {1, 0}}},
131{{{0, 1}, {0, 1}, {1, 0}, {6, 5}}},
132
133{{{95.837747722788592, 45.025976907939643}, {16.564570095652982, 0.72959763963222402},
134 {63.209855865319199, 68.047528419665767}, {57.640240647662544, 59.524565264361243}}},
135{{{51.593891741518817, 38.53849970667553}, {62.34752929878772, 74.924924725166022},
136 {74.810149322641152, 34.17966562983564}, {29.368398119401373, 94.66719277886078}}},
137
138{{{39.765160968417838, 33.060396198677083}, {5.1922921581157908, 66.854301452103215},
139 {31.619281802149157, 25.269248720849514}, {81.541621071073038, 70.025341524754353}}},
140{{{46.078911165743556, 48.259962651999651}, {20.24450549867214, 49.403916182650214},
141 {0.26325131778756683, 24.46489805563581}, {15.915006546264051, 83.515023059917155}}},
142
143{{{65.454505973241524, 93.881892270353575}, {45.867360264932437, 92.723972719499827},
144 {2.1464054482739447, 74.636369140183717}, {33.774068594804994, 40.770872887582925}}},
145{{{72.963387832494163, 95.659300729473728}, {11.809496633619768, 82.209921247423594},
146 {13.456139067865974, 57.329313623406605}, {36.060621606214262, 70.867335643091849}}},
147
148{{{32.484981432782945, 75.082940782924624}, {42.467313093350882, 48.131159948246157},
149 {3.5963115764764657, 43.208665839959245}, {79.442476890721579, 89.709102357602262}}},
150{{{18.98573861410177, 93.308887208490106}, {40.405250173250792, 91.039661826118675},
151 {8.0467721950480584, 42.100282172719147}, {40.883324221187891, 26.030185504830527}}},
152
153{{{7.5374809128872498, 82.441702896003477}, {22.444346930107265, 22.138854312775123},
154 {66.76091829629658, 50.753805856571446}, {78.193478508942519, 97.7932997968948}}},
155{{{97.700573130371311, 53.53260215070685}, {87.72443481149358, 84.575876772671876},
156 {19.215031396232092, 47.032676472809484}, {11.989686410869325, 10.659507480757082}}},
157
158{{{26.192053931854691, 9.8504326817814416}, {10.174241480498686, 98.476562741434464},
159 {21.177712558385782, 33.814968789841501}, {75.329030899018534, 55.02231980442177}}},
160{{{56.222082700683771, 24.54395039218662}, {95.589995289030483, 81.050822735322086},
161 {28.180450866082897, 28.837706255185282}, {60.128952916771617, 87.311672180570511}}},
162
163{{{42.449716172390481, 52.379709366885805}, {27.896043159019225, 48.797373636065686},
164 {92.770268299044233, 89.899302036454571}, {12.102066544863426, 99.43241951960718}}},
165{{{45.77532924980639, 45.958701495993274}, {37.458701356062065, 68.393691335056758},
166 {37.569326692060258, 27.673713456687381}, {60.674866037757539, 62.47349659096146}}},
167
168{{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306},
169 {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}},
170{{{61.336508189019057, 82.693132843213675}, {44.639380902349664, 54.074825790745592},
171 {16.815615499771951, 20.049704667203923}, {41.866884958868326, 56.735503699973002}}},
172
173{{{18.1312339, 31.6473732}, {95.5711034, 63.5350219}, {92.3283165, 62.0158945},
174 {18.5656052, 32.1268808}}},
175{{{97.402018, 35.7169972}, {33.1127443, 25.8935163}, {1.13970027, 54.9424981},
176 {56.4860195, 60.529264}}},
177};
178
179const int testSetCount = (int) std::size(testSet);
180
181static const CubicPts newTestSet[] = {
182
183{ { { 130.0427549999999997, 11417.41309999999976 },{ 130.2331240000000037, 11418.3192999999992 },{ 131.0370790000000056, 11419 },{ 132, 11419 } } },
184{ { { 132, 11419 },{ 130.8954319999999996, 11419 },{ 130, 11418.10449999999946 },{ 130, 11417 } } },
185
186{{{1,3}, {-1.0564518,1.79032254}, {1.45265341,0.229448318}, {1.45381773,0.22913377}}},
187{{{1.45381773,0.22913377}, {1.45425761,0.229014933}, {1.0967741,0.451612949}, {0,1}}},
188
189{{{1.64551306f, 3.57876182f}, {0.298127174f, 3.70454836f}, {-0.809808373f, 6.39524937f}, {-3.66666651f, 13.333334f}}},
190{{{1, 2}, {1, 2}, {-3.66666651f, 13.333334f}, {5, 6}}},
191
192{{{0.0660428554,1.65340209}, {-0.251940489,1.43560803}, {-0.782382965,-0.196299091}, {3.33333325,-0.666666627}}},
193{{{1,3}, {-1.22353387,1.09411383}, {0.319867611,0.12996155}, {0.886705518,0.107543148}}},
194
195{{{-0.13654758,2.10514426}, {-0.585797966,1.89349782}, {-0.807703257,-0.192306399}, {6,-1}}},
196{{{1,4}, {-2.25000453,1.42241001}, {1.1314013,0.0505309105}, {1.87140274,0.0363764353}}},
197
198{{{1.3127951622009277, 2.0637707710266113}, {1.8210518360137939, 1.9148571491241455}, {1.6106204986572266, -0.68700540065765381}, {8.5, -2.5}}},
199{{{3, 4}, {0.33333325386047363, 1.3333332538604736}, {3.6666667461395264, -0.66666674613952637}, {3.6666665077209473, -0.66666656732559204}}},
200
201{{{980.026001,1481.276}, {980.026001,1481.276}, {980.02594,1481.27576}, {980.025879,1481.27527}}},
202{{{980.025879,1481.27527}, {980.025452,1481.27222}, {980.023743,1481.26038}, {980.02179,1481.24072}}},
203
204{{{1.80943513,3.07782435}, {1.66686702,2.16806936}, {1.68301272,0}, {3,0}}},
205{{{0,1}, {0,3}, {3,2}, {5,2}}},
206
207{{{3.4386673,2.66977954}, {4.06668949,2.17046738}, {4.78887367,1.59629118}, {6,2}}},
208{{{1.71985495,3.49467373}, {2.11620402,2.7201426}, {2.91897964,1.15138781}, {6,3}}},
209
210{{{0,1}, {0.392703831,1.78540766}, {0.219947904,2.05676103}, {0.218561709,2.05630541}}},
211{{{0.218561709,2.05630541}, {0.216418028,2.05560064}, {0.624105453,1.40486407}, {4.16666651,1.00000012}}},
212
213{{{0, 1}, {3, 5}, {2, 1}, {3, 1}}},
214{{{1.01366711f, 2.21379328f}, {1.09074128f, 2.23241305f}, {1.60246587f, 0.451849401f}, {5, 3}}},
215
216{{{0, 1}, {0.541499972f, 3.16599989f}, {1.08299994f, 2.69299984f}, {2.10083938f, 1.80391729f}}},
217{{{0.806384504f, 2.85426903f}, {1.52740121f, 1.99355423f}, {2.81689167f, 0.454222918f}, {5, 1}}},
218
219{{{0, 1}, {1.90192389f, 2.90192389f}, {2.59807634f, 2.79422879f}, {3.1076951f, 2.71539044f}}},
220{{{2, 3}, {2.36602545f, 3.36602545f}, {2.330127f, 3.06217766f}, {2.28460979f, 2.67691422f}}},
221
222{{{0, 1}, {1.90192389f, 2.90192389f}, {2.59807634f, 2.79422879f}, {3.1076951f, 2.71539044f}}},
223{{{2.28460979f, 2.67691422f}, {2.20577145f, 2.00961876f}, {2.09807634f, 1.09807622f}, {4, 3}}},
224
225{{{0, 1}, {0.8211091160774231, 2.0948121547698975}, {0.91805583238601685, 2.515404224395752}, {0.91621249914169312, 2.5146586894989014}}},
226{{{0.91621249914169312, 2.5146586894989014}, {0.91132104396820068, 2.5126807689666748}, {0.21079301834106445, -0.45617169141769409}, {10.5, -1.6666665077209473}}},
227
228{{{42.6237564,68.9841232}, {32.449646,81.963089}, {14.7713947,103.565269}, {12.6310005,105.247002}}},
229{{{37.2640038,95.3540039}, {37.2640038,95.3540039}, {11.3710003,83.7339935}, {-25.0779991,124.912003}}},
230
231{{{0,1}, {4,5}, {6,0}, {1,0}}},
232{{{0,6}, {0,1}, {1,0}, {5,4}}},
233
234{{{0,1}, {4,6}, {5,1}, {6,2}}},
235{{{1,5}, {2,6}, {1,0}, {6,4}}},
236
237{{{322, 896.04803466796875}, {314.09201049804687, 833.4376220703125}, {260.24713134765625, 785}, {195, 785}}},
238{{{195, 785}, {265.14016723632812, 785}, {322, 842.30755615234375}, {322, 913}}},
239
240{{{1, 4}, {4, 5}, {3, 2}, {6, 3}}},
241{{{2, 3}, {3, 6}, {4, 1}, {5, 4}}},
242
243{{{67, 913}, {67, 917.388916015625}, {67.224380493164063, 921.72576904296875}, {67.662384033203125, 926}}},
244{{{194, 1041}, {123.85984039306641, 1041}, {67, 983.69244384765625}, {67, 913}}},
245
246{{{1,4}, {1,5}, {6,0}, {5,1}}},
247{{{0,6}, {1,5}, {4,1}, {5,1}}},
248
249{{{0,1}, {4,5}, {6,0}, {1,0}}},
250{{{0,6}, {0,1}, {1,0}, {5,4}}},
251
252{{{0,1}, {4,6}, {2,0}, {2,0}}},
253{{{0,2}, {0,2}, {1,0}, {6,4}}},
254
255{{{980.9000244140625, 1474.3280029296875}, {980.9000244140625, 1474.3280029296875}, {978.89300537109375, 1471.95703125}, {981.791015625, 1469.487060546875}}},
256{{{981.791015625, 1469.487060546875}, {981.791015625, 1469.4859619140625}, {983.3580322265625, 1472.72900390625}, {980.9000244140625, 1474.3280029296875}}},
257
258{{{275,532}, {277.209137,532}, {279,530.209106}, {279,528}}},
259{{{278,529}, {278,530.65686}, {276.65686,532}, {275,532}}},
260
261#if 0 // FIXME: asserts coincidence, not working yet
262{{{195, 785}, {124.30755615234375, 785}, {67, 841.85986328125}, {67, 912}}},
263{{{67, 913}, {67, 842.30755615234375}, {123.85984039306641, 785}, {194, 785}}},
264#endif
265
266{{{149,710.001465}, {149.000809,712.209961}, {150.791367,714}, {153,714}}},
267{{{154,715}, {151.238571,715}, {149,712.761414}, {149,710}}},
268
269{{{1,2}, {1,2}, {2,0}, {6,0}}},
270{{{0,2}, {0,6}, {2,1}, {2,1}}},
271
272{{{0,1}, {2,3}, {5,1}, {4,3}}},
273{{{1,5}, {3,4}, {1,0}, {3,2}}},
274
275{{{399,657}, {399,661.970581}, {403.029449,666}, {408,666}}},
276{{{406,666}, {402.686279,666}, {400,663.313721}, {400,660}}},
277
278{{{0,5}, {3,5}, {3,0}, {3,2}}},
279{{{0,3}, {2,3}, {5,0}, {5,3}}},
280
281{{{132, 11419}, {130.89543151855469, 11419}, {130, 11418.1044921875}, {130, 11417}}},
282
283{{{3, 4}, {1, 5}, {4, 3}, {6, 4}}},
284{{{3, 4}, {4, 6}, {4, 3}, {5, 1}}},
285
286{{{130.04275512695312, 11417.413085937500 },
287 {130.23312377929687, 11418.319335937500 },
288 {131.03707885742187, 11419.000000000000 },
289 {132.00000000000000, 11419.000000000000 }}},
290
291{{{132.00000000000000, 11419.000000000000 },
292 {130.89543151855469, 11419.000000000000 },
293 {130.00000000000000, 11418.104492187500 },
294 {130.00000000000000, 11417.000000000000 }}},
295
296{{{1.0516976506771041, 2.9684399028541346 },
297 {1.0604363140895228, 2.9633503074444141 },
298 {1.0692548215065762, 2.9580354426587459 },
299 {1.0781560339512140, 2.9525043684031349 }}},
300
301{{{1.0523038101345104, 2.9523755204833737 },
302 {1.0607035288264237, 2.9580853881628375 },
303 {1.0690530472271964, 2.9633896794787749 },
304 {1.0773566568712512, 2.9682969775000219 }}},
305
306{{{1.0386522625066592, 2.9759024812329078 },
307 {1.0559713690392631, 2.9661782500838885 },
308 {1.0736041309019990, 2.9555348259177858 },
309 {1.0915734362784633, 2.9440446879826569 }}},
310
311{{{1.0396670794879301, 2.9435062123457261 },
312 {1.0565690546812769, 2.9557413250983462 },
313 {1.0732616463413533, 2.9663369676594282 },
314 {1.0897791867435489, 2.9753618045797472 }}},
315
316{{{0.8685656183311091, 3.0409266475785208 },
317 {0.99189542936395292, 3.0212163698184424 },
318 {1.1302108367493320, 2.9265646471747306 },
319 {1.2952305904872474, 2.7940808546473788 }}},
320
321{{{0.85437872843682727, 2.7536036928549055 },
322 {1.0045584590592620, 2.9493041024831705 },
323 {1.1336998329885613, 3.0248027987251747 },
324 {1.2593809752247314, 3.0152560315809107 }}},
325
326{{{0, 1}, {1, 6}, {1, 0}, {6, 2}}},
327{{{0, 1}, {2, 6}, {1, 0}, {6, 1}}},
328
329{{{134,11414}, {131.990234375,11414}, {130.32666015625,11415.482421875}, {130.04275512695312,11417.4130859375}}},
330{{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}},
331
332{{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}},
333{{{130.04275512695312,11417.4130859375}, {130.23312377929687,11418.3193359375}, {131.03707885742187,11419}, {132,11419}}},
334
335{{{0, 1}, {2, 3}, {5, 1}, {4, 3}}},
336{{{1, 5}, {3, 4}, {1, 0}, {3, 2}}},
337
338{{{3, 5}, {1, 6}, {5, 0}, {3, 1}}},
339{{{0, 5}, {1, 3}, {5, 3}, {6, 1}}},
340
341{{{0, 1}, {1, 5}, {1, 0}, {1, 0}}},
342{{{0, 1}, {0, 1}, {1, 0}, {5, 1}}},
343
344{{{1, 3}, {5, 6}, {5, 3}, {5, 4}}},
345{{{3, 5}, {4, 5}, {3, 1}, {6, 5}}},
346
347{{{0, 5}, {0, 5}, {5, 4}, {6, 4}}},
348{{{4, 5}, {4, 6}, {5, 0}, {5, 0}}},
349
350{{{0, 4}, {1, 3}, {5, 4}, {4, 2}}},
351{{{4, 5}, {2, 4}, {4, 0}, {3, 1}}},
352
353{{{0, 2}, {1, 5}, {3, 2}, {4, 1}}},
354{{{2, 3}, {1, 4}, {2, 0}, {5, 1}}},
355
356{{{0, 2}, {2, 3}, {5, 1}, {3, 2}}},
357{{{1, 5}, {2, 3}, {2, 0}, {3, 2}}},
358
359{{{2, 6}, {4, 5}, {1, 0}, {6, 1}}},
360{{{0, 1}, {1, 6}, {6, 2}, {5, 4}}},
361
362{{{0, 1}, {1, 2}, {6, 5}, {5, 4}}},
363{{{5, 6}, {4, 5}, {1, 0}, {2, 1}}},
364
365{{{2.5119999999999996, 1.5710000000000002}, {2.6399999999999983, 1.6599999999999997},
366 {2.8000000000000007, 1.8000000000000003}, {3, 2}}},
367{{{2.4181876227114887, 1.9849772580462195}, {2.8269904869227211, 2.009330650246834},
368 {3.2004679292461624, 1.9942047174679169}, {3.4986199496818058, 2.0035994597094731}}},
369
370{{{2, 3}, {1, 4}, {1, 0}, {6, 0}}},
371{{{0, 1}, {0, 6}, {3, 2}, {4, 1}}},
372
373{{{0, 2}, {1, 5}, {1, 0}, {6, 1}}},
374{{{0, 1}, {1, 6}, {2, 0}, {5, 1}}},
375
376{{{0, 1}, {1, 5}, {2, 1}, {4, 0}}},
377{{{1, 2}, {0, 4}, {1, 0}, {5, 1}}},
378
379{{{0, 1}, {3, 5}, {2, 1}, {3, 1}}},
380{{{1, 2}, {1, 3}, {1, 0}, {5, 3}}},
381
382{{{0, 1}, {2, 5}, {6, 0}, {5, 3}}},
383{{{0, 6}, {3, 5}, {1, 0}, {5, 2}}},
384
385{{{0, 1}, {3, 6}, {1, 0}, {5, 2}}},
386{{{0, 1}, {2, 5}, {1, 0}, {6, 3}}},
387
388{{{1, 2}, {5, 6}, {1, 0}, {1, 0}}},
389{{{0, 1}, {0, 1}, {2, 1}, {6, 5}}},
390
391{{{0, 6}, {1, 2}, {1, 0}, {1, 0}}},
392{{{0, 1}, {0, 1}, {6, 0}, {2, 1}}},
393
394{{{0, 2}, {0, 1}, {3, 0}, {1, 0}}},
395{{{0, 3}, {0, 1}, {2, 0}, {1, 0}}},
396};
397
398const int newTestSetCount = (int) std::size(newTestSet);
399static void oneOff(skiatest::Reporter* reporter, const CubicPts& cubic1, const CubicPts& cubic2,
400 bool coin) {
401 SkDCubic c1, c2;
402 c1.debugSet(cubic1.fPts);
403 c2.debugSet(cubic2.fPts);
404 SkASSERT(ValidCubic(c1));
405 SkASSERT(ValidCubic(c2));
406#if ONE_OFF_DEBUG
407 SkDebugf("computed quadratics given\n");
408 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
409 cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY,
410 cubic1[2].fX, cubic1[2].fY, cubic1[3].fX, cubic1[3].fY);
411 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
412 cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY,
413 cubic2[2].fX, cubic2[2].fY, cubic2[3].fX, cubic2[3].fY);
414#endif
415 SkIntersections intersections;
416 intersections.intersect(c1, c2);
417#if DEBUG_T_SECT_DUMP == 3
418 SkDebugf("</div>\n\n");
419 SkDebugf("<script type=\"text/javascript\">\n\n");
420 SkDebugf("var testDivs = [\n");
421 for (int index = 1; index <= gDumpTSectNum; ++index) {
422 SkDebugf("sect%d,\n", index);
423 }
424#endif
425 REPORTER_ASSERT(reporter, !coin || intersections.used() >= 2);
426 double tt1, tt2;
427 SkDPoint xy1, xy2;
428 for (int pt3 = 0; pt3 < intersections.used(); ++pt3) {
429 tt1 = intersections[0][pt3];
430 xy1 = c1.ptAtT(tt1);
431 tt2 = intersections[1][pt3];
432 xy2 = c2.ptAtT(tt2);
433 const SkDPoint& iPt = intersections.pt(pt3);
434#if ONE_OFF_DEBUG
435 SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n",
436 __FUNCTION__, tt1, xy1.fX, xy1.fY, iPt.fX,
437 iPt.fY, xy2.fX, xy2.fY, tt2);
438#endif
439 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(iPt));
440 REPORTER_ASSERT(reporter, xy2.approximatelyEqual(iPt));
441 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
442 }
443 reporter->bumpTestCount();
444}
445
446static void oneOff(skiatest::Reporter* reporter, int outer, int inner) {
447 const CubicPts& cubic1 = testSet[outer];
448 const CubicPts& cubic2 = testSet[inner];
449 oneOff(reporter, cubic1, cubic2, false);
450}
451
452static void newOneOff(skiatest::Reporter* reporter, int outer, int inner) {
453 const CubicPts& cubic1 = newTestSet[outer];
454 const CubicPts& cubic2 = newTestSet[inner];
455 oneOff(reporter, cubic1, cubic2, false);
456}
457
458static void testsOneOff(skiatest::Reporter* reporter, int index) {
459 const CubicPts& cubic1 = tests[index][0];
460 const CubicPts& cubic2 = tests[index][1];
461 oneOff(reporter, cubic1, cubic2, false);
462}
463
464static void oneOffTests(skiatest::Reporter* reporter) {
465 for (int outer = 0; outer < testSetCount - 1; ++outer) {
466 for (int inner = outer + 1; inner < testSetCount; ++inner) {
467 oneOff(reporter, outer, inner);
468 }
469 }
470 for (int outer = 0; outer < newTestSetCount - 1; ++outer) {
471 for (int inner = outer + 1; inner < newTestSetCount; ++inner) {
472 newOneOff(reporter, outer, inner);
473 }
474 }
475}
476
477#define DEBUG_CRASH 0
478
479static void CubicIntersection_RandTest(skiatest::Reporter* reporter) {
480 srand(0);
481 const int kNumTests = 10000000;
482#if !defined(SK_BUILD_FOR_WIN) && !defined(SK_BUILD_FOR_ANDROID)
483 unsigned seed = 0;
484#endif
485 for (int test = 0; test < kNumTests; ++test) {
486 CubicPts cubic1, cubic2;
487 for (int i = 0; i < 4; ++i) {
488 cubic1.fPts[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
489 cubic1.fPts[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
490 cubic2.fPts[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
491 cubic2.fPts[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
492 }
493 #if DEBUG_CRASH
494 char str[1024];
495 snprintf(str, sizeof(str),
496 "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n"
497 "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n",
498 cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY, cubic1[2].fX, cubic1[2].fY,
499 cubic1[3].fX, cubic1[3].fY,
500 cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY, cubic2[2].fX, cubic2[2].fY,
501 cubic2[3].fX, cubic2[3].fY);
502 #endif
503 SkDRect rect1, rect2;
504 SkDCubic c1, c2;
505 c1.debugSet(cubic1.fPts);
506 c2.debugSet(cubic2.fPts);
507 rect1.setBounds(c1);
508 rect2.setBounds(c2);
509 bool boundsIntersect = rect1.fLeft <= rect2.fRight && rect2.fLeft <= rect2.fRight
510 && rect1.fTop <= rect2.fBottom && rect2.fTop <= rect1.fBottom;
511 if (test == -1) {
512 SkDebugf("ready...\n");
513 }
514 SkIntersections intersections2;
515 int newIntersects = intersections2.intersect(c1, c2);
516 if (!boundsIntersect && newIntersects) {
517 #if DEBUG_CRASH
518 SkDebugf("%s %d unexpected intersection boundsIntersect=%d "
519 " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsIntersect,
520 newIntersects, __FUNCTION__, str);
521 #endif
522 REPORTER_ASSERT(reporter, 0);
523 }
524 for (int pt = 0; pt < intersections2.used(); ++pt) {
525 double tt1 = intersections2[0][pt];
526 SkDPoint xy1 = c1.ptAtT(tt1);
527 double tt2 = intersections2[1][pt];
528 SkDPoint xy2 = c2.ptAtT(tt2);
529 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
530 }
531 reporter->bumpTestCount();
532 }
533}
534
535static void intersectionFinder(int index0, int index1, double t1Seed, double t2Seed,
536 double t1Step, double t2Step) {
537 const CubicPts& cubic1 = newTestSet[index0];
538 const CubicPts& cubic2 = newTestSet[index1];
539 SkDPoint t1[3], t2[3];
540 bool toggle = true;
541 SkDCubic c1, c2;
542 c1.debugSet(cubic1.fPts);
543 c2.debugSet(cubic2.fPts);
544 do {
545 t1[0] = c1.ptAtT(t1Seed - t1Step);
546 t1[1] = c1.ptAtT(t1Seed);
547 t1[2] = c1.ptAtT(t1Seed + t1Step);
548 t2[0] = c2.ptAtT(t2Seed - t2Step);
549 t2[1] = c2.ptAtT(t2Seed);
550 t2[2] = c2.ptAtT(t2Seed + t2Step);
551 double dist[3][3];
552 dist[1][1] = t1[1].distance(t2[1]);
553 int best_i = 1, best_j = 1;
554 for (int i = 0; i < 3; ++i) {
555 for (int j = 0; j < 3; ++j) {
556 if (i == 1 && j == 1) {
557 continue;
558 }
559 dist[i][j] = t1[i].distance(t2[j]);
560 if (dist[best_i][best_j] > dist[i][j]) {
561 best_i = i;
562 best_j = j;
563 }
564 }
565 }
566 if (best_i == 0) {
567 t1Seed -= t1Step;
568 } else if (best_i == 2) {
569 t1Seed += t1Step;
570 }
571 if (best_j == 0) {
572 t2Seed -= t2Step;
573 } else if (best_j == 2) {
574 t2Seed += t2Step;
575 }
576 if (best_i == 1 && best_j == 1) {
577 if ((toggle ^= true)) {
578 t1Step /= 2;
579 } else {
580 t2Step /= 2;
581 }
582 }
583 } while (!t1[1].approximatelyEqual(t2[1]));
584 t1Step = t2Step = 0.1;
585 double t10 = t1Seed - t1Step * 2;
586 double t12 = t1Seed + t1Step * 2;
587 double t20 = t2Seed - t2Step * 2;
588 double t22 = t2Seed + t2Step * 2;
589 SkDPoint test;
590 while (!approximately_zero(t1Step)) {
591 test = c1.ptAtT(t10);
592 t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step;
593 t1Step /= 2;
594 }
595 t1Step = 0.1;
596 while (!approximately_zero(t1Step)) {
597 test = c1.ptAtT(t12);
598 t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step;
599 t1Step /= 2;
600 }
601 while (!approximately_zero(t2Step)) {
602 test = c2.ptAtT(t20);
603 t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step;
604 t2Step /= 2;
605 }
606 t2Step = 0.1;
607 while (!approximately_zero(t2Step)) {
608 test = c2.ptAtT(t22);
609 t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step;
610 t2Step /= 2;
611 }
612#if ONE_OFF_DEBUG
613 SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__,
614 t10, t1Seed, t12, t20, t2Seed, t22);
615 SkDPoint p10 = c1.ptAtT(t10);
616 SkDPoint p1Seed = c1.ptAtT(t1Seed);
617 SkDPoint p12 = c1.ptAtT(t12);
618 SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
619 p10.fX, p10.fY, p1Seed.fX, p1Seed.fY, p12.fX, p12.fY);
620 SkDPoint p20 = c2.ptAtT(t20);
621 SkDPoint p2Seed = c2.ptAtT(t2Seed);
622 SkDPoint p22 = c2.ptAtT(t22);
623 SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
624 p20.fX, p20.fY, p2Seed.fX, p2Seed.fY, p22.fX, p22.fY);
625#endif
626}
627
628static void CubicIntersection_IntersectionFinder() {
629// double t1Seed = 0.87;
630// double t2Seed = 0.87;
631 double t1Step = 0.000001;
632 double t2Step = 0.000001;
633 intersectionFinder(0, 1, 0.855895664, 0.864850875, t1Step, t2Step);
634 intersectionFinder(0, 1, 0.865207906, 0.865207887, t1Step, t2Step);
635 intersectionFinder(0, 1, 0.865213351, 0.865208087, t1Step, t2Step);
636}
637
638static const CubicPts selfSet[] = {
639 {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}},
640 {{{3, 6}, {2, 3}, {4, 0}, {3, 2}}},
641 {{{0, 2}, {2, 3}, {5, 1}, {3, 2}}},
642 {{{0, 2}, {3, 5}, {5, 0}, {4, 2}}},
643 {{{3.34, 8.98}, {1.95, 10.27}, {3.76, 7.65}, {4.96, 10.64}}},
644 {{{3.13, 2.74}, {1.08, 4.62}, {3.71, 0.94}, {2.01, 3.81}}},
645 {{{6.71, 3.14}, {7.99, 2.75}, {8.27, 1.96}, {6.35, 3.57}}},
646 {{{12.81, 7.27}, {7.22, 6.98}, {12.49, 8.97}, {11.42, 6.18}}},
647};
648
649int selfSetCount = (int) std::size(selfSet);
650
651static void selfOneOff(skiatest::Reporter* reporter, int setIdx) {
652 const CubicPts& cubic = selfSet[setIdx];
653 SkPoint c[4];
654 for (int i = 0; i < 4; ++i) {
655 c[i] = cubic.fPts[i].asSkPoint();
656 }
657 SkScalar loopT[3];
658 SkCubicType cubicType = SkClassifyCubic(c);
659 int breaks = SkDCubic::ComplexBreak(c, loopT);
660 SkASSERT(breaks < 2);
661 if (breaks && cubicType == SkCubicType::kLoop) {
662 SkIntersections i;
663 SkPoint twoCubics[7];
664 SkChopCubicAt(c, twoCubics, loopT[0]);
665 SkDCubic chopped[2];
666 chopped[0].set(&twoCubics[0]);
667 chopped[1].set(&twoCubics[3]);
668 int result = i.intersect(chopped[0], chopped[1]);
669 REPORTER_ASSERT(reporter, result == 2);
670 REPORTER_ASSERT(reporter, i.used() == 2);
671 for (int index = 0; index < result; ++index) {
672 SkDPoint pt1 = chopped[0].ptAtT(i[0][index]);
673 SkDPoint pt2 = chopped[1].ptAtT(i[1][index]);
674 REPORTER_ASSERT(reporter, pt1.approximatelyEqual(pt2));
675 reporter->bumpTestCount();
676 }
677 }
678}
679
680static void cubicIntersectionSelfTest(skiatest::Reporter* reporter) {
681 int firstFail = 0;
682 for (int index = firstFail; index < selfSetCount; ++index) {
683 selfOneOff(reporter, index);
684 }
685}
686
687static const CubicPts coinSet[] = {
688 {{{72.350448608398438, 27.966041564941406}, {72.58441162109375, 27.861515045166016},
689 {72.818222045898437, 27.756658554077148}, {73.394996643066406, 27.49799919128418}}},
690 {{{73.394996643066406, 27.49799919128418}, {72.818222045898437, 27.756658554077148},
691 {72.58441162109375, 27.861515045166016}, {72.350448608398438, 27.966041564941406}}},
692
693 {{{297.04998779296875, 43.928997039794922}, {297.04998779296875, 43.928997039794922},
694 {300.69699096679688, 45.391998291015625}, {306.92498779296875, 43.08599853515625}}},
695 {{{297.04998779296875, 43.928997039794922}, {297.04998779296875, 43.928997039794922},
696 {300.69699096679688, 45.391998291015625}, {306.92498779296875, 43.08599853515625}}},
697
698 {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}},
699 {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}},
700
701 {{{317, 711}, {322.52285766601562, 711}, {327, 715.4771728515625}, {327, 721}}},
702 {{{324.07107543945312, 713.928955078125}, {324.4051513671875, 714.26300048828125},
703 {324.71566772460937, 714.62060546875}, {325, 714.9990234375}}},
704};
705
706static int coinSetCount = (int) std::size(coinSet);
707
708static void coinOneOff(skiatest::Reporter* reporter, int index) {
709 const CubicPts& cubic1 = coinSet[index];
710 const CubicPts& cubic2 = coinSet[index + 1];
711 oneOff(reporter, cubic1, cubic2, true);
712}
713
714static void cubicIntersectionCoinTest(skiatest::Reporter* reporter) {
715 int firstFail = 0;
716 for (int index = firstFail; index < coinSetCount; index += 2) {
717 coinOneOff(reporter, index);
718 }
719}
720
721DEF_TEST(PathOpsCubicCoinOneOff, reporter) {
722 coinOneOff(reporter, 0);
723}
724
725DEF_TEST(PathOpsCubicIntersectionOneOff, reporter) {
726 newOneOff(reporter, 0, 1);
727}
728
729DEF_TEST(PathOpsCubicIntersectionTestsOneOff, reporter) {
730 testsOneOff(reporter, 10);
731}
732
733DEF_TEST(PathOpsCubicSelfOneOff, reporter) {
734 selfOneOff(reporter, 0);
735}
736
737DEF_TEST(PathOpsCubicIntersection, reporter) {
738 oneOffTests(reporter);
739 cubicIntersectionSelfTest(reporter);
740 cubicIntersectionCoinTest(reporter);
741 standardTestCases(reporter);
742 if ((false)) CubicIntersection_IntersectionFinder();
743 if ((false)) CubicIntersection_RandTest(reporter);
744}
tests
static BlurTest tests[]
Definition: BlurTest.cpp:84
test
#define test(name)
reporter
reporter
Definition: FontMgrTest.cpp:39
coinOneOff
static void coinOneOff(skiatest::Reporter *reporter, int index)
Definition: PathOpsCubicIntersectionTest.cpp:708
kFirstCubicIntersectionTest
static constexpr int kFirstCubicIntersectionTest
Definition: PathOpsCubicIntersectionTest.cpp:28
coinSet
static const CubicPts coinSet[]
Definition: PathOpsCubicIntersectionTest.cpp:687
standardTestCases
static void standardTestCases(skiatest::Reporter *reporter)
Definition: PathOpsCubicIntersectionTest.cpp:30
newOneOff
static void newOneOff(skiatest::Reporter *reporter, int outer, int inner)
Definition: PathOpsCubicIntersectionTest.cpp:452
CubicIntersection_IntersectionFinder
static void CubicIntersection_IntersectionFinder()
Definition: PathOpsCubicIntersectionTest.cpp:628
newTestSet
static const CubicPts newTestSet[]
Definition: PathOpsCubicIntersectionTest.cpp:181
selfSet
static const CubicPts selfSet[]
Definition: PathOpsCubicIntersectionTest.cpp:638
newTestSetCount
const int newTestSetCount
Definition: PathOpsCubicIntersectionTest.cpp:398
intersectionFinder
static void intersectionFinder(int index0, int index1, double t1Seed, double t2Seed, double t1Step, double t2Step)
Definition: PathOpsCubicIntersectionTest.cpp:535
oneOff
static void oneOff(skiatest::Reporter *reporter, const CubicPts &cubic1, const CubicPts &cubic2, bool coin)
Definition: PathOpsCubicIntersectionTest.cpp:399
testsOneOff
static void testsOneOff(skiatest::Reporter *reporter, int index)
Definition: PathOpsCubicIntersectionTest.cpp:458
oneOffTests
static void oneOffTests(skiatest::Reporter *reporter)
Definition: PathOpsCubicIntersectionTest.cpp:464
coinSetCount
static int coinSetCount
Definition: PathOpsCubicIntersectionTest.cpp:706
cubicIntersectionCoinTest
static void cubicIntersectionCoinTest(skiatest::Reporter *reporter)
Definition: PathOpsCubicIntersectionTest.cpp:714
cubicIntersectionSelfTest
static void cubicIntersectionSelfTest(skiatest::Reporter *reporter)
Definition: PathOpsCubicIntersectionTest.cpp:680
testSetCount
const int testSetCount
Definition: PathOpsCubicIntersectionTest.cpp:179
testSet
static const CubicPts testSet[]
Definition: PathOpsCubicIntersectionTest.cpp:83
DEF_TEST
DEF_TEST(PathOpsCubicCoinOneOff, reporter)
Definition: PathOpsCubicIntersectionTest.cpp:721
CubicIntersection_RandTest
static void CubicIntersection_RandTest(skiatest::Reporter *reporter)
Definition: PathOpsCubicIntersectionTest.cpp:479
selfOneOff
static void selfOneOff(skiatest::Reporter *reporter, int setIdx)
Definition: PathOpsCubicIntersectionTest.cpp:651
gDumpTSectNum
int gDumpTSectNum
ValidCubic
bool ValidCubic(const SkDCubic &cubic)
Definition: PathOpsTestCommon.cpp:286
SkASSERT
#define SkASSERT(cond)
Definition: SkAssert.h:116
approximately_zero
static bool approximately_zero(double x)
Definition: SkCubics.cpp:153
SkDebugf
void SK_SPI SkDebugf(const char format[],...) SK_PRINTF_LIKE(1
SkChopCubicAt
void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t)
Definition: SkGeometry.cpp:473
SkClassifyCubic
SkCubicType SkClassifyCubic(const SkPoint P[4], double t[2], double s[2], double d[4])
Definition: SkGeometry.cpp:809
SkCubicType
SkCubicType
Definition: SkGeometry.h:264
SK_RAND
#define SK_RAND(seed)
Definition: SkPathOpsDebug.h:48
REPORTER_ASSERT
#define REPORTER_ASSERT(r, cond,...)
Definition: Test.h:286
SkIntersections::intersect
int intersect(const SkDLine &, const SkDLine &)
Definition: SkDLineIntersection.cpp:87
SkIntersections::pt
const SkDPoint & pt(int index) const
Definition: SkIntersections.h:173
SkIntersections::used
int used() const
Definition: SkIntersections.h:228
SkIntersections::isCoincident
bool isCoincident(int index)
Definition: SkIntersections.h:141
SkScalar
float SkScalar
Definition: extension.cpp:12
i
int i
Definition: fl_socket_accessible.cc:18
result
GAsyncResult * result
Definition: fl_text_input_plugin.cc:106
flutter::size
it will be possible to load the file into Perfetto s trace viewer disable asset Prevents usage of any non test fonts unless they were explicitly Loaded via prefetched default font Indicates whether the embedding started a prefetch of the default font manager before creating the engine run In non interactive keep the shell running after the Dart script has completed enable serial On low power devices with low core running concurrent GC tasks on threads can cause them to contend with the UI thread which could potentially lead to jank This option turns off all concurrent GC activities domain network JSON encoded network policy per domain This overrides the DisallowInsecureConnections switch Embedder can specify whether to allow or disallow insecure connections at a domain level old gen heap size
Definition: switches.h:259
skgpu::wangs_formula::cubic
AI float cubic(float precision, const SkPoint pts[], const VectorXform &vectorXform=VectorXform())
Definition: WangsFormula.h:195
CubicPts::fPts
SkDPoint fPts[kPointCount]
Definition: PathOpsTestCommon.h:34
SkDCubic::debugSet
void debugSet(const SkDPoint *pts)
Definition: SkPathOpsDebug.cpp:712
SkDCubic::set
const SkDCubic & set(const SkPoint pts[kPointCount] SkDEBUGPARAMS(SkOpGlobalState *state=nullptr))
Definition: SkPathOpsCubic.h:122
SkDCubic::ptAtT
SkDPoint ptAtT(double t) const
Definition: SkPathOpsCubic.cpp:591
SkDCubic::ComplexBreak
static int ComplexBreak(const SkPoint pts[4], SkScalar *t)
Definition: SkPathOpsCubic.cpp:254
SkDPoint::approximatelyEqual
bool approximatelyEqual(const SkDPoint &a) const
Definition: SkPathOpsPoint.h:177
SkDPoint::distance
double distance(const SkDPoint &a) const
Definition: SkPathOpsPoint.h:224
SkDRect::fTop
double fTop
Definition: SkPathOpsRect.h:22
SkDRect::fRight
double fRight
Definition: SkPathOpsRect.h:22
SkDRect::fBottom
double fBottom
Definition: SkPathOpsRect.h:22
SkDRect::setBounds
void setBounds(const SkDConic &curve)
Definition: SkPathOpsRect.h:59
SkDRect::fLeft
double fLeft
Definition: SkPathOpsRect.h:22
SkReduceOrder::reduce
int reduce(const SkDCubic &cubic, Quadratics)
Definition: SkReduceOrder.cpp:195
Generated on Sun Jun 23 2024 21:56:42 for Flutter Engine by doxygen 1.9.4