Python port of WebKit bezier solver

UnitBezier.py

# Copyright (C) 2008 Apple Inc. All Rights Reserved.
# Copyright (C) 2013 Grey Lee. 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 THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 THE COPYRIGHT OWNER 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.


from math import fabs


# Ported from WebKit/Source/core/platform/graphics/UnitBezier.h
class UnitBezier(object):
    def __init__(self, p1x, p1y, p2x, p2y):
        # Calculate the polynomial coefficients, implicit first and last
        # control points are (0.0, 0.0) and (1.0, 1.0).
        self.cx = 3.0 * p1x
        self.bx = 3.0 * (p2x - p1x) - self.cx
        self.ax = 1.0 - self.cx -self.bx
        
        self.cy = 3.0 * p1y
        self.by = 3.0 * (p2y - p1y) - self.cy
        self.ay = 1.0 - self.cy - self.by
        
    def sampleCurveX(self, t):
        # `ax t^3 + bx t^2 + cx t' expanded using Horner's rule.
        return ((self.ax * t + self.bx) * t + self.cx) * t
        
    def sampleCurveY(self, t):
        return ((self.ay * t + self.by) * t + self.cy) * t

    def sampleCurveDerivativeX(self, t):
        return (3.0 * self.ax * t + 2.0 * self.bx) * t + self.cx

    def solveCurveX(self, x, epsilon):
        """Given an x value, find a parametric value it came from.
        """
        assert x >= 0.0
        assert x <= 1.0

        # First try a few iterations of Newton's method -- normally very fast.
        t2 = x
        for i in xrange(8):
            x2 = self.sampleCurveX(t2) - x
            if (fabs(x2) < epsilon):
                return t2
            d2 = self.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

        while t0 < t1:
            x2 = self.sampleCurveX(t2)
            if fabs(x2 - x) < epsilon:
                return t2;
            if x > x2:
                t0 = t2;
            else:
                t1 = t2;
            t2 = (t1 - t0) * 0.5 + t0

        # Failure.
        return t2

    def solve(self, x, epsilon):
        """Evaluates y at the given x. The epsilon parameter provides a hint as
        to the required accuracy and is not guaranteed.
        """
        if x < 0.0:
            return 0.0
        if x > 1.0:
            return 1.0
        return self.sampleCurveY(self.solveCurveX(x, epsilon))


# Ported from WebKit/Source/core/svg/SVGAnimationElement.cpp
def solveEpsilon(duration):
    return 1.0 / (200 * duration)
 
 
if __name__ == '__main__':
    import unittest

    # Ported from WebKit/Source/core/platform/graphics/UnitBezierTest.cpp
    class UnitBezierTestCase(unittest.TestCase):

        def testBasicUse(self):
            bezier = UnitBezier(0.5, 1.0, 0.5, 1.0)
            self.assertEqual(0.875, bezier.solve(0.5, 0.005))

        def testOvershoot(self):
            bezier = UnitBezier(0.5, 2.0, 0.5, 2.0)
            self.assertEqual(1.625, bezier.solve(0.5, 0.005))

        def testUndershoot(self):
            bezier = UnitBezier(0.5, -1.0, 0.5, -1.0)
            self.assertEqual(-0.625, bezier.solve(0.5, 0.005))

        def testInputAtEdgeOfRange(self):
            bezier = UnitBezier(0.5, 1.0, 0.5, 1.0)
            self.assertEqual(0.0, bezier.solve(0.0, 0.005))
            self.assertEqual(1.0, bezier.solve(1.0, 0.005))

        def testInputOutOfRange(self):
            bezier = UnitBezier(0.5, 1.0, 0.5, 1.0)
            self.assertEqual(0.0, bezier.solve(-1.0, 0.005))
            self.assertEqual(1.0, bezier.solve(2.0, 0.005))

        def testInputOutOfRangeLargeEpsilon(self):
            bezier = UnitBezier(0.5, 1.0, 0.5, 1.0)
            self.assertEqual(0.0, bezier.solve(-1.0, 1.0))
            self.assertEqual(1.0, bezier.solve(2.0, 1.0))

    unittest.main()