19e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com/* 29e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Copyright 2012 Google Inc. 39e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * 49e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 59e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * found in the LICENSE file. 69e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com */ 7c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com#include "CurveIntersection.h" 88dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com#include "CurveUtilities.h" 9639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com#include "CubicIntersection_TestData.h" 1027accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com#include "Intersection_Tests.h" 11639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com#include "Intersections.h" 12639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com#include "TestUtilities.h" 13639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 14d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#define SHOW_ORIGINAL 1 15d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com 16639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comconst int firstCubicIntersectionTest = 9; 17639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 1845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic void standardTestCases() { 19639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com for (size_t index = firstCubicIntersectionTest; index < tests_count; ++index) { 20639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com const Cubic& cubic1 = tests[index][0]; 21639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com const Cubic& cubic2 = tests[index][1]; 22639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com Cubic reduce1, reduce2; 2347d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com int order1 = reduceOrder(cubic1, reduce1, kReduceOrder_NoQuadraticsAllowed, 2447d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com kReduceOrder_TreatAsFill); 2547d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com int order2 = reduceOrder(cubic2, reduce2, kReduceOrder_NoQuadraticsAllowed, 2647d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com kReduceOrder_TreatAsFill); 27639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (order1 < 4) { 2827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com printf("%s [%d] cubic1 order=%d\n", __FUNCTION__, (int) index, order1); 2927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com continue; 30639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 31639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (order2 < 4) { 3227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com printf("%s [%d] cubic2 order=%d\n", __FUNCTION__, (int) index, order2); 3327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com continue; 34639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 3527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com if (implicit_matches(reduce1, reduce2)) { 3627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com printf("%s [%d] coincident\n", __FUNCTION__, (int) index); 3727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com continue; 3827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com } 3927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com Intersections tIntersections; 40c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com intersect(reduce1, reduce2, tIntersections); 4127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com if (!tIntersections.intersected()) { 4227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com printf("%s [%d] no intersection\n", __FUNCTION__, (int) index); 4327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com continue; 4427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com } 4527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com for (int pt = 0; pt < tIntersections.used(); ++pt) { 4627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com double tt1 = tIntersections.fT[0][pt]; 4727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com double tx1, ty1; 4827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com xy_at_t(cubic1, tt1, tx1, ty1); 4927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com double tt2 = tIntersections.fT[1][pt]; 5027accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com double tx2, ty2; 5127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com xy_at_t(cubic2, tt2, tx2, ty2); 526d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com if (!AlmostEqualUlps(tx1, tx2)) { 5327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com printf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", 5427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2); 5527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com } 566d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com if (!AlmostEqualUlps(ty1, ty2)) { 5727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com printf("%s [%d,%d] y!= t1=%g (%g,%g) t2=%g (%g,%g)\n", 5827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2); 59639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 60639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 61639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 62639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 6373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 6445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic const Cubic testSet[] = { 65ebf95ba28db75212a1313edc947ed68decc30273caryclark@google.com{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306}, {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}, 66ebf95ba28db75212a1313edc947ed68decc30273caryclark@google.com{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826}, {75.3863417, 18.24489}}, 67ebf95ba28db75212a1313edc947ed68decc30273caryclark@google.com 68ebf95ba28db75212a1313edc947ed68decc30273caryclark@google.com{{0, 0}, {0, 1}, {1, 1}, {1, 0}}, 69ebf95ba28db75212a1313edc947ed68decc30273caryclark@google.com{{1, 0}, {0, 0}, {0, 1}, {1, 1}}, 70ebf95ba28db75212a1313edc947ed68decc30273caryclark@google.com 7145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com{{0,1}, {4,5}, {1,0}, {5,3}}, 7245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com{{0,1}, {3,5}, {1,0}, {5,4}}, 739f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com 7445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com{{0, 1}, {1, 6}, {1, 0}, {1, 0}}, 7545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com{{0, 1}, {0, 1}, {1, 0}, {6, 1}}, 7645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com 7745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com{{0,1}, {3,4}, {1,0}, {5,1}}, 7845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com{{0,1}, {1,5}, {1,0}, {4,3}}, 7945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com 8045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com{{0,1}, {1,2}, {1,0}, {6,1}}, 8145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com{{0,1}, {1,6}, {1,0}, {2,1}}, 8245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com 83044679ef8c08e1f01afadf5bc08251fe8597df81skia.committer@gmail.com{{0,1}, {0,5}, {1,0}, {4,0}}, 8445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com{{0,1}, {0,4}, {1,0}, {5,0}}, 8573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 86beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com{{0,1}, {3,4}, {1,0}, {3,0}}, 87beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com{{0,1}, {0,3}, {1,0}, {4,3}}, 88beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com 89beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com{{0, 0}, {1, 2}, {3, 4}, {4, 4}}, 90beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com{{0, 0}, {1, 2}, {3, 4}, {4, 4}}, 91beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com{{4, 4}, {3, 4}, {1, 2}, {0, 0}}, 92beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com 93beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com{{0,1}, {2,3}, {1,0}, {1,0}}, 94beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com{{0,1}, {0,1}, {1,0}, {3,2}}, 95beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com 96beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com{{0,2}, {0,1}, {1,0}, {1,0}}, 97beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com{{0,1}, {0,1}, {2,0}, {1,0}}, 98beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com 99aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com{{0, 1}, {0, 2}, {1, 0}, {1, 0}}, 100aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com{{0, 1}, {0, 1}, {1, 0}, {2, 0}}, 101aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com 102f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com{{0, 1}, {1, 6}, {1, 0}, {2, 0}}, 103f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com{{0, 1}, {0, 2}, {1, 0}, {6, 1}}, 104f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com 105f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com{{0, 1}, {5, 6}, {1, 0}, {1, 0}}, 106f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com{{0, 1}, {0, 1}, {1, 0}, {6, 5}}, 10785ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com 10885ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com{{95.837747722788592, 45.025976907939643}, {16.564570095652982, 0.72959763963222402}, {63.209855865319199, 68.047528419665767}, {57.640240647662544, 59.524565264361243}}, 10985ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com{{51.593891741518817, 38.53849970667553}, {62.34752929878772, 74.924924725166022}, {74.810149322641152, 34.17966562983564}, {29.368398119401373, 94.66719277886078}}, 11085ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com 11185ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com{{39.765160968417838, 33.060396198677083}, {5.1922921581157908, 66.854301452103215}, {31.619281802149157, 25.269248720849514}, {81.541621071073038, 70.025341524754353}}, 11285ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com{{46.078911165743556, 48.259962651999651}, {20.24450549867214, 49.403916182650214}, {0.26325131778756683, 24.46489805563581}, {15.915006546264051, 83.515023059917155}}, 11385ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com 1149f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com{{65.454505973241524, 93.881892270353575}, {45.867360264932437, 92.723972719499827}, {2.1464054482739447, 74.636369140183717}, {33.774068594804994, 40.770872887582925}}, 1159f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com{{72.963387832494163, 95.659300729473728}, {11.809496633619768, 82.209921247423594}, {13.456139067865974, 57.329313623406605}, {36.060621606214262, 70.867335643091849}}, 1169f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com 1179f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com{{32.484981432782945, 75.082940782924624}, {42.467313093350882, 48.131159948246157}, {3.5963115764764657, 43.208665839959245}, {79.442476890721579, 89.709102357602262}}, 1189f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com{{18.98573861410177, 93.308887208490106}, {40.405250173250792, 91.039661826118675}, {8.0467721950480584, 42.100282172719147}, {40.883324221187891, 26.030185504830527}}, 1199f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com 1209f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com{{7.5374809128872498, 82.441702896003477}, {22.444346930107265, 22.138854312775123}, {66.76091829629658, 50.753805856571446}, {78.193478508942519, 97.7932997968948}}, 1219f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com{{97.700573130371311, 53.53260215070685}, {87.72443481149358, 84.575876772671876}, {19.215031396232092, 47.032676472809484}, {11.989686410869325, 10.659507480757082}}, 1229f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com 1239f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com{{26.192053931854691, 9.8504326817814416}, {10.174241480498686, 98.476562741434464}, {21.177712558385782, 33.814968789841501}, {75.329030899018534, 55.02231980442177}}, 1249f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com{{56.222082700683771, 24.54395039218662}, {95.589995289030483, 81.050822735322086}, {28.180450866082897, 28.837706255185282}, {60.128952916771617, 87.311672180570511}}, 1259f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com 1269f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com{{42.449716172390481, 52.379709366885805}, {27.896043159019225, 48.797373636065686}, {92.770268299044233, 89.899302036454571}, {12.102066544863426, 99.43241951960718}}, 1279f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com{{45.77532924980639, 45.958701495993274}, {37.458701356062065, 68.393691335056758}, {37.569326692060258, 27.673713456687381}, {60.674866037757539, 62.47349659096146}}, 1289f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com 12973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306}, {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}, 13073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com{{61.336508189019057, 82.693132843213675}, {44.639380902349664, 54.074825790745592}, {16.815615499771951, 20.049704667203923}, {41.866884958868326, 56.735503699973002}}, 13173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 13273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826}, {75.3863417, 18.24489}}, 13373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com{{61.3365082, 82.6931328}, {44.6393809, 54.0748258}, {16.8156155, 20.0497047}, {41.866885, 56.7355037}}, 13473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 13573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com{{18.1312339, 31.6473732}, {95.5711034, 63.5350219}, {92.3283165, 62.0158945}, {18.5656052, 32.1268808}}, 13673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com{{97.402018, 35.7169972}, {33.1127443, 25.8935163}, {1.13970027, 54.9424981}, {56.4860195, 60.529264}}, 13773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com}; 13873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 13973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comconst size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]); 14073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 14147d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.comstatic const Cubic newTestSet[] = { 142996d78b7cf9863a5b574fc1b64b1715cad4d0a23caryclark@google.com{{1,3}, {5,6}, {5,3}, {5,4}}, 143996d78b7cf9863a5b574fc1b64b1715cad4d0a23caryclark@google.com{{3,5}, {4,5}, {3,1}, {6,5}}, 144996d78b7cf9863a5b574fc1b64b1715cad4d0a23caryclark@google.com 1451304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{0,5}, {0,5}, {5,4}, {6,4}}, 1461304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{4,5}, {4,6}, {5,0}, {5,0}}, 1471304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com 1481304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{0,4}, {1,3}, {5,4}, {4,2}}, 1491304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{4,5}, {2,4}, {4,0}, {3,1}}, 1501304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com 1511304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{0,2}, {1,5}, {3,2}, {4,1}}, 1521304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{2,3}, {1,4}, {2,0}, {5,1}}, 1531304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com 1541304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{0,2}, {2,3}, {5,1}, {3,2}}, 1551304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{1,5}, {2,3}, {2,0}, {3,2}}, 1561304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com 1571304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{2,6}, {4,5}, {1,0}, {6,1}}, 1581304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{0,1}, {1,6}, {6,2}, {5,4}}, 1591304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com 1601304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{0,1}, {1,2}, {6,5}, {5,4}}, 1611304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{5,6}, {4,5}, {1,0}, {2,1}}, 1621304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com 1631304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{2.5119999999999996, 1.5710000000000002}, {2.6399999999999983, 1.6599999999999997}, {2.8000000000000007, 1.8000000000000003}, {3, 2}}, 1641304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{2.4181876227114887, 1.9849772580462195}, {2.8269904869227211, 2.009330650246834}, {3.2004679292461624, 1.9942047174679169}, {3.4986199496818058, 2.0035994597094731}}, 1651304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com 1661304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{2,3}, {1,4}, {1,0}, {6,0}}, 1671304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com{{0,1}, {0,6}, {3,2}, {4,1}}, 1681304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com 169d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com{{0,2}, {1,5}, {1,0}, {6,1}}, 170d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com{{0,1}, {1,6}, {2,0}, {5,1}}, 171d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com 172d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com{{0,1}, {1,5}, {2,1}, {4,0}}, 173d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com{{1,2}, {0,4}, {1,0}, {5,1}}, 174d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com 1754aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com{{0,1}, {3,5}, {2,1}, {3,1}}, 1764aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com{{1,2}, {1,3}, {1,0}, {5,3}}, 1774aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com 178631cdcb4a6b926b6447f328b81911a4499fb3698skia.committer@gmail.com{{0,1}, {2,5}, {6,0}, {5,3}}, 1797ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com{{0,6}, {3,5}, {1,0}, {5,2}}, 1807ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com 181c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com{{0,1}, {3,6}, {1,0}, {5,2}}, 182c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com{{0,1}, {2,5}, {1,0}, {6,3}}, 183c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com 1845e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com{{1,2},{5,6},{1,0},{1,0}}, 1855e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com{{0,1},{0,1},{2,1},{6,5}}, 1865e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com 187d454ec135eeef48edea7ebc47a61ff39bd654576skia.committer@gmail.com{{0,6},{1,2},{1,0},{1,0}}, 1885e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com{{0,1},{0,1},{6,0},{2,1}}, 1895e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com 19047d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com{{0,2},{0,1},{3,0},{1,0}}, 19147d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com{{0,3},{0,1},{2,0},{1,0}}, 19247d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com}; 19347d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com 19447d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.comconst size_t newTestSetCount = sizeof(newTestSet) / sizeof(newTestSet[0]); 19547d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com 1964aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com#if 0 19745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic void oneOff(const Cubic& cubic1, const Cubic& cubic2) { 19845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkTDArray<Quadratic> quads1; 19945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com cubic_to_quadratics(cubic1, calcPrecision(cubic1), quads1); 200d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#if SHOW_ORIGINAL 201d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com SkDebugf("computed quadratics given\n"); 202d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}, {%1.9g,%1.9g}},\n", 203d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com cubic1[0].x, cubic1[0].y, cubic1[1].x, cubic1[1].y, 204d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com cubic1[2].x, cubic1[2].y, cubic1[3].x, cubic1[3].y)); 205d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}, {%1.9g,%1.9g}},\n", 206d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com cubic2[0].x, cubic2[0].y, cubic2[1].x, cubic2[1].y, 207d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com cubic2[2].x, cubic2[2].y, cubic2[3].x, cubic2[3].y)); 208d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com#endif 2099f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com#if ONE_OFF_DEBUG 2101304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com SkDebugf("computed quadratics set 1\n"); 21145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (int index = 0; index < quads1.count(); ++index) { 21245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com const Quadratic& q = quads1[index]; 21345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y, 21445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com q[1].x, q[1].y, q[2].x, q[2].y); 21545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 2169f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com#endif 21745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkTDArray<Quadratic> quads2; 21845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com cubic_to_quadratics(cubic2, calcPrecision(cubic2), quads2); 2199f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com#if ONE_OFF_DEBUG 2201304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com SkDebugf("computed quadratics set 2\n"); 22145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (int index = 0; index < quads2.count(); ++index) { 22245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com const Quadratic& q = quads2[index]; 22345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y, 22445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com q[1].x, q[1].y, q[2].x, q[2].y); 22545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 2269f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com#endif 22745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com Intersections intersections2, intersections3; 22845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersect2(cubic1, cubic2, intersections2); 22945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersect3(cubic1, cubic2, intersections3); 23045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com int pt1, pt2, pt3; 23145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com bool found; 23245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double tt1, tt2, last = -1; 23345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point xy1, xy2; 23445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (pt1 = 0; pt1 < intersections2.used(); ++pt1) { 23545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com tt1 = intersections2.fT[0][pt1]; 23645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkASSERT(!approximately_equal(last, tt1)); 23745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com last = tt1; 23845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com xy_at_t(cubic1, tt1, xy1.x, xy1.y); 23945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com pt2 = intersections2.fFlip ? intersections2.used() - pt1 - 1 : pt1; 24045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com tt2 = intersections2.fT[1][pt2]; 24145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com xy_at_t(cubic2, tt2, xy2.x, xy2.y); 24245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com#if ONE_OFF_DEBUG 24345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", 24445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com __FUNCTION__, tt1, xy1.x, xy1.y, intersections2.fPt[pt1].x, 24545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersections2.fPt[pt1].y, xy2.x, xy2.y, tt2); 24645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com#endif 24745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkASSERT(xy1.approximatelyEqual(xy2)); 24845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com#if SK_DEBUG 24945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com found = false; 25045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (pt3 = 0; pt3 < intersections3.used(); ++pt3) { 25145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (roughly_equal(tt1, intersections3.fT[0][pt3])) { 25245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com found = true; 25345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com break; 25445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 25545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 25645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkASSERT(found); 25745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com#endif 25845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 25945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com last = -1; 26045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (pt3 = 0; pt3 < intersections3.used(); ++pt3) { 26145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com found = false; 26245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double tt3 = intersections3.fT[0][pt3]; 26345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkASSERT(!approximately_equal(last, tt3)); 26445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com last = tt3; 26545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (pt1 = 0; pt1 < intersections2.used(); ++pt1) { 26645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (approximately_equal(tt3, intersections2.fT[0][pt1])) { 26745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com found = true; 26845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com break; 26945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 27045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 27145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (!found) { 27245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com tt1 = intersections3.fT[0][pt3]; 27345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com xy_at_t(cubic1, tt1, xy1.x, xy1.y); 27445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com pt2 = intersections3.fFlip ? intersections3.used() - pt3 - 1 : pt3; 27545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com tt2 = intersections3.fT[1][pt2]; 27645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com xy_at_t(cubic2, tt2, xy2.x, xy2.y); 27745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com #if ONE_OFF_DEBUG 2784aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", 27945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com __FUNCTION__, tt1, xy1.x, xy1.y, intersections3.fPt[pt1].x, 28045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersections3.fPt[pt1].y, xy2.x, xy2.y, tt2); 28145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com #endif 28245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkASSERT(xy1.approximatelyEqual(xy2)); 28345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkDebugf("%s missing in intersect2\n", __FUNCTION__); 28473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 28573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 28673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 2874aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com#endif 28873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 28945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic void oneOff3(const Cubic& cubic1, const Cubic& cubic2) { 2901304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com#if ONE_OFF_DEBUG 2911304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com SkDebugf("computed quadratics given\n"); 2921304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", 2931304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com cubic1[0].x, cubic1[0].y, cubic1[1].x, cubic1[1].y, 2941304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com cubic1[2].x, cubic1[2].y, cubic1[3].x, cubic1[3].y); 2951304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", 2961304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com cubic2[0].x, cubic2[0].y, cubic2[1].x, cubic2[1].y, 2971304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com cubic2[2].x, cubic2[2].y, cubic2[3].x, cubic2[3].y); 2981304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com#endif 29945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkTDArray<Quadratic> quads1; 30045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com cubic_to_quadratics(cubic1, calcPrecision(cubic1), quads1); 30145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com#if ONE_OFF_DEBUG 3021304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com SkDebugf("computed quadratics set 1\n"); 30345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (int index = 0; index < quads1.count(); ++index) { 30445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com const Quadratic& q = quads1[index]; 30545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y, 30645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com q[1].x, q[1].y, q[2].x, q[2].y); 30745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 30845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com#endif 30945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkTDArray<Quadratic> quads2; 31045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com cubic_to_quadratics(cubic2, calcPrecision(cubic2), quads2); 31145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com#if ONE_OFF_DEBUG 3121304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com SkDebugf("computed quadratics set 2\n"); 31345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (int index = 0; index < quads2.count(); ++index) { 31445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com const Quadratic& q = quads2[index]; 31545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y, 31645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com q[1].x, q[1].y, q[2].x, q[2].y); 31745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 31845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com#endif 31945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com Intersections intersections3; 32045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersect3(cubic1, cubic2, intersections3); 32145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com int pt2, pt3; 32245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double tt1, tt2, last = -1; 32345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point xy1, xy2; 32445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (pt3 = 0; pt3 < intersections3.used(); ++pt3) { 32545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double tt3 = intersections3.fT[0][pt3]; 3261304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com // SkASSERT(!approximately_equal(last, tt3)); 32745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com last = tt3; 32845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com tt1 = intersections3.fT[0][pt3]; 32945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com xy_at_t(cubic1, tt1, xy1.x, xy1.y); 33045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com pt2 = intersections3.fFlip ? intersections3.used() - pt3 - 1 : pt3; 33145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com tt2 = intersections3.fT[1][pt2]; 33245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com xy_at_t(cubic2, tt2, xy2.x, xy2.y); 33345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com#if ONE_OFF_DEBUG 3344aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", 33545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com __FUNCTION__, tt1, xy1.x, xy1.y, intersections3.fPt[pt3].x, 33645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersections3.fPt[pt3].y, xy2.x, xy2.y, tt2); 33745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com#endif 33845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkASSERT(xy1.approximatelyEqual(xy2)); 33945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 34045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com} 34145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com 3424aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com#if 0 34345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic int fails[][2] = { {0, 23}, // fails in intersect2 recursing 34445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com {2, 7}, // answers differ, but neither is correct ('3' is closer) 34545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com {3, 26}, // fails in intersect2 recursing 34645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com {4, 9}, // fails in intersect2 recursing 34745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com {4, 10}, // fails in intersect2 recursing 34845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com {10, 17}, // fails in intersect2 recursing 34945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com {12, 14}, // loops indefinitely 35045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com {12, 21}, // fails in intersect2 recursing 35145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com {13, 21}, // fails in intersect2 recursing 35245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com {14, 21}, // fails in intersect2 recursing 35345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com {17, 25}, // fails in intersect2 recursing 35445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com {23, 25}, // fails in intersect2 recursing 35545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com}; 35645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com 35745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic int failCount = sizeof(fails) / sizeof(fails[0]); 3584aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com#endif 35945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com 36045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic void oneOff(int outer, int inner) { 36145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com const Cubic& cubic1 = testSet[outer]; 36245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com const Cubic& cubic2 = testSet[inner]; 3634aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com#if 0 36445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com bool failing = false; 36545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (int i = 0; i < failCount; ++i) { 36645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if ((fails[i][0] == outer && fails[i][1] == inner) 36745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com || (fails[i][1] == outer && fails[i][0] == inner)) { 36845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com failing = true; 36945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com break; 37045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 37145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 37245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (!failing) { 37345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com oneOff(cubic1, cubic2); 37445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } else { 3754aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com#endif 37645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com oneOff3(cubic1, cubic2); 3774aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com// } 37845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com} 37945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com 38045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comvoid CubicIntersection_OneOffTest() { 381ebf95ba28db75212a1313edc947ed68decc30273caryclark@google.com oneOff(0, 1); 38245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com} 38345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com 38447d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.comstatic void newOneOff(int outer, int inner) { 38547d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com const Cubic& cubic1 = newTestSet[outer]; 38647d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com const Cubic& cubic2 = newTestSet[inner]; 38747d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com oneOff3(cubic1, cubic2); 38847d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com} 38947d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com 39047d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.comvoid CubicIntersection_NewOneOffTest() { 39147d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com newOneOff(0, 1); 39247d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com} 39347d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com 39445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic void oneOffTests() { 39545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (size_t outer = 0; outer < testSetCount - 1; ++outer) { 39645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (size_t inner = outer + 1; inner < testSetCount; ++inner) { 39745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com oneOff(outer, inner); 39845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 39945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 40045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com} 40145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com 40245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comvoid CubicIntersection_OneOffTests() { 40345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com oneOffTests(); 40445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com} 40545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com 406f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com#define DEBUG_CRASH 0 40773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 40873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comclass CubicChopper { 40973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.compublic: 41073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 41173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com// only finds one intersection 41273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comCubicChopper(const Cubic& c1, const Cubic& c2) 41373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com : cubic1(c1) 41473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com , cubic2(c2) 41573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com , depth(0) { 41673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 41773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 41873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.combool intersect(double minT1, double maxT1, double minT2, double maxT2) { 41973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com Cubic sub1, sub2; 42073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com // FIXME: carry last subdivide and reduceOrder result with cubic 42173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com sub_divide(cubic1, minT1, maxT1, sub1); 42273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com sub_divide(cubic2, minT2, maxT2, sub2); 42373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com Intersections i; 4244aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com intersect3(sub1, sub2, i); 42573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (i.used() == 0) { 42673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return false; 42773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 42873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double x1, y1, x2, y2; 42973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com t1 = minT1 + i.fT[0][0] * (maxT1 - minT1); 43073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com t2 = minT2 + i.fT[1][0] * (maxT2 - minT2); 43173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com xy_at_t(cubic1, t1, x1, y1); 43273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com xy_at_t(cubic2, t2, x2, y2); 43373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (AlmostEqualUlps(x1, x2) && AlmostEqualUlps(y1, y2)) { 43473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return true; 43573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 43673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double half1 = (minT1 + maxT1) / 2; 43773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double half2 = (minT2 + maxT2) / 2; 43873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com ++depth; 43973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com bool result; 44073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (depth & 1) { 44173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com result = intersect(minT1, half1, minT2, maxT2) || intersect(half1, maxT1, minT2, maxT2) 44273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com || intersect(minT1, maxT1, minT2, half2) || intersect(minT1, maxT1, half2, maxT2); 44373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } else { 44473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com result = intersect(minT1, maxT1, minT2, half2) || intersect(minT1, maxT1, half2, maxT2) 44573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com || intersect(minT1, half1, minT2, maxT2) || intersect(half1, maxT1, minT2, maxT2); 44673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 44773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com --depth; 44873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return result; 44973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 45073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 45173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comconst Cubic& cubic1; 45273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comconst Cubic& cubic2; 45373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comdouble t1; 45473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comdouble t2; 45573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comint depth; 45673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com}; 45773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 45873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com#define TRY_OLD 0 // old way fails on test == 1 45973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 46005c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.comvoid CubicIntersection_RandTestOld() { 46173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com srand(0); 46273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com const int tests = 1000000; // 10000000; 46373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double largestFactor = DBL_MAX; 46473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int test = 0; test < tests; ++test) { 46573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com Cubic cubic1, cubic2; 46673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int i = 0; i < 4; ++i) { 46773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com cubic1[i].x = (double) rand() / RAND_MAX * 100; 46873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com cubic1[i].y = (double) rand() / RAND_MAX * 100; 46973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com cubic2[i].x = (double) rand() / RAND_MAX * 100; 47073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com cubic2[i].y = (double) rand() / RAND_MAX * 100; 47173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 47273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (test == 2513) { // the pair crosses three times, but the quadratic approximation 47373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com continue; // only sees one -- should be OK to ignore the other two? 47473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 47573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (test == 12932) { // this exposes a weakness when one cubic touches the other but 47673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com continue; // does not touch the quad approximation. Captured in qc.htm as cubic15 47773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 47873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com #if DEBUG_CRASH 47973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com char str[1024]; 48073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com sprintf(str, "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n" 48173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n", 48273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com cubic1[0].x, cubic1[0].y, cubic1[1].x, cubic1[1].y, cubic1[2].x, cubic1[2].y, 48373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com cubic1[3].x, cubic1[3].y, 48473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com cubic2[0].x, cubic2[0].y, cubic2[1].x, cubic2[1].y, cubic2[2].x, cubic2[2].y, 48573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com cubic2[3].x, cubic2[3].y); 48673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com #endif 48773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com _Rect rect1, rect2; 48873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com rect1.setBounds(cubic1); 48973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com rect2.setBounds(cubic2); 49073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com bool boundsIntersect = rect1.left <= rect2.right && rect2.left <= rect2.right 49173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com && rect1.top <= rect2.bottom && rect2.top <= rect1.bottom; 49273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com Intersections i1, i2; 49373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com #if TRY_OLD 49473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com bool oldIntersects = intersect(cubic1, cubic2, i1); 49573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com #else 49673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com bool oldIntersects = false; 49773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com #endif 49873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (test == -1) { 49973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com SkDebugf("ready...\n"); 50073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 5014aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com bool newIntersects = intersect3(cubic1, cubic2, i2); 50273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (!boundsIntersect && (oldIntersects || newIntersects)) { 503f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com #if DEBUG_CRASH 50473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com SkDebugf("%s %d unexpected intersection boundsIntersect=%d oldIntersects=%d" 50573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsIntersect, 50673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com oldIntersects, newIntersects, __FUNCTION__, str); 507f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com #endif 508aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkASSERT(0); 50973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 51073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (oldIntersects && !newIntersects) { 511f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com #if DEBUG_CRASH 51273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com SkDebugf("%s %d missing intersection oldIntersects=%d newIntersects=%d\n%s %s\n", 51373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com __FUNCTION__, test, oldIntersects, newIntersects, __FUNCTION__, str); 514f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com #endif 515aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkASSERT(0); 51673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 51773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (!oldIntersects && !newIntersects) { 51873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com continue; 51973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 52073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (i2.used() > 1) { 52173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com continue; 52273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com // just look at single intercepts for simplicity 52373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 52473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com Intersections self1, self2; // self-intersect checks 52573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (intersect(cubic1, self1)) { 52673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com continue; 52773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 52873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (intersect(cubic2, self2)) { 52973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com continue; 53073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 53173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com // binary search for range necessary to enclose real intersection 53273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com CubicChopper c(cubic1, cubic2); 53373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com bool result = c.intersect(0, 1, 0, 1); 53473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (!result) { 53573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com // FIXME: a failure here probably means that a core routine used by CubicChopper is failing 53673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com continue; 53773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 53873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double delta1 = fabs(c.t1 - i2.fT[0][0]); 53973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double delta2 = fabs(c.t2 - i2.fT[1][0]); 54073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double calc1 = calcPrecision(cubic1); 54173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double calc2 = calcPrecision(cubic2); 54273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double factor1 = calc1 / delta1; 54373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double factor2 = calc2 / delta2; 54473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com SkDebugf("%s %d calc1=%1.9g delta1=%1.9g factor1=%1.9g calc2=%1.9g delta2=%1.9g" 54573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com " factor2=%1.9g\n", __FUNCTION__, test, 54673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com calc1, delta1, factor1, calc2, delta2, factor2); 54773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (factor1 < largestFactor) { 54873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com SkDebugf("WE HAVE A WINNER! %1.9g\n", factor1); 549f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com #if DEBUG_CRASH 55073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com SkDebugf("%s\n", str); 551f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com #endif 5524aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com oneOff3(cubic1, cubic2); 55373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com largestFactor = factor1; 55473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 55573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (factor2 < largestFactor) { 55673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com SkDebugf("WE HAVE A WINNER! %1.9g\n", factor2); 557f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com #if DEBUG_CRASH 55873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com SkDebugf("%s\n", str); 559f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com #endif 5604aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com oneOff3(cubic1, cubic2); 56173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com largestFactor = factor2; 56273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 56373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 56473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 56505c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com 56605c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.comvoid CubicIntersection_RandTest() { 56705c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com srand(0); 56885ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com const int tests = 10000000; 56905c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com for (int test = 0; test < tests; ++test) { 57005c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com Cubic cubic1, cubic2; 57105c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com for (int i = 0; i < 4; ++i) { 57205c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com cubic1[i].x = (double) rand() / RAND_MAX * 100; 57305c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com cubic1[i].y = (double) rand() / RAND_MAX * 100; 57405c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com cubic2[i].x = (double) rand() / RAND_MAX * 100; 57505c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com cubic2[i].y = (double) rand() / RAND_MAX * 100; 57605c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com } 57705c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com #if DEBUG_CRASH 57805c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com char str[1024]; 57905c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com sprintf(str, "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n" 58005c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n", 58105c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com cubic1[0].x, cubic1[0].y, cubic1[1].x, cubic1[1].y, cubic1[2].x, cubic1[2].y, 58205c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com cubic1[3].x, cubic1[3].y, 58305c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com cubic2[0].x, cubic2[0].y, cubic2[1].x, cubic2[1].y, cubic2[2].x, cubic2[2].y, 58405c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com cubic2[3].x, cubic2[3].y); 58505c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com #endif 58605c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com _Rect rect1, rect2; 58705c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com rect1.setBounds(cubic1); 58805c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com rect2.setBounds(cubic2); 58905c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com bool boundsIntersect = rect1.left <= rect2.right && rect2.left <= rect2.right 59005c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com && rect1.top <= rect2.bottom && rect2.top <= rect1.bottom; 59105c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com if (test == -1) { 59205c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com SkDebugf("ready...\n"); 59305c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com } 59405c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com Intersections intersections2; 5954aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com bool newIntersects = intersect3(cubic1, cubic2, intersections2); 59605c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com if (!boundsIntersect && newIntersects) { 597f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com #if DEBUG_CRASH 59805c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com SkDebugf("%s %d unexpected intersection boundsIntersect=%d " 59905c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsIntersect, 60005c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com newIntersects, __FUNCTION__, str); 601f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com #endif 602aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkASSERT(0); 60305c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com } 60405c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com for (int pt = 0; pt < intersections2.used(); ++pt) { 60505c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com double tt1 = intersections2.fT[0][pt]; 60605c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com _Point xy1, xy2; 60705c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com xy_at_t(cubic1, tt1, xy1.x, xy1.y); 60805c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com int pt2 = intersections2.fFlip ? intersections2.used() - pt - 1 : pt; 60905c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com double tt2 = intersections2.fT[1][pt2]; 61005c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com xy_at_t(cubic2, tt2, xy2.x, xy2.y); 6119f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com #if 0 61205c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", __FUNCTION__, 61305c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com tt1, xy1.x, xy1.y, xy2.x, xy2.y, tt2); 6149f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com #endif 615aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkASSERT(xy1.approximatelyEqual(xy2)); 61605c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com } 61705c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com } 61805c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com} 6199f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com 620d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.comstatic void intersectionFinder(int index0, int index1, double t1Seed, double t2Seed, 621d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com double t1Step, double t2Step) { 622d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com const Cubic& cubic1 = newTestSet[index0]; 623d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com const Cubic& cubic2 = newTestSet[index1]; 624f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com _Point t1[3], t2[3]; 625f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com bool toggle = true; 626f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com do { 627f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com xy_at_t(cubic1, t1Seed - t1Step, t1[0].x, t1[0].y); 628f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com xy_at_t(cubic1, t1Seed, t1[1].x, t1[1].y); 629f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com xy_at_t(cubic1, t1Seed + t1Step, t1[2].x, t1[2].y); 630f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com xy_at_t(cubic2, t2Seed - t2Step, t2[0].x, t2[0].y); 631f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com xy_at_t(cubic2, t2Seed, t2[1].x, t2[1].y); 632f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com xy_at_t(cubic2, t2Seed + t2Step, t2[2].x, t2[2].y); 633f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com double dist[3][3]; 634f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com dist[1][1] = t1[1].distance(t2[1]); 635f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com int best_i = 1, best_j = 1; 636f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com for (int i = 0; i < 3; ++i) { 637f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com for (int j = 0; j < 3; ++j) { 638f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com if (i == 1 && j == 1) { 639f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com continue; 640f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 641f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com dist[i][j] = t1[i].distance(t2[j]); 642f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com if (dist[best_i][best_j] > dist[i][j]) { 643f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com best_i = i; 644f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com best_j = j; 645f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 646f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 647f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 648f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com if (best_i == 0) { 649f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t1Seed -= t1Step; 650f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } else if (best_i == 2) { 651f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t1Seed += t1Step; 652f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 653f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com if (best_j == 0) { 654f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t2Seed -= t2Step; 655f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } else if (best_j == 2) { 656f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t2Seed += t2Step; 657f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 658f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com if (best_i == 1 && best_j == 1) { 659f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com if ((toggle ^= true)) { 660f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t1Step /= 2; 661f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } else { 662f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t2Step /= 2; 663f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 664f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 665f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } while (!t1[1].approximatelyEqual(t2[1])); 666f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t1Step = t2Step = 0.1; 667f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com double t10 = t1Seed - t1Step * 2; 668f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com double t12 = t1Seed + t1Step * 2; 669f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com double t20 = t2Seed - t2Step * 2; 670f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com double t22 = t2Seed + t2Step * 2; 671f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com _Point test; 672f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com while (!approximately_zero(t1Step)) { 673f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com xy_at_t(cubic1, t10, test.x, test.y); 674f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step; 675f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t1Step /= 2; 676f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 677f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t1Step = 0.1; 678f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com while (!approximately_zero(t1Step)) { 679f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com xy_at_t(cubic1, t12, test.x, test.y); 680f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step; 681f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t1Step /= 2; 682f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 683f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com while (!approximately_zero(t2Step)) { 684f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com xy_at_t(cubic2, t20, test.x, test.y); 685f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step; 686f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t2Step /= 2; 6879f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 688f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t2Step = 0.1; 689f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com while (!approximately_zero(t2Step)) { 690f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com xy_at_t(cubic2, t22, test.x, test.y); 691f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step; 692f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t2Step /= 2; 693f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 694c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com#if ONE_OFF_DEBUG 695f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__, 696f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com t10, t1Seed, t12, t20, t2Seed, t22); 69745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point p10 = xy_at_t(cubic1, t10); 69845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point p1Seed = xy_at_t(cubic1, t1Seed); 69945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point p12 = xy_at_t(cubic1, t12); 70045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, 70145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com p10.x, p10.y, p1Seed.x, p1Seed.y, p12.x, p12.y); 70245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point p20 = xy_at_t(cubic2, t20); 70345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point p2Seed = xy_at_t(cubic2, t2Seed); 70445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point p22 = xy_at_t(cubic2, t22); 70545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, 70645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com p20.x, p20.y, p2Seed.x, p2Seed.y, p22.x, p22.y); 707c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com#endif 708f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com} 709f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com 710d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.comvoid CubicIntersection_IntersectionFinder() { 711d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com 712996d78b7cf9863a5b574fc1b64b1715cad4d0a23caryclark@google.com // double t1Seed = 0.87; 713996d78b7cf9863a5b574fc1b64b1715cad4d0a23caryclark@google.com // double t2Seed = 0.87; 714996d78b7cf9863a5b574fc1b64b1715cad4d0a23caryclark@google.com double t1Step = 0.000001; 715996d78b7cf9863a5b574fc1b64b1715cad4d0a23caryclark@google.com double t2Step = 0.000001; 716996d78b7cf9863a5b574fc1b64b1715cad4d0a23caryclark@google.com intersectionFinder(0, 1, 0.855895664, 0.864850875, t1Step, t2Step); 717996d78b7cf9863a5b574fc1b64b1715cad4d0a23caryclark@google.com intersectionFinder(0, 1, 0.865207906, 0.865207887, t1Step, t2Step); 718996d78b7cf9863a5b574fc1b64b1715cad4d0a23caryclark@google.com intersectionFinder(0, 1, 0.865213351, 0.865208087, t1Step, t2Step); 719d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com} 720d4c8e1e035bc2edb6caf2c9eac71ef918e60b80bcaryclark@google.com 72145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic void coincidentTest() { 722f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com#if 0 723f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com Cubic cubic1 = {{0, 1}, {0, 2}, {1, 0}, {1, 0}}; 724f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com Cubic cubic2 = {{0, 1}, {0, 2}, {1, 0}, {6, 1}}; 72545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com#endif 72645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com} 7270c38ed3b1d704a0ed6147299046f51fd52e841a2skia.committer@gmail.com 728c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.comvoid CubicIntersection_SelfTest() { 729c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com const Cubic selfSet[] = { 7301304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com {{0,2}, {2,3}, {5,1}, {3,2}}, 7311304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com {{0,2}, {3,5}, {5,0}, {4,2}}, 732c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com {{3.34,8.98}, {1.95,10.27}, {3.76,7.65}, {4.96,10.64}}, 733c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com {{3.13,2.74}, {1.08,4.62}, {3.71,0.94}, {2.01,3.81}}, 73458433de8627c54ac2d68c65d248d67f48a79179dskia.committer@gmail.com {{6.71,3.14}, {7.99,2.75}, {8.27,1.96}, {6.35,3.57}}, 735c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com {{12.81,7.27}, {7.22,6.98}, {12.49,8.97}, {11.42,6.18}}, 736c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com }; 737c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com size_t selfSetCount = sizeof(selfSet) / sizeof(selfSet[0]); 738ebf95ba28db75212a1313edc947ed68decc30273caryclark@google.com size_t firstFail = 1; 739ebf95ba28db75212a1313edc947ed68decc30273caryclark@google.com for (size_t index = firstFail; index < selfSetCount; ++index) { 740c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com const Cubic& cubic = selfSet[index]; 741c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com #if ONE_OFF_DEBUG 7421304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com int idx2; 7431304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com double max[3]; 7441304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com int ts = find_cubic_max_curvature(cubic, max); 7451304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com for (idx2 = 0; idx2 < ts; ++idx2) { 7461304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com SkDebugf("%s max[%d]=%1.9g (%1.9g, %1.9g)\n", __FUNCTION__, idx2, 7471304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com max[idx2], xy_at_t(cubic, max[idx2]).x, xy_at_t(cubic, max[idx2]).y); 7481304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com } 7491304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com SkTDArray<double> ts1; 750c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com SkTDArray<Quadratic> quads1; 7511304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com cubic_to_quadratics(cubic, calcPrecision(cubic), ts1); 7521304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com for (idx2 = 0; idx2 < ts1.count(); ++idx2) { 7531304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com SkDebugf("%s t[%d]=%1.9g\n", __FUNCTION__, idx2, ts1[idx2]); 7541304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com } 755c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com cubic_to_quadratics(cubic, calcPrecision(cubic), quads1); 7561304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com for (idx2 = 0; idx2 < quads1.count(); ++idx2) { 7571304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com const Quadratic& q = quads1[idx2]; 75803682beb8c1c5dfe714933e9419e1412b33c932dskia.committer@gmail.com SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", 7591304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com q[0].x, q[0].y, q[1].x, q[1].y, q[2].x, q[2].y); 760c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com } 761c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com SkDebugf("\n"); 762c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com #endif 763c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com Intersections i; 7641304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com SkDEBUGCODE(int result = ) intersect(cubic, i); 765c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com SkASSERT(result == 1); 766c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com SkASSERT(i.used() == 1); 767c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com SkASSERT(!approximately_equal(i.fT[0][0], i.fT[1][0])); 768c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com _Point pt1 = xy_at_t(cubic, i.fT[0][0]); 769c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com _Point pt2 = xy_at_t(cubic, i.fT[1][0]); 770c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com SkASSERT(pt1.approximatelyEqual(pt2)); 771c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com } 772c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com} 773c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.com 77445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comvoid CubicIntersection_Test() { 77545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com oneOffTests(); 77645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com coincidentTest(); 77745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com standardTestCases(); 7789f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com} 779