OLD | NEW |
(Empty) | |
| 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 "PathOpsCubicIntersectionTestData.h" |
| 8 #include "PathOpsTestCommon.h" |
| 9 #include "SkIntersections.h" |
| 10 #include "SkPathOpsRect.h" |
| 11 #include "SkReduceOrder.h" |
| 12 #include "Test.h" |
| 13 |
| 14 const int firstCubicIntersectionTest = 9; |
| 15 |
| 16 static 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, orde
r1); |
| 30 } |
| 31 continue; |
| 32 } |
| 33 if (order2 < 4) { |
| 34 if (showSkipped) { |
| 35 SkDebugf("%s [%d] cubic2 order=%d\n", __FUNCTION__, iIndex, orde
r2); |
| 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]; |
| 55 SkDPoint xy1 = cubic1.xyAtT(tt1); |
| 56 double tt2 = tIntersections[1][pt]; |
| 57 SkDPoint xy2 = cubic2.xyAtT(tt2); |
| 58 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 |
| 67 static 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.476863174921
306}, |
| 72 {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038
969412}}}, |
| 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.7295976396322
2402}, |
| 118 {63.209855865319199, 68.047528419665767}, {57.640240647662544, 59.524565
264361243}}}, |
| 119 {{{51.593891741518817, 38.53849970667553}, {62.34752929878772, 74.92492472516602
2}, |
| 120 {74.810149322641152, 34.17966562983564}, {29.368398119401373, 94.6671927
7886078}}}, |
| 121 |
| 122 {{{39.765160968417838, 33.060396198677083}, {5.1922921581157908, 66.854301452103
215}, |
| 123 {31.619281802149157, 25.269248720849514}, {81.541621071073038, 70.025341
524754353}}}, |
| 124 {{{46.078911165743556, 48.259962651999651}, {20.24450549867214, 49.4039161826502
14}, |
| 125 {0.26325131778756683, 24.46489805563581}, {15.915006546264051, 83.515023
059917155}}}, |
| 126 |
| 127 {{{65.454505973241524, 93.881892270353575}, {45.867360264932437, 92.723972719499
827}, |
| 128 {2.1464054482739447, 74.636369140183717}, {33.774068594804994, 40.770872
887582925}}}, |
| 129 {{{72.963387832494163, 95.659300729473728}, {11.809496633619768, 82.209921247423
594}, |
| 130 {13.456139067865974, 57.329313623406605}, {36.060621606214262, 70.867335
643091849}}}, |
| 131 |
| 132 {{{32.484981432782945, 75.082940782924624}, {42.467313093350882, 48.131159948246
157}, |
| 133 {3.5963115764764657, 43.208665839959245}, {79.442476890721579, 89.709102
357602262}}}, |
| 134 {{{18.98573861410177, 93.308887208490106}, {40.405250173250792, 91.0396618261186
75}, |
| 135 {8.0467721950480584, 42.100282172719147}, {40.883324221187891, 26.030185
504830527}}}, |
| 136 |
| 137 {{{7.5374809128872498, 82.441702896003477}, {22.444346930107265, 22.138854312775
123}, |
| 138 {66.76091829629658, 50.753805856571446}, {78.193478508942519, 97.7932997
968948}}}, |
| 139 {{{97.700573130371311, 53.53260215070685}, {87.72443481149358, 84.57587677267187
6}, |
| 140 {19.215031396232092, 47.032676472809484}, {11.989686410869325, 10.659507
480757082}}}, |
| 141 |
| 142 {{{26.192053931854691, 9.8504326817814416}, {10.174241480498686, 98.476562741434
464}, |
| 143 {21.177712558385782, 33.814968789841501}, {75.329030899018534, 55.022319
80442177}}}, |
| 144 {{{56.222082700683771, 24.54395039218662}, {95.589995289030483, 81.0508227353220
86}, |
| 145 {28.180450866082897, 28.837706255185282}, {60.128952916771617, 87.311672
180570511}}}, |
| 146 |
| 147 {{{42.449716172390481, 52.379709366885805}, {27.896043159019225, 48.797373636065
686}, |
| 148 {92.770268299044233, 89.899302036454571}, {12.102066544863426, 99.432419
51960718}}}, |
| 149 {{{45.77532924980639, 45.958701495993274}, {37.458701356062065, 68.3936913350567
58}, |
| 150 {37.569326692060258, 27.673713456687381}, {60.674866037757539, 62.473496
59096146}}}, |
| 151 |
| 152 {{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921
306}, |
| 153 {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.2448900
38969412}}}, |
| 154 {{{61.336508189019057, 82.693132843213675}, {44.639380902349664, 54.074825790745
592}, |
| 155 {16.815615499771951, 20.049704667203923}, {41.866884958868326, 56.735503
699973002}}}, |
| 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 |
| 163 const size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]); |
| 164 |
| 165 static const SkDCubic newTestSet[] = { |
| 166 {{{0, 1}, {1, 5}, {1, 0}, {1, 0}}}, |
| 167 {{{0, 1}, {0, 1}, {1, 0}, {5, 1}}}, |
| 168 |
| 169 {{{1, 3}, {5, 6}, {5, 3}, {5, 4}}}, |
| 170 {{{3, 5}, {4, 5}, {3, 1}, {6, 5}}}, |
| 171 |
| 172 {{{0, 5}, {0, 5}, {5, 4}, {6, 4}}}, |
| 173 {{{4, 5}, {4, 6}, {5, 0}, {5, 0}}}, |
| 174 |
| 175 {{{0, 4}, {1, 3}, {5, 4}, {4, 2}}}, |
| 176 {{{4, 5}, {2, 4}, {4, 0}, {3, 1}}}, |
| 177 |
| 178 {{{0, 2}, {1, 5}, {3, 2}, {4, 1}}}, |
| 179 {{{2, 3}, {1, 4}, {2, 0}, {5, 1}}}, |
| 180 |
| 181 {{{0, 2}, {2, 3}, {5, 1}, {3, 2}}}, |
| 182 {{{1, 5}, {2, 3}, {2, 0}, {3, 2}}}, |
| 183 |
| 184 {{{2, 6}, {4, 5}, {1, 0}, {6, 1}}}, |
| 185 {{{0, 1}, {1, 6}, {6, 2}, {5, 4}}}, |
| 186 |
| 187 {{{0, 1}, {1, 2}, {6, 5}, {5, 4}}}, |
| 188 {{{5, 6}, {4, 5}, {1, 0}, {2, 1}}}, |
| 189 |
| 190 {{{2.5119999999999996, 1.5710000000000002}, {2.6399999999999983, 1.6599999999999
997}, |
| 191 {2.8000000000000007, 1.8000000000000003}, {3, 2}}}, |
| 192 {{{2.4181876227114887, 1.9849772580462195}, {2.8269904869227211, 2.0093306502468
34}, |
| 193 {3.2004679292461624, 1.9942047174679169}, {3.4986199496818058, 2.0035994
597094731}}}, |
| 194 |
| 195 {{{2, 3}, {1, 4}, {1, 0}, {6, 0}}}, |
| 196 {{{0, 1}, {0, 6}, {3, 2}, {4, 1}}}, |
| 197 |
| 198 {{{0, 2}, {1, 5}, {1, 0}, {6, 1}}}, |
| 199 {{{0, 1}, {1, 6}, {2, 0}, {5, 1}}}, |
| 200 |
| 201 {{{0, 1}, {1, 5}, {2, 1}, {4, 0}}}, |
| 202 {{{1, 2}, {0, 4}, {1, 0}, {5, 1}}}, |
| 203 |
| 204 {{{0, 1}, {3, 5}, {2, 1}, {3, 1}}}, |
| 205 {{{1, 2}, {1, 3}, {1, 0}, {5, 3}}}, |
| 206 |
| 207 {{{0, 1}, {2, 5}, {6, 0}, {5, 3}}}, |
| 208 {{{0, 6}, {3, 5}, {1, 0}, {5, 2}}}, |
| 209 |
| 210 {{{0, 1}, {3, 6}, {1, 0}, {5, 2}}}, |
| 211 {{{0, 1}, {2, 5}, {1, 0}, {6, 3}}}, |
| 212 |
| 213 {{{1, 2}, {5, 6}, {1, 0}, {1, 0}}}, |
| 214 {{{0, 1}, {0, 1}, {2, 1}, {6, 5}}}, |
| 215 |
| 216 {{{0, 6}, {1, 2}, {1, 0}, {1, 0}}}, |
| 217 {{{0, 1}, {0, 1}, {6, 0}, {2, 1}}}, |
| 218 |
| 219 {{{0, 2}, {0, 1}, {3, 0}, {1, 0}}}, |
| 220 {{{0, 3}, {0, 1}, {2, 0}, {1, 0}}}, |
| 221 }; |
| 222 |
| 223 const size_t newTestSetCount = sizeof(newTestSet) / sizeof(newTestSet[0]); |
| 224 |
| 225 static void oneOff(skiatest::Reporter* reporter, const SkDCubic& cubic1, const S
kDCubic& cubic2) { |
| 226 #if ONE_OFF_DEBUG |
| 227 SkDebugf("computed quadratics given\n"); |
| 228 SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\
n", |
| 229 cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY, |
| 230 cubic1[2].fX, cubic1[2].fY, cubic1[3].fX, cubic1[3].fY); |
| 231 SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\
n", |
| 232 cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY, |
| 233 cubic2[2].fX, cubic2[2].fY, cubic2[3].fX, cubic2[3].fY); |
| 234 #endif |
| 235 SkTDArray<SkDQuad> quads1; |
| 236 CubicToQuads(cubic1, cubic1.calcPrecision(), quads1); |
| 237 #if ONE_OFF_DEBUG |
| 238 SkDebugf("computed quadratics set 1\n"); |
| 239 for (int index = 0; index < quads1.count(); ++index) { |
| 240 const SkDQuad& q = quads1[index]; |
| 241 SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", q[0].fX
, q[0].fY, |
| 242 q[1].fX, q[1].fY, q[2].fX, q[2].fY); |
| 243 } |
| 244 #endif |
| 245 SkTDArray<SkDQuad> quads2; |
| 246 CubicToQuads(cubic2, cubic2.calcPrecision(), quads2); |
| 247 #if ONE_OFF_DEBUG |
| 248 SkDebugf("computed quadratics set 2\n"); |
| 249 for (int index = 0; index < quads2.count(); ++index) { |
| 250 const SkDQuad& q = quads2[index]; |
| 251 SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", q[0].fX
, q[0].fY, |
| 252 q[1].fX, q[1].fY, q[2].fX, q[2].fY); |
| 253 } |
| 254 #endif |
| 255 SkIntersections intersections; |
| 256 intersections.intersect(cubic1, cubic2); |
| 257 double tt1, tt2; |
| 258 SkDPoint xy1, xy2; |
| 259 for (int pt3 = 0; pt3 < intersections.used(); ++pt3) { |
| 260 tt1 = intersections[0][pt3]; |
| 261 xy1 = cubic1.xyAtT(tt1); |
| 262 tt2 = intersections[1][pt3]; |
| 263 xy2 = cubic2.xyAtT(tt2); |
| 264 #if ONE_OFF_DEBUG |
| 265 SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1
.9g\n", |
| 266 __FUNCTION__, tt1, xy1.fX, xy1.fY, intersections.pt(pt3).fX, |
| 267 intersections.pt(pt3).fY, xy2.fX, xy2.fY, tt2); |
| 268 #endif |
| 269 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); |
| 270 } |
| 271 } |
| 272 |
| 273 static void oneOff(skiatest::Reporter* reporter, int outer, int inner) { |
| 274 const SkDCubic& cubic1 = testSet[outer]; |
| 275 const SkDCubic& cubic2 = testSet[inner]; |
| 276 oneOff(reporter, cubic1, cubic2); |
| 277 } |
| 278 |
| 279 static void newOneOff(skiatest::Reporter* reporter, int outer, int inner) { |
| 280 const SkDCubic& cubic1 = newTestSet[outer]; |
| 281 const SkDCubic& cubic2 = newTestSet[inner]; |
| 282 oneOff(reporter, cubic1, cubic2); |
| 283 } |
| 284 |
| 285 static void oneOffTest(skiatest::Reporter* reporter) { |
| 286 newOneOff(reporter, 0, 1); |
| 287 oneOff(reporter, 0, 1); |
| 288 } |
| 289 |
| 290 static void oneOffTests(skiatest::Reporter* reporter) { |
| 291 for (size_t outer = 0; outer < testSetCount - 1; ++outer) { |
| 292 for (size_t inner = outer + 1; inner < testSetCount; ++inner) { |
| 293 oneOff(reporter, outer, inner); |
| 294 } |
| 295 } |
| 296 for (size_t outer = 0; outer < newTestSetCount - 1; ++outer) { |
| 297 for (size_t inner = outer + 1; inner < newTestSetCount; ++inner) { |
| 298 oneOff(reporter, outer, inner); |
| 299 } |
| 300 } |
| 301 } |
| 302 |
| 303 #define DEBUG_CRASH 0 |
| 304 |
| 305 static void CubicIntersection_RandTest(skiatest::Reporter* reporter) { |
| 306 srand(0); |
| 307 const int tests = 10000000; |
| 308 unsigned seed = 0; |
| 309 for (int test = 0; test < tests; ++test) { |
| 310 SkDCubic cubic1, cubic2; |
| 311 for (int i = 0; i < 4; ++i) { |
| 312 cubic1[i].fX = static_cast<double>(rand_r(&seed)) / RAND_MAX * 100; |
| 313 cubic1[i].fY = static_cast<double>(rand_r(&seed)) / RAND_MAX * 100; |
| 314 cubic2[i].fX = static_cast<double>(rand_r(&seed)) / RAND_MAX * 100; |
| 315 cubic2[i].fY = static_cast<double>(rand_r(&seed)) / RAND_MAX * 100; |
| 316 } |
| 317 #if DEBUG_CRASH |
| 318 char str[1024]; |
| 319 snprintf(str, sizeof(str), |
| 320 "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},
\n" |
| 321 "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},
\n", |
| 322 cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY, cubic1[
2].fX, cubic1[2].fY, |
| 323 cubic1[3].fX, cubic1[3].fY, |
| 324 cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY, cubic2[
2].fX, cubic2[2].fY, |
| 325 cubic2[3].fX, cubic2[3].fY); |
| 326 #endif |
| 327 SkDRect rect1, rect2; |
| 328 rect1.setBounds(cubic1); |
| 329 rect2.setBounds(cubic2); |
| 330 bool boundsIntersect = rect1.fLeft <= rect2.fRight && rect2.fLeft <= rec
t2.fRight |
| 331 && rect1.fTop <= rect2.fBottom && rect2.fTop <= rect1.fBottom; |
| 332 if (test == -1) { |
| 333 SkDebugf("ready...\n"); |
| 334 } |
| 335 SkIntersections intersections2; |
| 336 bool newIntersects = intersections2.intersect(cubic1, cubic2); |
| 337 if (!boundsIntersect && newIntersects) { |
| 338 #if DEBUG_CRASH |
| 339 SkDebugf("%s %d unexpected intersection boundsIntersect=%d " |
| 340 " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsInte
rsect, |
| 341 newIntersects, __FUNCTION__, str); |
| 342 #endif |
| 343 REPORTER_ASSERT(reporter, 0); |
| 344 } |
| 345 for (int pt = 0; pt < intersections2.used(); ++pt) { |
| 346 double tt1 = intersections2[0][pt]; |
| 347 SkDPoint xy1 = cubic1.xyAtT(tt1); |
| 348 double tt2 = intersections2[1][pt]; |
| 349 SkDPoint xy2 = cubic2.xyAtT(tt2); |
| 350 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); |
| 351 } |
| 352 } |
| 353 } |
| 354 |
| 355 static void intersectionFinder(int index0, int index1, double t1Seed, double t2S
eed, |
| 356 double t1Step, double t2Step) { |
| 357 const SkDCubic& cubic1 = newTestSet[index0]; |
| 358 const SkDCubic& cubic2 = newTestSet[index1]; |
| 359 SkDPoint t1[3], t2[3]; |
| 360 bool toggle = true; |
| 361 do { |
| 362 t1[0] = cubic1.xyAtT(t1Seed - t1Step); |
| 363 t1[1] = cubic1.xyAtT(t1Seed); |
| 364 t1[2] = cubic1.xyAtT(t1Seed + t1Step); |
| 365 t2[0] = cubic2.xyAtT(t2Seed - t2Step); |
| 366 t2[1] = cubic2.xyAtT(t2Seed); |
| 367 t2[2] = cubic2.xyAtT(t2Seed + t2Step); |
| 368 double dist[3][3]; |
| 369 dist[1][1] = t1[1].distance(t2[1]); |
| 370 int best_i = 1, best_j = 1; |
| 371 for (int i = 0; i < 3; ++i) { |
| 372 for (int j = 0; j < 3; ++j) { |
| 373 if (i == 1 && j == 1) { |
| 374 continue; |
| 375 } |
| 376 dist[i][j] = t1[i].distance(t2[j]); |
| 377 if (dist[best_i][best_j] > dist[i][j]) { |
| 378 best_i = i; |
| 379 best_j = j; |
| 380 } |
| 381 } |
| 382 } |
| 383 if (best_i == 0) { |
| 384 t1Seed -= t1Step; |
| 385 } else if (best_i == 2) { |
| 386 t1Seed += t1Step; |
| 387 } |
| 388 if (best_j == 0) { |
| 389 t2Seed -= t2Step; |
| 390 } else if (best_j == 2) { |
| 391 t2Seed += t2Step; |
| 392 } |
| 393 if (best_i == 1 && best_j == 1) { |
| 394 if ((toggle ^= true)) { |
| 395 t1Step /= 2; |
| 396 } else { |
| 397 t2Step /= 2; |
| 398 } |
| 399 } |
| 400 } while (!t1[1].approximatelyEqual(t2[1])); |
| 401 t1Step = t2Step = 0.1; |
| 402 double t10 = t1Seed - t1Step * 2; |
| 403 double t12 = t1Seed + t1Step * 2; |
| 404 double t20 = t2Seed - t2Step * 2; |
| 405 double t22 = t2Seed + t2Step * 2; |
| 406 SkDPoint test; |
| 407 while (!approximately_zero(t1Step)) { |
| 408 test = cubic1.xyAtT(t10); |
| 409 t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step; |
| 410 t1Step /= 2; |
| 411 } |
| 412 t1Step = 0.1; |
| 413 while (!approximately_zero(t1Step)) { |
| 414 test = cubic1.xyAtT(t12); |
| 415 t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step; |
| 416 t1Step /= 2; |
| 417 } |
| 418 while (!approximately_zero(t2Step)) { |
| 419 test = cubic2.xyAtT(t20); |
| 420 t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step; |
| 421 t2Step /= 2; |
| 422 } |
| 423 t2Step = 0.1; |
| 424 while (!approximately_zero(t2Step)) { |
| 425 test = cubic2.xyAtT(t22); |
| 426 t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step; |
| 427 t2Step /= 2; |
| 428 } |
| 429 #if ONE_OFF_DEBUG |
| 430 SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__, |
| 431 t10, t1Seed, t12, t20, t2Seed, t22); |
| 432 SkDPoint p10 = cubic1.xyAtT(t10); |
| 433 SkDPoint p1Seed = cubic1.xyAtT(t1Seed); |
| 434 SkDPoint p12 = cubic1.xyAtT(t12); |
| 435 SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, |
| 436 p10.fX, p10.fY, p1Seed.fX, p1Seed.fY, p12.fX, p12.fY); |
| 437 SkDPoint p20 = cubic2.xyAtT(t20); |
| 438 SkDPoint p2Seed = cubic2.xyAtT(t2Seed); |
| 439 SkDPoint p22 = cubic2.xyAtT(t22); |
| 440 SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, |
| 441 p20.fX, p20.fY, p2Seed.fX, p2Seed.fY, p22.fX, p22.fY); |
| 442 #endif |
| 443 } |
| 444 |
| 445 static void CubicIntersection_IntersectionFinder() { |
| 446 // double t1Seed = 0.87; |
| 447 // double t2Seed = 0.87; |
| 448 double t1Step = 0.000001; |
| 449 double t2Step = 0.000001; |
| 450 intersectionFinder(0, 1, 0.855895664, 0.864850875, t1Step, t2Step); |
| 451 intersectionFinder(0, 1, 0.865207906, 0.865207887, t1Step, t2Step); |
| 452 intersectionFinder(0, 1, 0.865213351, 0.865208087, t1Step, t2Step); |
| 453 } |
| 454 |
| 455 static void cubicIntersectionSelfTest(skiatest::Reporter* reporter) { |
| 456 const SkDCubic selfSet[] = { |
| 457 {{{0, 2}, {2, 3}, {5, 1}, {3, 2}}}, |
| 458 {{{0, 2}, {3, 5}, {5, 0}, {4, 2}}}, |
| 459 {{{3.34, 8.98}, {1.95, 10.27}, {3.76, 7.65}, {4.96, 10.64}}}, |
| 460 {{{3.13, 2.74}, {1.08, 4.62}, {3.71, 0.94}, {2.01, 3.81}}}, |
| 461 {{{6.71, 3.14}, {7.99, 2.75}, {8.27, 1.96}, {6.35, 3.57}}}, |
| 462 {{{12.81, 7.27}, {7.22, 6.98}, {12.49, 8.97}, {11.42, 6.18}}}, |
| 463 }; |
| 464 size_t selfSetCount = sizeof(selfSet) / sizeof(selfSet[0]); |
| 465 size_t firstFail = 1; |
| 466 for (size_t index = firstFail; index < selfSetCount; ++index) { |
| 467 const SkDCubic& cubic = selfSet[index]; |
| 468 #if ONE_OFF_DEBUG |
| 469 int idx2; |
| 470 double max[3]; |
| 471 int ts = cubic.findMaxCurvature(max); |
| 472 for (idx2 = 0; idx2 < ts; ++idx2) { |
| 473 SkDebugf("%s max[%d]=%1.9g (%1.9g, %1.9g)\n", __FUNCTION__, idx2, |
| 474 max[idx2], cubic.xyAtT(max[idx2]).fX, cubic.xyAtT(max[idx2])
.fY); |
| 475 } |
| 476 SkTDArray<double> ts1; |
| 477 SkTDArray<SkDQuad> quads1; |
| 478 cubic.toQuadraticTs(cubic.calcPrecision(), &ts1); |
| 479 for (idx2 = 0; idx2 < ts1.count(); ++idx2) { |
| 480 SkDebugf("%s t[%d]=%1.9g\n", __FUNCTION__, idx2, ts1[idx2]); |
| 481 } |
| 482 CubicToQuads(cubic, cubic.calcPrecision(), quads1); |
| 483 for (idx2 = 0; idx2 < quads1.count(); ++idx2) { |
| 484 const SkDQuad& q = quads1[idx2]; |
| 485 SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", |
| 486 q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY); |
| 487 } |
| 488 SkDebugf("\n"); |
| 489 #endif |
| 490 SkIntersections i; |
| 491 int result = i.intersect(cubic); |
| 492 REPORTER_ASSERT(reporter, result == 1); |
| 493 REPORTER_ASSERT(reporter, i.used() == 1); |
| 494 REPORTER_ASSERT(reporter, !approximately_equal(i[0][0], i[1][0])); |
| 495 SkDPoint pt1 = cubic.xyAtT(i[0][0]); |
| 496 SkDPoint pt2 = cubic.xyAtT(i[1][0]); |
| 497 REPORTER_ASSERT(reporter, pt1.approximatelyEqual(pt2)); |
| 498 } |
| 499 } |
| 500 |
| 501 static void TestCubicIntersection(skiatest::Reporter* reporter) { |
| 502 oneOffTest(reporter); |
| 503 oneOffTests(reporter); |
| 504 cubicIntersectionSelfTest(reporter); |
| 505 standardTestCases(reporter); |
| 506 if (false) CubicIntersection_IntersectionFinder(); |
| 507 if (false) CubicIntersection_RandTest(reporter); |
| 508 } |
| 509 |
| 510 #include "TestClassDef.h" |
| 511 DEFINE_TESTCLASS("PathOpsCubicIntersectionTest", CubicIntersectionTestClass, Tes
tCubicIntersection) |
OLD | NEW |