Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
De Casteljau's algorithm
Summary
In the mathematical field of numerical analysis, De Casteljau's algorithm is a recursive method to evaluate polynomials in Bernstein form or Bézier curves, named after its inventor Paul de Casteljau. De Casteljau's algorithm can also be used to split a single Bézier curve into two Bézier curves at an arbitrary parameter value.
Although the algorithm is slower for most architectures when compared with the direct approach, it is more numerically stable.
A Bézier curve (of degree , with control points ) can be written in Bernstein form as follows
where is a Bernstein basis polynomial
The curve at point can be evaluated with the recurrence relation
Then, the evaluation of at point can be evaluated in operations. The result is given by
Moreover, the Bézier curve can be split at point into two curves with respective control points:
The geometric interpretation of De Casteljau's algorithm is straightforward.
Consider a Bézier curve with control points . Connecting the consecutive points we create the control polygon of the curve.
Subdivide now each line segment of this polygon with the ratio and connect the points you get. This way you arrive at the new polygon having one fewer segment.
Repeat the process until you arrive at the single point – this is the point of the curve corresponding to the parameter .
The following picture shows this process for a cubic Bézier curve:
Note that the intermediate points that were constructed are in fact the control points for two new Bézier curves, both exactly coincident with the old one. This algorithm not only evaluates the curve at , but splits the curve into two pieces at , and provides the equations of the two sub-curves in Bézier form.
The interpretation given above is valid for a nonrational Bézier curve. To evaluate a rational Bézier curve in , we may project the point into ; for example, a curve in three dimensions may have its control points and weights projected to the weighted control points . The algorithm then proceeds as usual, interpolating in .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.