De Casteljau's algorithm

The de Casteljau's algorithm is a method invented by Paul de Casteljau that uses recursive linear interpolation to find Bézier curves.

The algorithm can be expressed by the recurrence relation

$P_{i,j}(t)=(1-t)P_{i-1,j}(t)+tP_{i-1,j+1}(t)\,\!$

for i = 1, 2, ..., n and j = 0, 1, ..., n-i where P_0,j for j = 0, 1, ..., n are the initial control points,

Example

With three control points

$P_{0,0}(t)=A\,\!$

$P_{0,1}(t)=B\,\!$

$P_{0,2}(t)=C\,\!$

we would have

$P_{1,0}(t)=(1-t)P_{0,0}(t)+tP_{0,1}(t)=(1-t)A+tB\,\!$

$P_{1,1}(t)=(1-t)P_{0,1}(t)+tP_{0,2}(t)=(1-t)B+tC\,\!$

and

${\begin{matrix}P_{2,0}(t)&=&(1-t)P_{1,0}(t)+tP_{1,1}(t)\\\ &=&(1-t)((1-t)A+tB)+t((1-t)B+tC)\\\ &=&(1-t)^{2}A+2t(1-t)B+t^{2}C\\\end{matrix}}$

This gives the expected quadratic Bézier curve as a result.