blob: 1cc037f1c4ff665ed4da106aaa58fef80ad447a5 [file] [log] [blame]
caryclark@google.com9166dcb2013-04-08 11:50:00 +00001/*
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 "PathOpsCubicIntersectionTestData.h"
8#include "PathOpsTestCommon.h"
9#include "SkIntersections.h"
10#include "SkPathOpsRect.h"
11#include "SkReduceOrder.h"
12#include "Test.h"
13
14const int firstCubicIntersectionTest = 9;
15
16static void standardTestCases(skiatest::Reporter* reporter) {
17 for (size_t index = firstCubicIntersectionTest; index < tests_count; ++index) {
18 int iIndex = static_cast<int>(index);
19 const SkDCubic& cubic1 = tests[index][0];
20 const SkDCubic& cubic2 = tests[index][1];
21 SkReduceOrder reduce1, reduce2;
22 int order1 = reduce1.reduce(cubic1, SkReduceOrder::kNo_Quadratics,
23 SkReduceOrder::kFill_Style);
24 int order2 = reduce2.reduce(cubic2, SkReduceOrder::kNo_Quadratics,
25 SkReduceOrder::kFill_Style);
26 const bool showSkipped = false;
27 if (order1 < 4) {
28 if (showSkipped) {
29 SkDebugf("%s [%d] cubic1 order=%d\n", __FUNCTION__, iIndex, order1);
30 }
31 continue;
32 }
33 if (order2 < 4) {
34 if (showSkipped) {
35 SkDebugf("%s [%d] cubic2 order=%d\n", __FUNCTION__, iIndex, order2);
36 }
37 continue;
38 }
39 SkIntersections tIntersections;
40 tIntersections.intersect(cubic1, cubic2);
41 if (!tIntersections.used()) {
42 if (showSkipped) {
43 SkDebugf("%s [%d] no intersection\n", __FUNCTION__, iIndex);
44 }
45 continue;
46 }
47 if (tIntersections.isCoincident(0)) {
48 if (showSkipped) {
49 SkDebugf("%s [%d] coincident\n", __FUNCTION__, iIndex);
50 }
51 continue;
52 }
53 for (int pt = 0; pt < tIntersections.used(); ++pt) {
54 double tt1 = tIntersections[0][pt];
caryclark@google.com4fdbb222013-07-23 15:27:41 +000055 SkDPoint xy1 = cubic1.ptAtT(tt1);
caryclark@google.com9166dcb2013-04-08 11:50:00 +000056 double tt2 = tIntersections[1][pt];
caryclark@google.com4fdbb222013-07-23 15:27:41 +000057 SkDPoint xy2 = cubic2.ptAtT(tt2);
caryclark@google.com9166dcb2013-04-08 11:50:00 +000058 if (!xy1.approximatelyEqual(xy2)) {
59 SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n",
60 __FUNCTION__, (int)index, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY);
61 }
62 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
63 }
64 }
65}
66
67static const SkDCubic testSet[] = {
68// FIXME: uncommenting these two will cause this to fail
69// this results in two curves very nearly but not exactly coincident
70#if 0
71{{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306},
72 {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}},
73{{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826},
74 {75.3863417, 18.24489}}},
75#endif
76
77{{{0, 0}, {0, 1}, {1, 1}, {1, 0}}},
78{{{1, 0}, {0, 0}, {0, 1}, {1, 1}}},
79
80{{{0, 1}, {4, 5}, {1, 0}, {5, 3}}},
81{{{0, 1}, {3, 5}, {1, 0}, {5, 4}}},
82
83{{{0, 1}, {1, 6}, {1, 0}, {1, 0}}},
84{{{0, 1}, {0, 1}, {1, 0}, {6, 1}}},
85
86{{{0, 1}, {3, 4}, {1, 0}, {5, 1}}},
87{{{0, 1}, {1, 5}, {1, 0}, {4, 3}}},
88
89{{{0, 1}, {1, 2}, {1, 0}, {6, 1}}},
90{{{0, 1}, {1, 6}, {1, 0}, {2, 1}}},
91
92{{{0, 1}, {0, 5}, {1, 0}, {4, 0}}},
93{{{0, 1}, {0, 4}, {1, 0}, {5, 0}}},
94
95{{{0, 1}, {3, 4}, {1, 0}, {3, 0}}},
96{{{0, 1}, {0, 3}, {1, 0}, {4, 3}}},
97
98{{{0, 0}, {1, 2}, {3, 4}, {4, 4}}},
99{{{0, 0}, {1, 2}, {3, 4}, {4, 4}}},
100{{{4, 4}, {3, 4}, {1, 2}, {0, 0}}},
101
102{{{0, 1}, {2, 3}, {1, 0}, {1, 0}}},
103{{{0, 1}, {0, 1}, {1, 0}, {3, 2}}},
104
105{{{0, 2}, {0, 1}, {1, 0}, {1, 0}}},
106{{{0, 1}, {0, 1}, {2, 0}, {1, 0}}},
107
108{{{0, 1}, {0, 2}, {1, 0}, {1, 0}}},
109{{{0, 1}, {0, 1}, {1, 0}, {2, 0}}},
110
111{{{0, 1}, {1, 6}, {1, 0}, {2, 0}}},
112{{{0, 1}, {0, 2}, {1, 0}, {6, 1}}},
113
114{{{0, 1}, {5, 6}, {1, 0}, {1, 0}}},
115{{{0, 1}, {0, 1}, {1, 0}, {6, 5}}},
116
117{{{95.837747722788592, 45.025976907939643}, {16.564570095652982, 0.72959763963222402},
118 {63.209855865319199, 68.047528419665767}, {57.640240647662544, 59.524565264361243}}},
119{{{51.593891741518817, 38.53849970667553}, {62.34752929878772, 74.924924725166022},
120 {74.810149322641152, 34.17966562983564}, {29.368398119401373, 94.66719277886078}}},
121
122{{{39.765160968417838, 33.060396198677083}, {5.1922921581157908, 66.854301452103215},
123 {31.619281802149157, 25.269248720849514}, {81.541621071073038, 70.025341524754353}}},
124{{{46.078911165743556, 48.259962651999651}, {20.24450549867214, 49.403916182650214},
125 {0.26325131778756683, 24.46489805563581}, {15.915006546264051, 83.515023059917155}}},
126
127{{{65.454505973241524, 93.881892270353575}, {45.867360264932437, 92.723972719499827},
128 {2.1464054482739447, 74.636369140183717}, {33.774068594804994, 40.770872887582925}}},
129{{{72.963387832494163, 95.659300729473728}, {11.809496633619768, 82.209921247423594},
130 {13.456139067865974, 57.329313623406605}, {36.060621606214262, 70.867335643091849}}},
131
132{{{32.484981432782945, 75.082940782924624}, {42.467313093350882, 48.131159948246157},
133 {3.5963115764764657, 43.208665839959245}, {79.442476890721579, 89.709102357602262}}},
134{{{18.98573861410177, 93.308887208490106}, {40.405250173250792, 91.039661826118675},
135 {8.0467721950480584, 42.100282172719147}, {40.883324221187891, 26.030185504830527}}},
136
137{{{7.5374809128872498, 82.441702896003477}, {22.444346930107265, 22.138854312775123},
138 {66.76091829629658, 50.753805856571446}, {78.193478508942519, 97.7932997968948}}},
139{{{97.700573130371311, 53.53260215070685}, {87.72443481149358, 84.575876772671876},
140 {19.215031396232092, 47.032676472809484}, {11.989686410869325, 10.659507480757082}}},
141
142{{{26.192053931854691, 9.8504326817814416}, {10.174241480498686, 98.476562741434464},
143 {21.177712558385782, 33.814968789841501}, {75.329030899018534, 55.02231980442177}}},
144{{{56.222082700683771, 24.54395039218662}, {95.589995289030483, 81.050822735322086},
145 {28.180450866082897, 28.837706255185282}, {60.128952916771617, 87.311672180570511}}},
146
147{{{42.449716172390481, 52.379709366885805}, {27.896043159019225, 48.797373636065686},
148 {92.770268299044233, 89.899302036454571}, {12.102066544863426, 99.43241951960718}}},
149{{{45.77532924980639, 45.958701495993274}, {37.458701356062065, 68.393691335056758},
150 {37.569326692060258, 27.673713456687381}, {60.674866037757539, 62.47349659096146}}},
151
152{{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306},
153 {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}},
154{{{61.336508189019057, 82.693132843213675}, {44.639380902349664, 54.074825790745592},
155 {16.815615499771951, 20.049704667203923}, {41.866884958868326, 56.735503699973002}}},
156
157{{{18.1312339, 31.6473732}, {95.5711034, 63.5350219}, {92.3283165, 62.0158945},
158 {18.5656052, 32.1268808}}},
159{{{97.402018, 35.7169972}, {33.1127443, 25.8935163}, {1.13970027, 54.9424981},
160 {56.4860195, 60.529264}}},
161};
162
caryclark@google.comad65a3e2013-04-15 19:13:59 +0000163const size_t testSetCount = SK_ARRAY_COUNT(testSet);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000164
165static const SkDCubic newTestSet[] = {
skia.committer@gmail.com7f1af502013-07-24 07:01:12 +0000166{{{3, 4}, {1, 5}, {4, 3}, {6, 4}}},
167{{{3, 4}, {4, 6}, {4, 3}, {5, 1}}},
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000168
skia.committer@gmail.com7f1af502013-07-24 07:01:12 +0000169{{{130.04275512695312, 11417.413085937500 },
170 {130.23312377929687, 11418.319335937500 },
171 {131.03707885742187, 11419.000000000000 },
172 {132.00000000000000, 11419.000000000000 }}},
173
174{{{132.00000000000000, 11419.000000000000 },
175 {130.89543151855469, 11419.000000000000 },
176 {130.00000000000000, 11418.104492187500 },
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000177 {130.00000000000000, 11417.000000000000 }}},
178
robertphillips@google.com8dcea7d2013-07-15 15:38:55 +0000179{{{1.0516976506771041, 2.9684399028541346 },
180 {1.0604363140895228, 2.9633503074444141 },
181 {1.0692548215065762, 2.9580354426587459 },
182 {1.0781560339512140, 2.9525043684031349 }}},
caryclark@google.comfa2aeee2013-07-15 13:29:13 +0000183
robertphillips@google.com8dcea7d2013-07-15 15:38:55 +0000184{{{1.0523038101345104, 2.9523755204833737 },
185 {1.0607035288264237, 2.9580853881628375 },
186 {1.0690530472271964, 2.9633896794787749 },
187 {1.0773566568712512, 2.9682969775000219 }}},
caryclark@google.comfa2aeee2013-07-15 13:29:13 +0000188
robertphillips@google.com8dcea7d2013-07-15 15:38:55 +0000189{{{1.0386522625066592, 2.9759024812329078 },
190 {1.0559713690392631, 2.9661782500838885 },
191 {1.0736041309019990, 2.9555348259177858 },
192 {1.0915734362784633, 2.9440446879826569 }}},
caryclark@google.comfa2aeee2013-07-15 13:29:13 +0000193
robertphillips@google.com8dcea7d2013-07-15 15:38:55 +0000194{{{1.0396670794879301, 2.9435062123457261 },
195 {1.0565690546812769, 2.9557413250983462 },
196 {1.0732616463413533, 2.9663369676594282 },
197 {1.0897791867435489, 2.9753618045797472 }}},
198
199{{{0.8685656183311091, 3.0409266475785208 },
200 {0.99189542936395292, 3.0212163698184424 },
201 {1.1302108367493320, 2.9265646471747306 },
202 {1.2952305904872474, 2.7940808546473788 }}},
203
204{{{0.85437872843682727, 2.7536036928549055 },
205 {1.0045584590592620, 2.9493041024831705 },
206 {1.1336998329885613, 3.0248027987251747 },
207 {1.2593809752247314, 3.0152560315809107 }}},
208
209{{{0, 1}, {1, 6}, {1, 0}, {6, 2}}},
210{{{0, 1}, {2, 6}, {1, 0}, {6, 1}}},
caryclark@google.comfa2aeee2013-07-15 13:29:13 +0000211
caryclark@google.comcffbcc32013-06-04 17:59:42 +0000212{{{134,11414}, {131.990234375,11414}, {130.32666015625,11415.482421875}, {130.04275512695312,11417.4130859375}}},
213{{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}},
214
215{{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}},
216{{{130.04275512695312,11417.4130859375}, {130.23312377929687,11418.3193359375}, {131.03707885742187,11419}, {132,11419}}},
217
caryclark@google.coma5e55922013-05-07 18:51:31 +0000218{{{0, 1}, {2, 3}, {5, 1}, {4, 3}}},
219{{{1, 5}, {3, 4}, {1, 0}, {3, 2}}},
220
caryclark@google.comb3f09212013-04-17 15:49:16 +0000221{{{3, 5}, {1, 6}, {5, 0}, {3, 1}}},
222{{{0, 5}, {1, 3}, {5, 3}, {6, 1}}},
223
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000224{{{0, 1}, {1, 5}, {1, 0}, {1, 0}}},
225{{{0, 1}, {0, 1}, {1, 0}, {5, 1}}},
226
227{{{1, 3}, {5, 6}, {5, 3}, {5, 4}}},
228{{{3, 5}, {4, 5}, {3, 1}, {6, 5}}},
229
230{{{0, 5}, {0, 5}, {5, 4}, {6, 4}}},
231{{{4, 5}, {4, 6}, {5, 0}, {5, 0}}},
232
233{{{0, 4}, {1, 3}, {5, 4}, {4, 2}}},
234{{{4, 5}, {2, 4}, {4, 0}, {3, 1}}},
235
236{{{0, 2}, {1, 5}, {3, 2}, {4, 1}}},
237{{{2, 3}, {1, 4}, {2, 0}, {5, 1}}},
238
239{{{0, 2}, {2, 3}, {5, 1}, {3, 2}}},
240{{{1, 5}, {2, 3}, {2, 0}, {3, 2}}},
241
242{{{2, 6}, {4, 5}, {1, 0}, {6, 1}}},
243{{{0, 1}, {1, 6}, {6, 2}, {5, 4}}},
244
245{{{0, 1}, {1, 2}, {6, 5}, {5, 4}}},
246{{{5, 6}, {4, 5}, {1, 0}, {2, 1}}},
247
248{{{2.5119999999999996, 1.5710000000000002}, {2.6399999999999983, 1.6599999999999997},
249 {2.8000000000000007, 1.8000000000000003}, {3, 2}}},
250{{{2.4181876227114887, 1.9849772580462195}, {2.8269904869227211, 2.009330650246834},
251 {3.2004679292461624, 1.9942047174679169}, {3.4986199496818058, 2.0035994597094731}}},
252
253{{{2, 3}, {1, 4}, {1, 0}, {6, 0}}},
254{{{0, 1}, {0, 6}, {3, 2}, {4, 1}}},
255
256{{{0, 2}, {1, 5}, {1, 0}, {6, 1}}},
257{{{0, 1}, {1, 6}, {2, 0}, {5, 1}}},
258
259{{{0, 1}, {1, 5}, {2, 1}, {4, 0}}},
260{{{1, 2}, {0, 4}, {1, 0}, {5, 1}}},
261
262{{{0, 1}, {3, 5}, {2, 1}, {3, 1}}},
263{{{1, 2}, {1, 3}, {1, 0}, {5, 3}}},
264
265{{{0, 1}, {2, 5}, {6, 0}, {5, 3}}},
266{{{0, 6}, {3, 5}, {1, 0}, {5, 2}}},
267
268{{{0, 1}, {3, 6}, {1, 0}, {5, 2}}},
269{{{0, 1}, {2, 5}, {1, 0}, {6, 3}}},
270
271{{{1, 2}, {5, 6}, {1, 0}, {1, 0}}},
272{{{0, 1}, {0, 1}, {2, 1}, {6, 5}}},
273
274{{{0, 6}, {1, 2}, {1, 0}, {1, 0}}},
275{{{0, 1}, {0, 1}, {6, 0}, {2, 1}}},
276
277{{{0, 2}, {0, 1}, {3, 0}, {1, 0}}},
278{{{0, 3}, {0, 1}, {2, 0}, {1, 0}}},
279};
280
caryclark@google.comad65a3e2013-04-15 19:13:59 +0000281const size_t newTestSetCount = SK_ARRAY_COUNT(newTestSet);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000282
283static void oneOff(skiatest::Reporter* reporter, const SkDCubic& cubic1, const SkDCubic& cubic2) {
caryclark@google.com8d0a5242013-07-16 16:11:16 +0000284 SkASSERT(ValidCubic(cubic1));
285 SkASSERT(ValidCubic(cubic2));
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000286#if ONE_OFF_DEBUG
287 SkDebugf("computed quadratics given\n");
caryclark@google.comcffbcc32013-06-04 17:59:42 +0000288 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000289 cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY,
290 cubic1[2].fX, cubic1[2].fY, cubic1[3].fX, cubic1[3].fY);
caryclark@google.comcffbcc32013-06-04 17:59:42 +0000291 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000292 cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY,
293 cubic2[2].fX, cubic2[2].fY, cubic2[3].fX, cubic2[3].fY);
294#endif
caryclark@google.comd892bd82013-06-17 14:10:36 +0000295 SkTArray<SkDQuad, true> quads1;
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000296 CubicToQuads(cubic1, cubic1.calcPrecision(), quads1);
297#if ONE_OFF_DEBUG
298 SkDebugf("computed quadratics set 1\n");
299 for (int index = 0; index < quads1.count(); ++index) {
300 const SkDQuad& q = quads1[index];
caryclark@google.comcffbcc32013-06-04 17:59:42 +0000301 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].fX, q[0].fY,
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000302 q[1].fX, q[1].fY, q[2].fX, q[2].fY);
303 }
304#endif
caryclark@google.comd892bd82013-06-17 14:10:36 +0000305 SkTArray<SkDQuad, true> quads2;
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000306 CubicToQuads(cubic2, cubic2.calcPrecision(), quads2);
307#if ONE_OFF_DEBUG
308 SkDebugf("computed quadratics set 2\n");
309 for (int index = 0; index < quads2.count(); ++index) {
310 const SkDQuad& q = quads2[index];
caryclark@google.comcffbcc32013-06-04 17:59:42 +0000311 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].fX, q[0].fY,
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000312 q[1].fX, q[1].fY, q[2].fX, q[2].fY);
313 }
314#endif
315 SkIntersections intersections;
316 intersections.intersect(cubic1, cubic2);
317 double tt1, tt2;
318 SkDPoint xy1, xy2;
319 for (int pt3 = 0; pt3 < intersections.used(); ++pt3) {
320 tt1 = intersections[0][pt3];
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000321 xy1 = cubic1.ptAtT(tt1);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000322 tt2 = intersections[1][pt3];
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000323 xy2 = cubic2.ptAtT(tt2);
caryclark@google.com5ec2b1e2013-07-15 20:50:24 +0000324 const SkDPoint& iPt = intersections.pt(pt3);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000325#if ONE_OFF_DEBUG
326 SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n",
caryclark@google.comcffbcc32013-06-04 17:59:42 +0000327 __FUNCTION__, tt1, xy1.fX, xy1.fY, iPt.fX,
328 iPt.fY, xy2.fX, xy2.fY, tt2);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000329#endif
caryclark@google.comcffbcc32013-06-04 17:59:42 +0000330 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(iPt));
331 REPORTER_ASSERT(reporter, xy2.approximatelyEqual(iPt));
332 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000333 }
334}
335
336static void oneOff(skiatest::Reporter* reporter, int outer, int inner) {
337 const SkDCubic& cubic1 = testSet[outer];
338 const SkDCubic& cubic2 = testSet[inner];
339 oneOff(reporter, cubic1, cubic2);
340}
341
342static void newOneOff(skiatest::Reporter* reporter, int outer, int inner) {
343 const SkDCubic& cubic1 = newTestSet[outer];
344 const SkDCubic& cubic2 = newTestSet[inner];
345 oneOff(reporter, cubic1, cubic2);
346}
347
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000348static void oneOffTests(skiatest::Reporter* reporter) {
349 for (size_t outer = 0; outer < testSetCount - 1; ++outer) {
350 for (size_t inner = outer + 1; inner < testSetCount; ++inner) {
351 oneOff(reporter, outer, inner);
352 }
353 }
354 for (size_t outer = 0; outer < newTestSetCount - 1; ++outer) {
355 for (size_t inner = outer + 1; inner < newTestSetCount; ++inner) {
caryclark@google.com5ec2b1e2013-07-15 20:50:24 +0000356 newOneOff(reporter, outer, inner);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000357 }
358 }
359}
360
361#define DEBUG_CRASH 0
362
363static void CubicIntersection_RandTest(skiatest::Reporter* reporter) {
364 srand(0);
365 const int tests = 10000000;
caryclark@google.comdb60de72013-04-11 12:33:23 +0000366#if !defined(SK_BUILD_FOR_WIN) && !defined(SK_BUILD_FOR_ANDROID)
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000367 unsigned seed = 0;
368#endif
369 for (int test = 0; test < tests; ++test) {
370 SkDCubic cubic1, cubic2;
371 for (int i = 0; i < 4; ++i) {
372 cubic1[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
373 cubic1[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
374 cubic2[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
375 cubic2[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
376 }
377 #if DEBUG_CRASH
378 char str[1024];
379 snprintf(str, sizeof(str),
380 "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n"
381 "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n",
382 cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY, cubic1[2].fX, cubic1[2].fY,
383 cubic1[3].fX, cubic1[3].fY,
384 cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY, cubic2[2].fX, cubic2[2].fY,
385 cubic2[3].fX, cubic2[3].fY);
386 #endif
387 SkDRect rect1, rect2;
388 rect1.setBounds(cubic1);
389 rect2.setBounds(cubic2);
390 bool boundsIntersect = rect1.fLeft <= rect2.fRight && rect2.fLeft <= rect2.fRight
391 && rect1.fTop <= rect2.fBottom && rect2.fTop <= rect1.fBottom;
392 if (test == -1) {
393 SkDebugf("ready...\n");
394 }
395 SkIntersections intersections2;
396 int newIntersects = intersections2.intersect(cubic1, cubic2);
397 if (!boundsIntersect && newIntersects) {
398 #if DEBUG_CRASH
399 SkDebugf("%s %d unexpected intersection boundsIntersect=%d "
400 " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsIntersect,
401 newIntersects, __FUNCTION__, str);
402 #endif
403 REPORTER_ASSERT(reporter, 0);
404 }
405 for (int pt = 0; pt < intersections2.used(); ++pt) {
406 double tt1 = intersections2[0][pt];
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000407 SkDPoint xy1 = cubic1.ptAtT(tt1);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000408 double tt2 = intersections2[1][pt];
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000409 SkDPoint xy2 = cubic2.ptAtT(tt2);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000410 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
411 }
412 }
413}
414
415static void intersectionFinder(int index0, int index1, double t1Seed, double t2Seed,
416 double t1Step, double t2Step) {
417 const SkDCubic& cubic1 = newTestSet[index0];
418 const SkDCubic& cubic2 = newTestSet[index1];
419 SkDPoint t1[3], t2[3];
420 bool toggle = true;
421 do {
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000422 t1[0] = cubic1.ptAtT(t1Seed - t1Step);
423 t1[1] = cubic1.ptAtT(t1Seed);
424 t1[2] = cubic1.ptAtT(t1Seed + t1Step);
425 t2[0] = cubic2.ptAtT(t2Seed - t2Step);
426 t2[1] = cubic2.ptAtT(t2Seed);
427 t2[2] = cubic2.ptAtT(t2Seed + t2Step);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000428 double dist[3][3];
429 dist[1][1] = t1[1].distance(t2[1]);
430 int best_i = 1, best_j = 1;
431 for (int i = 0; i < 3; ++i) {
432 for (int j = 0; j < 3; ++j) {
433 if (i == 1 && j == 1) {
434 continue;
435 }
436 dist[i][j] = t1[i].distance(t2[j]);
437 if (dist[best_i][best_j] > dist[i][j]) {
438 best_i = i;
439 best_j = j;
440 }
441 }
442 }
443 if (best_i == 0) {
444 t1Seed -= t1Step;
445 } else if (best_i == 2) {
446 t1Seed += t1Step;
447 }
448 if (best_j == 0) {
449 t2Seed -= t2Step;
450 } else if (best_j == 2) {
451 t2Seed += t2Step;
452 }
453 if (best_i == 1 && best_j == 1) {
454 if ((toggle ^= true)) {
455 t1Step /= 2;
456 } else {
457 t2Step /= 2;
458 }
459 }
460 } while (!t1[1].approximatelyEqual(t2[1]));
461 t1Step = t2Step = 0.1;
462 double t10 = t1Seed - t1Step * 2;
463 double t12 = t1Seed + t1Step * 2;
464 double t20 = t2Seed - t2Step * 2;
465 double t22 = t2Seed + t2Step * 2;
466 SkDPoint test;
467 while (!approximately_zero(t1Step)) {
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000468 test = cubic1.ptAtT(t10);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000469 t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step;
470 t1Step /= 2;
471 }
472 t1Step = 0.1;
473 while (!approximately_zero(t1Step)) {
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000474 test = cubic1.ptAtT(t12);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000475 t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step;
476 t1Step /= 2;
477 }
478 while (!approximately_zero(t2Step)) {
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000479 test = cubic2.ptAtT(t20);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000480 t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step;
481 t2Step /= 2;
482 }
483 t2Step = 0.1;
484 while (!approximately_zero(t2Step)) {
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000485 test = cubic2.ptAtT(t22);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000486 t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step;
487 t2Step /= 2;
488 }
489#if ONE_OFF_DEBUG
490 SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__,
491 t10, t1Seed, t12, t20, t2Seed, t22);
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000492 SkDPoint p10 = cubic1.ptAtT(t10);
493 SkDPoint p1Seed = cubic1.ptAtT(t1Seed);
494 SkDPoint p12 = cubic1.ptAtT(t12);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000495 SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
496 p10.fX, p10.fY, p1Seed.fX, p1Seed.fY, p12.fX, p12.fY);
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000497 SkDPoint p20 = cubic2.ptAtT(t20);
498 SkDPoint p2Seed = cubic2.ptAtT(t2Seed);
499 SkDPoint p22 = cubic2.ptAtT(t22);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000500 SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
501 p20.fX, p20.fY, p2Seed.fX, p2Seed.fY, p22.fX, p22.fY);
502#endif
503}
504
505static void CubicIntersection_IntersectionFinder() {
506// double t1Seed = 0.87;
507// double t2Seed = 0.87;
508 double t1Step = 0.000001;
509 double t2Step = 0.000001;
510 intersectionFinder(0, 1, 0.855895664, 0.864850875, t1Step, t2Step);
511 intersectionFinder(0, 1, 0.865207906, 0.865207887, t1Step, t2Step);
512 intersectionFinder(0, 1, 0.865213351, 0.865208087, t1Step, t2Step);
513}
514
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000515static const SkDCubic selfSet[] = {
516 {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}},
517 {{{3, 6}, {2, 3}, {4, 0}, {3, 2}}},
518 {{{0, 2}, {2, 3}, {5, 1}, {3, 2}}},
519 {{{0, 2}, {3, 5}, {5, 0}, {4, 2}}},
520 {{{3.34, 8.98}, {1.95, 10.27}, {3.76, 7.65}, {4.96, 10.64}}},
521 {{{3.13, 2.74}, {1.08, 4.62}, {3.71, 0.94}, {2.01, 3.81}}},
522 {{{6.71, 3.14}, {7.99, 2.75}, {8.27, 1.96}, {6.35, 3.57}}},
523 {{{12.81, 7.27}, {7.22, 6.98}, {12.49, 8.97}, {11.42, 6.18}}},
524};
525size_t selfSetCount = SK_ARRAY_COUNT(selfSet);
526
527static void selfOneOff(skiatest::Reporter* reporter, int index) {
528 const SkDCubic& cubic = selfSet[index];
529#if ONE_OFF_DEBUG
530 int idx2;
531 double max[3];
532 int ts = cubic.findMaxCurvature(max);
533 for (idx2 = 0; idx2 < ts; ++idx2) {
534 SkDebugf("%s max[%d]=%1.9g (%1.9g, %1.9g)\n", __FUNCTION__, idx2,
535 max[idx2], cubic.ptAtT(max[idx2]).fX, cubic.ptAtT(max[idx2]).fY);
536 }
537 SkTArray<double, true> ts1;
538 SkTArray<SkDQuad, true> quads1;
539 cubic.toQuadraticTs(cubic.calcPrecision(), &ts1);
540 for (idx2 = 0; idx2 < ts1.count(); ++idx2) {
541 SkDebugf("%s t[%d]=%1.9g\n", __FUNCTION__, idx2, ts1[idx2]);
542 }
543 CubicToQuads(cubic, cubic.calcPrecision(), quads1);
544 for (idx2 = 0; idx2 < quads1.count(); ++idx2) {
545 const SkDQuad& q = quads1[idx2];
546 SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n",
547 q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY);
548 }
549 SkDebugf("\n");
550#endif
551 SkIntersections i;
552 int result = i.intersect(cubic);
553 REPORTER_ASSERT(reporter, result == 1);
554 REPORTER_ASSERT(reporter, i.used() == 1);
555 REPORTER_ASSERT(reporter, !approximately_equal(i[0][0], i[1][0]));
556 SkDPoint pt1 = cubic.ptAtT(i[0][0]);
557 SkDPoint pt2 = cubic.ptAtT(i[1][0]);
558 REPORTER_ASSERT(reporter, pt1.approximatelyEqual(pt2));
559}
560
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000561static void cubicIntersectionSelfTest(skiatest::Reporter* reporter) {
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000562 size_t firstFail = 0;
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000563 for (size_t index = firstFail; index < selfSetCount; ++index) {
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000564 selfOneOff(reporter, index);
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000565 }
566}
567
caryclark@google.comfa2aeee2013-07-15 13:29:13 +0000568static void PathOpsCubicIntersectionOneOffTest(skiatest::Reporter* reporter) {
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000569 newOneOff(reporter, 0, 1);
570}
571
572static void PathOpsCubicSelfOneOffTest(skiatest::Reporter* reporter) {
573 selfOneOff(reporter, 0);
caryclark@google.comfa2aeee2013-07-15 13:29:13 +0000574}
575
caryclark@google.comad65a3e2013-04-15 19:13:59 +0000576static void PathOpsCubicIntersectionTest(skiatest::Reporter* reporter) {
caryclark@google.com9166dcb2013-04-08 11:50:00 +0000577 oneOffTests(reporter);
578 cubicIntersectionSelfTest(reporter);
579 standardTestCases(reporter);
580 if (false) CubicIntersection_IntersectionFinder();
581 if (false) CubicIntersection_RandTest(reporter);
582}
583
584#include "TestClassDef.h"
caryclark@google.comad65a3e2013-04-15 19:13:59 +0000585DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionTest)
caryclark@google.comfa2aeee2013-07-15 13:29:13 +0000586
587DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionOneOffTest)
caryclark@google.com4fdbb222013-07-23 15:27:41 +0000588
589DEFINE_TESTCLASS_SHORT(PathOpsCubicSelfOneOffTest)