Matheseitenüberblick
B-Splines

Der Algorithmus von de Casteljau

Paul de Faget de Casteljau (* 19.11.1930 in Besançon, † 24.3.2022 in Versailles), Phyiker und Mathematiker, fand bei und für Citroën 1958 einen effizienten rekursiven Algorithmus zur Berechnung von Spline-Kurven durch fortgesetzte Teilung der Teilstrecken im konstanten Verhältnis, der durch die damals neuen CAD-Systeme (Computer Aided Design) gut umsetzbar war. (Man denke hier an die legendäre Citroën DS mit dem damals avantgardistischen Design und den eleganten Karosseriekurven! →Foto bei Wikipedia)

Man kann das Verfahren hier interaktiv studieren. Die Stützpunkte des (bereits gezeichneten) B-Splines sind per Maus verschiebbar. Per Doppelklick können weitere Punkte hinzugefügt und auch wieder gelöscht werden. Aktivieren Sie die Option rekursives Teilen, und legen Sie entweder per Schieberegler oder per Mauszeiger am Spline selbst ein Teiungsverhältnis fest. (Wenn es an der Kurve festgelegt wird, dann wird der zugehörige Kurvenparameter t als Teilungsverhältnis übernommen.)

Die rekursive Teilung vermindert die Anzahl der Teilstrecken bei jedem Schritt um 1. Für einen B-Spline n-ten Grades (zu n+1 Stützstellen) endet der Algorithmus also nach der n-ten Teilung. Und zwar in genau dem Splinepunkt zum Parameterwert t, der dem Streckenteilungsverhältnis (zwischen 0 und 1) entspricht.

Citroën unterband damals die zeitnahe Veröffentlichung, wodurch Casteljaus Arbeit zunächst keine breite Beachtung und nicht die verdiente Anerkennung fand. Pierre Bèzier, der diese Spline-Kurven unabhängig davon zwei Jahre später bei Renault entwickelte und nach dem diese Kurven auch Bèzierkurven genannt werden, wies aber später — die Veröffentlichung fand schlußendlich 1974 statt — auf Casteljaus Bedeutung hin.

rekursives Teilen

Teilungsverhältnis:

interaktiv (Mauszeiger ) an Kurve

Animation  Tempo

Beweisskizze

Betrachten wir zunächst die Berechnung des Splinepunktes S zum Parameter t über die Gewichtung der Stützpunkte mit den Bernsteinpolynomen:

Die Faktoren sind die Binomialkoeffizienten (n
k) für die k von 0 bis n. Sie beschreiben bekanntlich (?) die Anzahl der Möglichkeiten, k Elemente aus n auszuwählen (ohne Wiederholung und ohne Beachtung der Reihenfolge).

Der Algorithmus von de Casteljau teilt alle Polygonteilstrecken (anfangs der Linienzug durch die n+1 vorgegebenen Stützpunkte P0 bis Pn) im Verhältnis t zu (1-t). Im ersten Schritt entstehten der neue Punkt Q0 (bzw. natürlich formal korrekt sein Ortsvektor) durch (1-t)·P0 + t·P1 (bzw. gleichwertig: P0 + t·(P1−P0) ) und die übrigen Punkte dieser ersten Unterteilungspunktgeneration bis Qn-1. Allgemein: Qi = (1-t)·Pi + t·Pi+1. Die Punkte Ri der zweiten Generation entstehen dann entsprechend durch Ri = (1-t)·Qi + t·Qi+1. und so weiter. Jede Generation hat dabei einen Punkt weniger, und am Ende bleibt ein Punkt übrig, der auf dem Spline liegt (was hier bewiesen werden soll).

Für den Fall n=3 stellt sich das nun m.E. recht anschaulich so dar:

P0P1P2P3
↘↙↘↙↘↙
Q0Q1Q2
↘↙↘↙
R0R1
↘↙
S
 Dabei repräsentieren die ↘ eine Multiplikation mit 1-t und die ↙ eine Multiplikation mit t.

Es fällt sofort die Ähnlichkeit mit dem Pascalschen Dreieck auf, und das ist natürlich kein Zufall, sondern im Grunde schon des Pudels Kern. Denn letztlich geht zum Beipiel P2 in S ein, indem stets zwei Schritte nach links (entsprichend jeweils mal t, folglich insgesamt: mal t²) vollzogen werden und einer nach rechts (entspricht mal (1-t)); und es sind insgesamt die 3 unterschiedlichen Pfade, die eben möglich sind, um aus den insgesamt drei erforderlichen Schritten genau zwei Schritte nach links unterzubringen, d.h. (3
2) = 3 unterschiedliche Pfade. Nach der Pfadregel wird dem Pfad entlang multipliziert, d.h. in diesen Fällen stets je zweimal mal t und einmal mal (1-t), was insgesamt ·t2·(1-t)1 macht. — Voilà!

In S geht also 3·t2·(1-t)1 · P2 ein. Und bei P1 ist es 3·t1·(1-t)2 · P1.

Verallgemeinert geht jeder Stützpunkt Pk tatsächlich (3
k)·tk·(1-t)3-k-mal in die Berechnung von S ein, was ja genau auf die obige Darstellung führt, sofern dort der Fall n=3 dargestellt wird —. (Die Aufstellung wird interaktiv der in der Graphik verwendeten Stützpunkteanzahl angepaßt, die ja n+1 ist: P0 bis Pn.)

© Arndt Brünner, 16. 8. 2022