107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Copyright 2012 Google Inc. 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * found in the LICENSE file. 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 7cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#include "SkIntersections.h" 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkLineParameters.h" 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsCubic.h" 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsQuad.h" 1107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsTriangle.h" 1207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// from http://blog.gludion.com/2009/08/distance-to-quadratic-bezier-curve.html 1407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// (currently only used by testing) 1507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comdouble SkDQuad::nearestT(const SkDPoint& pt) const { 1607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector pos = fPts[0] - pt; 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // search points P of bezier curve with PM.(dP / dt) = 0 1807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // a calculus leads to a 3d degree equation : 1907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector A = fPts[1] - fPts[0]; 2007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector B = fPts[2] - fPts[1]; 2107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com B -= A; 2207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double a = B.dot(B); 2307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double b = 3 * A.dot(B); 2407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double c = 2 * A.dot(A) + pos.dot(B); 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double d = pos.dot(A); 2607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double ts[3]; 2707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int roots = SkDCubic::RootsValidT(a, b, c, d, ts); 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double d0 = pt.distanceSquared(fPts[0]); 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double d2 = pt.distanceSquared(fPts[2]); 303b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com double distMin = SkTMin(d0, d2); 3107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int bestIndex = -1; 3207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int index = 0; index < roots; ++index) { 334fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint onQuad = ptAtT(ts[index]); 3407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dist = pt.distanceSquared(onQuad); 3507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (distMin > dist) { 3607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com distMin = dist; 3707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bestIndex = index; 3807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 4007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (bestIndex >= 0) { 4107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return ts[bestIndex]; 4207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 4307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return d0 < d2 ? 0 : 1; 4407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 4507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.combool SkDQuad::pointInHull(const SkDPoint& pt) const { 4707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return ((const SkDTriangle&) fPts).contains(pt); 4807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 4907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 5007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSkDPoint SkDQuad::top(double startT, double endT) const { 5107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuad sub = subDivide(startT, endT); 5207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDPoint topPt = sub[0]; 5307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (topPt.fY > sub[2].fY || (topPt.fY == sub[2].fY && topPt.fX > sub[2].fX)) { 5407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com topPt = sub[2]; 5507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!between(sub[0].fY, sub[1].fY, sub[2].fY)) { 5707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double extremeT; 5807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (FindExtrema(sub[0].fY, sub[1].fY, sub[2].fY, &extremeT)) { 5907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com extremeT = startT + (endT - startT) * extremeT; 604fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint test = ptAtT(extremeT); 6107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (topPt.fY > test.fY || (topPt.fY == test.fY && topPt.fX > test.fX)) { 6207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com topPt = test; 6307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return topPt; 6707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 6807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 6907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkDQuad::AddValidTs(double s[], int realRoots, double* t) { 7007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int foundRoots = 0; 7107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int index = 0; index < realRoots; ++index) { 7207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double tValue = s[index]; 7307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (approximately_zero_or_more(tValue) && approximately_one_or_less(tValue)) { 7407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (approximately_less_than_zero(tValue)) { 7507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com tValue = 0; 7607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else if (approximately_greater_than_one(tValue)) { 7707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com tValue = 1; 7807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int idx2 = 0; idx2 < foundRoots; ++idx2) { 8007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (approximately_equal(t[idx2], tValue)) { 8107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com goto nextRoot; 8207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 8307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 8407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t[foundRoots++] = tValue; 8507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 8607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comnextRoot: 8707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {} 8807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 8907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return foundRoots; 9007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 9107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 9207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// note: caller expects multiple results to be sorted smaller first 9307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// note: http://en.wikipedia.org/wiki/Loss_of_significance has an interesting 9407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// analysis of the quadratic equation, suggesting why the following looks at 9507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// the sign of B -- and further suggesting that the greatest loss of precision 9607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// is in b squared less two a c 9707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkDQuad::RootsValidT(double A, double B, double C, double t[2]) { 9807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double s[2]; 9907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int realRoots = RootsReal(A, B, C, s); 10007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int foundRoots = AddValidTs(s, realRoots, t); 10107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return foundRoots; 10207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 10307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 10407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 10507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comNumeric Solutions (5.6) suggests to solve the quadratic by computing 10607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Q = -1/2(B + sgn(B)Sqrt(B^2 - 4 A C)) 10707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comand using the roots 10807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t1 = Q / A 10907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t2 = C / Q 11007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com*/ 11107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// this does not discard real roots <= 0 or >= 1 11207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkDQuad::RootsReal(const double A, const double B, const double C, double s[2]) { 11307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double p = B / (2 * A); 11407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double q = C / A; 11507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (approximately_zero(A) && (approximately_zero_inverse(p) || approximately_zero_inverse(q))) { 11607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (approximately_zero(B)) { 11707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com s[0] = 0; 11807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return C == 0; 11907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 12007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com s[0] = -C / B; 12107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return 1; 12207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 12307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com /* normal form: x^2 + px + q = 0 */ 12407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double p2 = p * p; 1257eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (!AlmostDequalUlps(p2, q) && p2 < q) { 12607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return 0; 12707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 12807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double sqrt_D = 0; 12907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (p2 > q) { 13007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com sqrt_D = sqrt(p2 - q); 13107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com s[0] = sqrt_D - p; 13307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com s[1] = -sqrt_D - p; 1347eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return 1 + !AlmostDequalUlps(s[0], s[1]); 13507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 13607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 13707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.combool SkDQuad::isLinear(int startIndex, int endIndex) const { 13807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkLineParameters lineParameters; 13907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com lineParameters.quadEndPoints(*this, startIndex, endIndex); 14007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // FIXME: maybe it's possible to avoid this and compare non-normalized 14107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com lineParameters.normalize(); 14207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double distance = lineParameters.controlPtDistance(*this); 14307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return approximately_zero(distance); 14407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 14507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 14607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSkDCubic SkDQuad::toCubic() const { 14707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic cubic; 14807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic[0] = fPts[0]; 14907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic[2] = fPts[1]; 15007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic[3] = fPts[2]; 15107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3; 15207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3; 15307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3; 15407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3; 15507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return cubic; 15607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 15707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 15807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSkDVector SkDQuad::dxdyAtT(double t) const { 15907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double a = t - 1; 16007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double b = 1 - 2 * t; 16107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double c = t; 16207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector result = { a * fPts[0].fX + b * fPts[1].fX + c * fPts[2].fX, 16307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com a * fPts[0].fY + b * fPts[1].fY + c * fPts[2].fY }; 16407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return result; 16507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 16607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 167fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com// OPTIMIZE: assert if caller passes in t == 0 / t == 1 ? 1684fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.comSkDPoint SkDQuad::ptAtT(double t) const { 1694fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (0 == t) { 1704fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return fPts[0]; 1714fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 1724fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (1 == t) { 1734fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return fPts[2]; 1744fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 17507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double one_t = 1 - t; 17607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double a = one_t * one_t; 17707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double b = 2 * one_t * t; 17807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double c = t * t; 17907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDPoint result = { a * fPts[0].fX + b * fPts[1].fX + c * fPts[2].fX, 18007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com a * fPts[0].fY + b * fPts[1].fY + c * fPts[2].fY }; 18107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return result; 18207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 18307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 18407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 18507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comGiven a quadratic q, t1, and t2, find a small quadratic segment. 18607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 18707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comThe new quadratic is defined by A, B, and C, where 18807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com A = c[0]*(1 - t1)*(1 - t1) + 2*c[1]*t1*(1 - t1) + c[2]*t1*t1 18907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com C = c[3]*(1 - t1)*(1 - t1) + 2*c[2]*t1*(1 - t1) + c[1]*t1*t1 19007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 19107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comTo find B, compute the point halfway between t1 and t2: 19207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 19307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comq(at (t1 + t2)/2) == D 19407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 19507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comNext, compute where D must be if we know the value of B: 19607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 19707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com_12 = A/2 + B/2 19807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com12_ = B/2 + C/2 19907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com123 = A/4 + B/2 + C/4 20007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com = D 20107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 20207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comGroup the known values on one side: 20307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 20407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comB = D*2 - A/2 - C/2 20507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com*/ 20607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 20707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic double interp_quad_coords(const double* src, double t) { 20807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double ab = SkDInterp(src[0], src[2], t); 20907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double bc = SkDInterp(src[2], src[4], t); 21007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double abc = SkDInterp(ab, bc, t); 21107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return abc; 21207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 21307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 21407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.combool SkDQuad::monotonicInY() const { 21507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return between(fPts[0].fY, fPts[1].fY, fPts[2].fY); 21607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 21707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 21807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSkDQuad SkDQuad::subDivide(double t1, double t2) const { 21907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuad dst; 22007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double ax = dst[0].fX = interp_quad_coords(&fPts[0].fX, t1); 22107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double ay = dst[0].fY = interp_quad_coords(&fPts[0].fY, t1); 22207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dx = interp_quad_coords(&fPts[0].fX, (t1 + t2) / 2); 22307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dy = interp_quad_coords(&fPts[0].fY, (t1 + t2) / 2); 22407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double cx = dst[2].fX = interp_quad_coords(&fPts[0].fX, t2); 22507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double cy = dst[2].fY = interp_quad_coords(&fPts[0].fY, t2); 22607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com /* bx = */ dst[1].fX = 2*dx - (ax + cx)/2; 22707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com /* by = */ dst[1].fY = 2*dy - (ay + cy)/2; 22807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return dst; 22907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 23007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2318f6ef4010f6835c5ce9ede180e50a6a58512a81eskia.committer@gmail.comvoid SkDQuad::align(int endIndex, SkDPoint* dstPt) const { 232cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fPts[endIndex].fX == fPts[1].fX) { 233cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com dstPt->fX = fPts[endIndex].fX; 234cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 235cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fPts[endIndex].fY == fPts[1].fY) { 236cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com dstPt->fY = fPts[endIndex].fY; 237cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 238cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com} 239cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com 24007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSkDPoint SkDQuad::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2) const { 241cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkASSERT(t1 != t2); 24207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDPoint b; 243cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#if 0 244cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com // this approach assumes that the control point computed directly is accurate enough 24507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dx = interp_quad_coords(&fPts[0].fX, (t1 + t2) / 2); 24607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dy = interp_quad_coords(&fPts[0].fY, (t1 + t2) / 2); 24707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com b.fX = 2 * dx - (a.fX + c.fX) / 2; 24807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com b.fY = 2 * dy - (a.fY + c.fY) / 2; 249cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#else 250cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkDQuad sub = subDivide(t1, t2); 251cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkDLine b0 = {{a, sub[1] + (a - sub[0])}}; 252cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkDLine b1 = {{c, sub[1] + (c - sub[2])}}; 253cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkIntersections i; 254cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com i.intersectRay(b0, b1); 2554431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (i.used() == 1 && i[0][0] >= 0 && i[1][0] >= 0) { 256cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com b = i.pt(0); 257cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } else { 2584431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org SkASSERT(i.used() <= 2); 259cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com b = SkDPoint::Mid(b0[1], b1[1]); 260cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 261cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#endif 262cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (t1 == 0 || t2 == 0) { 263cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com align(0, &b); 264cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 265cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (t1 == 1 || t2 == 1) { 266cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com align(2, &b); 267cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 2684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (AlmostBequalUlps(b.fX, a.fX)) { 269cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com b.fX = a.fX; 2704431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else if (AlmostBequalUlps(b.fX, c.fX)) { 271cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com b.fX = c.fX; 272cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 2734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (AlmostBequalUlps(b.fY, a.fY)) { 274cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com b.fY = a.fY; 2754431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } else if (AlmostBequalUlps(b.fY, c.fY)) { 276cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com b.fY = c.fY; 277cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 27807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return b; 27907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 28007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 28107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* classic one t subdivision */ 28207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic void interp_quad_coords(const double* src, double* dst, double t) { 28307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double ab = SkDInterp(src[0], src[2], t); 28407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double bc = SkDInterp(src[2], src[4], t); 28507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dst[0] = src[0]; 28607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dst[2] = ab; 28707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dst[4] = SkDInterp(ab, bc, t); 28807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dst[6] = bc; 28907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dst[8] = src[4]; 29007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 29107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 29207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSkDQuadPair SkDQuad::chopAt(double t) const 29307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com{ 29407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuadPair dst; 29507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com interp_quad_coords(&fPts[0].fX, &dst.pts[0].fX, t); 29607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com interp_quad_coords(&fPts[0].fY, &dst.pts[0].fY, t); 29707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return dst; 29807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 29907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 30007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic int valid_unit_divide(double numer, double denom, double* ratio) 30107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com{ 30207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (numer < 0) { 30307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com numer = -numer; 30407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com denom = -denom; 30507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 30607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (denom == 0 || numer == 0 || numer >= denom) { 30707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return 0; 30807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 30907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double r = numer / denom; 31007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (r == 0) { // catch underflow if numer <<<< denom 31107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return 0; 31207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 31307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *ratio = r; 31407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return 1; 31507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 31607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 31707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/** Quad'(t) = At + B, where 31807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com A = 2(a - 2b + c) 31907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com B = 2(b - a) 32007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Solve for t, only if it fits between 0 < t < 1 32107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com*/ 32207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkDQuad::FindExtrema(double a, double b, double c, double tValue[1]) { 32307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com /* At + B == 0 32407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t = -B / A 32507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 32607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return valid_unit_divide(a - b, a - b - b + c, tValue); 32707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 32807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 32907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* Parameterization form, given A*t*t + 2*B*t*(1-t) + C*(1-t)*(1-t) 33007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 33107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * a = A - 2*B + C 33207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * b = 2*B - 2*C 33307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * c = C 33407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 33507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comvoid SkDQuad::SetABC(const double* quad, double* a, double* b, double* c) { 33607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *a = quad[0]; // a = A 33707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *b = 2 * quad[2]; // b = 2*B 33807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *c = quad[4]; // c = C 33907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *b -= *c; // b = 2*B - C 34007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *a -= *b; // a = A - 2*B + C 34107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com *b -= *c; // b = 2*B - 2*C 34207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 343