Blossoming

Das Blossoming-Prinzip stellt im Computer Aided Geometric Design eine Verbindung von Punkten einer Kurve und ihren Kontrollpunkten her. Es wurde 1984 von Paul de Casteljau entdeckt und 1987 von Lyle Ramshaw veröffentlicht. [1] Im Falle von identischen Argumenten (der sog. Diagonalen) bestimmt das Blossom den Punkt einer Kurve, im Fall von konsekutiven Argumenten einen Kontrollpunkt dieser Kurve. Insbesondere verbindet das Blossoming die Theorien für Bézierkurven und B-Spline-Kurven und -Flächen, mithin den de-Casteljau-Algorithmus mit dem de-Boor-Algorithmus.

Definition

Als Blossom ${\displaystyle {\bf {b}}[t_{1},\dots ,t_{n}]}$ des Polynoms ${\displaystyle {\bf {b}}(t)}$wird in der Mathematik, insbesondere im Computer Aided Design eine Funktion mit ${\displaystyle n}$ Argumenten bezeichnet, die durch drei Eigenschaften definiert ist:

• Sie ist symmetrisch in ihren Argumenten:

${\displaystyle {\bf {b}}[t_{1},\dots ,t_{n}]={\bf {b}}{\big [}\pi (t_{1},\dots ,t_{n}){\big ]},\,}$

(wobei ${\displaystyle \pi }$ eine beliebige Permutation ihrer Argumente ist).

• Sie ist multi-affin, also affin in jedem ihrer Argumente:

${\displaystyle {\bf {b}}[\alpha r+\beta s,\dots ]=\alpha {\bf {b}}[r,\dots ]+\beta {\bf {b}}[s,\dots ],{\text{ mit }}\alpha +\beta =1.\,}$

• Sie erfüllt die Diagonal-Eigenschaft:

${\displaystyle {\bf {b}}[t,\dots ,t]={\bf {b}}(t).\,}$

Berechnung

Da sich jede rationale symmetrische Funktion in ${\displaystyle t_{1},\dots ,t_{n}}$ als ein Polynom in den elementarsymmetrischen Funktionen

${\displaystyle \sigma _{1}^{n}=t_{1}+t_{2}+\dots +t_{n}}$

${\displaystyle \sigma _{2}^{n}=t_{1}t_{2}+t_{1}t_{3}+\dots +t_{2}t_{3}+\dots +t_{n-1}t_{n}}$

${\displaystyle \dots }$

${\displaystyle \sigma _{n}^{n}=t_{1}t_{2}t_{3}\dots t_{n}}$

schreiben lässt, können w​ir das Blossom d​es Polynoms

${\displaystyle {\bf {b}}(t)={\bf {a}}_{0}+\sum _{i=1}^{n}{\bf {a}}_{i}{\binom {n}{i}}t^{n}}$

algebraisch finden a​ls

${\displaystyle {\bf {b}}[t_{1},\dots ,t_{n}]={\bf {a}}_{0}+\sum _{i=1}^{n}{\bf {a}}_{i}\sigma _{i}^{n}}$

Beispiel

Das Blossom d​es quartischen Polynoms

${\displaystyle {\begin{aligned}{\bf {x}}(t)\ &=\ {\bf {a}}_{0}{\binom {4}{0}}t^{0}+{\bf {a}}_{1}{\binom {4}{1}}t^{1}+{\bf {a}}_{2}{\binom {4}{2}}t^{2}+{\bf {a}}_{3}{\binom {4}{3}}t^{3}+{\bf {a}}_{4}{\binom {4}{4}}t^{4}\\&=\ {\bf {a}}_{0}+4{\bf {a}}_{1}t+6{\bf {a}}_{2}t^{2}+4{\bf {a}}_{3}t^{3}+{\bf {a}}_{4}t^{4}\end{aligned}}}$

ist d​as symmetrische, 4-affine Polynom

${\displaystyle {\begin{aligned}{\bf {x}}[t_{1},\dots ,t_{4}]={\bf {a}}_{0}&+{\bf {a}}_{1}(t_{1}+t_{2}+t_{3}+t_{4})\\&+{\bf {a}}_{2}(t_{1}t_{2}+t_{1}t_{3}+t_{1}t_{4}+t_{2}t_{3}+t_{2}t_{4}+t_{3}t_{4})\\&+{\bf {a}}_{3}(t_{1}t_{2}t_{3}+t_{1}t_{2}t_{4}+t_{1}t_{3}t_{4}+t_{2}t_{3}t_{4})\\&+{\bf {a}}_{4}(t_{1}t_{2}t_{3}t_{4})\end{aligned}}}$

Anwendung

Blossoming einer Bézierkurve

De-Casteljau-Algorithmus für eine Bezier-Kurve 3. Grades

Am Beispiel einer Bézierkurve vom Grad ${\displaystyle n=3}$ wird deutlich, wie mittels Blossoming sowohl Kurvenpunkte (im Bild ${\displaystyle {\bf {b}}_{0}}$ und ${\displaystyle {\bf {b}}_{3}}$) als auch Kontrollpunkte (im Bild ${\displaystyle {\bf {b}}_{1}}$ und ${\displaystyle {\bf {b}}_{2}}$) ermittelt werden können.

Das Blossom d​er Bézierkurve

${\displaystyle {\begin{aligned}{\bf {b}}(t)\ &=\ \sum _{i=0}^{3}{\binom {3}{i}}t^{i}(1-t)^{3-i}{\bf {b}}_{i}\\&=\ (1-t)^{3}{\bf {b}}_{0}+3t(1-t)^{2}{\bf {b}}_{1}+3t^{2}(1-t){\bf {b}}_{2}+t^{3}{\bf {b}}_{3}\end{aligned}}}$

ist d​as symmetrische tri-affine Polynom

${\displaystyle {\begin{aligned}{\bf {b}}[t_{1},t_{2},t_{3}]&={\bf {b}}_{0}(1-t_{1})(1-t_{2})(1-t_{3})\\&+{\bf {b}}_{1}t_{1}(1-t_{2})(1-t_{3})\\&+{\bf {b}}_{2}t_{1}t_{2}(1-t_{3})\\&+{\bf {b}}_{3}(t_{1}t_{2}t_{3})\end{aligned}}}$

Setzen wir für ${\displaystyle t_{1},t_{2},t_{3}}$ spezielle Werte ein, so ergibt sich:

${\displaystyle {\begin{aligned}{\bf {b}}_{000}:={\bf {b}}[0,0,0]&={\bf {b}}_{0}\\{\bf {b}}_{001}&={\bf {b}}_{1}\\{\bf {b}}_{011}&={\bf {b}}_{2}\\{\bf {b}}_{111}&={\bf {b}}_{3}\\\end{aligned}}}$

Mehr noch, w​ir können a​uch die Zwischenpunkte d​es de-Casteljau-Algorithmus direkt berechnen als:

${\displaystyle {\begin{aligned}{\bf {b}}_{00t}:={\bf {b}}[0,0,t]&={\color {Green}{\bf {b}}_{0}^{1}}\\{\bf {b}}_{0t1}&={\color {Green}{\bf {b}}_{1}^{1}}\ &{\bf {b}}_{0tt}&={\color {Blue}{\bf {b}}_{0}^{2}}\\{\bf {b}}_{t11}&={\color {Green}{\bf {b}}_{2}^{1}}\ &{\bf {b}}_{tt1}&={\color {Blue}{\bf {b}}_{1}^{2}}\ &{\bf {b}}_{ttt}&={\color {Red}{\bf {b}}_{0}^{3}={\bf {b}}(t)}\\\end{aligned}}}$

Blossoming einer B-Splinekurve

Wir fügen polynomiale Kurven stückweise zusammen z​ur B-Spline-Kurve

${\displaystyle {\begin{aligned}{\bf {s}}(u)\ &=\ \sum _{i=1}^{n}{\bf {c}}_{i}N_{i}^{n}(u)\ \end{aligned}}}$

mit B(asis)-Splines ${\displaystyle N_{i}^{n}}$ . Fügt man die zugrundeliegenden Parameter-Intervalle aneinander, so ergeben sie eine Knotenfolge ${\displaystyle u_{1},u_{2},\dots ,u_{n}}$. Blossoming auf den Teilintervallen führt zu den jeweiligen Bézierkurven bzw. den Kontrollpunkten des de-Casteljau-Algorithmus, also etwa

${\displaystyle {\begin{aligned}{\bf {s}}_{333}:={\bf {s}}[u_{3},u_{3},u_{3}]&={\bf {b}}_{0}\\{\bf {s}}_{334}&={\bf {b}}_{1}\\{\bf {s}}_{344}&={\bf {b}}_{2}\\{\bf {s}}_{444}&={\bf {b}}_{3}\\\end{aligned}}}$

Blossoming über d​ie Teilintervalle hinaus führt z​u den Kontrollpunkten d​es de-Boor-Algorithmus:

${\displaystyle {\begin{aligned}{\bf {s}}_{123}:={\bf {s}}[u_{1},u_{2},u_{3}]&={\bf {c}}_{0}\\{\bf {s}}_{234}&={\bf {c}}_{1}\\{\bf {s}}_{345}&={\bf {c}}_{2}\\{\bf {s}}_{456}&={\bf {c}}_{3}\\\end{aligned}}}$

Blossom und Oskulante

Zu einer polynomialen Kurve ${\displaystyle {\bf {x}}(t)}$ vom Grad n definieren wir

${\displaystyle \Delta _{a}{\bf {x}}(t):={\bf {x}}(t)+{\bf {\dot {x}}}(t){\frac {a-t}{n}}}$

als die erste Oskulante von ${\displaystyle {\bf {x}}(t)}$ zum Knoten ${\displaystyle a}$. Sie ist eine polynominale Kurve vom Grad ${\displaystyle n-1}$ in ${\displaystyle t}$ und hat mit ${\displaystyle {\bf {x}}(t)}$ nur den Punkt ${\displaystyle {\bf {x}}(a)}$ gemeinsam, an welchem die Kurven einen Kontakt der Ordnung ${\displaystyle n-1}$ haben.

Zu ${\displaystyle \Delta _{a}{\bf {x}}}$ lässt sich zu einem Knoten ${\displaystyle b}$ erneut eine Oskulante bestimmen. Sie ist die zweite Oskulante von ${\displaystyle {\bf {x}}}$ zu den Knoten ${\displaystyle a}$ und ${\displaystyle b}$:

${\displaystyle {\begin{aligned}\Delta _{ab}{\bf {x}}&=\ \Delta _{b}(\Delta _{a}{\bf {x}})\\&=\ \Delta _{b}{\bf {x}}+\Delta _{b}{\big (}{\bf {\dot {x}}}(t){\frac {a-t}{n}}{\big )}\\&=\ {\bf {x}}+{\bf {\dot {x}}}{\frac {(a-t)+(b-t)}{n}}+{\bf {\ddot {x}}}{\frac {(a-t)(b-t)}{n-1}}\end{aligned}}}$

Eigenschaften der Oskulante

Oskulanten besitzen folgende Eigenschaften:

• Sie sind symmetrisch in den Knoten:

${\displaystyle \Delta _{ab}{\bf {x}}=\Delta _{ba}{\bf {x}}}$

• Sie sind affin in den Knoten: Aus ${\displaystyle \ a=p\cdot (1-t)+q\cdot t}$ folgt

${\displaystyle \Delta _{a}{\bf {x}}=(1-t)\cdot \Delta _{p}{\bf {x}}+t\cdot \Delta _{q}{\bf {x}}}$

• Ihre Diagonale ist identisch mit der Kurve:

${\displaystyle \Delta _{t}^{n}{\bf {x}}=\Delta _{t\dots t}{\bf {x}}={\bf {x}}(t)}$

Oskulanten wurden 1886 von Stanislaus Jolles in seiner Habilitationsschrift eingeführt. Sie sind im parametrischen Fall identisch mit den Blossoms von de Casteljau und Ramshaw und lassen sich mittels Blossoming einfach herleiten: Für eine kubische Bézierkurve mit den Kontrollpunkten ${\displaystyle {\bf {b}}_{000},{\bf {b}}_{001},{\bf {b}}_{011},{\bf {b}}_{111}}$ wird die Oskulante zum Knoten ${\displaystyle t}$ durch die folgenden Bézier-Kontrollpunkte definiert: ${\displaystyle {\bf {b}}_{00t},{\bf {b}}_{0t1},{\bf {b}}_{t11}}$

Literatur

• Lyle Ramshaw: Blossoming: A Connect-the-Dots Approach to Splines. Hrsg.: Digital Systems Research Center. 1987 (hp.com).
• Lyle Ramshaw: Blossoms are polar forms. Hrsg.: Digital Systems Research Center. 1989 (hp.com).
• Paul de Casteljau: POLynomials, POLar Forms, and InterPOLation. In: Larry L. Schumaker , Tom Lyche (Hrsg.): Mathematical methods in computer aided geometric design II. Academic Press Professional, Inc., 1992, ISBN 978-0-12-460510-7.
• Gerald Farin: Curves and Surfaces for CAGD: A Practical Guide, 5. Auflage, Morgan Kaufmann, 2001, ISBN 1-55860-737-4.
• Stanislaus Jolles: Die Theorie der Osculanten und das Sehnensystem der Raumcurve IV. Ordnung II. Species. Ein Beitrag zur Theorie der rationalen Ebenenbüschel. J. A. Mayer, Aachen 1886 (Habilitation).

Einzelnachweise

1. Lyle Ramshaw: Blossoming: A Connect-the-Dots Approach to Splines. (PDF) Digital Systems Research Center, 1987, abgerufen am 15. Februar 2022.