19e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com/* 29e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Copyright 2012 Google Inc. 39e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * 49e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 59e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * found in the LICENSE file. 69e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com */ 7beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com#include "CubicUtilities.h" 845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com#include "Extrema.h" 927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com#include "QuadraticUtilities.h" 10beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com#include "TriangleUtilities.h" 1127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 12beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com// from http://blog.gludion.com/2009/08/distance-to-quadratic-bezier-curve.html 13beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.comdouble nearestT(const Quadratic& quad, const _Point& pt) { 147ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com _Vector pos = quad[0] - pt; 15beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com // search points P of bezier curve with PM.(dP / dt) = 0 16beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com // a calculus leads to a 3d degree equation : 177ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com _Vector A = quad[1] - quad[0]; 187ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com _Vector B = quad[2] - quad[1]; 19beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com B -= A; 20beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double a = B.dot(B); 21beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double b = 3 * A.dot(B); 22beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double c = 2 * A.dot(A) + pos.dot(B); 23beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double d = pos.dot(A); 24beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double ts[3]; 25beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com int roots = cubicRootsValidT(a, b, c, d, ts); 26beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double d0 = pt.distanceSquared(quad[0]); 27beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double d2 = pt.distanceSquared(quad[2]); 28beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double distMin = SkTMin(d0, d2); 29beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com int bestIndex = -1; 30beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com for (int index = 0; index < roots; ++index) { 31beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com _Point onQuad; 32beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com xy_at_t(quad, ts[index], onQuad.x, onQuad.y); 33beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double dist = pt.distanceSquared(onQuad); 34beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com if (distMin > dist) { 35beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com distMin = dist; 36beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com bestIndex = index; 37beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com } 38beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com } 39beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com if (bestIndex >= 0) { 40beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com return ts[bestIndex]; 41beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com } 42beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com return d0 < d2 ? 0 : 1; 43beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com} 4403f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com 45beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.combool point_in_hull(const Quadratic& quad, const _Point& pt) { 46beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com return pointInTriangle((const Triangle&) quad, pt); 47beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com} 4803f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com 4945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com_Point top(const Quadratic& quad, double startT, double endT) { 5045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com Quadratic sub; 5145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com sub_divide(quad, startT, endT, sub); 5245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point topPt = sub[0]; 5345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (topPt.y > sub[2].y || (topPt.y == sub[2].y && topPt.x > sub[2].x)) { 5445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com topPt = sub[2]; 5545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 5645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (!between(sub[0].y, sub[1].y, sub[2].y)) { 5745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double extremeT; 5845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (findExtrema(sub[0].y, sub[1].y, sub[2].y, &extremeT)) { 5945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com extremeT = startT + (endT - startT) * extremeT; 6045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point test; 6145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com xy_at_t(quad, extremeT, test.x, test.y); 6245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if (topPt.y > test.y || (topPt.y == test.y && topPt.x > test.x)) { 6345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com topPt = test; 6445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 6545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 6645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 6745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com return topPt; 6845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com} 6945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com 70beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com/* 71beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.comNumeric Solutions (5.6) suggests to solve the quadratic by computing 7203f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com Q = -1/2(B + sgn(B)Sqrt(B^2 - 4 A C)) 7303f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.comand using the roots 7403f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com t1 = Q / A 7503f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com t2 = C / Q 7603f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com*/ 779f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.comint add_valid_ts(double s[], int realRoots, double* t) { 789f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com int foundRoots = 0; 799f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com for (int index = 0; index < realRoots; ++index) { 809f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com double tValue = s[index]; 819f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com if (approximately_zero_or_more(tValue) && approximately_one_or_less(tValue)) { 829f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com if (approximately_less_than_zero(tValue)) { 839f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com tValue = 0; 849f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } else if (approximately_greater_than_one(tValue)) { 859f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com tValue = 1; 869f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 879f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com for (int idx2 = 0; idx2 < foundRoots; ++idx2) { 889f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com if (approximately_equal(t[idx2], tValue)) { 899f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com goto nextRoot; 909f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 919f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 929f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com t[foundRoots++] = tValue; 939f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 949f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.comnextRoot: 959f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com ; 969f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 979f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return foundRoots; 989f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com} 999f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com 100a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com// note: caller expects multiple results to be sorted smaller first 101a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com// note: http://en.wikipedia.org/wiki/Loss_of_significance has an interesting 102a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com// analysis of the quadratic equation, suggesting why the following looks at 103a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com// the sign of B -- and further suggesting that the greatest loss of precision 104a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com// is in b squared less two a c 1059f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.comint quadraticRootsValidT(double A, double B, double C, double t[2]) { 1069f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com#if 0 10727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com B *= 2; 10827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com double square = B * B - 4 * A * C; 109235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (approximately_negative(square)) { 110235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (!approximately_positive(square)) { 111235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com return 0; 112235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 113235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com square = 0; 11427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com } 11527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com double squareRt = sqrt(square); 11627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com double Q = (B + (B < 0 ? -squareRt : squareRt)) / -2; 11727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com int foundRoots = 0; 11803f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com double ratio = Q / A; 119a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com if (approximately_zero_or_more(ratio) && approximately_one_or_less(ratio)) { 120a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com if (approximately_less_than_zero(ratio)) { 12103f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com ratio = 0; 122a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } else if (approximately_greater_than_one(ratio)) { 12303f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com ratio = 1; 12478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com } 125a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com t[0] = ratio; 126a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com ++foundRoots; 12727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com } 12803f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com ratio = C / Q; 129a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com if (approximately_zero_or_more(ratio) && approximately_one_or_less(ratio)) { 130a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com if (approximately_less_than_zero(ratio)) { 13103f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com ratio = 0; 132a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } else if (approximately_greater_than_one(ratio)) { 13303f970652e07c6832cae41fa374cb68ca80d472ccaryclark@google.com ratio = 1; 13478e17130f396d8b2157116c2504e357192f87ed1caryclark@google.com } 135a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com if (foundRoots == 0 || !approximately_negative(ratio - t[0])) { 136c899ad9c7fa28234d99479ab09afb6866bbd8dc3caryclark@google.com t[foundRoots++] = ratio; 137a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } else if (!approximately_negative(t[0] - ratio)) { 138a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com t[foundRoots++] = t[0]; 139a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com t[0] = ratio; 140c899ad9c7fa28234d99479ab09afb6866bbd8dc3caryclark@google.com } 14127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com } 1429f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com#else 1439f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com double s[2]; 1449f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com int realRoots = quadraticRootsReal(A, B, C, s); 1459f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com int foundRoots = add_valid_ts(s, realRoots, t); 1469f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com#endif 14727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com return foundRoots; 14827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com} 1498dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 1509f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com// unlike quadratic roots, this does not discard real roots <= 0 or >= 1 1519f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.comint quadraticRootsReal(const double A, const double B, const double C, double s[2]) { 15285ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com const double p = B / (2 * A); 15385ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com const double q = C / A; 15485ec74ca543b13739db1ad55dedd7bdfae4ab1a6caryclark@google.com if (approximately_zero(A) && (approximately_zero_inverse(p) || approximately_zero_inverse(q))) { 1559f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com if (approximately_zero(B)) { 1569f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com s[0] = 0; 1579f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return C == 0; 1589f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 1599f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com s[0] = -C / B; 1609f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return 1; 1619f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 1629f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com /* normal form: x^2 + px + q = 0 */ 1639f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com const double p2 = p * p; 1649f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com#if 0 1659f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com double D = AlmostEqualUlps(p2, q) ? 0 : p2 - q; 1669f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com if (D <= 0) { 1679f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com if (D < 0) { 1689f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return 0; 1699f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 1709f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com s[0] = -p; 1719f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com SkDebugf("[%d] %1.9g\n", 1, s[0]); 1729f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return 1; 1739f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 1749f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com double sqrt_D = sqrt(D); 1759f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com s[0] = sqrt_D - p; 1769f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com s[1] = -sqrt_D - p; 1779f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com SkDebugf("[%d] %1.9g %1.9g\n", 2, s[0], s[1]); 1789f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return 2; 1799f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com#else 1809f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com if (!AlmostEqualUlps(p2, q) && p2 < q) { 1819f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return 0; 1829f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 1839f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com double sqrt_D = 0; 1849f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com if (p2 > q) { 1859f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com sqrt_D = sqrt(p2 - q); 1869f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 1879f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com s[0] = sqrt_D - p; 1889f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com s[1] = -sqrt_D - p; 1899f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com#if 0 1909f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com if (AlmostEqualUlps(s[0], s[1])) { 1919f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com SkDebugf("[%d] %1.9g\n", 1, s[0]); 1929f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } else { 1939f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com SkDebugf("[%d] %1.9g %1.9g\n", 2, s[0], s[1]); 1949f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com } 1959f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com#endif 1969f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return 1 + !AlmostEqualUlps(s[0], s[1]); 1979f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com#endif 1989f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com} 1999f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com 200d0a19eb9140ecb968357f798f06d2b052b51fd89caryclark@google.comvoid toCubic(const Quadratic& quad, Cubic& cubic) { 201d0a19eb9140ecb968357f798f06d2b052b51fd89caryclark@google.com cubic[0] = quad[0]; 202d0a19eb9140ecb968357f798f06d2b052b51fd89caryclark@google.com cubic[2] = quad[1]; 203d0a19eb9140ecb968357f798f06d2b052b51fd89caryclark@google.com cubic[3] = quad[2]; 204d0a19eb9140ecb968357f798f06d2b052b51fd89caryclark@google.com cubic[1].x = (cubic[0].x + cubic[2].x * 2) / 3; 205d0a19eb9140ecb968357f798f06d2b052b51fd89caryclark@google.com cubic[1].y = (cubic[0].y + cubic[2].y * 2) / 3; 206d0a19eb9140ecb968357f798f06d2b052b51fd89caryclark@google.com cubic[2].x = (cubic[3].x + cubic[2].x * 2) / 3; 207d0a19eb9140ecb968357f798f06d2b052b51fd89caryclark@google.com cubic[2].y = (cubic[3].y + cubic[2].y * 2) / 3; 208d0a19eb9140ecb968357f798f06d2b052b51fd89caryclark@google.com} 209d0a19eb9140ecb968357f798f06d2b052b51fd89caryclark@google.com 21005c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.comstatic double derivativeAtT(const double* quad, double t) { 2118dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double a = t - 1; 2128dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double b = 1 - 2 * t; 2138dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double c = t; 21405c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com return a * quad[0] + b * quad[2] + c * quad[4]; 21505c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com} 21605c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com 21705c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.comdouble dx_at_t(const Quadratic& quad, double t) { 21805c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com return derivativeAtT(&quad[0].x, t); 21905c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com} 22005c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com 22105c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.comdouble dy_at_t(const Quadratic& quad, double t) { 22205c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com return derivativeAtT(&quad[0].y, t); 22305c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com} 22405c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com 2257ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com_Vector dxdy_at_t(const Quadratic& quad, double t) { 22605c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com double a = t - 1; 22705c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com double b = 1 - 2 * t; 22805c4bad470722bc4e5e6ae3d79aa8bcf9e732f06caryclark@google.com double c = t; 2297ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com _Vector result = { a * quad[0].x + b * quad[1].x + c * quad[2].x, 2307ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com a * quad[0].y + b * quad[1].y + c * quad[2].y }; 2317ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com return result; 2328dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com} 2338dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 2348dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.comvoid xy_at_t(const Quadratic& quad, double t, double& x, double& y) { 2358dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double one_t = 1 - t; 2368dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double a = one_t * one_t; 2378dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double b = 2 * one_t * t; 2388dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double c = t * t; 2398dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (&x) { 2408dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com x = a * quad[0].x + b * quad[1].x + c * quad[2].x; 2418dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2428dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (&y) { 2438dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com y = a * quad[0].y + b * quad[1].y + c * quad[2].y; 2448dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2458dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com} 24647d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com 24747d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com_Point xy_at_t(const Quadratic& quad, double t) { 24847d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com double one_t = 1 - t; 24947d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com double a = one_t * one_t; 25047d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com double b = 2 * one_t * t; 25147d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com double c = t * t; 25247d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com _Point result = { a * quad[0].x + b * quad[1].x + c * quad[2].x, 25347d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com a * quad[0].y + b * quad[1].y + c * quad[2].y }; 25447d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com return result; 25547d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com} 256