180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2006 The Android Open Source Project 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkGeometry.h" 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "Sk64.h" 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkMatrix.h" 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querubool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2], bool* ambiguous) { 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (ambiguous) { 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ambiguous = false; 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Determine quick discards. 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Consider query line going exactly through point 0 to not 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // intersect, for symmetry with SkXRayCrossesMonotonicCubic. 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt.fY == pts[0].fY) { 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (ambiguous) { 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ambiguous = true; 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt.fY < pts[0].fY && pt.fY < pts[1].fY) 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt.fY > pts[0].fY && pt.fY > pts[1].fY) 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt.fX > pts[0].fX && pt.fX > pts[1].fX) 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Determine degenerate cases 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (SkScalarNearlyZero(pts[0].fY - pts[1].fY)) 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (SkScalarNearlyZero(pts[0].fX - pts[1].fX)) { 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // We've already determined the query point lies within the 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // vertical range of the line segment. 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt.fX <= pts[0].fX) { 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (ambiguous) { 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ambiguous = (pt.fY == pts[1].fY); 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Ambiguity check 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt.fY == pts[1].fY) { 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt.fX <= pts[1].fX) { 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (ambiguous) { 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ambiguous = true; 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Full line segment evaluation 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar delta_y = pts[1].fY - pts[0].fY; 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar delta_x = pts[1].fX - pts[0].fX; 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar slope = SkScalarDiv(delta_y, delta_x); 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar b = pts[0].fY - SkScalarMul(slope, pts[0].fX); 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Solve for x coordinate at y = pt.fY 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar x = SkScalarDiv(pt.fY - b, slope); 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return pt.fX <= x; 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** If defined, this makes eval_quad and eval_cubic do more setup (sometimes 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru involving integer multiplies by 2 or 3, but fewer calls to SkScalarMul. 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru May also introduce overflow of fixed when we compute our setup. 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_SCALAR_IS_FIXED 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru #define DIRECT_EVAL_OF_POLYNOMIALS 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru//////////////////////////////////////////////////////////////////////// 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_SCALAR_IS_FIXED 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static int is_not_monotonic(int a, int b, int c, int d) 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return (((a - b) | (b - c) | (c - d)) & ((b - a) | (c - b) | (d - c))) >> 31; 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static int is_not_monotonic(int a, int b, int c) 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return (((a - b) | (b - c)) & ((b - a) | (c - b))) >> 31; 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#else 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static int is_not_monotonic(float a, float b, float c) 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru float ab = a - b; 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru float bc = b - c; 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (ab < 0) 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bc = -bc; 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return ab == 0 || bc < 0; 9580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru//////////////////////////////////////////////////////////////////////// 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic bool is_unit_interval(SkScalar x) 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return x > 0 && x < SK_Scalar1; 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic int valid_unit_divide(SkScalar numer, SkScalar denom, SkScalar* ratio) 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(ratio); 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (numer < 0) 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru numer = -numer; 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru denom = -denom; 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (denom == 0 || numer == 0 || numer >= denom) 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 0; 11780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar r = SkScalarDiv(numer, denom); 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (SkScalarIsNaN(r)) { 12080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 0; 12180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(r >= 0 && r < SK_Scalar1); 12380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (r == 0) // catch underflow if numer <<<< denom 12480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 0; 12580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ratio = r; 12680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 1; 12780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** From Numerical Recipes in C. 13080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Q = -1/2 (B + sign(B) sqrt[B*B - 4*A*C]) 13280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru x1 = Q / A 13380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru x2 = C / Q 13480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 13580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]) 13680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 13780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(roots); 13880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (A == 0) 14080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return valid_unit_divide(-C, B, roots); 14180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 14280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar* r = roots; 14380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 14480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_SCALAR_IS_FLOAT 14580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru float R = B*B - 4*A*C; 14680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (R < 0 || SkScalarIsNaN(R)) { // complex roots 14780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 0; 14880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 14980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru R = sk_float_sqrt(R); 15080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#else 15180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Sk64 RR, tmp; 15280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru RR.setMul(B,B); 15480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp.setMul(A,C); 15580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp.shiftLeft(2); 15680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru RR.sub(tmp); 15780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (RR.isNeg()) 15880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 0; 15980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFixed R = RR.getSqrt(); 16080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 16180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 16280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar Q = (B < 0) ? -(B-R)/2 : -(B+R)/2; 16380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru r += valid_unit_divide(Q, A, r); 16480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru r += valid_unit_divide(C, Q, r); 16580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (r - roots == 2) 16680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 16780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (roots[0] > roots[1]) 16880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkTSwap<SkScalar>(roots[0], roots[1]); 16980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else if (roots[0] == roots[1]) // nearly-equal? 17080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru r -= 1; // skip the double root 17180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 17280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return (int)(r - roots); 17380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 17480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 17580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_SCALAR_IS_FIXED 17680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** Trim A/B/C down so that they are all <= 32bits 17780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru and then call SkFindUnitQuadRoots() 17880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 17980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic int Sk64FindFixedQuadRoots(const Sk64& A, const Sk64& B, const Sk64& C, SkFixed roots[2]) 18080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 18180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int na = A.shiftToMake32(); 18280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int nb = B.shiftToMake32(); 18380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int nc = C.shiftToMake32(); 18480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 18580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int shift = SkMax32(na, SkMax32(nb, nc)); 18680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(shift >= 0); 18780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 18880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkFindUnitQuadRoots(A.getShiftRight(shift), B.getShiftRight(shift), C.getShiftRight(shift), roots); 18980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 19080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 19180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 19280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru///////////////////////////////////////////////////////////////////////////////////// 19380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru///////////////////////////////////////////////////////////////////////////////////// 19480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 19580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic SkScalar eval_quad(const SkScalar src[], SkScalar t) 19680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 19780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(src); 19880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(t >= 0 && t <= SK_Scalar1); 19980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 20080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef DIRECT_EVAL_OF_POLYNOMIALS 20180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar C = src[0]; 20280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar A = src[4] - 2 * src[2] + C; 20380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar B = 2 * (src[2] - C); 20480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 20580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#else 20680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar ab = SkScalarInterp(src[0], src[2], t); 20780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar bc = SkScalarInterp(src[2], src[4], t); 20880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkScalarInterp(ab, bc, t); 20980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 21080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 21180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 21280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic SkScalar eval_quad_derivative(const SkScalar src[], SkScalar t) 21380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 21480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar A = src[4] - 2 * src[2] + src[0]; 21580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar B = src[2] - src[0]; 21680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 21780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 2 * SkScalarMulAdd(A, t, B); 21880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 21980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 22080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic SkScalar eval_quad_derivative_at_half(const SkScalar src[]) 22180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 22280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar A = src[4] - 2 * src[2] + src[0]; 22380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar B = src[2] - src[0]; 22480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return A + 2 * B; 22580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 22680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 22780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent) 22880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 22980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(src); 23080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(t >= 0 && t <= SK_Scalar1); 23180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 23280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt) 23380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pt->set(eval_quad(&src[0].fX, t), eval_quad(&src[0].fY, t)); 23480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (tangent) 23580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tangent->set(eval_quad_derivative(&src[0].fX, t), 23680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru eval_quad_derivative(&src[0].fY, t)); 23780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 23880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 23980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkEvalQuadAtHalf(const SkPoint src[3], SkPoint* pt, SkVector* tangent) 24080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 24180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(src); 24280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 24380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt) 24480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 24580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 24680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 24780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 24880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 24980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pt->set(SkScalarAve(x01, x12), SkScalarAve(y01, y12)); 25080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 25180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (tangent) 25280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tangent->set(eval_quad_derivative_at_half(&src[0].fX), 25380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru eval_quad_derivative_at_half(&src[0].fY)); 25480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 25580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 25680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic void interp_quad_coords(const SkScalar* src, SkScalar* dst, SkScalar t) 25780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 25880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar ab = SkScalarInterp(src[0], src[2], t); 25980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar bc = SkScalarInterp(src[2], src[4], t); 26080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 26180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[0] = src[0]; 26280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[2] = ab; 26380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[4] = SkScalarInterp(ab, bc, t); 26480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[6] = bc; 26580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[8] = src[4]; 26680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 26780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 26880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t) 26980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 27080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(t > 0 && t < SK_Scalar1); 27180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 27280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru interp_quad_coords(&src[0].fX, &dst[0].fX, t); 27380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru interp_quad_coords(&src[0].fY, &dst[0].fY, t); 27480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 27580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 27680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]) 27780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 27880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 27980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 28080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 28180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 28280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 28380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[0] = src[0]; 28480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[1].set(x01, y01); 28580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[2].set(SkScalarAve(x01, x12), SkScalarAve(y01, y12)); 28680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[3].set(x12, y12); 28780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[4] = src[2]; 28880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 28980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 29080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** Quad'(t) = At + B, where 29180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru A = 2(a - 2b + c) 29280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru B = 2(b - a) 29380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Solve for t, only if it fits between 0 < t < 1 29480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 29580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValue[1]) 29680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 29780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /* At + B == 0 29880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru t = -B / A 29980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 30080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_SCALAR_IS_FIXED 30180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return is_not_monotonic(a, b, c) && valid_unit_divide(a - b, a - b - b + c, tValue); 30280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#else 30380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return valid_unit_divide(a - b, a - b - b + c, tValue); 30480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 30580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 30680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 30780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic inline void flatten_double_quad_extrema(SkScalar coords[14]) 30880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 30980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru coords[2] = coords[6] = coords[4]; 31080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 31180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 31280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* Returns 0 for 1 quad, and 1 for two quads, either way the answer is 31380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru stored in dst[]. Guarantees that the 1/2 quads will be monotonic. 31480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 31580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]) 31680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 31780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(src); 31880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(dst); 31980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 32080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#if 0 32180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static bool once = true; 32280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (once) 32380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 32480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru once = false; 32580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint s[3] = { 0, 26398, 0, 26331, 0, 20621428 }; 32680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint d[6]; 32780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 32880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int n = SkChopQuadAtYExtrema(s, d); 32980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDebugf("chop=%d, Y=[%x %x %x %x %x %x]\n", n, d[0].fY, d[1].fY, d[2].fY, d[3].fY, d[4].fY, d[5].fY); 33080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 33180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 33280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 33380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar a = src[0].fY; 33480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar b = src[1].fY; 33580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar c = src[2].fY; 33680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 33780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (is_not_monotonic(a, b, c)) 33880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 33980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar tValue; 34080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (valid_unit_divide(a - b, a - b - b + c, &tValue)) 34180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 34280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopQuadAt(src, dst, tValue); 34380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru flatten_double_quad_extrema(&dst[0].fY); 34480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 1; 34580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 34680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if we get here, we need to force dst to be monotonic, even though 34780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // we couldn't compute a unit_divide value (probably underflow). 34880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; 34980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 35080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[0].set(src[0].fX, a); 35180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[1].set(src[1].fX, b); 35280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[2].set(src[2].fX, c); 35380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 0; 35480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 35580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 35680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* Returns 0 for 1 quad, and 1 for two quads, either way the answer is 35780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru stored in dst[]. Guarantees that the 1/2 quads will be monotonic. 35880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 35980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]) 36080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 36180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(src); 36280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(dst); 36380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 36480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar a = src[0].fX; 36580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar b = src[1].fX; 36680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar c = src[2].fX; 36780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 36880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (is_not_monotonic(a, b, c)) { 36980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar tValue; 37080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (valid_unit_divide(a - b, a - b - b + c, &tValue)) { 37180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopQuadAt(src, dst, tValue); 37280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru flatten_double_quad_extrema(&dst[0].fX); 37380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 1; 37480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 37580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if we get here, we need to force dst to be monotonic, even though 37680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // we couldn't compute a unit_divide value (probably underflow). 37780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; 37880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 37980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[0].set(a, src[0].fY); 38080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[1].set(b, src[1].fY); 38180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[2].set(c, src[2].fY); 38280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 0; 38380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 38480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 38580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// F(t) = a (1 - t) ^ 2 + 2 b t (1 - t) + c t ^ 2 38680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// F'(t) = 2 (b - a) + 2 (a - 2b + c) t 38780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// F''(t) = 2 (a - 2b + c) 38880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// 38980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// A = 2 (b - a) 39080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// B = 2 (a - 2b + c) 39180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// 39280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// Maximum curvature for a quadratic means solving 39380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// Fx' Fx'' + Fy' Fy'' = 0 39480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// 39580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// t = - (Ax Bx + Ay By) / (Bx ^ 2 + By ^ 2) 39680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// 39780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]) 39880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 39980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar Ax = src[1].fX - src[0].fX; 40080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar Ay = src[1].fY - src[0].fY; 40180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar Bx = src[0].fX - src[1].fX - src[1].fX + src[2].fX; 40280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar By = src[0].fY - src[1].fY - src[1].fY + src[2].fY; 40380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar t = 0; // 0 means don't chop 40480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 40580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_SCALAR_IS_FLOAT 40680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru (void)valid_unit_divide(-(Ax * Bx + Ay * By), Bx * Bx + By * By, &t); 40780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#else 40880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // !!! should I use SkFloat here? seems like it 40980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Sk64 numer, denom, tmp; 41080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 41180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru numer.setMul(Ax, -Bx); 41280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp.setMul(Ay, -By); 41380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru numer.add(tmp); 41480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 41580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (numer.isPos()) // do nothing if numer <= 0 41680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 41780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru denom.setMul(Bx, Bx); 41880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp.setMul(By, By); 41980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru denom.add(tmp); 42080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(!denom.isNeg()); 42180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (numer < denom) 42280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 42380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru t = numer.getFixedDiv(denom); 42480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(t >= 0 && t <= SK_Fixed1); // assert that we're numerically stable (ha!) 42580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if ((unsigned)t >= SK_Fixed1) // runtime check for numerical stability 42680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru t = 0; // ignore the chop 42780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 42880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 42980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 43080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 43180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (t == 0) 43280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 43380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(dst, src, 3 * sizeof(SkPoint)); 43480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 1; 43580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 43680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 43780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 43880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopQuadAt(src, dst, t); 43980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 2; 44080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 44180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 44280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 44380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_SCALAR_IS_FLOAT 44480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru #define SK_ScalarTwoThirds (0.666666666f) 44580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#else 44680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru #define SK_ScalarTwoThirds ((SkFixed)(43691)) 44780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 44880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 44980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]) { 45080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const SkScalar scale = SK_ScalarTwoThirds; 45180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[0] = src[0]; 45280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[1].set(src[0].fX + SkScalarMul(src[1].fX - src[0].fX, scale), 45380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru src[0].fY + SkScalarMul(src[1].fY - src[0].fY, scale)); 45480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[2].set(src[2].fX + SkScalarMul(src[1].fX - src[2].fX, scale), 45580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru src[2].fY + SkScalarMul(src[1].fY - src[2].fY, scale)); 45680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[3] = src[2]; 45780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 45880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 45980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru//////////////////////////////////////////////////////////////////////////////////////// 46080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru///// CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS ///// 46180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru//////////////////////////////////////////////////////////////////////////////////////// 46280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 46380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic void get_cubic_coeff(const SkScalar pt[], SkScalar coeff[4]) 46480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 46580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru coeff[0] = pt[6] + 3*(pt[2] - pt[4]) - pt[0]; 46680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru coeff[1] = 3*(pt[4] - pt[2] - pt[2] + pt[0]); 46780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru coeff[2] = 3*(pt[2] - pt[0]); 46880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru coeff[3] = pt[0]; 46980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 47080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 47180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]) 47280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 47380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(pts); 47480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 47580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (cx) 47680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru get_cubic_coeff(&pts[0].fX, cx); 47780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (cy) 47880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru get_cubic_coeff(&pts[0].fY, cy); 47980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 48080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 48180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic SkScalar eval_cubic(const SkScalar src[], SkScalar t) 48280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 48380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(src); 48480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(t >= 0 && t <= SK_Scalar1); 48580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 48680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (t == 0) 48780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return src[0]; 48880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 48980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef DIRECT_EVAL_OF_POLYNOMIALS 49080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar D = src[0]; 49180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar A = src[6] + 3*(src[2] - src[4]) - D; 49280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar B = 3*(src[4] - src[2] - src[2] + D); 49380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar C = 3*(src[2] - D); 49480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 49580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); 49680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#else 49780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar ab = SkScalarInterp(src[0], src[2], t); 49880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar bc = SkScalarInterp(src[2], src[4], t); 49980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar cd = SkScalarInterp(src[4], src[6], t); 50080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar abc = SkScalarInterp(ab, bc, t); 50180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar bcd = SkScalarInterp(bc, cd, t); 50280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkScalarInterp(abc, bcd, t); 50380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 50480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 50580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 50680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** return At^2 + Bt + C 50780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 50880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic SkScalar eval_quadratic(SkScalar A, SkScalar B, SkScalar C, SkScalar t) 50980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 51080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(t >= 0 && t <= SK_Scalar1); 51180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 51280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 51380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 51480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 51580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic SkScalar eval_cubic_derivative(const SkScalar src[], SkScalar t) 51680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 51780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; 51880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar B = 2*(src[4] - 2 * src[2] + src[0]); 51980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar C = src[2] - src[0]; 52080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 52180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return eval_quadratic(A, B, C, t); 52280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 52380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 52480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic SkScalar eval_cubic_2ndDerivative(const SkScalar src[], SkScalar t) 52580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 52680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; 52780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar B = src[4] - 2 * src[2] + src[0]; 52880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 52980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkScalarMulAdd(A, t, B); 53080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 53180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 53280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* loc, SkVector* tangent, SkVector* curvature) 53380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 53480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(src); 53580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(t >= 0 && t <= SK_Scalar1); 53680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 53780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (loc) 53880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru loc->set(eval_cubic(&src[0].fX, t), eval_cubic(&src[0].fY, t)); 53980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (tangent) 54080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tangent->set(eval_cubic_derivative(&src[0].fX, t), 54180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru eval_cubic_derivative(&src[0].fY, t)); 54280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (curvature) 54380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru curvature->set(eval_cubic_2ndDerivative(&src[0].fX, t), 54480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru eval_cubic_2ndDerivative(&src[0].fY, t)); 54580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 54680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 54780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** Cubic'(t) = At^2 + Bt + C, where 54880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru A = 3(-a + 3(b - c) + d) 54980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru B = 6(a - 2b + c) 55080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru C = 3(b - a) 55180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Solve for t, keeping only those that fit betwee 0 < t < 1 55280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 55380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, SkScalar tValues[2]) 55480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 55580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_SCALAR_IS_FIXED 55680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (!is_not_monotonic(a, b, c, d)) 55780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 0; 55880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 55980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 56080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // we divide A,B,C by 3 to simplify 56180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar A = d - a + 3*(b - c); 56280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar B = 2*(a - b - b + c); 56380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar C = b - a; 56480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 56580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkFindUnitQuadRoots(A, B, C, tValues); 56680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 56780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 56880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic void interp_cubic_coords(const SkScalar* src, SkScalar* dst, SkScalar t) 56980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 57080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar ab = SkScalarInterp(src[0], src[2], t); 57180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar bc = SkScalarInterp(src[2], src[4], t); 57280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar cd = SkScalarInterp(src[4], src[6], t); 57380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar abc = SkScalarInterp(ab, bc, t); 57480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar bcd = SkScalarInterp(bc, cd, t); 57580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar abcd = SkScalarInterp(abc, bcd, t); 57680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 57780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[0] = src[0]; 57880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[2] = ab; 57980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[4] = abc; 58080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[6] = abcd; 58180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[8] = bcd; 58280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[10] = cd; 58380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[12] = src[6]; 58480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 58580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 58680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t) 58780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 58880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(t > 0 && t < SK_Scalar1); 58980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 59080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru interp_cubic_coords(&src[0].fX, &dst[0].fX, t); 59180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru interp_cubic_coords(&src[0].fY, &dst[0].fY, t); 59280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 59380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 59480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* http://code.google.com/p/skia/issues/detail?id=32 59580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 59680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru This test code would fail when we didn't check the return result of 59780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru valid_unit_divide in SkChopCubicAt(... tValues[], int roots). The reason is 59880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru that after the first chop, the parameters to valid_unit_divide are equal 59980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru (thanks to finite float precision and rounding in the subtracts). Thus 60080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru even though the 2nd tValue looks < 1.0, after we renormalize it, we end 60180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru up with 1.0, hence the need to check and just return the last cubic as 60280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru a degenerate clump of 4 points in the sampe place. 60380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 60480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static void test_cubic() { 60580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint src[4] = { 60680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 556.25000, 523.03003 }, 60780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 556.23999, 522.96002 }, 60880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 556.21997, 522.89001 }, 60980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 556.21997, 522.82001 } 61080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 61180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint dst[10]; 61280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar tval[] = { 0.33333334f, 0.99999994f }; 61380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopCubicAt(src, dst, tval, 2); 61480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 61580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 61680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 61780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar tValues[], int roots) 61880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 61980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_DEBUG 62080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 62180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 0; i < roots - 1; i++) 62280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 62380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(is_unit_interval(tValues[i])); 62480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(is_unit_interval(tValues[i+1])); 62580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(tValues[i] < tValues[i+1]); 62680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 62780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 62880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 62980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 63080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (dst) 63180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 63280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (roots == 0) // nothing to chop 63380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(dst, src, 4*sizeof(SkPoint)); 63480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 63580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 63680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar t = tValues[0]; 63780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint tmp[4]; 63880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 63980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 0; i < roots; i++) 64080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 64180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopCubicAt(src, dst, t); 64280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (i == roots - 1) 64380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru break; 64480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 64580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst += 3; 64680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // have src point to the remaining cubic (after the chop) 64780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(tmp, dst, 4 * sizeof(SkPoint)); 64880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru src = tmp; 64980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 65080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // watch out in case the renormalized t isn't in range 65180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (!valid_unit_divide(tValues[i+1] - tValues[i], 65280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SK_Scalar1 - tValues[i], &t)) { 65380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if we can't, just create a degenerate cubic 65480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[4] = dst[5] = dst[6] = src[3]; 65580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru break; 65680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 65780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 65880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 65980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 66080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 66180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 66280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]) 66380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 66480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 66580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 66680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 66780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 66880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar x23 = SkScalarAve(src[2].fX, src[3].fX); 66980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar y23 = SkScalarAve(src[2].fY, src[3].fY); 67080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 67180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar x012 = SkScalarAve(x01, x12); 67280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar y012 = SkScalarAve(y01, y12); 67380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar x123 = SkScalarAve(x12, x23); 67480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar y123 = SkScalarAve(y12, y23); 67580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 67680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[0] = src[0]; 67780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[1].set(x01, y01); 67880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[2].set(x012, y012); 67980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[3].set(SkScalarAve(x012, x123), SkScalarAve(y012, y123)); 68080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[4].set(x123, y123); 68180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[5].set(x23, y23); 68280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[6] = src[3]; 68380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 68480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 68580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic void flatten_double_cubic_extrema(SkScalar coords[14]) 68680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 68780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru coords[4] = coords[8] = coords[6]; 68880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 68980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 69080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that 69180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru the resulting beziers are monotonic in Y. This is called by the scan converter. 69280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Depending on what is returned, dst[] is treated as follows 69380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 0 dst[0..3] is the original cubic 69480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1 dst[0..3] and dst[3..6] are the two new cubics 69580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics 69680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru If dst == null, it is ignored and only the count is returned. 69780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 69880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]) { 69980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar tValues[2]; 70080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int roots = SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY, 70180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru src[3].fY, tValues); 70280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 70380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopCubicAt(src, dst, tValues, roots); 70480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (dst && roots > 0) { 70580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // we do some cleanup to ensure our Y extrema are flat 70680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru flatten_double_cubic_extrema(&dst[0].fY); 70780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (roots == 2) { 70880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru flatten_double_cubic_extrema(&dst[3].fY); 70980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 71080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 71180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return roots; 71280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 71380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 71480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]) { 71580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar tValues[2]; 71680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int roots = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX, 71780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru src[3].fX, tValues); 71880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 71980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopCubicAt(src, dst, tValues, roots); 72080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (dst && roots > 0) { 72180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // we do some cleanup to ensure our Y extrema are flat 72280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru flatten_double_cubic_extrema(&dst[0].fX); 72380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (roots == 2) { 72480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru flatten_double_cubic_extrema(&dst[3].fX); 72580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 72680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 72780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return roots; 72880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 72980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 73080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** http://www.faculty.idc.ac.il/arik/quality/appendixA.html 73180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 73280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Inflection means that curvature is zero. 73380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Curvature is [F' x F''] / [F'^3] 73480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru So we solve F'x X F''y - F'y X F''y == 0 73580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru After some canceling of the cubic term, we get 73680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru A = b - a 73780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru B = c - 2b + a 73880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru C = d - 3c + 3b - a 73980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru (BxCy - ByCx)t^2 + (AxCy - AyCx)t + AxBy - AyBx == 0 74080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 74180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[]) 74280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 74380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar Ax = src[1].fX - src[0].fX; 74480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar Ay = src[1].fY - src[0].fY; 74580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar Bx = src[2].fX - 2 * src[1].fX + src[0].fX; 74680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar By = src[2].fY - 2 * src[1].fY + src[0].fY; 74780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar Cx = src[3].fX + 3 * (src[1].fX - src[2].fX) - src[0].fX; 74880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar Cy = src[3].fY + 3 * (src[1].fY - src[2].fY) - src[0].fY; 74980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count; 75080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 75180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_SCALAR_IS_FLOAT 75280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru count = SkFindUnitQuadRoots(Bx*Cy - By*Cx, Ax*Cy - Ay*Cx, Ax*By - Ay*Bx, tValues); 75380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#else 75480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Sk64 A, B, C, tmp; 75580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 75680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru A.setMul(Bx, Cy); 75780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp.setMul(By, Cx); 75880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru A.sub(tmp); 75980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 76080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru B.setMul(Ax, Cy); 76180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp.setMul(Ay, Cx); 76280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru B.sub(tmp); 76380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 76480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru C.setMul(Ax, By); 76580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp.setMul(Ay, Bx); 76680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru C.sub(tmp); 76780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 76880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru count = Sk64FindFixedQuadRoots(A, B, C, tValues); 76980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 77080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 77180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return count; 77280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 77380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 77480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkChopCubicAtInflections(const SkPoint src[], SkPoint dst[10]) 77580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 77680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar tValues[2]; 77780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count = SkFindCubicInflections(src, tValues); 77880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 77980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (dst) 78080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 78180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (count == 0) 78280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(dst, src, 4 * sizeof(SkPoint)); 78380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 78480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopCubicAt(src, dst, tValues, count); 78580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 78680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return count + 1; 78780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 78880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 78980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querutemplate <typename T> void bubble_sort(T array[], int count) 79080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 79180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = count - 1; i > 0; --i) 79280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int j = i; j > 0; --j) 79380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (array[j] < array[j-1]) 79480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 79580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru T tmp(array[j]); 79680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru array[j] = array[j-1]; 79780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru array[j-1] = tmp; 79880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 79980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 80080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 80180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkFP.h" 80280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 80380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// newton refinement 80480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#if 0 80580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic SkScalar refine_cubic_root(const SkFP coeff[4], SkScalar root) 80680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 80780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // x1 = x0 - f(t) / f'(t) 80880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 80980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFP T = SkScalarToFloat(root); 81080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFP N, D; 81180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 81280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // f' = 3*coeff[0]*T^2 + 2*coeff[1]*T + coeff[2] 81380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru D = SkFPMul(SkFPMul(coeff[0], SkFPMul(T,T)), 3); 81480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru D = SkFPAdd(D, SkFPMulInt(SkFPMul(coeff[1], T), 2)); 81580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru D = SkFPAdd(D, coeff[2]); 81680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 81780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (D == 0) 81880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return root; 81980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 82080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // f = coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3] 82180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru N = SkFPMul(SkFPMul(SkFPMul(T, T), T), coeff[0]); 82280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru N = SkFPAdd(N, SkFPMul(SkFPMul(T, T), coeff[1])); 82380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru N = SkFPAdd(N, SkFPMul(T, coeff[2])); 82480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru N = SkFPAdd(N, coeff[3]); 82580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 82680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (N) 82780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 82880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar delta = SkFPToScalar(SkFPDiv(N, D)); 82980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 83080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (delta) 83180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru root -= delta; 83280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 83380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return root; 83480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 83580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 83680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 83780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** 83880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Given an array and count, remove all pair-wise duplicates from the array, 83980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * keeping the existing sorting, and return the new count 84080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 84180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic int collaps_duplicates(float array[], int count) { 84280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int n = count; n > 1; --n) { 84380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (array[0] == array[1]) { 84480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 1; i < n; ++i) { 84580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru array[i - 1] = array[i]; 84680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 84780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru count -= 1; 84880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 84980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru array += 1; 85080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 85180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 85280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return count; 85380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 85480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 85580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_DEBUG 85680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 85780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define TEST_COLLAPS_ENTRY(array) array, SK_ARRAY_COUNT(array) 85880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 85980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic void test_collaps_duplicates() { 86080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static bool gOnce; 86180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (gOnce) { return; } 86280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru gOnce = true; 86380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const float src0[] = { 0 }; 86480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const float src1[] = { 0, 0 }; 86580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const float src2[] = { 0, 1 }; 86680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const float src3[] = { 0, 0, 0 }; 86780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const float src4[] = { 0, 0, 1 }; 86880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const float src5[] = { 0, 1, 1 }; 86980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const float src6[] = { 0, 1, 2 }; 87080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const struct { 87180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const float* fData; 87280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int fCount; 87380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int fCollapsedCount; 87480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } data[] = { 87580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { TEST_COLLAPS_ENTRY(src0), 1 }, 87680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { TEST_COLLAPS_ENTRY(src1), 1 }, 87780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { TEST_COLLAPS_ENTRY(src2), 2 }, 87880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { TEST_COLLAPS_ENTRY(src3), 1 }, 87980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { TEST_COLLAPS_ENTRY(src4), 2 }, 88080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { TEST_COLLAPS_ENTRY(src5), 2 }, 88180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { TEST_COLLAPS_ENTRY(src6), 3 }, 88280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 88380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (size_t i = 0; i < SK_ARRAY_COUNT(data); ++i) { 88480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru float dst[3]; 88580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(dst, data[i].fData, data[i].fCount * sizeof(dst[0])); 88680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count = collaps_duplicates(dst, data[i].fCount); 88780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(data[i].fCollapsedCount == count); 88880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int j = 1; j < count; ++j) { 88980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(dst[j-1] < dst[j]); 89080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 89180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 89280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 89380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 89480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 89580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#if defined _WIN32 && _MSC_VER >= 1300 && defined SK_SCALAR_IS_FIXED // disable warning : unreachable code if building fixed point for windows desktop 89680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#pragma warning ( disable : 4702 ) 89780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 89880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 89980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* Solve coeff(t) == 0, returning the number of roots that 90080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lie withing 0 < t < 1. 90180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3] 90280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 90380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Eliminates repeated roots (so that all tValues are distinct, and are always 90480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru in increasing order. 90580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 90680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic int solve_cubic_polynomial(const SkFP coeff[4], SkScalar tValues[3]) 90780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 90880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifndef SK_SCALAR_IS_FLOAT 90980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 0; // this is not yet implemented for software float 91080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 91180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 91280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (SkScalarNearlyZero(coeff[0])) // we're just a quadratic 91380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 91480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues); 91580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 91680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 91780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFP a, b, c, Q, R; 91880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 91980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 92080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(coeff[0] != 0); 92180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 92280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFP inva = SkFPInvert(coeff[0]); 92380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru a = SkFPMul(coeff[1], inva); 92480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru b = SkFPMul(coeff[2], inva); 92580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru c = SkFPMul(coeff[3], inva); 92680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 92780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Q = SkFPDivInt(SkFPSub(SkFPMul(a,a), SkFPMulInt(b, 3)), 9); 92880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// R = (2*a*a*a - 9*a*b + 27*c) / 54; 92980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru R = SkFPMulInt(SkFPMul(SkFPMul(a, a), a), 2); 93080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru R = SkFPSub(R, SkFPMulInt(SkFPMul(a, b), 9)); 93180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru R = SkFPAdd(R, SkFPMulInt(c, 27)); 93280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru R = SkFPDivInt(R, 54); 93380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 93480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFP Q3 = SkFPMul(SkFPMul(Q, Q), Q); 93580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFP R2MinusQ3 = SkFPSub(SkFPMul(R,R), Q3); 93680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFP adiv3 = SkFPDivInt(a, 3); 93780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 93880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar* roots = tValues; 93980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar r; 94080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 94180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (SkFPLT(R2MinusQ3, 0)) // we have 3 real roots 94280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 94380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_SCALAR_IS_FLOAT 94480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru float theta = sk_float_acos(R / sk_float_sqrt(Q3)); 94580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru float neg2RootQ = -2 * sk_float_sqrt(Q); 94680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 94780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru r = neg2RootQ * sk_float_cos(theta/3) - adiv3; 94880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (is_unit_interval(r)) 94980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *roots++ = r; 95080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 95180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru r = neg2RootQ * sk_float_cos((theta + 2*SK_ScalarPI)/3) - adiv3; 95280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (is_unit_interval(r)) 95380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *roots++ = r; 95480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 95580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru r = neg2RootQ * sk_float_cos((theta - 2*SK_ScalarPI)/3) - adiv3; 95680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (is_unit_interval(r)) 95780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *roots++ = r; 95880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 95980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDEBUGCODE(test_collaps_duplicates();) 96080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 96180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // now sort the roots 96280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count = (int)(roots - tValues); 96380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT((unsigned)count <= 3); 96480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bubble_sort(tValues, count); 96580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru count = collaps_duplicates(tValues, count); 96680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru roots = tValues + count; // so we compute the proper count below 96780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 96880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 96980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else // we have 1 real root 97080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 97180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFP A = SkFPAdd(SkFPAbs(R), SkFPSqrt(R2MinusQ3)); 97280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru A = SkFPCubeRoot(A); 97380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (SkFPGT(R, 0)) 97480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru A = SkFPNeg(A); 97580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 97680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (A != 0) 97780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru A = SkFPAdd(A, SkFPDiv(Q, A)); 97880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru r = SkFPToScalar(SkFPSub(A, adiv3)); 97980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (is_unit_interval(r)) 98080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *roots++ = r; 98180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 98280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 98380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return (int)(roots - tValues); 98480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 98580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 98680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* Looking for F' dot F'' == 0 98780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 98880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru A = b - a 98980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru B = c - 2b + a 99080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru C = d - 3c + 3b - a 99180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 99280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru F' = 3Ct^2 + 6Bt + 3A 99380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru F'' = 6Ct + 6B 99480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 99580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 99680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 99780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic void formulate_F1DotF2(const SkScalar src[], SkFP coeff[4]) 99880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 99980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar a = src[2] - src[0]; 100080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar b = src[4] - 2 * src[2] + src[0]; 100180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar c = src[6] + 3 * (src[2] - src[4]) - src[0]; 100280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 100380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFP A = SkScalarToFP(a); 100480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFP B = SkScalarToFP(b); 100580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFP C = SkScalarToFP(c); 100680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 100780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru coeff[0] = SkFPMul(C, C); 100880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru coeff[1] = SkFPMulInt(SkFPMul(B, C), 3); 100980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru coeff[2] = SkFPMulInt(SkFPMul(B, B), 2); 101080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru coeff[2] = SkFPAdd(coeff[2], SkFPMul(C, A)); 101180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru coeff[3] = SkFPMul(A, B); 101280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 101380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 101480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// EXPERIMENTAL: can set this to zero to accept all t-values 0 < t < 1 101580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru//#define kMinTValueForChopping (SK_Scalar1 / 256) 101680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define kMinTValueForChopping 0 101780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 101880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* Looking for F' dot F'' == 0 101980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 102080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru A = b - a 102180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru B = c - 2b + a 102280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru C = d - 3c + 3b - a 102380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 102480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru F' = 3Ct^2 + 6Bt + 3A 102580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru F'' = 6Ct + 6B 102680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 102780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 102880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 102980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]) 103080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 103180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFP coeffX[4], coeffY[4]; 103280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int i; 103380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 103480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru formulate_F1DotF2(&src[0].fX, coeffX); 103580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru formulate_F1DotF2(&src[0].fY, coeffY); 103680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 103780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (i = 0; i < 4; i++) 103880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru coeffX[i] = SkFPAdd(coeffX[i],coeffY[i]); 103980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 104080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar t[3]; 104180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count = solve_cubic_polynomial(coeffX, t); 104280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int maxCount = 0; 104380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 104480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // now remove extrema where the curvature is zero (mins) 104580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // !!!! need a test for this !!!! 104680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (i = 0; i < count; i++) 104780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 104880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if (not_min_curvature()) 104980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (t[i] > kMinTValueForChopping && t[i] < SK_Scalar1 - kMinTValueForChopping) 105080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tValues[maxCount++] = t[i]; 105180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 105280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return maxCount; 105380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 105480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 105580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], SkScalar tValues[3]) 105680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 105780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar t_storage[3]; 105880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 105980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (tValues == NULL) 106080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tValues = t_storage; 106180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 106280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count = SkFindCubicMaxCurvature(src, tValues); 106380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 106480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (dst) 106580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 106680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (count == 0) 106780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(dst, src, 4 * sizeof(SkPoint)); 106880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 106980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopCubicAt(src, dst, tValues, count); 107080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 107180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return count + 1; 107280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 107380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 107480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querubool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous) { 107580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (ambiguous) { 107680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ambiguous = false; 107780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 107880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 107980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Find the minimum and maximum y of the extrema, which are the 108080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // first and last points since this cubic is monotonic 108180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar min_y = SkMinScalar(cubic[0].fY, cubic[3].fY); 108280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar max_y = SkMaxScalar(cubic[0].fY, cubic[3].fY); 108380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 108480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt.fY == cubic[0].fY 108580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru || pt.fY < min_y 108680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru || pt.fY > max_y) { 108780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // The query line definitely does not cross the curve 108880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (ambiguous) { 108980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ambiguous = (pt.fY == cubic[0].fY); 109080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 109180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 109280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 109380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 109480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool pt_at_extremum = (pt.fY == cubic[3].fY); 109580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 109680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar min_x = 109780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkMinScalar( 109880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkMinScalar( 109980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkMinScalar(cubic[0].fX, cubic[1].fX), 110080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru cubic[2].fX), 110180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru cubic[3].fX); 110280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt.fX < min_x) { 110380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // The query line definitely crosses the curve 110480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (ambiguous) { 110580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ambiguous = pt_at_extremum; 110680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 110780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 110880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 110980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 111080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar max_x = 111180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkMaxScalar( 111280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkMaxScalar( 111380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkMaxScalar(cubic[0].fX, cubic[1].fX), 111480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru cubic[2].fX), 111580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru cubic[3].fX); 111680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt.fX > max_x) { 111780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // The query line definitely does not cross the curve 111880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 111980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 112080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 112180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Do a binary search to find the parameter value which makes y as 112280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // close as possible to the query point. See whether the query 112380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // line's origin is to the left of the associated x coordinate. 112480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 112580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // kMaxIter is chosen as the number of mantissa bits for a float, 112680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // since there's no way we are going to get more precision by 112780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // iterating more times than that. 112880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const int kMaxIter = 23; 112980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint eval; 113080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int iter = 0; 113180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar upper_t; 113280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar lower_t; 113380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Need to invert direction of t parameter if cubic goes up 113480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // instead of down 113580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (cubic[3].fY > cubic[0].fY) { 113680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru upper_t = SK_Scalar1; 113780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lower_t = SkFloatToScalar(0); 113880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 113980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru upper_t = SkFloatToScalar(0); 114080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lower_t = SK_Scalar1; 114180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 114280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru do { 114380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar t = SkScalarAve(upper_t, lower_t); 114480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkEvalCubicAt(cubic, t, &eval, NULL, NULL); 114580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt.fY > eval.fY) { 114680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lower_t = t; 114780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 114880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru upper_t = t; 114980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 115080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } while (++iter < kMaxIter 115180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru && !SkScalarNearlyZero(eval.fY - pt.fY)); 115280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pt.fX <= eval.fX) { 115380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (ambiguous) { 115480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ambiguous = pt_at_extremum; 115580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 115680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 115780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 115880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 115980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 116080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 116180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous) { 116280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int num_crossings = 0; 116380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint monotonic_cubics[10]; 116480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int num_monotonic_cubics = SkChopCubicAtYExtrema(cubic, monotonic_cubics); 116580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (ambiguous) { 116680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ambiguous = false; 116780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 116880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool locally_ambiguous; 116980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[0], &locally_ambiguous)) 117080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ++num_crossings; 117180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (ambiguous) { 117280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ambiguous |= locally_ambiguous; 117380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 117480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (num_monotonic_cubics > 0) 117580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[3], &locally_ambiguous)) 117680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ++num_crossings; 117780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (ambiguous) { 117880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ambiguous |= locally_ambiguous; 117980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 118080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (num_monotonic_cubics > 1) 118180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[6], &locally_ambiguous)) 118280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ++num_crossings; 118380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (ambiguous) { 118480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ambiguous |= locally_ambiguous; 118580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 118680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return num_crossings; 118780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 118880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 118980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru//////////////////////////////////////////////////////////////////////////////// 119080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 119180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* Find t value for quadratic [a, b, c] = d. 119280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Return 0 if there is no solution within [0, 1) 119380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 119480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic SkScalar quad_solve(SkScalar a, SkScalar b, SkScalar c, SkScalar d) 119580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 119680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // At^2 + Bt + C = d 119780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar A = a - 2 * b + c; 119880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar B = 2 * (b - a); 119980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar C = a - d; 120080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 120180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar roots[2]; 120280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count = SkFindUnitQuadRoots(A, B, C, roots); 120380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 120480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(count <= 1); 120580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return count == 1 ? roots[0] : 0; 120680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 120780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 120880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* given a quad-curve and a point (x,y), chop the quad at that point and return 120980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru the new quad's offCurve point. Should only return false if the computed pos 121080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru is the start of the curve (i.e. root == 0) 121180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 121280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic bool quad_pt2OffCurve(const SkPoint quad[3], SkScalar x, SkScalar y, SkPoint* offCurve) 121380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 121480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const SkScalar* base; 121580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar value; 121680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 121780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (SkScalarAbs(x) < SkScalarAbs(y)) { 121880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru base = &quad[0].fX; 121980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru value = x; 122080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 122180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru base = &quad[0].fY; 122280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru value = y; 122380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 122480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 122580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // note: this returns 0 if it thinks value is out of range, meaning the 122680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // root might return something outside of [0, 1) 122780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar t = quad_solve(base[0], base[2], base[4], value); 122880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 122980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (t > 0) 123080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 123180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint tmp[5]; 123280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopQuadAt(quad, tmp, t); 123380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *offCurve = tmp[1]; 123480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 123580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 123680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /* t == 0 means either the value triggered a root outside of [0, 1) 123780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru For our purposes, we can ignore the <= 0 roots, but we want to 123880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru catch the >= 1 roots (which given our caller, will basically mean 123980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru a root of 1, give-or-take numerical instability). If we are in the 124080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru >= 1 case, return the existing offCurve point. 124180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 124280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru The test below checks to see if we are close to the "end" of the 124380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru curve (near base[4]). Rather than specifying a tolerance, I just 124480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru check to see if value is on to the right/left of the middle point 124580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru (depending on the direction/sign of the end points). 124680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 124780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if ((base[0] < base[4] && value > base[2]) || 124880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru (base[0] > base[4] && value < base[2])) // should root have been 1 124980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 125080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *offCurve = quad[1]; 125180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 125280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 125380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 125480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 125580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 125680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1257363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger#ifdef SK_SCALAR_IS_FLOAT 1258363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger// Due to floating point issues (i.e., 1.0f - SK_ScalarRoot2Over2 != 1259363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger// SK_ScalarRoot2Over2 - SK_ScalarTanPIOver8) a cruder root2over2 1260363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger// approximation is required to make the quad circle points convex. The 1261363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger// root of the problem is that with the root2over2 value in SkScalar.h 1262363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger// the arcs really are ever so slightly concave. Some alternative fixes 1263363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger// to this problem (besides just arbitrarily pushing out the mid-point as 1264363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger// is done here) are: 1265363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger// Adjust all the points (not just the middle) to both better approximate 1266363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger// the curve and remain convex 1267363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger// Switch over to using cubics rather then quads 1268363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger// Use a different method to create the mid-point (e.g., compute 1269363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger// the two side points, average them, then move it out as needed 1270d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger#ifndef SK_IGNORE_CONVEX_QUAD_OPT 1271363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger #define SK_ScalarRoot2Over2_QuadCircle 0.7072f 1272363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger#else 1273363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger #define SK_ScalarRoot2Over2_QuadCircle SK_ScalarRoot2Over2 1274363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger#endif 1275363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 1276363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger#else 1277363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger #define SK_ScalarRoot2Over2_QuadCircle SK_FixedRoot2Over2 1278363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger#endif 1279363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 1280363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 128180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic const SkPoint gQuadCirclePts[kSkBuildQuadArcStorage] = { 1282363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { SK_Scalar1, 0 }, 1283363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { SK_Scalar1, SK_ScalarTanPIOver8 }, 1284363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { SK_ScalarRoot2Over2_QuadCircle, SK_ScalarRoot2Over2_QuadCircle }, 1285363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { SK_ScalarTanPIOver8, SK_Scalar1 }, 1286363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 1287363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { 0, SK_Scalar1 }, 1288363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { -SK_ScalarTanPIOver8, SK_Scalar1 }, 1289363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { -SK_ScalarRoot2Over2_QuadCircle, SK_ScalarRoot2Over2_QuadCircle }, 1290363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { -SK_Scalar1, SK_ScalarTanPIOver8 }, 1291363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 1292363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { -SK_Scalar1, 0 }, 1293363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { -SK_Scalar1, -SK_ScalarTanPIOver8 }, 1294363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { -SK_ScalarRoot2Over2_QuadCircle, -SK_ScalarRoot2Over2_QuadCircle }, 1295363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { -SK_ScalarTanPIOver8, -SK_Scalar1 }, 1296363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 1297363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { 0, -SK_Scalar1 }, 1298363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { SK_ScalarTanPIOver8, -SK_Scalar1 }, 1299363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { SK_ScalarRoot2Over2_QuadCircle, -SK_ScalarRoot2Over2_QuadCircle }, 1300363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { SK_Scalar1, -SK_ScalarTanPIOver8 }, 1301363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger 1302363e546ed626b6dbbc42f5db87b3594bc0b5944bDerek Sollenberger { SK_Scalar1, 0 } 130380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 130480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 130580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkBuildQuadArc(const SkVector& uStart, const SkVector& uStop, 130680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRotationDirection dir, const SkMatrix* userMatrix, 130780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint quadPoints[]) 130880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 130980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // rotate by x,y so that uStart is (1.0) 131080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar x = SkPoint::DotProduct(uStart, uStop); 131180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar y = SkPoint::CrossProduct(uStart, uStop); 131280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 131380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar absX = SkScalarAbs(x); 131480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar absY = SkScalarAbs(y); 131580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 131680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int pointCount; 131780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 131880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // check for (effectively) coincident vectors 131980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // this can happen if our angle is nearly 0 or nearly 180 (y == 0) 132080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // ... we use the dot-prod to distinguish between 0 and 180 (x > 0) 132180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (absY <= SK_ScalarNearlyZero && x > 0 && 132280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ((y >= 0 && kCW_SkRotationDirection == dir) || 132380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru (y <= 0 && kCCW_SkRotationDirection == dir))) { 132480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 132580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // just return the start-point 132680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru quadPoints[0].set(SK_Scalar1, 0); 132780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pointCount = 1; 132880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 132980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (dir == kCCW_SkRotationDirection) 133080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru y = -y; 133180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 133280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // what octant (quadratic curve) is [xy] in? 133380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int oct = 0; 133480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool sameSign = true; 133580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 133680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (0 == y) 133780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 133880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru oct = 4; // 180 133980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero); 134080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 134180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else if (0 == x) 134280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 134380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero); 134480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (y > 0) 134580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru oct = 2; // 90 134680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 134780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru oct = 6; // 270 134880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 134980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 135080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 135180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (y < 0) 135280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru oct += 4; 135380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if ((x < 0) != (y < 0)) 135480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 135580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru oct += 2; 135680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru sameSign = false; 135780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 135880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if ((absX < absY) == sameSign) 135980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru oct += 1; 136080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 136180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 136280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int wholeCount = oct << 1; 136380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(quadPoints, gQuadCirclePts, (wholeCount + 1) * sizeof(SkPoint)); 136480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 136580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const SkPoint* arc = &gQuadCirclePts[wholeCount]; 136680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (quad_pt2OffCurve(arc, x, y, &quadPoints[wholeCount + 1])) 136780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 136880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru quadPoints[wholeCount + 2].set(x, y); 136980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru wholeCount += 2; 137080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 137180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pointCount = wholeCount + 1; 137280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 137380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 137480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // now handle counter-clockwise and the initial unitStart rotation 137580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkMatrix matrix; 137680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru matrix.setSinCos(uStart.fY, uStart.fX); 137780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (dir == kCCW_SkRotationDirection) { 137880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru matrix.preScale(SK_Scalar1, -SK_Scalar1); 137980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 138080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (userMatrix) { 138180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru matrix.postConcat(*userMatrix); 138280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 138380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru matrix.mapPoints(quadPoints, pointCount); 138480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return pointCount; 138580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 1386