121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com/* 221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * Copyright 2012 Google Inc. 321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * Use of this source code is governed by a BSD-style license that can be 521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * found in the LICENSE file. 621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com */ 73bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#include "SkIntersections.h" 821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#include "SkLineParameters.h" 921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#include "SkPathOpsCubic.h" 1021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#include "SkPathOpsQuad.h" 1121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#include "SkPathOpsTriangle.h" 1221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 1321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// from http://blog.gludion.com/2009/08/distance-to-quadratic-bezier-curve.html 1421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// (currently only used by testing) 1521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comdouble SkDQuad::nearestT(const SkDPoint& pt) const { 1621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDVector pos = fPts[0] - pt; 1721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // search points P of bezier curve with PM.(dP / dt) = 0 1821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // a calculus leads to a 3d degree equation : 1921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDVector A = fPts[1] - fPts[0]; 2021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDVector B = fPts[2] - fPts[1]; 2121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com B -= A; 2221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double a = B.dot(B); 2321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double b = 3 * A.dot(B); 2421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double c = 2 * A.dot(A) + pos.dot(B); 2521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double d = pos.dot(A); 2621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double ts[3]; 2721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int roots = SkDCubic::RootsValidT(a, b, c, d, ts); 2821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double d0 = pt.distanceSquared(fPts[0]); 2921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double d2 = pt.distanceSquared(fPts[2]); 30b3985896fe7478e1a556e572224503bff2d7d669caryclark@google.com double distMin = SkTMin(d0, d2); 3121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int bestIndex = -1; 3221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int index = 0; index < roots; ++index) { 331a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkDPoint onQuad = ptAtT(ts[index]); 3421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double dist = pt.distanceSquared(onQuad); 3521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (distMin > dist) { 3621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com distMin = dist; 3721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com bestIndex = index; 3821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 3921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 4021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (bestIndex >= 0) { 4121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return ts[bestIndex]; 4221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 4321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return d0 < d2 ? 0 : 1; 4421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 4521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 4621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.combool SkDQuad::pointInHull(const SkDPoint& pt) const { 4721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return ((const SkDTriangle&) fPts).contains(pt); 4821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 4921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 5021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comSkDPoint SkDQuad::top(double startT, double endT) const { 5121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDQuad sub = subDivide(startT, endT); 5221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDPoint topPt = sub[0]; 5321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (topPt.fY > sub[2].fY || (topPt.fY == sub[2].fY && topPt.fX > sub[2].fX)) { 5421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com topPt = sub[2]; 5521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 5621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (!between(sub[0].fY, sub[1].fY, sub[2].fY)) { 5721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double extremeT; 5821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (FindExtrema(sub[0].fY, sub[1].fY, sub[2].fY, &extremeT)) { 5921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com extremeT = startT + (endT - startT) * extremeT; 601a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com SkDPoint test = ptAtT(extremeT); 6121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (topPt.fY > test.fY || (topPt.fY == test.fY && topPt.fX > test.fX)) { 6221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com topPt = test; 6321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 6421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 6521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 6621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return topPt; 6721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 6821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 6921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comint SkDQuad::AddValidTs(double s[], int realRoots, double* t) { 7021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int foundRoots = 0; 7121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int index = 0; index < realRoots; ++index) { 7221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double tValue = s[index]; 7321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (approximately_zero_or_more(tValue) && approximately_one_or_less(tValue)) { 7421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (approximately_less_than_zero(tValue)) { 7521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com tValue = 0; 7621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } else if (approximately_greater_than_one(tValue)) { 7721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com tValue = 1; 7821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 7921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int idx2 = 0; idx2 < foundRoots; ++idx2) { 8021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (approximately_equal(t[idx2], tValue)) { 8121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com goto nextRoot; 8221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 8321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 8421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t[foundRoots++] = tValue; 8521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 8621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comnextRoot: 8721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com {} 8821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 8921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return foundRoots; 9021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 9121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 9221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// note: caller expects multiple results to be sorted smaller first 9321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// note: http://en.wikipedia.org/wiki/Loss_of_significance has an interesting 9421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// analysis of the quadratic equation, suggesting why the following looks at 9521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// the sign of B -- and further suggesting that the greatest loss of precision 9621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// is in b squared less two a c 9721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comint SkDQuad::RootsValidT(double A, double B, double C, double t[2]) { 9821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double s[2]; 9921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int realRoots = RootsReal(A, B, C, s); 10021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int foundRoots = AddValidTs(s, realRoots, t); 10121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return foundRoots; 10221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 10321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 10421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com/* 10521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comNumeric Solutions (5.6) suggests to solve the quadratic by computing 10621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com Q = -1/2(B + sgn(B)Sqrt(B^2 - 4 A C)) 10721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comand using the roots 10821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t1 = Q / A 10921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t2 = C / Q 11021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com*/ 11121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com// this does not discard real roots <= 0 or >= 1 11221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comint SkDQuad::RootsReal(const double A, const double B, const double C, double s[2]) { 11321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com const double p = B / (2 * A); 11421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com const double q = C / A; 11521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (approximately_zero(A) && (approximately_zero_inverse(p) || approximately_zero_inverse(q))) { 11621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (approximately_zero(B)) { 11721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com s[0] = 0; 11821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return C == 0; 11921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 12021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com s[0] = -C / B; 12121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return 1; 12221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 12321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com /* normal form: x^2 + px + q = 0 */ 12421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com const double p2 = p * p; 12521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (!AlmostEqualUlps(p2, q) && p2 < q) { 12621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return 0; 12721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 12821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double sqrt_D = 0; 12921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (p2 > q) { 13021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com sqrt_D = sqrt(p2 - q); 13121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 13221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com s[0] = sqrt_D - p; 13321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com s[1] = -sqrt_D - p; 13421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return 1 + !AlmostEqualUlps(s[0], s[1]); 13521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 13621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 13721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.combool SkDQuad::isLinear(int startIndex, int endIndex) const { 13821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkLineParameters lineParameters; 13921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com lineParameters.quadEndPoints(*this, startIndex, endIndex); 14021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // FIXME: maybe it's possible to avoid this and compare non-normalized 14121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com lineParameters.normalize(); 14221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double distance = lineParameters.controlPtDistance(*this); 14321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return approximately_zero(distance); 14421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 14521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 14621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comSkDCubic SkDQuad::toCubic() const { 14721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDCubic cubic; 14821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com cubic[0] = fPts[0]; 14921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com cubic[2] = fPts[1]; 15021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com cubic[3] = fPts[2]; 15121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3; 15221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3; 15321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3; 15421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3; 15521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return cubic; 15621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 15721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 15821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comSkDVector SkDQuad::dxdyAtT(double t) const { 15921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double a = t - 1; 16021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double b = 1 - 2 * t; 16121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double c = t; 16221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDVector result = { a * fPts[0].fX + b * fPts[1].fX + c * fPts[2].fX, 16321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com a * fPts[0].fY + b * fPts[1].fY + c * fPts[2].fY }; 16421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return result; 16521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 16621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 1672607e2e5a8f13275d86e2242f9906f2106a2fa79caryclark@google.com// OPTIMIZE: assert if caller passes in t == 0 / t == 1 ? 1681a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.comSkDPoint SkDQuad::ptAtT(double t) const { 1691a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (0 == t) { 1701a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com return fPts[0]; 1711a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com } 1721a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com if (1 == t) { 1731a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com return fPts[2]; 1741a4d09d786e54862a38f367490a7e4769f7e73adcaryclark@google.com } 17521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double one_t = 1 - t; 17621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double a = one_t * one_t; 17721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double b = 2 * one_t * t; 17821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double c = t * t; 17921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDPoint result = { a * fPts[0].fX + b * fPts[1].fX + c * fPts[2].fX, 18021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com a * fPts[0].fY + b * fPts[1].fY + c * fPts[2].fY }; 18121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return result; 18221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 18321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 18421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com/* 18521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comGiven a quadratic q, t1, and t2, find a small quadratic segment. 18621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 18721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comThe new quadratic is defined by A, B, and C, where 18821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com A = c[0]*(1 - t1)*(1 - t1) + 2*c[1]*t1*(1 - t1) + c[2]*t1*t1 18921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com C = c[3]*(1 - t1)*(1 - t1) + 2*c[2]*t1*(1 - t1) + c[1]*t1*t1 19021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 19121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comTo find B, compute the point halfway between t1 and t2: 19221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 19321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comq(at (t1 + t2)/2) == D 19421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 19521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comNext, compute where D must be if we know the value of B: 19621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 19721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com_12 = A/2 + B/2 19821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com12_ = B/2 + C/2 19921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com123 = A/4 + B/2 + C/4 20021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com = D 20121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 20221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comGroup the known values on one side: 20321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 20421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comB = D*2 - A/2 - C/2 20521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com*/ 20621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 20721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comstatic double interp_quad_coords(const double* src, double t) { 20821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double ab = SkDInterp(src[0], src[2], t); 20921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double bc = SkDInterp(src[2], src[4], t); 21021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double abc = SkDInterp(ab, bc, t); 21121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return abc; 21221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 21321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 21421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.combool SkDQuad::monotonicInY() const { 21521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return between(fPts[0].fY, fPts[1].fY, fPts[2].fY); 21621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 21721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 21821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comSkDQuad SkDQuad::subDivide(double t1, double t2) const { 21921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDQuad dst; 22021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double ax = dst[0].fX = interp_quad_coords(&fPts[0].fX, t1); 22121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double ay = dst[0].fY = interp_quad_coords(&fPts[0].fY, t1); 22221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double dx = interp_quad_coords(&fPts[0].fX, (t1 + t2) / 2); 22321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double dy = interp_quad_coords(&fPts[0].fY, (t1 + t2) / 2); 22421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double cx = dst[2].fX = interp_quad_coords(&fPts[0].fX, t2); 22521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double cy = dst[2].fY = interp_quad_coords(&fPts[0].fY, t2); 22621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com /* bx = */ dst[1].fX = 2*dx - (ax + cx)/2; 22721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com /* by = */ dst[1].fY = 2*dy - (ay + cy)/2; 22821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return dst; 22921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 23021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 23165e1cb6c52fd6cf5d4df14a9f258df13aa3facfcskia.committer@gmail.comvoid SkDQuad::align(int endIndex, SkDPoint* dstPt) const { 2323bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (fPts[endIndex].fX == fPts[1].fX) { 2333bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com dstPt->fX = fPts[endIndex].fX; 2343bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 2353bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (fPts[endIndex].fY == fPts[1].fY) { 2363bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com dstPt->fY = fPts[endIndex].fY; 2373bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 2383bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com} 2393bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com 24021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comSkDPoint SkDQuad::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2) const { 2413bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkASSERT(t1 != t2); 24221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDPoint b; 2433bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#if 0 2443bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com // this approach assumes that the control point computed directly is accurate enough 24521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double dx = interp_quad_coords(&fPts[0].fX, (t1 + t2) / 2); 24621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double dy = interp_quad_coords(&fPts[0].fY, (t1 + t2) / 2); 24721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com b.fX = 2 * dx - (a.fX + c.fX) / 2; 24821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com b.fY = 2 * dy - (a.fY + c.fY) / 2; 2493bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#else 2503bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkDQuad sub = subDivide(t1, t2); 2513bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkDLine b0 = {{a, sub[1] + (a - sub[0])}}; 2523bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkDLine b1 = {{c, sub[1] + (c - sub[2])}}; 2533bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkIntersections i; 2543bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com i.intersectRay(b0, b1); 2553bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (i.used() == 1) { 2563bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com b = i.pt(0); 2573bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } else { 2583bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com SkASSERT(i.used() == 2 || i.used() == 0); 2593bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com b = SkDPoint::Mid(b0[1], b1[1]); 2603bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 2613bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com#endif 2623bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (t1 == 0 || t2 == 0) { 2633bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com align(0, &b); 2643bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 2653bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (t1 == 1 || t2 == 1) { 2663bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com align(2, &b); 2673bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 2683bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (precisely_subdivide_equal(b.fX, a.fX)) { 2693bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com b.fX = a.fX; 2703bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } else if (precisely_subdivide_equal(b.fX, c.fX)) { 2713bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com b.fX = c.fX; 2723bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 2733bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com if (precisely_subdivide_equal(b.fY, a.fY)) { 2743bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com b.fY = a.fY; 2753bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } else if (precisely_subdivide_equal(b.fY, c.fY)) { 2763bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com b.fY = c.fY; 2773bdb9d9ce8ef9f8b297f65af3c8de018e97459c0caryclark@google.com } 27821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return b; 27921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 28021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 28121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com/* classic one t subdivision */ 28221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comstatic void interp_quad_coords(const double* src, double* dst, double t) { 28321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double ab = SkDInterp(src[0], src[2], t); 28421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double bc = SkDInterp(src[2], src[4], t); 28521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com dst[0] = src[0]; 28621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com dst[2] = ab; 28721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com dst[4] = SkDInterp(ab, bc, t); 28821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com dst[6] = bc; 28921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com dst[8] = src[4]; 29021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 29121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 29221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comSkDQuadPair SkDQuad::chopAt(double t) const 29321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com{ 29421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDQuadPair dst; 29521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com interp_quad_coords(&fPts[0].fX, &dst.pts[0].fX, t); 29621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com interp_quad_coords(&fPts[0].fY, &dst.pts[0].fY, t); 29721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return dst; 29821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 29921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 30021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comstatic int valid_unit_divide(double numer, double denom, double* ratio) 30121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com{ 30221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (numer < 0) { 30321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com numer = -numer; 30421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com denom = -denom; 30521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 30621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (denom == 0 || numer == 0 || numer >= denom) { 30721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return 0; 30821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 30921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double r = numer / denom; 31021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (r == 0) { // catch underflow if numer <<<< denom 31121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return 0; 31221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 31321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com *ratio = r; 31421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return 1; 31521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 31621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 31721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com/** Quad'(t) = At + B, where 31821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com A = 2(a - 2b + c) 31921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com B = 2(b - a) 32021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com Solve for t, only if it fits between 0 < t < 1 32121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com*/ 32221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comint SkDQuad::FindExtrema(double a, double b, double c, double tValue[1]) { 32321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com /* At + B == 0 32421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com t = -B / A 32521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com */ 32621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return valid_unit_divide(a - b, a - b - b + c, tValue); 32721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 32821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 32921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com/* Parameterization form, given A*t*t + 2*B*t*(1-t) + C*(1-t)*(1-t) 33021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 33121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * a = A - 2*B + C 33221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * b = 2*B - 2*C 33321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * c = C 33421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com */ 33521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comvoid SkDQuad::SetABC(const double* quad, double* a, double* b, double* c) { 33621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com *a = quad[0]; // a = A 33721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com *b = 2 * quad[2]; // b = 2*B 33821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com *c = quad[4]; // c = C 33921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com *b -= *c; // b = 2*B - C 34021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com *a -= *b; // a = A - 2*B + C 34121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com *b -= *c; // b = 2*B - 2*C 34221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 343