Tuesday, June 16, 2009

How to calculate Bezier curves' bounding box

Hi, it is NISHIO Hirokazu. Today I wanted to make a lot of Bezier curves same size. And I got it.

Here is what I want to draw:


To calculate bounding box of cubic Bezier seems easy, especially you know its parametric form. See B├ęzier curve - Wikipedia, the free encyclopedia

However, there are some pitfall. The derivative of Bezier equation is usually quadratic equation but not always. Solutions of the derivative may out of range, etc.

I publish following source code under MIT License. Feel free to use it.

def calc_box(start, curves):
P0 = start
bounds = [[P0[0]], [P0[1]]]

for c in curves:
P1, P2, P3 = (
(c[0], c[1]),
(c[2], c[3]),
(c[4], c[5]))

bounds[0].append(P3[0])
bounds[1].append(P3[1])

for i in [0, 1]:
f = lambda t: (
(1-t)**3 * P0[i]
+ 3 * (1-t)**2 * t * P1[i]
+ 3 * (1-t) * t**2 * P2[i]
+ t**3 * P3[i])

b = 6 * P0[i] - 12 * P1[i] + 6 * P2[i]
a = -3 * P0[i] + 9 * P1[i] - 9 * P2[i] + 3 * P3[i]
c = 3 * P1[i] - 3 * P0[i]

if a == 0:
if b == 0:
continue
t = -c / b
if 0 < t < 1:
bounds[i].append(f(t))
continue

b2ac = b ** 2 - 4 * c * a
if b2ac < 0:
continue
t1 = (-b + sqrt(b2ac))/(2 * a)
if 0 < t1 < 1: bounds[i].append(f(t1))
t2 = (-b - sqrt(b2ac))/(2 * a)
if 0 < t2 < 1: bounds[i].append(f(t2))

P0 = P3

x = min(bounds[0])
w = max(bounds[0]) - x
y = min(bounds[1])
h = max(bounds[1]) - y
return (x, y, w, h)



Blaze Boy asked me about the structure, thank you. for each c in curves is 6-tuples: P1, P2, P3 = ((c[0], c[1]), (c[2], c[3]), (c[4], c[5])) P0 and P3 are terminal points of each bezier curves.

No comments: