15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/*
25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2008 Apple Inc. All Rights Reserved.
35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *
45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without
55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions
65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * are met:
75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1. Redistributions of source code must retain the above copyright
85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *    notice, this list of conditions and the following disclaimer.
95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2. Redistributions in binary form must reproduce the above copyright
105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *    notice, this list of conditions and the following disclaimer in the
115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *    documentation and/or other materials provided with the distribution.
125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *
135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */
2502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch
265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef UnitBezier_h
275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define UnitBezier_h
285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
291e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "platform/PlatformExport.h"
30f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)#include "wtf/Assertions.h"
315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include <math.h>
325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
33c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)namespace blink {
345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
35591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochstruct UnitBezier {
36591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    UnitBezier(double p1x, double p1y, double p2x, double p2y)
37591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    {
38591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        // Calculate the polynomial coefficients, implicit first and last control points are (0,0) and (1,1).
39591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        cx = 3.0 * p1x;
40591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        bx = 3.0 * (p2x - p1x) - cx;
41591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        ax = 1.0 - cx -bx;
42591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
43591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        cy = 3.0 * p1y;
44591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        by = 3.0 * (p2y - p1y) - cy;
45591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        ay = 1.0 - cy - by;
46f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
47f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        // End-point gradients are used to calculate timing function results
48f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        // outside the range [0, 1].
49f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        //
50f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        // There are three possibilities for the gradient at each end:
51f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        // (1) the closest control point is not horizontally coincident with regard to
52f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        //     (0, 0) or (1, 1). In this case the line between the end point and
53f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        //     the control point is tangent to the bezier at the end point.
54f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        // (2) the closest control point is coincident with the end point. In
55f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        //     this case the line between the end point and the far control
56f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        //     point is tangent to the bezier at the end point.
57f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        // (3) the closest control point is horizontally coincident with the end
58f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        //     point, but vertically distinct. In this case the gradient at the
59f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        //     end point is Infinite. However, this causes issues when
60f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        //     interpolating. As a result, we break down to a simple case of
61f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        //     0 gradient under these conditions.
62f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
63f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        if (p1x > 0)
64f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            m_startGradient = p1y / p1x;
65f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        else if (!p1y && p2x > 0)
66f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            m_startGradient = p2y / p2x;
67f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        else
68f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            m_startGradient = 0;
69f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
70f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        if (p2x < 1)
71f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            m_endGradient = (p2y - 1) / (p2x - 1);
72f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        else if (p2x == 1 && p1x < 1)
73f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            m_endGradient = (p1y - 1) / (p1x - 1);
74f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        else
75f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            m_endGradient = 0;
76591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    }
77591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
78591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    double sampleCurveX(double t)
79591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    {
80591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        // `ax t^3 + bx t^2 + cx t' expanded using Horner's rule.
81591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        return ((ax * t + bx) * t + cx) * t;
82591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    }
83591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
84591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    double sampleCurveY(double t)
85591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    {
86591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        return ((ay * t + by) * t + cy) * t;
87591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    }
88591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
89591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    double sampleCurveDerivativeX(double t)
90591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    {
91591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        return (3.0 * ax * t + 2.0 * bx) * t + cx;
92591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    }
93591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
94591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    // Given an x value, find a parametric value it came from.
95591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    double solveCurveX(double x, double epsilon)
96591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    {
97591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        ASSERT(x >= 0.0);
98591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        ASSERT(x <= 1.0);
99591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
100591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        double t0;
101591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        double t1;
102591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        double t2;
103591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        double x2;
104591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        double d2;
105591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        int i;
106591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
107591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        // First try a few iterations of Newton's method -- normally very fast.
108591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        for (t2 = x, i = 0; i < 8; i++) {
109591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch            x2 = sampleCurveX(t2) - x;
110591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch            if (fabs (x2) < epsilon)
111591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch                return t2;
112591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch            d2 = sampleCurveDerivativeX(t2);
113591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch            if (fabs(d2) < 1e-6)
114591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch                break;
115591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch            t2 = t2 - x2 / d2;
1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        }
1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
118591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        // Fall back to the bisection method for reliability.
119591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        t0 = 0.0;
120591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        t1 = 1.0;
121591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        t2 = x;
122591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
123591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        while (t0 < t1) {
124591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch            x2 = sampleCurveX(t2);
125591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch            if (fabs(x2 - x) < epsilon)
126591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch                return t2;
127591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch            if (x > x2)
128591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch                t0 = t2;
129591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch            else
130591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch                t1 = t2;
131591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch            t2 = (t1 - t0) * .5 + t0;
1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)        }
133591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
134591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        // Failure.
135591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        return t2;
136591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    }
137591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
138591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    // Evaluates y at the given x. The epsilon parameter provides a hint as to the required
139591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    // accuracy and is not guaranteed.
140591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    double solve(double x, double epsilon)
141591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    {
142591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        if (x < 0.0)
143f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            return 0.0 + m_startGradient * x;
144591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        if (x > 1.0)
145f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            return 1.0 + m_endGradient * (x - 1.0);
146591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        return sampleCurveY(solveCurveX(x, epsilon));
147591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    }
148591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
149591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochprivate:
150591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    double ax;
151591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    double bx;
152591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    double cx;
153591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
154591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    double ay;
155591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    double by;
156591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    double cy;
157f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
158f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    double m_startGradient;
159f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    double m_endGradient;
160591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch};
161591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
162c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)} // namespace blink
163591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
164591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#endif // UnitBezier_h
165