SkGeometry.cpp revision b640203cd5733aaf110277e28e22007c5b541565
1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkGeometry.h" 98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkMatrix.h" 1040b7dd57ef1f4e91af72512d8ca57459b99d71bdreed#include "Sk2x.h" 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 12b640203cd5733aaf110277e28e22007c5b541565reedstatic Sk2s from_point(const SkPoint& point) { 13b640203cd5733aaf110277e28e22007c5b541565reed return Sk2s::Load(&point.fX); 14b640203cd5733aaf110277e28e22007c5b541565reed} 15b640203cd5733aaf110277e28e22007c5b541565reed 16b640203cd5733aaf110277e28e22007c5b541565reedstatic SkPoint to_point(const Sk2s& x) { 17b640203cd5733aaf110277e28e22007c5b541565reed SkPoint point; 18b640203cd5733aaf110277e28e22007c5b541565reed x.store(&point.fX); 19b640203cd5733aaf110277e28e22007c5b541565reed return point; 20b640203cd5733aaf110277e28e22007c5b541565reed} 21b640203cd5733aaf110277e28e22007c5b541565reed 22b640203cd5733aaf110277e28e22007c5b541565reedstatic SkVector to_vector(const Sk2s& x) { 23b640203cd5733aaf110277e28e22007c5b541565reed SkVector vector; 24b640203cd5733aaf110277e28e22007c5b541565reed x.store(&vector.fX); 25b640203cd5733aaf110277e28e22007c5b541565reed return vector; 26b640203cd5733aaf110277e28e22007c5b541565reed} 27b640203cd5733aaf110277e28e22007c5b541565reed 28b640203cd5733aaf110277e28e22007c5b541565reed#if 0 29b640203cd5733aaf110277e28e22007c5b541565reedstatic Sk2s divide(const Sk2s& numer, const Sk2s& denom) { 30b640203cd5733aaf110277e28e22007c5b541565reed SkScalar numerStorage[2], denomStorage[2]; 31b640203cd5733aaf110277e28e22007c5b541565reed numer.store(numerStorage); 32b640203cd5733aaf110277e28e22007c5b541565reed denom.store(denomStorage); 33b640203cd5733aaf110277e28e22007c5b541565reed numerStorage[0] /= denomStorage[0]; 34b640203cd5733aaf110277e28e22007c5b541565reed numerStorage[1] /= denomStorage[1]; 35b640203cd5733aaf110277e28e22007c5b541565reed return Sk2s::Load(numerStorage); 36b640203cd5733aaf110277e28e22007c5b541565reed} 37b640203cd5733aaf110277e28e22007c5b541565reed#endif 38b640203cd5733aaf110277e28e22007c5b541565reed 398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** If defined, this makes eval_quad and eval_cubic do more setup (sometimes 408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com involving integer multiplies by 2 or 3, but fewer calls to SkScalarMul. 418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com May also introduce overflow of fixed when we compute our setup. 428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 438f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com// #define DIRECT_EVAL_OF_POLYNOMIALS 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//////////////////////////////////////////////////////////////////////// 468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 47b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic int is_not_monotonic(SkScalar a, SkScalar b, SkScalar c) { 48b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar ab = a - b; 49b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar bc = b - c; 508f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com if (ab < 0) { 518f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com bc = -bc; 528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 538f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com return ab == 0 || bc < 0; 548f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com} 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//////////////////////////////////////////////////////////////////////// 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 58b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic bool is_unit_interval(SkScalar x) { 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return x > 0 && x < SK_Scalar1; 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 62b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic int valid_unit_divide(SkScalar numer, SkScalar denom, SkScalar* ratio) { 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(ratio); 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 65b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (numer < 0) { 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com numer = -numer; 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com denom = -denom; 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 70b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (denom == 0 || numer == 0 || numer >= denom) { 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 72b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar r = SkScalarDiv(numer, denom); 7515161620bee33efcb706685486c9ce0fb51a72bbreed@android.com if (SkScalarIsNaN(r)) { 7615161620bee33efcb706685486c9ce0fb51a72bbreed@android.com return 0; 7715161620bee33efcb706685486c9ce0fb51a72bbreed@android.com } 7811fca3f29f0117eda798c67fafde40465d9903e1Mike Klein SkASSERTF(r >= 0 && r < SK_Scalar1, "numer %f, denom %f, r %f", numer, denom, r); 79b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (r == 0) { // catch underflow if numer <<<< denom 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 81b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *ratio = r; 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1; 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** From Numerical Recipes in C. 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Q = -1/2 (B + sign(B) sqrt[B*B - 4*A*C]) 898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com x1 = Q / A 908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com x2 = C / Q 918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 92b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]) { 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(roots); 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 95b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (A == 0) { 968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return valid_unit_divide(-C, B, roots); 97b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar* r = roots; 1008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 101b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar R = B*B - 4*A*C; 10215161620bee33efcb706685486c9ce0fb51a72bbreed@android.com if (R < 0 || SkScalarIsNaN(R)) { // complex roots 1038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 10415161620bee33efcb706685486c9ce0fb51a72bbreed@android.com } 105b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org R = SkScalarSqrt(R); 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Q = (B < 0) ? -(B-R)/2 : -(B+R)/2; 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r += valid_unit_divide(Q, A, r); 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r += valid_unit_divide(C, Q, r); 110b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (r - roots == 2) { 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (roots[0] > roots[1]) 1128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTSwap<SkScalar>(roots[0], roots[1]); 1138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else if (roots[0] == roots[1]) // nearly-equal? 1148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r -= 1; // skip the double root 1158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (int)(r - roots); 1178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1198f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com/////////////////////////////////////////////////////////////////////////////// 1208f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com/////////////////////////////////////////////////////////////////////////////// 1218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 122b640203cd5733aaf110277e28e22007c5b541565reedstatic Sk2s quad_poly_eval(const Sk2s& A, const Sk2s& B, const Sk2s& C, const Sk2s& t) { 123b640203cd5733aaf110277e28e22007c5b541565reed return (A * t + B) * t + C; 124b640203cd5733aaf110277e28e22007c5b541565reed} 125b640203cd5733aaf110277e28e22007c5b541565reed 126b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar eval_quad(const SkScalar src[], SkScalar t) { 1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 1288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 1298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef DIRECT_EVAL_OF_POLYNOMIALS 1318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = src[0]; 1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[4] - 2 * src[2] + C; 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 2 * (src[2] - C); 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar ab = SkScalarInterp(src[0], src[2], t); 137fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com SkScalar bc = SkScalarInterp(src[2], src[4], t); 1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarInterp(ab, bc, t); 1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 1408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 142b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar eval_quad_derivative(const SkScalar src[], SkScalar t) { 1438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[4] - 2 * src[2] + src[0]; 1448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = src[2] - src[0]; 1458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 2 * SkScalarMulAdd(A, t, B); 1478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 14965cb2cd2f7ad4146f055810b8bd77bff03a4e76ereedvoid SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent) { 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 152950e986b1bc127af1f484572d2494091957486f9mtklein 153b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (pt) { 1548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com pt->set(eval_quad(&src[0].fX, t), eval_quad(&src[0].fY, t)); 155b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 156b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (tangent) { 1578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tangent->set(eval_quad_derivative(&src[0].fX, t), 1588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com eval_quad_derivative(&src[0].fY, t)); 159b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 1608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 16265cb2cd2f7ad4146f055810b8bd77bff03a4e76ereedSkPoint SkEvalQuadAt(const SkPoint src[3], SkScalar t) { 1638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 16465cb2cd2f7ad4146f055810b8bd77bff03a4e76ereed SkASSERT(t >= 0 && t <= SK_Scalar1); 1658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 166b640203cd5733aaf110277e28e22007c5b541565reed const Sk2s t2(t); 167950e986b1bc127af1f484572d2494091957486f9mtklein 168b640203cd5733aaf110277e28e22007c5b541565reed Sk2s P0 = from_point(src[0]); 169b640203cd5733aaf110277e28e22007c5b541565reed Sk2s P1 = from_point(src[1]); 170b640203cd5733aaf110277e28e22007c5b541565reed Sk2s P2 = from_point(src[2]); 171950e986b1bc127af1f484572d2494091957486f9mtklein 172b640203cd5733aaf110277e28e22007c5b541565reed Sk2s B = P1 - P0; 173b640203cd5733aaf110277e28e22007c5b541565reed Sk2s A = P2 - P1 - B; 174950e986b1bc127af1f484572d2494091957486f9mtklein 175b640203cd5733aaf110277e28e22007c5b541565reed return to_point((A * t2 + B+B) * t2 + P0); 1768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 17840b7dd57ef1f4e91af72512d8ca57459b99d71bdreedSkVector SkEvalQuadTangentAt(const SkPoint src[3], SkScalar t) { 17940b7dd57ef1f4e91af72512d8ca57459b99d71bdreed SkASSERT(src); 18040b7dd57ef1f4e91af72512d8ca57459b99d71bdreed SkASSERT(t >= 0 && t <= SK_Scalar1); 18140b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 182b640203cd5733aaf110277e28e22007c5b541565reed Sk2s P0 = from_point(src[0]); 183b640203cd5733aaf110277e28e22007c5b541565reed Sk2s P1 = from_point(src[1]); 184b640203cd5733aaf110277e28e22007c5b541565reed Sk2s P2 = from_point(src[2]); 18540b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 186b640203cd5733aaf110277e28e22007c5b541565reed Sk2s B = P1 - P0; 187b640203cd5733aaf110277e28e22007c5b541565reed Sk2s A = P2 - P1 - B; 188b640203cd5733aaf110277e28e22007c5b541565reed Sk2s T = A * Sk2s(t) + B; 18940b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 190b640203cd5733aaf110277e28e22007c5b541565reed return to_vector(T + T); 19140b7dd57ef1f4e91af72512d8ca57459b99d71bdreed} 19240b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 193b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic void interp_quad_coords(const SkScalar* src, SkScalar* dst, SkScalar t) { 1948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar ab = SkScalarInterp(src[0], src[2], t); 1958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bc = SkScalarInterp(src[2], src[4], t); 1968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0] = src[0]; 1988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2] = ab; 1998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[4] = SkScalarInterp(ab, bc, t); 2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[6] = bc; 2018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[8] = src[4]; 2028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 204b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t) { 2058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t > 0 && t < SK_Scalar1); 2068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com interp_quad_coords(&src[0].fX, &dst[0].fX, t); 2088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com interp_quad_coords(&src[0].fY, &dst[0].fY, t); 2098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 21140b7dd57ef1f4e91af72512d8ca57459b99d71bdreedstatic inline Sk2s interp(const Sk2s& v0, const Sk2s& v1, const Sk2s& t) { 21240b7dd57ef1f4e91af72512d8ca57459b99d71bdreed return v0 + (v1 - v0) * t; 21340b7dd57ef1f4e91af72512d8ca57459b99d71bdreed} 21440b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 21540b7dd57ef1f4e91af72512d8ca57459b99d71bdreedvoid SkChopQuadAt2(const SkPoint src[3], SkPoint dst[5], SkScalar t) { 21640b7dd57ef1f4e91af72512d8ca57459b99d71bdreed SkASSERT(t > 0 && t < SK_Scalar1); 21740b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 218b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p0 = from_point(src[0]); 219b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p1 = from_point(src[1]); 220b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p2 = from_point(src[2]); 22140b7dd57ef1f4e91af72512d8ca57459b99d71bdreed Sk2s tt = Sk2s(t); 22240b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 22340b7dd57ef1f4e91af72512d8ca57459b99d71bdreed Sk2s p01 = interp(p0, p1, tt); 22440b7dd57ef1f4e91af72512d8ca57459b99d71bdreed Sk2s p12 = interp(p1, p2, tt); 22540b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 226b640203cd5733aaf110277e28e22007c5b541565reed dst[0] = to_point(p0); 227b640203cd5733aaf110277e28e22007c5b541565reed dst[1] = to_point(p01); 228b640203cd5733aaf110277e28e22007c5b541565reed dst[2] = to_point(interp(p01, p12, tt)); 229b640203cd5733aaf110277e28e22007c5b541565reed dst[3] = to_point(p12); 230b640203cd5733aaf110277e28e22007c5b541565reed dst[4] = to_point(p2); 23140b7dd57ef1f4e91af72512d8ca57459b99d71bdreed} 23240b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 233b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]) { 2348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 2358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 2368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 2378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 2388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0] = src[0]; 2408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[1].set(x01, y01); 2418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2].set(SkScalarAve(x01, x12), SkScalarAve(y01, y12)); 2428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[3].set(x12, y12); 2438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[4] = src[2]; 2448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Quad'(t) = At + B, where 2478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = 2(a - 2b + c) 2488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = 2(b - a) 2498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Solve for t, only if it fits between 0 < t < 1 2508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 251b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValue[1]) { 2528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /* At + B == 0 2538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com t = -B / A 2548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 2558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return valid_unit_divide(a - b, a - b - b + c, tValue); 2568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 258b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic inline void flatten_double_quad_extrema(SkScalar coords[14]) { 2598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coords[2] = coords[6] = coords[4]; 2608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Returns 0 for 1 quad, and 1 for two quads, either way the answer is 26377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com stored in dst[]. Guarantees that the 1/2 quads will be monotonic. 26477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com */ 265b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]) { 2668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 2678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(dst); 268fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 2698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar a = src[0].fY; 2708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar b = src[1].fY; 2718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar c = src[2].fY; 272fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 273b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_not_monotonic(a, b, c)) { 2748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar tValue; 275b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (valid_unit_divide(a - b, a - b - b + c, &tValue)) { 2768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAt(src, dst, tValue); 2778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com flatten_double_quad_extrema(&dst[0].fY); 2788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1; 2798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // if we get here, we need to force dst to be monotonic, even though 2818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we couldn't compute a unit_divide value (probably underflow). 2828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; 2838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0].set(src[0].fX, a); 2858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[1].set(src[1].fX, b); 2868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2].set(src[2].fX, c); 2878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 2888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 29077f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com/* Returns 0 for 1 quad, and 1 for two quads, either way the answer is 29177f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com stored in dst[]. Guarantees that the 1/2 quads will be monotonic. 29277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com */ 293b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]) { 29477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkASSERT(src); 29577f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkASSERT(dst); 296fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 29777f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar a = src[0].fX; 29877f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar b = src[1].fX; 29977f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar c = src[2].fX; 300fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 30177f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com if (is_not_monotonic(a, b, c)) { 30277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar tValue; 30377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com if (valid_unit_divide(a - b, a - b - b + c, &tValue)) { 30477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkChopQuadAt(src, dst, tValue); 30577f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com flatten_double_quad_extrema(&dst[0].fX); 30677f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com return 1; 30777f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com } 30877f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com // if we get here, we need to force dst to be monotonic, even though 30977f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com // we couldn't compute a unit_divide value (probably underflow). 31077f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; 31177f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com } 31277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com dst[0].set(a, src[0].fY); 31377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com dst[1].set(b, src[1].fY); 31477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com dst[2].set(c, src[2].fY); 31577f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com return 0; 31677f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com} 31777f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com 3188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// F(t) = a (1 - t) ^ 2 + 2 b t (1 - t) + c t ^ 2 3198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// F'(t) = 2 (b - a) + 2 (a - 2b + c) t 3208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// F''(t) = 2 (a - 2b + c) 3218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 3228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// A = 2 (b - a) 3238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// B = 2 (a - 2b + c) 3248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 3258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// Maximum curvature for a quadratic means solving 3268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// Fx' Fx'' + Fy' Fy'' = 0 3278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 3288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// t = - (Ax Bx + Ay By) / (Bx ^ 2 + By ^ 2) 3298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 330b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgSkScalar SkFindQuadMaxCurvature(const SkPoint src[3]) { 3318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ax = src[1].fX - src[0].fX; 3328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ay = src[1].fY - src[0].fY; 3338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Bx = src[0].fX - src[1].fX - src[1].fX + src[2].fX; 3348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar By = src[0].fY - src[1].fY - src[1].fY + src[2].fY; 3358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t = 0; // 0 means don't chop 3368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (void)valid_unit_divide(-(Ax * Bx + Ay * By), Bx * Bx + By * By, &t); 3385383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com return t; 3395383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com} 3408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 341b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]) { 3425383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com SkScalar t = SkFindQuadMaxCurvature(src); 3435383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com if (t == 0) { 3448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 3 * sizeof(SkPoint)); 3458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1; 3465383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com } else { 3478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAt(src, dst, t); 3488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 2; 3498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3528f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com#define SK_ScalarTwoThirds (0.666666666f) 3536fc321a18acc8c6437735007240eefe7054e83b0reed@google.com 3546fc321a18acc8c6437735007240eefe7054e83b0reed@google.comvoid SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]) { 3556fc321a18acc8c6437735007240eefe7054e83b0reed@google.com const SkScalar scale = SK_ScalarTwoThirds; 3566fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[0] = src[0]; 3576fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[1].set(src[0].fX + SkScalarMul(src[1].fX - src[0].fX, scale), 3586fc321a18acc8c6437735007240eefe7054e83b0reed@google.com src[0].fY + SkScalarMul(src[1].fY - src[0].fY, scale)); 3596fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[2].set(src[2].fX + SkScalarMul(src[1].fX - src[2].fX, scale), 3606fc321a18acc8c6437735007240eefe7054e83b0reed@google.com src[2].fY + SkScalarMul(src[1].fY - src[2].fY, scale)); 3616fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[3] = src[2]; 362945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com} 363945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 364b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org////////////////////////////////////////////////////////////////////////////// 365b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org///// CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS ///// 366b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org////////////////////////////////////////////////////////////////////////////// 3678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 368b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic void get_cubic_coeff(const SkScalar pt[], SkScalar coeff[4]) { 3698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[0] = pt[6] + 3*(pt[2] - pt[4]) - pt[0]; 3708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[1] = 3*(pt[4] - pt[2] - pt[2] + pt[0]); 3718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[2] = 3*(pt[2] - pt[0]); 3728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[3] = pt[0]; 3738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 375b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]) { 3768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(pts); 3778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 378b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (cx) { 3798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com get_cubic_coeff(&pts[0].fX, cx); 380b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 381b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (cy) { 3828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com get_cubic_coeff(&pts[0].fY, cy); 383b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 3848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 386b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar eval_cubic(const SkScalar src[], SkScalar t) { 3878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 3888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 3898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 390b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (t == 0) { 3918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return src[0]; 392b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 3938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef DIRECT_EVAL_OF_POLYNOMIALS 3958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar D = src[0]; 3968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[6] + 3*(src[2] - src[4]) - D; 3978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 3*(src[4] - src[2] - src[2] + D); 3988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = 3*(src[2] - D); 3998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); 4018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 4028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar ab = SkScalarInterp(src[0], src[2], t); 4038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bc = SkScalarInterp(src[2], src[4], t); 4048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar cd = SkScalarInterp(src[4], src[6], t); 4058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar abc = SkScalarInterp(ab, bc, t); 4068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bcd = SkScalarInterp(bc, cd, t); 4078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarInterp(abc, bcd, t); 4088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 4098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** return At^2 + Bt + C 4128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 413b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar eval_quadratic(SkScalar A, SkScalar B, SkScalar C, SkScalar t) { 4148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 4158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 4178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 419b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar eval_cubic_derivative(const SkScalar src[], SkScalar t) { 4208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; 4218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 2*(src[4] - 2 * src[2] + src[0]); 4228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = src[2] - src[0]; 4238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return eval_quadratic(A, B, C, t); 4258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 427b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar eval_cubic_2ndDerivative(const SkScalar src[], SkScalar t) { 4288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; 4298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = src[4] - 2 * src[2] + src[0]; 4308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkScalarMulAdd(A, t, B); 4328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 434b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* loc, 435b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkVector* tangent, SkVector* curvature) { 4368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 4378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 4388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 439b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (loc) { 4408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com loc->set(eval_cubic(&src[0].fX, t), eval_cubic(&src[0].fY, t)); 441b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 442b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (tangent) { 4438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tangent->set(eval_cubic_derivative(&src[0].fX, t), 4448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com eval_cubic_derivative(&src[0].fY, t)); 445b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 446b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (curvature) { 4478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com curvature->set(eval_cubic_2ndDerivative(&src[0].fX, t), 4488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com eval_cubic_2ndDerivative(&src[0].fY, t)); 449b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 4508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Cubic'(t) = At^2 + Bt + C, where 4538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = 3(-a + 3(b - c) + d) 4548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = 6(a - 2b + c) 4558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = 3(b - a) 4568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Solve for t, keeping only those that fit betwee 0 < t < 1 4578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 458b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, 459b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar tValues[2]) { 4608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we divide A,B,C by 3 to simplify 4618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = d - a + 3*(b - c); 4628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 2*(a - b - b + c); 4638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = b - a; 4648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkFindUnitQuadRoots(A, B, C, tValues); 4668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 468b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic void interp_cubic_coords(const SkScalar* src, SkScalar* dst, 469b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar t) { 4708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar ab = SkScalarInterp(src[0], src[2], t); 4718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bc = SkScalarInterp(src[2], src[4], t); 4728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar cd = SkScalarInterp(src[4], src[6], t); 4738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar abc = SkScalarInterp(ab, bc, t); 4748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bcd = SkScalarInterp(bc, cd, t); 4758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar abcd = SkScalarInterp(abc, bcd, t); 4768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0] = src[0]; 4788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2] = ab; 4798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[4] = abc; 4808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[6] = abcd; 4818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[8] = bcd; 4828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[10] = cd; 4838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[12] = src[6]; 4848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 486b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t) { 4878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t > 0 && t < SK_Scalar1); 4888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com interp_cubic_coords(&src[0].fX, &dst[0].fX, t); 4908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com interp_cubic_coords(&src[0].fY, &dst[0].fY, t); 4918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 493a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com/* http://code.google.com/p/skia/issues/detail?id=32 494fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 495a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com This test code would fail when we didn't check the return result of 496a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com valid_unit_divide in SkChopCubicAt(... tValues[], int roots). The reason is 497a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com that after the first chop, the parameters to valid_unit_divide are equal 498a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com (thanks to finite float precision and rounding in the subtracts). Thus 499a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com even though the 2nd tValue looks < 1.0, after we renormalize it, we end 500a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com up with 1.0, hence the need to check and just return the last cubic as 501a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com a degenerate clump of 4 points in the sampe place. 502a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com 503a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com static void test_cubic() { 504a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkPoint src[4] = { 505a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.25000, 523.03003 }, 506a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.23999, 522.96002 }, 507a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.21997, 522.89001 }, 508a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.21997, 522.82001 } 509a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com }; 510a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkPoint dst[10]; 511a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkScalar tval[] = { 0.33333334f, 0.99999994f }; 512a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkChopCubicAt(src, dst, tval, 2); 513a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com } 514a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com */ 515a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com 516b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[], 517b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar tValues[], int roots) { 5188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 5198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 5208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = 0; i < roots - 1; i++) 5218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 5228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(is_unit_interval(tValues[i])); 5238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(is_unit_interval(tValues[i+1])); 5248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(tValues[i] < tValues[i+1]); 5258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 5288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 529b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (dst) { 530b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (roots == 0) { // nothing to chop 5318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 4*sizeof(SkPoint)); 532b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { 5338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t = tValues[0]; 5348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint tmp[4]; 5358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 536b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org for (int i = 0; i < roots; i++) { 5378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, t); 538b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (i == roots - 1) { 5398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 540b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 5418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst += 3; 543a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com // have src point to the remaining cubic (after the chop) 5448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(tmp, dst, 4 * sizeof(SkPoint)); 5458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com src = tmp; 546a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com 547a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com // watch out in case the renormalized t isn't in range 548a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com if (!valid_unit_divide(tValues[i+1] - tValues[i], 549a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SK_Scalar1 - tValues[i], &t)) { 550a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com // if we can't, just create a degenerate cubic 551a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com dst[4] = dst[5] = dst[6] = src[3]; 552a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com break; 553a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com } 5548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 559b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]) { 5608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 5618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 5628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 5638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 5648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x23 = SkScalarAve(src[2].fX, src[3].fX); 5658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y23 = SkScalarAve(src[2].fY, src[3].fY); 5668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x012 = SkScalarAve(x01, x12); 5688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y012 = SkScalarAve(y01, y12); 5698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x123 = SkScalarAve(x12, x23); 5708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y123 = SkScalarAve(y12, y23); 5718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0] = src[0]; 5738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[1].set(x01, y01); 5748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2].set(x012, y012); 5758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[3].set(SkScalarAve(x012, x123), SkScalarAve(y012, y123)); 5768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[4].set(x123, y123); 5778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[5].set(x23, y23); 5788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[6] = src[3]; 5798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 581b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic void flatten_double_cubic_extrema(SkScalar coords[14]) { 5828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coords[4] = coords[8] = coords[6]; 5838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that 586def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org the resulting beziers are monotonic in Y. This is called by the scan 587def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org converter. Depending on what is returned, dst[] is treated as follows: 5888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 dst[0..3] is the original cubic 5898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1 dst[0..3] and dst[3..6] are the two new cubics 5908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics 5918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com If dst == null, it is ignored and only the count is returned. 5928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 593bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.comint SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]) { 5948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar tValues[2]; 595bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com int roots = SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY, 596bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com src[3].fY, tValues); 597fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 5988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, tValues, roots); 599bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (dst && roots > 0) { 6008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we do some cleanup to ensure our Y extrema are flat 6018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com flatten_double_cubic_extrema(&dst[0].fY); 602bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (roots == 2) { 6038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com flatten_double_cubic_extrema(&dst[3].fY); 604bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 605bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 606bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com return roots; 607bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com} 608bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com 609bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.comint SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]) { 610bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com SkScalar tValues[2]; 611bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com int roots = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX, 612bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com src[3].fX, tValues); 613fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 614bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com SkChopCubicAt(src, dst, tValues, roots); 615bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (dst && roots > 0) { 616bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // we do some cleanup to ensure our Y extrema are flat 617bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com flatten_double_cubic_extrema(&dst[0].fX); 618bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (roots == 2) { 619bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com flatten_double_cubic_extrema(&dst[3].fX); 620bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 6218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return roots; 6238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** http://www.faculty.idc.ac.il/arik/quality/appendixA.html 6268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Inflection means that curvature is zero. 6288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Curvature is [F' x F''] / [F'^3] 6298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com So we solve F'x X F''y - F'y X F''y == 0 6308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com After some canceling of the cubic term, we get 6318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = b - a 6328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = c - 2b + a 6338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = d - 3c + 3b - a 6348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (BxCy - ByCx)t^2 + (AxCy - AyCx)t + AxBy - AyBx == 0 6358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 636b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[]) { 6378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ax = src[1].fX - src[0].fX; 6388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ay = src[1].fY - src[0].fY; 6398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Bx = src[2].fX - 2 * src[1].fX + src[0].fX; 6408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar By = src[2].fY - 2 * src[1].fY + src[0].fY; 6418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Cx = src[3].fX + 3 * (src[1].fX - src[2].fX) - src[0].fX; 6428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Cy = src[3].fY + 3 * (src[1].fY - src[2].fY) - src[0].fY; 6438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 644def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org return SkFindUnitQuadRoots(Bx*Cy - By*Cx, 645def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org Ax*Cy - Ay*Cx, 646def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org Ax*By - Ay*Bx, 647def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org tValues); 6488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 650b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopCubicAtInflections(const SkPoint src[], SkPoint dst[10]) { 6518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar tValues[2]; 6528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = SkFindCubicInflections(src, tValues); 6538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 654b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (dst) { 655b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (count == 0) { 6568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 4 * sizeof(SkPoint)); 657b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { 6588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, tValues, count); 659b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 6608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count + 1; 6628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6648dd31cf69e24ff82865309781107dfab948b6a02caryclark// See http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html (from the book GPU Gems 3) 6658dd31cf69e24ff82865309781107dfab948b6a02caryclark// discr(I) = d0^2 * (3*d1^2 - 4*d0*d2) 6668dd31cf69e24ff82865309781107dfab948b6a02caryclark// Classification: 6678dd31cf69e24ff82865309781107dfab948b6a02caryclark// discr(I) > 0 Serpentine 6688dd31cf69e24ff82865309781107dfab948b6a02caryclark// discr(I) = 0 Cusp 6698dd31cf69e24ff82865309781107dfab948b6a02caryclark// discr(I) < 0 Loop 6708dd31cf69e24ff82865309781107dfab948b6a02caryclark// d0 = d1 = 0 Quadratic 6718dd31cf69e24ff82865309781107dfab948b6a02caryclark// d0 = d1 = d2 = 0 Line 6728dd31cf69e24ff82865309781107dfab948b6a02caryclark// p0 = p1 = p2 = p3 Point 6738dd31cf69e24ff82865309781107dfab948b6a02caryclarkstatic SkCubicType classify_cubic(const SkPoint p[4], const SkScalar d[3]) { 6748dd31cf69e24ff82865309781107dfab948b6a02caryclark if (p[0] == p[1] && p[0] == p[2] && p[0] == p[3]) { 6758dd31cf69e24ff82865309781107dfab948b6a02caryclark return kPoint_SkCubicType; 6768dd31cf69e24ff82865309781107dfab948b6a02caryclark } 6778dd31cf69e24ff82865309781107dfab948b6a02caryclark const SkScalar discr = d[0] * d[0] * (3.f * d[1] * d[1] - 4.f * d[0] * d[2]); 6788dd31cf69e24ff82865309781107dfab948b6a02caryclark if (discr > SK_ScalarNearlyZero) { 6798dd31cf69e24ff82865309781107dfab948b6a02caryclark return kSerpentine_SkCubicType; 6808dd31cf69e24ff82865309781107dfab948b6a02caryclark } else if (discr < -SK_ScalarNearlyZero) { 6818dd31cf69e24ff82865309781107dfab948b6a02caryclark return kLoop_SkCubicType; 6828dd31cf69e24ff82865309781107dfab948b6a02caryclark } else { 6838dd31cf69e24ff82865309781107dfab948b6a02caryclark if (0.f == d[0] && 0.f == d[1]) { 6848dd31cf69e24ff82865309781107dfab948b6a02caryclark return (0.f == d[2] ? kLine_SkCubicType : kQuadratic_SkCubicType); 6858dd31cf69e24ff82865309781107dfab948b6a02caryclark } else { 6868dd31cf69e24ff82865309781107dfab948b6a02caryclark return kCusp_SkCubicType; 6878dd31cf69e24ff82865309781107dfab948b6a02caryclark } 6888dd31cf69e24ff82865309781107dfab948b6a02caryclark } 6898dd31cf69e24ff82865309781107dfab948b6a02caryclark} 6908dd31cf69e24ff82865309781107dfab948b6a02caryclark 6918dd31cf69e24ff82865309781107dfab948b6a02caryclark// Assumes the third component of points is 1. 6928dd31cf69e24ff82865309781107dfab948b6a02caryclark// Calcs p0 . (p1 x p2) 6938dd31cf69e24ff82865309781107dfab948b6a02caryclarkstatic SkScalar calc_dot_cross_cubic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { 6948dd31cf69e24ff82865309781107dfab948b6a02caryclark const SkScalar xComp = p0.fX * (p1.fY - p2.fY); 6958dd31cf69e24ff82865309781107dfab948b6a02caryclark const SkScalar yComp = p0.fY * (p2.fX - p1.fX); 6968dd31cf69e24ff82865309781107dfab948b6a02caryclark const SkScalar wComp = p1.fX * p2.fY - p1.fY * p2.fX; 6978dd31cf69e24ff82865309781107dfab948b6a02caryclark return (xComp + yComp + wComp); 6988dd31cf69e24ff82865309781107dfab948b6a02caryclark} 6998dd31cf69e24ff82865309781107dfab948b6a02caryclark 7008dd31cf69e24ff82865309781107dfab948b6a02caryclark// Calc coefficients of I(s,t) where roots of I are inflection points of curve 7018dd31cf69e24ff82865309781107dfab948b6a02caryclark// I(s,t) = t*(3*d0*s^2 - 3*d1*s*t + d2*t^2) 7028dd31cf69e24ff82865309781107dfab948b6a02caryclark// d0 = a1 - 2*a2+3*a3 7038dd31cf69e24ff82865309781107dfab948b6a02caryclark// d1 = -a2 + 3*a3 7048dd31cf69e24ff82865309781107dfab948b6a02caryclark// d2 = 3*a3 7058dd31cf69e24ff82865309781107dfab948b6a02caryclark// a1 = p0 . (p3 x p2) 7068dd31cf69e24ff82865309781107dfab948b6a02caryclark// a2 = p1 . (p0 x p3) 7078dd31cf69e24ff82865309781107dfab948b6a02caryclark// a3 = p2 . (p1 x p0) 7088dd31cf69e24ff82865309781107dfab948b6a02caryclark// Places the values of d1, d2, d3 in array d passed in 7098dd31cf69e24ff82865309781107dfab948b6a02caryclarkstatic void calc_cubic_inflection_func(const SkPoint p[4], SkScalar d[3]) { 7108dd31cf69e24ff82865309781107dfab948b6a02caryclark SkScalar a1 = calc_dot_cross_cubic(p[0], p[3], p[2]); 7118dd31cf69e24ff82865309781107dfab948b6a02caryclark SkScalar a2 = calc_dot_cross_cubic(p[1], p[0], p[3]); 7128dd31cf69e24ff82865309781107dfab948b6a02caryclark SkScalar a3 = calc_dot_cross_cubic(p[2], p[1], p[0]); 7138dd31cf69e24ff82865309781107dfab948b6a02caryclark 7148dd31cf69e24ff82865309781107dfab948b6a02caryclark // need to scale a's or values in later calculations will grow to high 7158dd31cf69e24ff82865309781107dfab948b6a02caryclark SkScalar max = SkScalarAbs(a1); 7168dd31cf69e24ff82865309781107dfab948b6a02caryclark max = SkMaxScalar(max, SkScalarAbs(a2)); 7178dd31cf69e24ff82865309781107dfab948b6a02caryclark max = SkMaxScalar(max, SkScalarAbs(a3)); 7188dd31cf69e24ff82865309781107dfab948b6a02caryclark max = 1.f/max; 7198dd31cf69e24ff82865309781107dfab948b6a02caryclark a1 = a1 * max; 7208dd31cf69e24ff82865309781107dfab948b6a02caryclark a2 = a2 * max; 7218dd31cf69e24ff82865309781107dfab948b6a02caryclark a3 = a3 * max; 7228dd31cf69e24ff82865309781107dfab948b6a02caryclark 7238dd31cf69e24ff82865309781107dfab948b6a02caryclark d[2] = 3.f * a3; 7248dd31cf69e24ff82865309781107dfab948b6a02caryclark d[1] = d[2] - a2; 7258dd31cf69e24ff82865309781107dfab948b6a02caryclark d[0] = d[1] - a2 + a1; 7268dd31cf69e24ff82865309781107dfab948b6a02caryclark} 7278dd31cf69e24ff82865309781107dfab948b6a02caryclark 7288dd31cf69e24ff82865309781107dfab948b6a02caryclarkSkCubicType SkClassifyCubic(const SkPoint src[4], SkScalar d[3]) { 7298dd31cf69e24ff82865309781107dfab948b6a02caryclark calc_cubic_inflection_func(src, d); 7308dd31cf69e24ff82865309781107dfab948b6a02caryclark return classify_cubic(src, d); 7318dd31cf69e24ff82865309781107dfab948b6a02caryclark} 7328dd31cf69e24ff82865309781107dfab948b6a02caryclark 733b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgtemplate <typename T> void bubble_sort(T array[], int count) { 7348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = count - 1; i > 0; --i) 7358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int j = i; j > 0; --j) 7368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (array[j] < array[j-1]) 7378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 7388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T tmp(array[j]); 7398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com array[j] = array[j-1]; 7408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com array[j-1] = tmp; 7418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 7428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 7438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 744087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com/** 745087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com * Given an array and count, remove all pair-wise duplicates from the array, 746087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com * keeping the existing sorting, and return the new count 747087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com */ 748b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic int collaps_duplicates(SkScalar array[], int count) { 749087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (int n = count; n > 1; --n) { 750087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com if (array[0] == array[1]) { 751087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (int i = 1; i < n; ++i) { 752087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com array[i - 1] = array[i]; 753087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 754087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com count -= 1; 755087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } else { 756087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com array += 1; 757087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 758087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 759087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com return count; 760087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com} 761087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 762087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com#ifdef SK_DEBUG 763087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 764087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com#define TEST_COLLAPS_ENTRY(array) array, SK_ARRAY_COUNT(array) 765087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 766087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.comstatic void test_collaps_duplicates() { 767087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com static bool gOnce; 768087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com if (gOnce) { return; } 769087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com gOnce = true; 770b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src0[] = { 0 }; 771b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src1[] = { 0, 0 }; 772b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src2[] = { 0, 1 }; 773b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src3[] = { 0, 0, 0 }; 774b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src4[] = { 0, 0, 1 }; 775b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src5[] = { 0, 1, 1 }; 776b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src6[] = { 0, 1, 2 }; 777087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com const struct { 778b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar* fData; 779087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int fCount; 780087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int fCollapsedCount; 781087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } data[] = { 782087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src0), 1 }, 783087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src1), 1 }, 784087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src2), 2 }, 785087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src3), 1 }, 786087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src4), 2 }, 787087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src5), 2 }, 788087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src6), 3 }, 789087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com }; 790087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (size_t i = 0; i < SK_ARRAY_COUNT(data); ++i) { 791b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar dst[3]; 792087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com memcpy(dst, data[i].fData, data[i].fCount * sizeof(dst[0])); 793087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int count = collaps_duplicates(dst, data[i].fCount); 794087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkASSERT(data[i].fCollapsedCount == count); 795087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (int j = 1; j < count; ++j) { 796087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkASSERT(dst[j-1] < dst[j]); 797087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 798087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 799087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com} 800087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com#endif 801087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 8023c12840b234e614faf569e80f311a77ce65d9fe0reed@google.comstatic SkScalar SkScalarCubeRoot(SkScalar x) { 803b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org return SkScalarPow(x, 0.3333333f); 8043c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com} 8053c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com 8068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Solve coeff(t) == 0, returning the number of roots that 8078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com lie withing 0 < t < 1. 8088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3] 809fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 810087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com Eliminates repeated roots (so that all tValues are distinct, and are always 811087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com in increasing order. 8128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 813b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic int solve_cubic_poly(const SkScalar coeff[4], SkScalar tValues[3]) { 814b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (SkScalarNearlyZero(coeff[0])) { // we're just a quadratic 8158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues); 8168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 8178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8183c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar a, b, c, Q, R; 8198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 8218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(coeff[0] != 0); 8228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8233c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar inva = SkScalarInvert(coeff[0]); 8243c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com a = coeff[1] * inva; 8253c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com b = coeff[2] * inva; 8263c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com c = coeff[3] * inva; 8278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 8283c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com Q = (a*a - b*3) / 9; 8293c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com R = (2*a*a*a - 9*a*b + 27*c) / 54; 8308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8313c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar Q3 = Q * Q * Q; 8323c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar R2MinusQ3 = R * R - Q3; 8333c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar adiv3 = a / 3; 8348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar* roots = tValues; 8368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar r; 8378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 838b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (R2MinusQ3 < 0) { // we have 3 real roots 839b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar theta = SkScalarACos(R / SkScalarSqrt(Q3)); 840b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar neg2RootQ = -2 * SkScalarSqrt(Q); 8418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 842b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org r = neg2RootQ * SkScalarCos(theta/3) - adiv3; 843b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_unit_interval(r)) { 8448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 845b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 846b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org r = neg2RootQ * SkScalarCos((theta + 2*SK_ScalarPI)/3) - adiv3; 847b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_unit_interval(r)) { 8488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 849b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 850b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org r = neg2RootQ * SkScalarCos((theta - 2*SK_ScalarPI)/3) - adiv3; 851b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_unit_interval(r)) { 8528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 853b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 854087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkDEBUGCODE(test_collaps_duplicates();) 855087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 8568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // now sort the roots 857087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int count = (int)(roots - tValues); 858087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkASSERT((unsigned)count <= 3); 859087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com bubble_sort(tValues, count); 860087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com count = collaps_duplicates(tValues, count); 861087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com roots = tValues + count; // so we compute the proper count below 862b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { // we have 1 real root 8633c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar A = SkScalarAbs(R) + SkScalarSqrt(R2MinusQ3); 8643c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com A = SkScalarCubeRoot(A); 865b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (R > 0) { 8663c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com A = -A; 867b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 868b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (A != 0) { 8693c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com A += Q / A; 870b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 8713c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com r = A - adiv3; 872b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_unit_interval(r)) { 8738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 874b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 8758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 8768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (int)(roots - tValues); 8788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 8798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Looking for F' dot F'' == 0 881fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 8828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = b - a 8838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = c - 2b + a 8848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = d - 3c + 3b - a 8858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' = 3Ct^2 + 6Bt + 3A 8878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F'' = 6Ct + 6B 8888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 8908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 891b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic void formulate_F1DotF2(const SkScalar src[], SkScalar coeff[4]) { 8928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar a = src[2] - src[0]; 8938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar b = src[4] - 2 * src[2] + src[0]; 8948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar c = src[6] + 3 * (src[2] - src[4]) - src[0]; 8958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8963c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeff[0] = c * c; 8973c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeff[1] = 3 * b * c; 8983c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeff[2] = 2 * b * b + c * a; 8993c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeff[3] = a * b; 9008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 9018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Looking for F' dot F'' == 0 903fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 9048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = b - a 9058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = c - 2b + a 9068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = d - 3c + 3b - a 9078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' = 3Ct^2 + 6Bt + 3A 9098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F'' = 6Ct + 6B 9108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 9128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 913b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]) { 9143c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar coeffX[4], coeffY[4]; 9153c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com int i; 9168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com formulate_F1DotF2(&src[0].fX, coeffX); 9188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com formulate_F1DotF2(&src[0].fY, coeffY); 9198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 920b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org for (i = 0; i < 4; i++) { 9213c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeffX[i] += coeffY[i]; 922b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 9238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t[3]; 925b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org int count = solve_cubic_poly(coeffX, t); 9268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int maxCount = 0; 9278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // now remove extrema where the curvature is zero (mins) 9298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // !!!! need a test for this !!!! 930b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org for (i = 0; i < count; i++) { 9318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // if (not_min_curvature()) 932b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (t[i] > 0 && t[i] < SK_Scalar1) { 9338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tValues[maxCount++] = t[i]; 934b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 9358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 9368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return maxCount; 9378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 9388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 939b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], 940b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar tValues[3]) { 9418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t_storage[3]; 9428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 943b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (tValues == NULL) { 9448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tValues = t_storage; 945b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 9468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = SkFindCubicMaxCurvature(src, tValues); 9488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9495383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com if (dst) { 950b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (count == 0) { 9518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 4 * sizeof(SkPoint)); 952b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { 9538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, tValues, count); 954b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 9558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 9568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count + 1; 9578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 9588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 959b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org/////////////////////////////////////////////////////////////////////////////// 9608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Find t value for quadratic [a, b, c] = d. 9628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Return 0 if there is no solution within [0, 1) 9638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 964b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic SkScalar quad_solve(SkScalar a, SkScalar b, SkScalar c, SkScalar d) { 9658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // At^2 + Bt + C = d 9668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = a - 2 * b + c; 9678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 2 * (b - a); 9688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = a - d; 9698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar roots[2]; 9718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = SkFindUnitQuadRoots(A, B, C, roots); 9728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(count <= 1); 9748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count == 1 ? roots[0] : 0; 9758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 9768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 977e1b75b4096c8ba9a569ae33d580806edd3c4a97arobertphillips@google.com/* given a quad-curve and a point (x,y), chop the quad at that point and place 97850df4d013f840749f70d1759c23c4217e727fd54skia.committer@gmail.com the new off-curve point and endpoint into 'dest'. 9799e1ec1a52985cce9db3a0d0e8d448b82a32e70cbskia.committer@gmail.com Should only return false if the computed pos is the start of the curve 980e1b75b4096c8ba9a569ae33d580806edd3c4a97arobertphillips@google.com (i.e. root == 0) 9818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 982b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic bool truncate_last_curve(const SkPoint quad[3], SkScalar x, SkScalar y, 983b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkPoint* dest) { 9848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkScalar* base; 9858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar value; 9868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (SkScalarAbs(x) < SkScalarAbs(y)) { 9888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com base = &quad[0].fX; 9898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com value = x; 9908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 9918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com base = &quad[0].fY; 9928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com value = y; 9938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 9948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // note: this returns 0 if it thinks value is out of range, meaning the 9968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // root might return something outside of [0, 1) 9978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t = quad_solve(base[0], base[2], base[4], value); 9988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 999b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (t > 0) { 10008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint tmp[5]; 10018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAt(quad, tmp, t); 1002e1b75b4096c8ba9a569ae33d580806edd3c4a97arobertphillips@google.com dest[0] = tmp[1]; 1003b0889a5aa610552bf306edc8d9a35d2d601acdb9robertphillips@google.com dest[1].set(x, y); 10048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 10058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 10068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /* t == 0 means either the value triggered a root outside of [0, 1) 10078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com For our purposes, we can ignore the <= 0 roots, but we want to 10088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com catch the >= 1 roots (which given our caller, will basically mean 10098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com a root of 1, give-or-take numerical instability). If we are in the 10108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com >= 1 case, return the existing offCurve point. 1011fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 10128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com The test below checks to see if we are close to the "end" of the 10138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com curve (near base[4]). Rather than specifying a tolerance, I just 10148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com check to see if value is on to the right/left of the middle point 10158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (depending on the direction/sign of the end points). 10168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 10178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((base[0] < base[4] && value > base[2]) || 10188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (base[0] > base[4] && value < base[2])) // should root have been 1 10198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 1020e1b75b4096c8ba9a569ae33d580806edd3c4a97arobertphillips@google.com dest[0] = quad[1]; 1021e1b75b4096c8ba9a569ae33d580806edd3c4a97arobertphillips@google.com dest[1].set(x, y); 10228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 10238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 10248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 10258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 10268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 10278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic const SkPoint gQuadCirclePts[kSkBuildQuadArcStorage] = { 1029f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org// The mid point of the quadratic arc approximation is half way between the two 1030f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org// control points. The float epsilon adjustment moves the on curve point out by 1031def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// two bits, distributing the convex test error between the round rect 1032def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// approximation and the convex cross product sign equality test. 1033def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org#define SK_MID_RRECT_OFFSET \ 1034def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org (SK_Scalar1 + SK_ScalarTanPIOver8 + FLT_EPSILON * 4) / 2 1035f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_Scalar1, 0 }, 1036f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_Scalar1, SK_ScalarTanPIOver8 }, 1037f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_MID_RRECT_OFFSET, SK_MID_RRECT_OFFSET }, 1038f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_ScalarTanPIOver8, SK_Scalar1 }, 1039f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org 1040f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { 0, SK_Scalar1 }, 1041f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_ScalarTanPIOver8, SK_Scalar1 }, 1042f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_MID_RRECT_OFFSET, SK_MID_RRECT_OFFSET }, 1043f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_Scalar1, SK_ScalarTanPIOver8 }, 1044f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org 1045f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_Scalar1, 0 }, 1046f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_Scalar1, -SK_ScalarTanPIOver8 }, 1047f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_MID_RRECT_OFFSET, -SK_MID_RRECT_OFFSET }, 1048f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { -SK_ScalarTanPIOver8, -SK_Scalar1 }, 1049f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org 1050f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { 0, -SK_Scalar1 }, 1051f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_ScalarTanPIOver8, -SK_Scalar1 }, 1052f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_MID_RRECT_OFFSET, -SK_MID_RRECT_OFFSET }, 1053f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_Scalar1, -SK_ScalarTanPIOver8 }, 1054f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org 1055f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org { SK_Scalar1, 0 } 1056f91aaecbe9d3630123d803d80f7b29f06c8976c7commit-bot@chromium.org#undef SK_MID_RRECT_OFFSET 10578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 10588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkBuildQuadArc(const SkVector& uStart, const SkVector& uStop, 10608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRotationDirection dir, const SkMatrix* userMatrix, 1061b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkPoint quadPoints[]) { 10628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // rotate by x,y so that uStart is (1.0) 10638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar x = SkPoint::DotProduct(uStart, uStop); 10648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar y = SkPoint::CrossProduct(uStart, uStop); 10658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar absX = SkScalarAbs(x); 10678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar absY = SkScalarAbs(y); 10688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int pointCount; 10708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // check for (effectively) coincident vectors 10728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // this can happen if our angle is nearly 0 or nearly 180 (y == 0) 10738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // ... we use the dot-prod to distinguish between 0 and 180 (x > 0) 10748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (absY <= SK_ScalarNearlyZero && x > 0 && 10758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ((y >= 0 && kCW_SkRotationDirection == dir) || 10768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (y <= 0 && kCCW_SkRotationDirection == dir))) { 1077fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 10788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // just return the start-point 10798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com quadPoints[0].set(SK_Scalar1, 0); 10808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com pointCount = 1; 10818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1082b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (dir == kCCW_SkRotationDirection) { 10838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com y = -y; 1084b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 10858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // what octant (quadratic curve) is [xy] in? 10868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int oct = 0; 10878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool sameSign = true; 10888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1089b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (0 == y) { 10908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct = 4; // 180 10918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero); 1092b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else if (0 == x) { 10938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero); 1094b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org oct = y > 0 ? 2 : 6; // 90 : 270 1095b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { 1096b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (y < 0) { 10978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct += 4; 1098b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 1099b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if ((x < 0) != (y < 0)) { 11008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct += 2; 11018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sameSign = false; 11028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1103b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if ((absX < absY) == sameSign) { 11048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com oct += 1; 1105b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 11068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 11078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int wholeCount = oct << 1; 11098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(quadPoints, gQuadCirclePts, (wholeCount + 1) * sizeof(SkPoint)); 11108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkPoint* arc = &gQuadCirclePts[wholeCount]; 1112b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (truncate_last_curve(arc, x, y, &quadPoints[wholeCount + 1])) { 11138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com wholeCount += 2; 11148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 11158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com pointCount = wholeCount + 1; 11168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 11178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // now handle counter-clockwise and the initial unitStart rotation 11198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkMatrix matrix; 11208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix.setSinCos(uStart.fY, uStart.fX); 11218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (dir == kCCW_SkRotationDirection) { 11228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix.preScale(SK_Scalar1, -SK_Scalar1); 11238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 11248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (userMatrix) { 11258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix.postConcat(*userMatrix); 11268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 11278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix.mapPoints(quadPoints, pointCount); 11288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return pointCount; 11298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1130c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 1131c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 1132def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org/////////////////////////////////////////////////////////////////////////////// 1133def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// 1134def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// NURB representation for conics. Helpful explanations at: 1135def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// 1136def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// http://citeseerx.ist.psu.edu/viewdoc/ 1137def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// download?doi=10.1.1.44.5740&rep=rep1&type=ps 1138def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// and 1139def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/NURBS/RB-conics.html 1140def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// 114117a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// F = (A (1 - t)^2 + C t^2 + 2 B (1 - t) t w) 114217a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// ------------------------------------------ 114317a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// ((1 - t)^2 + t^2 + 2 (1 - t) t w) 114417a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// 114517a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// = {t^2 (P0 + P2 - 2 P1 w), t (-2 P0 + 2 P1 w), P0} 114617a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// ------------------------------------------------ 114717a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// {t^2 (2 - 2 w), t (-2 + 2 w), 1} 114817a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// 114917a2c919d095797c364d407a5dbdb4d60533b953reed@google.com 11506862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.orgstatic SkScalar conic_eval_pos(const SkScalar src[], SkScalar w, SkScalar t) { 11510c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkASSERT(src); 11520c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkASSERT(t >= 0 && t <= SK_Scalar1); 115345fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 11540c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar src2w = SkScalarMul(src[2], w); 11550c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar C = src[0]; 11560c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar A = src[4] - 2 * src2w + C; 11570c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar B = 2 * (src2w - C); 11580c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar numer = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 115945fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 11600c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org B = 2 * (w - SK_Scalar1); 11610c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org C = SK_Scalar1; 11620c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org A = -B; 11630c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar denom = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 116445fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 11650c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return SkScalarDiv(numer, denom); 11660c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 116717a2c919d095797c364d407a5dbdb4d60533b953reed@google.com 11680c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org// F' = 2 (C t (1 + t (-1 + w)) - A (-1 + t) (t (-1 + w) - w) + B (1 - 2 t) w) 11690c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org// 11706862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// t^2 : (2 P0 - 2 P2 - 2 P0 w + 2 P2 w) 11716862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// t^1 : (-2 P0 + 2 P2 + 4 P0 w - 4 P1 w) 11726862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// t^0 : -2 P0 w + 2 P1 w 11736862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// 11746862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// We disregard magnitude, so we can freely ignore the denominator of F', and 11756862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// divide the numerator by 2 11760c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org// 117717a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// coeff[0] for t^2 11786862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// coeff[1] for t^1 11796862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// coeff[2] for t^0 118017a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// 1181def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.orgstatic void conic_deriv_coeff(const SkScalar src[], 1182def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org SkScalar w, 1183def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org SkScalar coeff[3]) { 11846862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org const SkScalar P20 = src[4] - src[0]; 11856862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org const SkScalar P10 = src[2] - src[0]; 11866862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org const SkScalar wP10 = w * P10; 11876862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org coeff[0] = w * P20 - P20; 11886862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org coeff[1] = P20 - 2 * wP10; 11896862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org coeff[2] = wP10; 11906862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org} 11916862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org 11926862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.orgstatic SkScalar conic_eval_tan(const SkScalar coord[], SkScalar w, SkScalar t) { 11936862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org SkScalar coeff[3]; 11946862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org conic_deriv_coeff(coord, w, coeff); 11956862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org return t * (t * coeff[0] + coeff[1]) + coeff[2]; 11960c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 11970c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 11986862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.orgstatic bool conic_find_extrema(const SkScalar src[], SkScalar w, SkScalar* t) { 11990c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar coeff[3]; 12006862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org conic_deriv_coeff(src, w, coeff); 12010c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 12020c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar tValues[2]; 12030c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org int roots = SkFindUnitQuadRoots(coeff[0], coeff[1], coeff[2], tValues); 12040c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkASSERT(0 == roots || 1 == roots); 120545fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 12060c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org if (1 == roots) { 12070c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org *t = tValues[0]; 12080c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return true; 12090c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org } 12100c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return false; 121117a2c919d095797c364d407a5dbdb4d60533b953reed@google.com} 121217a2c919d095797c364d407a5dbdb4d60533b953reed@google.com 12130d099557feb99707c8f601746f46f5a295eb33b7reed@google.comstruct SkP3D { 12140d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkScalar fX, fY, fZ; 12154bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 12160d099557feb99707c8f601746f46f5a295eb33b7reed@google.com void set(SkScalar x, SkScalar y, SkScalar z) { 12170d099557feb99707c8f601746f46f5a295eb33b7reed@google.com fX = x; fY = y; fZ = z; 12180d099557feb99707c8f601746f46f5a295eb33b7reed@google.com } 12194bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 12200d099557feb99707c8f601746f46f5a295eb33b7reed@google.com void projectDown(SkPoint* dst) const { 12210d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst->set(fX / fZ, fY / fZ); 12220d099557feb99707c8f601746f46f5a295eb33b7reed@google.com } 12230d099557feb99707c8f601746f46f5a295eb33b7reed@google.com}; 12240d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 1225d50d87a185d26a38d7100bbbb119be17947aa5e4commit-bot@chromium.org// We only interpolate one dimension at a time (the first, at +0, +3, +6). 1226d50d87a185d26a38d7100bbbb119be17947aa5e4commit-bot@chromium.orgstatic void p3d_interp(const SkScalar src[7], SkScalar dst[7], SkScalar t) { 12270d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkScalar ab = SkScalarInterp(src[0], src[3], t); 12280d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkScalar bc = SkScalarInterp(src[3], src[6], t); 12290d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[0] = ab; 12300d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[3] = SkScalarInterp(ab, bc, t); 12310d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[6] = bc; 12320d099557feb99707c8f601746f46f5a295eb33b7reed@google.com} 12330d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 12340d099557feb99707c8f601746f46f5a295eb33b7reed@google.comstatic void ratquad_mapTo3D(const SkPoint src[3], SkScalar w, SkP3D dst[]) { 12350d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[0].set(src[0].fX * 1, src[0].fY * 1, 1); 12360d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[1].set(src[1].fX * w, src[1].fY * w, w); 12370d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[2].set(src[2].fX * 1, src[2].fY * 1, 1); 12380d099557feb99707c8f601746f46f5a295eb33b7reed@google.com} 12390d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 124024bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.comvoid SkConic::evalAt(SkScalar t, SkPoint* pt, SkVector* tangent) const { 1241c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com SkASSERT(t >= 0 && t <= SK_Scalar1); 12424bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 1243c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com if (pt) { 12446862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org pt->set(conic_eval_pos(&fPts[0].fX, fW, t), 12456862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org conic_eval_pos(&fPts[0].fY, fW, t)); 1246c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com } 124724bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com if (tangent) { 124824bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com tangent->set(conic_eval_tan(&fPts[0].fX, fW, t), 124924bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com conic_eval_tan(&fPts[0].fY, fW, t)); 125024bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com } 1251c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com} 1252c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 125328552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::chopAt(SkScalar t, SkConic dst[2]) const { 12540d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkP3D tmp[3], tmp2[3]; 12550d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 12560d099557feb99707c8f601746f46f5a295eb33b7reed@google.com ratquad_mapTo3D(fPts, fW, tmp); 12574bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 12580d099557feb99707c8f601746f46f5a295eb33b7reed@google.com p3d_interp(&tmp[0].fX, &tmp2[0].fX, t); 12590d099557feb99707c8f601746f46f5a295eb33b7reed@google.com p3d_interp(&tmp[0].fY, &tmp2[0].fY, t); 12600d099557feb99707c8f601746f46f5a295eb33b7reed@google.com p3d_interp(&tmp[0].fZ, &tmp2[0].fZ, t); 12614bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 12620d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[0].fPts[0] = fPts[0]; 12630d099557feb99707c8f601746f46f5a295eb33b7reed@google.com tmp2[0].projectDown(&dst[0].fPts[1]); 12640d099557feb99707c8f601746f46f5a295eb33b7reed@google.com tmp2[1].projectDown(&dst[0].fPts[2]); dst[1].fPts[0] = dst[0].fPts[2]; 12650d099557feb99707c8f601746f46f5a295eb33b7reed@google.com tmp2[2].projectDown(&dst[1].fPts[1]); 12660d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[1].fPts[2] = fPts[2]; 12670d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 12684af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // to put in "standard form", where w0 and w2 are both 1, we compute the 12694af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // new w1 as sqrt(w1*w1/w0*w2) 12704af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // or 12714af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // w1 /= sqrt(w0*w2) 12724af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // 1273def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org // However, in our case, we know that for dst[0]: 1274def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org // w0 == 1, and for dst[1], w2 == 1 12754af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // 12764af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org SkScalar root = SkScalarSqrt(tmp2[1].fZ); 12774af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org dst[0].fW = tmp2[0].fZ / root; 12784af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org dst[1].fW = tmp2[2].fZ / root; 1279c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com} 12808d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org 1281b640203cd5733aaf110277e28e22007c5b541565reedstatic Sk2s times_2(const Sk2s& value) { 1282b640203cd5733aaf110277e28e22007c5b541565reed return value + value; 1283b640203cd5733aaf110277e28e22007c5b541565reed} 1284b640203cd5733aaf110277e28e22007c5b541565reed 1285b640203cd5733aaf110277e28e22007c5b541565reedSkPoint SkConic::evalAt(SkScalar t) const { 1286b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p0 = from_point(fPts[0]); 1287b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p1 = from_point(fPts[1]); 1288b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p2 = from_point(fPts[2]); 1289b640203cd5733aaf110277e28e22007c5b541565reed Sk2s tt = Sk2s(t); 1290b640203cd5733aaf110277e28e22007c5b541565reed Sk2s ww = Sk2s(fW); 1291b640203cd5733aaf110277e28e22007c5b541565reed Sk2s one = Sk2s(1); 1292b640203cd5733aaf110277e28e22007c5b541565reed 1293b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p1w = p1 * ww; 1294b640203cd5733aaf110277e28e22007c5b541565reed Sk2s C = p0; 1295b640203cd5733aaf110277e28e22007c5b541565reed Sk2s A = p2 - times_2(p1w) + p0; 1296b640203cd5733aaf110277e28e22007c5b541565reed Sk2s B = times_2(p1w - C); 1297b640203cd5733aaf110277e28e22007c5b541565reed Sk2s numer = quad_poly_eval(A, B, C, tt); 1298b640203cd5733aaf110277e28e22007c5b541565reed 1299b640203cd5733aaf110277e28e22007c5b541565reed B = times_2(ww - one); 1300b640203cd5733aaf110277e28e22007c5b541565reed A = -B; 1301b640203cd5733aaf110277e28e22007c5b541565reed Sk2s denom = quad_poly_eval(A, B, one, tt); 1302b640203cd5733aaf110277e28e22007c5b541565reed 1303b640203cd5733aaf110277e28e22007c5b541565reed return to_point(numer / denom); 1304b640203cd5733aaf110277e28e22007c5b541565reed} 1305b640203cd5733aaf110277e28e22007c5b541565reed 1306b640203cd5733aaf110277e28e22007c5b541565reedSkVector SkConic::evalTangentAt(SkScalar t) const { 1307b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p0 = from_point(fPts[0]); 1308b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p1 = from_point(fPts[1]); 1309b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p2 = from_point(fPts[2]); 1310b640203cd5733aaf110277e28e22007c5b541565reed Sk2s ww = Sk2s(fW); 1311b640203cd5733aaf110277e28e22007c5b541565reed 1312b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p20 = p2 - p0; 1313b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p10 = p1 - p0; 1314b640203cd5733aaf110277e28e22007c5b541565reed 1315b640203cd5733aaf110277e28e22007c5b541565reed Sk2s C = ww * p10; 1316b640203cd5733aaf110277e28e22007c5b541565reed Sk2s A = ww * p20 - p20; 1317b640203cd5733aaf110277e28e22007c5b541565reed Sk2s B = p20 - C - C; 1318b640203cd5733aaf110277e28e22007c5b541565reed 1319b640203cd5733aaf110277e28e22007c5b541565reed return to_vector(quad_poly_eval(A, B, C, Sk2s(t))); 1320b640203cd5733aaf110277e28e22007c5b541565reed#if 0 1321b640203cd5733aaf110277e28e22007c5b541565reed static void conic_deriv_coeff(const SkScalar src[], 1322b640203cd5733aaf110277e28e22007c5b541565reed SkScalar w, 1323b640203cd5733aaf110277e28e22007c5b541565reed SkScalar coeff[3]) { 1324b640203cd5733aaf110277e28e22007c5b541565reed const SkScalar P20 = src[4] - src[0]; 1325b640203cd5733aaf110277e28e22007c5b541565reed const SkScalar P10 = src[2] - src[0]; 1326b640203cd5733aaf110277e28e22007c5b541565reed const SkScalar wP10 = w * P10; 1327b640203cd5733aaf110277e28e22007c5b541565reed coeff[0] = w * P20 - P20; 1328b640203cd5733aaf110277e28e22007c5b541565reed coeff[1] = P20 - 2 * wP10; 1329b640203cd5733aaf110277e28e22007c5b541565reed coeff[2] = wP10; 1330b640203cd5733aaf110277e28e22007c5b541565reed } 1331b640203cd5733aaf110277e28e22007c5b541565reed 1332b640203cd5733aaf110277e28e22007c5b541565reed static SkScalar conic_eval_tan(const SkScalar coord[], SkScalar w, SkScalar t) { 1333b640203cd5733aaf110277e28e22007c5b541565reed SkScalar coeff[3]; 1334b640203cd5733aaf110277e28e22007c5b541565reed conic_deriv_coeff(coord, w, coeff); 1335b640203cd5733aaf110277e28e22007c5b541565reed return t * (t * coeff[0] + coeff[1]) + coeff[2]; 1336b640203cd5733aaf110277e28e22007c5b541565reed } 1337b640203cd5733aaf110277e28e22007c5b541565reed#endif 1338b640203cd5733aaf110277e28e22007c5b541565reed} 1339b640203cd5733aaf110277e28e22007c5b541565reed 13403df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.orgstatic SkScalar subdivide_w_value(SkScalar w) { 13416862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org return SkScalarSqrt(SK_ScalarHalf + w * SK_ScalarHalf); 13423df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 13433df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 134428552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::chop(SkConic dst[2]) const { 13458d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar scale = SkScalarInvert(SK_Scalar1 + fW); 13468d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar p1x = fW * fPts[1].fX; 13478d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar p1y = fW * fPts[1].fY; 13488d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar mx = (fPts[0].fX + 2 * p1x + fPts[2].fX) * scale * SK_ScalarHalf; 13498d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org SkScalar my = (fPts[0].fY + 2 * p1y + fPts[2].fY) * scale * SK_ScalarHalf; 13508d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org 13518d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[0].fPts[0] = fPts[0]; 13528d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[0].fPts[1].set((fPts[0].fX + p1x) * scale, 13538d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org (fPts[0].fY + p1y) * scale); 13548d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[0].fPts[2].set(mx, my); 13558d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org 13568d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[1].fPts[0].set(mx, my); 13578d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[1].fPts[1].set((p1x + fPts[2].fX) * scale, 13588d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org (p1y + fPts[2].fY) * scale); 13598d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org dst[1].fPts[2] = fPts[2]; 13608d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org 13613df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org dst[0].fW = dst[1].fW = subdivide_w_value(fW); 13623df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 13633df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 1364b640203cd5733aaf110277e28e22007c5b541565reedvoid SkConic::chop2(SkConic * SK_RESTRICT dst) const { 1365b640203cd5733aaf110277e28e22007c5b541565reed Sk2s scale(SkScalarInvert(SK_Scalar1 + fW)); 1366b640203cd5733aaf110277e28e22007c5b541565reed// Sk2s scale = Sk2s(SK_Scalar1 + fW).invert(); 1367b640203cd5733aaf110277e28e22007c5b541565reed SkScalar newW = subdivide_w_value(fW); 1368b640203cd5733aaf110277e28e22007c5b541565reed 1369b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p0 = from_point(fPts[0]); 1370b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p1 = from_point(fPts[1]); 1371b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p2 = from_point(fPts[2]); 1372b640203cd5733aaf110277e28e22007c5b541565reed Sk2s ww = Sk2s(fW); 1373b640203cd5733aaf110277e28e22007c5b541565reed Sk2s half = Sk2s(0.5f); 1374b640203cd5733aaf110277e28e22007c5b541565reed 1375b640203cd5733aaf110277e28e22007c5b541565reed Sk2s wp1 = ww * p1; 1376b640203cd5733aaf110277e28e22007c5b541565reed Sk2s m = ((p0 + wp1 + wp1 + p2) * half) * scale; 1377b640203cd5733aaf110277e28e22007c5b541565reed 1378b640203cd5733aaf110277e28e22007c5b541565reed dst[0].fPts[0] = fPts[0]; 1379b640203cd5733aaf110277e28e22007c5b541565reed dst[0].fPts[1] = to_point((p0 + wp1) * scale); 1380b640203cd5733aaf110277e28e22007c5b541565reed dst[0].fPts[2] = dst[1].fPts[0] = to_point(m); 1381b640203cd5733aaf110277e28e22007c5b541565reed dst[1].fPts[1] = to_point((wp1 + p2) * scale); 1382b640203cd5733aaf110277e28e22007c5b541565reed dst[1].fPts[2] = fPts[2]; 1383b640203cd5733aaf110277e28e22007c5b541565reed 1384b640203cd5733aaf110277e28e22007c5b541565reed dst[0].fW = dst[1].fW = newW; 1385b640203cd5733aaf110277e28e22007c5b541565reed} 1386b640203cd5733aaf110277e28e22007c5b541565reed 138797514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org/* 138897514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org * "High order approximation of conic sections by quadratic splines" 138997514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org * by Michael Floater, 1993 139097514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org */ 1391af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org#define AS_QUAD_ERROR_SETUP \ 1392af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar a = fW - 1; \ 1393af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar k = a / (4 * (2 + a)); \ 1394af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar x = k * (fPts[0].fX - 2 * fPts[1].fX + fPts[2].fX); \ 1395af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar y = k * (fPts[0].fY - 2 * fPts[1].fY + fPts[2].fY); 1396af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 1397af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.orgvoid SkConic::computeAsQuadError(SkVector* err) const { 1398af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org AS_QUAD_ERROR_SETUP 1399af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org err->set(x, y); 1400af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org} 1401af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 1402af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.orgbool SkConic::asQuadTol(SkScalar tol) const { 1403af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org AS_QUAD_ERROR_SETUP 1404af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org return (x * x + y * y) <= tol * tol; 140597514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org} 14067841c63136e8aa2d3aadbeab8432405abcd73c32skia.committer@gmail.com 1407f16c00e41b72daa81ed7efacbead06b387767841reed// Limit the number of suggested quads to approximate a conic 1408f16c00e41b72daa81ed7efacbead06b387767841reed#define kMaxConicToQuadPOW2 5 1409f16c00e41b72daa81ed7efacbead06b387767841reed 141097514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.orgint SkConic::computeQuadPOW2(SkScalar tol) const { 1411f16c00e41b72daa81ed7efacbead06b387767841reed if (tol < 0 || !SkScalarIsFinite(tol)) { 1412f16c00e41b72daa81ed7efacbead06b387767841reed return 0; 1413f16c00e41b72daa81ed7efacbead06b387767841reed } 1414f16c00e41b72daa81ed7efacbead06b387767841reed 1415af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org AS_QUAD_ERROR_SETUP 1416f16c00e41b72daa81ed7efacbead06b387767841reed 1417f16c00e41b72daa81ed7efacbead06b387767841reed SkScalar error = SkScalarSqrt(x * x + y * y); 1418f16c00e41b72daa81ed7efacbead06b387767841reed int pow2; 1419f16c00e41b72daa81ed7efacbead06b387767841reed for (pow2 = 0; pow2 < kMaxConicToQuadPOW2; ++pow2) { 1420f16c00e41b72daa81ed7efacbead06b387767841reed if (error <= tol) { 1421f16c00e41b72daa81ed7efacbead06b387767841reed break; 1422f16c00e41b72daa81ed7efacbead06b387767841reed } 1423f16c00e41b72daa81ed7efacbead06b387767841reed error *= 0.25f; 1424f16c00e41b72daa81ed7efacbead06b387767841reed } 1425f16c00e41b72daa81ed7efacbead06b387767841reed // float version -- using ceil gives the same results as the above. 1426f16c00e41b72daa81ed7efacbead06b387767841reed if (false) { 1427f16c00e41b72daa81ed7efacbead06b387767841reed SkScalar err = SkScalarSqrt(x * x + y * y); 1428f16c00e41b72daa81ed7efacbead06b387767841reed if (err <= tol) { 1429f16c00e41b72daa81ed7efacbead06b387767841reed return 0; 1430f16c00e41b72daa81ed7efacbead06b387767841reed } 1431f16c00e41b72daa81ed7efacbead06b387767841reed SkScalar tol2 = tol * tol; 1432f16c00e41b72daa81ed7efacbead06b387767841reed if (tol2 == 0) { 1433f16c00e41b72daa81ed7efacbead06b387767841reed return kMaxConicToQuadPOW2; 1434f16c00e41b72daa81ed7efacbead06b387767841reed } 1435f16c00e41b72daa81ed7efacbead06b387767841reed SkScalar fpow2 = SkScalarLog2((x * x + y * y) / tol2) * 0.25f; 1436f16c00e41b72daa81ed7efacbead06b387767841reed int altPow2 = SkScalarCeilToInt(fpow2); 1437f16c00e41b72daa81ed7efacbead06b387767841reed if (altPow2 != pow2) { 1438f16c00e41b72daa81ed7efacbead06b387767841reed SkDebugf("pow2 %d altPow2 %d fbits %g err %g tol %g\n", pow2, altPow2, fpow2, err, tol); 1439f16c00e41b72daa81ed7efacbead06b387767841reed } 1440f16c00e41b72daa81ed7efacbead06b387767841reed pow2 = altPow2; 1441f16c00e41b72daa81ed7efacbead06b387767841reed } 1442f16c00e41b72daa81ed7efacbead06b387767841reed return pow2; 14433df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 14443df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 144528552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgstatic SkPoint* subdivide(const SkConic& src, SkPoint pts[], int level) { 14463df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org SkASSERT(level >= 0); 1447af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 14483df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org if (0 == level) { 14493df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org memcpy(pts, &src.fPts[1], 2 * sizeof(SkPoint)); 14503df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org return pts + 2; 14513df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org } else { 145228552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org SkConic dst[2]; 14533df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org src.chop(dst); 14543df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org --level; 14553df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org pts = subdivide(dst[0], pts, level); 14563df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org return subdivide(dst[1], pts, level); 14573df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org } 14588d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org} 14593df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 146028552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgint SkConic::chopIntoQuadsPOW2(SkPoint pts[], int pow2) const { 1461af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkASSERT(pow2 >= 0); 14623df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org *pts = fPts[0]; 1463aebfa7e1b1e94f693f3e7beb6ad43cfcb0f69e98reed@google.com SkDEBUGCODE(SkPoint* endPts =) subdivide(*this, pts + 1, pow2); 14643df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org SkASSERT(endPts - pts == (2 * (1 << pow2) + 1)); 14653df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org return 1 << pow2; 14663df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 14670c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 146828552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::findXExtrema(SkScalar* t) const { 14696862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org return conic_find_extrema(&fPts[0].fX, fW, t); 14700c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 14710c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 147228552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::findYExtrema(SkScalar* t) const { 14736862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org return conic_find_extrema(&fPts[0].fY, fW, t); 14740c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 14750c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 147628552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::chopAtXExtrema(SkConic dst[2]) const { 14770c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar t; 14780c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org if (this->findXExtrema(&t)) { 14790c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org this->chopAt(t, dst); 14800c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // now clean-up the middle, since we know t was meant to be at 14810c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // an X-extrema 14820c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar value = dst[0].fPts[2].fX; 14830c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[0].fPts[1].fX = value; 14840c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[0].fX = value; 14850c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[1].fX = value; 14860c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return true; 14870c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org } 14880c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return false; 14890c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 14900c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 149128552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::chopAtYExtrema(SkConic dst[2]) const { 14920c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar t; 14930c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org if (this->findYExtrema(&t)) { 14940c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org this->chopAt(t, dst); 14950c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // now clean-up the middle, since we know t was meant to be at 14960c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // an Y-extrema 14970c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar value = dst[0].fPts[2].fY; 14980c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[0].fPts[1].fY = value; 14990c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[0].fY = value; 15000c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[1].fY = value; 15010c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return true; 15020c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org } 15030c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return false; 15040c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 15050c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 150628552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::computeTightBounds(SkRect* bounds) const { 15075c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org SkPoint pts[4]; 15085c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org pts[0] = fPts[0]; 15095c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org pts[1] = fPts[2]; 15105c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org int count = 2; 15115c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org 15125c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org SkScalar t; 15135c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org if (this->findXExtrema(&t)) { 15145c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org this->evalAt(t, &pts[count++]); 15155c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org } 15165c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org if (this->findYExtrema(&t)) { 15175c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org this->evalAt(t, &pts[count++]); 15185c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org } 15195c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org bounds->set(pts, count); 15205c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org} 15215c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org 152228552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::computeFastBounds(SkRect* bounds) const { 15235c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org bounds->set(fPts, 3); 15245c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org} 1525def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org 1526def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.orgbool SkConic::findMaxCurvature(SkScalar* t) const { 1527def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org // TODO: Implement me 1528def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org return false; 1529def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org} 1530220f926d9d4b38a9018c922c095847bbd261f583reed 1531220f926d9d4b38a9018c922c095847bbd261f583reedSkScalar SkConic::TransformW(const SkPoint pts[], SkScalar w, 1532220f926d9d4b38a9018c922c095847bbd261f583reed const SkMatrix& matrix) { 1533220f926d9d4b38a9018c922c095847bbd261f583reed if (!matrix.hasPerspective()) { 1534220f926d9d4b38a9018c922c095847bbd261f583reed return w; 1535220f926d9d4b38a9018c922c095847bbd261f583reed } 1536220f926d9d4b38a9018c922c095847bbd261f583reed 1537220f926d9d4b38a9018c922c095847bbd261f583reed SkP3D src[3], dst[3]; 1538950e986b1bc127af1f484572d2494091957486f9mtklein 1539220f926d9d4b38a9018c922c095847bbd261f583reed ratquad_mapTo3D(pts, w, src); 1540220f926d9d4b38a9018c922c095847bbd261f583reed 1541220f926d9d4b38a9018c922c095847bbd261f583reed matrix.mapHomogeneousPoints(&dst[0].fX, &src[0].fX, 3); 1542220f926d9d4b38a9018c922c095847bbd261f583reed 1543220f926d9d4b38a9018c922c095847bbd261f583reed // w' = sqrt(w1*w1/w0*w2) 1544220f926d9d4b38a9018c922c095847bbd261f583reed SkScalar w0 = dst[0].fZ; 1545220f926d9d4b38a9018c922c095847bbd261f583reed SkScalar w1 = dst[1].fZ; 1546220f926d9d4b38a9018c922c095847bbd261f583reed SkScalar w2 = dst[2].fZ; 1547220f926d9d4b38a9018c922c095847bbd261f583reed w = SkScalarSqrt((w1 * w1) / (w0 * w2)); 1548220f926d9d4b38a9018c922c095847bbd261f583reed return w; 1549220f926d9d4b38a9018c922c095847bbd261f583reed} 1550d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1551d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reedint SkConic::BuildUnitArc(const SkVector& uStart, const SkVector& uStop, SkRotationDirection dir, 1552d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkMatrix* userMatrix, SkConic dst[kMaxConicsForArc]) { 1553d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // rotate by x,y so that uStart is (1.0) 1554d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkScalar x = SkPoint::DotProduct(uStart, uStop); 1555d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkScalar y = SkPoint::CrossProduct(uStart, uStop); 1556d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1557d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkScalar absY = SkScalarAbs(y); 1558d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1559d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // check for (effectively) coincident vectors 1560d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // this can happen if our angle is nearly 0 or nearly 180 (y == 0) 1561d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // ... we use the dot-prod to distinguish between 0 and 180 (x > 0) 1562d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if (absY <= SK_ScalarNearlyZero && x > 0 && ((y >= 0 && kCW_SkRotationDirection == dir) || 1563d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed (y <= 0 && kCCW_SkRotationDirection == dir))) { 1564d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed return 0; 1565d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1566d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1567d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if (dir == kCCW_SkRotationDirection) { 1568d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed y = -y; 1569d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1570d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1571d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // We decide to use 1-conic per quadrant of a circle. What quadrant does [xy] lie in? 1572d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // 0 == [0 .. 90) 1573d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // 1 == [90 ..180) 1574d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // 2 == [180..270) 1575d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // 3 == [270..360) 1576d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // 1577d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed int quadrant = 0; 1578d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if (0 == y) { 1579d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed quadrant = 2; // 180 1580d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero); 1581d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } else if (0 == x) { 1582d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero); 1583d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed quadrant = y > 0 ? 1 : 3; // 90 : 270 1584d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } else { 1585d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if (y < 0) { 1586d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed quadrant += 2; 1587d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1588d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if ((x < 0) != (y < 0)) { 1589d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed quadrant += 1; 1590d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1591d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1592d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1593d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkPoint quadrantPts[] = { 1594d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 }, { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 } 1595d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed }; 1596d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkScalar quadrantWeight = SK_ScalarRoot2Over2; 1597d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1598d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed int conicCount = quadrant; 1599d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed for (int i = 0; i < conicCount; ++i) { 1600d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed dst[i].set(&quadrantPts[i * 2], quadrantWeight); 1601d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1602d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1603d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // Now compute any remaing (sub-90-degree) arc for the last conic 1604d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkPoint finalP = { x, y }; 1605d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkPoint& lastQ = quadrantPts[quadrant * 2]; // will already be a unit-vector 1606d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkScalar dot = SkVector::DotProduct(lastQ, finalP); 160788f0a99fd48cfb30ca5596182f8932d76cd76f17reed SkASSERT(0 <= dot && dot <= SK_Scalar1 + SK_ScalarNearlyZero); 1608d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1609d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if (dot < 1 - SK_ScalarNearlyZero) { 1610d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkVector offCurve = { lastQ.x() + x, lastQ.y() + y }; 1611d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // compute the bisector vector, and then rescale to be the off-curve point. 1612d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // we compute its length from cos(theta/2) = length / 1, using half-angle identity we get 1613d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // length = sqrt(2 / (1 + cos(theta)). We already have cos() when to computed the dot. 1614d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // This is nice, since our computed weight is cos(theta/2) as well! 1615d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // 1616d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkScalar cosThetaOver2 = SkScalarSqrt((1 + dot) / 2); 1617d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed offCurve.setLength(SkScalarInvert(cosThetaOver2)); 1618d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed dst[conicCount].set(lastQ, offCurve, finalP, cosThetaOver2); 1619d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed conicCount += 1; 1620d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1621d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1622d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // now handle counter-clockwise and the initial unitStart rotation 1623d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkMatrix matrix; 1624d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed matrix.setSinCos(uStart.fY, uStart.fX); 1625d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if (dir == kCCW_SkRotationDirection) { 1626d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed matrix.preScale(SK_Scalar1, -SK_Scalar1); 1627d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1628d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if (userMatrix) { 1629d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed matrix.postConcat(*userMatrix); 1630d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1631d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed for (int i = 0; i < conicCount; ++i) { 1632d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed matrix.mapPoints(dst[i].fPts, 3); 1633d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1634d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed return conicCount; 1635d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed} 1636