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