18e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 28e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Copyright (C) 2008 Apple Inc. All Rights Reserved. 38e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 48e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Redistribution and use in source and binary forms, with or without 58e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * modification, are permitted provided that the following conditions 68e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * are met: 78e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 1. Redistributions of source code must retain the above copyright 88e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * notice, this list of conditions and the following disclaimer. 98e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 2. Redistributions in binary form must reproduce the above copyright 108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * notice, this list of conditions and the following disclaimer in the 118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * documentation and/or other materials provided with the distribution. 128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR 178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project */ 258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef UnitBezier_h 278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define UnitBezier_h 288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include <math.h> 308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectnamespace WebCore { 328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project struct UnitBezier { 348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project UnitBezier(double p1x, double p1y, double p2x, double p2y) 358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Calculate the polynomial coefficients, implicit first and last control points are (0,0) and (1,1). 378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cx = 3.0 * p1x; 388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bx = 3.0 * (p2x - p1x) - cx; 398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ax = 1.0 - cx -bx; 408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cy = 3.0 * p1y; 428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project by = 3.0 * (p2y - p1y) - cy; 438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ay = 1.0 - cy - by; 448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double sampleCurveX(double t) 478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // `ax t^3 + bx t^2 + cx t' expanded using Horner's rule. 498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return ((ax * t + bx) * t + cx) * t; 508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double sampleCurveY(double t) 538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return ((ay * t + by) * t + cy) * t; 558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double sampleCurveDerivativeX(double t) 588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return (3.0 * ax * t + 2.0 * bx) * t + cx; 608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Given an x value, find a parametric value it came from. 638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double solveCurveX(double x, double epsilon) 648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double t0; 668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double t1; 678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double t2; 688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double x2; 698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double d2; 708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int i; 718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // First try a few iterations of Newton's method -- normally very fast. 738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (t2 = x, i = 0; i < 8; i++) { 748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project x2 = sampleCurveX(t2) - x; 758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (fabs (x2) < epsilon) 768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return t2; 778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project d2 = sampleCurveDerivativeX(t2); 788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (fabs(d2) < 1e-6) 798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project t2 = t2 - x2 / d2; 818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Fall back to the bisection method for reliability. 848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project t0 = 0.0; 858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project t1 = 1.0; 868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project t2 = x; 878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (t2 < t0) 898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return t0; 908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (t2 > t1) 918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return t1; 928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (t0 < t1) { 948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project x2 = sampleCurveX(t2); 958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (fabs(x2 - x) < epsilon) 968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return t2; 978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (x > x2) 988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project t0 = t2; 998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 1008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project t1 = t2; 1018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project t2 = (t1 - t0) * .5 + t0; 1028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Failure. 1058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return t2; 1068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double solve(double x, double epsilon) 1098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return sampleCurveY(solveCurveX(x, epsilon)); 1118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 1148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double ax; 1158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double bx; 1168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double cx; 1178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double ay; 1198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double by; 1208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project double cy; 1218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 1228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 1238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 124