src/third_party/skia/tests/PathOpsCubicIntersectionTest.cpp

   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         int order2 = reduce2.reduce(cubic2, SkReduceOrder::kNo_Quadratics);
  24         const bool showSkipped = false;
  25         if (order1 < 4) {
  26             if (showSkipped) {
  27                 SkDebugf("%s [%d] cubic1 order=%d\n", __FUNCTION__, iIndex, order1);
  28             }
  29             continue;
  30         }
  31         if (order2 < 4) {
  32             if (showSkipped) {
  33                 SkDebugf("%s [%d] cubic2 order=%d\n", __FUNCTION__, iIndex, order2);
  34             }
  35             continue;
  36         }
  37         SkIntersections tIntersections;
  38         tIntersections.intersect(cubic1, cubic2);
  39         if (!tIntersections.used()) {
  40             if (showSkipped) {
  41                 SkDebugf("%s [%d] no intersection\n", __FUNCTION__, iIndex);
  42             }
  43             continue;
  44         }
  45         if (tIntersections.isCoincident(0)) {
  46             if (showSkipped) {
  47                 SkDebugf("%s [%d] coincident\n", __FUNCTION__, iIndex);
  48             }
  49             continue;
  50         }
  51         for (int pt = 0; pt < tIntersections.used(); ++pt) {
  52             double tt1 = tIntersections[0][pt];
  53             SkDPoint xy1 = cubic1.ptAtT(tt1);
  54             double tt2 = tIntersections[1][pt];
  55             SkDPoint xy2 = cubic2.ptAtT(tt2);
  56             if (!xy1.approximatelyEqual(xy2)) {
  57                 SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n",
  58                     __FUNCTION__, (int)index, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY);
  59             }
  60             REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
  61         }
  62         reporter->bumpTestCount();
  63     }
  64 }
  65
  66 static const SkDCubic testSet[] = {
  67 // FIXME: uncommenting these two will cause this to fail
  68 // this results in two curves very nearly but not exactly coincident
  69 #if 0
  70 {{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306},
  71       {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}},
  72 {{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826},
  73       {75.3863417, 18.24489}}},
  74 #endif
  75
  76 {{{0, 0}, {0, 1}, {1, 1}, {1, 0}}},
  77 {{{1, 0}, {0, 0}, {0, 1}, {1, 1}}},
  78
  79 {{{0, 1}, {4, 5}, {1, 0}, {5, 3}}},
  80 {{{0, 1}, {3, 5}, {1, 0}, {5, 4}}},
  81
  82 {{{0, 1}, {1, 6}, {1, 0}, {1, 0}}},
  83 {{{0, 1}, {0, 1}, {1, 0}, {6, 1}}},
  84
  85 {{{0, 1}, {3, 4}, {1, 0}, {5, 1}}},
  86 {{{0, 1}, {1, 5}, {1, 0}, {4, 3}}},
  87
  88 {{{0, 1}, {1, 2}, {1, 0}, {6, 1}}},
  89 {{{0, 1}, {1, 6}, {1, 0}, {2, 1}}},
  90
  91 {{{0, 1}, {0, 5}, {1, 0}, {4, 0}}},
  92 {{{0, 1}, {0, 4}, {1, 0}, {5, 0}}},
  93
  94 {{{0, 1}, {3, 4}, {1, 0}, {3, 0}}},
  95 {{{0, 1}, {0, 3}, {1, 0}, {4, 3}}},
  96
  97 {{{0, 0}, {1, 2}, {3, 4}, {4, 4}}},
  98 {{{0, 0}, {1, 2}, {3, 4}, {4, 4}}},
  99 {{{4, 4}, {3, 4}, {1, 2}, {0, 0}}},
 100
 101 {{{0, 1}, {2, 3}, {1, 0}, {1, 0}}},
 102 {{{0, 1}, {0, 1}, {1, 0}, {3, 2}}},
 103
 104 {{{0, 2}, {0, 1}, {1, 0}, {1, 0}}},
 105 {{{0, 1}, {0, 1}, {2, 0}, {1, 0}}},
 106
 107 {{{0, 1}, {0, 2}, {1, 0}, {1, 0}}},
 108 {{{0, 1}, {0, 1}, {1, 0}, {2, 0}}},
 109
 110 {{{0, 1}, {1, 6}, {1, 0}, {2, 0}}},
 111 {{{0, 1}, {0, 2}, {1, 0}, {6, 1}}},
 112
 113 {{{0, 1}, {5, 6}, {1, 0}, {1, 0}}},
 114 {{{0, 1}, {0, 1}, {1, 0}, {6, 5}}},
 115
 116 {{{95.837747722788592, 45.025976907939643}, {16.564570095652982, 0.72959763963222402},
 117         {63.209855865319199, 68.047528419665767}, {57.640240647662544, 59.524565264361243}}},
 118 {{{51.593891741518817, 38.53849970667553}, {62.34752929878772, 74.924924725166022},
 119         {74.810149322641152, 34.17966562983564}, {29.368398119401373, 94.66719277886078}}},
 120
 121 {{{39.765160968417838, 33.060396198677083}, {5.1922921581157908, 66.854301452103215},
 122         {31.619281802149157, 25.269248720849514}, {81.541621071073038, 70.025341524754353}}},
 123 {{{46.078911165743556, 48.259962651999651}, {20.24450549867214, 49.403916182650214},
 124         {0.26325131778756683, 24.46489805563581}, {15.915006546264051, 83.515023059917155}}},
 125
 126 {{{65.454505973241524, 93.881892270353575}, {45.867360264932437, 92.723972719499827},
 127         {2.1464054482739447, 74.636369140183717}, {33.774068594804994, 40.770872887582925}}},
 128 {{{72.963387832494163, 95.659300729473728}, {11.809496633619768, 82.209921247423594},
 129         {13.456139067865974, 57.329313623406605}, {36.060621606214262, 70.867335643091849}}},
 130
 131 {{{32.484981432782945, 75.082940782924624}, {42.467313093350882, 48.131159948246157},
 132         {3.5963115764764657, 43.208665839959245}, {79.442476890721579, 89.709102357602262}}},
 133 {{{18.98573861410177, 93.308887208490106}, {40.405250173250792, 91.039661826118675},
 134         {8.0467721950480584, 42.100282172719147}, {40.883324221187891, 26.030185504830527}}},
 135
 136 {{{7.5374809128872498, 82.441702896003477}, {22.444346930107265, 22.138854312775123},
 137         {66.76091829629658, 50.753805856571446}, {78.193478508942519, 97.7932997968948}}},
 138 {{{97.700573130371311, 53.53260215070685}, {87.72443481149358, 84.575876772671876},
 139         {19.215031396232092, 47.032676472809484}, {11.989686410869325, 10.659507480757082}}},
 140
 141 {{{26.192053931854691, 9.8504326817814416}, {10.174241480498686, 98.476562741434464},
 142         {21.177712558385782, 33.814968789841501}, {75.329030899018534, 55.02231980442177}}},
 143 {{{56.222082700683771, 24.54395039218662}, {95.589995289030483, 81.050822735322086},
 144         {28.180450866082897, 28.837706255185282}, {60.128952916771617, 87.311672180570511}}},
 145
 146 {{{42.449716172390481, 52.379709366885805}, {27.896043159019225, 48.797373636065686},
 147         {92.770268299044233, 89.899302036454571}, {12.102066544863426, 99.43241951960718}}},
 148 {{{45.77532924980639, 45.958701495993274}, {37.458701356062065, 68.393691335056758},
 149         {37.569326692060258, 27.673713456687381}, {60.674866037757539, 62.47349659096146}}},
 150
 151 {{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306},
 152         {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}},
 153 {{{61.336508189019057, 82.693132843213675}, {44.639380902349664, 54.074825790745592},
 154         {16.815615499771951, 20.049704667203923}, {41.866884958868326, 56.735503699973002}}},
 155
 156 {{{18.1312339, 31.6473732}, {95.5711034, 63.5350219}, {92.3283165, 62.0158945},
 157         {18.5656052, 32.1268808}}},
 158 {{{97.402018, 35.7169972}, {33.1127443, 25.8935163}, {1.13970027, 54.9424981},
 159         {56.4860195, 60.529264}}},
 160 };
 161
 162 const int testSetCount = (int) SK_ARRAY_COUNT(testSet);
 163
 164 static const SkDCubic newTestSet[] = {
 165 {{{980.9000244140625, 1474.3280029296875}, {980.9000244140625, 1474.3280029296875}, {978.89300537109375, 1471.95703125}, {981.791015625, 1469.487060546875}}},
 166 {{{981.791015625, 1469.487060546875}, {981.791015625, 1469.4859619140625}, {983.3580322265625, 1472.72900390625}, {980.9000244140625, 1474.3280029296875}}},
 167
 168 {{{275,532}, {277.209137,532}, {279,530.209106}, {279,528}}},
 169 {{{278,529}, {278,530.65686}, {276.65686,532}, {275,532}}},
 170
 171 #if 0  // FIXME: asserts coincidence, not working yet
 172 {{{195, 785}, {124.30755615234375, 785}, {67, 841.85986328125}, {67, 912}}},
 173 {{{67, 913}, {67, 842.30755615234375}, {123.85984039306641, 785}, {194, 785}}},
 174 #endif
 175
 176 {{{149,710.001465}, {149.000809,712.209961}, {150.791367,714}, {153,714}}},
 177 {{{154,715}, {151.238571,715}, {149,712.761414}, {149,710}}},
 178
 179 {{{1,2}, {1,2}, {2,0}, {6,0}}},
 180 {{{0,2}, {0,6}, {2,1}, {2,1}}},
 181
 182 {{{0,1}, {2,3}, {5,1}, {4,3}}},
 183 {{{1,5}, {3,4}, {1,0}, {3,2}}},
 184
 185 {{{399,657}, {399,661.970581}, {403.029449,666}, {408,666}}},
 186 {{{406,666}, {402.686279,666}, {400,663.313721}, {400,660}}},
 187
 188 {{{0,5}, {3,5}, {3,0}, {3,2}}},
 189 {{{0,3}, {2,3}, {5,0}, {5,3}}},
 190
 191 {{{132, 11419}, {130.89543151855469, 11419}, {130, 11418.1044921875}, {130, 11417}}},
 192
 193 {{{3, 4}, {1, 5}, {4, 3}, {6, 4}}},
 194 {{{3, 4}, {4, 6}, {4, 3}, {5, 1}}},
 195
 196 {{{130.04275512695312, 11417.413085937500 },
 197     {130.23312377929687, 11418.319335937500 },
 198     {131.03707885742187, 11419.000000000000 },
 199     {132.00000000000000, 11419.000000000000 }}},
 200
 201 {{{132.00000000000000, 11419.000000000000 },
 202     {130.89543151855469, 11419.000000000000 },
 203     {130.00000000000000, 11418.104492187500 },
 204     {130.00000000000000, 11417.000000000000 }}},
 205
 206 {{{1.0516976506771041, 2.9684399028541346 },
 207     {1.0604363140895228, 2.9633503074444141 },
 208     {1.0692548215065762, 2.9580354426587459 },
 209     {1.0781560339512140, 2.9525043684031349 }}},
 210
 211 {{{1.0523038101345104, 2.9523755204833737 },
 212     {1.0607035288264237, 2.9580853881628375 },
 213     {1.0690530472271964, 2.9633896794787749 },
 214     {1.0773566568712512, 2.9682969775000219 }}},
 215
 216 {{{1.0386522625066592, 2.9759024812329078 },
 217     {1.0559713690392631, 2.9661782500838885 },
 218     {1.0736041309019990, 2.9555348259177858 },
 219     {1.0915734362784633, 2.9440446879826569 }}},
 220
 221 {{{1.0396670794879301, 2.9435062123457261 },
 222     {1.0565690546812769, 2.9557413250983462 },
 223     {1.0732616463413533, 2.9663369676594282 },
 224     {1.0897791867435489, 2.9753618045797472 }}},
 225
 226 {{{0.8685656183311091, 3.0409266475785208 },
 227     {0.99189542936395292, 3.0212163698184424 },
 228     {1.1302108367493320, 2.9265646471747306 },
 229     {1.2952305904872474, 2.7940808546473788 }}},
 230
 231 {{{0.85437872843682727, 2.7536036928549055 },
 232     {1.0045584590592620, 2.9493041024831705 },
 233     {1.1336998329885613, 3.0248027987251747 },
 234     {1.2593809752247314, 3.0152560315809107 }}},
 235
 236 {{{0, 1}, {1, 6}, {1, 0}, {6, 2}}},
 237 {{{0, 1}, {2, 6}, {1, 0}, {6, 1}}},
 238
 239 {{{134,11414}, {131.990234375,11414}, {130.32666015625,11415.482421875}, {130.04275512695312,11417.4130859375}}},
 240 {{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}},
 241
 242 {{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}},
 243 {{{130.04275512695312,11417.4130859375}, {130.23312377929687,11418.3193359375}, {131.03707885742187,11419}, {132,11419}}},
 244
 245 {{{0, 1}, {2, 3}, {5, 1}, {4, 3}}},
 246 {{{1, 5}, {3, 4}, {1, 0}, {3, 2}}},
 247
 248 {{{3, 5}, {1, 6}, {5, 0}, {3, 1}}},
 249 {{{0, 5}, {1, 3}, {5, 3}, {6, 1}}},
 250
 251 {{{0, 1}, {1, 5}, {1, 0}, {1, 0}}},
 252 {{{0, 1}, {0, 1}, {1, 0}, {5, 1}}},
 253
 254 {{{1, 3}, {5, 6}, {5, 3}, {5, 4}}},
 255 {{{3, 5}, {4, 5}, {3, 1}, {6, 5}}},
 256
 257 {{{0, 5}, {0, 5}, {5, 4}, {6, 4}}},
 258 {{{4, 5}, {4, 6}, {5, 0}, {5, 0}}},
 259
 260 {{{0, 4}, {1, 3}, {5, 4}, {4, 2}}},
 261 {{{4, 5}, {2, 4}, {4, 0}, {3, 1}}},
 262
 263 {{{0, 2}, {1, 5}, {3, 2}, {4, 1}}},
 264 {{{2, 3}, {1, 4}, {2, 0}, {5, 1}}},
 265
 266 {{{0, 2}, {2, 3}, {5, 1}, {3, 2}}},
 267 {{{1, 5}, {2, 3}, {2, 0}, {3, 2}}},
 268
 269 {{{2, 6}, {4, 5}, {1, 0}, {6, 1}}},
 270 {{{0, 1}, {1, 6}, {6, 2}, {5, 4}}},
 271
 272 {{{0, 1}, {1, 2}, {6, 5}, {5, 4}}},
 273 {{{5, 6}, {4, 5}, {1, 0}, {2, 1}}},
 274
 275 {{{2.5119999999999996, 1.5710000000000002}, {2.6399999999999983, 1.6599999999999997},
 276         {2.8000000000000007, 1.8000000000000003}, {3, 2}}},
 277 {{{2.4181876227114887, 1.9849772580462195}, {2.8269904869227211, 2.009330650246834},
 278         {3.2004679292461624, 1.9942047174679169}, {3.4986199496818058, 2.0035994597094731}}},
 279
 280 {{{2, 3}, {1, 4}, {1, 0}, {6, 0}}},
 281 {{{0, 1}, {0, 6}, {3, 2}, {4, 1}}},
 282
 283 {{{0, 2}, {1, 5}, {1, 0}, {6, 1}}},
 284 {{{0, 1}, {1, 6}, {2, 0}, {5, 1}}},
 285
 286 {{{0, 1}, {1, 5}, {2, 1}, {4, 0}}},
 287 {{{1, 2}, {0, 4}, {1, 0}, {5, 1}}},
 288
 289 {{{0, 1}, {3, 5}, {2, 1}, {3, 1}}},
 290 {{{1, 2}, {1, 3}, {1, 0}, {5, 3}}},
 291
 292 {{{0, 1}, {2, 5}, {6, 0}, {5, 3}}},
 293 {{{0, 6}, {3, 5}, {1, 0}, {5, 2}}},
 294
 295 {{{0, 1}, {3, 6}, {1, 0}, {5, 2}}},
 296 {{{0, 1}, {2, 5}, {1, 0}, {6, 3}}},
 297
 298 {{{1, 2}, {5, 6}, {1, 0}, {1, 0}}},
 299 {{{0, 1}, {0, 1}, {2, 1}, {6, 5}}},
 300
 301 {{{0, 6}, {1, 2}, {1, 0}, {1, 0}}},
 302 {{{0, 1}, {0, 1}, {6, 0}, {2, 1}}},
 303
 304 {{{0, 2}, {0, 1}, {3, 0}, {1, 0}}},
 305 {{{0, 3}, {0, 1}, {2, 0}, {1, 0}}},
 306 };
 307
 308 const int newTestSetCount = (int) SK_ARRAY_COUNT(newTestSet);
 309
 310 static void oneOff(skiatest::Reporter* reporter, const SkDCubic& cubic1, const SkDCubic& cubic2,
 311         bool coin) {
 312     SkASSERT(ValidCubic(cubic1));
 313     SkASSERT(ValidCubic(cubic2));
 314 #if ONE_OFF_DEBUG
 315     SkDebugf("computed quadratics given\n");
 316     SkDebugf("  {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
 317         cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY,
 318         cubic1[2].fX, cubic1[2].fY, cubic1[3].fX, cubic1[3].fY);
 319     SkDebugf("  {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
 320         cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY,
 321         cubic2[2].fX, cubic2[2].fY, cubic2[3].fX, cubic2[3].fY);
 322 #endif
 323     SkTArray<SkDQuad, true> quads1;
 324     CubicToQuads(cubic1, cubic1.calcPrecision(), quads1);
 325 #if ONE_OFF_DEBUG
 326     SkDebugf("computed quadratics set 1\n");
 327     for (int index = 0; index < quads1.count(); ++index) {
 328         const SkDQuad& q = quads1[index];
 329         SkDebugf("  {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].fX, q[0].fY,
 330                  q[1].fX, q[1].fY,  q[2].fX, q[2].fY);
 331     }
 332 #endif
 333     SkTArray<SkDQuad, true> quads2;
 334     CubicToQuads(cubic2, cubic2.calcPrecision(), quads2);
 335 #if ONE_OFF_DEBUG
 336     SkDebugf("computed quadratics set 2\n");
 337     for (int index = 0; index < quads2.count(); ++index) {
 338         const SkDQuad& q = quads2[index];
 339         SkDebugf("  {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].fX, q[0].fY,
 340                  q[1].fX, q[1].fY,  q[2].fX, q[2].fY);
 341     }
 342 #endif
 343     SkIntersections intersections;
 344     intersections.intersect(cubic1, cubic2);
 345     REPORTER_ASSERT(reporter, !coin || intersections.used() == 2);
 346     double tt1, tt2;
 347     SkDPoint xy1, xy2;
 348     for (int pt3 = 0; pt3 < intersections.used(); ++pt3) {
 349         tt1 = intersections[0][pt3];
 350         xy1 = cubic1.ptAtT(tt1);
 351         tt2 = intersections[1][pt3];
 352         xy2 = cubic2.ptAtT(tt2);
 353         const SkDPoint& iPt = intersections.pt(pt3);
 354 #if ONE_OFF_DEBUG
 355         SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n",
 356                 __FUNCTION__, tt1, xy1.fX, xy1.fY, iPt.fX,
 357                 iPt.fY, xy2.fX, xy2.fY, tt2);
 358 #endif
 359        REPORTER_ASSERT(reporter, xy1.approximatelyEqual(iPt));
 360        REPORTER_ASSERT(reporter, xy2.approximatelyEqual(iPt));
 361        REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
 362     }
 363     reporter->bumpTestCount();
 364 }
 365
 366 static void oneOff(skiatest::Reporter* reporter, int outer, int inner) {
 367     const SkDCubic& cubic1 = testSet[outer];
 368     const SkDCubic& cubic2 = testSet[inner];
 369     oneOff(reporter, cubic1, cubic2, false);
 370 }
 371
 372 static void newOneOff(skiatest::Reporter* reporter, int outer, int inner) {
 373     const SkDCubic& cubic1 = newTestSet[outer];
 374     const SkDCubic& cubic2 = newTestSet[inner];
 375     oneOff(reporter, cubic1, cubic2, false);
 376 }
 377
 378 static void oneOffTests(skiatest::Reporter* reporter) {
 379     for (int outer = 0; outer < testSetCount - 1; ++outer) {
 380         for (int inner = outer + 1; inner < testSetCount; ++inner) {
 381             oneOff(reporter, outer, inner);
 382         }
 383     }
 384     for (int outer = 0; outer < newTestSetCount - 1; ++outer) {
 385         for (int inner = outer + 1; inner < newTestSetCount; ++inner) {
 386             newOneOff(reporter, outer, inner);
 387         }
 388     }
 389 }
 390
 391 #define DEBUG_CRASH 0
 392
 393 static void CubicIntersection_RandTest(skiatest::Reporter* reporter) {
 394     srand(0);
 395     const int tests = 10000000;
 396 #if !defined(SK_BUILD_FOR_WIN) && !defined(SK_BUILD_FOR_ANDROID)
 397     unsigned seed = 0;
 398 #endif
 399     for (int test = 0; test < tests; ++test) {
 400         SkDCubic cubic1, cubic2;
 401         for (int i = 0; i < 4; ++i) {
 402             cubic1[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
 403             cubic1[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
 404             cubic2[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
 405             cubic2[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
 406         }
 407     #if DEBUG_CRASH
 408         char str[1024];
 409         snprintf(str, sizeof(str),
 410             "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n"
 411             "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n",
 412                 cubic1[0].fX, cubic1[0].fY,  cubic1[1].fX, cubic1[1].fY, cubic1[2].fX, cubic1[2].fY,
 413                 cubic1[3].fX, cubic1[3].fY,
 414                 cubic2[0].fX, cubic2[0].fY,  cubic2[1].fX, cubic2[1].fY, cubic2[2].fX, cubic2[2].fY,
 415                 cubic2[3].fX, cubic2[3].fY);
 416     #endif
 417         SkDRect rect1, rect2;
 418         rect1.setBounds(cubic1);
 419         rect2.setBounds(cubic2);
 420         bool boundsIntersect = rect1.fLeft <= rect2.fRight && rect2.fLeft <= rect2.fRight
 421                 && rect1.fTop <= rect2.fBottom && rect2.fTop <= rect1.fBottom;
 422         if (test == -1) {
 423             SkDebugf("ready...\n");
 424         }
 425         SkIntersections intersections2;
 426         int newIntersects = intersections2.intersect(cubic1, cubic2);
 427         if (!boundsIntersect && newIntersects) {
 428     #if DEBUG_CRASH
 429             SkDebugf("%s %d unexpected intersection boundsIntersect=%d "
 430                     " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsIntersect,
 431                     newIntersects, __FUNCTION__, str);
 432     #endif
 433             REPORTER_ASSERT(reporter, 0);
 434         }
 435         for (int pt = 0; pt < intersections2.used(); ++pt) {
 436             double tt1 = intersections2[0][pt];
 437             SkDPoint xy1 = cubic1.ptAtT(tt1);
 438             double tt2 = intersections2[1][pt];
 439             SkDPoint xy2 = cubic2.ptAtT(tt2);
 440             REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
 441         }
 442         reporter->bumpTestCount();
 443     }
 444 }
 445
 446 static void intersectionFinder(int index0, int index1, double t1Seed, double t2Seed,
 447         double t1Step, double t2Step) {
 448     const SkDCubic& cubic1 = newTestSet[index0];
 449     const SkDCubic& cubic2 = newTestSet[index1];
 450     SkDPoint t1[3], t2[3];
 451     bool toggle = true;
 452     do {
 453         t1[0] = cubic1.ptAtT(t1Seed - t1Step);
 454         t1[1] = cubic1.ptAtT(t1Seed);
 455         t1[2] = cubic1.ptAtT(t1Seed + t1Step);
 456         t2[0] = cubic2.ptAtT(t2Seed - t2Step);
 457         t2[1] = cubic2.ptAtT(t2Seed);
 458         t2[2] = cubic2.ptAtT(t2Seed + t2Step);
 459         double dist[3][3];
 460         dist[1][1] = t1[1].distance(t2[1]);
 461         int best_i = 1, best_j = 1;
 462         for (int i = 0; i < 3; ++i) {
 463             for (int j = 0; j < 3; ++j) {
 464                 if (i == 1 && j == 1) {
 465                     continue;
 466                 }
 467                 dist[i][j] = t1[i].distance(t2[j]);
 468                 if (dist[best_i][best_j] > dist[i][j]) {
 469                     best_i = i;
 470                     best_j = j;
 471                 }
 472             }
 473         }
 474         if (best_i == 0) {
 475             t1Seed -= t1Step;
 476         } else if (best_i == 2) {
 477             t1Seed += t1Step;
 478         }
 479         if (best_j == 0) {
 480             t2Seed -= t2Step;
 481         } else if (best_j == 2) {
 482             t2Seed += t2Step;
 483         }
 484         if (best_i == 1 && best_j == 1) {
 485             if ((toggle ^= true)) {
 486                 t1Step /= 2;
 487             } else {
 488                 t2Step /= 2;
 489             }
 490         }
 491     } while (!t1[1].approximatelyEqual(t2[1]));
 492     t1Step = t2Step = 0.1;
 493     double t10 = t1Seed - t1Step * 2;
 494     double t12 = t1Seed + t1Step * 2;
 495     double t20 = t2Seed - t2Step * 2;
 496     double t22 = t2Seed + t2Step * 2;
 497     SkDPoint test;
 498     while (!approximately_zero(t1Step)) {
 499         test = cubic1.ptAtT(t10);
 500         t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step;
 501         t1Step /= 2;
 502     }
 503     t1Step = 0.1;
 504     while (!approximately_zero(t1Step)) {
 505         test = cubic1.ptAtT(t12);
 506         t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step;
 507         t1Step /= 2;
 508     }
 509     while (!approximately_zero(t2Step)) {
 510         test = cubic2.ptAtT(t20);
 511         t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step;
 512         t2Step /= 2;
 513     }
 514     t2Step = 0.1;
 515     while (!approximately_zero(t2Step)) {
 516         test = cubic2.ptAtT(t22);
 517         t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step;
 518         t2Step /= 2;
 519     }
 520 #if ONE_OFF_DEBUG
 521     SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__,
 522         t10, t1Seed, t12, t20, t2Seed, t22);
 523     SkDPoint p10 = cubic1.ptAtT(t10);
 524     SkDPoint p1Seed = cubic1.ptAtT(t1Seed);
 525     SkDPoint p12 = cubic1.ptAtT(t12);
 526     SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
 527         p10.fX, p10.fY, p1Seed.fX, p1Seed.fY, p12.fX, p12.fY);
 528     SkDPoint p20 = cubic2.ptAtT(t20);
 529     SkDPoint p2Seed = cubic2.ptAtT(t2Seed);
 530     SkDPoint p22 = cubic2.ptAtT(t22);
 531     SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
 532         p20.fX, p20.fY, p2Seed.fX, p2Seed.fY, p22.fX, p22.fY);
 533 #endif
 534 }
 535
 536 static void CubicIntersection_IntersectionFinder() {
 537 //   double t1Seed = 0.87;
 538 //   double t2Seed = 0.87;
 539     double t1Step = 0.000001;
 540     double t2Step = 0.000001;
 541     intersectionFinder(0, 1, 0.855895664, 0.864850875, t1Step, t2Step);
 542     intersectionFinder(0, 1, 0.865207906, 0.865207887, t1Step, t2Step);
 543     intersectionFinder(0, 1, 0.865213351, 0.865208087, t1Step, t2Step);
 544 }
 545
 546 static const SkDCubic selfSet[] = {
 547     {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}},
 548     {{{3, 6}, {2, 3}, {4, 0}, {3, 2}}},
 549     {{{0, 2}, {2, 3}, {5, 1}, {3, 2}}},
 550     {{{0, 2}, {3, 5}, {5, 0}, {4, 2}}},
 551     {{{3.34, 8.98}, {1.95, 10.27}, {3.76, 7.65}, {4.96, 10.64}}},
 552     {{{3.13, 2.74}, {1.08, 4.62}, {3.71, 0.94}, {2.01, 3.81}}},
 553     {{{6.71, 3.14}, {7.99, 2.75}, {8.27, 1.96}, {6.35, 3.57}}},
 554     {{{12.81, 7.27}, {7.22, 6.98}, {12.49, 8.97}, {11.42, 6.18}}},
 555 };
 556
 557 int selfSetCount = (int) SK_ARRAY_COUNT(selfSet);
 558
 559 static void selfOneOff(skiatest::Reporter* reporter, int index) {
 560     const SkDCubic& cubic = selfSet[index];
 561 #if ONE_OFF_DEBUG
 562     int idx2;
 563     double max[3];
 564     int ts = cubic.findMaxCurvature(max);
 565     for (idx2 = 0; idx2 < ts; ++idx2) {
 566         SkDebugf("%s max[%d]=%1.9g (%1.9g, %1.9g)\n", __FUNCTION__, idx2,
 567                 max[idx2], cubic.ptAtT(max[idx2]).fX, cubic.ptAtT(max[idx2]).fY);
 568     }
 569     SkTArray<double, true> ts1;
 570     SkTArray<SkDQuad, true> quads1;
 571     cubic.toQuadraticTs(cubic.calcPrecision(), &ts1);
 572     for (idx2 = 0; idx2 < ts1.count(); ++idx2) {
 573         SkDebugf("%s t[%d]=%1.9g\n", __FUNCTION__, idx2, ts1[idx2]);
 574     }
 575     CubicToQuads(cubic, cubic.calcPrecision(), quads1);
 576     for (idx2 = 0; idx2 < quads1.count(); ++idx2) {
 577         const SkDQuad& q = quads1[idx2];
 578         SkDebugf("  {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n",
 579                 q[0].fX, q[0].fY,  q[1].fX, q[1].fY,  q[2].fX, q[2].fY);
 580     }
 581     SkDebugf("\n");
 582 #endif
 583     SkIntersections i;
 584     int result = i.intersect(cubic);
 585     REPORTER_ASSERT(reporter, result == 1);
 586     REPORTER_ASSERT(reporter, i.used() == 1);
 587     REPORTER_ASSERT(reporter, !approximately_equal(i[0][0], i[1][0]));
 588     SkDPoint pt1 = cubic.ptAtT(i[0][0]);
 589     SkDPoint pt2 = cubic.ptAtT(i[1][0]);
 590     REPORTER_ASSERT(reporter, pt1.approximatelyEqual(pt2));
 591     reporter->bumpTestCount();
 592 }
 593
 594 static void cubicIntersectionSelfTest(skiatest::Reporter* reporter) {
 595     int firstFail = 0;
 596     for (int index = firstFail; index < selfSetCount; ++index) {
 597         selfOneOff(reporter, index);
 598     }
 599 }
 600
 601 static const SkDCubic coinSet[] = {
 602     {{{317, 711}, {322.52285766601562, 711}, {327, 715.4771728515625}, {327, 721}}},
 603     {{{324.07107543945312, 713.928955078125}, {324.4051513671875, 714.26300048828125},
 604             {324.71566772460937, 714.62060546875}, {325, 714.9990234375}}},
 605
 606     {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}},
 607     {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}},
 608 };
 609
 610 static int coinSetCount = (int) SK_ARRAY_COUNT(coinSet);
 611
 612 static void coinOneOff(skiatest::Reporter* reporter, int index) {
 613     const SkDCubic& cubic1 = coinSet[index];
 614     const SkDCubic& cubic2 = coinSet[index + 1];
 615     oneOff(reporter, cubic1, cubic2, true);
 616 }
 617
 618 static void cubicIntersectionCoinTest(skiatest::Reporter* reporter) {
 619     int firstFail = 0;
 620     for (int index = firstFail; index < coinSetCount; index += 2) {
 621         coinOneOff(reporter, index);
 622     }
 623 }
 624
 625 DEF_TEST(PathOpsCubicCoinOneOff, reporter) {
 626     coinOneOff(reporter, 0);
 627 }
 628
 629 DEF_TEST(PathOpsCubicIntersectionOneOff, reporter) {
 630     newOneOff(reporter, 0, 1);
 631 }
 632
 633 DEF_TEST(PathOpsCubicSelfOneOff, reporter) {
 634     selfOneOff(reporter, 0);
 635 }
 636
 637 DEF_TEST(PathOpsCubicIntersection, reporter) {
 638     oneOffTests(reporter);
 639     cubicIntersectionSelfTest(reporter);
 640     cubicIntersectionCoinTest(reporter);
 641     standardTestCases(reporter);
 642     if (false) CubicIntersection_IntersectionFinder();
 643     if (false) CubicIntersection_RandTest(reporter);
 644 }