Skip to content

Instantly share code, notes, and snippets.

@bcse
Last active December 23, 2015 21:29
Show Gist options
  • Save bcse/6696208 to your computer and use it in GitHub Desktop.
Save bcse/6696208 to your computer and use it in GitHub Desktop.
Python port of WebKit bezier solver
# 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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment