Casteljau

Casteljau, also known as de Casteljau's algorithm, is a recursive method for evaluating points on Bezier curves. It was introduced by Paul de Casteljau in 1959 for the subdivision and evaluation of Bezier curves. Given a Bezier curve of degree n defined by control points P0, P1, ..., Pn and a parameter t in [0, 1], the algorithm constructs a triangular array Q_i^k where Q_i^0 = P_i and Q_i^{k+1} = (1 − t) Q_i^k + t Q_{i+1}^k for i = 0, ..., n − k − 1. The point on the curve at t is P(t) = Q_0^n. The same process yields the control points of the left and right subcurves, enabling efficient subdivision.

The method is numerically stable because it uses only convex combinations, preserves the convex hull of the control points, and does not require explicit polynomial evaluation in the Bernstein basis. It generalizes to rational Bezier curves by using homogeneous coordinates to incorporate weights, making it a robust tool in graphics and CAD. It works for any degree and supports adaptive refinement and rendering.

Applications include rendering and design of curves in computer graphics, font rendering, illustration software, and CAD/CAM systems. Computationally, evaluating a point requires O(n^2) operations; the subdivision property also provides a straightforward way to split curves at a given parameter. The algorithm remains a standard reference in Bezier curve discussions due to its geometric intuition and numerical stability.