1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkGeometry.h" 98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkMatrix.h" 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.orgbool SkXRayCrossesLine(const SkXRay& pt, 12def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org const SkPoint pts[2], 13def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org bool* ambiguous) { 142e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 152e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = false; 162e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 17945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Determine quick discards. 18945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Consider query line going exactly through point 0 to not 19945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // intersect, for symmetry with SkXRayCrossesMonotonicCubic. 202e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (pt.fY == pts[0].fY) { 212e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 222e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = true; 232e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 24945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 252e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 26945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fY < pts[0].fY && pt.fY < pts[1].fY) 27945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 28945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fY > pts[0].fY && pt.fY > pts[1].fY) 29945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 30945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fX > pts[0].fX && pt.fX > pts[1].fX) 31945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 32945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Determine degenerate cases 33945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (SkScalarNearlyZero(pts[0].fY - pts[1].fY)) 34945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 352e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (SkScalarNearlyZero(pts[0].fX - pts[1].fX)) { 36945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // We've already determined the query point lies within the 37945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // vertical range of the line segment. 382e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (pt.fX <= pts[0].fX) { 392e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 402e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = (pt.fY == pts[1].fY); 412e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 422e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org return true; 432e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 442e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org return false; 452e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 462e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org // Ambiguity check 472e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (pt.fY == pts[1].fY) { 482e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (pt.fX <= pts[1].fX) { 492e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 502e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = true; 512e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 522e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org return true; 532e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 542e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org return false; 552e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 56945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Full line segment evaluation 57945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar delta_y = pts[1].fY - pts[0].fY; 58945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar delta_x = pts[1].fX - pts[0].fX; 59945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar slope = SkScalarDiv(delta_y, delta_x); 60945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar b = pts[0].fY - SkScalarMul(slope, pts[0].fX); 61945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Solve for x coordinate at y = pt.fY 62945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar x = SkScalarDiv(pt.fY - b, slope); 63945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return pt.fX <= x; 64945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com} 65945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** If defined, this makes eval_quad and eval_cubic do more setup (sometimes 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com involving integer multiplies by 2 or 3, but fewer calls to SkScalarMul. 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com May also introduce overflow of fixed when we compute our setup. 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 708f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com// #define DIRECT_EVAL_OF_POLYNOMIALS 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//////////////////////////////////////////////////////////////////////// 738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 74b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic int is_not_monotonic(SkScalar a, SkScalar b, SkScalar c) { 75b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar ab = a - b; 76b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar bc = b - c; 778f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com if (ab < 0) { 788f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com bc = -bc; 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 808f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com return ab == 0 || bc < 0; 818f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com} 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//////////////////////////////////////////////////////////////////////// 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 85b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic bool is_unit_interval(SkScalar x) { 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return x > 0 && x < SK_Scalar1; 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 89b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic int valid_unit_divide(SkScalar numer, SkScalar denom, SkScalar* ratio) { 908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(ratio); 918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 92b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (numer < 0) { 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com numer = -numer; 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com denom = -denom; 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 97b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (denom == 0 || numer == 0 || numer >= denom) { 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 99b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 1008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar r = SkScalarDiv(numer, denom); 10215161620bee33efcb706685486c9ce0fb51a72bbreed@android.com if (SkScalarIsNaN(r)) { 10315161620bee33efcb706685486c9ce0fb51a72bbreed@android.com return 0; 10415161620bee33efcb706685486c9ce0fb51a72bbreed@android.com } 1058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(r >= 0 && r < SK_Scalar1); 106b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (r == 0) { // catch underflow if numer <<<< denom 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 108b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *ratio = r; 1108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1; 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** From Numerical Recipes in C. 1148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Q = -1/2 (B + sign(B) sqrt[B*B - 4*A*C]) 1168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com x1 = Q / A 1178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com x2 = C / Q 1188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 119b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]) { 1208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(roots); 1218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 122b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (A == 0) { 1238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return valid_unit_divide(-C, B, roots); 124b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 1258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar* r = roots; 1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 128b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar R = B*B - 4*A*C; 12915161620bee33efcb706685486c9ce0fb51a72bbreed@android.com if (R < 0 || SkScalarIsNaN(R)) { // complex roots 1308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 13115161620bee33efcb706685486c9ce0fb51a72bbreed@android.com } 132b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org R = SkScalarSqrt(R); 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Q = (B < 0) ? -(B-R)/2 : -(B+R)/2; 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r += valid_unit_divide(Q, A, r); 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r += valid_unit_divide(C, Q, r); 137b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (r - roots == 2) { 1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (roots[0] > roots[1]) 1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTSwap<SkScalar>(roots[0], roots[1]); 1408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else if (roots[0] == roots[1]) // nearly-equal? 1418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r -= 1; // skip the double root 1428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (int)(r - roots); 1448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1468f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com/////////////////////////////////////////////////////////////////////////////// 1478f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com/////////////////////////////////////////////////////////////////////////////// 1488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 149b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar eval_quad(const SkScalar src[], SkScalar t) { 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 1528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef DIRECT_EVAL_OF_POLYNOMIALS 1548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = src[0]; 1558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[4] - 2 * src[2] + C; 1568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 2 * (src[2] - C); 1578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 1588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 1598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar ab = SkScalarInterp(src[0], src[2], t); 160fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com SkScalar bc = SkScalarInterp(src[2], src[4], t); 1618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarInterp(ab, bc, t); 1628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 1638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 165b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar eval_quad_derivative(const SkScalar src[], SkScalar t) { 1668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[4] - 2 * src[2] + src[0]; 1678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = src[2] - src[0]; 1688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 2 * SkScalarMulAdd(A, t, B); 1708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 172b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar eval_quad_derivative_at_half(const SkScalar src[]) { 1738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[4] - 2 * src[2] + src[0]; 1748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = src[2] - src[0]; 1758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return A + 2 * B; 1768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 178b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, 179b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkVector* tangent) { 1808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 1818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 1828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 183b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (pt) { 1848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com pt->set(eval_quad(&src[0].fX, t), eval_quad(&src[0].fY, t)); 185b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 186b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (tangent) { 1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tangent->set(eval_quad_derivative(&src[0].fX, t), 1888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com eval_quad_derivative(&src[0].fY, t)); 189b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 1908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 192b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkEvalQuadAtHalf(const SkPoint src[3], SkPoint* pt, SkVector* tangent) { 1938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 1948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 195b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (pt) { 1968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 1978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 1988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 1998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com pt->set(SkScalarAve(x01, x12), SkScalarAve(y01, y12)); 2018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 202b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (tangent) { 2038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tangent->set(eval_quad_derivative_at_half(&src[0].fX), 2048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com eval_quad_derivative_at_half(&src[0].fY)); 205b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 2068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 208b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic void interp_quad_coords(const SkScalar* src, SkScalar* dst, SkScalar t) { 2098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar ab = SkScalarInterp(src[0], src[2], t); 2108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bc = SkScalarInterp(src[2], src[4], t); 2118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0] = src[0]; 2138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2] = ab; 2148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[4] = SkScalarInterp(ab, bc, t); 2158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[6] = bc; 2168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[8] = src[4]; 2178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 219b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t) { 2208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t > 0 && t < SK_Scalar1); 2218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com interp_quad_coords(&src[0].fX, &dst[0].fX, t); 2238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com interp_quad_coords(&src[0].fY, &dst[0].fY, t); 2248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 226b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]) { 2278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 2288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 2298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 2308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 2318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0] = src[0]; 2338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[1].set(x01, y01); 2348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2].set(SkScalarAve(x01, x12), SkScalarAve(y01, y12)); 2358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[3].set(x12, y12); 2368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[4] = src[2]; 2378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Quad'(t) = At + B, where 2408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = 2(a - 2b + c) 2418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = 2(b - a) 2428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Solve for t, only if it fits between 0 < t < 1 2438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 244b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValue[1]) { 2458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /* At + B == 0 2468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com t = -B / A 2478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 2488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return valid_unit_divide(a - b, a - b - b + c, tValue); 2498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 251b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic inline void flatten_double_quad_extrema(SkScalar coords[14]) { 2528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coords[2] = coords[6] = coords[4]; 2538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Returns 0 for 1 quad, and 1 for two quads, either way the answer is 25677f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com stored in dst[]. Guarantees that the 1/2 quads will be monotonic. 25777f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com */ 258b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]) { 2598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 2608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(dst); 261fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 2628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar a = src[0].fY; 2638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar b = src[1].fY; 2648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar c = src[2].fY; 265fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 266b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_not_monotonic(a, b, c)) { 2678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar tValue; 268b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (valid_unit_divide(a - b, a - b - b + c, &tValue)) { 2698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAt(src, dst, tValue); 2708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com flatten_double_quad_extrema(&dst[0].fY); 2718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1; 2728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // if we get here, we need to force dst to be monotonic, even though 2748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we couldn't compute a unit_divide value (probably underflow). 2758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; 2768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0].set(src[0].fX, a); 2788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[1].set(src[1].fX, b); 2798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2].set(src[2].fX, c); 2808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 2818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 28377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com/* Returns 0 for 1 quad, and 1 for two quads, either way the answer is 28477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com stored in dst[]. Guarantees that the 1/2 quads will be monotonic. 28577f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com */ 286b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]) { 28777f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkASSERT(src); 28877f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkASSERT(dst); 289fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 29077f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar a = src[0].fX; 29177f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar b = src[1].fX; 29277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar c = src[2].fX; 293fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 29477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com if (is_not_monotonic(a, b, c)) { 29577f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar tValue; 29677f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com if (valid_unit_divide(a - b, a - b - b + c, &tValue)) { 29777f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkChopQuadAt(src, dst, tValue); 29877f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com flatten_double_quad_extrema(&dst[0].fX); 29977f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com return 1; 30077f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com } 30177f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com // if we get here, we need to force dst to be monotonic, even though 30277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com // we couldn't compute a unit_divide value (probably underflow). 30377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; 30477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com } 30577f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com dst[0].set(a, src[0].fY); 30677f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com dst[1].set(b, src[1].fY); 30777f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com dst[2].set(c, src[2].fY); 30877f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com return 0; 30977f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com} 31077f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com 3118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// F(t) = a (1 - t) ^ 2 + 2 b t (1 - t) + c t ^ 2 3128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// F'(t) = 2 (b - a) + 2 (a - 2b + c) t 3138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// F''(t) = 2 (a - 2b + c) 3148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 3158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// A = 2 (b - a) 3168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// B = 2 (a - 2b + c) 3178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 3188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// Maximum curvature for a quadratic means solving 3198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// Fx' Fx'' + Fy' Fy'' = 0 3208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 3218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// t = - (Ax Bx + Ay By) / (Bx ^ 2 + By ^ 2) 3228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 323b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgSkScalar SkFindQuadMaxCurvature(const SkPoint src[3]) { 3248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ax = src[1].fX - src[0].fX; 3258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ay = src[1].fY - src[0].fY; 3268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Bx = src[0].fX - src[1].fX - src[1].fX + src[2].fX; 3278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar By = src[0].fY - src[1].fY - src[1].fY + src[2].fY; 3288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t = 0; // 0 means don't chop 3298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (void)valid_unit_divide(-(Ax * Bx + Ay * By), Bx * Bx + By * By, &t); 3315383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com return t; 3325383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com} 3338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 334b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]) { 3355383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com SkScalar t = SkFindQuadMaxCurvature(src); 3365383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com if (t == 0) { 3378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 3 * sizeof(SkPoint)); 3388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1; 3395383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com } else { 3408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAt(src, dst, t); 3418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 2; 3428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3458f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com#define SK_ScalarTwoThirds (0.666666666f) 3466fc321a18acc8c6437735007240eefe7054e83b0reed@google.com 3476fc321a18acc8c6437735007240eefe7054e83b0reed@google.comvoid SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]) { 3486fc321a18acc8c6437735007240eefe7054e83b0reed@google.com const SkScalar scale = SK_ScalarTwoThirds; 3496fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[0] = src[0]; 3506fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[1].set(src[0].fX + SkScalarMul(src[1].fX - src[0].fX, scale), 3516fc321a18acc8c6437735007240eefe7054e83b0reed@google.com src[0].fY + SkScalarMul(src[1].fY - src[0].fY, scale)); 3526fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[2].set(src[2].fX + SkScalarMul(src[1].fX - src[2].fX, scale), 3536fc321a18acc8c6437735007240eefe7054e83b0reed@google.com src[2].fY + SkScalarMul(src[1].fY - src[2].fY, scale)); 3546fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[3] = src[2]; 355945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com} 356945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 357b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org////////////////////////////////////////////////////////////////////////////// 358b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org///// CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS ///// 359b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org////////////////////////////////////////////////////////////////////////////// 3608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 361b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic void get_cubic_coeff(const SkScalar pt[], SkScalar coeff[4]) { 3628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[0] = pt[6] + 3*(pt[2] - pt[4]) - pt[0]; 3638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[1] = 3*(pt[4] - pt[2] - pt[2] + pt[0]); 3648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[2] = 3*(pt[2] - pt[0]); 3658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[3] = pt[0]; 3668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 368b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]) { 3698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(pts); 3708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 371b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (cx) { 3728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com get_cubic_coeff(&pts[0].fX, cx); 373b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 374b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (cy) { 3758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com get_cubic_coeff(&pts[0].fY, cy); 376b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 3778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 379b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar eval_cubic(const SkScalar src[], SkScalar t) { 3808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 3818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 3828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 383b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (t == 0) { 3848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return src[0]; 385b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 3868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef DIRECT_EVAL_OF_POLYNOMIALS 3888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar D = src[0]; 3898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[6] + 3*(src[2] - src[4]) - D; 3908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 3*(src[4] - src[2] - src[2] + D); 3918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = 3*(src[2] - D); 3928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); 3948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 3958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar ab = SkScalarInterp(src[0], src[2], t); 3968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bc = SkScalarInterp(src[2], src[4], t); 3978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar cd = SkScalarInterp(src[4], src[6], t); 3988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar abc = SkScalarInterp(ab, bc, t); 3998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bcd = SkScalarInterp(bc, cd, t); 4008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarInterp(abc, bcd, t); 4018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 4028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** return At^2 + Bt + C 4058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 406b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar eval_quadratic(SkScalar A, SkScalar B, SkScalar C, SkScalar t) { 4078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 4088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 4108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 412b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar eval_cubic_derivative(const SkScalar src[], SkScalar t) { 4138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; 4148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 2*(src[4] - 2 * src[2] + src[0]); 4158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = src[2] - src[0]; 4168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return eval_quadratic(A, B, C, t); 4188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 420b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar eval_cubic_2ndDerivative(const SkScalar src[], SkScalar t) { 4218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; 4228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = src[4] - 2 * src[2] + src[0]; 4238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarMulAdd(A, t, B); 4258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 427b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* loc, 428b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkVector* tangent, SkVector* curvature) { 4298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 4308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 4318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 432b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (loc) { 4338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com loc->set(eval_cubic(&src[0].fX, t), eval_cubic(&src[0].fY, t)); 434b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 435b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (tangent) { 4368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tangent->set(eval_cubic_derivative(&src[0].fX, t), 4378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com eval_cubic_derivative(&src[0].fY, t)); 438b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 439b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (curvature) { 4408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com curvature->set(eval_cubic_2ndDerivative(&src[0].fX, t), 4418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com eval_cubic_2ndDerivative(&src[0].fY, t)); 442b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 4438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Cubic'(t) = At^2 + Bt + C, where 4468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = 3(-a + 3(b - c) + d) 4478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = 6(a - 2b + c) 4488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = 3(b - a) 4498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Solve for t, keeping only those that fit betwee 0 < t < 1 4508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 451b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, 452b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar tValues[2]) { 4538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we divide A,B,C by 3 to simplify 4548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = d - a + 3*(b - c); 4558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 2*(a - b - b + c); 4568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = b - a; 4578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkFindUnitQuadRoots(A, B, C, tValues); 4598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 461b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic void interp_cubic_coords(const SkScalar* src, SkScalar* dst, 462b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar t) { 4638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar ab = SkScalarInterp(src[0], src[2], t); 4648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bc = SkScalarInterp(src[2], src[4], t); 4658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar cd = SkScalarInterp(src[4], src[6], t); 4668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar abc = SkScalarInterp(ab, bc, t); 4678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bcd = SkScalarInterp(bc, cd, t); 4688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar abcd = SkScalarInterp(abc, bcd, t); 4698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0] = src[0]; 4718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2] = ab; 4728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[4] = abc; 4738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[6] = abcd; 4748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[8] = bcd; 4758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[10] = cd; 4768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[12] = src[6]; 4778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 479b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t) { 4808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t > 0 && t < SK_Scalar1); 4818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com interp_cubic_coords(&src[0].fX, &dst[0].fX, t); 4838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com interp_cubic_coords(&src[0].fY, &dst[0].fY, t); 4848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 486a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com/* http://code.google.com/p/skia/issues/detail?id=32 487fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 488a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com This test code would fail when we didn't check the return result of 489a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com valid_unit_divide in SkChopCubicAt(... tValues[], int roots). The reason is 490a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com that after the first chop, the parameters to valid_unit_divide are equal 491a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com (thanks to finite float precision and rounding in the subtracts). Thus 492a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com even though the 2nd tValue looks < 1.0, after we renormalize it, we end 493a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com up with 1.0, hence the need to check and just return the last cubic as 494a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com a degenerate clump of 4 points in the sampe place. 495a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com 496a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com static void test_cubic() { 497a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkPoint src[4] = { 498a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.25000, 523.03003 }, 499a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.23999, 522.96002 }, 500a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.21997, 522.89001 }, 501a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.21997, 522.82001 } 502a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com }; 503a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkPoint dst[10]; 504a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkScalar tval[] = { 0.33333334f, 0.99999994f }; 505a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkChopCubicAt(src, dst, tval, 2); 506a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com } 507a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com */ 508a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com 509b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[], 510b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar tValues[], int roots) { 5118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 5128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 5138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = 0; i < roots - 1; i++) 5148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 5158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(is_unit_interval(tValues[i])); 5168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(is_unit_interval(tValues[i+1])); 5178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(tValues[i] < tValues[i+1]); 5188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 5218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 522b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (dst) { 523b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (roots == 0) { // nothing to chop 5248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 4*sizeof(SkPoint)); 525b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { 5268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t = tValues[0]; 5278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint tmp[4]; 5288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 529b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org for (int i = 0; i < roots; i++) { 5308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, t); 531b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (i == roots - 1) { 5328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 533b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 5348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst += 3; 536a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com // have src point to the remaining cubic (after the chop) 5378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(tmp, dst, 4 * sizeof(SkPoint)); 5388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com src = tmp; 539a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com 540a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com // watch out in case the renormalized t isn't in range 541a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com if (!valid_unit_divide(tValues[i+1] - tValues[i], 542a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SK_Scalar1 - tValues[i], &t)) { 543a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com // if we can't, just create a degenerate cubic 544a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com dst[4] = dst[5] = dst[6] = src[3]; 545a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com break; 546a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com } 5478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 552b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]) { 5538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 5548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 5558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 5568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 5578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x23 = SkScalarAve(src[2].fX, src[3].fX); 5588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y23 = SkScalarAve(src[2].fY, src[3].fY); 5598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x012 = SkScalarAve(x01, x12); 5618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y012 = SkScalarAve(y01, y12); 5628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x123 = SkScalarAve(x12, x23); 5638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y123 = SkScalarAve(y12, y23); 5648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0] = src[0]; 5668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[1].set(x01, y01); 5678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2].set(x012, y012); 5688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[3].set(SkScalarAve(x012, x123), SkScalarAve(y012, y123)); 5698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[4].set(x123, y123); 5708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[5].set(x23, y23); 5718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[6] = src[3]; 5728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 574b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic void flatten_double_cubic_extrema(SkScalar coords[14]) { 5758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coords[4] = coords[8] = coords[6]; 5768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that 579def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org the resulting beziers are monotonic in Y. This is called by the scan 580def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org converter. Depending on what is returned, dst[] is treated as follows: 5818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 dst[0..3] is the original cubic 5828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1 dst[0..3] and dst[3..6] are the two new cubics 5838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics 5848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com If dst == null, it is ignored and only the count is returned. 5858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 586bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.comint SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]) { 5878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar tValues[2]; 588bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com int roots = SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY, 589bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com src[3].fY, tValues); 590fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 5918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, tValues, roots); 592bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (dst && roots > 0) { 5938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we do some cleanup to ensure our Y extrema are flat 5948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com flatten_double_cubic_extrema(&dst[0].fY); 595bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (roots == 2) { 5968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com flatten_double_cubic_extrema(&dst[3].fY); 597bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 598bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 599bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com return roots; 600bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com} 601bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com 602bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.comint SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]) { 603bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com SkScalar tValues[2]; 604bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com int roots = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX, 605bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com src[3].fX, tValues); 606fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 607bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com SkChopCubicAt(src, dst, tValues, roots); 608bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (dst && roots > 0) { 609bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // we do some cleanup to ensure our Y extrema are flat 610bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com flatten_double_cubic_extrema(&dst[0].fX); 611bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (roots == 2) { 612bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com flatten_double_cubic_extrema(&dst[3].fX); 613bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 6148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return roots; 6168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** http://www.faculty.idc.ac.il/arik/quality/appendixA.html 6198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Inflection means that curvature is zero. 6218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Curvature is [F' x F''] / [F'^3] 6228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com So we solve F'x X F''y - F'y X F''y == 0 6238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com After some canceling of the cubic term, we get 6248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = b - a 6258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = c - 2b + a 6268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = d - 3c + 3b - a 6278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (BxCy - ByCx)t^2 + (AxCy - AyCx)t + AxBy - AyBx == 0 6288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 629b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[]) { 6308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ax = src[1].fX - src[0].fX; 6318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ay = src[1].fY - src[0].fY; 6328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Bx = src[2].fX - 2 * src[1].fX + src[0].fX; 6338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar By = src[2].fY - 2 * src[1].fY + src[0].fY; 6348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Cx = src[3].fX + 3 * (src[1].fX - src[2].fX) - src[0].fX; 6358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Cy = src[3].fY + 3 * (src[1].fY - src[2].fY) - src[0].fY; 6368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 637def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org return SkFindUnitQuadRoots(Bx*Cy - By*Cx, 638def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org Ax*Cy - Ay*Cx, 639def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org Ax*By - Ay*Bx, 640def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org tValues); 6418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 643b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopCubicAtInflections(const SkPoint src[], SkPoint dst[10]) { 6448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar tValues[2]; 6458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = SkFindCubicInflections(src, tValues); 6468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 647b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (dst) { 648b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (count == 0) { 6498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 4 * sizeof(SkPoint)); 650b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { 6518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, tValues, count); 652b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 6538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count + 1; 6558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 657b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgtemplate <typename T> void bubble_sort(T array[], int count) { 6588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = count - 1; i > 0; --i) 6598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int j = i; j > 0; --j) 6608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (array[j] < array[j-1]) 6618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 6628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T tmp(array[j]); 6638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com array[j] = array[j-1]; 6648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com array[j-1] = tmp; 6658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 668087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com/** 669087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com * Given an array and count, remove all pair-wise duplicates from the array, 670087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com * keeping the existing sorting, and return the new count 671087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com */ 672b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic int collaps_duplicates(SkScalar array[], int count) { 673087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (int n = count; n > 1; --n) { 674087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com if (array[0] == array[1]) { 675087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (int i = 1; i < n; ++i) { 676087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com array[i - 1] = array[i]; 677087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 678087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com count -= 1; 679087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } else { 680087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com array += 1; 681087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 682087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 683087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com return count; 684087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com} 685087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 686087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com#ifdef SK_DEBUG 687087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 688087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com#define TEST_COLLAPS_ENTRY(array) array, SK_ARRAY_COUNT(array) 689087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 690087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.comstatic void test_collaps_duplicates() { 691087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com static bool gOnce; 692087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com if (gOnce) { return; } 693087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com gOnce = true; 694b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src0[] = { 0 }; 695b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src1[] = { 0, 0 }; 696b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src2[] = { 0, 1 }; 697b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src3[] = { 0, 0, 0 }; 698b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src4[] = { 0, 0, 1 }; 699b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src5[] = { 0, 1, 1 }; 700b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src6[] = { 0, 1, 2 }; 701087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com const struct { 702b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar* fData; 703087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int fCount; 704087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int fCollapsedCount; 705087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } data[] = { 706087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src0), 1 }, 707087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src1), 1 }, 708087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src2), 2 }, 709087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src3), 1 }, 710087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src4), 2 }, 711087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src5), 2 }, 712087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src6), 3 }, 713087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com }; 714087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (size_t i = 0; i < SK_ARRAY_COUNT(data); ++i) { 715b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar dst[3]; 716087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com memcpy(dst, data[i].fData, data[i].fCount * sizeof(dst[0])); 717087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int count = collaps_duplicates(dst, data[i].fCount); 718087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkASSERT(data[i].fCollapsedCount == count); 719087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (int j = 1; j < count; ++j) { 720087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkASSERT(dst[j-1] < dst[j]); 721087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 722087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 723087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com} 724087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com#endif 725087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 7263c12840b234e614faf569e80f311a77ce65d9fe0reed@google.comstatic SkScalar SkScalarCubeRoot(SkScalar x) { 727b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org return SkScalarPow(x, 0.3333333f); 7283c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com} 7293c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com 7308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Solve coeff(t) == 0, returning the number of roots that 7318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com lie withing 0 < t < 1. 7328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3] 733fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 734087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com Eliminates repeated roots (so that all tValues are distinct, and are always 735087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com in increasing order. 7368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 737b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic int solve_cubic_poly(const SkScalar coeff[4], SkScalar tValues[3]) { 738b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (SkScalarNearlyZero(coeff[0])) { // we're just a quadratic 7398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues); 7408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 7418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7423c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar a, b, c, Q, R; 7438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 7458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(coeff[0] != 0); 7468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7473c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar inva = SkScalarInvert(coeff[0]); 7483c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com a = coeff[1] * inva; 7493c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com b = coeff[2] * inva; 7503c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com c = coeff[3] * inva; 7518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 7523c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com Q = (a*a - b*3) / 9; 7533c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com R = (2*a*a*a - 9*a*b + 27*c) / 54; 7548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7553c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar Q3 = Q * Q * Q; 7563c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar R2MinusQ3 = R * R - Q3; 7573c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar adiv3 = a / 3; 7588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar* roots = tValues; 7608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar r; 7618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 762b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (R2MinusQ3 < 0) { // we have 3 real roots 763b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar theta = SkScalarACos(R / SkScalarSqrt(Q3)); 764b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar neg2RootQ = -2 * SkScalarSqrt(Q); 7658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 766b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org r = neg2RootQ * SkScalarCos(theta/3) - adiv3; 767b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_unit_interval(r)) { 7688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 769b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 770b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org r = neg2RootQ * SkScalarCos((theta + 2*SK_ScalarPI)/3) - adiv3; 771b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_unit_interval(r)) { 7728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 773b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 774b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org r = neg2RootQ * SkScalarCos((theta - 2*SK_ScalarPI)/3) - adiv3; 775b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_unit_interval(r)) { 7768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 777b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 778087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkDEBUGCODE(test_collaps_duplicates();) 779087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 7808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // now sort the roots 781087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int count = (int)(roots - tValues); 782087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkASSERT((unsigned)count <= 3); 783087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com bubble_sort(tValues, count); 784087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com count = collaps_duplicates(tValues, count); 785087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com roots = tValues + count; // so we compute the proper count below 786b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { // we have 1 real root 7873c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar A = SkScalarAbs(R) + SkScalarSqrt(R2MinusQ3); 7883c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com A = SkScalarCubeRoot(A); 789b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (R > 0) { 7903c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com A = -A; 791b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 792b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (A != 0) { 7933c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com A += Q / A; 794b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 7953c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com r = A - adiv3; 796b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_unit_interval(r)) { 7978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 798b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 7998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 8008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (int)(roots - tValues); 8028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 8038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Looking for F' dot F'' == 0 805fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 8068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = b - a 8078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = c - 2b + a 8088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = d - 3c + 3b - a 8098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' = 3Ct^2 + 6Bt + 3A 8118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F'' = 6Ct + 6B 8128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 8148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 815b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic void formulate_F1DotF2(const SkScalar src[], SkScalar coeff[4]) { 8168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar a = src[2] - src[0]; 8178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar b = src[4] - 2 * src[2] + src[0]; 8188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar c = src[6] + 3 * (src[2] - src[4]) - src[0]; 8198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8203c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeff[0] = c * c; 8213c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeff[1] = 3 * b * c; 8223c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeff[2] = 2 * b * b + c * a; 8233c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeff[3] = a * b; 8248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 8258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Looking for F' dot F'' == 0 827fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 8288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = b - a 8298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = c - 2b + a 8308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = d - 3c + 3b - a 8318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' = 3Ct^2 + 6Bt + 3A 8338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F'' = 6Ct + 6B 8348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 8368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 837b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]) { 8383c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar coeffX[4], coeffY[4]; 8393c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com int i; 8408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com formulate_F1DotF2(&src[0].fX, coeffX); 8428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com formulate_F1DotF2(&src[0].fY, coeffY); 8438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 844b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org for (i = 0; i < 4; i++) { 8453c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeffX[i] += coeffY[i]; 846b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 8478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t[3]; 849b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org int count = solve_cubic_poly(coeffX, t); 8508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int maxCount = 0; 8518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // now remove extrema where the curvature is zero (mins) 8538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // !!!! need a test for this !!!! 854b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org for (i = 0; i < count; i++) { 8558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // if (not_min_curvature()) 856b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (t[i] > 0 && t[i] < SK_Scalar1) { 8578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tValues[maxCount++] = t[i]; 858b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 8598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 8608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return maxCount; 8618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 8628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 863b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], 864b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar tValues[3]) { 8658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t_storage[3]; 8668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 867b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (tValues == NULL) { 8688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tValues = t_storage; 869b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 8708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = SkFindCubicMaxCurvature(src, tValues); 8728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8735383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com if (dst) { 874b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (count == 0) { 8758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 4 * sizeof(SkPoint)); 876b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { 8778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, tValues, count); 878b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 8798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 8808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count + 1; 8818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 8828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 883b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgbool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], 884b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org bool* ambiguous) { 8852e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 8862e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = false; 8872e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 8882e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org 889945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Find the minimum and maximum y of the extrema, which are the 890945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // first and last points since this cubic is monotonic 891945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar min_y = SkMinScalar(cubic[0].fY, cubic[3].fY); 892945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar max_y = SkMaxScalar(cubic[0].fY, cubic[3].fY); 893945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 894945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fY == cubic[0].fY 895945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com || pt.fY < min_y 896945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com || pt.fY > max_y) { 897945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // The query line definitely does not cross the curve 8982e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 8992e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = (pt.fY == cubic[0].fY); 9002e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 901945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 902945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } 903945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 9042e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org bool pt_at_extremum = (pt.fY == cubic[3].fY); 9052e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org 906945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar min_x = 907945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkMinScalar( 908945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkMinScalar( 909945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkMinScalar(cubic[0].fX, cubic[1].fX), 910945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com cubic[2].fX), 911945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com cubic[3].fX); 912945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fX < min_x) { 913945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // The query line definitely crosses the curve 9142e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 9152e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = pt_at_extremum; 9162e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 917945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return true; 918945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } 919945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 920945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar max_x = 921945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkMaxScalar( 922945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkMaxScalar( 923945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkMaxScalar(cubic[0].fX, cubic[1].fX), 924945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com cubic[2].fX), 925945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com cubic[3].fX); 926945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fX > max_x) { 927945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // The query line definitely does not cross the curve 928945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 929945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } 930945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 931945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Do a binary search to find the parameter value which makes y as 932945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // close as possible to the query point. See whether the query 933945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // line's origin is to the left of the associated x coordinate. 934945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 935945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // kMaxIter is chosen as the number of mantissa bits for a float, 936945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // since there's no way we are going to get more precision by 937945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // iterating more times than that. 938945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com const int kMaxIter = 23; 939945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkPoint eval; 940945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com int iter = 0; 941945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar upper_t; 942945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar lower_t; 943945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Need to invert direction of t parameter if cubic goes up 944945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // instead of down 945945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (cubic[3].fY > cubic[0].fY) { 946945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com upper_t = SK_Scalar1; 9474b413c8bb123e42ca4b9c7bfa6bc2167283cb84ccommit-bot@chromium.org lower_t = 0; 948945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } else { 9494b413c8bb123e42ca4b9c7bfa6bc2167283cb84ccommit-bot@chromium.org upper_t = 0; 950945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com lower_t = SK_Scalar1; 951945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } 952945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com do { 953945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar t = SkScalarAve(upper_t, lower_t); 954945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkEvalCubicAt(cubic, t, &eval, NULL, NULL); 955945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fY > eval.fY) { 956945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com lower_t = t; 957945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } else { 958945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com upper_t = t; 959945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } 960945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } while (++iter < kMaxIter 961945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com && !SkScalarNearlyZero(eval.fY - pt.fY)); 962945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fX <= eval.fX) { 9632e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 9642e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = pt_at_extremum; 9652e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 966945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return true; 967945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } 968945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 969945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com} 970945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 971def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.orgint SkNumXRayCrossingsForCubic(const SkXRay& pt, 972def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org const SkPoint cubic[4], 973def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org bool* ambiguous) { 974945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com int num_crossings = 0; 975945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkPoint monotonic_cubics[10]; 976945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com int num_monotonic_cubics = SkChopCubicAtYExtrema(cubic, monotonic_cubics); 9772e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 9782e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = false; 9792e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 9802e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org bool locally_ambiguous; 981def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org if (SkXRayCrossesMonotonicCubic(pt, 982def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org &monotonic_cubics[0], 983def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org &locally_ambiguous)) 984945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com ++num_crossings; 9852e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 9862e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous |= locally_ambiguous; 9872e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 988945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (num_monotonic_cubics > 0) 989def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org if (SkXRayCrossesMonotonicCubic(pt, 990def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org &monotonic_cubics[3], 991def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org &locally_ambiguous)) 992945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com ++num_crossings; 9932e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 9942e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous |= locally_ambiguous; 9952e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 996945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (num_monotonic_cubics > 1) 997def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org if (SkXRayCrossesMonotonicCubic(pt, 998def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org &monotonic_cubics[6], 999def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org &locally_ambiguous)) 1000945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com ++num_crossings; 10012e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 10022e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous |= locally_ambiguous; 10032e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 1004945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return num_crossings; 1005945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com} 1006b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org 1007b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org/////////////////////////////////////////////////////////////////////////////// 10088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Find t value for quadratic [a, b, c] = d. 10108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Return 0 if there is no solution within [0, 1) 10118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1012b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar quad_solve(SkScalar a, SkScalar b, SkScalar c, SkScalar d) { 10138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // At^2 + Bt + C = d 10148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = a - 2 * b + c; 10158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 2 * (b - a); 10168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = a - d; 10178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar roots[2]; 10198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = SkFindUnitQuadRoots(A, B, C, roots); 10208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(count <= 1); 10228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count == 1 ? roots[0] : 0; 10238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 10248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1025e1b75b4096c8ba9a569ae33d580806edd3c4a97arobertphillips@google.com/* given a quad-curve and a point (x,y), chop the quad at that point and place 102650df4d013f840749f70d1759c23c4217e727fd54skia.committer@gmail.com the new off-curve point and endpoint into 'dest'. 10279e1ec1a52985cce9db3a0d0e8d448b82a32e70cbskia.committer@gmail.com Should only return false if the computed pos is the start of the curve 1028e1b75b4096c8ba9a569ae33d580806edd3c4a97arobertphillips@google.com (i.e. root == 0) 10298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1030b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic bool truncate_last_curve(const SkPoint quad[3], SkScalar x, SkScalar y, 1031b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkPoint* dest) { 10328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkScalar* base; 10338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar value; 10348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (SkScalarAbs(x) < SkScalarAbs(y)) { 10368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com base = &quad[0].fX; 10378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com value = x; 10388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 10398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com base = &quad[0].fY; 10408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com value = y; 10418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 10428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // note: this returns 0 if it thinks value is out of range, meaning the 10448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // root might return something outside of [0, 1) 10458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t = quad_solve(base[0], base[2], base[4], value); 10468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1047b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (t > 0) { 10488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint tmp[5]; 10498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAt(quad, tmp, t); 1050e1b75b4096c8ba9a569ae33d580806edd3c4a97arobertphillips@google.com dest[0] = tmp[1]; 1051b0889a5aa610552bf306edc8d9a35d2d601acdb9robertphillips@google.com dest[1].set(x, y); 10528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 10538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 10548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /* t == 0 means either the value triggered a root outside of [0, 1) 10558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com For our purposes, we can ignore the <= 0 roots, but we want to 10568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com catch the >= 1 roots (which given our caller, will basically mean 10578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com a root of 1, give-or-take numerical instability). If we are in the 10588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com >= 1 case, return the existing offCurve point. 1059fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 10608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com The test below checks to see if we are close to the "end" of the 10618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com curve (near base[4]). Rather than specifying a tolerance, I just 10628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com check to see if value is on to the right/left of the middle point 10638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (depending on the direction/sign of the end points). 10648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 10658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((base[0] < base[4] && value > base[2]) || 10668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (base[0] > base[4] && value < base[2])) // should root have been 1 10678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 1068e1b75b4096c8ba9a569ae33d580806edd3c4a97arobertphillips@google.com dest[0] = quad[1]; 1069e1b75b4096c8ba9a569ae33d580806edd3c4a97arobertphillips@google.com dest[1].set(x, y); 10708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 10718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 10728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 10738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 10748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 10758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic const SkPoint gQuadCirclePts[kSkBuildQuadArcStorage] = { 1077f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org// The mid point of the quadratic arc approximation is half way between the two 1078f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org// control points. The float epsilon adjustment moves the on curve point out by 1079def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// two bits, distributing the convex test error between the round rect 1080def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// approximation and the convex cross product sign equality test. 1081def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org#define SK_MID_RRECT_OFFSET \ 1082def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org (SK_Scalar1 + SK_ScalarTanPIOver8 + FLT_EPSILON * 4) / 2 1083f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_Scalar1, 0 }, 1084f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_Scalar1, SK_ScalarTanPIOver8 }, 1085f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_MID_RRECT_OFFSET, SK_MID_RRECT_OFFSET }, 1086f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_ScalarTanPIOver8, SK_Scalar1 }, 1087f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org 1088f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { 0, SK_Scalar1 }, 1089f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_ScalarTanPIOver8, SK_Scalar1 }, 1090f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_MID_RRECT_OFFSET, SK_MID_RRECT_OFFSET }, 1091f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_Scalar1, SK_ScalarTanPIOver8 }, 1092f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org 1093f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_Scalar1, 0 }, 1094f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_Scalar1, -SK_ScalarTanPIOver8 }, 1095f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_MID_RRECT_OFFSET, -SK_MID_RRECT_OFFSET }, 1096f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_ScalarTanPIOver8, -SK_Scalar1 }, 1097f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org 1098f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { 0, -SK_Scalar1 }, 1099f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_ScalarTanPIOver8, -SK_Scalar1 }, 1100f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_MID_RRECT_OFFSET, -SK_MID_RRECT_OFFSET }, 1101f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_Scalar1, -SK_ScalarTanPIOver8 }, 1102f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org 1103f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_Scalar1, 0 } 1104f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org#undef SK_MID_RRECT_OFFSET 11058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 11068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkBuildQuadArc(const SkVector& uStart, const SkVector& uStop, 11088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRotationDirection dir, const SkMatrix* userMatrix, 1109b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkPoint quadPoints[]) { 11108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // rotate by x,y so that uStart is (1.0) 11118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x = SkPoint::DotProduct(uStart, uStop); 11128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y = SkPoint::CrossProduct(uStart, uStop); 11138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar absX = SkScalarAbs(x); 11158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar absY = SkScalarAbs(y); 11168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int pointCount; 11188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // check for (effectively) coincident vectors 11208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // this can happen if our angle is nearly 0 or nearly 180 (y == 0) 11218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // ... we use the dot-prod to distinguish between 0 and 180 (x > 0) 11228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (absY <= SK_ScalarNearlyZero && x > 0 && 11238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ((y >= 0 && kCW_SkRotationDirection == dir) || 11248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (y <= 0 && kCCW_SkRotationDirection == dir))) { 1125fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 11268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // just return the start-point 11278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com quadPoints[0].set(SK_Scalar1, 0); 11288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com pointCount = 1; 11298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1130b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (dir == kCCW_SkRotationDirection) { 11318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com y = -y; 1132b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 11338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // what octant (quadratic curve) is [xy] in? 11348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int oct = 0; 11358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool sameSign = true; 11368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1137b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (0 == y) { 11388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct = 4; // 180 11398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero); 1140b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else if (0 == x) { 11418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero); 1142b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org oct = y > 0 ? 2 : 6; // 90 : 270 1143b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { 1144b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (y < 0) { 11458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct += 4; 1146b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 1147b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if ((x < 0) != (y < 0)) { 11488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct += 2; 11498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sameSign = false; 11508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1151b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if ((absX < absY) == sameSign) { 11528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct += 1; 1153b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 11548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 11558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int wholeCount = oct << 1; 11578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(quadPoints, gQuadCirclePts, (wholeCount + 1) * sizeof(SkPoint)); 11588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkPoint* arc = &gQuadCirclePts[wholeCount]; 1160b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (truncate_last_curve(arc, x, y, &quadPoints[wholeCount + 1])) { 11618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com wholeCount += 2; 11628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 11638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com pointCount = wholeCount + 1; 11648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 11658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // now handle counter-clockwise and the initial unitStart rotation 11678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkMatrix matrix; 11688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix.setSinCos(uStart.fY, uStart.fX); 11698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (dir == kCCW_SkRotationDirection) { 11708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix.preScale(SK_Scalar1, -SK_Scalar1); 11718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 11728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (userMatrix) { 11738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix.postConcat(*userMatrix); 11748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 11758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix.mapPoints(quadPoints, pointCount); 11768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return pointCount; 11778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1178c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 1179c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 1180def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org/////////////////////////////////////////////////////////////////////////////// 1181def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// 1182def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// NURB representation for conics. Helpful explanations at: 1183def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// 1184def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// http://citeseerx.ist.psu.edu/viewdoc/ 1185def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// download?doi=10.1.1.44.5740&rep=rep1&type=ps 1186def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// and 1187def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/NURBS/RB-conics.html 1188def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// 118917a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// F = (A (1 - t)^2 + C t^2 + 2 B (1 - t) t w) 119017a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// ------------------------------------------ 119117a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// ((1 - t)^2 + t^2 + 2 (1 - t) t w) 119217a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// 119317a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// = {t^2 (P0 + P2 - 2 P1 w), t (-2 P0 + 2 P1 w), P0} 119417a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// ------------------------------------------------ 119517a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// {t^2 (2 - 2 w), t (-2 + 2 w), 1} 119617a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// 119717a2c919d095797c364d407a5dbdb4d60533b953reed@google.com 11986862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.orgstatic SkScalar conic_eval_pos(const SkScalar src[], SkScalar w, SkScalar t) { 11990c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkASSERT(src); 12000c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkASSERT(t >= 0 && t <= SK_Scalar1); 120145fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 12020c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar src2w = SkScalarMul(src[2], w); 12030c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar C = src[0]; 12040c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar A = src[4] - 2 * src2w + C; 12050c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar B = 2 * (src2w - C); 12060c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar numer = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 120745fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 12080c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org B = 2 * (w - SK_Scalar1); 12090c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org C = SK_Scalar1; 12100c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org A = -B; 12110c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar denom = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 121245fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 12130c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return SkScalarDiv(numer, denom); 12140c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 121517a2c919d095797c364d407a5dbdb4d60533b953reed@google.com 12160c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org// F' = 2 (C t (1 + t (-1 + w)) - A (-1 + t) (t (-1 + w) - w) + B (1 - 2 t) w) 12170c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org// 12186862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// t^2 : (2 P0 - 2 P2 - 2 P0 w + 2 P2 w) 12196862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// t^1 : (-2 P0 + 2 P2 + 4 P0 w - 4 P1 w) 12206862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// t^0 : -2 P0 w + 2 P1 w 12216862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// 12226862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// We disregard magnitude, so we can freely ignore the denominator of F', and 12236862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// divide the numerator by 2 12240c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org// 122517a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// coeff[0] for t^2 12266862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// coeff[1] for t^1 12276862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// coeff[2] for t^0 122817a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// 1229def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.orgstatic void conic_deriv_coeff(const SkScalar src[], 1230def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org SkScalar w, 1231def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org SkScalar coeff[3]) { 12326862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org const SkScalar P20 = src[4] - src[0]; 12336862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org const SkScalar P10 = src[2] - src[0]; 12346862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org const SkScalar wP10 = w * P10; 12356862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org coeff[0] = w * P20 - P20; 12366862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org coeff[1] = P20 - 2 * wP10; 12376862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org coeff[2] = wP10; 12386862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org} 12396862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org 12406862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.orgstatic SkScalar conic_eval_tan(const SkScalar coord[], SkScalar w, SkScalar t) { 12416862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org SkScalar coeff[3]; 12426862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org conic_deriv_coeff(coord, w, coeff); 12436862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org return t * (t * coeff[0] + coeff[1]) + coeff[2]; 12440c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 12450c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 12466862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.orgstatic bool conic_find_extrema(const SkScalar src[], SkScalar w, SkScalar* t) { 12470c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar coeff[3]; 12486862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org conic_deriv_coeff(src, w, coeff); 12490c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 12500c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar tValues[2]; 12510c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org int roots = SkFindUnitQuadRoots(coeff[0], coeff[1], coeff[2], tValues); 12520c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkASSERT(0 == roots || 1 == roots); 125345fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 12540c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org if (1 == roots) { 12550c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org *t = tValues[0]; 12560c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return true; 12570c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org } 12580c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return false; 125917a2c919d095797c364d407a5dbdb4d60533b953reed@google.com} 126017a2c919d095797c364d407a5dbdb4d60533b953reed@google.com 12610d099557feb99707c8f601746f46f5a295eb33b7reed@google.comstruct SkP3D { 12620d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkScalar fX, fY, fZ; 12634bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 12640d099557feb99707c8f601746f46f5a295eb33b7reed@google.com void set(SkScalar x, SkScalar y, SkScalar z) { 12650d099557feb99707c8f601746f46f5a295eb33b7reed@google.com fX = x; fY = y; fZ = z; 12660d099557feb99707c8f601746f46f5a295eb33b7reed@google.com } 12674bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 12680d099557feb99707c8f601746f46f5a295eb33b7reed@google.com void projectDown(SkPoint* dst) const { 12690d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst->set(fX / fZ, fY / fZ); 12700d099557feb99707c8f601746f46f5a295eb33b7reed@google.com } 12710d099557feb99707c8f601746f46f5a295eb33b7reed@google.com}; 12720d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 1273d50d87a185d26a38d7100bbbb119be17947aa5e4commit-bot@chromium.org// We only interpolate one dimension at a time (the first, at +0, +3, +6). 1274d50d87a185d26a38d7100bbbb119be17947aa5e4commit-bot@chromium.orgstatic void p3d_interp(const SkScalar src[7], SkScalar dst[7], SkScalar t) { 12750d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkScalar ab = SkScalarInterp(src[0], src[3], t); 12760d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkScalar bc = SkScalarInterp(src[3], src[6], t); 12770d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[0] = ab; 12780d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[3] = SkScalarInterp(ab, bc, t); 12790d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[6] = bc; 12800d099557feb99707c8f601746f46f5a295eb33b7reed@google.com} 12810d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 12820d099557feb99707c8f601746f46f5a295eb33b7reed@google.comstatic void ratquad_mapTo3D(const SkPoint src[3], SkScalar w, SkP3D dst[]) { 12830d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[0].set(src[0].fX * 1, src[0].fY * 1, 1); 12840d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[1].set(src[1].fX * w, src[1].fY * w, w); 12850d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[2].set(src[2].fX * 1, src[2].fY * 1, 1); 12860d099557feb99707c8f601746f46f5a295eb33b7reed@google.com} 12870d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 128824bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.comvoid SkConic::evalAt(SkScalar t, SkPoint* pt, SkVector* tangent) const { 1289c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com SkASSERT(t >= 0 && t <= SK_Scalar1); 12904bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 1291c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com if (pt) { 12926862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org pt->set(conic_eval_pos(&fPts[0].fX, fW, t), 12936862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org conic_eval_pos(&fPts[0].fY, fW, t)); 1294c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com } 129524bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com if (tangent) { 129624bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com tangent->set(conic_eval_tan(&fPts[0].fX, fW, t), 129724bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com conic_eval_tan(&fPts[0].fY, fW, t)); 129824bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com } 1299c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com} 1300c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 130128552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::chopAt(SkScalar t, SkConic dst[2]) const { 13020d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkP3D tmp[3], tmp2[3]; 13030d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 13040d099557feb99707c8f601746f46f5a295eb33b7reed@google.com ratquad_mapTo3D(fPts, fW, tmp); 13054bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 13060d099557feb99707c8f601746f46f5a295eb33b7reed@google.com p3d_interp(&tmp[0].fX, &tmp2[0].fX, t); 13070d099557feb99707c8f601746f46f5a295eb33b7reed@google.com p3d_interp(&tmp[0].fY, &tmp2[0].fY, t); 13080d099557feb99707c8f601746f46f5a295eb33b7reed@google.com p3d_interp(&tmp[0].fZ, &tmp2[0].fZ, t); 13094bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 13100d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[0].fPts[0] = fPts[0]; 13110d099557feb99707c8f601746f46f5a295eb33b7reed@google.com tmp2[0].projectDown(&dst[0].fPts[1]); 13120d099557feb99707c8f601746f46f5a295eb33b7reed@google.com tmp2[1].projectDown(&dst[0].fPts[2]); dst[1].fPts[0] = dst[0].fPts[2]; 13130d099557feb99707c8f601746f46f5a295eb33b7reed@google.com tmp2[2].projectDown(&dst[1].fPts[1]); 13140d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[1].fPts[2] = fPts[2]; 13150d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 13164af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // to put in "standard form", where w0 and w2 are both 1, we compute the 13174af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // new w1 as sqrt(w1*w1/w0*w2) 13184af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // or 13194af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // w1 /= sqrt(w0*w2) 13204af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // 1321def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org // However, in our case, we know that for dst[0]: 1322def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org // w0 == 1, and for dst[1], w2 == 1 13234af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // 13244af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org SkScalar root = SkScalarSqrt(tmp2[1].fZ); 13254af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org dst[0].fW = tmp2[0].fZ / root; 13264af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org dst[1].fW = tmp2[2].fZ / root; 1327c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com} 13288d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org 13293df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.orgstatic SkScalar subdivide_w_value(SkScalar w) { 13306862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org return SkScalarSqrt(SK_ScalarHalf + w * SK_ScalarHalf); 13313df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 13323df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 133328552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::chop(SkConic dst[2]) const { 13348d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar scale = SkScalarInvert(SK_Scalar1 + fW); 13358d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar p1x = fW * fPts[1].fX; 13368d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar p1y = fW * fPts[1].fY; 13378d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar mx = (fPts[0].fX + 2 * p1x + fPts[2].fX) * scale * SK_ScalarHalf; 13388d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar my = (fPts[0].fY + 2 * p1y + fPts[2].fY) * scale * SK_ScalarHalf; 13398d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org 13408d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[0].fPts[0] = fPts[0]; 13418d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[0].fPts[1].set((fPts[0].fX + p1x) * scale, 13428d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org (fPts[0].fY + p1y) * scale); 13438d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[0].fPts[2].set(mx, my); 13448d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org 13458d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[1].fPts[0].set(mx, my); 13468d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[1].fPts[1].set((p1x + fPts[2].fX) * scale, 13478d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org (p1y + fPts[2].fY) * scale); 13488d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[1].fPts[2] = fPts[2]; 13498d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org 13503df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org dst[0].fW = dst[1].fW = subdivide_w_value(fW); 13513df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 13523df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 135397514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org/* 135497514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org * "High order approximation of conic sections by quadratic splines" 135597514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org * by Michael Floater, 1993 135697514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org */ 1357af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org#define AS_QUAD_ERROR_SETUP \ 1358af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar a = fW - 1; \ 1359af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar k = a / (4 * (2 + a)); \ 1360af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar x = k * (fPts[0].fX - 2 * fPts[1].fX + fPts[2].fX); \ 1361af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar y = k * (fPts[0].fY - 2 * fPts[1].fY + fPts[2].fY); 1362af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 1363af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.orgvoid SkConic::computeAsQuadError(SkVector* err) const { 1364af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org AS_QUAD_ERROR_SETUP 1365af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org err->set(x, y); 1366af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org} 1367af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 1368af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.orgbool SkConic::asQuadTol(SkScalar tol) const { 1369af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org AS_QUAD_ERROR_SETUP 1370af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org return (x * x + y * y) <= tol * tol; 137197514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org} 13727841c63136e8aa2d3aadbeab8432405abcd73c32skia.committer@gmail.com 137397514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.orgint SkConic::computeQuadPOW2(SkScalar tol) const { 1374af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org AS_QUAD_ERROR_SETUP 1375af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar error = SkScalarSqrt(x * x + y * y) - tol; 1376af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 1377af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org if (error <= 0) { 137897514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org return 0; 13793df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org } 138097514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org uint32_t ierr = (uint32_t)error; 1381af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org return (34 - SkCLZ(ierr)) >> 1; 13823df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 13833df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 138428552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgstatic SkPoint* subdivide(const SkConic& src, SkPoint pts[], int level) { 13853df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org SkASSERT(level >= 0); 1386af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 13873df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org if (0 == level) { 13883df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org memcpy(pts, &src.fPts[1], 2 * sizeof(SkPoint)); 13893df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org return pts + 2; 13903df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org } else { 139128552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org SkConic dst[2]; 13923df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org src.chop(dst); 13933df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org --level; 13943df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org pts = subdivide(dst[0], pts, level); 13953df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org return subdivide(dst[1], pts, level); 13963df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org } 13978d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org} 13983df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 139928552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgint SkConic::chopIntoQuadsPOW2(SkPoint pts[], int pow2) const { 1400af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkASSERT(pow2 >= 0); 14013df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org *pts = fPts[0]; 1402aebfa7e1b1e94f693f3e7beb6ad43cfcb0f69e98reed@google.com SkDEBUGCODE(SkPoint* endPts =) subdivide(*this, pts + 1, pow2); 14033df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org SkASSERT(endPts - pts == (2 * (1 << pow2) + 1)); 14043df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org return 1 << pow2; 14053df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 14060c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 140728552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::findXExtrema(SkScalar* t) const { 14086862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org return conic_find_extrema(&fPts[0].fX, fW, t); 14090c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 14100c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 141128552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::findYExtrema(SkScalar* t) const { 14126862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org return conic_find_extrema(&fPts[0].fY, fW, t); 14130c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 14140c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 141528552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::chopAtXExtrema(SkConic dst[2]) const { 14160c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar t; 14170c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org if (this->findXExtrema(&t)) { 14180c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org this->chopAt(t, dst); 14190c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // now clean-up the middle, since we know t was meant to be at 14200c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // an X-extrema 14210c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar value = dst[0].fPts[2].fX; 14220c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[0].fPts[1].fX = value; 14230c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[0].fX = value; 14240c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[1].fX = value; 14250c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return true; 14260c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org } 14270c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return false; 14280c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 14290c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 143028552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::chopAtYExtrema(SkConic dst[2]) const { 14310c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar t; 14320c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org if (this->findYExtrema(&t)) { 14330c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org this->chopAt(t, dst); 14340c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // now clean-up the middle, since we know t was meant to be at 14350c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // an Y-extrema 14360c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar value = dst[0].fPts[2].fY; 14370c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[0].fPts[1].fY = value; 14380c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[0].fY = value; 14390c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[1].fY = value; 14400c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return true; 14410c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org } 14420c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return false; 14430c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 14440c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 144528552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::computeTightBounds(SkRect* bounds) const { 14465c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org SkPoint pts[4]; 14475c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org pts[0] = fPts[0]; 14485c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org pts[1] = fPts[2]; 14495c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org int count = 2; 14505c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org 14515c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org SkScalar t; 14525c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org if (this->findXExtrema(&t)) { 14535c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org this->evalAt(t, &pts[count++]); 14545c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org } 14555c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org if (this->findYExtrema(&t)) { 14565c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org this->evalAt(t, &pts[count++]); 14575c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org } 14585c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org bounds->set(pts, count); 14595c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org} 14605c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org 146128552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::computeFastBounds(SkRect* bounds) const { 14625c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org bounds->set(fPts, 3); 14635c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org} 1464def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org 1465def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.orgbool SkConic::findMaxCurvature(SkScalar* t) const { 1466def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org // TODO: Implement me 1467def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org return false; 1468def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org} 1469