121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// Another approach is to start with the implicit form of one curve and solve 221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// (seek implicit coefficients in QuadraticParameter.cpp 321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// by substituting in the parametric form of the other. 421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// The downside of this approach is that early rejects are difficult to come by. 521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormula.html#step 621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#include "SkDQuadImplicit.h" 921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#include "SkIntersections.h" 1021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#include "SkPathOpsLine.h" 1121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#include "SkQuarticRoot.h" 12b36bcb965cc651ee0c215d439b7fbfdb52516c00caryclark@google.com#include "SkTArray.h" 13d4a6daad3bb2b40cc215fa0e8522873154c5a59bcommit-bot@chromium.org#include "SkTSort.h" 1421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 1521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com/* given the implicit form 0 = Ax^2 + Bxy + Cy^2 + Dx + Ey + F 1621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * and given x = at^2 + bt + c (the parameterized form) 1721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * y = dt^2 + et + f 1821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * then 1921c2924b178f0d4c298d6631e568401473ed8d16caryclark@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 2021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com */ 2121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 223bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.comstatic int findRoots(const SkDQuadImplicit& i, const SkDQuad& quad, double roots[4], 233bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com bool oneHint, bool flip, int firstCubicRoot) { 243bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkDQuad flipped; 253bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com const SkDQuad& q = flip ? (flipped = quad.flip()) : quad; 2621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double a, b, c; 273bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkDQuad::SetABC(&q[0].fX, &a, &b, &c); 2821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double d, e, f; 293bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkDQuad::SetABC(&q[0].fY, &d, &e, &f); 3021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com const double t4 = i.x2() * a * a 3121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.xy() * a * d 3221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.y2() * d * d; 3321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com const double t3 = 2 * i.x2() * a * b 3421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.xy() * (a * e + b * d) 3521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + 2 * i.y2() * d * e; 3621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com const double t2 = i.x2() * (b * b + 2 * a * c) 3721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.xy() * (c * d + b * e + a * f) 3821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.y2() * (e * e + 2 * d * f) 3921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.x() * a 4021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.y() * d; 4121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com const double t1 = 2 * i.x2() * b * c 4221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.xy() * (c * e + b * f) 4321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + 2 * i.y2() * e * f 4421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.x() * b 4521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.y() * e; 4621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com const double t0 = i.x2() * c * c 4721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.xy() * c * f 4821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.y2() * f * f 4921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.x() * c 5021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.y() * f 5121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + i.c(); 5221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int rootCount = SkReducedQuarticRoots(t4, t3, t2, t1, t0, oneHint, roots); 533bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (rootCount < 0) { 543bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com rootCount = SkQuarticRootsReal(firstCubicRoot, t4, t3, t2, t1, t0, roots); 5521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 563bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (flip) { 573bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com for (int index = 0; index < rootCount; ++index) { 583bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com roots[index] = 1 - roots[index]; 593bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 603bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 613bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com return rootCount; 6221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 6321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 6421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comstatic int addValidRoots(const double roots[4], const int count, double valid[4]) { 6521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int result = 0; 6621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int index; 6721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (index = 0; index < count; ++index) { 6821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (!approximately_zero_or_more(roots[index]) || !approximately_one_or_less(roots[index])) { 6921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com continue; 7021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 7121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double t = 1 - roots[index]; 7221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (approximately_less_than_zero(t)) { 7321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t = 0; 7421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } else if (approximately_greater_than_one(t)) { 7521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t = 1; 7621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 7721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com valid[result++] = t; 7821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 7921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return result; 8021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 8121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 826645d6469358421636adc7d11e837a90078340abcaryclark@google.comstatic bool only_end_pts_in_common(const SkDQuad& q1, const SkDQuad& q2) { 8321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// the idea here is to see at minimum do a quick reject by rotating all points 8421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// to either side of the line formed by connecting the endpoints 8521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// if the opposite curves points are on the line or on the other side, the 8621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// curves at most intersect at the endpoints 8721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int oddMan = 0; oddMan < 3; ++oddMan) { 8821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com const SkDPoint* endPt[2]; 8921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int opp = 1; opp < 3; ++opp) { 901a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com int end = oddMan ^ opp; // choose a value not equal to oddMan 911a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (3 == end) { // and correct so that largest value is 1 or 2 9221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com end = opp; 9321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 9421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com endPt[opp - 1] = &q1[end]; 9521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 9621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double origX = endPt[0]->fX; 9721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double origY = endPt[0]->fY; 9821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double adj = endPt[1]->fX - origX; 9921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double opp = endPt[1]->fY - origY; 10021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double sign = (q1[oddMan].fY - origY) * adj - (q1[oddMan].fX - origX) * opp; 10121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (approximately_zero(sign)) { 10221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com goto tryNextHalfPlane; 10321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 10421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int n = 0; n < 3; ++n) { 10521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp; 1066645d6469358421636adc7d11e837a90078340abcaryclark@google.com if (test * sign > 0 && !precisely_zero(test)) { 10721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com goto tryNextHalfPlane; 10821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 10921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 11021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return true; 11121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comtryNextHalfPlane: 11221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com ; 11321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 11421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return false; 11521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 11621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 11721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// returns false if there's more than one intercept or the intercept doesn't match the point 11821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// returns true if the intercept was successfully added or if the 11921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// original quads need to be subdivided 12021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comstatic bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, double tMax, 12121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkIntersections* i, bool* subDivide) { 12221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double tMid = (tMin + tMax) / 2; 1231a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkDPoint mid = q2.ptAtT(tMid); 12421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDLine line; 12521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com line[0] = line[1] = mid; 12621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDVector dxdy = q2.dxdyAtT(tMid); 12721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com line[0] -= dxdy; 12821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com line[1] += dxdy; 12921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkIntersections rootTs; 1302607e2e5a8f13275d86e2242f9906f2106a2fa79caryclark@google.com rootTs.allowNear(false); 13121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int roots = rootTs.intersect(q1, line); 13221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (roots == 0) { 13321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (subDivide) { 13421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com *subDivide = true; 13521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 13621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return true; 13721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 13821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (roots == 2) { 13921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return false; 14021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 1411a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkDPoint pt2 = q1.ptAtT(rootTs[0][0]); 14221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (!pt2.approximatelyEqualHalf(mid)) { 14321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return false; 14421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 14521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com i->insertSwap(rootTs[0][0], tMid, pt2); 14621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return true; 14721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 14821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 14921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comstatic bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkDQuad& q2, 15021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double t2s, double t2e, SkIntersections* i, bool* subDivide) { 15121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDQuad hull = q1.subDivide(t1s, t1e); 15221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDLine line = {{hull[2], hull[0]}}; 15321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com const SkDLine* testLines[] = { &line, (const SkDLine*) &hull[0], (const SkDLine*) &hull[1] }; 154b36bcb965cc651ee0c215d439b7fbfdb52516c00caryclark@google.com const size_t kTestCount = SK_ARRAY_COUNT(testLines); 155b36bcb965cc651ee0c215d439b7fbfdb52516c00caryclark@google.com SkSTArray<kTestCount * 2, double, true> tsFound; 156b36bcb965cc651ee0c215d439b7fbfdb52516c00caryclark@google.com for (size_t index = 0; index < kTestCount; ++index) { 15721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkIntersections rootTs; 1582607e2e5a8f13275d86e2242f9906f2106a2fa79caryclark@google.com rootTs.allowNear(false); 15921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int roots = rootTs.intersect(q2, *testLines[index]); 16021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int idx2 = 0; idx2 < roots; ++idx2) { 16121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double t = rootTs[0][idx2]; 16221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#ifdef SK_DEBUG 1631a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkDPoint qPt = q2.ptAtT(t); 1641a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkDPoint lPt = testLines[index]->ptAtT(rootTs[1][idx2]); 16521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkASSERT(qPt.approximatelyEqual(lPt)); 16621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#endif 16721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (approximately_negative(t - t2s) || approximately_positive(t - t2e)) { 16821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com continue; 16921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 170b36bcb965cc651ee0c215d439b7fbfdb52516c00caryclark@google.com tsFound.push_back(rootTs[0][idx2]); 17121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 17221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 17321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int tCount = tsFound.count(); 17421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (tCount <= 0) { 17521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return true; 17621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 17721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double tMin, tMax; 17821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (tCount == 1) { 17921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com tMin = tMax = tsFound[0]; 180b631c40b93daf8b48f22b1c1bce7bcec1369c9e7reed@google.com } else { 181b631c40b93daf8b48f22b1c1bce7bcec1369c9e7reed@google.com SkASSERT(tCount > 1); 182d4a6daad3bb2b40cc215fa0e8522873154c5a59bcommit-bot@chromium.org SkTQSort<double>(tsFound.begin(), tsFound.end() - 1); 18321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com tMin = tsFound[0]; 18421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com tMax = tsFound[tsFound.count() - 1]; 18521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 1861a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkDPoint end = q2.ptAtT(t2s); 18721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com bool startInTriangle = hull.pointInHull(end); 18821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (startInTriangle) { 18921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com tMin = t2s; 19021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 1911a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com end = q2.ptAtT(t2e); 19221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com bool endInTriangle = hull.pointInHull(end); 19321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (endInTriangle) { 19421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com tMax = t2e; 19521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 19621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int split = 0; 19721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDVector dxy1, dxy2; 19821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (tMin != tMax || tCount > 2) { 19921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com dxy2 = q2.dxdyAtT(tMin); 20021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int index = 1; index < tCount; ++index) { 20121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com dxy1 = dxy2; 20221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com dxy2 = q2.dxdyAtT(tsFound[index]); 20321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double dot = dxy1.dot(dxy2); 20421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (dot < 0) { 20521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com split = index - 1; 20621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com break; 20721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 20821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 20921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 21021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (split == 0) { // there's one point 21121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (add_intercept(q1, q2, tMin, tMax, i, subDivide)) { 21221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return true; 21321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 21421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com i->swap(); 21521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return is_linear_inner(q2, tMin, tMax, q1, t1s, t1e, i, subDivide); 21621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 21721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // At this point, we have two ranges of t values -- treat each separately at the split 21821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com bool result; 21921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (add_intercept(q1, q2, tMin, tsFound[split - 1], i, subDivide)) { 22021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com result = true; 22121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } else { 22221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com i->swap(); 22321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com result = is_linear_inner(q2, tMin, tsFound[split - 1], q1, t1s, t1e, i, subDivide); 22421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 22521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (add_intercept(q1, q2, tsFound[split], tMax, i, subDivide)) { 22621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com result = true; 22721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } else { 22821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com i->swap(); 22921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com result |= is_linear_inner(q2, tsFound[split], tMax, q1, t1s, t1e, i, subDivide); 23021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 23121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return result; 23221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 23321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 23421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comstatic double flat_measure(const SkDQuad& q) { 23521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDVector mid = q[1] - q[0]; 23621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDVector dxy = q[2] - q[0]; 23721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double length = dxy.length(); // OPTIMIZE: get rid of sqrt 23821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return fabs(mid.cross(dxy) / length); 23921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 24021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 24121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// FIXME ? should this measure both and then use the quad that is the flattest as the line? 24221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comstatic bool is_linear(const SkDQuad& q1, const SkDQuad& q2, SkIntersections* i) { 24321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double measure = flat_measure(q1); 24421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // OPTIMIZE: (get rid of sqrt) use approximately_zero 24521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (!approximately_zero_sqrt(measure)) { 24621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return false; 24721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 24821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return is_linear_inner(q1, 0, 1, q2, 0, 1, i, NULL); 24921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 25021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 25121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// FIXME: if flat measure is sufficiently large, then probably the quartic solution failed 25221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comstatic void relaxed_is_linear(const SkDQuad& q1, const SkDQuad& q2, SkIntersections* i) { 25321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double m1 = flat_measure(q1); 25421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double m2 = flat_measure(q2); 25521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#if DEBUG_FLAT_QUADS 256b3985896fe7478e1a556e572224503bff2d7d669caryclark@google.com double min = SkTMin(m1, m2); 25721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (min > 5) { 25821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDebugf("%s maybe not flat enough.. %1.9g\n", __FUNCTION__, min); 25921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 26021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#endif 26121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com i->reset(); 26221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com const SkDQuad& rounder = m2 < m1 ? q1 : q2; 26321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com const SkDQuad& flatter = m2 < m1 ? q2 : q1; 26421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com bool subDivide = false; 26521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com is_linear_inner(flatter, 0, 1, rounder, 0, 1, i, &subDivide); 26621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (subDivide) { 26721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDQuadPair pair = flatter.chopAt(0.5); 26821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkIntersections firstI, secondI; 26921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com relaxed_is_linear(pair.first(), rounder, &firstI); 27021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int index = 0; index < firstI.used(); ++index) { 27121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com i->insert(firstI[0][index] * 0.5, firstI[1][index], firstI.pt(index)); 27221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 27321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com relaxed_is_linear(pair.second(), rounder, &secondI); 27421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int index = 0; index < secondI.used(); ++index) { 27521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com i->insert(0.5 + secondI[0][index] * 0.5, secondI[1][index], secondI.pt(index)); 27621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 27721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 27821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (m2 < m1) { 27921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com i->swapPts(); 28021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 28121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 28221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 28321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// each time through the loop, this computes values it had from the last loop 28421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// if i == j == 1, the center values are still good 28521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// otherwise, for i != 1 or j != 1, four of the values are still good 28621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// and if i == 1 ^ j == 1, an additional value is good 28721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comstatic bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1Seed, 28821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double* t2Seed, SkDPoint* pt) { 28921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double tStep = ROUGH_EPSILON; 29021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDPoint t1[3], t2[3]; 29121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int calcMask = ~0; 29221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com do { 2931a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (calcMask & (1 << 1)) t1[1] = quad1.ptAtT(*t1Seed); 2941a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (calcMask & (1 << 4)) t2[1] = quad2.ptAtT(*t2Seed); 29521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (t1[1].approximatelyEqual(t2[1])) { 29621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com *pt = t1[1]; 29721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com #if ONE_OFF_DEBUG 29821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __FUNCTION__, 29921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t1Seed, t2Seed, t1[1].fX, t1[1].fY, t1[2].fX, t1[2].fY); 30021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com #endif 30121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return true; 30221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 3031a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(*t1Seed - tStep); 3041a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(*t1Seed + tStep); 3051a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(*t2Seed - tStep); 3061a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(*t2Seed + tStep); 30721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double dist[3][3]; 30821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // OPTIMIZE: using calcMask value permits skipping some distance calcuations 30921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // if prior loop's results are moved to correct slot for reuse 31021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com dist[1][1] = t1[1].distanceSquared(t2[1]); 31121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int best_i = 1, best_j = 1; 31221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int i = 0; i < 3; ++i) { 31321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int j = 0; j < 3; ++j) { 31421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (i == 1 && j == 1) { 31521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com continue; 31621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 31721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com dist[i][j] = t1[i].distanceSquared(t2[j]); 31821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (dist[best_i][best_j] > dist[i][j]) { 31921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com best_i = i; 32021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com best_j = j; 32121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 32221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 32321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 32421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (best_i == 1 && best_j == 1) { 32521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com tStep /= 2; 32621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (tStep < FLT_EPSILON_HALF) { 32721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com break; 32821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 32921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com calcMask = (1 << 0) | (1 << 2) | (1 << 3) | (1 << 5); 33021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com continue; 33121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 33221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (best_i == 0) { 33321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com *t1Seed -= tStep; 33421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t1[2] = t1[1]; 33521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t1[1] = t1[0]; 33621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com calcMask = 1 << 0; 33721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } else if (best_i == 2) { 33821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com *t1Seed += tStep; 33921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t1[0] = t1[1]; 34021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t1[1] = t1[2]; 34121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com calcMask = 1 << 2; 34221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } else { 34321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com calcMask = 0; 34421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 34521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (best_j == 0) { 34621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com *t2Seed -= tStep; 34721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t2[2] = t2[1]; 34821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t2[1] = t2[0]; 34921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com calcMask |= 1 << 3; 35021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } else if (best_j == 2) { 35121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com *t2Seed += tStep; 35221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t2[0] = t2[1]; 35321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t2[1] = t2[2]; 35421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com calcMask |= 1 << 5; 35521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 35621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } while (true); 35721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#if ONE_OFF_DEBUG 35821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) != (%1.9g,%1.9g) %s\n", __FUNCTION__, 35921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t1Seed, t2Seed, t1[1].fX, t1[1].fY, t1[2].fX, t1[2].fY); 36021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#endif 36121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return false; 36221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 36321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 3641a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.comstatic void lookNearEnd(const SkDQuad& q1, const SkDQuad& q2, int testT, 3651a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com const SkIntersections& orig, bool swap, SkIntersections* i) { 3661a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (orig.used() == 1 && orig[!swap][0] == testT) { 3671a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com return; 3681a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com } 3691a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (orig.used() == 2 && orig[!swap][1] == testT) { 3701a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com return; 3711a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com } 3721a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkDLine tmpLine; 3731a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com int testTIndex = testT << 1; 3741a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com tmpLine[0] = tmpLine[1] = q2[testTIndex]; 3751a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com tmpLine[1].fX += q2[1].fY - q2[testTIndex].fY; 3761a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com tmpLine[1].fY -= q2[1].fX - q2[testTIndex].fX; 3771a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkIntersections impTs; 3781a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com impTs.intersectRay(q1, tmpLine); 3791a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com for (int index = 0; index < impTs.used(); ++index) { 3801a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkDPoint realPt = impTs.pt(index); 3811a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (!tmpLine[0].approximatelyEqualHalf(realPt)) { 3821a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com continue; 3831a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com } 3841a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (swap) { 3851a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com i->insert(testT, impTs[0][index], tmpLine[0]); 3861a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com } else { 3871a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com i->insert(impTs[0][index], testT, tmpLine[0]); 3881a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com } 3891a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com } 3901a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com} 3911a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com 39221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comint SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { 39321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // if the quads share an end point, check to see if they overlap 39421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 3956645d6469358421636adc7d11e837a90078340abcaryclark@google.com for (int i1 = 0; i1 < 3; i1 += 2) { 3966645d6469358421636adc7d11e837a90078340abcaryclark@google.com for (int i2 = 0; i2 < 3; i2 += 2) { 3976645d6469358421636adc7d11e837a90078340abcaryclark@google.com if (q1[i1].approximatelyEqualHalf(q2[i2])) { 3986645d6469358421636adc7d11e837a90078340abcaryclark@google.com insert(i1 >> 1, i2 >> 1, q1[i1]); 3996645d6469358421636adc7d11e837a90078340abcaryclark@google.com } 4006645d6469358421636adc7d11e837a90078340abcaryclark@google.com } 4016645d6469358421636adc7d11e837a90078340abcaryclark@google.com } 4026645d6469358421636adc7d11e837a90078340abcaryclark@google.com SkASSERT(fUsed < 3); 4036645d6469358421636adc7d11e837a90078340abcaryclark@google.com if (only_end_pts_in_common(q1, q2)) { 40421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return fUsed; 40521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 4066645d6469358421636adc7d11e837a90078340abcaryclark@google.com if (only_end_pts_in_common(q2, q1)) { 40721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return fUsed; 40821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 40921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // see if either quad is really a line 4101a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com // FIXME: figure out why reduce step didn't find this earlier 41121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (is_linear(q1, q2, this)) { 41221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return fUsed; 41321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 4146645d6469358421636adc7d11e837a90078340abcaryclark@google.com SkIntersections swapped; 4156645d6469358421636adc7d11e837a90078340abcaryclark@google.com if (is_linear(q2, q1, &swapped)) { 4166645d6469358421636adc7d11e837a90078340abcaryclark@google.com swapped.swapPts(); 4176645d6469358421636adc7d11e837a90078340abcaryclark@google.com set(swapped); 41821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return fUsed; 41921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 4201a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkIntersections copyI(*this); 4211a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com lookNearEnd(q1, q2, 0, *this, false, ©I); 4221a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com lookNearEnd(q1, q2, 1, *this, false, ©I); 4231a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com lookNearEnd(q2, q1, 0, *this, true, ©I); 4241a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com lookNearEnd(q2, q1, 1, *this, true, ©I); 4251a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com int innerEqual = 0; 4261a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (copyI.fUsed >= 2) { 4271a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkASSERT(copyI.fUsed <= 4); 4281a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com double width = copyI[0][1] - copyI[0][0]; 4291a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com int midEnd = 1; 4301a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com for (int index = 2; index < copyI.fUsed; ++index) { 4311a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com double testWidth = copyI[0][index] - copyI[0][index - 1]; 4321a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (testWidth <= width) { 4331a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com continue; 4341a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com } 4351a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com midEnd = index; 43621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 4371a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com for (int index = 0; index < 2; ++index) { 4381a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com double testT = (copyI[0][midEnd] * (index + 1) 4391a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com + copyI[0][midEnd - 1] * (2 - index)) / 3; 4401a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkDPoint testPt1 = q1.ptAtT(testT); 4411a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com testT = (copyI[1][midEnd] * (index + 1) + copyI[1][midEnd - 1] * (2 - index)) / 3; 4421a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkDPoint testPt2 = q2.ptAtT(testT); 4431a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com innerEqual += testPt1.approximatelyEqual(testPt2); 44421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 4451a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com } 4461a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com bool expectCoincident = copyI.fUsed >= 2 && innerEqual == 2; 4471a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (expectCoincident) { 4481a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com reset(); 4491a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com insertCoincident(copyI[0][0], copyI[1][0], copyI.fPt[0]); 4501a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com int last = copyI.fUsed - 1; 4511a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com insertCoincident(copyI[0][last], copyI[1][last], copyI.fPt[last]); 45221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return fUsed; 45321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 4541a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkDQuadImplicit i1(q1); 4551a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkDQuadImplicit i2(q2); 45621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int index; 4573bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com bool flip1 = q1[2] == q2[0]; 4583bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com bool flip2 = q1[0] == q2[2]; 4593bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com bool useCubic = q1[0] == q2[0]; 46021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double roots1[4]; 4613bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com int rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); 46221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1 46321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double roots1Copy[4]; 46421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int r1Count = addValidRoots(roots1, rootCount, roots1Copy); 46521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDPoint pts1[4]; 46621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (index = 0; index < r1Count; ++index) { 4671a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com pts1[index] = q1.ptAtT(roots1Copy[index]); 46821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 46921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double roots2[4]; 4703bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); 47121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double roots2Copy[4]; 47221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int r2Count = addValidRoots(roots2, rootCount2, roots2Copy); 47321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDPoint pts2[4]; 47421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (index = 0; index < r2Count; ++index) { 4751a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com pts2[index] = q2.ptAtT(roots2Copy[index]); 47621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 47721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (r1Count == r2Count && r1Count <= 1) { 47821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (r1Count == 1) { 47921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (pts1[0].approximatelyEqualHalf(pts2[0])) { 48021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com insert(roots1Copy[0], roots2Copy[0], pts1[0]); 48121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } else if (pts1[0].moreRoughlyEqual(pts2[0])) { 48221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // experiment: try to find intersection by chasing t 4833bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); 48421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com (void) addValidRoots(roots1, rootCount, roots1Copy); 4853bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); 48621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com (void) addValidRoots(roots2, rootCount2, roots2Copy); 48721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) { 48821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com insert(roots1Copy[0], roots2Copy[0], pts1[0]); 48921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 49021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 49121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 49221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return fUsed; 49321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 49421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int closest[4]; 49521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double dist[4]; 49621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com bool foundSomething = false; 49721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (index = 0; index < r1Count; ++index) { 49821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com dist[index] = DBL_MAX; 49921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com closest[index] = -1; 50021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int ndex2 = 0; ndex2 < r2Count; ++ndex2) { 50121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (!pts2[ndex2].approximatelyEqualHalf(pts1[index])) { 50221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com continue; 50321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 50421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double dx = pts2[ndex2].fX - pts1[index].fX; 50521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double dy = pts2[ndex2].fY - pts1[index].fY; 50621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double distance = dx * dx + dy * dy; 50721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (dist[index] <= distance) { 50821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com continue; 50921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 51021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int outer = 0; outer < index; ++outer) { 51121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (closest[outer] != ndex2) { 51221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com continue; 51321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 51421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (dist[outer] < distance) { 51521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com goto next; 51621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 51721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com closest[outer] = -1; 51821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 51921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com dist[index] = distance; 52021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com closest[index] = ndex2; 52121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com foundSomething = true; 52221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com next: 52321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com ; 52421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 52521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 52621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (r1Count && r2Count && !foundSomething) { 52721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com relaxed_is_linear(q1, q2, this); 52821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return fUsed; 52921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 53021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int used = 0; 53121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com do { 53221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double lowest = DBL_MAX; 53321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int lowestIndex = -1; 53421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (index = 0; index < r1Count; ++index) { 53521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (closest[index] < 0) { 53621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com continue; 53721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 53821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (roots1Copy[index] < lowest) { 53921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com lowestIndex = index; 54021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com lowest = roots1Copy[index]; 54121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 54221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 54321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (lowestIndex < 0) { 54421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com break; 54521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 54621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], 54721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com pts1[lowestIndex]); 54821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com closest[lowestIndex] = -1; 54921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } while (++used < r1Count); 55021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return fUsed; 55121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 552