1235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com// Another approach is to start with the implicit form of one curve and solve 2235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com// (seek implicit coefficients in QuadraticParameter.cpp 3235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com// by substituting in the parametric form of the other. 4235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com// The downside of this approach is that early rejects are difficult to come by. 5235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com// http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormula.html#step 6235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 7235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com#include "CubicUtilities.h" 9235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com#include "CurveIntersection.h" 10235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com#include "Intersections.h" 11235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com#include "QuadraticParameterization.h" 12235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com#include "QuarticRoot.h" 13235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com#include "QuadraticUtilities.h" 1473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com#include "TSearch.h" 1573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 16753b870c62bd22cee3d9a15efc634822724084acmtklein#ifdef SK_DEBUG 1785ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com#include "LineUtilities.h" 1885ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com#endif 1985ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com 20235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com/* given the implicit form 0 = Ax^2 + Bxy + Cy^2 + Dx + Ey + F 21235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com * and given x = at^2 + bt + c (the parameterized form) 22235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com * y = dt^2 + et + f 23055c7c299cb47eebd360b809ad58a0006e2e55f7skia.committer@gmail.com * then 24235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com * 0 = A(at^2+bt+c)(at^2+bt+c)+B(at^2+bt+c)(dt^2+et+f)+C(dt^2+et+f)(dt^2+et+f)+D(at^2+bt+c)+E(dt^2+et+f)+F 25235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com */ 2615dd300ac6d7695b4d2aca81d8f3648eae704451skia.committer@gmail.com 2773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comstatic int findRoots(const QuadImplicitForm& i, const Quadratic& q2, double roots[4], 285e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com bool oneHint, int firstCubicRoot) { 29235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double a, b, c; 30235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com set_abc(&q2[0].x, a, b, c); 31235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double d, e, f; 32235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com set_abc(&q2[0].y, d, e, f); 33235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com const double t4 = i.x2() * a * a 34235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.xy() * a * d 35235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.y2() * d * d; 36235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com const double t3 = 2 * i.x2() * a * b 37235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.xy() * (a * e + b * d) 38235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + 2 * i.y2() * d * e; 39235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com const double t2 = i.x2() * (b * b + 2 * a * c) 40235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.xy() * (c * d + b * e + a * f) 41235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.y2() * (e * e + 2 * d * f) 42235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.x() * a 43235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.y() * d; 44235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com const double t1 = 2 * i.x2() * b * c 45235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.xy() * (c * e + b * f) 46235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + 2 * i.y2() * e * f 47235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.x() * b 48235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.y() * e; 49235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com const double t0 = i.x2() * c * c 50235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.xy() * c * f 51235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.y2() * f * f 52235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.x() * c 53235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.y() * f 54235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com + i.c(); 559f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com int rootCount = reducedQuarticRoots(t4, t3, t2, t1, t0, oneHint, roots); 569f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com if (rootCount >= 0) { 579f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return rootCount; 5873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 595e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com return quarticRootsReal(firstCubicRoot, t4, t3, t2, t1, t0, roots); 60235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com} 61235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 6245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic int addValidRoots(const double roots[4], const int count, double valid[4]) { 6345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com int result = 0; 64235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com int index; 65235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com for (index = 0; index < count; ++index) { 66235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (!approximately_zero_or_more(roots[index]) || !approximately_one_or_less(roots[index])) { 67235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com continue; 68235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 69235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double t = 1 - roots[index]; 70235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (approximately_less_than_zero(t)) { 71235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com t = 0; 72235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } else if (approximately_greater_than_one(t)) { 73235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com t = 1; 74235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 7545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com valid[result++] = t; 76235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 7745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com return result; 78235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com} 79235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 806aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.comstatic bool onlyEndPtsInCommon(const Quadratic& q1, const Quadratic& q2, Intersections& i) { 816aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com// the idea here is to see at minimum do a quick reject by rotating all points 826aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com// to either side of the line formed by connecting the endpoints 836aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com// if the opposite curves points are on the line or on the other side, the 846aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com// curves at most intersect at the endpoints 856aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com for (int oddMan = 0; oddMan < 3; ++oddMan) { 866aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com const _Point* endPt[2]; 876aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com for (int opp = 1; opp < 3; ++opp) { 886aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com int end = oddMan ^ opp; 896aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com if (end == 3) { 906aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com end = opp; 916aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com } 926aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com endPt[opp - 1] = &q1[end]; 936aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com } 946aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com double origX = endPt[0]->x; 956aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com double origY = endPt[0]->y; 966aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com double adj = endPt[1]->x - origX; 976aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com double opp = endPt[1]->y - origY; 986aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com double sign = (q1[oddMan].y - origY) * adj - (q1[oddMan].x - origX) * opp; 9973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (approximately_zero(sign)) { 10073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com goto tryNextHalfPlane; 10173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 1026aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com for (int n = 0; n < 3; ++n) { 1036aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com double test = (q2[n].y - origY) * adj - (q2[n].x - origX) * opp; 1046aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com if (test * sign > 0) { 1056aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com goto tryNextHalfPlane; 1066aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com } 1076aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com } 1086aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com for (int i1 = 0; i1 < 3; i1 += 2) { 1096aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com for (int i2 = 0; i2 < 3; i2 += 2) { 1106aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com if (q1[i1] == q2[i2]) { 11145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.insert(i1 >> 1, i2 >> 1, q1[i1]); 1126aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com } 1136aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com } 1146aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com } 115aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkASSERT(i.fUsed < 3); 1166aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com return true; 1176aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.comtryNextHalfPlane: 1186aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com ; 1196aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com } 1206aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com return false; 1216aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com} 1226aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com 12385ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com// returns false if there's more than one intercept or the intercept doesn't match the point 124cdcb2ce2744c7e5c47453328dbf292edee79ab37skia.committer@gmail.com// returns true if the intercept was successfully added or if the 12585ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com// original quads need to be subdivided 12673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comstatic bool addIntercept(const Quadratic& q1, const Quadratic& q2, double tMin, double tMax, 12785ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com Intersections& i, bool* subDivide) { 12873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double tMid = (tMin + tMax) / 2; 12973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com _Point mid; 13073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com xy_at_t(q2, tMid, mid.x, mid.y); 13173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com _Line line; 13273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com line[0] = line[1] = mid; 1337ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com _Vector dxdy = dxdy_at_t(q2, tMid); 1347ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com line[0] -= dxdy; 1357ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com line[1] += dxdy; 13673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com Intersections rootTs; 13773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int roots = intersect(q1, line, rootTs); 13885ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com if (roots == 0) { 13985ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com if (subDivide) { 14085ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com *subDivide = true; 14185ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com } 14285ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com return true; 14385ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com } 1449f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com if (roots == 2) { 1459f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return false; 1469f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 14773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com _Point pt2; 14873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com xy_at_t(q1, rootTs.fT[0][0], pt2.x, pt2.y); 14945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (!pt2.approximatelyEqualHalf(mid)) { 15073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return false; 15173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 15245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.insertSwap(rootTs.fT[0][0], tMid, pt2); 15373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return true; 15473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 15573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 15673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comstatic bool isLinearInner(const Quadratic& q1, double t1s, double t1e, const Quadratic& q2, 15785ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com double t2s, double t2e, Intersections& i, bool* subDivide) { 15873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com Quadratic hull; 15973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com sub_divide(q1, t1s, t1e, hull); 16073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com _Line line = {hull[2], hull[0]}; 16173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com const _Line* testLines[] = { &line, (const _Line*) &hull[0], (const _Line*) &hull[1] }; 16273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com size_t testCount = sizeof(testLines) / sizeof(testLines[0]); 16373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com SkTDArray<double> tsFound; 16473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (size_t index = 0; index < testCount; ++index) { 16573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com Intersections rootTs; 16673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int roots = intersect(q2, *testLines[index], rootTs); 16773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int idx2 = 0; idx2 < roots; ++idx2) { 16873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double t = rootTs.fT[0][idx2]; 169753b870c62bd22cee3d9a15efc634822724084acmtklein#ifdef SK_DEBUG 17085ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com _Point qPt, lPt; 17185ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com xy_at_t(q2, t, qPt.x, qPt.y); 17285ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com xy_at_t(*testLines[index], rootTs.fT[1][idx2], lPt.x, lPt.y); 17385ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com SkASSERT(qPt.approximatelyEqual(lPt)); 17485ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com#endif 17573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (approximately_negative(t - t2s) || approximately_positive(t - t2e)) { 17673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com continue; 17773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 17873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com *tsFound.append() = rootTs.fT[0][idx2]; 17973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 18073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 18173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int tCount = tsFound.count(); 18273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (!tCount) { 18373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return true; 18473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 18573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double tMin, tMax; 18673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (tCount == 1) { 18773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com tMin = tMax = tsFound[0]; 18873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } else if (tCount > 1) { 18973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com QSort<double>(tsFound.begin(), tsFound.end() - 1); 19073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com tMin = tsFound[0]; 1911304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com tMax = tsFound[tsFound.count() - 1]; 19273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 19373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com _Point end; 19473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com xy_at_t(q2, t2s, end.x, end.y); 195beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com bool startInTriangle = point_in_hull(hull, end); 19673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (startInTriangle) { 19773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com tMin = t2s; 19815dd300ac6d7695b4d2aca81d8f3648eae704451skia.committer@gmail.com } 19973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com xy_at_t(q2, t2e, end.x, end.y); 200beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com bool endInTriangle = point_in_hull(hull, end); 20173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (endInTriangle) { 20273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com tMax = t2e; 20373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 20473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int split = 0; 2057ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com _Vector dxy1, dxy2; 20673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (tMin != tMax || tCount > 2) { 2077ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com dxy2 = dxdy_at_t(q2, tMin); 20873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int index = 1; index < tCount; ++index) { 20973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com dxy1 = dxy2; 2107ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com dxy2 = dxdy_at_t(q2, tsFound[index]); 21173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double dot = dxy1.dot(dxy2); 21273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (dot < 0) { 21373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com split = index - 1; 21473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com break; 21573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 21673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 21715dd300ac6d7695b4d2aca81d8f3648eae704451skia.committer@gmail.com 21873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 21973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (split == 0) { // there's one point 22085ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com if (addIntercept(q1, q2, tMin, tMax, i, subDivide)) { 22173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return true; 22273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 22373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com i.swap(); 22485ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com return isLinearInner(q2, tMin, tMax, q1, t1s, t1e, i, subDivide); 22573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 22673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com // At this point, we have two ranges of t values -- treat each separately at the split 22773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com bool result; 22885ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com if (addIntercept(q1, q2, tMin, tsFound[split - 1], i, subDivide)) { 22973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com result = true; 23073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } else { 23173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com i.swap(); 23285ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com result = isLinearInner(q2, tMin, tsFound[split - 1], q1, t1s, t1e, i, subDivide); 23373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 23485ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com if (addIntercept(q1, q2, tsFound[split], tMax, i, subDivide)) { 23573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com result = true; 23673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } else { 23773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com i.swap(); 23885ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com result |= isLinearInner(q2, tsFound[split], tMax, q1, t1s, t1e, i, subDivide); 23973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 24073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return result; 24173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 24273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 24373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comstatic double flatMeasure(const Quadratic& q) { 2447ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com _Vector mid = q[1] - q[0]; 2457ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com _Vector dxy = q[2] - q[0]; 2469f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com double length = dxy.length(); // OPTIMIZE: get rid of sqrt 2479f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return fabs(mid.cross(dxy) / length); 24873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 24973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 25073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com// FIXME ? should this measure both and then use the quad that is the flattest as the line? 25173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comstatic bool isLinear(const Quadratic& q1, const Quadratic& q2, Intersections& i) { 25273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double measure = flatMeasure(q1); 25373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com // OPTIMIZE: (get rid of sqrt) use approximately_zero 25473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (!approximately_zero_sqrt(measure)) { 25573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return false; 25673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 25785ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com return isLinearInner(q1, 0, 1, q2, 0, 1, i, NULL); 25873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 25973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 2609f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com// FIXME: if flat measure is sufficiently large, then probably the quartic solution failed 26185ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.comstatic void relaxedIsLinear(const Quadratic& q1, const Quadratic& q2, Intersections& i) { 26273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double m1 = flatMeasure(q1); 26373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double m2 = flatMeasure(q2); 264753b870c62bd22cee3d9a15efc634822724084acmtklein#ifdef SK_DEBUG 2659f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com double min = SkTMin(m1, m2); 2669f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com if (min > 5) { 2679f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com SkDebugf("%s maybe not flat enough.. %1.9g\n", __FUNCTION__, min); 2689f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 2699f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com#endif 27005c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com i.reset(); 27185ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com const Quadratic& rounder = m2 < m1 ? q1 : q2; 27285ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com const Quadratic& flatter = m2 < m1 ? q2 : q1; 27385ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com bool subDivide = false; 27485ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com isLinearInner(flatter, 0, 1, rounder, 0, 1, i, &subDivide); 27585ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com if (subDivide) { 27685ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com QuadraticPair pair; 27785ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com chop_at(flatter, pair, 0.5); 27885ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com Intersections firstI, secondI; 27985ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com relaxedIsLinear(pair.first(), rounder, firstI); 28085ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com for (int index = 0; index < firstI.used(); ++index) { 28145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.insert(firstI.fT[0][index] * 0.5, firstI.fT[1][index], firstI.fPt[index]); 28285ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com } 28385ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com relaxedIsLinear(pair.second(), rounder, secondI); 28485ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com for (int index = 0; index < secondI.used(); ++index) { 28545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.insert(0.5 + secondI.fT[0][index] * 0.5, secondI.fT[1][index], secondI.fPt[index]); 28685ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com } 28785ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com } 28885ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com if (m2 < m1) { 28985ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com i.swapPts(); 29073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 29173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 29273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 29373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com#if 0 29473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comstatic void unsortableExpanse(const Quadratic& q1, const Quadratic& q2, Intersections& i) { 29573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com const Quadratic* qs[2] = { &q1, &q2 }; 29673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com // need t values for start and end of unsortable expanse on both curves 29773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com // try projecting lines parallel to the end points 29873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com i.fT[0][0] = 0; 29973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com i.fT[0][1] = 1; 30073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int flip = -1; // undecided 30173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int qIdx = 0; qIdx < 2; qIdx++) { 30273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int t = 0; t < 2; t++) { 30373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com _Point dxdy; 30405c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com dxdy_at_t(*qs[qIdx], t, dxdy); 30573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com _Line perp; 30673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com perp[0] = perp[1] = (*qs[qIdx])[t == 0 ? 0 : 2]; 30773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com perp[0].x += dxdy.y; 30873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com perp[0].y -= dxdy.x; 30973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com perp[1].x -= dxdy.y; 31073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com perp[1].y += dxdy.x; 31173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com Intersections hitData; 31273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int hits = intersectRay(*qs[qIdx ^ 1], perp, hitData); 313aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkASSERT(hits <= 1); 31473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (hits) { 31573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (flip < 0) { 31673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com _Point dxdy2; 31705c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com dxdy_at_t(*qs[qIdx ^ 1], hitData.fT[0][0], dxdy2); 31873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double dot = dxdy.dot(dxdy2); 31973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com flip = dot < 0; 32073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com i.fT[1][0] = flip; 32173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com i.fT[1][1] = !flip; 32273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 32373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com i.fT[qIdx ^ 1][t ^ flip] = hitData.fT[0][0]; 32473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 32573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 32673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 32773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com i.fUnsortable = true; // failed, probably coincident or near-coincident 32873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com i.fUsed = 2; 32973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 33073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com#endif 33173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 3325e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com// each time through the loop, this computes values it had from the last loop 3335e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com// if i == j == 1, the center values are still good 3345e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com// otherwise, for i != 1 or j != 1, four of the values are still good 3355e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com// and if i == 1 ^ j == 1, an additional value is good 3365e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.comstatic bool binarySearch(const Quadratic& quad1, const Quadratic& quad2, double& t1Seed, 3375e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com double& t2Seed, _Point& pt) { 3385e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com double tStep = ROUGH_EPSILON; 3395e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com _Point t1[3], t2[3]; 3405e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com int calcMask = ~0; 3415e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com do { 3425e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (calcMask & (1 << 1)) t1[1] = xy_at_t(quad1, t1Seed); 3435e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (calcMask & (1 << 4)) t2[1] = xy_at_t(quad2, t2Seed); 3445e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (t1[1].approximatelyEqual(t2[1])) { 3455e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com pt = t1[1]; 3465e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com #if ONE_OFF_DEBUG 3475e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __FUNCTION__, 3485e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t1Seed, t2Seed, t1[1].x, t1[1].y, t1[2].x, t1[2].y); 3495e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com #endif 3505e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com return true; 3515e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 3525e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (calcMask & (1 << 0)) t1[0] = xy_at_t(quad1, t1Seed - tStep); 3535e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (calcMask & (1 << 2)) t1[2] = xy_at_t(quad1, t1Seed + tStep); 3545e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (calcMask & (1 << 3)) t2[0] = xy_at_t(quad2, t2Seed - tStep); 3555e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (calcMask & (1 << 5)) t2[2] = xy_at_t(quad2, t2Seed + tStep); 3565e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com double dist[3][3]; 3575e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com // OPTIMIZE: using calcMask value permits skipping some distance calcuations 3585e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com // if prior loop's results are moved to correct slot for reuse 3595e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com dist[1][1] = t1[1].distanceSquared(t2[1]); 3605e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com int best_i = 1, best_j = 1; 3615e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com for (int i = 0; i < 3; ++i) { 3625e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com for (int j = 0; j < 3; ++j) { 3635e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (i == 1 && j == 1) { 3645e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com continue; 3655e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 3665e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com dist[i][j] = t1[i].distanceSquared(t2[j]); 3675e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (dist[best_i][best_j] > dist[i][j]) { 3685e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com best_i = i; 3695e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com best_j = j; 3705e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 3715e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 3725e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 3735e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (best_i == 1 && best_j == 1) { 3745e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com tStep /= 2; 3755e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (tStep < FLT_EPSILON_HALF) { 3765e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com break; 3775e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 378d454ec135eeef48edea7ebc47a61ff39bd654576skia.committer@gmail.com calcMask = (1 << 0) | (1 << 2) | (1 << 3) | (1 << 5); 3795e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com continue; 3805e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 3815e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (best_i == 0) { 3825e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t1Seed -= tStep; 3835e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t1[2] = t1[1]; 3845e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t1[1] = t1[0]; 3855e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com calcMask = 1 << 0; 3865e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } else if (best_i == 2) { 3875e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t1Seed += tStep; 3885e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t1[0] = t1[1]; 3895e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t1[1] = t1[2]; 3905e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com calcMask = 1 << 2; 3915e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } else { 3925e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com calcMask = 0; 3935e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 3945e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (best_j == 0) { 3955e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t2Seed -= tStep; 3965e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t2[2] = t2[1]; 3975e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t2[1] = t2[0]; 3985e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com calcMask |= 1 << 3; 3995e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } else if (best_j == 2) { 4005e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t2Seed += tStep; 4015e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t2[0] = t2[1]; 4025e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t2[1] = t2[2]; 4035e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com calcMask |= 1 << 5; 4045e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 4055e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } while (true); 4065e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com#if ONE_OFF_DEBUG 4075e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) != (%1.9g,%1.9g) %s\n", __FUNCTION__, 4085e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com t1Seed, t2Seed, t1[1].x, t1[1].y, t1[2].x, t1[2].y); 4095e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com#endif 4105e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com return false; 4115e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com} 4125e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com 413235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.combool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i) { 4146aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com // if the quads share an end point, check to see if they overlap 4156aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com 4166aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com if (onlyEndPtsInCommon(q1, q2, i)) { 4176aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com return i.intersected(); 4186aea33f92c611d6fdc88bc2352c5c966168af83bcaryclark@google.com } 41973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (onlyEndPtsInCommon(q2, q1, i)) { 42073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com i.swapPts(); 42173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return i.intersected(); 42273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 42373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com // see if either quad is really a line 42473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (isLinear(q1, q2, i)) { 42573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return i.intersected(); 42673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 42773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (isLinear(q2, q1, i)) { 42873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com i.swapPts(); 42973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return i.intersected(); 43073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 431235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com QuadImplicitForm i1(q1); 432235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com QuadImplicitForm i2(q2); 433235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (i1.implicit_match(i2)) { 434235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // FIXME: compute T values 435235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // compute the intersections of the ends to find the coincident span 436235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com bool useVertical = fabs(q1[0].x - q1[2].x) < fabs(q1[0].y - q1[2].y); 437235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double t; 438235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if ((t = axialIntersect(q1, q2[0], useVertical)) >= 0) { 43945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.insertCoincident(t, 0, q2[0]); 440235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 441235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if ((t = axialIntersect(q1, q2[2], useVertical)) >= 0) { 44245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.insertCoincident(t, 1, q2[2]); 443235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 444235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com useVertical = fabs(q2[0].x - q2[2].x) < fabs(q2[0].y - q2[2].y); 445235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if ((t = axialIntersect(q2, q1[0], useVertical)) >= 0) { 44645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.insertCoincident(0, t, q1[0]); 447235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 448235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if ((t = axialIntersect(q2, q1[2], useVertical)) >= 0) { 44945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.insertCoincident(1, t, q1[2]); 450235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 45145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkASSERT(i.coincidentUsed() <= 2); 45245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com return i.coincidentUsed() > 0; 453235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 45445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com int index; 45573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com bool useCubic = q1[0] == q2[0] || q1[0] == q2[2] || q1[2] == q2[0]; 45645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double roots1[4]; 4575e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com int rootCount = findRoots(i2, q1, roots1, useCubic, 0); 458235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1 45945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double roots1Copy[4]; 46045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com int r1Count = addValidRoots(roots1, rootCount, roots1Copy); 46145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point pts1[4]; 46245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (index = 0; index < r1Count; ++index) { 46345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com xy_at_t(q1, roots1Copy[index], pts1[index].x, pts1[index].y); 46445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 46545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double roots2[4]; 4665e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com int rootCount2 = findRoots(i1, q2, roots2, useCubic, 0); 46745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double roots2Copy[4]; 46845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com int r2Count = addValidRoots(roots2, rootCount2, roots2Copy); 46945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point pts2[4]; 47045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (index = 0; index < r2Count; ++index) { 47145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com xy_at_t(q2, roots2Copy[index], pts2[index].x, pts2[index].y); 47245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 47345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (r1Count == r2Count && r1Count <= 1) { 47445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (r1Count == 1) { 47545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (pts1[0].approximatelyEqualHalf(pts2[0])) { 47645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.insert(roots1Copy[0], roots2Copy[0], pts1[0]); 4771304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com } else if (pts1[0].moreRoughlyEqual(pts2[0])) { 4785e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com // experiment: see if a different cubic solution provides the correct quartic answer 4795e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com #if 0 4805e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com for (int cu1 = 0; cu1 < 3; ++cu1) { 4815e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com rootCount = findRoots(i2, q1, roots1, useCubic, cu1); 4825e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com r1Count = addValidRoots(roots1, rootCount, roots1Copy); 4835e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (r1Count == 0) { 4845e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com continue; 4855e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 4865e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com for (int cu2 = 0; cu2 < 3; ++cu2) { 4875e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (cu1 == 0 && cu2 == 0) { 4885e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com continue; 4895e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 4905e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com rootCount2 = findRoots(i1, q2, roots2, useCubic, cu2); 4915e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com r2Count = addValidRoots(roots2, rootCount2, roots2Copy); 4925e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (r2Count == 0) { 4935e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com continue; 4945e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 4955e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com SkASSERT(r1Count == 1 && r2Count == 1); 496d454ec135eeef48edea7ebc47a61ff39bd654576skia.committer@gmail.com SkDebugf("*** [%d,%d] (%1.9g,%1.9g) %s (%1.9g,%1.9g)\n", cu1, cu2, 4975e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com pts1[0].x, pts1[0].y, pts1[0].approximatelyEqualHalf(pts2[0]) 4985e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com ? "==" : "!=", pts2[0].x, pts2[0].y); 4995e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 5005e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 5015e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com #endif 5025e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com // experiment: try to find intersection by chasing t 5035e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com rootCount = findRoots(i2, q1, roots1, useCubic, 0); 5045e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com r1Count = addValidRoots(roots1, rootCount, roots1Copy); 5055e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com rootCount2 = findRoots(i1, q2, roots2, useCubic, 0); 5065e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com r2Count = addValidRoots(roots2, rootCount2, roots2Copy); 5075e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com if (binarySearch(q1, q2, roots1Copy[0], roots2Copy[0], pts1[0])) { 5085e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com i.insert(roots1Copy[0], roots2Copy[0], pts1[0]); 5095e0500fb5f17fe14db42fc3e0aad08e6b41ccc5fcaryclark@google.com } 5100b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com } 5110b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com } 5120b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com return i.intersected(); 5130b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com } 5140b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com int closest[4]; 5150b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com double dist[4]; 51673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com bool foundSomething = false; 51745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (index = 0; index < r1Count; ++index) { 5180b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com dist[index] = DBL_MAX; 5190b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com closest[index] = -1; 52045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (int ndex2 = 0; ndex2 < r2Count; ++ndex2) { 52145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (!pts2[ndex2].approximatelyEqualHalf(pts1[index])) { 5220b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com continue; 5230b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com } 52445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double dx = pts2[ndex2].x - pts1[index].x; 52545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double dy = pts2[ndex2].y - pts1[index].y; 5260b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com double distance = dx * dx + dy * dy; 5270b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com if (dist[index] <= distance) { 5280b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com continue; 5290b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com } 5300b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com for (int outer = 0; outer < index; ++outer) { 5310b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com if (closest[outer] != ndex2) { 5320b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com continue; 5330b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com } 5340b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com if (dist[outer] < distance) { 5350b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com goto next; 5360b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com } 5370b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com closest[outer] = -1; 5380b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com } 5390b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com dist[index] = distance; 5400b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com closest[index] = ndex2; 54173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com foundSomething = true; 5420b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com next: 5430b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com ; 5440b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com } 5450b7da433fe0eaa2833d1b2900715b013b36d93dacaryclark@google.com } 54645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (r1Count && r2Count && !foundSomething) { 54785ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com relaxedIsLinear(q1, q2, i); 54873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return i.intersected(); 549235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 55073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int used = 0; 55173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com do { 55273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double lowest = DBL_MAX; 55373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int lowestIndex = -1; 55445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com for (index = 0; index < r1Count; ++index) { 55573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (closest[index] < 0) { 556235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com continue; 55773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 55873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (roots1Copy[index] < lowest) { 55973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com lowestIndex = index; 56073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com lowest = roots1Copy[index]; 56173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 562235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 56373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (lowestIndex < 0) { 56473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com break; 56573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 56645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], 56745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com pts1[lowestIndex]); 56873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com closest[lowestIndex] = -1; 56945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } while (++used < r1Count); 57073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com i.fFlip = false; 571235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com return i.intersected(); 572235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com} 573