TP1 : Bézier curves, De Casteljau’s algorithm

5 February 2016 in

Bézier curves

A degree $n$ Bézier curve takes the form

where

are the degree $n$ Bernstein polynomials, and the binomial coefficients are defined as

The Bézier points $\mathbf b_i \in \mathbb R^d$ form the control polygon.

De Casteljau’s algorithm

  • input Bézier points $\mathbf b_i$ for $i = 0, \dots, n$, and parameter $t \in [0,1]$.
  • output The point $\mathbf b_0^n$ on the curve.
  • compute Set $\mathbf b_i^0 = \mathbf b_i$ and compute the points

Visualisation of the steps of the De Casteljau's algorithm

Visualisation of the steps of the De Casteljau’s algorithm, $t=0.5$.

The De Casteljau’s algorithm provides an efficient means for evaluating a Bézier curve $\mathbf{x}(t)$. It is useful to look at this algorithm in its schematic form. For a quartic curve ($n=4$):

Animation of the De Casteljau's algorithm for a quintic curve

Animation of the De Casteljau’s algorithm for a quintic curve ($n=5$).

Code

git clone https://github.com/bbrrck/geo-num-2016.git
cd geo-num-2016/TP1
mkdir build
cd build
cmake ..
make
./geonum_TP1

For rendering, you can use gnuplot or matplotlib. While still in the build/ directory, test them by running :

gnuplot -p ../plots/plot.gnu
python ../plots/plot.py

Many of you have reported problems with gnuplot due to the line set terminal qt. Change it to something else to make things work, e.g. set terminal x11. For a complete list of terminals available on your machine, execute

echo "set terminal" | gnuplot

ToDo

  1. Implement the computation of a curve point $\mathbf x(t)$ using Bernstein polynomials.
  2. Implement the De Casteljau algorithm for a parameter $t$.
  3. Evaluate the curve using both methods and compare their performance the De Casteljau algorithm for various sampling densities.
  4. Visualise the curve and its Bézier polygon. Use all input files from the data/ folder.
  5. Visualise the intermediate polygons $\mathbf b_i^k$ from the De Casteljau algorithm for a fixed parameter $t$. (Only the simple.bcv is enough.)

Resources