Re: Bezier Bounding Box



On Wed, 13 Jul 2005 10:21:40 +0600, "283587133 Alexander Materukhin"
<felix@xxxxxxxxxxxxxxx> wrote:
>Please, help me to determine 2D Bezier spline AABB and Point-in-Bezier
>algorithms.
>All I can do now is "flatten" bezier then test trivial polygon. Have you any
>"direct" methods?

Both the x coordinate and the y coordinate are polynomial. Newton told
us that at a maximum or minimum the derivative will be zero. Take all
those points, and take the ends; their AABB will be that of the curve.

EXAMPLE
Consider the cubic Bezier curve with control points

(0,0) (6,2) (-1,4) (1,1)

Taken as Bernstein basis coefficints, this is equivalent to these:

x(t) = 0*[(1-t)^3] + 6*[3(1-t)^2 t] + (-1)*[3(1-t) t^2] + 1*[t^3]
= 18t -39t^2 + 22t^3
y(t) = 0*[(1-t)^3] + 2*[3(1-t)^2 t] + 4*[3(1-t) t^2] + 1*[t^3]
= 6t - 5t^3

The derivative of x with respect to t is zero at approximately

t2 = 0.31442
t3 = 0.867398

The derivative of y with respect to t is zero at approximately

t4 = -0.632456
t5 = 0.632456

The zero at t3 is not part of the curve, so we discard it. We add the
ends, t0 = 0 and t1 = 1. Now we evaluate the curve at these five t
values and take the bounds.

t0 |--> (0,0) (first control point)
t1 |--> (1,1) (last control point)
t2 |--> (2.49,1.73)
t3 |--> (0.63,1.94)
t5 |--> (1.35,2.53)

So the bounds are

min x = 0
max x = 2.49
min y = 0
max y = 2.53

COMMENT
We have a helpful trick for the derivatives: use the curve defined by
differences of successive control points. For our example, we have

(6,2) (-7,2) (2,-3)

This is a quadratic Bezier curve, giving x and y functions:

x'(t)/3 = 6*[(1-t)^2] + (-7)*[2(1-t) t] + 2*[t^2]
= 6 - 26t + 22t^2
y'(t)/3 = 2*[(1-t)^2] + 2*[2(1-t) t] + (-3)*[t^2]
= 2 - 5t^2

For finding zeros the factor of 3 can be ignored.

.