Bézier-Kurven und der Algorithmus von De Casteljau

Bézier-Kurven und der Algorithmus von De Casteljau

🌐 Read in English
📅 20.11.2026 ✍️ Andreas Wittmann 👁️ ... algorithm graphics computer-graphics bezier

Bresenhams Linienalgorithmus und der Midpoint-Circle-Algorithmus zeichnen Formen, die durch eine Formel definiert sind: eine Linie, einen Kreis. Die meisten Kurven in der Praxis sind nicht so. Der Umriss eines Buchstabens in einer Schrift, ein Pfad in einer SVG-Datei oder eine Kurve in einem Zeichenprogramm ist eine von Hand gestaltete Form, und die gängigste Art, solche Formen zu beschreiben, ist die Bézier-Kurve: eine Handvoll Kontrollpunkte, die die Kurve in Form ziehen, ohne dass die Kurve zwangsläufig durch sie hindurchläuft.

Benannt sind Bézier-Kurven nach Pierre Bézier, der sie in den 1960er Jahren bei Renault für das Design von Karosserien bekannt machte. Paul de Casteljau hatte dieselben Kurven einige Jahre zuvor bei Citroën entwickelt, und der nach ihm benannte Algorithmus ist bis heute die anschaulichste Art, sie zu berechnen.

Die Idee

Alles beginnt mit linearer Interpolation: Zu zwei Punkten A und B und einer Zahl t zwischen 0 und 1 liegt der Punkt lerp(A, B, t) auf der geraden Strecke von A nach B, und zwar beim Anteil t des Weges. Bei t = 0 ist er A, bei t = 1 ist er B, bei t = 0,5 liegt er genau in der Mitte.

Der Algorithmus von De Casteljau wendet diese eine Operation immer wieder an. Man nimmt die Kontrollpunkte, interpoliert zwischen jedem benachbarten Paar mit demselben t und erhält einen Punkt weniger. Mit den neuen Punkten wiederholt man das. Wenn nur noch ein einziger Punkt übrig ist, liegt dieser Punkt beim Parameter t auf der Kurve. Lässt man t von 0 bis 1 laufen, entsteht die ganze Kurve.

Ein kleines Beispiel mit drei Kontrollpunkten, P0 = (0, 0), P1 = (2, 4), P2 = (4, 0), bei t = 0,5:

Stufe Punkte
Kontrollpunkte (0, 0), (2, 4), (4, 0)
1 (1, 2), (3, 2)
2 (2, 2)

Die Kurve läuft bei t = 0,5 also durch (2, 2) — auf halber Höhe in Richtung P1, aber nicht durch P1 hindurch.

Implementierung

#include "plot.hpp"

// The control points. Four points give a cubic curve; add or remove
// points to get a curve of higher or lower degree (at most MAX_POINTS).
PlotPoint control[] = {
    {70, 380},
    {200, 60},
    {440, 440},
    {570, 100},
};
const int N = sizeof(control) / sizeof(control[0]);
const int MAX_POINTS = 10;

const int STEPS = 240;   // frames for t to go from 0 to 1
const int PAUSE = 90;    // frames to hold the finished curve

PlotPoint lerp(PlotPoint a, PlotPoint b, double t) {
    return {a.x + (b.x - a.x) * t, a.y + (b.y - a.y) * t};
}

// De Casteljau's algorithm: interpolate between neighboring points,
// then between those results, and so on, until one point is left.
PlotPoint de_casteljau(double t) {
    PlotPoint p[MAX_POINTS];
    for (int i = 0; i < N; i++) p[i] = control[i];
    for (int level = 1; level < N; level++) {
        for (int i = 0; i + level < N; i++) {
            p[i] = lerp(p[i], p[i + 1], t);
        }
    }
    return p[0];
}

void dot(PlotPoint p, int size) {
    PlotFilledRectangle(p.x - size, p.y - size, p.x + size, p.y + size);
}

void setup() {
    PlotCanvas(640, 480);
}

void frame() {
    int f = g_current_frame % (STEPS + PAUSE);
    double t = (f < STEPS) ? (double)f / STEPS : 1.0;

    PlotBackground(250, 250, 250);

    // The control polygon.
    PlotColor(40, 44, 52);
    for (int i = 0; i + 1 < N; i++) PlotLine(control[i], control[i + 1]);
    for (int i = 0; i < N; i++) dot(control[i], 4);

    // The curve from 0 up to the current t, and a marker at every 0.1.
    PlotColor(70, 170, 90);
    PlotPoint prev = control[0];
    for (int k = 1; k <= 600 && k <= t * 600; k++) {
        PlotPoint q = de_casteljau(k / 600.0);
        PlotLine(prev, q);
        PlotLine(prev.x, prev.y + 1, q.x, q.y + 1); // a little thicker
        prev = q;
    }
    for (int k = 0; k <= 10 && k <= t * 10 + 1e-9; k++) {
        dot(de_casteljau(k / 10.0), 3);
    }

    // While the finished curve is held, leave out the construction.
    if (f >= STEPS) {
        PlotColor(40, 44, 52);
        PlotText(10, 10, "t = 1.00");
        return;
    }

    // The construction for the current t: every level of interpolation.
    PlotPoint p[MAX_POINTS];
    for (int i = 0; i < N; i++) p[i] = control[i];
    for (int level = 1; level < N; level++) {
        for (int i = 0; i + level < N; i++) p[i] = lerp(p[i], p[i + 1], t);
        if (level < N - 1) {
            PlotColor(30, 100, 200);
            for (int i = 0; i + level + 1 < N; i++) PlotLine(p[i], p[i + 1]);
            for (int i = 0; i + level < N; i++) dot(p[i], 3);
        }
    }

    // The point on the curve.
    PlotColor(220, 60, 60);
    dot(p[0], 5);

    PlotColor(40, 44, 52);
    PlotText(10, 10, "t = %.2f", t);
}
Open in full editor →

de_casteljau ist der Algorithmus genau wie beschrieben: die Kontrollpunkte kopieren und dann Stufe für Stufe jeden Punkt durch die Interpolation zwischen ihm und seinem rechten Nachbarn ersetzen. Bei N Kontrollpunkten sind das N - 1 Stufen.

Die Animation zeichnet dieselbe Konstruktion für das aktuelle t. Die dunklen Linien verbinden die Kontrollpunkte, die blauen Linien und Punkte sind die Zwischenstufen der Interpolation, der rote Punkt ist das Ergebnis für dieses t, und die grüne Linie ist die bisher gezeichnete Kurve. Die kleinen grünen Markierungen sitzen bei t = 0; 0,1; 0,2; …; 1. Ändere die Kontrollpunkte im Code oben und klicke auf „Compile & Run“: Drei Punkte ergeben eine quadratische Kurve, vier eine kubische, und mehr Punkte eine Kurve höheren Grades.

Was die Konstruktion verrät

Vieles am Verhalten einer Bézier-Kurve lässt sich direkt an der Konstruktion ablesen — und numerisch nachprüfen. Für die Kurve im Sample gilt:

Nicht gleichmäßig verteilt

Die grünen Markierungen in der Animation zeigen etwas weniger Offensichtliches: Gleich große Schritte in t ergeben keine gleich großen Abstände entlang der Kurve. Bei der Kurve im Sample, die etwa 641 Pixel lang ist, sind die zehn Abschnitte zwischen den Markierungen zwischen 54 Pixel in der Mitte und 92 Pixel am Ende lang. An ihren Enden bewegt sich die Kurve etwa 1,7-mal so schnell wie in der Mitte.

Fürs Zeichnen spielt das kaum eine Rolle. Alles, was sich mit konstanter Geschwindigkeit entlang einer Kurve bewegen soll — eine Animation oder Text, der einem Pfad folgt —, muss aber die Länge der Kurve messen und sie nach Strecke statt nach t durchlaufen.

Die Formel dahinter

Multipliziert man alle Interpolationen aus, ergibt sich eine geschlossene Formel. Für eine kubische Kurve mit den Kontrollpunkten P0 bis P3:

B(t) = (1-t)³·P0 + 3(1-t)²t·P1 + 3(1-t)t²·P2 + t³·P3

Die Gewichte vor den einzelnen Punkten sind die Bernstein-Polynome, und für jedes t ergeben sie zusammen 1 — B(t) ist also immer ein gewichteter Mittelwert der Kontrollpunkte, was wieder die Eigenschaft der konvexen Hülle ist. Der Algorithmus von De Casteljau und diese Formel ergeben dieselbe Kurve: Über 5.000 zufällige Kurven vom Grad 1 bis 7 wichen die beiden nie um mehr als etwa 10⁻¹² Pixel voneinander ab. Die Formel ist kürzer hinzuschreiben; der Algorithmus ist anschaulicher, numerisch sehr gutmütig und funktioniert für jede Anzahl von Punkten gleich.

Warum Kurven meist kubisch sind

Mit mehr Kontrollpunkten wird die Kurve schwerer zu steuern. Jeder Kontrollpunkt beeinflusst die gesamte Kurve, nicht nur den Teil in seiner Nähe, und die Kurve folgt dem Kontrollpolygon nur noch lose: Probiere im Sample sechs Punkte aus, und das Ergebnis ist ein glatter Bogen, der das meiste Zickzack dazwischen ignoriert. Deshalb setzen praktische Systeme stattdessen kurze Segmente niedrigen Grades aneinander. TrueType-Schriften bauen ihre Umrisse aus quadratischen Bézier-Stücken, während PostScript- und OpenType/CFF-Schriften, SVG-Pfade und die meisten Zeichenprogramme kubische verwenden — aneinandergehängt, und überall dort, wo der Umriss glatt wirken soll, beginnt jedes neue Segment in der Richtung, in der das vorige endete.

Fazit

Eine Bézier-Kurve wirkt wie eine glatte, komplizierte Form, doch der Algorithmus von De Casteljau baut sie aus der einfachsten Operation der Geometrie: einen Punkt auf halbem — oder beliebigem — Weg entlang einer geraden Strecke zu finden. Alles andere, von Anfang und Ende der Kurve bis zur Frage, warum sie innerhalb ihrer Kontrollpunkte bleibt, folgt aus der Wiederholung dieses einen Schritts.