College Math Teaching

March 9, 2014

Bézier Curves

I am currently teaching Numerical Analysis and using Burden-Faires. The book covers the topics we like, but I feel that the section on splines and parametrized curves is a bit weak; in particular the discussion on Bézier curves is a bit lacking. The pity: the discussion need not be all that deep, and the standard equation for Bézier curves is actually easy to remember.

Also: where the text talks about how the Bézier curve equations differs from the “bare handed parametric cubic spline” that they derive, they don’t explain the reason for the difference.

So, I decided to write these notes. I will have to explain some basic concepts.

The setting: $R^n$ with the usual geometry induced by the usual “dot product”.

Convex Sets in $R^n$

A set $X \subset R^n$ is said to be convex if for any two points $x, y \in X$, the straight line segment connecting $x$ to $y$ is also in $X$; that is, the set $tx + (1-t)y \in X$ for all $t \in [0,1]$.

Convex Hull for a set of points

Now suppose one is given a collection of points $C= x_0, x_1, x_2, x_3,.... \in R^n$. The convex hull $H$ for $C$ is the smallest convex set which contains all of $C$. That is, if $Y$ is any convex set that contains $C$, then $H \subseteq Y$. In the case where the set of points is finite (say, $C = \{x_0, x_1, x_2, ....x_n \} )$ then $H$ consists the set of all $\sum^{n}_{i = 0} \alpha_i x_i$ where $\alpha_i \ge 0$ and $\sum^{n}_{i=0} \alpha_i = 1$.

Note: the convex hull for a set of points is, in general, an example of a vector subset that is NOT a vector subspace.

Binomial Theorem and the Bernstein coefficient polynomials

Recall from algebra: if $n$ is a positive integer and $a, b$ numbers (real, complex, or even arbitrary field elements), $(a+b)^n = \sum^{n}_{j =0} { n \choose j} a^{n-j} b^{j}$, where ${n \choose j} = \frac{n!}{(n-j)! j !}$. For example, $(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3$.

Now consider the rather silly looking: $1^n = ((1-t) + t)^n = \sum^n_{j=0}{ n \choose j} (1-t)^{n-j} t^{j}$ Note that this expression is equal to 1 for ALL values of $t$ and that for $t \in [0,1]$, each summand ${ n \choose j} (1-t)^{n-j} t^{j}$ is positive or zero.

These “coefficient polynomials” ${ n \choose j} (1-t)^{n-j} t^{j}$ are called the Bernstein polynomials (or Bernstein basis polynomials) and we denote them as follows: $b_{j,n}(t) = { n \choose j} (1-t)^{n-j} t^{j}$. We now see that for all $t \in [0,1], 0 \le b_{j,n}(t) \le 1$ and $\sum^n_{j=0}b_{j,n}(t) = ((1-t)+t)^n =1^n =1$

Definition of a Bézier curve and some of its properties

Now let $P_0, P_1, P_2, ...P_n$ be a collection of distinct points in $R^k$. One can think of these points as vectors.
The Bézier curve with control points $P_0, P_1, P_2, ...P_n$ is defined to be $B(t)= \sum^n_{j=0}b_{j,n}(t)P_j, t \in [0,1]$.

Properties

$B(0) = P_0, B(1) =P_n$. This is clear because $b_{0,n}(0) = 1, b_{n,n}(1) =1$ and for $i \notin \{0,1\}, b_{i,n}(0)=b_{i,n}(1) = 0$.

The polygon formed by $P_0, P_1, ....P_n$ is called the control polygon for the Bézier curve.

For all $t \in [0,1], B(t)$ is in the convex hull of $P_0, P_1, ...P_n$. This is clear because $\sum^n_{j=0}b_{j,n}(t) = ((1-t)+t)^n =1^n =1$ and each $b_{i,n}(t)$ is positive.

“Guideposts”: the text talks about the “guideposts”: the text looks at a cubic Bézier curve in the plane and uses $(x_0, y_0) =P_0, (x_0+ \alpha_0, y_0 + \beta_0) = P_1, (x_1 - \alpha_1, y_1 - \beta_1)= P_2, (x_1, y_1) =P_3$

Now $P_1$ and $P_{n-1}$ directly affect the (one sided) tangent to the Bézier curve at $t=0, t=1$. In fact we will show that if we use the one-sided parametric curve derivative, we see that $B'(0) = n(P_1 - P_0), B'(1) = n(P_n - P_{n-1})$. The text calls $n$ the scaling factor and notes that the scaling factor is 3 when $n = 3$.

We’ll do the calculations for $B'(0), B'(1)$ for the general degree $n$ Bézier curve using elementary calculus (product rule):

First write $B(t) = (1-t)^nP_0 + n(1-t)^{n-1}tP_1 + \sum^{n-2}_{j=2} b_{j,n}(t) P_j + n(1-t)t^{n-1}P_{n-1} + t^n P_n$. Now take the derivative and we see:
$B'(t) = -n(1-t)^{n-1}P_0 + (n(1-t)^{n-1} - n(n-1)(1-t)^{n-2}t)P_1 + \frac{d}{dt} (\sum^{n-2}_{j=2} b_{j,n}(t) P_j) +(n(n-1)(1-t)t^{n-2}-nt^{n-1})P_{n-1} + nt^{n-1}P_n$

Key observation: every term of $\frac{d}{dt} (\sum^{n-2}_{j=2} b_{j,n}(t) P_j)$ has both a factor of $t$ and $(1-t)$ in it; hence this middle term evaluates to zero when $t \in {0,1}$ and is therefor irrelevant to the calculation of $B'(0)$ and $B'(1)$.

So $B'(0) = -nP_0 + nP_1 = n(P_1 - P_0)$ (the last two terms are zero at $t =0$ and $B'(1) = -nP_{n-1} + nP_n = n(P_n - P_{n-1})$ (the first two terms are zero at $t = 1$ ).

It follows that the DIRECTION of the (one sided) tangents at the ends of the Bézier curve depends only on the unit tangent vectors in the direction of $P_1 - P_0, P_n - P_{n-1}$ respectively. Of course, the tangent vector has a magnitude (norm) as well, and that certainly affects the curve.

Here are some examples of Bézier cubic curves: the points with the open circles are $P_0, P_3$ and the points that are filled in with gray are the control points $P_1, P_2$. The last curve is two Bézier cubics joined together.

Software
The software that I provided writes the cubic Bézier curve as a “conventional” cubic in $x, y$ coordinates: $B_{x}(t) = a_3t^3 + a_2t^2 + a_1t + a_0$ and $B_{y} = b_3t^3 + b_2t^2 + b_1t + b_0$.

1 Comment »

1. […] You can find it here. […]

Pingback by My main post of the evening… « blueollie — March 9, 2014 @ 11:45 pm