|home | pictures | links|
To understand why de Casteljau's algorithm for drawing polynomial surfaces works, one should first understand some affine geometry. An explanation of this is somewhat beyond what I want to do here, so I will refer you to a book by my thesis advisor, Jean Gallier, called "Curves and Surfaces in Geometric Modeling". For the purposes of this page, one only needs to realize that for any triangluar patch like this, there is a corresponding polynomial surface, and for every polynomial surface, there is a corresponding triangular patch.
In general, if the triangular patch has n rows and is non-degenerate, then the total degree of the polynomial will be n-1. Thus, the case you just saw is a framework for a polynomial of degree 5. The de Casteljau algorithm is a fast way to find any point on the polynomial surface given the framework. What is even more useful is that it may be used to construct an iterative algorithm whereby one may construct a new triangular framework that is a better approximation of the surface. An explanation of this algorithm may also be found in "Curves and Surfaces in Geometric Modeling". Here is an example of a randomly generated patch with six rows (similar to the one linked above) after just one iteration of my own variation on this iterative algorithm. Each time you reload the page you will get a different randomly generated surface.
One might ask the question of why this algorithm is useful. Why not simply draw the surface with a finer triangular grid? The answer is that, to animate the surface using this algorithm, I am only performing rotations on 21 points, but to animate the same thing without the algorithm I must rotate 126 points (and that's after just one iteration). Also, this is completely scalable. Thus software may be written for both slow and fast machines. The fast ones will simply be able to draw the surfaces more smoothly by running through more iterations.
|Note: You'll need the Java Virtual Machine to view the example of the algorithm and the example of the triangular framework.|