SkGeometry.cpp revision 24bd210f2e2cf66f356b4e98f7801631089b8aa3
1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 8ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkGeometry.h" 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "Sk64.h" 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkMatrix.h" 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 142e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.orgbool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2], bool* ambiguous) { 152e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 162e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = false; 172e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 18945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Determine quick discards. 19945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Consider query line going exactly through point 0 to not 20945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // intersect, for symmetry with SkXRayCrossesMonotonicCubic. 212e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (pt.fY == pts[0].fY) { 222e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 232e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = true; 242e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 25945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 262e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 27945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fY < pts[0].fY && pt.fY < pts[1].fY) 28945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 29945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fY > pts[0].fY && pt.fY > pts[1].fY) 30945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 31945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fX > pts[0].fX && pt.fX > pts[1].fX) 32945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 33945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Determine degenerate cases 34945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (SkScalarNearlyZero(pts[0].fY - pts[1].fY)) 35945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 362e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (SkScalarNearlyZero(pts[0].fX - pts[1].fX)) { 37945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // We've already determined the query point lies within the 38945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // vertical range of the line segment. 392e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (pt.fX <= pts[0].fX) { 402e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 412e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = (pt.fY == pts[1].fY); 422e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 432e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org return true; 442e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 452e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org return false; 462e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 472e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org // Ambiguity check 482e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (pt.fY == pts[1].fY) { 492e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (pt.fX <= pts[1].fX) { 502e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 512e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = true; 522e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 532e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org return true; 542e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 552e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org return false; 562e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 57945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Full line segment evaluation 58945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar delta_y = pts[1].fY - pts[0].fY; 59945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar delta_x = pts[1].fX - pts[0].fX; 60945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar slope = SkScalarDiv(delta_y, delta_x); 61945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar b = pts[0].fY - SkScalarMul(slope, pts[0].fX); 62945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Solve for x coordinate at y = pt.fY 63945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar x = SkScalarDiv(pt.fY - b, slope); 64945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return pt.fX <= x; 65945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com} 66945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** If defined, this makes eval_quad and eval_cubic do more setup (sometimes 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com involving integer multiplies by 2 or 3, but fewer calls to SkScalarMul. 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com May also introduce overflow of fixed when we compute our setup. 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_SCALAR_IS_FIXED 728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com #define DIRECT_EVAL_OF_POLYNOMIALS 738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//////////////////////////////////////////////////////////////////////// 768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_SCALAR_IS_FIXED 788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static int is_not_monotonic(int a, int b, int c, int d) 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (((a - b) | (b - c) | (c - d)) & ((b - a) | (c - b) | (d - c))) >> 31; 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static int is_not_monotonic(int a, int b, int c) 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (((a - b) | (b - c)) & ((b - a) | (c - b))) >> 31; 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static int is_not_monotonic(float a, float b, float c) 898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com float ab = a - b; 918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com float bc = b - c; 928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (ab < 0) 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bc = -bc; 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return ab == 0 || bc < 0; 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//////////////////////////////////////////////////////////////////////// 998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic bool is_unit_interval(SkScalar x) 1018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 1028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return x > 0 && x < SK_Scalar1; 1038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic int valid_unit_divide(SkScalar numer, SkScalar denom, SkScalar* ratio) 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(ratio); 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (numer < 0) 1108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com numer = -numer; 1128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com denom = -denom; 1138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (denom == 0 || numer == 0 || numer >= denom) 1168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 1178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar r = SkScalarDiv(numer, denom); 11915161620bee33efcb706685486c9ce0fb51a72bbreed@android.com if (SkScalarIsNaN(r)) { 12015161620bee33efcb706685486c9ce0fb51a72bbreed@android.com return 0; 12115161620bee33efcb706685486c9ce0fb51a72bbreed@android.com } 1228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(r >= 0 && r < SK_Scalar1); 1238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (r == 0) // catch underflow if numer <<<< denom 1248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 1258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *ratio = r; 1268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1; 1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** From Numerical Recipes in C. 1308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Q = -1/2 (B + sign(B) sqrt[B*B - 4*A*C]) 1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com x1 = Q / A 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com x2 = C / Q 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]) 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 1378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(roots); 1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (A == 0) 1408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return valid_unit_divide(-C, B, roots); 1418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar* r = roots; 1438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_SCALAR_IS_FLOAT 1458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com float R = B*B - 4*A*C; 14615161620bee33efcb706685486c9ce0fb51a72bbreed@android.com if (R < 0 || SkScalarIsNaN(R)) { // complex roots 1478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 14815161620bee33efcb706685486c9ce0fb51a72bbreed@android.com } 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com R = sk_float_sqrt(R); 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Sk64 RR, tmp; 1528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com RR.setMul(B,B); 1548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tmp.setMul(A,C); 1558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tmp.shiftLeft(2); 1568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com RR.sub(tmp); 1578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (RR.isNeg()) 1588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 1598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkFixed R = RR.getSqrt(); 1608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 1618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Q = (B < 0) ? -(B-R)/2 : -(B+R)/2; 1638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r += valid_unit_divide(Q, A, r); 1648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r += valid_unit_divide(C, Q, r); 1658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (r - roots == 2) 1668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 1678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (roots[0] > roots[1]) 1688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTSwap<SkScalar>(roots[0], roots[1]); 1698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else if (roots[0] == roots[1]) // nearly-equal? 1708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r -= 1; // skip the double root 1718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (int)(r - roots); 1738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_SCALAR_IS_FIXED 1768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Trim A/B/C down so that they are all <= 32bits 1778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com and then call SkFindUnitQuadRoots() 1788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic int Sk64FindFixedQuadRoots(const Sk64& A, const Sk64& B, const Sk64& C, SkFixed roots[2]) 1808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 1818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int na = A.shiftToMake32(); 1828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int nb = B.shiftToMake32(); 1838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int nc = C.shiftToMake32(); 1848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int shift = SkMax32(na, SkMax32(nb, nc)); 1868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(shift >= 0); 1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkFindUnitQuadRoots(A.getShiftRight(shift), B.getShiftRight(shift), C.getShiftRight(shift), roots); 1898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 1918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com///////////////////////////////////////////////////////////////////////////////////// 1938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com///////////////////////////////////////////////////////////////////////////////////// 1948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic SkScalar eval_quad(const SkScalar src[], SkScalar t) 1968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 1978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 1988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 1998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef DIRECT_EVAL_OF_POLYNOMIALS 2018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = src[0]; 2028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[4] - 2 * src[2] + C; 2038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 2 * (src[2] - C); 2048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 2058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 2068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar ab = SkScalarInterp(src[0], src[2], t); 207fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com SkScalar bc = SkScalarInterp(src[2], src[4], t); 2088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarInterp(ab, bc, t); 2098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 2108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic SkScalar eval_quad_derivative(const SkScalar src[], SkScalar t) 2138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 2148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[4] - 2 * src[2] + src[0]; 2158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = src[2] - src[0]; 2168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 2 * SkScalarMulAdd(A, t, B); 2188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic SkScalar eval_quad_derivative_at_half(const SkScalar src[]) 2218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 2228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[4] - 2 * src[2] + src[0]; 2238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = src[2] - src[0]; 2248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return A + 2 * B; 2258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent) 2288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 2298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 2308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 2318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (pt) 2338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com pt->set(eval_quad(&src[0].fX, t), eval_quad(&src[0].fY, t)); 2348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (tangent) 2358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tangent->set(eval_quad_derivative(&src[0].fX, t), 2368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com eval_quad_derivative(&src[0].fY, t)); 2378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkEvalQuadAtHalf(const SkPoint src[3], SkPoint* pt, SkVector* tangent) 2408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 2418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 2428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (pt) 2448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 2458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 2468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 2478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 2488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 2498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com pt->set(SkScalarAve(x01, x12), SkScalarAve(y01, y12)); 2508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (tangent) 2528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tangent->set(eval_quad_derivative_at_half(&src[0].fX), 2538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com eval_quad_derivative_at_half(&src[0].fY)); 2548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic void interp_quad_coords(const SkScalar* src, SkScalar* dst, SkScalar t) 2578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 2588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar ab = SkScalarInterp(src[0], src[2], t); 2598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bc = SkScalarInterp(src[2], src[4], t); 2608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0] = src[0]; 2628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2] = ab; 2638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[4] = SkScalarInterp(ab, bc, t); 2648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[6] = bc; 2658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[8] = src[4]; 2668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t) 2698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 2708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t > 0 && t < SK_Scalar1); 2718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com interp_quad_coords(&src[0].fX, &dst[0].fX, t); 2738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com interp_quad_coords(&src[0].fY, &dst[0].fY, t); 2748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]) 2778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 2788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 2798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 2808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 2818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 2828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0] = src[0]; 2848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[1].set(x01, y01); 2858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2].set(SkScalarAve(x01, x12), SkScalarAve(y01, y12)); 2868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[3].set(x12, y12); 2878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[4] = src[2]; 2888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Quad'(t) = At + B, where 2918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = 2(a - 2b + c) 2928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = 2(b - a) 2938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Solve for t, only if it fits between 0 < t < 1 2948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 2958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValue[1]) 2968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 2978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /* At + B == 0 2988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com t = -B / A 2998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 3008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_SCALAR_IS_FIXED 3018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return is_not_monotonic(a, b, c) && valid_unit_divide(a - b, a - b - b + c, tValue); 3028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 3038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return valid_unit_divide(a - b, a - b - b + c, tValue); 3048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 3058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 307fc25abdabff76f913fb9d4f373418c10a1eca92breed@android.comstatic inline void flatten_double_quad_extrema(SkScalar coords[14]) 3088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 3098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coords[2] = coords[6] = coords[4]; 3108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Returns 0 for 1 quad, and 1 for two quads, either way the answer is 31377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com stored in dst[]. Guarantees that the 1/2 quads will be monotonic. 31477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com */ 3158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]) 3168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 3178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 3188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(dst); 319fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 3208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#if 0 3218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static bool once = true; 3228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (once) 3238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 3248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com once = false; 3258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint s[3] = { 0, 26398, 0, 26331, 0, 20621428 }; 3268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint d[6]; 327fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 3288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int n = SkChopQuadAtYExtrema(s, d); 3298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDebugf("chop=%d, Y=[%x %x %x %x %x %x]\n", n, d[0].fY, d[1].fY, d[2].fY, d[3].fY, d[4].fY, d[5].fY); 3308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 332fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 3338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar a = src[0].fY; 3348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar b = src[1].fY; 3358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar c = src[2].fY; 336fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 3378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (is_not_monotonic(a, b, c)) 3388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 3398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar tValue; 3408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (valid_unit_divide(a - b, a - b - b + c, &tValue)) 3418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 3428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAt(src, dst, tValue); 3438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com flatten_double_quad_extrema(&dst[0].fY); 3448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1; 3458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // if we get here, we need to force dst to be monotonic, even though 3478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we couldn't compute a unit_divide value (probably underflow). 3488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; 3498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0].set(src[0].fX, a); 3518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[1].set(src[1].fX, b); 3528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2].set(src[2].fX, c); 3538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 3548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 35677f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com/* Returns 0 for 1 quad, and 1 for two quads, either way the answer is 35777f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com stored in dst[]. Guarantees that the 1/2 quads will be monotonic. 35877f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com */ 35977f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.comint SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]) 36077f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com{ 36177f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkASSERT(src); 36277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkASSERT(dst); 363fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 36477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar a = src[0].fX; 36577f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar b = src[1].fX; 36677f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar c = src[2].fX; 367fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 36877f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com if (is_not_monotonic(a, b, c)) { 36977f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar tValue; 37077f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com if (valid_unit_divide(a - b, a - b - b + c, &tValue)) { 37177f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkChopQuadAt(src, dst, tValue); 37277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com flatten_double_quad_extrema(&dst[0].fX); 37377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com return 1; 37477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com } 37577f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com // if we get here, we need to force dst to be monotonic, even though 37677f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com // we couldn't compute a unit_divide value (probably underflow). 37777f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; 37877f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com } 37977f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com dst[0].set(a, src[0].fY); 38077f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com dst[1].set(b, src[1].fY); 38177f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com dst[2].set(c, src[2].fY); 38277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com return 0; 38377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com} 38477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com 3858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// F(t) = a (1 - t) ^ 2 + 2 b t (1 - t) + c t ^ 2 3868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// F'(t) = 2 (b - a) + 2 (a - 2b + c) t 3878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// F''(t) = 2 (a - 2b + c) 3888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 3898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// A = 2 (b - a) 3908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// B = 2 (a - 2b + c) 3918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 3928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// Maximum curvature for a quadratic means solving 3938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// Fx' Fx'' + Fy' Fy'' = 0 3948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 3958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// t = - (Ax Bx + Ay By) / (Bx ^ 2 + By ^ 2) 3968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 3978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]) 3988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 3998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ax = src[1].fX - src[0].fX; 4008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ay = src[1].fY - src[0].fY; 4018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Bx = src[0].fX - src[1].fX - src[1].fX + src[2].fX; 4028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar By = src[0].fY - src[1].fY - src[1].fY + src[2].fY; 4038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t = 0; // 0 means don't chop 4048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_SCALAR_IS_FLOAT 4068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (void)valid_unit_divide(-(Ax * Bx + Ay * By), Bx * Bx + By * By, &t); 4078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 4088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // !!! should I use SkFloat here? seems like it 4098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Sk64 numer, denom, tmp; 4108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com numer.setMul(Ax, -Bx); 4128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tmp.setMul(Ay, -By); 4138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com numer.add(tmp); 4148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (numer.isPos()) // do nothing if numer <= 0 4168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 4178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com denom.setMul(Bx, Bx); 4188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tmp.setMul(By, By); 4198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com denom.add(tmp); 4208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(!denom.isNeg()); 4218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (numer < denom) 4228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 4238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com t = numer.getFixedDiv(denom); 4248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Fixed1); // assert that we're numerically stable (ha!) 4258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((unsigned)t >= SK_Fixed1) // runtime check for numerical stability 4268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com t = 0; // ignore the chop 4278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 4308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (t == 0) 4328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 4338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 3 * sizeof(SkPoint)); 4348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1; 4358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else 4378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 4388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAt(src, dst, t); 4398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 2; 4408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4436fc321a18acc8c6437735007240eefe7054e83b0reed@google.com#ifdef SK_SCALAR_IS_FLOAT 4446fc321a18acc8c6437735007240eefe7054e83b0reed@google.com #define SK_ScalarTwoThirds (0.666666666f) 4456fc321a18acc8c6437735007240eefe7054e83b0reed@google.com#else 4466fc321a18acc8c6437735007240eefe7054e83b0reed@google.com #define SK_ScalarTwoThirds ((SkFixed)(43691)) 4476fc321a18acc8c6437735007240eefe7054e83b0reed@google.com#endif 4486fc321a18acc8c6437735007240eefe7054e83b0reed@google.com 4496fc321a18acc8c6437735007240eefe7054e83b0reed@google.comvoid SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]) { 4506fc321a18acc8c6437735007240eefe7054e83b0reed@google.com const SkScalar scale = SK_ScalarTwoThirds; 4516fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[0] = src[0]; 4526fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[1].set(src[0].fX + SkScalarMul(src[1].fX - src[0].fX, scale), 4536fc321a18acc8c6437735007240eefe7054e83b0reed@google.com src[0].fY + SkScalarMul(src[1].fY - src[0].fY, scale)); 4546fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[2].set(src[2].fX + SkScalarMul(src[1].fX - src[2].fX, scale), 4556fc321a18acc8c6437735007240eefe7054e83b0reed@google.com src[2].fY + SkScalarMul(src[1].fY - src[2].fY, scale)); 4566fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[3] = src[2]; 457945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com} 458945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 4598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//////////////////////////////////////////////////////////////////////////////////////// 4608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com///// CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS ///// 4618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//////////////////////////////////////////////////////////////////////////////////////// 4628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic void get_cubic_coeff(const SkScalar pt[], SkScalar coeff[4]) 4648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 4658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[0] = pt[6] + 3*(pt[2] - pt[4]) - pt[0]; 4668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[1] = 3*(pt[4] - pt[2] - pt[2] + pt[0]); 4678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[2] = 3*(pt[2] - pt[0]); 4688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[3] = pt[0]; 4698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]) 4728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 4738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(pts); 4748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (cx) 4768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com get_cubic_coeff(&pts[0].fX, cx); 4778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (cy) 4788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com get_cubic_coeff(&pts[0].fY, cy); 4798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic SkScalar eval_cubic(const SkScalar src[], SkScalar t) 4828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 4838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 4848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 4858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (t == 0) 4878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return src[0]; 4888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef DIRECT_EVAL_OF_POLYNOMIALS 4908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar D = src[0]; 4918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[6] + 3*(src[2] - src[4]) - D; 4928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 3*(src[4] - src[2] - src[2] + D); 4938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = 3*(src[2] - D); 4948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); 4968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 4978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar ab = SkScalarInterp(src[0], src[2], t); 4988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bc = SkScalarInterp(src[2], src[4], t); 4998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar cd = SkScalarInterp(src[4], src[6], t); 5008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar abc = SkScalarInterp(ab, bc, t); 5018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bcd = SkScalarInterp(bc, cd, t); 5028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarInterp(abc, bcd, t); 5038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 5048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** return At^2 + Bt + C 5078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 5088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic SkScalar eval_quadratic(SkScalar A, SkScalar B, SkScalar C, SkScalar t) 5098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 5108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 5118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 5138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic SkScalar eval_cubic_derivative(const SkScalar src[], SkScalar t) 5168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 5178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; 5188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 2*(src[4] - 2 * src[2] + src[0]); 5198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = src[2] - src[0]; 5208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return eval_quadratic(A, B, C, t); 5228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic SkScalar eval_cubic_2ndDerivative(const SkScalar src[], SkScalar t) 5258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 5268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; 5278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = src[4] - 2 * src[2] + src[0]; 5288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarMulAdd(A, t, B); 5308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* loc, SkVector* tangent, SkVector* curvature) 5338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 5348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 5358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 5368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (loc) 5388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com loc->set(eval_cubic(&src[0].fX, t), eval_cubic(&src[0].fY, t)); 5398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (tangent) 5408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tangent->set(eval_cubic_derivative(&src[0].fX, t), 5418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com eval_cubic_derivative(&src[0].fY, t)); 5428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (curvature) 5438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com curvature->set(eval_cubic_2ndDerivative(&src[0].fX, t), 5448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com eval_cubic_2ndDerivative(&src[0].fY, t)); 5458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Cubic'(t) = At^2 + Bt + C, where 5488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = 3(-a + 3(b - c) + d) 5498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = 6(a - 2b + c) 5508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = 3(b - a) 5518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Solve for t, keeping only those that fit betwee 0 < t < 1 5528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 5538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, SkScalar tValues[2]) 5548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 5558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_SCALAR_IS_FIXED 5568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!is_not_monotonic(a, b, c, d)) 5578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 5588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 5598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we divide A,B,C by 3 to simplify 5618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = d - a + 3*(b - c); 5628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 2*(a - b - b + c); 5638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = b - a; 5648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkFindUnitQuadRoots(A, B, C, tValues); 5668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic void interp_cubic_coords(const SkScalar* src, SkScalar* dst, SkScalar t) 5698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 5708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar ab = SkScalarInterp(src[0], src[2], t); 5718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bc = SkScalarInterp(src[2], src[4], t); 5728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar cd = SkScalarInterp(src[4], src[6], t); 5738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar abc = SkScalarInterp(ab, bc, t); 5748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bcd = SkScalarInterp(bc, cd, t); 5758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar abcd = SkScalarInterp(abc, bcd, t); 5768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0] = src[0]; 5788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2] = ab; 5798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[4] = abc; 5808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[6] = abcd; 5818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[8] = bcd; 5828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[10] = cd; 5838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[12] = src[6]; 5848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t) 5878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 5888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t > 0 && t < SK_Scalar1); 5898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com interp_cubic_coords(&src[0].fX, &dst[0].fX, t); 5918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com interp_cubic_coords(&src[0].fY, &dst[0].fY, t); 5928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 594a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com/* http://code.google.com/p/skia/issues/detail?id=32 595fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 596a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com This test code would fail when we didn't check the return result of 597a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com valid_unit_divide in SkChopCubicAt(... tValues[], int roots). The reason is 598a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com that after the first chop, the parameters to valid_unit_divide are equal 599a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com (thanks to finite float precision and rounding in the subtracts). Thus 600a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com even though the 2nd tValue looks < 1.0, after we renormalize it, we end 601a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com up with 1.0, hence the need to check and just return the last cubic as 602a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com a degenerate clump of 4 points in the sampe place. 603a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com 604a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com static void test_cubic() { 605a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkPoint src[4] = { 606a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.25000, 523.03003 }, 607a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.23999, 522.96002 }, 608a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.21997, 522.89001 }, 609a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.21997, 522.82001 } 610a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com }; 611a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkPoint dst[10]; 612a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkScalar tval[] = { 0.33333334f, 0.99999994f }; 613a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkChopCubicAt(src, dst, tval, 2); 614a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com } 615a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com */ 616a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com 6178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar tValues[], int roots) 6188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 6198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 6208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 6218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = 0; i < roots - 1; i++) 6228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 6238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(is_unit_interval(tValues[i])); 6248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(is_unit_interval(tValues[i+1])); 6258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(tValues[i] < tValues[i+1]); 6268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 6298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (dst) 6318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 6328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (roots == 0) // nothing to chop 6338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 4*sizeof(SkPoint)); 6348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else 6358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 6368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t = tValues[0]; 6378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint tmp[4]; 6388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = 0; i < roots; i++) 6408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 6418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, t); 6428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (i == roots - 1) 6438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 6448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst += 3; 646a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com // have src point to the remaining cubic (after the chop) 6478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(tmp, dst, 4 * sizeof(SkPoint)); 6488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com src = tmp; 649a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com 650a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com // watch out in case the renormalized t isn't in range 651a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com if (!valid_unit_divide(tValues[i+1] - tValues[i], 652a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SK_Scalar1 - tValues[i], &t)) { 653a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com // if we can't, just create a degenerate cubic 654a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com dst[4] = dst[5] = dst[6] = src[3]; 655a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com break; 656a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com } 6578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]) 6638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 6648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 6658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 6668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 6678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 6688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x23 = SkScalarAve(src[2].fX, src[3].fX); 6698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y23 = SkScalarAve(src[2].fY, src[3].fY); 6708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x012 = SkScalarAve(x01, x12); 6728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y012 = SkScalarAve(y01, y12); 6738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x123 = SkScalarAve(x12, x23); 6748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y123 = SkScalarAve(y12, y23); 6758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0] = src[0]; 6778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[1].set(x01, y01); 6788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2].set(x012, y012); 6798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[3].set(SkScalarAve(x012, x123), SkScalarAve(y012, y123)); 6808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[4].set(x123, y123); 6818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[5].set(x23, y23); 6828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[6] = src[3]; 6838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic void flatten_double_cubic_extrema(SkScalar coords[14]) 6868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 6878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coords[4] = coords[8] = coords[6]; 6888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that 6918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com the resulting beziers are monotonic in Y. This is called by the scan converter. 6928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Depending on what is returned, dst[] is treated as follows 6938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 dst[0..3] is the original cubic 6948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1 dst[0..3] and dst[3..6] are the two new cubics 6958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics 6968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com If dst == null, it is ignored and only the count is returned. 6978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 698bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.comint SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]) { 6998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar tValues[2]; 700bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com int roots = SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY, 701bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com src[3].fY, tValues); 702fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 7038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, tValues, roots); 704bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (dst && roots > 0) { 7058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we do some cleanup to ensure our Y extrema are flat 7068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com flatten_double_cubic_extrema(&dst[0].fY); 707bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (roots == 2) { 7088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com flatten_double_cubic_extrema(&dst[3].fY); 709bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 710bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 711bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com return roots; 712bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com} 713bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com 714bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.comint SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]) { 715bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com SkScalar tValues[2]; 716bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com int roots = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX, 717bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com src[3].fX, tValues); 718fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 719bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com SkChopCubicAt(src, dst, tValues, roots); 720bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (dst && roots > 0) { 721bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // we do some cleanup to ensure our Y extrema are flat 722bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com flatten_double_cubic_extrema(&dst[0].fX); 723bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (roots == 2) { 724bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com flatten_double_cubic_extrema(&dst[3].fX); 725bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 7268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 7278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return roots; 7288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 7298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** http://www.faculty.idc.ac.il/arik/quality/appendixA.html 7318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Inflection means that curvature is zero. 7338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Curvature is [F' x F''] / [F'^3] 7348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com So we solve F'x X F''y - F'y X F''y == 0 7358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com After some canceling of the cubic term, we get 7368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = b - a 7378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = c - 2b + a 7388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = d - 3c + 3b - a 7398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (BxCy - ByCx)t^2 + (AxCy - AyCx)t + AxBy - AyBx == 0 7408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 7418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[]) 7428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 7438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ax = src[1].fX - src[0].fX; 7448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ay = src[1].fY - src[0].fY; 7458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Bx = src[2].fX - 2 * src[1].fX + src[0].fX; 7468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar By = src[2].fY - 2 * src[1].fY + src[0].fY; 7478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Cx = src[3].fX + 3 * (src[1].fX - src[2].fX) - src[0].fX; 7488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Cy = src[3].fY + 3 * (src[1].fY - src[2].fY) - src[0].fY; 7498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count; 7508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_SCALAR_IS_FLOAT 7528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com count = SkFindUnitQuadRoots(Bx*Cy - By*Cx, Ax*Cy - Ay*Cx, Ax*By - Ay*Bx, tValues); 7538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 7548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Sk64 A, B, C, tmp; 7558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A.setMul(Bx, Cy); 7578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tmp.setMul(By, Cx); 7588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A.sub(tmp); 7598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B.setMul(Ax, Cy); 7618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tmp.setMul(Ay, Cx); 7628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B.sub(tmp); 7638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C.setMul(Ax, By); 7658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tmp.setMul(Ay, Bx); 7668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C.sub(tmp); 7678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com count = Sk64FindFixedQuadRoots(A, B, C, tValues); 7698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 7708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count; 7728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 7738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopCubicAtInflections(const SkPoint src[], SkPoint dst[10]) 7758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 7768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar tValues[2]; 7778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = SkFindCubicInflections(src, tValues); 7788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (dst) 7808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 7818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count == 0) 7828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 4 * sizeof(SkPoint)); 7838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else 7848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, tValues, count); 7858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 7868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count + 1; 7878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 7888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comtemplate <typename T> void bubble_sort(T array[], int count) 7908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 7918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = count - 1; i > 0; --i) 7928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int j = i; j > 0; --j) 7938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (array[j] < array[j-1]) 7948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 7958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T tmp(array[j]); 7968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com array[j] = array[j-1]; 7978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com array[j-1] = tmp; 7988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 7998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 8008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkFP.h" 8028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// newton refinement 8048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#if 0 8058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic SkScalar refine_cubic_root(const SkFP coeff[4], SkScalar root) 8068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 8078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // x1 = x0 - f(t) / f'(t) 8088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkFP T = SkScalarToFloat(root); 8108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkFP N, D; 8118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // f' = 3*coeff[0]*T^2 + 2*coeff[1]*T + coeff[2] 8138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com D = SkFPMul(SkFPMul(coeff[0], SkFPMul(T,T)), 3); 8148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com D = SkFPAdd(D, SkFPMulInt(SkFPMul(coeff[1], T), 2)); 8158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com D = SkFPAdd(D, coeff[2]); 8168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (D == 0) 8188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return root; 8198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // f = coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3] 8218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com N = SkFPMul(SkFPMul(SkFPMul(T, T), T), coeff[0]); 8228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com N = SkFPAdd(N, SkFPMul(SkFPMul(T, T), coeff[1])); 8238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com N = SkFPAdd(N, SkFPMul(T, coeff[2])); 8248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com N = SkFPAdd(N, coeff[3]); 8258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (N) 8278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 8288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar delta = SkFPToScalar(SkFPDiv(N, D)); 8298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (delta) 8318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com root -= delta; 8328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 8338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return root; 8348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 8358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 8368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 837087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com/** 838087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com * Given an array and count, remove all pair-wise duplicates from the array, 839087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com * keeping the existing sorting, and return the new count 840087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com */ 841087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.comstatic int collaps_duplicates(float array[], int count) { 842087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (int n = count; n > 1; --n) { 843087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com if (array[0] == array[1]) { 844087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (int i = 1; i < n; ++i) { 845087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com array[i - 1] = array[i]; 846087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 847087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com count -= 1; 848087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } else { 849087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com array += 1; 850087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 851087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 852087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com return count; 853087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com} 854087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 855087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com#ifdef SK_DEBUG 856087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 857087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com#define TEST_COLLAPS_ENTRY(array) array, SK_ARRAY_COUNT(array) 858087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 859087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.comstatic void test_collaps_duplicates() { 860087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com static bool gOnce; 861087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com if (gOnce) { return; } 862087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com gOnce = true; 863087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com const float src0[] = { 0 }; 864087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com const float src1[] = { 0, 0 }; 865087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com const float src2[] = { 0, 1 }; 866087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com const float src3[] = { 0, 0, 0 }; 867087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com const float src4[] = { 0, 0, 1 }; 868087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com const float src5[] = { 0, 1, 1 }; 869087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com const float src6[] = { 0, 1, 2 }; 870087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com const struct { 871087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com const float* fData; 872087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int fCount; 873087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int fCollapsedCount; 874087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } data[] = { 875087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src0), 1 }, 876087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src1), 1 }, 877087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src2), 2 }, 878087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src3), 1 }, 879087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src4), 2 }, 880087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src5), 2 }, 881087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src6), 3 }, 882087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com }; 883087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (size_t i = 0; i < SK_ARRAY_COUNT(data); ++i) { 884087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com float dst[3]; 885087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com memcpy(dst, data[i].fData, data[i].fCount * sizeof(dst[0])); 886087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int count = collaps_duplicates(dst, data[i].fCount); 887087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkASSERT(data[i].fCollapsedCount == count); 888087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (int j = 1; j < count; ++j) { 889087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkASSERT(dst[j-1] < dst[j]); 890087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 891087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 892087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com} 893087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com#endif 894087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 8958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#if defined _WIN32 && _MSC_VER >= 1300 && defined SK_SCALAR_IS_FIXED // disable warning : unreachable code if building fixed point for windows desktop 8968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#pragma warning ( disable : 4702 ) 8978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 8988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Solve coeff(t) == 0, returning the number of roots that 9008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com lie withing 0 < t < 1. 9018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3] 902fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 903087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com Eliminates repeated roots (so that all tValues are distinct, and are always 904087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com in increasing order. 9058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 9068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic int solve_cubic_polynomial(const SkFP coeff[4], SkScalar tValues[3]) 9078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 9088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifndef SK_SCALAR_IS_FLOAT 9098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; // this is not yet implemented for software float 9108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 9118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (SkScalarNearlyZero(coeff[0])) // we're just a quadratic 9138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 9148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues); 9158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 9168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkFP a, b, c, Q, R; 9188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 9208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(coeff[0] != 0); 9218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkFP inva = SkFPInvert(coeff[0]); 9238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com a = SkFPMul(coeff[1], inva); 9248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com b = SkFPMul(coeff[2], inva); 9258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com c = SkFPMul(coeff[3], inva); 9268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 9278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Q = SkFPDivInt(SkFPSub(SkFPMul(a,a), SkFPMulInt(b, 3)), 9); 9288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// R = (2*a*a*a - 9*a*b + 27*c) / 54; 9298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com R = SkFPMulInt(SkFPMul(SkFPMul(a, a), a), 2); 9308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com R = SkFPSub(R, SkFPMulInt(SkFPMul(a, b), 9)); 9318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com R = SkFPAdd(R, SkFPMulInt(c, 27)); 9328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com R = SkFPDivInt(R, 54); 9338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkFP Q3 = SkFPMul(SkFPMul(Q, Q), Q); 9358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkFP R2MinusQ3 = SkFPSub(SkFPMul(R,R), Q3); 9368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkFP adiv3 = SkFPDivInt(a, 3); 9378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar* roots = tValues; 9398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar r; 9408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (SkFPLT(R2MinusQ3, 0)) // we have 3 real roots 9428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 9438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_SCALAR_IS_FLOAT 9448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com float theta = sk_float_acos(R / sk_float_sqrt(Q3)); 9458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com float neg2RootQ = -2 * sk_float_sqrt(Q); 9468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r = neg2RootQ * sk_float_cos(theta/3) - adiv3; 9488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (is_unit_interval(r)) 9498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 9508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r = neg2RootQ * sk_float_cos((theta + 2*SK_ScalarPI)/3) - adiv3; 9528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (is_unit_interval(r)) 9538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 9548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r = neg2RootQ * sk_float_cos((theta - 2*SK_ScalarPI)/3) - adiv3; 9568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (is_unit_interval(r)) 9578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 9588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 959087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkDEBUGCODE(test_collaps_duplicates();) 960087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 9618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // now sort the roots 962087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int count = (int)(roots - tValues); 963087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkASSERT((unsigned)count <= 3); 964087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com bubble_sort(tValues, count); 965087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com count = collaps_duplicates(tValues, count); 966087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com roots = tValues + count; // so we compute the proper count below 9678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 9688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 9698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else // we have 1 real root 9708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 9718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkFP A = SkFPAdd(SkFPAbs(R), SkFPSqrt(R2MinusQ3)); 9728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = SkFPCubeRoot(A); 9738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (SkFPGT(R, 0)) 9748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = SkFPNeg(A); 9758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (A != 0) 9778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = SkFPAdd(A, SkFPDiv(Q, A)); 9788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r = SkFPToScalar(SkFPSub(A, adiv3)); 9798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (is_unit_interval(r)) 9808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 9818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 9828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (int)(roots - tValues); 9848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 9858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Looking for F' dot F'' == 0 987fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 9888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = b - a 9898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = c - 2b + a 9908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = d - 3c + 3b - a 9918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' = 3Ct^2 + 6Bt + 3A 9938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F'' = 6Ct + 6B 9948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 9968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 9978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic void formulate_F1DotF2(const SkScalar src[], SkFP coeff[4]) 9988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 9998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar a = src[2] - src[0]; 10008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar b = src[4] - 2 * src[2] + src[0]; 10018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar c = src[6] + 3 * (src[2] - src[4]) - src[0]; 10028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkFP A = SkScalarToFP(a); 10048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkFP B = SkScalarToFP(b); 10058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkFP C = SkScalarToFP(c); 10068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[0] = SkFPMul(C, C); 10088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[1] = SkFPMulInt(SkFPMul(B, C), 3); 10098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[2] = SkFPMulInt(SkFPMul(B, B), 2); 10108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[2] = SkFPAdd(coeff[2], SkFPMul(C, A)); 10118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[3] = SkFPMul(A, B); 10128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 10138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// EXPERIMENTAL: can set this to zero to accept all t-values 0 < t < 1 10158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//#define kMinTValueForChopping (SK_Scalar1 / 256) 10168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define kMinTValueForChopping 0 10178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Looking for F' dot F'' == 0 1019fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 10208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = b - a 10218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = c - 2b + a 10228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = d - 3c + 3b - a 10238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' = 3Ct^2 + 6Bt + 3A 10258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F'' = 6Ct + 6B 10268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 10288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 10298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]) 10308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 10318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkFP coeffX[4], coeffY[4]; 10328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int i; 10338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com formulate_F1DotF2(&src[0].fX, coeffX); 10358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com formulate_F1DotF2(&src[0].fY, coeffY); 10368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (i = 0; i < 4; i++) 10388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeffX[i] = SkFPAdd(coeffX[i],coeffY[i]); 10398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t[3]; 10418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = solve_cubic_polynomial(coeffX, t); 10428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int maxCount = 0; 10438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // now remove extrema where the curvature is zero (mins) 10458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // !!!! need a test for this !!!! 10468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (i = 0; i < count; i++) 10478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 10488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // if (not_min_curvature()) 10498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (t[i] > kMinTValueForChopping && t[i] < SK_Scalar1 - kMinTValueForChopping) 10508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tValues[maxCount++] = t[i]; 10518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 10528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return maxCount; 10538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 10548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], SkScalar tValues[3]) 10568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 10578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t_storage[3]; 10588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (tValues == NULL) 10608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tValues = t_storage; 10618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = SkFindCubicMaxCurvature(src, tValues); 10638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (dst) 10658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 10668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count == 0) 10678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 4 * sizeof(SkPoint)); 10688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else 10698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, tValues, count); 10708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 10718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count + 1; 10728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 10738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10742e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.orgbool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous) { 10752e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 10762e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = false; 10772e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 10782e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org 1079945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Find the minimum and maximum y of the extrema, which are the 1080945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // first and last points since this cubic is monotonic 1081945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar min_y = SkMinScalar(cubic[0].fY, cubic[3].fY); 1082945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar max_y = SkMaxScalar(cubic[0].fY, cubic[3].fY); 1083945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 1084945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fY == cubic[0].fY 1085945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com || pt.fY < min_y 1086945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com || pt.fY > max_y) { 1087945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // The query line definitely does not cross the curve 10882e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 10892e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = (pt.fY == cubic[0].fY); 10902e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 1091945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 1092945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } 1093945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 10942e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org bool pt_at_extremum = (pt.fY == cubic[3].fY); 10952e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org 1096945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar min_x = 1097945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkMinScalar( 1098945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkMinScalar( 1099945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkMinScalar(cubic[0].fX, cubic[1].fX), 1100945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com cubic[2].fX), 1101945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com cubic[3].fX); 1102945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fX < min_x) { 1103945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // The query line definitely crosses the curve 11042e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 11052e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = pt_at_extremum; 11062e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 1107945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return true; 1108945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } 1109945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 1110945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar max_x = 1111945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkMaxScalar( 1112945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkMaxScalar( 1113945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkMaxScalar(cubic[0].fX, cubic[1].fX), 1114945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com cubic[2].fX), 1115945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com cubic[3].fX); 1116945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fX > max_x) { 1117945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // The query line definitely does not cross the curve 1118945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 1119945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } 1120945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 1121945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Do a binary search to find the parameter value which makes y as 1122945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // close as possible to the query point. See whether the query 1123945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // line's origin is to the left of the associated x coordinate. 1124945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 1125945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // kMaxIter is chosen as the number of mantissa bits for a float, 1126945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // since there's no way we are going to get more precision by 1127945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // iterating more times than that. 1128945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com const int kMaxIter = 23; 1129945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkPoint eval; 1130945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com int iter = 0; 1131945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar upper_t; 1132945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar lower_t; 1133945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // Need to invert direction of t parameter if cubic goes up 1134945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com // instead of down 1135945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (cubic[3].fY > cubic[0].fY) { 1136945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com upper_t = SK_Scalar1; 1137945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com lower_t = SkFloatToScalar(0); 1138945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } else { 1139945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com upper_t = SkFloatToScalar(0); 1140945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com lower_t = SK_Scalar1; 1141945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } 1142945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com do { 1143945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkScalar t = SkScalarAve(upper_t, lower_t); 1144945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkEvalCubicAt(cubic, t, &eval, NULL, NULL); 1145945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fY > eval.fY) { 1146945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com lower_t = t; 1147945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } else { 1148945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com upper_t = t; 1149945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } 1150945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } while (++iter < kMaxIter 1151945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com && !SkScalarNearlyZero(eval.fY - pt.fY)); 1152945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (pt.fX <= eval.fX) { 11532e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 11542e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = pt_at_extremum; 11552e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 1156945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return true; 1157945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com } 1158945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return false; 1159945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com} 1160945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 11612e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.orgint SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous) { 1162945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com int num_crossings = 0; 1163945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com SkPoint monotonic_cubics[10]; 1164945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com int num_monotonic_cubics = SkChopCubicAtYExtrema(cubic, monotonic_cubics); 11652e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 11662e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous = false; 11672e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 11682e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org bool locally_ambiguous; 11692e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[0], &locally_ambiguous)) 1170945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com ++num_crossings; 11712e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 11722e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous |= locally_ambiguous; 11732e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 1174945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (num_monotonic_cubics > 0) 11752e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[3], &locally_ambiguous)) 1176945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com ++num_crossings; 11772e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 11782e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous |= locally_ambiguous; 11792e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 1180945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com if (num_monotonic_cubics > 1) 11812e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[6], &locally_ambiguous)) 1182945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com ++num_crossings; 11832e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org if (ambiguous) { 11842e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org *ambiguous |= locally_ambiguous; 11852e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org } 1186945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com return num_crossings; 1187945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com} 1188945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 11898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//////////////////////////////////////////////////////////////////////////////// 11908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Find t value for quadratic [a, b, c] = d. 11928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Return 0 if there is no solution within [0, 1) 11938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 11948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic SkScalar quad_solve(SkScalar a, SkScalar b, SkScalar c, SkScalar d) 11958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 11968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // At^2 + Bt + C = d 11978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = a - 2 * b + c; 11988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 2 * (b - a); 11998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = a - d; 12008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 12018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar roots[2]; 12028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = SkFindUnitQuadRoots(A, B, C, roots); 12038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 12048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(count <= 1); 12058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count == 1 ? roots[0] : 0; 12068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 12078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 12088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* given a quad-curve and a point (x,y), chop the quad at that point and return 12098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com the new quad's offCurve point. Should only return false if the computed pos 12108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com is the start of the curve (i.e. root == 0) 12118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 12128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic bool quad_pt2OffCurve(const SkPoint quad[3], SkScalar x, SkScalar y, SkPoint* offCurve) 12138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 12148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkScalar* base; 12158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar value; 12168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 12178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (SkScalarAbs(x) < SkScalarAbs(y)) { 12188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com base = &quad[0].fX; 12198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com value = x; 12208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 12218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com base = &quad[0].fY; 12228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com value = y; 12238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 12248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 12258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // note: this returns 0 if it thinks value is out of range, meaning the 12268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // root might return something outside of [0, 1) 12278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t = quad_solve(base[0], base[2], base[4], value); 12288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 12298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (t > 0) 12308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 12318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint tmp[5]; 12328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAt(quad, tmp, t); 12338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *offCurve = tmp[1]; 12348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 12358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 12368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /* t == 0 means either the value triggered a root outside of [0, 1) 12378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com For our purposes, we can ignore the <= 0 roots, but we want to 12388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com catch the >= 1 roots (which given our caller, will basically mean 12398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com a root of 1, give-or-take numerical instability). If we are in the 12408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com >= 1 case, return the existing offCurve point. 1241fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 12428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com The test below checks to see if we are close to the "end" of the 12438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com curve (near base[4]). Rather than specifying a tolerance, I just 12448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com check to see if value is on to the right/left of the middle point 12458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (depending on the direction/sign of the end points). 12468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 12478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((base[0] < base[4] && value > base[2]) || 12488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (base[0] > base[4] && value < base[2])) // should root have been 1 12498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 12508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *offCurve = quad[1]; 12518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 12528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 12538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 12548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 12558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 12568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1257b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com#ifdef SK_SCALAR_IS_FLOAT 1258dff53c26e7ef80da4767433ecfe17741a059e247reed@google.com 1259b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com// Due to floating point issues (i.e., 1.0f - SK_ScalarRoot2Over2 != 12606a748ad8d82576c4ce59e9b2409d41a93bf05cdfskia.committer@gmail.com// SK_ScalarRoot2Over2 - SK_ScalarTanPIOver8) a cruder root2over2 12616a748ad8d82576c4ce59e9b2409d41a93bf05cdfskia.committer@gmail.com// approximation is required to make the quad circle points convex. The 1262b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com// root of the problem is that with the root2over2 value in SkScalar.h 1263b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com// the arcs really are ever so slightly concave. Some alternative fixes 1264b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com// to this problem (besides just arbitrarily pushing out the mid-point as 1265b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com// is done here) are: 1266b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com// Adjust all the points (not just the middle) to both better approximate 1267b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com// the curve and remain convex 1268b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com// Switch over to using cubics rather then quads 1269b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com// Use a different method to create the mid-point (e.g., compute 1270b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com// the two side points, average them, then move it out as needed 1271dff53c26e7ef80da4767433ecfe17741a059e247reed@google.com#define SK_ScalarRoot2Over2_QuadCircle 0.7072f 1272c7a37c7bb2279d8c15d6fcbaf38f59dbd727eb6crobertphillips@google.com 1273c7a37c7bb2279d8c15d6fcbaf38f59dbd727eb6crobertphillips@google.com#else 1274b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com #define SK_ScalarRoot2Over2_QuadCircle SK_FixedRoot2Over2 1275b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com#endif 1276b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com 1277b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com 12788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic const SkPoint gQuadCirclePts[kSkBuildQuadArcStorage] = { 1279b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { SK_Scalar1, 0 }, 1280b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { SK_Scalar1, SK_ScalarTanPIOver8 }, 1281b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { SK_ScalarRoot2Over2_QuadCircle, SK_ScalarRoot2Over2_QuadCircle }, 1282b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { SK_ScalarTanPIOver8, SK_Scalar1 }, 1283b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com 1284b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { 0, SK_Scalar1 }, 1285b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { -SK_ScalarTanPIOver8, SK_Scalar1 }, 1286b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { -SK_ScalarRoot2Over2_QuadCircle, SK_ScalarRoot2Over2_QuadCircle }, 1287b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { -SK_Scalar1, SK_ScalarTanPIOver8 }, 1288b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com 1289b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { -SK_Scalar1, 0 }, 1290b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { -SK_Scalar1, -SK_ScalarTanPIOver8 }, 1291b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { -SK_ScalarRoot2Over2_QuadCircle, -SK_ScalarRoot2Over2_QuadCircle }, 1292b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { -SK_ScalarTanPIOver8, -SK_Scalar1 }, 1293b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com 1294b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { 0, -SK_Scalar1 }, 1295b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { SK_ScalarTanPIOver8, -SK_Scalar1 }, 1296b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { SK_ScalarRoot2Over2_QuadCircle, -SK_ScalarRoot2Over2_QuadCircle }, 1297b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { SK_Scalar1, -SK_ScalarTanPIOver8 }, 1298b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com 1299b95eaa8d0842a8bba97f0bc7e19cfd9172d09722robertphillips@google.com { SK_Scalar1, 0 } 13008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 13018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 13028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkBuildQuadArc(const SkVector& uStart, const SkVector& uStop, 13038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRotationDirection dir, const SkMatrix* userMatrix, 13048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint quadPoints[]) 13058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 13068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // rotate by x,y so that uStart is (1.0) 13078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x = SkPoint::DotProduct(uStart, uStop); 13088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y = SkPoint::CrossProduct(uStart, uStop); 13098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 13108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar absX = SkScalarAbs(x); 13118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar absY = SkScalarAbs(y); 13128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 13138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int pointCount; 13148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 13158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // check for (effectively) coincident vectors 13168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // this can happen if our angle is nearly 0 or nearly 180 (y == 0) 13178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // ... we use the dot-prod to distinguish between 0 and 180 (x > 0) 13188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (absY <= SK_ScalarNearlyZero && x > 0 && 13198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ((y >= 0 && kCW_SkRotationDirection == dir) || 13208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (y <= 0 && kCCW_SkRotationDirection == dir))) { 1321fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 13228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // just return the start-point 13238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com quadPoints[0].set(SK_Scalar1, 0); 13248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com pointCount = 1; 13258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 13268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (dir == kCCW_SkRotationDirection) 13278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com y = -y; 13288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 13298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // what octant (quadratic curve) is [xy] in? 13308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int oct = 0; 13318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool sameSign = true; 13328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 13338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (0 == y) 13348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 13358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct = 4; // 180 13368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero); 13378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 13388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else if (0 == x) 13398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 13408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero); 13418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (y > 0) 13428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct = 2; // 90 13438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else 13448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct = 6; // 270 13458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 13468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else 13478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 13488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (y < 0) 13498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct += 4; 13508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((x < 0) != (y < 0)) 13518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 13528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct += 2; 13538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sameSign = false; 13548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 13558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((absX < absY) == sameSign) 13568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct += 1; 13578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 13588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 13598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int wholeCount = oct << 1; 13608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(quadPoints, gQuadCirclePts, (wholeCount + 1) * sizeof(SkPoint)); 13618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 13628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkPoint* arc = &gQuadCirclePts[wholeCount]; 13638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (quad_pt2OffCurve(arc, x, y, &quadPoints[wholeCount + 1])) 13648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 13658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com quadPoints[wholeCount + 2].set(x, y); 13668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com wholeCount += 2; 13678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 13688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com pointCount = wholeCount + 1; 13698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 13708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 13718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // now handle counter-clockwise and the initial unitStart rotation 13728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkMatrix matrix; 13738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix.setSinCos(uStart.fY, uStart.fX); 13748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (dir == kCCW_SkRotationDirection) { 13758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix.preScale(SK_Scalar1, -SK_Scalar1); 13768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 13778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (userMatrix) { 13788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix.postConcat(*userMatrix); 13798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 13808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix.mapPoints(quadPoints, pointCount); 13818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return pointCount; 13828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1383c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 1384c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com/////////////////////////////////////////////////////////////////////////////// 1385c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 138617a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// F = (A (1 - t)^2 + C t^2 + 2 B (1 - t) t w) 138717a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// ------------------------------------------ 138817a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// ((1 - t)^2 + t^2 + 2 (1 - t) t w) 138917a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// 139017a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// = {t^2 (P0 + P2 - 2 P1 w), t (-2 P0 + 2 P1 w), P0} 139117a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// ------------------------------------------------ 139217a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// {t^2 (2 - 2 w), t (-2 + 2 w), 1} 139317a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// 139417a2c919d095797c364d407a5dbdb4d60533b953reed@google.com 139517a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// Take the parametric specification for the conic (either X or Y) and return 139617a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// in coeff[] the coefficients for the simple quadratic polynomial 139717a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// coeff[0] for t^2 139817a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// coeff[1] for t 139917a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// coeff[2] for constant term 140017a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// 14010c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org#if 0 14020c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.orgstatic void rat_numer_coeff(const SkScalar src[], SkScalar w, SkScalar coeff[3]) { 140317a2c919d095797c364d407a5dbdb4d60533b953reed@google.com coeff[0] = src[0] + src[4] - 2 * src[2] * w; 140417a2c919d095797c364d407a5dbdb4d60533b953reed@google.com coeff[1] = 2 * (src[2] * w - src[0]); 140517a2c919d095797c364d407a5dbdb4d60533b953reed@google.com coeff[0] = src[0]; 140617a2c919d095797c364d407a5dbdb4d60533b953reed@google.com} 14070c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org#endif 14080c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 14090c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.orgstatic SkScalar rat_eval_pos(const SkScalar src[], SkScalar w, SkScalar t) { 14100c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkASSERT(src); 14110c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkASSERT(t >= 0 && t <= SK_Scalar1); 141245fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 14130c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar src2w = SkScalarMul(src[2], w); 14140c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar C = src[0]; 14150c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar A = src[4] - 2 * src2w + C; 14160c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar B = 2 * (src2w - C); 14170c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar numer = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 141845fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 14190c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org B = 2 * (w - SK_Scalar1); 14200c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org C = SK_Scalar1; 14210c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org A = -B; 14220c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar denom = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 142345fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 14240c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return SkScalarDiv(numer, denom); 14250c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 142617a2c919d095797c364d407a5dbdb4d60533b953reed@google.com 14270c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org// F' = 2 (C t (1 + t (-1 + w)) - A (-1 + t) (t (-1 + w) - w) + B (1 - 2 t) w) 14280c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org// 14290c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org// {t^2 (2 P0 - 2 P2 - 2 P0 w + 2 P2 w), t (-2 P0 + 2 P2 + 4 P0 w - 4 P1 w), -2 P0 w + 2 P1 w} 14300c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org// 143117a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// coeff[0] for t^2 143217a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// coeff[1] for t 143317a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// coeff[2] for constant term 143417a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// 14350c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.orgstatic void rat_deriv_coeff(const SkScalar src[], SkScalar w, SkScalar coeff[3]) { 14360c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar diff40 = src[4] - src[0]; 14370c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar diff20 = 2 * w * (src[2] - src[0]); 14380c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org coeff[0] = 2 * (w * diff40 - diff40); 14390c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org coeff[1] = 2 * (diff40 - diff20); 14400c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org coeff[2] = diff20; 14410c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 14420c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 14430c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.orgstatic bool rat_find_extrema(const SkScalar src[], SkScalar w, SkScalar* t) { 14440c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar coeff[3]; 14450c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org rat_deriv_coeff(src, w, coeff); 14460c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 14470c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar tValues[2]; 14480c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org int roots = SkFindUnitQuadRoots(coeff[0], coeff[1], coeff[2], tValues); 14490c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkASSERT(0 == roots || 1 == roots); 145045fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 14510c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org if (1 == roots) { 14520c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org *t = tValues[0]; 14530c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return true; 14540c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org } 14550c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return false; 145617a2c919d095797c364d407a5dbdb4d60533b953reed@google.com} 145717a2c919d095797c364d407a5dbdb4d60533b953reed@google.com 14580d099557feb99707c8f601746f46f5a295eb33b7reed@google.comstruct SkP3D { 14590d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkScalar fX, fY, fZ; 14604bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 14610d099557feb99707c8f601746f46f5a295eb33b7reed@google.com void set(SkScalar x, SkScalar y, SkScalar z) { 14620d099557feb99707c8f601746f46f5a295eb33b7reed@google.com fX = x; fY = y; fZ = z; 14630d099557feb99707c8f601746f46f5a295eb33b7reed@google.com } 14644bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 14650d099557feb99707c8f601746f46f5a295eb33b7reed@google.com void projectDown(SkPoint* dst) const { 14660d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst->set(fX / fZ, fY / fZ); 14670d099557feb99707c8f601746f46f5a295eb33b7reed@google.com } 14680d099557feb99707c8f601746f46f5a295eb33b7reed@google.com}; 14690d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 14700d099557feb99707c8f601746f46f5a295eb33b7reed@google.com// we just return the middle 3 points, since the first and last are dups of src 14710d099557feb99707c8f601746f46f5a295eb33b7reed@google.com// 14720d099557feb99707c8f601746f46f5a295eb33b7reed@google.comstatic void p3d_interp(const SkScalar src[3], SkScalar dst[3], SkScalar t) { 14730d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkScalar ab = SkScalarInterp(src[0], src[3], t); 14740d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkScalar bc = SkScalarInterp(src[3], src[6], t); 14750d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[0] = ab; 14760d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[3] = SkScalarInterp(ab, bc, t); 14770d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[6] = bc; 14780d099557feb99707c8f601746f46f5a295eb33b7reed@google.com} 14790d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 14800d099557feb99707c8f601746f46f5a295eb33b7reed@google.comstatic void ratquad_mapTo3D(const SkPoint src[3], SkScalar w, SkP3D dst[]) { 14810d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[0].set(src[0].fX * 1, src[0].fY * 1, 1); 14820d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[1].set(src[1].fX * w, src[1].fY * w, w); 14830d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[2].set(src[2].fX * 1, src[2].fY * 1, 1); 14840d099557feb99707c8f601746f46f5a295eb33b7reed@google.com} 14850d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 148624bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com/* Derivative of conic : just the numerator, as the denom has no P values 148724bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com and can be ignored if we want to return a "normalized" tangent vector. 148824bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com 148924bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com 2 (P2 t (1 + t (-1 + w)) - P0 (-1 + t) (t (-1 + w) - w) + P1 (1 - 2 t) w) 149024bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com 149124bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com -- grouping by powers of t yields -- 149224bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com 149324bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com t^2 : (2 P0 - 2 P2 - 2 P0 w + 2 P2 w) 149424bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com t^1 : (-2 P0 + 2 P2 + 4 P0 w - 4 P1 w) 149524bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com t^0 : -2 P0 w + 2 P1 w 149624bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com 149724bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com We can trivially divide everything by 2 to simplify 149824bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com*/ 149924bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.comstatic SkScalar conic_eval_tan(const SkScalar coord[], SkScalar w, SkScalar t) { 150024bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com // At^2 + Bt + C == t * (t * A + B) + C 150124bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com 150224bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com const SkScalar P0 = coord[0]; 150324bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com const SkScalar P1 = coord[2]; 150424bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com const SkScalar P2 = coord[4]; 150524bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com const SkScalar P20 = P2 - P0; 150624bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com const SkScalar P10 = P1 - P0; 150724bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com const SkScalar wP10 = w * P10; 150824bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com // 2 P0 - 2 P2 - 2 P0 w + 2 P2 w 150924bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com // 2 * (P0 - P2 - P0w + P2w) 151024bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com // 2 * (invW * P0 - invW * P2 151124bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com SkScalar A = P20 - w * P20; 151224bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com // -2 P0 + 2 P2 + 4 P0 w - 4 P1 w 151324bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com // 2 * (P2 - P0 + P0w - P1w) 151424bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com // 2 * (w * (P0 - P1) + P2 - P0) 151524bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com SkScalar B = P20 - wP10; 151624bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com // -2 P0 w + 2 P1 w 151724bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com SkScalar C = wP10; 151824bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com 151924bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com return t * (t * A + B) + C; 152024bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com} 152124bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com 152224bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.comvoid SkConic::evalAt(SkScalar t, SkPoint* pt, SkVector* tangent) const { 1523c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com SkASSERT(t >= 0 && t <= SK_Scalar1); 15244bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 1525c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com if (pt) { 15260c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org pt->set(rat_eval_pos(&fPts[0].fX, fW, t), 15270c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org rat_eval_pos(&fPts[0].fY, fW, t)); 1528c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com } 152924bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com if (tangent) { 153024bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com tangent->set(conic_eval_tan(&fPts[0].fX, fW, t), 153124bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com conic_eval_tan(&fPts[0].fY, fW, t)); 153224bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com } 1533c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com} 1534c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 153528552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::chopAt(SkScalar t, SkConic dst[2]) const { 15360d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkP3D tmp[3], tmp2[3]; 15370d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 15380d099557feb99707c8f601746f46f5a295eb33b7reed@google.com ratquad_mapTo3D(fPts, fW, tmp); 15394bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 15400d099557feb99707c8f601746f46f5a295eb33b7reed@google.com p3d_interp(&tmp[0].fX, &tmp2[0].fX, t); 15410d099557feb99707c8f601746f46f5a295eb33b7reed@google.com p3d_interp(&tmp[0].fY, &tmp2[0].fY, t); 15420d099557feb99707c8f601746f46f5a295eb33b7reed@google.com p3d_interp(&tmp[0].fZ, &tmp2[0].fZ, t); 15434bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 15440d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[0].fPts[0] = fPts[0]; 15450d099557feb99707c8f601746f46f5a295eb33b7reed@google.com tmp2[0].projectDown(&dst[0].fPts[1]); 15460d099557feb99707c8f601746f46f5a295eb33b7reed@google.com tmp2[1].projectDown(&dst[0].fPts[2]); dst[1].fPts[0] = dst[0].fPts[2]; 15470d099557feb99707c8f601746f46f5a295eb33b7reed@google.com tmp2[2].projectDown(&dst[1].fPts[1]); 15480d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[1].fPts[2] = fPts[2]; 15490d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 15504af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // to put in "standard form", where w0 and w2 are both 1, we compute the 15514af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // new w1 as sqrt(w1*w1/w0*w2) 15524af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // or 15534af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // w1 /= sqrt(w0*w2) 15544af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // 15554af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // However, in our case, we know that for dst[0], w0 == 1, and for dst[1], w2 == 1 15564af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // 15574af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org SkScalar root = SkScalarSqrt(tmp2[1].fZ); 15584af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org dst[0].fW = tmp2[0].fZ / root; 15594af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org dst[1].fW = tmp2[2].fZ / root; 1560c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com} 15618d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org 15623df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.orgstatic SkScalar subdivide_w_value(SkScalar w) { 15633df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org return SkScalarSqrt((1 + w) * SK_ScalarHalf); 15643df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 15653df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 156628552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::chop(SkConic dst[2]) const { 15678d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar scale = SkScalarInvert(SK_Scalar1 + fW); 15688d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar p1x = fW * fPts[1].fX; 15698d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar p1y = fW * fPts[1].fY; 15708d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar mx = (fPts[0].fX + 2 * p1x + fPts[2].fX) * scale * SK_ScalarHalf; 15718d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar my = (fPts[0].fY + 2 * p1y + fPts[2].fY) * scale * SK_ScalarHalf; 15728d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org 15738d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[0].fPts[0] = fPts[0]; 15748d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[0].fPts[1].set((fPts[0].fX + p1x) * scale, 15758d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org (fPts[0].fY + p1y) * scale); 15768d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[0].fPts[2].set(mx, my); 15778d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org 15788d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[1].fPts[0].set(mx, my); 15798d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[1].fPts[1].set((p1x + fPts[2].fX) * scale, 15808d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org (p1y + fPts[2].fY) * scale); 15818d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[1].fPts[2] = fPts[2]; 15828d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org 15833df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org dst[0].fW = dst[1].fW = subdivide_w_value(fW); 15843df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 15853df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 158697514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org/* 158797514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org * "High order approximation of conic sections by quadratic splines" 158897514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org * by Michael Floater, 1993 158997514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org */ 1590af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org#define AS_QUAD_ERROR_SETUP \ 1591af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar a = fW - 1; \ 1592af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar k = a / (4 * (2 + a)); \ 1593af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar x = k * (fPts[0].fX - 2 * fPts[1].fX + fPts[2].fX); \ 1594af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar y = k * (fPts[0].fY - 2 * fPts[1].fY + fPts[2].fY); 1595af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 1596af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.orgvoid SkConic::computeAsQuadError(SkVector* err) const { 1597af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org AS_QUAD_ERROR_SETUP 1598af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org err->set(x, y); 1599af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org} 1600af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 1601af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.orgbool SkConic::asQuadTol(SkScalar tol) const { 1602af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org AS_QUAD_ERROR_SETUP 1603af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org return (x * x + y * y) <= tol * tol; 160497514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org} 16057841c63136e8aa2d3aadbeab8432405abcd73c32skia.committer@gmail.com 160697514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.orgint SkConic::computeQuadPOW2(SkScalar tol) const { 1607af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org AS_QUAD_ERROR_SETUP 1608af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar error = SkScalarSqrt(x * x + y * y) - tol; 1609af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 1610af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org if (error <= 0) { 161197514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org return 0; 16123df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org } 161397514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org uint32_t ierr = (uint32_t)error; 1614af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org return (34 - SkCLZ(ierr)) >> 1; 16153df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 16163df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 161728552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgstatic SkPoint* subdivide(const SkConic& src, SkPoint pts[], int level) { 16183df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org SkASSERT(level >= 0); 1619af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 16203df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org if (0 == level) { 16213df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org memcpy(pts, &src.fPts[1], 2 * sizeof(SkPoint)); 16223df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org return pts + 2; 16233df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org } else { 162428552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org SkConic dst[2]; 16253df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org src.chop(dst); 16263df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org --level; 16273df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org pts = subdivide(dst[0], pts, level); 16283df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org return subdivide(dst[1], pts, level); 16293df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org } 16308d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org} 16313df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 163228552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgint SkConic::chopIntoQuadsPOW2(SkPoint pts[], int pow2) const { 1633af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkASSERT(pow2 >= 0); 16343df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org *pts = fPts[0]; 1635aebfa7e1b1e94f693f3e7beb6ad43cfcb0f69e98reed@google.com SkDEBUGCODE(SkPoint* endPts =) subdivide(*this, pts + 1, pow2); 16363df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org SkASSERT(endPts - pts == (2 * (1 << pow2) + 1)); 16373df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org return 1 << pow2; 16383df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 16390c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 164028552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::findXExtrema(SkScalar* t) const { 16410c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return rat_find_extrema(&fPts[0].fX, fW, t); 16420c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 16430c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 164428552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::findYExtrema(SkScalar* t) const { 16450c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return rat_find_extrema(&fPts[0].fY, fW, t); 16460c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 16470c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 164828552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::chopAtXExtrema(SkConic dst[2]) const { 16490c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar t; 16500c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org if (this->findXExtrema(&t)) { 16510c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org this->chopAt(t, dst); 16520c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // now clean-up the middle, since we know t was meant to be at 16530c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // an X-extrema 16540c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar value = dst[0].fPts[2].fX; 16550c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[0].fPts[1].fX = value; 16560c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[0].fX = value; 16570c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[1].fX = value; 16580c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return true; 16590c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org } 16600c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return false; 16610c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 16620c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 166328552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::chopAtYExtrema(SkConic dst[2]) const { 16640c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar t; 16650c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org if (this->findYExtrema(&t)) { 16660c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org this->chopAt(t, dst); 16670c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // now clean-up the middle, since we know t was meant to be at 16680c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // an Y-extrema 16690c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar value = dst[0].fPts[2].fY; 16700c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[0].fPts[1].fY = value; 16710c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[0].fY = value; 16720c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[1].fY = value; 16730c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return true; 16740c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org } 16750c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return false; 16760c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 16770c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 167828552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::computeTightBounds(SkRect* bounds) const { 16795c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org SkPoint pts[4]; 16805c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org pts[0] = fPts[0]; 16815c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org pts[1] = fPts[2]; 16825c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org int count = 2; 16835c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org 16845c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org SkScalar t; 16855c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org if (this->findXExtrema(&t)) { 16865c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org this->evalAt(t, &pts[count++]); 16875c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org } 16885c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org if (this->findYExtrema(&t)) { 16895c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org this->evalAt(t, &pts[count++]); 16905c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org } 16915c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org bounds->set(pts, count); 16925c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org} 16935c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org 169428552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::computeFastBounds(SkRect* bounds) const { 16955c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org bounds->set(fPts, 3); 16965c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org} 169724bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com 1698