# Re: Bezier Bounding Box

*From*: Just d' FAQs <nobody-here@xxxxxxx>*Date*: Wed, 13 Jul 2005 02:16:10 -0500

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.

.

**References**:**Bezier Bounding Box***From:*283587133 Alexander Materukhin

- Prev by Date:
**Re: Query on distance between 2D line segments** - Next by Date:
**Re: Closest point on 2D triangle from 2D point** - Previous by thread:
**Bezier Bounding Box** - Next by thread:
**finding a word** - Index(es):