/* * Copyright (C) 2008 Apple Inc. All Rights Reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef UnitBezier_h #define UnitBezier_h #include namespace WebCore { struct UnitBezier { UnitBezier(double p1x, double p1y, double p2x, double p2y) { // Calculate the polynomial coefficients, implicit first and last control points are (0,0) and (1,1). cx = 3.0 * p1x; bx = 3.0 * (p2x - p1x) - cx; ax = 1.0 - cx -bx; cy = 3.0 * p1y; by = 3.0 * (p2y - p1y) - cy; ay = 1.0 - cy - by; } double sampleCurveX(double t) { // `ax t^3 + bx t^2 + cx t' expanded using Horner's rule. return ((ax * t + bx) * t + cx) * t; } double sampleCurveY(double t) { return ((ay * t + by) * t + cy) * t; } double sampleCurveDerivativeX(double t) { return (3.0 * ax * t + 2.0 * bx) * t + cx; } // Given an x value, find a parametric value it came from. double solveCurveX(double x, double epsilon) { double t0; double t1; double t2; double x2; double d2; int i; // First try a few iterations of Newton's method -- normally very fast. for (t2 = x, i = 0; i < 8; i++) { x2 = sampleCurveX(t2) - x; if (fabs (x2) < epsilon) return t2; d2 = sampleCurveDerivativeX(t2); if (fabs(d2) < 1e-6) break; t2 = t2 - x2 / d2; } // Fall back to the bisection method for reliability. t0 = 0.0; t1 = 1.0; t2 = x; if (t2 < t0) return t0; if (t2 > t1) return t1; while (t0 < t1) { x2 = sampleCurveX(t2); if (fabs(x2 - x) < epsilon) return t2; if (x > x2) t0 = t2; else t1 = t2; t2 = (t1 - t0) * .5 + t0; } // Failure. return t2; } double solve(double x, double epsilon) { return sampleCurveY(solveCurveX(x, epsilon)); } private: double ax; double bx; double cx; double ay; double by; double cy; }; } #endif