12db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org/* 22db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org * Copyright 2014 Google Inc. 32db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org * 42db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org * Use of this source code is governed by a BSD-style license that can be 52db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org * found in the LICENSE file. 62db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org */ 72db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#include "PathOpsTestCommon.h" 82db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#include "SkIntersections.h" 92db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#include "SkPathOpsCubic.h" 102db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#include "SkPathOpsLine.h" 112db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#include "SkPathOpsQuad.h" 122db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#include "SkRandom.h" 132db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#include "SkReduceOrder.h" 142db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#include "Test.h" 152db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 162db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.orgstatic bool gPathOpsCubicLineIntersectionIdeasVerbose = false; 172db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 182db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.orgstatic struct CubicLineFailures { 192db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDCubic c; 202db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double t; 212db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDPoint p; 222db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org} cubicLineFailures[] = { 232db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org {{{{-164.3726806640625, 36.826904296875}, {-189.045166015625, -953.2220458984375}, 242db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org {926.505859375, -897.36175537109375}, {-139.33489990234375, 204.40771484375}}}, 252db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 0.37329583, {107.54935269006289, -632.13736293162208}}, 262db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org {{{{784.056884765625, -554.8350830078125}, {67.5489501953125, 509.0224609375}, 272db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org {-447.713134765625, 751.375}, {415.7784423828125, 172.22265625}}}, 282db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 0.660005242, {-32.973148967736151, 478.01341797403569}}, 292db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org {{{{-580.6834716796875, -127.044921875}, {-872.8983154296875, -945.54302978515625}, 302db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org {260.8092041015625, -909.34991455078125}, {-976.2125244140625, -18.46551513671875}}}, 312db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 0.578826774, {-390.17910153915489, -687.21144412296007}}, 322db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org}; 332db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 342db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.orgint cubicLineFailuresCount = (int) SK_ARRAY_COUNT(cubicLineFailures); 352db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 362db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.orgdouble measuredSteps[] = { 372db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 9.15910731e-007, 8.6600277e-007, 7.4122059e-007, 6.92087618e-007, 8.35290245e-007, 382db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 3.29763199e-007, 5.07547773e-007, 4.41294224e-007, 0, 0, 392db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 3.76879167e-006, 1.06126249e-006, 2.36873967e-006, 1.62421134e-005, 3.09103599e-005, 402db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 4.38917976e-005, 0.000112348938, 0.000243149242, 0.000433174114, 0.00170880232, 412db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 0.00272619724, 0.00518844604, 0.000352621078, 0.00175960064, 0.027875185, 422db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 0.0351329803, 0.103964925, 432db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org}; 442db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 45b2c82c99f891e4e846e4959c811661bf68fa43d6skia.committer@gmail.com/* last output : errors=3121 462db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 9.1796875e-007 8.59375e-007 7.5e-007 6.875e-007 8.4375e-007 472db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 3.125e-007 5e-007 4.375e-007 0 0 482db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 3.75e-006 1.09375e-006 2.1875e-006 1.640625e-005 3.0859375e-005 492db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 4.38964844e-005 0.000112304687 0.000243164063 0.000433181763 0.00170898437 502db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 0.00272619247 0.00518844604 0.000352621078 0.00175960064 0.027875185 512db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 0.0351329803 0.103964925 522db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org*/ 532db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 542db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.orgstatic double binary_search(const SkDCubic& cubic, double step, const SkDPoint& pt, double t, 552db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org int* iters) { 562db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double firstStep = step; 572db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org do { 582db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org *iters += 1; 592db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDPoint cubicAtT = cubic.ptAtT(t); 602db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (cubicAtT.approximatelyEqual(pt)) { 612db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org break; 622db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 632db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double calcX = cubicAtT.fX - pt.fX; 642db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double calcY = cubicAtT.fY - pt.fY; 652db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double calcDist = calcX * calcX + calcY * calcY; 662db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (step == 0) { 672db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDebugf("binary search failed: step=%1.9g cubic=", firstStep); 682db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org cubic.dump(); 692db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDebugf(" t=%1.9g ", t); 702db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org pt.dump(); 712db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDebugf("\n"); 722db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org return -1; 732db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 742db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double lastStep = step; 752db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org step /= 2; 762db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDPoint lessPt = cubic.ptAtT(t - lastStep); 772db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double lessX = lessPt.fX - pt.fX; 782db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double lessY = lessPt.fY - pt.fY; 792db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double lessDist = lessX * lessX + lessY * lessY; 802db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org // use larger x/y difference to choose step 812db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (calcDist > lessDist) { 822db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org t -= step; 832db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org t = SkTMax(0., t); 842db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } else { 852db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDPoint morePt = cubic.ptAtT(t + lastStep); 862db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double moreX = morePt.fX - pt.fX; 872db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double moreY = morePt.fY - pt.fY; 882db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double moreDist = moreX * moreX + moreY * moreY; 892db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (calcDist <= moreDist) { 902db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org continue; 912db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 922db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org t += step; 932db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org t = SkTMin(1., t); 942db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 952db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } while (true); 962db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org return t; 972db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org} 982db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 992db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#if 0 1002db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.orgstatic bool r2check(double A, double B, double C, double D, double* R2MinusQ3Ptr) { 1012db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (approximately_zero(A) 1022db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org && approximately_zero_when_compared_to(A, B) 1032db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org && approximately_zero_when_compared_to(A, C) 1042db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org && approximately_zero_when_compared_to(A, D)) { // we're just a quadratic 1052db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org return false; 1062db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 1072db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (approximately_zero_when_compared_to(D, A) 1082db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org && approximately_zero_when_compared_to(D, B) 1092db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org && approximately_zero_when_compared_to(D, C)) { // 0 is one root 1102db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org return false; 1112db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 1122db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (approximately_zero(A + B + C + D)) { // 1 is one root 1132db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org return false; 1142db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 1152db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double a, b, c; 1162db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org { 1172db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double invA = 1 / A; 1182db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org a = B * invA; 1192db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org b = C * invA; 1202db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org c = D * invA; 1212db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 1222db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double a2 = a * a; 1232db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double Q = (a2 - b * 3) / 9; 1242db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double R = (2 * a2 * a - 9 * a * b + 27 * c) / 54; 1252db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double R2 = R * R; 1262db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double Q3 = Q * Q * Q; 1272db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double R2MinusQ3 = R2 - Q3; 1282db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org *R2MinusQ3Ptr = R2MinusQ3; 1292db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org return true; 1302db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org} 1312db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#endif 1322db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 1332db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org/* What is the relationship between the accuracy of the root in range and the magnitude of all 1342db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org roots? To find out, create a bunch of cubics, and measure */ 1352db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 1362db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.orgDEF_TEST(PathOpsCubicLineRoots, reporter) { 1372db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (!gPathOpsCubicLineIntersectionIdeasVerbose) { // slow; exclude it by default 1382db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org return; 1392db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 1402db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkRandom ran; 1412db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double worstStep[256] = {0}; 1422db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org int errors = 0; 1432db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org int iters = 0; 1442db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double smallestR2 = 0; 1452db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double largestR2 = 0; 1462db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org for (int index = 0; index < 1000000000; ++index) { 1472db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}; 1482db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDCubic cubic = {{origin, 1492db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}, 1502db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}, 1512db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)} 1522db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org }}; 1532db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org // construct a line at a known intersection 1542db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double t = ran.nextRangeF(0, 1); 1552db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDPoint pt = cubic.ptAtT(t); 1562db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org // skip answers with no intersections (although note the bug!) or two, or more 1572db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org // see if the line / cubic has a fun range of roots 1582db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double A, B, C, D; 1592db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDCubic::Coefficients(&cubic[0].fY, &A, &B, &C, &D); 1602db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org D -= pt.fY; 1612db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double allRoots[3] = {0}, validRoots[3] = {0}; 1622db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org int realRoots = SkDCubic::RootsReal(A, B, C, D, allRoots); 1632db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org int valid = SkDQuad::AddValidTs(allRoots, realRoots, validRoots); 1642db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (valid != 1) { 1652db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org continue; 1662db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 1672db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (realRoots == 1) { 1682db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org continue; 1692db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 1702db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org t = validRoots[0]; 1712db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDPoint calcPt = cubic.ptAtT(t); 1722db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (calcPt.approximatelyEqual(pt)) { 1732db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org continue; 1742db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 1752db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#if 0 1762db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double R2MinusQ3; 1772db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (r2check(A, B, C, D, &R2MinusQ3)) { 1782db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org smallestR2 = SkTMin(smallestR2, R2MinusQ3); 1792db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org largestR2 = SkTMax(largestR2, R2MinusQ3); 1802db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 1812db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#endif 1822db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double largest = SkTMax(fabs(allRoots[0]), fabs(allRoots[1])); 1832db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (realRoots == 3) { 1842db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org largest = SkTMax(largest, fabs(allRoots[2])); 1852db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 1862db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org int largeBits; 1872db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (largest <= 1) { 1882db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#if 0 1892db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDebugf("realRoots=%d (%1.9g, %1.9g, %1.9g) valid=%d (%1.9g, %1.9g, %1.9g)\n", 1902db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org realRoots, allRoots[0], allRoots[1], allRoots[2], valid, validRoots[0], 1912db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org validRoots[1], validRoots[2]); 1922db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#endif 1932db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double smallest = SkTMin(allRoots[0], allRoots[1]); 1942db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (realRoots == 3) { 1952db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org smallest = SkTMin(smallest, allRoots[2]); 1962db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 1972db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SK_ALWAYSBREAK(smallest < 0); 1982db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SK_ALWAYSBREAK(smallest >= -1); 1992db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org largeBits = 0; 2002db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } else { 2012db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org frexp(largest, &largeBits); 2022db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SK_ALWAYSBREAK(largeBits >= 0); 2032db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SK_ALWAYSBREAK(largeBits < 256); 2042db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 2052db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double step = 1e-6; 2062db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (largeBits > 21) { 2072db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org step = 1e-1; 2082db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } else if (largeBits > 18) { 2092db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org step = 1e-2; 2102db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } else if (largeBits > 15) { 2112db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org step = 1e-3; 2122db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } else if (largeBits > 12) { 2132db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org step = 1e-4; 2142db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } else if (largeBits > 9) { 2152db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org step = 1e-5; 2162db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 2172db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double diff; 2182db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org do { 2192db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double newT = binary_search(cubic, step, pt, t, &iters); 2202db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org if (newT >= 0) { 2212db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org diff = fabs(t - newT); 2222db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org break; 2232db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 2242db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org step *= 1.5; 2252db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SK_ALWAYSBREAK(step < 1); 2262db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } while (true); 2272db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org worstStep[largeBits] = SkTMax(worstStep[largeBits], diff); 2282db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#if 0 2292db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org { 2302db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org cubic.dump(); 2312db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDebugf("\n"); 2322db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDLine line = {{{pt.fX - 1, pt.fY}, {pt.fX + 1, pt.fY}}}; 2332db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org line.dump(); 2342db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDebugf("\n"); 2352db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 2362db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org#endif 2372db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org ++errors; 2382db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 2392db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDebugf("errors=%d avgIter=%1.9g", errors, (double) iters / errors); 2402db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDebugf(" steps: "); 2412db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org int worstLimit = SK_ARRAY_COUNT(worstStep); 2422db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org while (worstStep[--worstLimit] == 0) ; 2432db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org for (int idx2 = 0; idx2 <= worstLimit; ++idx2) { 2442db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDebugf("%1.9g ", worstStep[idx2]); 2452db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 2462db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDebugf("\n"); 2472db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDebugf("smallestR2=%1.9g largestR2=%1.9g\n", smallestR2, largestR2); 2482db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org} 2492db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 2502db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.orgstatic double testOneFailure(const CubicLineFailures& failure) { 2512db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org const SkDCubic& cubic = failure.c; 2522db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org const SkDPoint& pt = failure.p; 2532db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double A, B, C, D; 2542db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDCubic::Coefficients(&cubic[0].fY, &A, &B, &C, &D); 2552db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org D -= pt.fY; 2562db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double allRoots[3] = {0}, validRoots[3] = {0}; 2572db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org int realRoots = SkDCubic::RootsReal(A, B, C, D, allRoots); 2582db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org int valid = SkDQuad::AddValidTs(allRoots, realRoots, validRoots); 2592db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SK_ALWAYSBREAK(valid == 1); 2602db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SK_ALWAYSBREAK(realRoots != 1); 2612db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double t = validRoots[0]; 2622db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SkDPoint calcPt = cubic.ptAtT(t); 2632db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SK_ALWAYSBREAK(!calcPt.approximatelyEqual(pt)); 2642db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org int iters = 0; 2652db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double newT = binary_search(cubic, 0.1, pt, t, &iters); 2662db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org return newT; 2672db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org} 2682db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 2692db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.orgDEF_TEST(PathOpsCubicLineFailures, reporter) { 2702db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org return; // disable for now 2712db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org for (int index = 0; index < cubicLineFailuresCount; ++index) { 2722db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org const CubicLineFailures& failure = cubicLineFailures[index]; 2732db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double newT = testOneFailure(failure); 2742db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SK_ALWAYSBREAK(newT >= 0); 2752db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org } 2762db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org} 2772db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 2782db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.orgDEF_TEST(PathOpsCubicLineOneFailure, reporter) { 2792db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org return; // disable for now 2802db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org const CubicLineFailures& failure = cubicLineFailures[1]; 2812db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org double newT = testOneFailure(failure); 2822db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org SK_ALWAYSBREAK(newT >= 0); 2832db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org} 284