Skip to content

De Casteljau Algorithm

venshine edited this page Nov 16, 2026 · 2 revisions

中文

De Casteljau's algorithm finds the point $C(t)$ on a Bézier curve for a given parameter $t$. Run it for many values of $t$ between 0 and 1 and you get the whole curve. BezierView uses it to draw the curve and the colored construction lines you see in the animation.

You could also evaluate the curve from its Bernstein polynomial form, which needs powers of $t$ and binomial coefficients. De Casteljau's algorithm only repeats one simple step: take a weighted average of two points with weights $1-t$ and $t$. Because both weights lie between 0 and 1, every intermediate point stays between the points it came from. This makes the algorithm numerically stable, and every step has a direct geometric meaning.

1. One step: split a segment

Given two points $A$ and $B$ and a number $t$ between 0 and 1, the point

$$C = (1 - t)\,A + t\,B$$

lies on segment $AB$. It divides $AB$ so that $|AC| : |CB| = t : (1 - t)$. At $t = 0$ it is $A$, at $t = 1$ it is $B$, and as $t$ grows it slides from $A$ to $B$.

Linear interpolation on one segment

2. Repeat until one point is left

A Bézier curve of order $n$ has $n + 1$ control points $P_0, P_1, \dots, P_n$. Connect them in order to get the control polygon, which has $n$ segments.

  1. Split every segment of the control polygon at ratio $t$. This gives $n$ new points; connect them to get a polygon with $n - 1$ segments.
  2. Split every segment of that new polygon at the same ratio $t$. This gives $n - 1$ points.
  3. Keep going. Each round has one point fewer than the previous one. After $n$ rounds a single point is left, and that point is $C(t)$.

The figure shows a cubic curve ($n = 3$) at $t = 0.25$. The control points are $P_0 = (0, 0)$, $P_1 = (2, 4)$, $P_2 = (6, 4)$ and $P_3 = (8, 0)$. The green points come from the first round, the purple points from the second, and the black point is the curve point. The solid red part is the curve traced from $t = 0$ to $t = 0.25$.

Constructing C(0.25) on a cubic curve

Here are the numbers. Write $P_i^{(k)}$ for the $i$-th point produced in round $k$; round 0 is the control points themselves.

Round $k$ Points
0 $P_0 = (0, 0)$, $P_1 = (2, 4)$, $P_2 = (6, 4)$, $P_3 = (8, 0)$
1 $P_0^{(1)} = (0.5, 1)$, $P_1^{(1)} = (3, 4)$, $P_2^{(1)} = (6.5, 3)$
2 $P_0^{(2)} = (1.125, 1.75)$, $P_1^{(2)} = (3.875, 3.75)$
3 $P_0^{(3)} = (1.8125, 2.25)$

So $C(0.25) = (1.8125, 2.25)$. You can check this against the Bernstein form: $x = 3 \cdot 0.75^2 \cdot 0.25 \cdot 2 + 3 \cdot 0.75 \cdot 0.25^2 \cdot 6 + 0.25^3 \cdot 8 = 1.8125$, and $y$ works out to $2.25$ the same way.

3. Computing it: the triangle

Every round uses only the points from the round before. In formula form:

$$P_i^{(0)} = P_i, \qquad P_i^{(k)} = (1 - t)\,P_i^{(k-1)} + t\,P_{i+1}^{(k-1)}, \qquad C(t) = P_0^{(n)}$$

Laid out row by row, the points form an upside-down triangle. Each point is computed from the two points directly above it, with weight $1 - t$ on the left one and $t$ on the right one.

The triangular computation scheme for n = 3

The triangle maps directly to code. Copy the control points into a working array. In round $k$, overwrite the first $n + 1 - k$ entries from left to right. Each entry only needs itself and its right-hand neighbor, and the neighbor has not been overwritten yet, so one array is enough:

fun deCasteljau(points: List<PointF>, t: Float): PointF {
    // Work on a copy so the caller's control points stay unchanged
    val q = points.map { PointF(it.x, it.y) }
    val n = points.size - 1
    for (k in 1..n) {
        for (i in 0..n - k) {
            q[i].x = (1 - t) * q[i].x + t * q[i + 1].x
            q[i].y = (1 - t) * q[i].y + t * q[i + 1].y
        }
    }
    return q[0]
}

An order-$n$ curve needs $n + (n - 1) + \dots + 1 = n(n + 1)/2$ interpolations per point: 6 for a cubic, 28 for order 7.

4. Why not just recurse

The recurrence above looks like it was made for a recursive function: to get $P_0^{(n)}$, compute $P_0^{(n-1)}$ and $P_1^{(n-1)}$ and combine them. That works, but it is slow, because the two halves share most of their work and neither knows what the other has already computed.

The call tree for a cubic shows the problem. The red nodes are values that are computed more than once.

Recursive calls for P0(3)

The tree has 15 calls, but there are only 10 distinct values. In general the recursion makes $2^{n+1} - 1$ calls, so the count doubles with every extra order: 255 calls for order 7, against the 28 interpolations of the triangle. The same thing happens with the textbook recursive Fibonacci function, which recomputes the same smaller Fibonacci numbers again and again. The fix is the same too: compute each value once, in order, and reuse it. That is exactly what the triangle does.

5. Every small triangle is a smaller curve

Pick any run of consecutive points in one row of the triangle, say $m + 1$ of them. They are the control points of a Bézier curve of order $m$. Running de Casteljau's algorithm on them with the same $t$ fills in a smaller triangle inside the big one. That smaller triangle points down, and its bottom tip is the point that algorithm returns.

In the figure ($n = 4$), the purple run $P_2, P_3, P_4$ is a quadratic curve whose point at $t$ is $P_2^{(2)}$. The green run $P_0^{(1)}, P_1^{(1)}$ is a straight line whose point at $t$ is $P_0^{(2)}$.

Sub-triangles inside the scheme for n = 4

A few useful facts follow from this:

  • Every row leads to the same answer. The whole of row $k$ is the control polygon of a curve of order $n - k$, and its tip is the same $P_0^{(n)}$. So $C(t)$ can be computed from any row, not only from the original control points.
  • The last segment is the tangent. Row $n - 1$ has two points, and $C(t)$ lies on the segment between them. That segment is tangent to the curve at $C(t)$, and the derivative is $C'(t) = n\,(P_1^{(n-1)} - P_0^{(n-1)})$.
  • The edges split the curve. The left edge of the triangle, $P_0^{(0)}, P_0^{(1)}, \dots, P_0^{(n)}$, holds the control points of the part of the curve from $t = 0$ to the current $t$. The right edge, $P_n^{(0)}, P_{n-1}^{(1)}, \dots, P_0^{(n)}$, holds the control points of the remaining part. This is how a Bézier curve is cut in two.

6. In BezierView

BezierView draws all of the rounds while the animation plays. The gray lines are the control polygon, each colored layer is one round of interpolation, the black dot is $C(t)$, and the red curve is its trail. The last colored segment always passes through the black dot, which is the tangent fact from section 5.

De Casteljau construction in the sample app, order 4

In the source (BezierView.kt):

  • buildBezierPoints() samples the curve at about 1,000 values of $t$ when the animation starts. It uses the recursive form (deCasteljauX / deCasteljauY). For order 7 that is 127 calls per coordinate per sample, which is cheap enough to do once per playback.
  • buildTangentPoints() builds the intermediate rounds one after another. Each round reuses the round before it, the way the triangle does. These are the colored lines in the animation.

Further reading