Your browser (Internet Explorer 6) is out of date. It has known security flaws and may not display all features of this and other websites. Learn how to update your browser.
X
Degree Reduction of Bezier Curves

Degree Reduction of Bezier Curves

Continuing with my reading efforts in Curves and Surfaces for GACD by Gerald Farin, I will talk today about a topic that comes up in chapter 6: elevating and reducing the degree of a Bézier curve.

Elevating the dimensionality

First, we start out by proving that the degree of a Bézier curve can always be elevated without the curve being changed.

A curve $$\vec{x}(t)$$ with the control polygon $$B = {\vec{b}_0, \ldots, \vec{b}_n}$$ can be represented as a Bézier curve using the Bernstein Polynomials $$B_i^n$$ as basis:

\begin{equation*}\vec{x}(t) = \sum_{i=0}^{n} \vec{b}_i B_i^n(t)\end{equation*}

We will now prove that we can increase the degree from $$n$$ to $$n+1$$ and still keep the same curve, given we choose then new control polygon accordingly.

We start out by rewriting $$\vec{x}(t)$$ as

\begin{eqnarray*}\vec{x}(t) &=& (1-t) \vec{x}(t) + t \vec{x}(t) \\ &=& \sum_{i=0}^n (1-t) \vec{b}_i B_i^n (t) + \sum_{i=0}^n t \vec{b}_i B_i^n (t)\end{eqnarray*}

And now we show that the terms can be rewritten as a sum from 0 to n+1. Let's start with the first term:

\begin{eqnarray*}(1-t) B_i^n (t) &=& (1-t) \frac{n!}{(n-i)! i!} t^i (1-t)^{n-i} \\ &=& \frac{n + 1 - i}{n + 1} \frac{(n+1)!}{(n+1 -i)! i!} t^i (1-t)^{(n+1)-i} \\ &=& \frac{n+1 - i}{n+1} B_i^{n+1}(t)\end{eqnarray*}

Easy. Now the second one

\begin{eqnarray*}t B_i^n(t) &=& t \frac{n!}{(n-i)! i!} t^i (1-t)^{n-i} \\ &=& \frac{i+1}{n+1} \frac{(n+1)!}{(n+1)!(i+1)!} t^{i+1} (1-t)^{n-i} \\ &=& \frac{i+1}{n+1} B_{i+1}^{n+1} (t)\end{eqnarray*}

Now, we plug this into the summation formula. We can readjust the summation variables cleverly by noting that we only add 0 terms and we get the formula:

\begin{eqnarray*}\vec{x}(t) &=& \sum_{i=0}^{n+1} \frac{n+1-i}{n+1} \vec{b}_i B_i^{n+1} (t) + \sum_{i=0}^{n+1} \frac{i}{n+1} \vec{b}_{i-1} B_i^{n+1} (t) \\ &=& \sum_{i=0}^{n+1} \Big( \big(1 - \frac{i}{n+1}\big) b_i + \frac{i}{n+1} b_{i-1}) \Big) B_i^{n+1} (t)\end{eqnarray*}

Now all there is to do is to compare the coefficients for old control polygon points and new polygon points and we have our solution: the new points are linear interpolations of the old ones. We can find the new points $$\vec{B}^{(1)}$$ from the old $$\vec{B}$$ by a simple Matrix multiplication:

\begin{equation*}\mat{M} \vec{B} = \vec{B^{(1)}}\end{equation*}

with the Matrix $$\mat{M}$$ being of shape $$n+1 \times n$$ and looking something like this:

\begin{equation*}\mat{M} = \begin{pmatrix} 1 & & & \\ \frac{1}{n+1} & 1- \frac{1}{n+1} & & \\ & \frac{2}{n+1} & 1- \frac{2}{n+1} & \\ \vdots \\ & & \frac{n}{n+1} & 1- \frac{n}{n+1} & \\ & & & 1 \end{pmatrix}\end{equation*}

Degree Reduction

The hard work is already done now: It only remains to say that we indeed find the best approximation to our Bézier curve (in the least squares sense) by finding the least-squares solution to the inverse of the system of equations given in the Matrix equation. Therefore, we find the best degree reduced control polygon by

\begin{equation*}\vec{B} = (\mat{M}^T \mat{M})^{-1} \mat{M}^T \vec{B}^{(1)}\end{equation*}

And here is an example from inside Blender. The highlighted objects are the reduced control polygon (n=4) and its Bézier curve. The non highlighted are the originals with one degree higher (5).

Reduced control Polygon and original + splines

As always, you can find the source code for this in the corresponding GitHub project.

August 23 2011 Click for Comments Permalink
« Generators in C++
Better Navigation »
blog comments powered by Disqus