De Casteljau's Algorithm

Introduction

Every letter you read, every smooth path in a vector drawing, every surface in a 3-D model — they are all described by Bézier curves. And every Bézier curve is evaluated by the same elegant recursion invented (independently of Bézier himself) by the engineer Paul de Casteljau at Citroën in 1959.

The idea could not be simpler: given a set of control points and a parameter $t \in [0, 1]$ , repeatedly blend neighboring points by the ratio $t : (1-t)$ until only one point remains. That final point lies on the curve. Do this for every $t$ and you trace the whole shape.

What makes the algorithm remarkable is not just its elegance but its numerical stability. Evaluating a Bézier curve by expanding its polynomial and then plugging in $t$ can suffer from catastrophic cancellation; de Casteljau's repeated linear blending never does. It also reveals the geometric structure of the curve — the intermediate scaffolding it builds is the very skeleton that makes subdivision, clipping and degree elevation natural.

Try It

Drag the t slider to step through the algorithm. The gray lines are the original control polygon. Each colored layer connects the linearly interpolated points at that level — watch the scaffold collapse until a single point traces the Bézier curve in blue.

<!-- Controls (t slider + buttons) above the canvas -->
<div class="controls">
  <label for="tSlider"><strong>t =</strong> <span id="tVal">0.50</span></label>
  <input id="tSlider" type="range" min="0" max="100" value="50" step="1" aria-label="Parameter t from 0 to 1">
  <button id="animBtn" type="button">Animate</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<canvas id="cv" width="480" height="320" aria-label="De Casteljau scaffold collapsing to the Bézier curve point"></canvas>
<p class="hint" id="hint">Drag any white control point to reshape the curve.</p>

/* Layout, canvas and button styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; align-items: center; gap: .7rem; flex-wrap: wrap; margin-bottom: .5rem; }
label { font-size: .95rem; white-space: nowrap; }
input[type=range] { flex: 1; min-width: 120px; max-width: 280px; cursor: pointer; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; white-space: nowrap; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 10px;
         background: #f8fafc; cursor: crosshair; touch-action: none; max-width: 100%; }
.hint { font-size: .85rem; color: #555; margin: .4rem 0 0; }

// De Casteljau's algorithm: evaluate a cubic Bézier curve at parameter t
// by repeated linear interpolation of the control polygon.
const canvas = document.getElementById('cv');
const ctx = canvas.getContext('2d');
const slider = document.getElementById('tSlider');
const tValEl = document.getElementById('tVal');
const hintEl = document.getElementById('hint');
const animBtn = document.getElementById('animBtn');

// Hi-DPI canvas scaling
const DPR = window.devicePixelRatio || 1;
const W = canvas.width, H = canvas.height;
canvas.width = W * DPR; canvas.height = H * DPR;
canvas.style.width = W + 'px'; canvas.style.height = H + 'px';
ctx.scale(DPR, DPR);

// Control points (cubic: 4 points = degree 3)
let pts = [
  { x: 60,  y: 260 },
  { x: 140, y: 60  },
  { x: 320, y: 60  },
  { x: 400, y: 260 }
];

// Color per interpolation layer: [control polygon, level 1, level 2, result]
const LAYER_COLORS = ['#adb5bd', '#e9c46a', '#e76f51', '#2a9d8f'];

let t = 0.5;
let dragging = null;
let animId = null;
let animDir = 1;

// Linear interpolation: blend two points by ratio t
function lerp(a, b, t) {
  return { x: a.x + (b.x - a.x) * t, y: a.y + (b.y - a.y) * t };
}

// Run De Casteljau and return ALL intermediate layers for drawing
function deCasteljau(points, t) {
  const layers = [points.map(p => ({ ...p }))];
  while (layers[layers.length - 1].length > 1) {
    const prev = layers[layers.length - 1];
    const next = [];
    for (let i = 0; i < prev.length - 1; i++) {
      next.push(lerp(prev[i], prev[i + 1], t));
    }
    layers.push(next);
  }
  return layers;
}

// Sample the full curve at many t values for the blue stroke
function bezierCurve(points, steps) {
  const pts = [];
  for (let i = 0; i <= steps; i++) {
    const layers = deCasteljau(points, i / steps);
    pts.push(layers[layers.length - 1][0]);
  }
  return pts;
}

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Draw the full Bézier curve in blue
  const curve = bezierCurve(pts, 120);
  ctx.beginPath();
  ctx.moveTo(curve[0].x, curve[0].y);
  for (let i = 1; i < curve.length; i++) ctx.lineTo(curve[i].x, curve[i].y);
  ctx.strokeStyle = '#1d6fa8';
  ctx.lineWidth = 2.5;
  ctx.stroke();

  // Draw each interpolation layer (scaffold)
  const layers = deCasteljau(pts, t);
  layers.forEach((layer, li) => {
    if (layer.length < 2) return;
    ctx.beginPath();
    ctx.moveTo(layer[0].x, layer[0].y);
    for (let i = 1; i < layer.length; i++) ctx.lineTo(layer[i].x, layer[i].y);
    ctx.strokeStyle = LAYER_COLORS[li] || '#aaa';
    ctx.lineWidth = li === 0 ? 1.2 : 1.8;
    ctx.setLineDash(li === 0 ? [5, 4] : []);
    ctx.stroke();
    ctx.setLineDash([]);

    // Draw dots at each intermediate point
    layer.forEach(p => {
      ctx.beginPath();
      ctx.arc(p.x, p.y, li === 0 ? 4.5 : 3.5, 0, 2 * Math.PI);
      ctx.fillStyle = li === 0 ? '#fff' : (LAYER_COLORS[li] || '#aaa');
      ctx.strokeStyle = LAYER_COLORS[li] || '#aaa';
      ctx.lineWidth = 1.5;
      ctx.fill();
      ctx.stroke();
    });
  });

  // Highlight the final result point in green
  const result = layers[layers.length - 1][0];
  ctx.beginPath();
  ctx.arc(result.x, result.y, 7, 0, 2 * Math.PI);
  ctx.fillStyle = '#2a9d8f';
  ctx.fill();
  ctx.strokeStyle = '#fff';
  ctx.lineWidth = 2;
  ctx.stroke();
}

function update() {
  t = slider.value / 100;
  tValEl.textContent = t.toFixed(2);
  draw();
}

// Animation: bounce t between 0 and 1
function tick() {
  let v = parseInt(slider.value) + animDir;
  if (v >= 100) { v = 100; animDir = -1; }
  if (v <= 0)   { v = 0;   animDir = 1;  }
  slider.value = v;
  update();
  animId = requestAnimationFrame(tick);
}

animBtn.addEventListener('click', () => {
  if (animId) {
    cancelAnimationFrame(animId);
    animId = null;
    animBtn.textContent = 'Animate';
  } else {
    animDir = slider.value >= 100 ? -1 : 1;
    animId = requestAnimationFrame(tick);
    animBtn.textContent = 'Pause';
  }
});

document.getElementById('resetBtn').addEventListener('click', () => {
  pts = [{ x:60,y:260 },{ x:140,y:60 },{ x:320,y:60 },{ x:400,y:260 }];
  slider.value = 50; update();
});

slider.addEventListener('input', update);

// Pointer drag to move control points
function ptAt(px, py) {
  for (let i = 0; i < pts.length; i++) {
    const dx = pts[i].x - px, dy = pts[i].y - py;
    if (Math.sqrt(dx*dx + dy*dy) < 14) return i;
  }
  return null;
}
function clientXY(e) {
  const r = canvas.getBoundingClientRect();
  const src = e.touches ? e.touches[0] : e;
  return { x: (src.clientX - r.left) * (W / r.width), y: (src.clientY - r.top) * (H / r.height) };
}
canvas.addEventListener('pointerdown', e => {
  const p = clientXY(e);
  dragging = ptAt(p.x, p.y);
  if (dragging !== null) { canvas.setPointerCapture(e.pointerId); hintEl.textContent = 'Release to stop dragging.'; }
});
canvas.addEventListener('pointermove', e => {
  if (dragging === null) return;
  const p = clientXY(e);
  pts[dragging] = { x: Math.max(0, Math.min(W, p.x)), y: Math.max(0, Math.min(H, p.y)) };
  draw();
});
canvas.addEventListener('pointerup', () => { dragging = null; hintEl.textContent = 'Drag any white control point to reshape the curve.'; });

update();

<!-- Controls (t slider + buttons) above the canvas -->
<div class="controls">
  <label for="tSlider"><strong>t =</strong> <span id="tVal">0.50</span></label>
  <input id="tSlider" type="range" min="0" max="100" value="50" step="1" aria-label="Parameter t from 0 to 1">
  <button id="animBtn" type="button">Animate</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<canvas id="cv" width="480" height="320" aria-label="De Casteljau scaffold collapsing to the Bézier curve point"></canvas>
<p class="hint" id="hint">Drag any white control point to reshape the curve.</p>

/* Layout, canvas and button styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; align-items: center; gap: .7rem; flex-wrap: wrap; margin-bottom: .5rem; }
label { font-size: .95rem; white-space: nowrap; }
input[type=range] { flex: 1; min-width: 120px; max-width: 280px; cursor: pointer; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; white-space: nowrap; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 10px;
         background: #f8fafc; cursor: crosshair; touch-action: none; max-width: 100%; }
.hint { font-size: .85rem; color: #555; margin: .4rem 0 0; }

// De Casteljau's algorithm: evaluate a cubic Bézier curve at parameter t
// by repeated linear interpolation of the control polygon.
const canvas = document.getElementById('cv');
const ctx = canvas.getContext('2d');
const slider = document.getElementById('tSlider');
const tValEl = document.getElementById('tVal');
const hintEl = document.getElementById('hint');
const animBtn = document.getElementById('animBtn');

// Hi-DPI canvas scaling
const DPR = window.devicePixelRatio || 1;
const W = canvas.width, H = canvas.height;
canvas.width = W * DPR; canvas.height = H * DPR;
canvas.style.width = W + 'px'; canvas.style.height = H + 'px';
ctx.scale(DPR, DPR);

// Control points (cubic: 4 points = degree 3)
let pts = [
  { x: 60,  y: 260 },
  { x: 140, y: 60  },
  { x: 320, y: 60  },
  { x: 400, y: 260 }
];

// Color per interpolation layer: [control polygon, level 1, level 2, result]
const LAYER_COLORS = ['#adb5bd', '#e9c46a', '#e76f51', '#2a9d8f'];

let t = 0.5;
let dragging = null;
let animId = null;
let animDir = 1;

// Linear interpolation: blend two points by ratio t
function lerp(a, b, t) {
  return { x: a.x + (b.x - a.x) * t, y: a.y + (b.y - a.y) * t };
}

// Run De Casteljau and return ALL intermediate layers for drawing
function deCasteljau(points, t) {
  const layers = [points.map(p => ({ ...p }))];
  while (layers[layers.length - 1].length > 1) {
    const prev = layers[layers.length - 1];
    const next = [];
    for (let i = 0; i < prev.length - 1; i++) {
      next.push(lerp(prev[i], prev[i + 1], t));
    }
    layers.push(next);
  }
  return layers;
}

// Sample the full curve at many t values for the blue stroke
function bezierCurve(points, steps) {
  const pts = [];
  for (let i = 0; i <= steps; i++) {
    const layers = deCasteljau(points, i / steps);
    pts.push(layers[layers.length - 1][0]);
  }
  return pts;
}

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Draw the full Bézier curve in blue
  const curve = bezierCurve(pts, 120);
  ctx.beginPath();
  ctx.moveTo(curve[0].x, curve[0].y);
  for (let i = 1; i < curve.length; i++) ctx.lineTo(curve[i].x, curve[i].y);
  ctx.strokeStyle = '#1d6fa8';
  ctx.lineWidth = 2.5;
  ctx.stroke();

  // Draw each interpolation layer (scaffold)
  const layers = deCasteljau(pts, t);
  layers.forEach((layer, li) => {
    if (layer.length < 2) return;
    ctx.beginPath();
    ctx.moveTo(layer[0].x, layer[0].y);
    for (let i = 1; i < layer.length; i++) ctx.lineTo(layer[i].x, layer[i].y);
    ctx.strokeStyle = LAYER_COLORS[li] || '#aaa';
    ctx.lineWidth = li === 0 ? 1.2 : 1.8;
    ctx.setLineDash(li === 0 ? [5, 4] : []);
    ctx.stroke();
    ctx.setLineDash([]);

    // Draw dots at each intermediate point
    layer.forEach(p => {
      ctx.beginPath();
      ctx.arc(p.x, p.y, li === 0 ? 4.5 : 3.5, 0, 2 * Math.PI);
      ctx.fillStyle = li === 0 ? '#fff' : (LAYER_COLORS[li] || '#aaa');
      ctx.strokeStyle = LAYER_COLORS[li] || '#aaa';
      ctx.lineWidth = 1.5;
      ctx.fill();
      ctx.stroke();
    });
  });

  // Highlight the final result point in green
  const result = layers[layers.length - 1][0];
  ctx.beginPath();
  ctx.arc(result.x, result.y, 7, 0, 2 * Math.PI);
  ctx.fillStyle = '#2a9d8f';
  ctx.fill();
  ctx.strokeStyle = '#fff';
  ctx.lineWidth = 2;
  ctx.stroke();
}

function update() {
  t = slider.value / 100;
  tValEl.textContent = t.toFixed(2);
  draw();
}

// Animation: bounce t between 0 and 1
function tick() {
  let v = parseInt(slider.value) + animDir;
  if (v >= 100) { v = 100; animDir = -1; }
  if (v <= 0)   { v = 0;   animDir = 1;  }
  slider.value = v;
  update();
  animId = requestAnimationFrame(tick);
}

animBtn.addEventListener('click', () => {
  if (animId) {
    cancelAnimationFrame(animId);
    animId = null;
    animBtn.textContent = 'Animate';
  } else {
    animDir = slider.value >= 100 ? -1 : 1;
    animId = requestAnimationFrame(tick);
    animBtn.textContent = 'Pause';
  }
});

document.getElementById('resetBtn').addEventListener('click', () => {
  pts = [{ x:60,y:260 },{ x:140,y:60 },{ x:320,y:60 },{ x:400,y:260 }];
  slider.value = 50; update();
});

slider.addEventListener('input', update);

// Pointer drag to move control points
function ptAt(px, py) {
  for (let i = 0; i < pts.length; i++) {
    const dx = pts[i].x - px, dy = pts[i].y - py;
    if (Math.sqrt(dx*dx + dy*dy) < 14) return i;
  }
  return null;
}
function clientXY(e) {
  const r = canvas.getBoundingClientRect();
  const src = e.touches ? e.touches[0] : e;
  return { x: (src.clientX - r.left) * (W / r.width), y: (src.clientY - r.top) * (H / r.height) };
}
canvas.addEventListener('pointerdown', e => {
  const p = clientXY(e);
  dragging = ptAt(p.x, p.y);
  if (dragging !== null) { canvas.setPointerCapture(e.pointerId); hintEl.textContent = 'Release to stop dragging.'; }
});
canvas.addEventListener('pointermove', e => {
  if (dragging === null) return;
  const p = clientXY(e);
  pts[dragging] = { x: Math.max(0, Math.min(W, p.x)), y: Math.max(0, Math.min(H, p.y)) };
  draw();
});
canvas.addEventListener('pointerup', () => { dragging = null; hintEl.textContent = 'Drag any white control point to reshape the curve.'; });

update();

Result

Console

Drag any of the four control points to reshape the curve and see how the polygon changes. The green dot is the curve point $B(t)$ — the output of the algorithm for the current $t$ .

The Real Complexity

De Casteljau's algorithm is a solved, classical result — not an open problem.

Paul de Casteljau derived it at Citroën in 1959, though the work remained proprietary for years; Pierre Bézier independently published the parametric curve framework at Renault in the 1960s, and the mathematical equivalence was later recognized.

For a degree- $n$ Bézier curve with $n+1$ control points, the algorithm computes:

\mathbf{b}_i^{(r)}(t) = (1-t)\,\mathbf{b}_i^{(r-1)}(t) + t\,\mathbf{b}_{i+1}^{(r-1)}(t)

starting from $\mathbf{b}_i^{(0)} = \mathbf{P}_i$ and finishing at $\mathbf{b}_0^{(n)} = B(t)$ .

Time: $O(n^2)$ linear interpolations (the triangular table has $1 + 2 + \dots + n$ entries).
Space: $O(n)$ — each reduction round can overwrite the previous layer in place.
Numerical stability: every step is a convex combination $(1-t)a + tb$ with $t \in [0,1]$ , so intermediate values stay inside the convex hull of the control points. Horner evaluation of the equivalent Bernstein polynomial is faster ( $O(n)$ ) but amplifies floating-point errors at the boundaries.
Subdivision for free: splitting at parameter $t$ produces the left sub-polygon $\mathbf{b}_0^{(0)}, \mathbf{b}_0^{(1)}, \dots, \mathbf{b}_0^{(n)}$ and the right sub-polygon $\mathbf{b}_0^{(n)}, \mathbf{b}_1^{(n-1)}, \dots, \mathbf{b}_n^{(0)}$ — both read directly from the triangular table. Subdivision is the engine behind adaptive curve rendering and convex-hull clipping in computer graphics.

Because the algorithm only uses addition and multiplication by scalars, it works unchanged over any field — real, complex, or even symbolic — which is why it generalizes so cleanly to rational Bézier curves (NURBS) and tensor-product surfaces.

Where It Matters

The algorithm is so fundamental that it appears, often invisibly, in almost every corner of digital geometry:

Font rendering: TrueType and PostScript fonts define glyph outlines as quadratic or cubic Bézier curves evaluated by de Casteljau's algorithm every time text is rasterized.
Vector graphics (SVG, PDF, Illustrator): the C, Q and S path commands in SVG describe Bézier segments; renderers subdivide them via de Casteljau until each piece is flat enough to fill with scan lines.
CAD and industrial design: the surface of every car, aircraft fuselage and consumer product designed with CATIA, Rhino or SolidWorks is a patchwork of Bézier (or rational B-spline) surfaces ultimately evaluated by generalizations of de Casteljau's scheme.
Animation easing: CSS cubic-bezier() timing functions and After Effects motion paths are cubic Bézier curves; the browser evaluates them with the same recursion to smooth out every UI transition.
CNC and robotics: toolpaths and joint trajectories are parameterized as Bézier curves so that speed and curvature vary smoothly along the path.

In short, de Casteljau's algorithm is the quiet foundation of computer-aided geometric design (CAGD). Understanding it unlocks the geometry behind convex-hull algorithms, compression of curve data, and the entire family of spline methods used in modern rendering.

Conclusion

De Casteljau's algorithm answers one of the most natural questions in geometry: given a set of control points and a parameter $t$ , where exactly is the curve? The answer is a cascade of linear blends — each level averaging its neighbors by $t$ and $(1-t)$ — until only one point remains.

The result is numerically stable, geometrically transparent, and simultaneously solves the evaluation problem, the subdivision problem and the clipping problem. It has been at the heart of every CAD system, every font renderer and every vector graphics engine for six decades — not because no one found something cleverer, but because the algorithm is already as clean as geometry allows.

So the next time you smooth an animation curve, extrude a car door in CAD, or simply read a word on screen, you are watching de Casteljau's recursion run — thousands of times per second, collapsing polygons to points.

Comments

Loading comments...

https://www.kipuhub.com/en/article/de-casteljau/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Repeated linear interpolation collapses a polygon to a point