107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Another approach is to start with the implicit form of one curve and solve 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// (seek implicit coefficients in QuadraticParameter.cpp 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// by substituting in the parametric form of the other. 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// The downside of this approach is that early rejects are difficult to come by. 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormula.html#step 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkDQuadImplicit.h" 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkIntersections.h" 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsLine.h" 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkQuarticRoot.h" 11d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com#include "SkTArray.h" 12b76d3b677713693137936ff813b92c4be48af173commit-bot@chromium.org#include "SkTSort.h" 1307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* given the implicit form 0 = Ax^2 + Bxy + Cy^2 + Dx + Ey + F 1507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * and given x = at^2 + bt + c (the parameterized form) 1607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * y = dt^2 + et + f 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * then 1807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@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 1907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 2007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 21cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.comstatic int findRoots(const SkDQuadImplicit& i, const SkDQuad& quad, double roots[4], 22cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com bool oneHint, bool flip, int firstCubicRoot) { 23cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkDQuad flipped; 24cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com const SkDQuad& q = flip ? (flipped = quad.flip()) : quad; 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double a, b, c; 26cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkDQuad::SetABC(&q[0].fX, &a, &b, &c); 2707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double d, e, f; 28cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkDQuad::SetABC(&q[0].fY, &d, &e, &f); 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double t4 = i.x2() * a * a 3007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.xy() * a * d 3107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.y2() * d * d; 3207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double t3 = 2 * i.x2() * a * b 3307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.xy() * (a * e + b * d) 3407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + 2 * i.y2() * d * e; 3507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double t2 = i.x2() * (b * b + 2 * a * c) 3607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.xy() * (c * d + b * e + a * f) 3707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.y2() * (e * e + 2 * d * f) 3807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.x() * a 3907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.y() * d; 4007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double t1 = 2 * i.x2() * b * c 4107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.xy() * (c * e + b * f) 4207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + 2 * i.y2() * e * f 4307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.x() * b 4407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.y() * e; 4507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double t0 = i.x2() * c * c 4607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.xy() * c * f 4707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.y2() * f * f 4807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.x() * c 4907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.y() * f 5007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com + i.c(); 5107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int rootCount = SkReducedQuarticRoots(t4, t3, t2, t1, t0, oneHint, roots); 52cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (rootCount < 0) { 53cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com rootCount = SkQuarticRootsReal(firstCubicRoot, t4, t3, t2, t1, t0, roots); 5407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 55cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (flip) { 56cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com for (int index = 0; index < rootCount; ++index) { 57cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com roots[index] = 1 - roots[index]; 58cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 59cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 60cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return rootCount; 6107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 6207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 6307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic int addValidRoots(const double roots[4], const int count, double valid[4]) { 6407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int result = 0; 6507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int index; 6607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (index = 0; index < count; ++index) { 6707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!approximately_zero_or_more(roots[index]) || !approximately_one_or_less(roots[index])) { 6807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 6907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double t = 1 - roots[index]; 7107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (approximately_less_than_zero(t)) { 7207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t = 0; 7307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else if (approximately_greater_than_one(t)) { 7407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t = 1; 7507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com valid[result++] = t; 7707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return result; 7907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 8007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 81b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.comstatic bool only_end_pts_in_common(const SkDQuad& q1, const SkDQuad& q2) { 8207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// the idea here is to see at minimum do a quick reject by rotating all points 8307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// to either side of the line formed by connecting the endpoints 8407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// if the opposite curves points are on the line or on the other side, the 8507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// curves at most intersect at the endpoints 8607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int oddMan = 0; oddMan < 3; ++oddMan) { 8707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkDPoint* endPt[2]; 8807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int opp = 1; opp < 3; ++opp) { 894fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com int end = oddMan ^ opp; // choose a value not equal to oddMan 904fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (3 == end) { // and correct so that largest value is 1 or 2 9107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com end = opp; 9207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 9307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com endPt[opp - 1] = &q1[end]; 9407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 9507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double origX = endPt[0]->fX; 9607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double origY = endPt[0]->fY; 9707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double adj = endPt[1]->fX - origX; 9807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double opp = endPt[1]->fY - origY; 9907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double sign = (q1[oddMan].fY - origY) * adj - (q1[oddMan].fX - origX) * opp; 10007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (approximately_zero(sign)) { 10107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com goto tryNextHalfPlane; 10207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 10307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int n = 0; n < 3; ++n) { 10407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp; 105b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com if (test * sign > 0 && !precisely_zero(test)) { 10607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com goto tryNextHalfPlane; 10707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 10807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 10907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 11007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comtryNextHalfPlane: 11107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ; 11207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 11307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 11407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 11507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 11607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// returns false if there's more than one intercept or the intercept doesn't match the point 11707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// returns true if the intercept was successfully added or if the 11807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// original quads need to be subdivided 11907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, double tMax, 12007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkIntersections* i, bool* subDivide) { 12107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double tMid = (tMin + tMax) / 2; 1224fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint mid = q2.ptAtT(tMid); 12307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDLine line; 12407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com line[0] = line[1] = mid; 12507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector dxdy = q2.dxdyAtT(tMid); 12607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com line[0] -= dxdy; 12707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com line[1] += dxdy; 12807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkIntersections rootTs; 129fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com rootTs.allowNear(false); 13007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int roots = rootTs.intersect(q1, line); 13107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (roots == 0) { 13207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (subDivide) { 13307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *subDivide = true; 13407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 13607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (roots == 2) { 13807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 13907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1404fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint pt2 = q1.ptAtT(rootTs[0][0]); 1417eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (!pt2.approximatelyEqual(mid)) { 14207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 14307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 14407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i->insertSwap(rootTs[0][0], tMid, pt2); 14507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 14607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 14707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 14807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkDQuad& q2, 14907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double t2s, double t2e, SkIntersections* i, bool* subDivide) { 15007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuad hull = q1.subDivide(t1s, t1e); 15107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDLine line = {{hull[2], hull[0]}}; 15207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkDLine* testLines[] = { &line, (const SkDLine*) &hull[0], (const SkDLine*) &hull[1] }; 153d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com const size_t kTestCount = SK_ARRAY_COUNT(testLines); 154d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com SkSTArray<kTestCount * 2, double, true> tsFound; 155d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com for (size_t index = 0; index < kTestCount; ++index) { 15607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkIntersections rootTs; 157fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com rootTs.allowNear(false); 15807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int roots = rootTs.intersect(q2, *testLines[index]); 15907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int idx2 = 0; idx2 < roots; ++idx2) { 16007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double t = rootTs[0][idx2]; 1614431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if 0 // def SK_DEBUG // FIXME : accurate for error = 16, error of 17.5 seen 1624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// {{{136.08723965397621, 1648.2814535211637}, {593.49031197259478, 1190.8784277439891}, {593.49031197259478, 544.0128173828125}}} 1634431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org// {{{-968.181396484375, 544.0128173828125}, {592.2825927734375, 870.552490234375}, {593.435302734375, 557.8828125}}} 1644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org 1654fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint qPt = q2.ptAtT(t); 1664fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint lPt = testLines[index]->ptAtT(rootTs[1][idx2]); 1674431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(qPt.approximatelyDEqual(lPt)); 16807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 16907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (approximately_negative(t - t2s) || approximately_positive(t - t2e)) { 17007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 17107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 172d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com tsFound.push_back(rootTs[0][idx2]); 17307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 17407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 17507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int tCount = tsFound.count(); 17607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (tCount <= 0) { 17707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 17807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 17907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double tMin, tMax; 18007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (tCount == 1) { 18107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com tMin = tMax = tsFound[0]; 182a3e500cee9fb1750bfd4a05901636d6fcbda597creed@google.com } else { 183a3e500cee9fb1750bfd4a05901636d6fcbda597creed@google.com SkASSERT(tCount > 1); 184b76d3b677713693137936ff813b92c4be48af173commit-bot@chromium.org SkTQSort<double>(tsFound.begin(), tsFound.end() - 1); 18507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com tMin = tsFound[0]; 18607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com tMax = tsFound[tsFound.count() - 1]; 18707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1884fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint end = q2.ptAtT(t2s); 18907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool startInTriangle = hull.pointInHull(end); 19007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (startInTriangle) { 19107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com tMin = t2s; 19207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1934fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com end = q2.ptAtT(t2e); 19407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool endInTriangle = hull.pointInHull(end); 19507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (endInTriangle) { 19607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com tMax = t2e; 19707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 19807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int split = 0; 19907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector dxy1, dxy2; 20007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (tMin != tMax || tCount > 2) { 20107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dxy2 = q2.dxdyAtT(tMin); 20207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int index = 1; index < tCount; ++index) { 20307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dxy1 = dxy2; 20407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dxy2 = q2.dxdyAtT(tsFound[index]); 20507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dot = dxy1.dot(dxy2); 20607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (dot < 0) { 20707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com split = index - 1; 20807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com break; 20907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (split == 0) { // there's one point 21307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (add_intercept(q1, q2, tMin, tMax, i, subDivide)) { 21407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 21507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i->swap(); 21707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return is_linear_inner(q2, tMin, tMax, q1, t1s, t1e, i, subDivide); 21807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // At this point, we have two ranges of t values -- treat each separately at the split 22007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool result; 22107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (add_intercept(q1, q2, tMin, tsFound[split - 1], i, subDivide)) { 22207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com result = true; 22307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 22407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i->swap(); 22507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com result = is_linear_inner(q2, tMin, tsFound[split - 1], q1, t1s, t1e, i, subDivide); 22607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 22707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (add_intercept(q1, q2, tsFound[split], tMax, i, subDivide)) { 22807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com result = true; 22907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 23007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i->swap(); 23107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com result |= is_linear_inner(q2, tsFound[split], tMax, q1, t1s, t1e, i, subDivide); 23207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 23307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return result; 23407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 23507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 23607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic double flat_measure(const SkDQuad& q) { 23707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector mid = q[1] - q[0]; 23807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector dxy = q[2] - q[0]; 23907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double length = dxy.length(); // OPTIMIZE: get rid of sqrt 24007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fabs(mid.cross(dxy) / length); 24107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 24207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 24307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// FIXME ? should this measure both and then use the quad that is the flattest as the line? 24407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic bool is_linear(const SkDQuad& q1, const SkDQuad& q2, SkIntersections* i) { 24507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double measure = flat_measure(q1); 24607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // OPTIMIZE: (get rid of sqrt) use approximately_zero 24707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!approximately_zero_sqrt(measure)) { 24807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 24907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 25007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return is_linear_inner(q1, 0, 1, q2, 0, 1, i, NULL); 25107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 25207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 25307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// FIXME: if flat measure is sufficiently large, then probably the quartic solution failed 2547eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com// avoid imprecision incurred with chopAt 255b0a0589f8ac0254ec1beba9db2fc32a2bedb31e5skia.committer@gmail.comstatic void relaxed_is_linear(const SkDQuad* q1, double s1, double e1, const SkDQuad* q2, 2567eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com double s2, double e2, SkIntersections* i) { 2577eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com double m1 = flat_measure(*q1); 2587eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com double m2 = flat_measure(*q2); 25907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i->reset(); 2607eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com const SkDQuad* rounder, *flatter; 2617eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com double sf, midf, ef, sr, er; 2627eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (m2 < m1) { 2637eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com rounder = q1; 2647eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com sr = s1; 2657eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com er = e1; 2667eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com flatter = q2; 2677eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com sf = s2; 2687eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com midf = (s2 + e2) / 2; 2697eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com ef = e2; 2707eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } else { 2717eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com rounder = q2; 2727eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com sr = s2; 2737eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com er = e2; 2747eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com flatter = q1; 2757eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com sf = s1; 2767eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com midf = (s1 + e1) / 2; 2777eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com ef = e1; 2787eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 27907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool subDivide = false; 2807eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com is_linear_inner(*flatter, sf, ef, *rounder, sr, er, i, &subDivide); 28107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (subDivide) { 2827eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com relaxed_is_linear(flatter, sf, midf, rounder, sr, er, i); 2837eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com relaxed_is_linear(flatter, midf, ef, rounder, sr, er, i); 28407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 28507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (m2 < m1) { 28607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i->swapPts(); 28707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 28807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 28907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 29007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// each time through the loop, this computes values it had from the last loop 29107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// if i == j == 1, the center values are still good 29207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// otherwise, for i != 1 or j != 1, four of the values are still good 29307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// and if i == 1 ^ j == 1, an additional value is good 29407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1Seed, 29507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double* t2Seed, SkDPoint* pt) { 29607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double tStep = ROUGH_EPSILON; 29707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDPoint t1[3], t2[3]; 29807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int calcMask = ~0; 29907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 3004fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (calcMask & (1 << 1)) t1[1] = quad1.ptAtT(*t1Seed); 3014fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (calcMask & (1 << 4)) t2[1] = quad2.ptAtT(*t2Seed); 30207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (t1[1].approximatelyEqual(t2[1])) { 30307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *pt = t1[1]; 30407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #if ONE_OFF_DEBUG 30507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __FUNCTION__, 306a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com t1Seed, t2Seed, t1[1].fX, t1[1].fY, t2[1].fX, t2[1].fY); 30707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 30807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 30907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(SkTMax(0., *t1Seed - tStep)); 3114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(SkTMin(1., *t1Seed + tStep)); 3124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(SkTMax(0., *t2Seed - tStep)); 3134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(SkTMin(1., *t2Seed + tStep)); 31407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dist[3][3]; 31507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // OPTIMIZE: using calcMask value permits skipping some distance calcuations 31607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // if prior loop's results are moved to correct slot for reuse 31707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dist[1][1] = t1[1].distanceSquared(t2[1]); 31807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int best_i = 1, best_j = 1; 31907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int i = 0; i < 3; ++i) { 32007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int j = 0; j < 3; ++j) { 32107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (i == 1 && j == 1) { 32207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 32307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 32407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dist[i][j] = t1[i].distanceSquared(t2[j]); 32507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (dist[best_i][best_j] > dist[i][j]) { 32607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com best_i = i; 32707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com best_j = j; 32807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 32907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 33007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 33107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (best_i == 1 && best_j == 1) { 33207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com tStep /= 2; 33307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (tStep < FLT_EPSILON_HALF) { 33407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com break; 33507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 33607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com calcMask = (1 << 0) | (1 << 2) | (1 << 3) | (1 << 5); 33707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 33807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 33907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (best_i == 0) { 34007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *t1Seed -= tStep; 34107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t1[2] = t1[1]; 34207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t1[1] = t1[0]; 34307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com calcMask = 1 << 0; 34407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else if (best_i == 2) { 34507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *t1Seed += tStep; 34607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t1[0] = t1[1]; 34707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t1[1] = t1[2]; 34807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com calcMask = 1 << 2; 34907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 35007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com calcMask = 0; 35107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 35207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (best_j == 0) { 35307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *t2Seed -= tStep; 35407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t2[2] = t2[1]; 35507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t2[1] = t2[0]; 35607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com calcMask |= 1 << 3; 35707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else if (best_j == 2) { 35807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *t2Seed += tStep; 35907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t2[0] = t2[1]; 36007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t2[1] = t2[2]; 36107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com calcMask |= 1 << 5; 36207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 36307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } while (true); 36407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if ONE_OFF_DEBUG 36507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) != (%1.9g,%1.9g) %s\n", __FUNCTION__, 36607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t1Seed, t2Seed, t1[1].fX, t1[1].fY, t1[2].fX, t1[2].fY); 36707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 36807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 36907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 37007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 3714fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.comstatic void lookNearEnd(const SkDQuad& q1, const SkDQuad& q2, int testT, 3724fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com const SkIntersections& orig, bool swap, SkIntersections* i) { 3734fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (orig.used() == 1 && orig[!swap][0] == testT) { 3744fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return; 3754fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 3764fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (orig.used() == 2 && orig[!swap][1] == testT) { 3774fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return; 3784fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 3794fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDLine tmpLine; 3804fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com int testTIndex = testT << 1; 3814fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com tmpLine[0] = tmpLine[1] = q2[testTIndex]; 3824fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com tmpLine[1].fX += q2[1].fY - q2[testTIndex].fY; 3834fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com tmpLine[1].fY -= q2[1].fX - q2[testTIndex].fX; 3844fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkIntersections impTs; 3854fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com impTs.intersectRay(q1, tmpLine); 3864fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com for (int index = 0; index < impTs.used(); ++index) { 3874fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint realPt = impTs.pt(index); 3884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!tmpLine[0].approximatelyPEqual(realPt)) { 3894fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com continue; 3904fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 3914fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (swap) { 3924fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com i->insert(testT, impTs[0][index], tmpLine[0]); 3934fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } else { 3944fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com i->insert(impTs[0][index], testT, tmpLine[0]); 3954fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 3964fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 3974fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com} 3984fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com 39907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { 4007eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 4; 40107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // if the quads share an end point, check to see if they overlap 402b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com for (int i1 = 0; i1 < 3; i1 += 2) { 403b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com for (int i2 = 0; i2 < 3; i2 += 2) { 404866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (q1[i1].asSkPoint() == q2[i2].asSkPoint()) { 405b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com insert(i1 >> 1, i2 >> 1, q1[i1]); 406b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com } 407b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com } 408570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 409b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com SkASSERT(fUsed < 3); 410b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com if (only_end_pts_in_common(q1, q2)) { 41107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fUsed; 41207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 413b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com if (only_end_pts_in_common(q2, q1)) { 41407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fUsed; 41507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 41607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // see if either quad is really a line 4174fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com // FIXME: figure out why reduce step didn't find this earlier 41807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (is_linear(q1, q2, this)) { 41907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fUsed; 42007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 421b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com SkIntersections swapped; 4227eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com swapped.setMax(fMax); 423b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com if (is_linear(q2, q1, &swapped)) { 424b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com swapped.swapPts(); 425dac1d17027dcaa5596885a9f333979418b35001ccaryclark *this = swapped; 42607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fUsed; 42707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 4284fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkIntersections copyI(*this); 4294fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com lookNearEnd(q1, q2, 0, *this, false, ©I); 4304fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com lookNearEnd(q1, q2, 1, *this, false, ©I); 4314fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com lookNearEnd(q2, q1, 0, *this, true, ©I); 4324fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com lookNearEnd(q2, q1, 1, *this, true, ©I); 4334fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com int innerEqual = 0; 4344fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (copyI.fUsed >= 2) { 4354fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkASSERT(copyI.fUsed <= 4); 4364fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double width = copyI[0][1] - copyI[0][0]; 4374fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com int midEnd = 1; 4384fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com for (int index = 2; index < copyI.fUsed; ++index) { 4394fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double testWidth = copyI[0][index] - copyI[0][index - 1]; 4404fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (testWidth <= width) { 4414fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com continue; 4424fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4434fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com midEnd = index; 44407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 4454fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com for (int index = 0; index < 2; ++index) { 4464fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double testT = (copyI[0][midEnd] * (index + 1) 4474fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com + copyI[0][midEnd - 1] * (2 - index)) / 3; 4484fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint testPt1 = q1.ptAtT(testT); 4494fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com testT = (copyI[1][midEnd] * (index + 1) + copyI[1][midEnd - 1] * (2 - index)) / 3; 4504fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint testPt2 = q2.ptAtT(testT); 4514fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com innerEqual += testPt1.approximatelyEqual(testPt2); 45207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 4534fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4544fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com bool expectCoincident = copyI.fUsed >= 2 && innerEqual == 2; 4554fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (expectCoincident) { 4564fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com reset(); 4574fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com insertCoincident(copyI[0][0], copyI[1][0], copyI.fPt[0]); 4584fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com int last = copyI.fUsed - 1; 4594fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com insertCoincident(copyI[0][last], copyI[1][last], copyI.fPt[last]); 46007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fUsed; 46107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 4624fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDQuadImplicit i1(q1); 4634fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDQuadImplicit i2(q2); 46407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int index; 465cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com bool flip1 = q1[2] == q2[0]; 466cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com bool flip2 = q1[0] == q2[2]; 467cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com bool useCubic = q1[0] == q2[0]; 46807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double roots1[4]; 469cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); 47007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1 47107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double roots1Copy[4]; 47207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int r1Count = addValidRoots(roots1, rootCount, roots1Copy); 47307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDPoint pts1[4]; 47407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (index = 0; index < r1Count; ++index) { 4754fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com pts1[index] = q1.ptAtT(roots1Copy[index]); 47607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 47707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double roots2[4]; 478cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); 47907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double roots2Copy[4]; 48007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int r2Count = addValidRoots(roots2, rootCount2, roots2Copy); 48107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDPoint pts2[4]; 48207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (index = 0; index < r2Count; ++index) { 4834fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com pts2[index] = q2.ptAtT(roots2Copy[index]); 48407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 48507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (r1Count == r2Count && r1Count <= 1) { 486a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (r1Count == 1 && used() == 0) { 4877eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (pts1[0].approximatelyEqual(pts2[0])) { 48807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com insert(roots1Copy[0], roots2Copy[0], pts1[0]); 48907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else if (pts1[0].moreRoughlyEqual(pts2[0])) { 49007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // experiment: try to find intersection by chasing t 49107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) { 49207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com insert(roots1Copy[0], roots2Copy[0], pts1[0]); 49307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 49407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 49507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 49607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fUsed; 49707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 49807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int closest[4]; 49907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dist[4]; 50007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool foundSomething = false; 50107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (index = 0; index < r1Count; ++index) { 50207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dist[index] = DBL_MAX; 50307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com closest[index] = -1; 50407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int ndex2 = 0; ndex2 < r2Count; ++ndex2) { 5057eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (!pts2[ndex2].approximatelyEqual(pts1[index])) { 50607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 50707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 50807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dx = pts2[ndex2].fX - pts1[index].fX; 50907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dy = pts2[ndex2].fY - pts1[index].fY; 51007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double distance = dx * dx + dy * dy; 51107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (dist[index] <= distance) { 51207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 51307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 51407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int outer = 0; outer < index; ++outer) { 51507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (closest[outer] != ndex2) { 51607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 51707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 51807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (dist[outer] < distance) { 51907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com goto next; 52007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 52107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com closest[outer] = -1; 52207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 52307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dist[index] = distance; 52407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com closest[index] = ndex2; 52507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com foundSomething = true; 52607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com next: 52707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ; 52807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 52907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 53007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (r1Count && r2Count && !foundSomething) { 5317eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com relaxed_is_linear(&q1, 0, 1, &q2, 0, 1, this); 53207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fUsed; 53307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 53407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int used = 0; 53507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 53607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double lowest = DBL_MAX; 53707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int lowestIndex = -1; 53807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (index = 0; index < r1Count; ++index) { 53907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (closest[index] < 0) { 54007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 54107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 54207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (roots1Copy[index] < lowest) { 54307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com lowestIndex = index; 54407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com lowest = roots1Copy[index]; 54507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 54607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 54707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (lowestIndex < 0) { 54807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com break; 54907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 55007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], 55107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com pts1[lowestIndex]); 55207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com closest[lowestIndex] = -1; 55307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } while (++used < r1Count); 55407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fUsed; 55507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 556