Bézier-Kurven und der Algorithmus von De Casteljau
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);
}
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:
- Sie beginnt beim ersten Kontrollpunkt und endet beim letzten. Bei
t = 0liefert jede Interpolation ihren linken Punkt, das Ergebnis ist alsoP0; beit = 1ist es der letzte Punkt. - Sie verlässt den ersten Punkt in Richtung des zweiten und erreicht den
letzten aus Richtung des vorletzten. Die Richtung am Anfang stimmt
exakt mit der Strecke von
P0nachP1überein, am Ende entsprechend. - Sie läuft nicht durch die inneren Kontrollpunkte. Die Kurve im
Sample kommt
P1nie näher als 182 Pixel undP2nie näher als 189 Pixel. Die Punkte ziehen die Kurve zu sich hin, liegen aber nicht auf ihr. - Sie bleibt innerhalb der konvexen Hülle ihrer Kontrollpunkte, der kleinsten konvexen Form, die alle Kontrollpunkte enthält. Jede Interpolation erzeugt einen Punkt zwischen zwei Punkten, die bereits in dieser Hülle liegen — das Ergebnis kann sie also nie verlassen. Geprüft an 5.000 zufälligen Kurven mit bis zu acht Kontrollpunkten lag kein einziger Kurvenpunkt außerhalb.
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.