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" 10c9adb05b64fa0bfadf9d1a782afcda470da68c9emtklein#include "SkNx.h" 11e4442cb0b537720ab32106b3b5353dbb78f11b26Cary Clark#include "SkPoint3.h" 12df429f3beac1c191289ba1e3bd918bf84df57bf5Cary Clark#include "SkPointPriv.h" 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 14b640203cd5733aaf110277e28e22007c5b541565reedstatic SkVector to_vector(const Sk2s& x) { 15b640203cd5733aaf110277e28e22007c5b541565reed SkVector vector; 16507ef6d68115ae9e6d884bb36436a1463523d893mtklein x.store(&vector); 17b640203cd5733aaf110277e28e22007c5b541565reed return vector; 18b640203cd5733aaf110277e28e22007c5b541565reed} 19b640203cd5733aaf110277e28e22007c5b541565reed 208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//////////////////////////////////////////////////////////////////////// 218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 22b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic int is_not_monotonic(SkScalar a, SkScalar b, SkScalar c) { 23b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar ab = a - b; 24b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar bc = b - c; 258f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com if (ab < 0) { 268f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com bc = -bc; 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 288f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com return ab == 0 || bc < 0; 298f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com} 308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//////////////////////////////////////////////////////////////////////// 328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 33b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic bool is_unit_interval(SkScalar x) { 348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return x > 0 && x < SK_Scalar1; 358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 37b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic int valid_unit_divide(SkScalar numer, SkScalar denom, SkScalar* ratio) { 388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(ratio); 398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 40b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (numer < 0) { 418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com numer = -numer; 428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com denom = -denom; 438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 45b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (denom == 0 || numer == 0 || numer >= denom) { 468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 47b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4980ea19ca4bdd68c1493666a5fe7e4ce9d43ded8breed SkScalar r = numer / denom; 5015161620bee33efcb706685486c9ce0fb51a72bbreed@android.com if (SkScalarIsNaN(r)) { 5115161620bee33efcb706685486c9ce0fb51a72bbreed@android.com return 0; 5215161620bee33efcb706685486c9ce0fb51a72bbreed@android.com } 5311fca3f29f0117eda798c67fafde40465d9903e1Mike Klein SkASSERTF(r >= 0 && r < SK_Scalar1, "numer %f, denom %f, r %f", numer, denom, r); 54b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (r == 0) { // catch underflow if numer <<<< denom 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 56b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *ratio = r; 588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1; 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** From Numerical Recipes in C. 628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Q = -1/2 (B + sign(B) sqrt[B*B - 4*A*C]) 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com x1 = Q / A 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com x2 = C / Q 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 67b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]) { 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(roots); 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 70b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (A == 0) { 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return valid_unit_divide(-C, B, roots); 72b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar* r = roots; 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 76b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar R = B*B - 4*A*C; 77dbaec7323f20c3a7e8a234dac9dfb8a9446a2717caryclark if (R < 0 || !SkScalarIsFinite(R)) { // complex roots 783323b05be5aacb6008e8e09fd922d0c9269e4c07caryclark // if R is infinite, it's possible that it may still produce 793323b05be5aacb6008e8e09fd922d0c9269e4c07caryclark // useful results if the operation was repeated in doubles 803323b05be5aacb6008e8e09fd922d0c9269e4c07caryclark // the flipside is determining if the more precise answer 813323b05be5aacb6008e8e09fd922d0c9269e4c07caryclark // isn't useful because surrounding machinery (e.g., subtracting 823323b05be5aacb6008e8e09fd922d0c9269e4c07caryclark // the axis offset from C) already discards the extra precision 833323b05be5aacb6008e8e09fd922d0c9269e4c07caryclark // more investigation and unit tests required... 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 8515161620bee33efcb706685486c9ce0fb51a72bbreed@android.com } 86b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org R = SkScalarSqrt(R); 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Q = (B < 0) ? -(B-R)/2 : -(B+R)/2; 898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r += valid_unit_divide(Q, A, r); 908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r += valid_unit_divide(C, Q, r); 91b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (r - roots == 2) { 928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (roots[0] > roots[1]) 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTSwap<SkScalar>(roots[0], roots[1]); 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else if (roots[0] == roots[1]) // nearly-equal? 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r -= 1; // skip the double root 968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (int)(r - roots); 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1008f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com/////////////////////////////////////////////////////////////////////////////// 1018f4d2306fa866a26f9448048ff63f692b2ba43aareed@google.com/////////////////////////////////////////////////////////////////////////////// 1028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10365cb2cd2f7ad4146f055810b8bd77bff03a4e76ereedvoid SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent) { 1048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 1058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 106950e986b1bc127af1f484572d2494091957486f9mtklein 107b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (pt) { 1085ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark *pt = SkEvalQuadAt(src, t); 109b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 110b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (tangent) { 11145398dff710c6cdadbc3c686faa7bf692febd222caryclark *tangent = SkEvalQuadTangentAt(src, t); 112b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 1138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11565cb2cd2f7ad4146f055810b8bd77bff03a4e76ereedSkPoint SkEvalQuadAt(const SkPoint src[3], SkScalar t) { 1165ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark return to_point(SkQuadCoeff(src).eval(t)); 1178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11940b7dd57ef1f4e91af72512d8ca57459b99d71bdreedSkVector SkEvalQuadTangentAt(const SkPoint src[3], SkScalar t) { 12045398dff710c6cdadbc3c686faa7bf692febd222caryclark // The derivative equation is 2(b - a +(a - 2b +c)t). This returns a 12145398dff710c6cdadbc3c686faa7bf692febd222caryclark // zero tangent vector when t is 0 or 1, and the control point is equal 12245398dff710c6cdadbc3c686faa7bf692febd222caryclark // to the end point. In this case, use the quad end points to compute the tangent. 12345398dff710c6cdadbc3c686faa7bf692febd222caryclark if ((t == 0 && src[0] == src[1]) || (t == 1 && src[1] == src[2])) { 12445398dff710c6cdadbc3c686faa7bf692febd222caryclark return src[2] - src[0]; 12545398dff710c6cdadbc3c686faa7bf692febd222caryclark } 12640b7dd57ef1f4e91af72512d8ca57459b99d71bdreed SkASSERT(src); 12740b7dd57ef1f4e91af72512d8ca57459b99d71bdreed SkASSERT(t >= 0 && t <= SK_Scalar1); 12840b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 129b640203cd5733aaf110277e28e22007c5b541565reed Sk2s P0 = from_point(src[0]); 130b640203cd5733aaf110277e28e22007c5b541565reed Sk2s P1 = from_point(src[1]); 131b640203cd5733aaf110277e28e22007c5b541565reed Sk2s P2 = from_point(src[2]); 13240b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 133b640203cd5733aaf110277e28e22007c5b541565reed Sk2s B = P1 - P0; 134b640203cd5733aaf110277e28e22007c5b541565reed Sk2s A = P2 - P1 - B; 135b640203cd5733aaf110277e28e22007c5b541565reed Sk2s T = A * Sk2s(t) + B; 13640b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 137b640203cd5733aaf110277e28e22007c5b541565reed return to_vector(T + T); 13840b7dd57ef1f4e91af72512d8ca57459b99d71bdreed} 13940b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 14040b7dd57ef1f4e91af72512d8ca57459b99d71bdreedstatic inline Sk2s interp(const Sk2s& v0, const Sk2s& v1, const Sk2s& t) { 14140b7dd57ef1f4e91af72512d8ca57459b99d71bdreed return v0 + (v1 - v0) * t; 14240b7dd57ef1f4e91af72512d8ca57459b99d71bdreed} 14340b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 144c08330f1601aeca7f10aeb2194118decbfbf83e1reedvoid SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t) { 14540b7dd57ef1f4e91af72512d8ca57459b99d71bdreed SkASSERT(t > 0 && t < SK_Scalar1); 14640b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 147b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p0 = from_point(src[0]); 148b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p1 = from_point(src[1]); 149b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p2 = from_point(src[2]); 150ce6acc91085c4b6d87d4bac84e66193908e648f9reed Sk2s tt(t); 151c9adb05b64fa0bfadf9d1a782afcda470da68c9emtklein 15240b7dd57ef1f4e91af72512d8ca57459b99d71bdreed Sk2s p01 = interp(p0, p1, tt); 15340b7dd57ef1f4e91af72512d8ca57459b99d71bdreed Sk2s p12 = interp(p1, p2, tt); 15440b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 155b640203cd5733aaf110277e28e22007c5b541565reed dst[0] = to_point(p0); 156b640203cd5733aaf110277e28e22007c5b541565reed dst[1] = to_point(p01); 157b640203cd5733aaf110277e28e22007c5b541565reed dst[2] = to_point(interp(p01, p12, tt)); 158b640203cd5733aaf110277e28e22007c5b541565reed dst[3] = to_point(p12); 159b640203cd5733aaf110277e28e22007c5b541565reed dst[4] = to_point(p2); 16040b7dd57ef1f4e91af72512d8ca57459b99d71bdreed} 16140b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 162b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]) { 163b6474dd1a530a543ae799c3822e8bc60180761c0caryclark SkChopQuadAt(src, dst, 0.5f); 1648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Quad'(t) = At + B, where 1678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = 2(a - 2b + c) 1688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = 2(b - a) 1698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Solve for t, only if it fits between 0 < t < 1 1708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 171b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValue[1]) { 1728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /* At + B == 0 1738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com t = -B / A 1748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 1758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return valid_unit_divide(a - b, a - b - b + c, tValue); 1768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 178b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic inline void flatten_double_quad_extrema(SkScalar coords[14]) { 1798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coords[2] = coords[6] = coords[4]; 1808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Returns 0 for 1 quad, and 1 for two quads, either way the answer is 18377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com stored in dst[]. Guarantees that the 1/2 quads will be monotonic. 18477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com */ 185b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]) { 1868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(dst); 188fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 1898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar a = src[0].fY; 1908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar b = src[1].fY; 1918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar c = src[2].fY; 192fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 193b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_not_monotonic(a, b, c)) { 1948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar tValue; 195b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (valid_unit_divide(a - b, a - b - b + c, &tValue)) { 1968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAt(src, dst, tValue); 1978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com flatten_double_quad_extrema(&dst[0].fY); 1988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1; 1998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // if we get here, we need to force dst to be monotonic, even though 2018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we couldn't compute a unit_divide value (probably underflow). 2028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; 2038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0].set(src[0].fX, a); 2058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[1].set(src[1].fX, b); 2068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[2].set(src[2].fX, c); 2078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 2088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 21077f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com/* Returns 0 for 1 quad, and 1 for two quads, either way the answer is 21177f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com stored in dst[]. Guarantees that the 1/2 quads will be monotonic. 21277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com */ 213b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]) { 21477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkASSERT(src); 21577f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkASSERT(dst); 216fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 21777f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar a = src[0].fX; 21877f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar b = src[1].fX; 21977f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar c = src[2].fX; 220fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 22177f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com if (is_not_monotonic(a, b, c)) { 22277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkScalar tValue; 22377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com if (valid_unit_divide(a - b, a - b - b + c, &tValue)) { 22477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com SkChopQuadAt(src, dst, tValue); 22577f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com flatten_double_quad_extrema(&dst[0].fX); 22677f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com return 1; 22777f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com } 22877f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com // if we get here, we need to force dst to be monotonic, even though 22977f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com // we couldn't compute a unit_divide value (probably underflow). 23077f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; 23177f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com } 23277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com dst[0].set(a, src[0].fY); 23377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com dst[1].set(b, src[1].fY); 23477f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com dst[2].set(c, src[2].fY); 23577f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com return 0; 23677f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com} 23777f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.com 2388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// F(t) = a (1 - t) ^ 2 + 2 b t (1 - t) + c t ^ 2 2398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// F'(t) = 2 (b - a) + 2 (a - 2b + c) t 2408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// F''(t) = 2 (a - 2b + c) 2418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 2428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// A = 2 (b - a) 2438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// B = 2 (a - 2b + c) 2448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 2458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// Maximum curvature for a quadratic means solving 2468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// Fx' Fx'' + Fy' Fy'' = 0 2478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 2488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// t = - (Ax Bx + Ay By) / (Bx ^ 2 + By ^ 2) 2498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 250b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgSkScalar SkFindQuadMaxCurvature(const SkPoint src[3]) { 2518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ax = src[1].fX - src[0].fX; 2528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ay = src[1].fY - src[0].fY; 2538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Bx = src[0].fX - src[1].fX - src[1].fX + src[2].fX; 2548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar By = src[0].fY - src[1].fY - src[1].fY + src[2].fY; 2558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t = 0; // 0 means don't chop 2568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (void)valid_unit_divide(-(Ax * Bx + Ay * By), Bx * Bx + By * By, &t); 2585383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com return t; 2595383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com} 2608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 261b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]) { 2625383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com SkScalar t = SkFindQuadMaxCurvature(src); 2635383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com if (t == 0) { 2648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 3 * sizeof(SkPoint)); 2658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1; 2665383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com } else { 2678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopQuadAt(src, dst, t); 2688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 2; 2698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2726fc321a18acc8c6437735007240eefe7054e83b0reed@google.comvoid SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]) { 273daee7eadd1b704078217e9a0f5ad218fcaeae099reed Sk2s scale(SkDoubleToScalar(2.0 / 3.0)); 274daee7eadd1b704078217e9a0f5ad218fcaeae099reed Sk2s s0 = from_point(src[0]); 275daee7eadd1b704078217e9a0f5ad218fcaeae099reed Sk2s s1 = from_point(src[1]); 276daee7eadd1b704078217e9a0f5ad218fcaeae099reed Sk2s s2 = from_point(src[2]); 277daee7eadd1b704078217e9a0f5ad218fcaeae099reed 2786fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[0] = src[0]; 279daee7eadd1b704078217e9a0f5ad218fcaeae099reed dst[1] = to_point(s0 + (s1 - s0) * scale); 280daee7eadd1b704078217e9a0f5ad218fcaeae099reed dst[2] = to_point(s2 + (s1 - s2) * scale); 2816fc321a18acc8c6437735007240eefe7054e83b0reed@google.com dst[3] = src[2]; 282945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com} 283945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 284b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org////////////////////////////////////////////////////////////////////////////// 285b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org///// CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS ///// 286b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org////////////////////////////////////////////////////////////////////////////// 2878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2885ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclarkstatic SkVector eval_cubic_derivative(const SkPoint src[4], SkScalar t) { 2895ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark SkQuadCoeff coeff; 2905ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark Sk2s P0 = from_point(src[0]); 2915ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark Sk2s P1 = from_point(src[1]); 2925ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark Sk2s P2 = from_point(src[2]); 2935ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark Sk2s P3 = from_point(src[3]); 2948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2955ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark coeff.fA = P3 + Sk2s(3) * (P1 - P2) - P0; 2965ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark coeff.fB = times_2(P2 - times_2(P1) + P0); 2975ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark coeff.fC = P1 - P0; 2985ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark return to_vector(coeff.eval(t)); 2998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3015ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclarkstatic SkVector eval_cubic_2ndDerivative(const SkPoint src[4], SkScalar t) { 3025ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark Sk2s P0 = from_point(src[0]); 3035ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark Sk2s P1 = from_point(src[1]); 3045ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark Sk2s P2 = from_point(src[2]); 3055ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark Sk2s P3 = from_point(src[3]); 3065ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark Sk2s A = P3 + Sk2s(3) * (P1 - P2) - P0; 3075ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark Sk2s B = P2 - times_2(P1) + P0; 3088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3095ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark return to_vector(A * Sk2s(t) + B); 3108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 312b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* loc, 313b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkVector* tangent, SkVector* curvature) { 3148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src); 3158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t >= 0 && t <= SK_Scalar1); 3168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 317b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (loc) { 3185ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark *loc = to_point(SkCubicCoeff(src).eval(t)); 319b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 320b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (tangent) { 32145398dff710c6cdadbc3c686faa7bf692febd222caryclark // The derivative equation returns a zero tangent vector when t is 0 or 1, and the 32245398dff710c6cdadbc3c686faa7bf692febd222caryclark // adjacent control point is equal to the end point. In this case, use the 32345398dff710c6cdadbc3c686faa7bf692febd222caryclark // next control point or the end points to compute the tangent. 32445398dff710c6cdadbc3c686faa7bf692febd222caryclark if ((t == 0 && src[0] == src[1]) || (t == 1 && src[2] == src[3])) { 32545398dff710c6cdadbc3c686faa7bf692febd222caryclark if (t == 0) { 32645398dff710c6cdadbc3c686faa7bf692febd222caryclark *tangent = src[2] - src[0]; 32745398dff710c6cdadbc3c686faa7bf692febd222caryclark } else { 32845398dff710c6cdadbc3c686faa7bf692febd222caryclark *tangent = src[3] - src[1]; 32945398dff710c6cdadbc3c686faa7bf692febd222caryclark } 33045398dff710c6cdadbc3c686faa7bf692febd222caryclark if (!tangent->fX && !tangent->fY) { 33145398dff710c6cdadbc3c686faa7bf692febd222caryclark *tangent = src[3] - src[0]; 33245398dff710c6cdadbc3c686faa7bf692febd222caryclark } 33345398dff710c6cdadbc3c686faa7bf692febd222caryclark } else { 3345ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark *tangent = eval_cubic_derivative(src, t); 33545398dff710c6cdadbc3c686faa7bf692febd222caryclark } 336b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 337b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (curvature) { 3385ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark *curvature = eval_cubic_2ndDerivative(src, t); 339b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 3408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Cubic'(t) = At^2 + Bt + C, where 3438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = 3(-a + 3(b - c) + d) 3448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = 6(a - 2b + c) 3458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = 3(b - a) 3468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Solve for t, keeping only those that fit betwee 0 < t < 1 3478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 348b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, 349b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar tValues[2]) { 3508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we divide A,B,C by 3 to simplify 3518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar A = d - a + 3*(b - c); 3528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar B = 2*(a - b - b + c); 3538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar C = b - a; 3548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkFindUnitQuadRoots(A, B, C, tValues); 3568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 358b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t) { 3598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(t > 0 && t < SK_Scalar1); 3608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3616b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed Sk2s p0 = from_point(src[0]); 3626b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed Sk2s p1 = from_point(src[1]); 3636b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed Sk2s p2 = from_point(src[2]); 3646b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed Sk2s p3 = from_point(src[3]); 3656b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed Sk2s tt(t); 3666b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed 3676b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed Sk2s ab = interp(p0, p1, tt); 3686b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed Sk2s bc = interp(p1, p2, tt); 3696b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed Sk2s cd = interp(p2, p3, tt); 3706b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed Sk2s abc = interp(ab, bc, tt); 3716b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed Sk2s bcd = interp(bc, cd, tt); 3726b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed Sk2s abcd = interp(abc, bcd, tt); 373c9adb05b64fa0bfadf9d1a782afcda470da68c9emtklein 3746b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed dst[0] = src[0]; 3756b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed dst[1] = to_point(ab); 3766b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed dst[2] = to_point(abc); 3776b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed dst[3] = to_point(abcd); 3786b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed dst[4] = to_point(bcd); 3796b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed dst[5] = to_point(cd); 3806b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed dst[6] = src[3]; 3816b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed} 3826b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed 383a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com/* http://code.google.com/p/skia/issues/detail?id=32 384fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 385a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com This test code would fail when we didn't check the return result of 386a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com valid_unit_divide in SkChopCubicAt(... tValues[], int roots). The reason is 387a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com that after the first chop, the parameters to valid_unit_divide are equal 388a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com (thanks to finite float precision and rounding in the subtracts). Thus 389a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com even though the 2nd tValue looks < 1.0, after we renormalize it, we end 390a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com up with 1.0, hence the need to check and just return the last cubic as 391a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com a degenerate clump of 4 points in the sampe place. 392a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com 393a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com static void test_cubic() { 394a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkPoint src[4] = { 395a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.25000, 523.03003 }, 396a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.23999, 522.96002 }, 397a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.21997, 522.89001 }, 398a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com { 556.21997, 522.82001 } 399a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com }; 400a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkPoint dst[10]; 401a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkScalar tval[] = { 0.33333334f, 0.99999994f }; 402a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SkChopCubicAt(src, dst, tval, 2); 403a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com } 404a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com */ 405a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com 406b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[], 407b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar tValues[], int roots) { 4088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 4098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 4108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = 0; i < roots - 1; i++) 4118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 4128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(is_unit_interval(tValues[i])); 4138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(is_unit_interval(tValues[i+1])); 4148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(tValues[i] < tValues[i+1]); 4158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 4188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 419b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (dst) { 420b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (roots == 0) { // nothing to chop 4218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 4*sizeof(SkPoint)); 422b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { 4238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t = tValues[0]; 4248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint tmp[4]; 4258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 426b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org for (int i = 0; i < roots; i++) { 4278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, t); 428b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (i == roots - 1) { 4298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 430b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 4318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst += 3; 433a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com // have src point to the remaining cubic (after the chop) 4348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(tmp, dst, 4 * sizeof(SkPoint)); 4358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com src = tmp; 436a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com 437a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com // watch out in case the renormalized t isn't in range 438a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com if (!valid_unit_divide(tValues[i+1] - tValues[i], 439a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com SK_Scalar1 - tValues[i], &t)) { 440a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com // if we can't, just create a degenerate cubic 441a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com dst[4] = dst[5] = dst[6] = src[3]; 442a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com break; 443a964028843ec3f69b3b2e556426ff881d1fcb4b2reed@android.com } 4448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 449b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgvoid SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]) { 450c08330f1601aeca7f10aeb2194118decbfbf83e1reed SkChopCubicAt(src, dst, 0.5f); 4518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 453b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic void flatten_double_cubic_extrema(SkScalar coords[14]) { 4548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coords[4] = coords[8] = coords[6]; 4558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that 458def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org the resulting beziers are monotonic in Y. This is called by the scan 459def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org converter. Depending on what is returned, dst[] is treated as follows: 4608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 dst[0..3] is the original cubic 4618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1 dst[0..3] and dst[3..6] are the two new cubics 4628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics 4638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com If dst == null, it is ignored and only the count is returned. 4648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 465bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.comint SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]) { 4668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar tValues[2]; 467bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com int roots = SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY, 468bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com src[3].fY, tValues); 469fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 4708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, tValues, roots); 471bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (dst && roots > 0) { 4728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we do some cleanup to ensure our Y extrema are flat 4738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com flatten_double_cubic_extrema(&dst[0].fY); 474bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (roots == 2) { 4758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com flatten_double_cubic_extrema(&dst[3].fY); 476bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 477bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 478bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com return roots; 479bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com} 480bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com 481bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.comint SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]) { 482bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com SkScalar tValues[2]; 483bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com int roots = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX, 484bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com src[3].fX, tValues); 485fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 486bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com SkChopCubicAt(src, dst, tValues, roots); 487bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (dst && roots > 0) { 488bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com // we do some cleanup to ensure our Y extrema are flat 489bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com flatten_double_cubic_extrema(&dst[0].fX); 490bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com if (roots == 2) { 491bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com flatten_double_cubic_extrema(&dst[3].fX); 492bb13586591bd412a0372aeb85d44159d2fa3f947reed@android.com } 4938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return roots; 4958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** http://www.faculty.idc.ac.il/arik/quality/appendixA.html 4988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Inflection means that curvature is zero. 5008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Curvature is [F' x F''] / [F'^3] 5018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com So we solve F'x X F''y - F'y X F''y == 0 5028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com After some canceling of the cubic term, we get 5038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = b - a 5048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = c - 2b + a 5058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = d - 3c + 3b - a 5068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (BxCy - ByCx)t^2 + (AxCy - AyCx)t + AxBy - AyBx == 0 5078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 508b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[]) { 5098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ax = src[1].fX - src[0].fX; 5108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Ay = src[1].fY - src[0].fY; 5118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Bx = src[2].fX - 2 * src[1].fX + src[0].fX; 5128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar By = src[2].fY - 2 * src[1].fY + src[0].fY; 5138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Cx = src[3].fX + 3 * (src[1].fX - src[2].fX) - src[0].fX; 5148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar Cy = src[3].fY + 3 * (src[1].fY - src[2].fY) - src[0].fY; 5158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 516def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org return SkFindUnitQuadRoots(Bx*Cy - By*Cx, 517def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org Ax*Cy - Ay*Cx, 518def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org Ax*By - Ay*Bx, 519def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org tValues); 5208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 522b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopCubicAtInflections(const SkPoint src[], SkPoint dst[10]) { 5238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar tValues[2]; 5248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = SkFindCubicInflections(src, tValues); 5258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 526b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (dst) { 527b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (count == 0) { 5288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 4 * sizeof(SkPoint)); 529b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { 5308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, tValues, count); 531b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 5328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count + 1; 5348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5368dd31cf69e24ff82865309781107dfab948b6a02caryclark// Assumes the third component of points is 1. 5378dd31cf69e24ff82865309781107dfab948b6a02caryclark// Calcs p0 . (p1 x p2) 538390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Daltonstatic double calc_dot_cross_cubic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { 539fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton const double xComp = (double) p0.fX * ((double) p1.fY - (double) p2.fY); 540fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton const double yComp = (double) p0.fY * ((double) p2.fX - (double) p1.fX); 541390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton const double wComp = (double) p1.fX * (double) p2.fY - (double) p1.fY * (double) p2.fX; 5428dd31cf69e24ff82865309781107dfab948b6a02caryclark return (xComp + yComp + wComp); 5438dd31cf69e24ff82865309781107dfab948b6a02caryclark} 5448dd31cf69e24ff82865309781107dfab948b6a02caryclark 5458dd31cf69e24ff82865309781107dfab948b6a02caryclark// Calc coefficients of I(s,t) where roots of I are inflection points of curve 5468dd31cf69e24ff82865309781107dfab948b6a02caryclark// I(s,t) = t*(3*d0*s^2 - 3*d1*s*t + d2*t^2) 5478dd31cf69e24ff82865309781107dfab948b6a02caryclark// d0 = a1 - 2*a2+3*a3 5488dd31cf69e24ff82865309781107dfab948b6a02caryclark// d1 = -a2 + 3*a3 5498dd31cf69e24ff82865309781107dfab948b6a02caryclark// d2 = 3*a3 5508dd31cf69e24ff82865309781107dfab948b6a02caryclark// a1 = p0 . (p3 x p2) 5518dd31cf69e24ff82865309781107dfab948b6a02caryclark// a2 = p1 . (p0 x p3) 5528dd31cf69e24ff82865309781107dfab948b6a02caryclark// a3 = p2 . (p1 x p0) 5538dd31cf69e24ff82865309781107dfab948b6a02caryclark// Places the values of d1, d2, d3 in array d passed in 554390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Daltonstatic void calc_cubic_inflection_func(const SkPoint p[4], double d[4]) { 555390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton const double a1 = calc_dot_cross_cubic(p[0], p[3], p[2]); 556390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton const double a2 = calc_dot_cross_cubic(p[1], p[0], p[3]); 557390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton const double a3 = calc_dot_cross_cubic(p[2], p[1], p[0]); 5588dd31cf69e24ff82865309781107dfab948b6a02caryclark 559390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton d[3] = 3 * a3; 5604343654bc4a93812cba168a665deef0de2ebcfddChris Dalton d[2] = d[3] - a2; 5614343654bc4a93812cba168a665deef0de2ebcfddChris Dalton d[1] = d[2] - a2 + a1; 5624343654bc4a93812cba168a665deef0de2ebcfddChris Dalton d[0] = 0; 5638dd31cf69e24ff82865309781107dfab948b6a02caryclark} 5648dd31cf69e24ff82865309781107dfab948b6a02caryclark 565390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Daltonstatic void normalize_t_s(double t[], double s[], int count) { 566febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton // Keep the exponents at or below zero to avoid overflow down the road. 567febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton for (int i = 0; i < count; ++i) { 568fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton SkASSERT(0 != s[i]); // classify_cubic should not call this method when s[i] is 0 or NaN. 5694dbdc677affd61309f1da173096089fdd20219b3Chris Dalton 570fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton uint64_t bitsT, bitsS; 571fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton memcpy(&bitsT, &t[i], sizeof(double)); 572fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton memcpy(&bitsS, &s[i], sizeof(double)); 5734dbdc677affd61309f1da173096089fdd20219b3Chris Dalton 574fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton uint64_t maxExponent = SkTMax(bitsT & 0x7ff0000000000000, bitsS & 0x7ff0000000000000); 5754dbdc677affd61309f1da173096089fdd20219b3Chris Dalton 576fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton#ifdef SK_DEBUG 577fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton uint64_t maxExponentValue = maxExponent >> 52; 578fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton // Ensure max(absT,absS) is NOT in denormalized form. SkClassifyCubic is given fp32 points, 579fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton // and does not call this method when s==0, so this should never happen. 580fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton SkASSERT(0 != maxExponentValue); 581fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton // Ensure 1/max(absT,absS) will NOT be in denormalized form. SkClassifyCubic is given fp32 582fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton // points, so this should never happen. 583fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton SkASSERT(2046 != maxExponentValue); 584fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton#endif 585fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton 586fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton // Pick a normalizer that scales the larger exponent to 1 (aka 1023 in biased form), but 587fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton // does NOT change the mantissa (thus preserving accuracy). 588fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton double normalizer; 589fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton uint64_t normalizerExponent = (uint64_t(1023 * 2) << 52) - maxExponent; 590fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton memcpy(&normalizer, &normalizerExponent, sizeof(double)); 5914dbdc677affd61309f1da173096089fdd20219b3Chris Dalton 592fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton t[i] *= normalizer; 593fc31be40cede4dfd5b06ecaffb551b06aea85693Chris Dalton s[i] *= normalizer; 594febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton } 595febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton} 596febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton 597390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Daltonstatic void sort_and_orient_t_s(double t[2], double s[2]) { 598febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton // This copysign/abs business orients the implicit function so positive values are always on the 599febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton // "left" side of the curve. 600390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton t[1] = -copysign(t[1], t[1] * s[1]); 601390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton s[1] = -fabs(s[1]); 602febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton 603febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton // Ensure t[0]/s[0] <= t[1]/s[1] (s[1] is negative from above). 604390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton if (copysign(s[1], s[0]) * t[0] > -fabs(s[0]) * t[1]) { 605febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton std::swap(t[0], t[1]); 606febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton std::swap(s[0], s[1]); 607febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton } 608febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton} 609febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton 610febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton// See "Resolution Independent Curve Rendering using Programmable Graphics Hardware" 611febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton// https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf 612febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton// discr(I) = 3*d2^2 - 4*d1*d3 613febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton// Classification: 614febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton// d1 != 0, discr(I) > 0 Serpentine 615febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton// d1 != 0, discr(I) < 0 Loop 616febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton// d1 != 0, discr(I) = 0 Cusp (with inflection at infinity) 617febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton// d1 = 0, d2 != 0 Cusp (with cusp at infinity) 618febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton// d1 = d2 = 0, d3 != 0 Quadratic 619febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton// d1 = d2 = d3 = 0 Line or Point 620390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Daltonstatic SkCubicType classify_cubic(const double d[4], double t[2], double s[2]) { 62191982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton if (0 == d[1]) { 62229011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton if (0 == d[2]) { 62329011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton if (t && s) { 62429011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton t[0] = t[1] = 1; 62529011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton s[0] = s[1] = 0; // infinity 62629011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton } 62729011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton return 0 == d[3] ? SkCubicType::kLineOrPoint : SkCubicType::kQuadratic; 62829011a2bda560a645e6ddbe162df0856fe259e7bChris Dalton } 62991982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton if (t && s) { 63091982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton t[0] = d[3]; 63191982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton s[0] = 3 * d[2]; 63291982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton normalize_t_s(t, s, 1); 63391982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton t[1] = 1; 63491982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton s[1] = 0; // infinity 635febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton } 63691982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton return SkCubicType::kCuspAtInfinity; 63791982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton } 63891982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton 63991982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton const double discr = 3 * d[2] * d[2] - 4 * d[1] * d[3]; 64091982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton if (discr > 0) { 64191982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton if (t && s) { 64291982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton const double q = 3 * d[2] + copysign(sqrt(3 * discr), d[2]); 64391982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton t[0] = q; 64491982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton s[0] = 6 * d[1]; 64591982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton t[1] = 2 * d[3]; 64691982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton s[1] = q; 64791982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton normalize_t_s(t, s, 2); 64891982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton sort_and_orient_t_s(t, s); 64991982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton } 65091982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton return SkCubicType::kSerpentine; 65191982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton } else if (discr < 0) { 65291982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton if (t && s) { 65391982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton const double q = d[2] + copysign(sqrt(-discr), d[2]); 65491982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton t[0] = q; 65591982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton s[0] = 2 * d[1]; 65691982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton t[1] = 2 * (d[2] * d[2] - d[3] * d[1]); 65791982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton s[1] = d[1] * q; 65891982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton normalize_t_s(t, s, 2); 65991982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton sort_and_orient_t_s(t, s); 66091982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton } 66191982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton return SkCubicType::kLoop; 662febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton } else { 66391982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton if (t && s) { 66491982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton t[0] = d[2]; 66591982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton s[0] = 2 * d[1]; 66691982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton normalize_t_s(t, s, 1); 66791982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton t[1] = t[0]; 66891982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton s[1] = s[0]; 66991982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton sort_and_orient_t_s(t, s); 670febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton } 67191982ee8d92a80193915d59760e2ba9ce6f46989Chris Dalton return SkCubicType::kLocalCusp; 672febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton } 673febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton} 674febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton 675390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris DaltonSkCubicType SkClassifyCubic(const SkPoint src[4], double t[2], double s[2], double d[4]) { 676390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton double localD[4]; 677390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton double* dd = d ? d : localD; 678febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton calc_cubic_inflection_func(src, dd); 679febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton return classify_cubic(dd, t, s); 6808dd31cf69e24ff82865309781107dfab948b6a02caryclark} 6818dd31cf69e24ff82865309781107dfab948b6a02caryclark 682b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgtemplate <typename T> void bubble_sort(T array[], int count) { 6838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = count - 1; i > 0; --i) 6848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int j = i; j > 0; --j) 6858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (array[j] < array[j-1]) 6868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 6878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T tmp(array[j]); 6888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com array[j] = array[j-1]; 6898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com array[j-1] = tmp; 6908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 6928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 693087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com/** 694087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com * Given an array and count, remove all pair-wise duplicates from the array, 695087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com * keeping the existing sorting, and return the new count 696087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com */ 697b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic int collaps_duplicates(SkScalar array[], int count) { 698087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (int n = count; n > 1; --n) { 699087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com if (array[0] == array[1]) { 700087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (int i = 1; i < n; ++i) { 701087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com array[i - 1] = array[i]; 702087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 703087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com count -= 1; 704087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } else { 705087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com array += 1; 706087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 707087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 708087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com return count; 709087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com} 710087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 711087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com#ifdef SK_DEBUG 712087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 713087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com#define TEST_COLLAPS_ENTRY(array) array, SK_ARRAY_COUNT(array) 714087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 715087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.comstatic void test_collaps_duplicates() { 716087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com static bool gOnce; 717087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com if (gOnce) { return; } 718087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com gOnce = true; 719b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src0[] = { 0 }; 720b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src1[] = { 0, 0 }; 721b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src2[] = { 0, 1 }; 722b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src3[] = { 0, 0, 0 }; 723b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src4[] = { 0, 0, 1 }; 724b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src5[] = { 0, 1, 1 }; 725b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar src6[] = { 0, 1, 2 }; 726087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com const struct { 727b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org const SkScalar* fData; 728087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int fCount; 729087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int fCollapsedCount; 730087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } data[] = { 731087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src0), 1 }, 732087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src1), 1 }, 733087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src2), 2 }, 734087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src3), 1 }, 735087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src4), 2 }, 736087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src5), 2 }, 737087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com { TEST_COLLAPS_ENTRY(src6), 3 }, 738087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com }; 739087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (size_t i = 0; i < SK_ARRAY_COUNT(data); ++i) { 740b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar dst[3]; 741087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com memcpy(dst, data[i].fData, data[i].fCount * sizeof(dst[0])); 742087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int count = collaps_duplicates(dst, data[i].fCount); 743087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkASSERT(data[i].fCollapsedCount == count); 744087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com for (int j = 1; j < count; ++j) { 745087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkASSERT(dst[j-1] < dst[j]); 746087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 747087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com } 748087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com} 749087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com#endif 750087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 7513c12840b234e614faf569e80f311a77ce65d9fe0reed@google.comstatic SkScalar SkScalarCubeRoot(SkScalar x) { 752b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org return SkScalarPow(x, 0.3333333f); 7533c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com} 7543c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com 7558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Solve coeff(t) == 0, returning the number of roots that 7568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com lie withing 0 < t < 1. 7578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3] 758fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 759087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com Eliminates repeated roots (so that all tValues are distinct, and are always 760087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com in increasing order. 7618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 762b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic int solve_cubic_poly(const SkScalar coeff[4], SkScalar tValues[3]) { 763b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (SkScalarNearlyZero(coeff[0])) { // we're just a quadratic 7648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues); 7658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 7668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7673c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar a, b, c, Q, R; 7688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 7708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(coeff[0] != 0); 7718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7723c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar inva = SkScalarInvert(coeff[0]); 7733c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com a = coeff[1] * inva; 7743c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com b = coeff[2] * inva; 7753c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com c = coeff[3] * inva; 7768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 7773c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com Q = (a*a - b*3) / 9; 7783c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com R = (2*a*a*a - 9*a*b + 27*c) / 54; 7798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7803c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar Q3 = Q * Q * Q; 7813c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar R2MinusQ3 = R * R - Q3; 7823c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar adiv3 = a / 3; 7838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar* roots = tValues; 7858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar r; 7868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 787b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (R2MinusQ3 < 0) { // we have 3 real roots 78893ca884879e3469b46d32c36deb7b46f2fff1c0ccaryclark // the divide/root can, due to finite precisions, be slightly outside of -1...1 78993ca884879e3469b46d32c36deb7b46f2fff1c0ccaryclark SkScalar theta = SkScalarACos(SkScalarPin(R / SkScalarSqrt(Q3), -1, 1)); 790b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar neg2RootQ = -2 * SkScalarSqrt(Q); 7918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 792b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org r = neg2RootQ * SkScalarCos(theta/3) - adiv3; 793b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_unit_interval(r)) { 7948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 795b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 796b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org r = neg2RootQ * SkScalarCos((theta + 2*SK_ScalarPI)/3) - adiv3; 797b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_unit_interval(r)) { 7988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 799b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 800b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org r = neg2RootQ * SkScalarCos((theta - 2*SK_ScalarPI)/3) - adiv3; 801b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_unit_interval(r)) { 8028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 803b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 804087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkDEBUGCODE(test_collaps_duplicates();) 805087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com 8068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // now sort the roots 807087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com int count = (int)(roots - tValues); 808087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com SkASSERT((unsigned)count <= 3); 809087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com bubble_sort(tValues, count); 810087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com count = collaps_duplicates(tValues, count); 811087d5aafb18b88dfc6c6a5dbf59160c8be914e62reed@google.com roots = tValues + count; // so we compute the proper count below 812b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { // we have 1 real root 8133c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar A = SkScalarAbs(R) + SkScalarSqrt(R2MinusQ3); 8143c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com A = SkScalarCubeRoot(A); 815b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (R > 0) { 8163c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com A = -A; 817b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 818b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (A != 0) { 8193c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com A += Q / A; 820b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 8213c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com r = A - adiv3; 822b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (is_unit_interval(r)) { 8238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *roots++ = r; 824b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 8258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 8268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (int)(roots - tValues); 8288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 8298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Looking for F' dot F'' == 0 831fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 8328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = b - a 8338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = c - 2b + a 8348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = d - 3c + 3b - a 8358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' = 3Ct^2 + 6Bt + 3A 8378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F'' = 6Ct + 6B 8388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 8408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 841b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgstatic void formulate_F1DotF2(const SkScalar src[], SkScalar coeff[4]) { 8428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar a = src[2] - src[0]; 8438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar b = src[4] - 2 * src[2] + src[0]; 8448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar c = src[6] + 3 * (src[2] - src[4]) - src[0]; 8458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8463c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeff[0] = c * c; 8473c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeff[1] = 3 * b * c; 8483c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeff[2] = 2 * b * b + c * a; 8493c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeff[3] = a * b; 8508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 8518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* Looking for F' dot F'' == 0 853fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 8548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com A = b - a 8558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com B = c - 2b + a 8568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com C = d - 3c + 3b - a 8578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' = 3Ct^2 + 6Bt + 3A 8598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F'' = 6Ct + 6B 8608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 8628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 863b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]) { 8643c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com SkScalar coeffX[4], coeffY[4]; 8653c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com int i; 8668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com formulate_F1DotF2(&src[0].fX, coeffX); 8688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com formulate_F1DotF2(&src[0].fY, coeffY); 8698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 870b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org for (i = 0; i < 4; i++) { 8713c12840b234e614faf569e80f311a77ce65d9fe0reed@google.com coeffX[i] += coeffY[i]; 872b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 8738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t[3]; 875b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org int count = solve_cubic_poly(coeffX, t); 8768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int maxCount = 0; 8778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // now remove extrema where the curvature is zero (mins) 8798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // !!!! need a test for this !!!! 880b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org for (i = 0; i < count; i++) { 8818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // if (not_min_curvature()) 882b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (t[i] > 0 && t[i] < SK_Scalar1) { 8838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tValues[maxCount++] = t[i]; 884b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 8858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 8868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return maxCount; 8878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 8888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 889b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.orgint SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], 890b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org SkScalar tValues[3]) { 8918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar t_storage[3]; 8928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 89396fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (tValues == nullptr) { 8948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tValues = t_storage; 895b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 8968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = SkFindCubicMaxCurvature(src, tValues); 8988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8995383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com if (dst) { 900b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org if (count == 0) { 9018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, 4 * sizeof(SkPoint)); 902b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } else { 9038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkChopCubicAt(src, dst, tValues, count); 904b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org } 9058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 9068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count + 1; 9078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 9088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 909dc3088570f945ed0ede84f0af0016eedc267dda3reed#include "../pathops/SkPathOpsCubic.h" 910dc3088570f945ed0ede84f0af0016eedc267dda3reed 911dc3088570f945ed0ede84f0af0016eedc267dda3reedtypedef int (SkDCubic::*InterceptProc)(double intercept, double roots[3]) const; 912dc3088570f945ed0ede84f0af0016eedc267dda3reed 913dc3088570f945ed0ede84f0af0016eedc267dda3reedstatic bool cubic_dchop_at_intercept(const SkPoint src[4], SkScalar intercept, SkPoint dst[7], 914dc3088570f945ed0ede84f0af0016eedc267dda3reed InterceptProc method) { 915dc3088570f945ed0ede84f0af0016eedc267dda3reed SkDCubic cubic; 916dc3088570f945ed0ede84f0af0016eedc267dda3reed double roots[3]; 917dc3088570f945ed0ede84f0af0016eedc267dda3reed int count = (cubic.set(src).*method)(intercept, roots); 918dc3088570f945ed0ede84f0af0016eedc267dda3reed if (count > 0) { 919dc3088570f945ed0ede84f0af0016eedc267dda3reed SkDCubicPair pair = cubic.chopAt(roots[0]); 920dc3088570f945ed0ede84f0af0016eedc267dda3reed for (int i = 0; i < 7; ++i) { 921dc3088570f945ed0ede84f0af0016eedc267dda3reed dst[i] = pair.pts[i].asSkPoint(); 922dc3088570f945ed0ede84f0af0016eedc267dda3reed } 923dc3088570f945ed0ede84f0af0016eedc267dda3reed return true; 924dc3088570f945ed0ede84f0af0016eedc267dda3reed } 925dc3088570f945ed0ede84f0af0016eedc267dda3reed return false; 926dc3088570f945ed0ede84f0af0016eedc267dda3reed} 927dc3088570f945ed0ede84f0af0016eedc267dda3reed 928dc3088570f945ed0ede84f0af0016eedc267dda3reedbool SkChopMonoCubicAtY(SkPoint src[4], SkScalar y, SkPoint dst[7]) { 929dc3088570f945ed0ede84f0af0016eedc267dda3reed return cubic_dchop_at_intercept(src, y, dst, &SkDCubic::horizontalIntersect); 930dc3088570f945ed0ede84f0af0016eedc267dda3reed} 931dc3088570f945ed0ede84f0af0016eedc267dda3reed 932dc3088570f945ed0ede84f0af0016eedc267dda3reedbool SkChopMonoCubicAtX(SkPoint src[4], SkScalar x, SkPoint dst[7]) { 933dc3088570f945ed0ede84f0af0016eedc267dda3reed return cubic_dchop_at_intercept(src, x, dst, &SkDCubic::verticalIntersect); 934dc3088570f945ed0ede84f0af0016eedc267dda3reed} 935dc3088570f945ed0ede84f0af0016eedc267dda3reed 936b39d5617f60e8c26f76011cfcd984d7ad42d9fa9commit-bot@chromium.org/////////////////////////////////////////////////////////////////////////////// 937def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// 938def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// NURB representation for conics. Helpful explanations at: 939def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// 940def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// http://citeseerx.ist.psu.edu/viewdoc/ 941def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// download?doi=10.1.1.44.5740&rep=rep1&type=ps 942def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// and 943def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/NURBS/RB-conics.html 944def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org// 94517a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// F = (A (1 - t)^2 + C t^2 + 2 B (1 - t) t w) 94617a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// ------------------------------------------ 94717a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// ((1 - t)^2 + t^2 + 2 (1 - t) t w) 94817a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// 94917a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// = {t^2 (P0 + P2 - 2 P1 w), t (-2 P0 + 2 P1 w), P0} 95017a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// ------------------------------------------------ 95117a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// {t^2 (2 - 2 w), t (-2 + 2 w), 1} 95217a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// 95317a2c919d095797c364d407a5dbdb4d60533b953reed@google.com 9540c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org// F' = 2 (C t (1 + t (-1 + w)) - A (-1 + t) (t (-1 + w) - w) + B (1 - 2 t) w) 9550c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org// 9566862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// t^2 : (2 P0 - 2 P2 - 2 P0 w + 2 P2 w) 9576862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// t^1 : (-2 P0 + 2 P2 + 4 P0 w - 4 P1 w) 9586862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// t^0 : -2 P0 w + 2 P1 w 9596862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// 9606862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// We disregard magnitude, so we can freely ignore the denominator of F', and 9616862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// divide the numerator by 2 9620c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org// 96317a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// coeff[0] for t^2 9646862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// coeff[1] for t^1 9656862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org// coeff[2] for t^0 96617a2c919d095797c364d407a5dbdb4d60533b953reed@google.com// 967def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.orgstatic void conic_deriv_coeff(const SkScalar src[], 968def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org SkScalar w, 969def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org SkScalar coeff[3]) { 9706862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org const SkScalar P20 = src[4] - src[0]; 9716862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org const SkScalar P10 = src[2] - src[0]; 9726862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org const SkScalar wP10 = w * P10; 9736862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org coeff[0] = w * P20 - P20; 9746862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org coeff[1] = P20 - 2 * wP10; 9756862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org coeff[2] = wP10; 9766862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org} 9776862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org 9786862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.orgstatic bool conic_find_extrema(const SkScalar src[], SkScalar w, SkScalar* t) { 9790c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar coeff[3]; 9806862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org conic_deriv_coeff(src, w, coeff); 9810c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 9820c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar tValues[2]; 9830c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org int roots = SkFindUnitQuadRoots(coeff[0], coeff[1], coeff[2], tValues); 9840c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkASSERT(0 == roots || 1 == roots); 98545fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 9860c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org if (1 == roots) { 9870c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org *t = tValues[0]; 9880c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return true; 9890c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org } 9900c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return false; 99117a2c919d095797c364d407a5dbdb4d60533b953reed@google.com} 99217a2c919d095797c364d407a5dbdb4d60533b953reed@google.com 993d50d87a185d26a38d7100bbbb119be17947aa5e4commit-bot@chromium.org// We only interpolate one dimension at a time (the first, at +0, +3, +6). 994d50d87a185d26a38d7100bbbb119be17947aa5e4commit-bot@chromium.orgstatic void p3d_interp(const SkScalar src[7], SkScalar dst[7], SkScalar t) { 9950d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkScalar ab = SkScalarInterp(src[0], src[3], t); 9960d099557feb99707c8f601746f46f5a295eb33b7reed@google.com SkScalar bc = SkScalarInterp(src[3], src[6], t); 9970d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[0] = ab; 9980d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[3] = SkScalarInterp(ab, bc, t); 9990d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[6] = bc; 10000d099557feb99707c8f601746f46f5a295eb33b7reed@google.com} 10010d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 1002e4442cb0b537720ab32106b3b5353dbb78f11b26Cary Clarkstatic void ratquad_mapTo3D(const SkPoint src[3], SkScalar w, SkPoint3 dst[3]) { 10030d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[0].set(src[0].fX * 1, src[0].fY * 1, 1); 10040d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[1].set(src[1].fX * w, src[1].fY * w, w); 10050d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[2].set(src[2].fX * 1, src[2].fY * 1, 1); 10060d099557feb99707c8f601746f46f5a295eb33b7reed@google.com} 10070d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 1008e4442cb0b537720ab32106b3b5353dbb78f11b26Cary Clarkstatic SkPoint project_down(const SkPoint3& src) { 1009e4442cb0b537720ab32106b3b5353dbb78f11b26Cary Clark return {src.fX / src.fZ, src.fY / src.fZ}; 1010e4442cb0b537720ab32106b3b5353dbb78f11b26Cary Clark} 1011e4442cb0b537720ab32106b3b5353dbb78f11b26Cary Clark 1012414c4295f951d43068666b6294df15b2fd2ba85ccaryclark// return false if infinity or NaN is generated; caller must check 1013414c4295f951d43068666b6294df15b2fd2ba85ccaryclarkbool SkConic::chopAt(SkScalar t, SkConic dst[2]) const { 1014e4442cb0b537720ab32106b3b5353dbb78f11b26Cary Clark SkPoint3 tmp[3], tmp2[3]; 10150d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 10160d099557feb99707c8f601746f46f5a295eb33b7reed@google.com ratquad_mapTo3D(fPts, fW, tmp); 10174bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 10180d099557feb99707c8f601746f46f5a295eb33b7reed@google.com p3d_interp(&tmp[0].fX, &tmp2[0].fX, t); 10190d099557feb99707c8f601746f46f5a295eb33b7reed@google.com p3d_interp(&tmp[0].fY, &tmp2[0].fY, t); 10200d099557feb99707c8f601746f46f5a295eb33b7reed@google.com p3d_interp(&tmp[0].fZ, &tmp2[0].fZ, t); 10214bb50b22fce5c4031549976cf7b04d63cc22e624skia.committer@gmail.com 10220d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[0].fPts[0] = fPts[0]; 1023e4442cb0b537720ab32106b3b5353dbb78f11b26Cary Clark dst[0].fPts[1] = project_down(tmp2[0]); 1024e4442cb0b537720ab32106b3b5353dbb78f11b26Cary Clark dst[0].fPts[2] = project_down(tmp2[1]); dst[1].fPts[0] = dst[0].fPts[2]; 1025e4442cb0b537720ab32106b3b5353dbb78f11b26Cary Clark dst[1].fPts[1] = project_down(tmp2[2]); 10260d099557feb99707c8f601746f46f5a295eb33b7reed@google.com dst[1].fPts[2] = fPts[2]; 10270d099557feb99707c8f601746f46f5a295eb33b7reed@google.com 10284af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // to put in "standard form", where w0 and w2 are both 1, we compute the 10294af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // new w1 as sqrt(w1*w1/w0*w2) 10304af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // or 10314af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // w1 /= sqrt(w0*w2) 10324af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // 1033def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org // However, in our case, we know that for dst[0]: 1034def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org // w0 == 1, and for dst[1], w2 == 1 10354af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org // 10364af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org SkScalar root = SkScalarSqrt(tmp2[1].fZ); 10374af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org dst[0].fW = tmp2[0].fZ / root; 10384af6280aa366a02540f34c48f89ea73ce3d27974mike@reedtribe.org dst[1].fW = tmp2[2].fZ / root; 1039414c4295f951d43068666b6294df15b2fd2ba85ccaryclark SkASSERT(sizeof(dst[0]) == sizeof(SkScalar) * 7); 1040414c4295f951d43068666b6294df15b2fd2ba85ccaryclark SkASSERT(0 == offsetof(SkConic, fPts[0].fX)); 1041414c4295f951d43068666b6294df15b2fd2ba85ccaryclark return SkScalarsAreFinite(&dst[0].fPts[0].fX, 7 * 2); 1042c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com} 10438d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org 1044b6474dd1a530a543ae799c3822e8bc60180761c0caryclarkvoid SkConic::chopAt(SkScalar t1, SkScalar t2, SkConic* dst) const { 1045b6474dd1a530a543ae799c3822e8bc60180761c0caryclark if (0 == t1 || 1 == t2) { 1046b6474dd1a530a543ae799c3822e8bc60180761c0caryclark if (0 == t1 && 1 == t2) { 1047b6474dd1a530a543ae799c3822e8bc60180761c0caryclark *dst = *this; 1048414c4295f951d43068666b6294df15b2fd2ba85ccaryclark return; 1049b6474dd1a530a543ae799c3822e8bc60180761c0caryclark } else { 1050b6474dd1a530a543ae799c3822e8bc60180761c0caryclark SkConic pair[2]; 1051414c4295f951d43068666b6294df15b2fd2ba85ccaryclark if (this->chopAt(t1 ? t1 : t2, pair)) { 1052414c4295f951d43068666b6294df15b2fd2ba85ccaryclark *dst = pair[SkToBool(t1)]; 1053414c4295f951d43068666b6294df15b2fd2ba85ccaryclark return; 1054414c4295f951d43068666b6294df15b2fd2ba85ccaryclark } 1055b6474dd1a530a543ae799c3822e8bc60180761c0caryclark } 1056b6474dd1a530a543ae799c3822e8bc60180761c0caryclark } 1057b6474dd1a530a543ae799c3822e8bc60180761c0caryclark SkConicCoeff coeff(*this); 1058b6474dd1a530a543ae799c3822e8bc60180761c0caryclark Sk2s tt1(t1); 1059b6474dd1a530a543ae799c3822e8bc60180761c0caryclark Sk2s aXY = coeff.fNumer.eval(tt1); 1060b6474dd1a530a543ae799c3822e8bc60180761c0caryclark Sk2s aZZ = coeff.fDenom.eval(tt1); 1061b6474dd1a530a543ae799c3822e8bc60180761c0caryclark Sk2s midTT((t1 + t2) / 2); 1062b6474dd1a530a543ae799c3822e8bc60180761c0caryclark Sk2s dXY = coeff.fNumer.eval(midTT); 1063b6474dd1a530a543ae799c3822e8bc60180761c0caryclark Sk2s dZZ = coeff.fDenom.eval(midTT); 1064b6474dd1a530a543ae799c3822e8bc60180761c0caryclark Sk2s tt2(t2); 1065b6474dd1a530a543ae799c3822e8bc60180761c0caryclark Sk2s cXY = coeff.fNumer.eval(tt2); 1066b6474dd1a530a543ae799c3822e8bc60180761c0caryclark Sk2s cZZ = coeff.fDenom.eval(tt2); 1067b6474dd1a530a543ae799c3822e8bc60180761c0caryclark Sk2s bXY = times_2(dXY) - (aXY + cXY) * Sk2s(0.5f); 1068b6474dd1a530a543ae799c3822e8bc60180761c0caryclark Sk2s bZZ = times_2(dZZ) - (aZZ + cZZ) * Sk2s(0.5f); 1069b6474dd1a530a543ae799c3822e8bc60180761c0caryclark dst->fPts[0] = to_point(aXY / aZZ); 1070b6474dd1a530a543ae799c3822e8bc60180761c0caryclark dst->fPts[1] = to_point(bXY / bZZ); 1071b6474dd1a530a543ae799c3822e8bc60180761c0caryclark dst->fPts[2] = to_point(cXY / cZZ); 1072b6474dd1a530a543ae799c3822e8bc60180761c0caryclark Sk2s ww = bZZ / (aZZ * cZZ).sqrt(); 10737c249e531900929c2fe2cdde76619fa6d2538c49mtklein dst->fW = ww[0]; 1074b640203cd5733aaf110277e28e22007c5b541565reed} 1075b640203cd5733aaf110277e28e22007c5b541565reed 1076b640203cd5733aaf110277e28e22007c5b541565reedSkPoint SkConic::evalAt(SkScalar t) const { 10775ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark return to_point(SkConicCoeff(*this).eval(t)); 1078b640203cd5733aaf110277e28e22007c5b541565reed} 1079b640203cd5733aaf110277e28e22007c5b541565reed 1080b640203cd5733aaf110277e28e22007c5b541565reedSkVector SkConic::evalTangentAt(SkScalar t) const { 108145398dff710c6cdadbc3c686faa7bf692febd222caryclark // The derivative equation returns a zero tangent vector when t is 0 or 1, 108245398dff710c6cdadbc3c686faa7bf692febd222caryclark // and the control point is equal to the end point. 108345398dff710c6cdadbc3c686faa7bf692febd222caryclark // In this case, use the conic endpoints to compute the tangent. 108445398dff710c6cdadbc3c686faa7bf692febd222caryclark if ((t == 0 && fPts[0] == fPts[1]) || (t == 1 && fPts[1] == fPts[2])) { 108545398dff710c6cdadbc3c686faa7bf692febd222caryclark return fPts[2] - fPts[0]; 108645398dff710c6cdadbc3c686faa7bf692febd222caryclark } 1087b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p0 = from_point(fPts[0]); 1088b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p1 = from_point(fPts[1]); 1089b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p2 = from_point(fPts[2]); 1090ce6acc91085c4b6d87d4bac84e66193908e648f9reed Sk2s ww(fW); 1091b640203cd5733aaf110277e28e22007c5b541565reed 1092b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p20 = p2 - p0; 1093b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p10 = p1 - p0; 1094b640203cd5733aaf110277e28e22007c5b541565reed 1095b640203cd5733aaf110277e28e22007c5b541565reed Sk2s C = ww * p10; 1096b640203cd5733aaf110277e28e22007c5b541565reed Sk2s A = ww * p20 - p20; 1097b640203cd5733aaf110277e28e22007c5b541565reed Sk2s B = p20 - C - C; 1098b640203cd5733aaf110277e28e22007c5b541565reed 10995ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark return to_vector(SkQuadCoeff(A, B, C).eval(t)); 1100b640203cd5733aaf110277e28e22007c5b541565reed} 1101b640203cd5733aaf110277e28e22007c5b541565reed 1102f0b6c553aeec0da32193d354a034bd387bdbf19areedvoid SkConic::evalAt(SkScalar t, SkPoint* pt, SkVector* tangent) const { 1103f0b6c553aeec0da32193d354a034bd387bdbf19areed SkASSERT(t >= 0 && t <= SK_Scalar1); 1104507ef6d68115ae9e6d884bb36436a1463523d893mtklein 1105f0b6c553aeec0da32193d354a034bd387bdbf19areed if (pt) { 1106f0b6c553aeec0da32193d354a034bd387bdbf19areed *pt = this->evalAt(t); 1107f0b6c553aeec0da32193d354a034bd387bdbf19areed } 1108f0b6c553aeec0da32193d354a034bd387bdbf19areed if (tangent) { 1109f0b6c553aeec0da32193d354a034bd387bdbf19areed *tangent = this->evalTangentAt(t); 1110f0b6c553aeec0da32193d354a034bd387bdbf19areed } 1111f0b6c553aeec0da32193d354a034bd387bdbf19areed} 1112f0b6c553aeec0da32193d354a034bd387bdbf19areed 11133df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.orgstatic SkScalar subdivide_w_value(SkScalar w) { 11146862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org return SkScalarSqrt(SK_ScalarHalf + w * SK_ScalarHalf); 11153df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 11163df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 111755011038816a3fc7f0c0a39d482fb85347cc2e78reedvoid SkConic::chop(SkConic * SK_RESTRICT dst) const { 111855011038816a3fc7f0c0a39d482fb85347cc2e78reed Sk2s scale = Sk2s(SkScalarInvert(SK_Scalar1 + fW)); 1119b640203cd5733aaf110277e28e22007c5b541565reed SkScalar newW = subdivide_w_value(fW); 1120b640203cd5733aaf110277e28e22007c5b541565reed 1121b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p0 = from_point(fPts[0]); 1122b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p1 = from_point(fPts[1]); 1123b640203cd5733aaf110277e28e22007c5b541565reed Sk2s p2 = from_point(fPts[2]); 1124ce6acc91085c4b6d87d4bac84e66193908e648f9reed Sk2s ww(fW); 1125b640203cd5733aaf110277e28e22007c5b541565reed 1126b640203cd5733aaf110277e28e22007c5b541565reed Sk2s wp1 = ww * p1; 11275ba2b9612ae4bc3a244bf45f1ec55c3a5a41e181caryclark Sk2s m = (p0 + times_2(wp1) + p2) * scale * Sk2s(0.5f); 1128a0e30b1e40459629e48c5e59f7385b51067e31d6Cary Clark SkPoint mPt = to_point(m); 1129a0e30b1e40459629e48c5e59f7385b51067e31d6Cary Clark if (!mPt.isFinite()) { 1130a0e30b1e40459629e48c5e59f7385b51067e31d6Cary Clark double w_d = fW; 1131a0e30b1e40459629e48c5e59f7385b51067e31d6Cary Clark double w_2 = w_d * 2; 1132a0e30b1e40459629e48c5e59f7385b51067e31d6Cary Clark double scale_half = 1 / (1 + w_d) * 0.5; 1133a0e30b1e40459629e48c5e59f7385b51067e31d6Cary Clark mPt.fX = SkDoubleToScalar((fPts[0].fX + w_2 * fPts[1].fX + fPts[2].fX) * scale_half); 1134a0e30b1e40459629e48c5e59f7385b51067e31d6Cary Clark mPt.fY = SkDoubleToScalar((fPts[0].fY + w_2 * fPts[1].fY + fPts[2].fY) * scale_half); 1135a0e30b1e40459629e48c5e59f7385b51067e31d6Cary Clark } 1136b640203cd5733aaf110277e28e22007c5b541565reed dst[0].fPts[0] = fPts[0]; 1137b640203cd5733aaf110277e28e22007c5b541565reed dst[0].fPts[1] = to_point((p0 + wp1) * scale); 1138a0e30b1e40459629e48c5e59f7385b51067e31d6Cary Clark dst[0].fPts[2] = dst[1].fPts[0] = mPt; 1139b640203cd5733aaf110277e28e22007c5b541565reed dst[1].fPts[1] = to_point((wp1 + p2) * scale); 1140b640203cd5733aaf110277e28e22007c5b541565reed dst[1].fPts[2] = fPts[2]; 1141b640203cd5733aaf110277e28e22007c5b541565reed 1142b640203cd5733aaf110277e28e22007c5b541565reed dst[0].fW = dst[1].fW = newW; 1143b640203cd5733aaf110277e28e22007c5b541565reed} 1144b640203cd5733aaf110277e28e22007c5b541565reed 114597514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org/* 114697514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org * "High order approximation of conic sections by quadratic splines" 114797514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org * by Michael Floater, 1993 114897514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org */ 1149af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org#define AS_QUAD_ERROR_SETUP \ 1150af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar a = fW - 1; \ 1151af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar k = a / (4 * (2 + a)); \ 1152af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar x = k * (fPts[0].fX - 2 * fPts[1].fX + fPts[2].fX); \ 1153af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkScalar y = k * (fPts[0].fY - 2 * fPts[1].fY + fPts[2].fY); 1154af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 1155af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.orgvoid SkConic::computeAsQuadError(SkVector* err) const { 1156af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org AS_QUAD_ERROR_SETUP 1157af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org err->set(x, y); 1158af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org} 1159af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 1160af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.orgbool SkConic::asQuadTol(SkScalar tol) const { 1161af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org AS_QUAD_ERROR_SETUP 1162af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org return (x * x + y * y) <= tol * tol; 116397514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org} 11647841c63136e8aa2d3aadbeab8432405abcd73c32skia.committer@gmail.com 1165f16c00e41b72daa81ed7efacbead06b387767841reed// Limit the number of suggested quads to approximate a conic 1166f16c00e41b72daa81ed7efacbead06b387767841reed#define kMaxConicToQuadPOW2 5 1167f16c00e41b72daa81ed7efacbead06b387767841reed 116897514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.orgint SkConic::computeQuadPOW2(SkScalar tol) const { 1169df429f3beac1c191289ba1e3bd918bf84df57bf5Cary Clark if (tol < 0 || !SkScalarIsFinite(tol) || !SkPointPriv::AreFinite(fPts, 3)) { 1170f16c00e41b72daa81ed7efacbead06b387767841reed return 0; 1171f16c00e41b72daa81ed7efacbead06b387767841reed } 1172f16c00e41b72daa81ed7efacbead06b387767841reed 1173af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org AS_QUAD_ERROR_SETUP 1174f16c00e41b72daa81ed7efacbead06b387767841reed 1175f16c00e41b72daa81ed7efacbead06b387767841reed SkScalar error = SkScalarSqrt(x * x + y * y); 1176f16c00e41b72daa81ed7efacbead06b387767841reed int pow2; 1177f16c00e41b72daa81ed7efacbead06b387767841reed for (pow2 = 0; pow2 < kMaxConicToQuadPOW2; ++pow2) { 1178f16c00e41b72daa81ed7efacbead06b387767841reed if (error <= tol) { 1179f16c00e41b72daa81ed7efacbead06b387767841reed break; 1180f16c00e41b72daa81ed7efacbead06b387767841reed } 1181f16c00e41b72daa81ed7efacbead06b387767841reed error *= 0.25f; 1182f16c00e41b72daa81ed7efacbead06b387767841reed } 1183f16c00e41b72daa81ed7efacbead06b387767841reed // float version -- using ceil gives the same results as the above. 1184f16c00e41b72daa81ed7efacbead06b387767841reed if (false) { 1185f16c00e41b72daa81ed7efacbead06b387767841reed SkScalar err = SkScalarSqrt(x * x + y * y); 1186f16c00e41b72daa81ed7efacbead06b387767841reed if (err <= tol) { 1187f16c00e41b72daa81ed7efacbead06b387767841reed return 0; 1188f16c00e41b72daa81ed7efacbead06b387767841reed } 1189f16c00e41b72daa81ed7efacbead06b387767841reed SkScalar tol2 = tol * tol; 1190f16c00e41b72daa81ed7efacbead06b387767841reed if (tol2 == 0) { 1191f16c00e41b72daa81ed7efacbead06b387767841reed return kMaxConicToQuadPOW2; 1192f16c00e41b72daa81ed7efacbead06b387767841reed } 1193f16c00e41b72daa81ed7efacbead06b387767841reed SkScalar fpow2 = SkScalarLog2((x * x + y * y) / tol2) * 0.25f; 1194f16c00e41b72daa81ed7efacbead06b387767841reed int altPow2 = SkScalarCeilToInt(fpow2); 1195f16c00e41b72daa81ed7efacbead06b387767841reed if (altPow2 != pow2) { 1196f16c00e41b72daa81ed7efacbead06b387767841reed SkDebugf("pow2 %d altPow2 %d fbits %g err %g tol %g\n", pow2, altPow2, fpow2, err, tol); 1197f16c00e41b72daa81ed7efacbead06b387767841reed } 1198f16c00e41b72daa81ed7efacbead06b387767841reed pow2 = altPow2; 1199f16c00e41b72daa81ed7efacbead06b387767841reed } 1200f16c00e41b72daa81ed7efacbead06b387767841reed return pow2; 12013df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 12023df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 120363fd760a37905c45d26fc3d49cac261fad1b4808Ben Wagner// This was originally developed and tested for pathops: see SkOpTypes.h 1204bac104605ef3d9a8ed0022694990f00518b809e9caryclark// returns true if (a <= b <= c) || (a >= b >= c) 1205bac104605ef3d9a8ed0022694990f00518b809e9caryclarkstatic bool between(SkScalar a, SkScalar b, SkScalar c) { 1206bac104605ef3d9a8ed0022694990f00518b809e9caryclark return (a - b) * (c - b) <= 0; 1207bac104605ef3d9a8ed0022694990f00518b809e9caryclark} 1208bac104605ef3d9a8ed0022694990f00518b809e9caryclark 120928552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgstatic SkPoint* subdivide(const SkConic& src, SkPoint pts[], int level) { 12103df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org SkASSERT(level >= 0); 1211af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org 12123df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org if (0 == level) { 12133df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org memcpy(pts, &src.fPts[1], 2 * sizeof(SkPoint)); 12143df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org return pts + 2; 12153df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org } else { 121628552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org SkConic dst[2]; 12173df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org src.chop(dst); 1218bac104605ef3d9a8ed0022694990f00518b809e9caryclark const SkScalar startY = src.fPts[0].fY; 1219a0e30b1e40459629e48c5e59f7385b51067e31d6Cary Clark SkScalar endY = src.fPts[2].fY; 1220bac104605ef3d9a8ed0022694990f00518b809e9caryclark if (between(startY, src.fPts[1].fY, endY)) { 1221bac104605ef3d9a8ed0022694990f00518b809e9caryclark // If the input is monotonic and the output is not, the scan converter hangs. 1222bac104605ef3d9a8ed0022694990f00518b809e9caryclark // Ensure that the chopped conics maintain their y-order. 1223bac104605ef3d9a8ed0022694990f00518b809e9caryclark SkScalar midY = dst[0].fPts[2].fY; 1224bac104605ef3d9a8ed0022694990f00518b809e9caryclark if (!between(startY, midY, endY)) { 1225bac104605ef3d9a8ed0022694990f00518b809e9caryclark // If the computed midpoint is outside the ends, move it to the closer one. 1226bac104605ef3d9a8ed0022694990f00518b809e9caryclark SkScalar closerY = SkTAbs(midY - startY) < SkTAbs(midY - endY) ? startY : endY; 1227bac104605ef3d9a8ed0022694990f00518b809e9caryclark dst[0].fPts[2].fY = dst[1].fPts[0].fY = closerY; 1228bac104605ef3d9a8ed0022694990f00518b809e9caryclark } 1229bac104605ef3d9a8ed0022694990f00518b809e9caryclark if (!between(startY, dst[0].fPts[1].fY, dst[0].fPts[2].fY)) { 1230bac104605ef3d9a8ed0022694990f00518b809e9caryclark // If the 1st control is not between the start and end, put it at the start. 1231bac104605ef3d9a8ed0022694990f00518b809e9caryclark // This also reduces the quad to a line. 1232bac104605ef3d9a8ed0022694990f00518b809e9caryclark dst[0].fPts[1].fY = startY; 1233bac104605ef3d9a8ed0022694990f00518b809e9caryclark } 1234bac104605ef3d9a8ed0022694990f00518b809e9caryclark if (!between(dst[1].fPts[0].fY, dst[1].fPts[1].fY, endY)) { 1235bac104605ef3d9a8ed0022694990f00518b809e9caryclark // If the 2nd control is not between the start and end, put it at the end. 1236bac104605ef3d9a8ed0022694990f00518b809e9caryclark // This also reduces the quad to a line. 1237bac104605ef3d9a8ed0022694990f00518b809e9caryclark dst[1].fPts[1].fY = endY; 1238bac104605ef3d9a8ed0022694990f00518b809e9caryclark } 1239bac104605ef3d9a8ed0022694990f00518b809e9caryclark // Verify that all five points are in order. 1240bac104605ef3d9a8ed0022694990f00518b809e9caryclark SkASSERT(between(startY, dst[0].fPts[1].fY, dst[0].fPts[2].fY)); 1241bac104605ef3d9a8ed0022694990f00518b809e9caryclark SkASSERT(between(dst[0].fPts[1].fY, dst[0].fPts[2].fY, dst[1].fPts[1].fY)); 1242bac104605ef3d9a8ed0022694990f00518b809e9caryclark SkASSERT(between(dst[0].fPts[2].fY, dst[1].fPts[1].fY, endY)); 1243bac104605ef3d9a8ed0022694990f00518b809e9caryclark } 12443df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org --level; 12453df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org pts = subdivide(dst[0], pts, level); 12463df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org return subdivide(dst[1], pts, level); 12473df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org } 12488d551011966a1bc14a654dbde704f343c0e222b6mike@reedtribe.org} 12493df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org 125028552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgint SkConic::chopIntoQuadsPOW2(SkPoint pts[], int pow2) const { 1251af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org SkASSERT(pow2 >= 0); 12523cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark *pts = fPts[0]; 12533cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark SkDEBUGCODE(SkPoint* endPts); 12543cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark if (pow2 == kMaxConicToQuadPOW2) { // If an extreme weight generates many quads ... 12553cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark SkConic dst[2]; 12563cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark this->chop(dst); 12573cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark // check to see if the first chop generates a pair of lines 1258df429f3beac1c191289ba1e3bd918bf84df57bf5Cary Clark if (SkPointPriv::EqualsWithinTolerance(dst[0].fPts[1], dst[0].fPts[2]) && 1259df429f3beac1c191289ba1e3bd918bf84df57bf5Cary Clark SkPointPriv::EqualsWithinTolerance(dst[1].fPts[0], dst[1].fPts[1])) { 12603cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark pts[1] = pts[2] = pts[3] = dst[0].fPts[1]; // set ctrl == end to make lines 12613cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark pts[4] = dst[1].fPts[2]; 12623cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark pow2 = 1; 12633cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark SkDEBUGCODE(endPts = &pts[5]); 12643cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark goto commonFinitePtCheck; 12653cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark } 12663cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark } 12673cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclark SkDEBUGCODE(endPts = ) subdivide(*this, pts + 1, pow2); 12683cebe24682ea8bea3bcab400ff1c79b8e0b12ff0caryclarkcommonFinitePtCheck: 1269b1b12f8666a48b8ff1367beed97bc84032552ac8reed const int quadCount = 1 << pow2; 1270b1b12f8666a48b8ff1367beed97bc84032552ac8reed const int ptCount = 2 * quadCount + 1; 1271b1b12f8666a48b8ff1367beed97bc84032552ac8reed SkASSERT(endPts - pts == ptCount); 1272df429f3beac1c191289ba1e3bd918bf84df57bf5Cary Clark if (!SkPointPriv::AreFinite(pts, ptCount)) { 1273b1b12f8666a48b8ff1367beed97bc84032552ac8reed // if we generated a non-finite, pin ourselves to the middle of the hull, 1274b1b12f8666a48b8ff1367beed97bc84032552ac8reed // as our first and last are already on the first/last pts of the hull. 1275b1b12f8666a48b8ff1367beed97bc84032552ac8reed for (int i = 1; i < ptCount - 1; ++i) { 1276b1b12f8666a48b8ff1367beed97bc84032552ac8reed pts[i] = fPts[1]; 1277b1b12f8666a48b8ff1367beed97bc84032552ac8reed } 1278b1b12f8666a48b8ff1367beed97bc84032552ac8reed } 12793df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org return 1 << pow2; 12803df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org} 12810c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 128228552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::findXExtrema(SkScalar* t) const { 12836862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org return conic_find_extrema(&fPts[0].fX, fW, t); 12840c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 12850c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 128628552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::findYExtrema(SkScalar* t) const { 12876862cbad085729acb77825392c8c2a4f888a99cfmike@reedtribe.org return conic_find_extrema(&fPts[0].fY, fW, t); 12880c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 12890c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 129028552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::chopAtXExtrema(SkConic dst[2]) const { 12910c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar t; 12920c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org if (this->findXExtrema(&t)) { 1293414c4295f951d43068666b6294df15b2fd2ba85ccaryclark if (!this->chopAt(t, dst)) { 1294414c4295f951d43068666b6294df15b2fd2ba85ccaryclark // if chop can't return finite values, don't chop 1295414c4295f951d43068666b6294df15b2fd2ba85ccaryclark return false; 1296414c4295f951d43068666b6294df15b2fd2ba85ccaryclark } 12970c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // now clean-up the middle, since we know t was meant to be at 12980c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // an X-extrema 12990c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar value = dst[0].fPts[2].fX; 13000c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[0].fPts[1].fX = value; 13010c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[0].fX = value; 13020c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[1].fX = value; 13030c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return true; 13040c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org } 13050c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return false; 13060c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 13070c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 130828552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgbool SkConic::chopAtYExtrema(SkConic dst[2]) const { 13090c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar t; 13100c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org if (this->findYExtrema(&t)) { 1311414c4295f951d43068666b6294df15b2fd2ba85ccaryclark if (!this->chopAt(t, dst)) { 1312414c4295f951d43068666b6294df15b2fd2ba85ccaryclark // if chop can't return finite values, don't chop 1313414c4295f951d43068666b6294df15b2fd2ba85ccaryclark return false; 1314414c4295f951d43068666b6294df15b2fd2ba85ccaryclark } 13150c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // now clean-up the middle, since we know t was meant to be at 13160c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org // an Y-extrema 13170c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org SkScalar value = dst[0].fPts[2].fY; 13180c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[0].fPts[1].fY = value; 13190c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[0].fY = value; 13200c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org dst[1].fPts[1].fY = value; 13210c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return true; 13220c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org } 13230c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org return false; 13240c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org} 13250c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 132628552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::computeTightBounds(SkRect* bounds) const { 13275c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org SkPoint pts[4]; 13285c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org pts[0] = fPts[0]; 13295c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org pts[1] = fPts[2]; 13305c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org int count = 2; 13315c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org 13325c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org SkScalar t; 13335c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org if (this->findXExtrema(&t)) { 13345c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org this->evalAt(t, &pts[count++]); 13355c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org } 13365c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org if (this->findYExtrema(&t)) { 13375c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org this->evalAt(t, &pts[count++]); 13385c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org } 13395c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org bounds->set(pts, count); 13405c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org} 13415c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org 134228552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgvoid SkConic::computeFastBounds(SkRect* bounds) const { 13435c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org bounds->set(fPts, 3); 13445c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org} 1345def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org 1346612f70d5fa2d4bf7a393c791966bbce933407017caryclark#if 0 // unimplemented 1347def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.orgbool SkConic::findMaxCurvature(SkScalar* t) const { 1348def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org // TODO: Implement me 1349def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org return false; 1350def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org} 1351612f70d5fa2d4bf7a393c791966bbce933407017caryclark#endif 1352220f926d9d4b38a9018c922c095847bbd261f583reed 13530a78e1e37ebdb3250f472a64b067fa463bea37ffMike ReedSkScalar SkConic::TransformW(const SkPoint pts[], SkScalar w, const SkMatrix& matrix) { 1354220f926d9d4b38a9018c922c095847bbd261f583reed if (!matrix.hasPerspective()) { 1355220f926d9d4b38a9018c922c095847bbd261f583reed return w; 1356220f926d9d4b38a9018c922c095847bbd261f583reed } 1357220f926d9d4b38a9018c922c095847bbd261f583reed 1358e4442cb0b537720ab32106b3b5353dbb78f11b26Cary Clark SkPoint3 src[3], dst[3]; 1359950e986b1bc127af1f484572d2494091957486f9mtklein 1360220f926d9d4b38a9018c922c095847bbd261f583reed ratquad_mapTo3D(pts, w, src); 1361220f926d9d4b38a9018c922c095847bbd261f583reed 1362e4442cb0b537720ab32106b3b5353dbb78f11b26Cary Clark matrix.mapHomogeneousPoints(dst, src, 3); 1363220f926d9d4b38a9018c922c095847bbd261f583reed 1364220f926d9d4b38a9018c922c095847bbd261f583reed // w' = sqrt(w1*w1/w0*w2) 13650a78e1e37ebdb3250f472a64b067fa463bea37ffMike Reed // use doubles temporarily, to handle small numer/denom 13660a78e1e37ebdb3250f472a64b067fa463bea37ffMike Reed double w0 = dst[0].fZ; 13670a78e1e37ebdb3250f472a64b067fa463bea37ffMike Reed double w1 = dst[1].fZ; 13680a78e1e37ebdb3250f472a64b067fa463bea37ffMike Reed double w2 = dst[2].fZ; 13690a78e1e37ebdb3250f472a64b067fa463bea37ffMike Reed return sk_double_to_float(sqrt((w1 * w1) / (w0 * w2))); 1370220f926d9d4b38a9018c922c095847bbd261f583reed} 1371d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1372d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reedint SkConic::BuildUnitArc(const SkVector& uStart, const SkVector& uStop, SkRotationDirection dir, 1373d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkMatrix* userMatrix, SkConic dst[kMaxConicsForArc]) { 1374d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // rotate by x,y so that uStart is (1.0) 1375d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkScalar x = SkPoint::DotProduct(uStart, uStop); 1376d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkScalar y = SkPoint::CrossProduct(uStart, uStop); 1377d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1378d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkScalar absY = SkScalarAbs(y); 1379d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1380d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // check for (effectively) coincident vectors 1381d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // this can happen if our angle is nearly 0 or nearly 180 (y == 0) 1382d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // ... we use the dot-prod to distinguish between 0 and 180 (x > 0) 1383d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if (absY <= SK_ScalarNearlyZero && x > 0 && ((y >= 0 && kCW_SkRotationDirection == dir) || 1384d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed (y <= 0 && kCCW_SkRotationDirection == dir))) { 1385d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed return 0; 1386d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1387d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1388d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if (dir == kCCW_SkRotationDirection) { 1389d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed y = -y; 1390d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1391d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1392d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // We decide to use 1-conic per quadrant of a circle. What quadrant does [xy] lie in? 1393d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // 0 == [0 .. 90) 1394d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // 1 == [90 ..180) 1395d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // 2 == [180..270) 1396d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // 3 == [270..360) 1397d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // 1398d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed int quadrant = 0; 1399d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if (0 == y) { 1400d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed quadrant = 2; // 180 1401d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero); 1402d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } else if (0 == x) { 1403d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero); 1404d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed quadrant = y > 0 ? 1 : 3; // 90 : 270 1405d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } else { 1406d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if (y < 0) { 1407d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed quadrant += 2; 1408d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1409d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if ((x < 0) != (y < 0)) { 1410d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed quadrant += 1; 1411d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1412d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1413d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1414d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkPoint quadrantPts[] = { 1415d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 }, { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 } 1416d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed }; 1417d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkScalar quadrantWeight = SK_ScalarRoot2Over2; 1418d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1419d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed int conicCount = quadrant; 1420d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed for (int i = 0; i < conicCount; ++i) { 1421d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed dst[i].set(&quadrantPts[i * 2], quadrantWeight); 1422d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1423d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1424d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // Now compute any remaing (sub-90-degree) arc for the last conic 1425d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkPoint finalP = { x, y }; 1426d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkPoint& lastQ = quadrantPts[quadrant * 2]; // will already be a unit-vector 1427d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkScalar dot = SkVector::DotProduct(lastQ, finalP); 142888f0a99fd48cfb30ca5596182f8932d76cd76f17reed SkASSERT(0 <= dot && dot <= SK_Scalar1 + SK_ScalarNearlyZero); 1429d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1430c6325cde797baeedebc515bc8610f96eacbd36c9caryclark if (dot < 1) { 1431d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkVector offCurve = { lastQ.x() + x, lastQ.y() + y }; 1432d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // compute the bisector vector, and then rescale to be the off-curve point. 1433d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // we compute its length from cos(theta/2) = length / 1, using half-angle identity we get 1434d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // length = sqrt(2 / (1 + cos(theta)). We already have cos() when to computed the dot. 1435d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // This is nice, since our computed weight is cos(theta/2) as well! 1436d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // 1437d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkScalar cosThetaOver2 = SkScalarSqrt((1 + dot) / 2); 1438d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed offCurve.setLength(SkScalarInvert(cosThetaOver2)); 1439df429f3beac1c191289ba1e3bd918bf84df57bf5Cary Clark if (!SkPointPriv::EqualsWithinTolerance(lastQ, offCurve)) { 1440f71ab8f58b0a7abb7818cf665dfb116ef370d572caryclark dst[conicCount].set(lastQ, offCurve, finalP, cosThetaOver2); 1441f71ab8f58b0a7abb7818cf665dfb116ef370d572caryclark conicCount += 1; 144263fd760a37905c45d26fc3d49cac261fad1b4808Ben Wagner } 1443d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1444d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 1445d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed // now handle counter-clockwise and the initial unitStart rotation 1446d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed SkMatrix matrix; 1447d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed matrix.setSinCos(uStart.fY, uStart.fX); 1448d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if (dir == kCCW_SkRotationDirection) { 1449d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed matrix.preScale(SK_Scalar1, -SK_Scalar1); 1450d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1451d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed if (userMatrix) { 1452d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed matrix.postConcat(*userMatrix); 1453d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1454d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed for (int i = 0; i < conicCount; ++i) { 1455d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed matrix.mapPoints(dst[i].fPts, 3); 1456d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 1457d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed return conicCount; 1458d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed} 1459