Bézier-Kurven

Spezifiziere die Kurve durch $n+1$ Stützpunkte $P_{0}, P_{1}, \ldots, P_{n}$. Die Kurve läuft nicht durch alle Stützpunkte, sondern wird von ihnen beeinflußt. Zeitgleich in den 1960'ern entwickelt von P. Bézier bei Renault und von P. de Casteljau bei Citroen. Damals sollten Karosserien entworfen werden, die den ästhetischen Ansprüchen der Designer und den technischen Ansprüchen der Ingenieure genügten.

$$P(t)=\sum_{i = 0}^{n} B_{i,n} (t)\cdot P_{i}, ~~0 \leq t \leq 1$$

Der Punkt $P_i$ wird gewichtet mit Hilfe eines Bernstein-Polynoms.

$$B_{i,n} (t) = \frac{n!}{i!\cdot (n-i)!} \cdot t^{i} \cdot (1-t)^{n-i}, ~ i = 0, ... , n$$

Abbildung 7.2: Verlauf der Bernsteinpolynome für n=3

Die wichtigsten Eigenschaften der Bernsteinpolynome:

• alle Bernsteinpolynome sind positiv auf $[0,1]$,
• für jedes feste $t$ gilt $\sum_{i = 0}^{n}B_{i,n} (t)=1$,
• $B_{i,n} (t) = B_{n - i,n} (1-t)$,
• $\frac {d B_{i,n} (t)}{d t}=n \cdot (B_{i-1, n-1}(t)- B_{i, n-1}(t)), i > 0$,
• Maxima von $B_{i,n} (t)$ in $[0,1]$ an den Stellen $t = \frac{i}{n},i=0, \ldots, n$.

Da alle Bernsteinpolynome für $0 < t < 1$ ungleich Null sind, beeinflussen alle Stützpunkte in diesem Intervall den Kurvenverlauf.

Die Kurve beginnt im Stützpunkt $P_0$ tangential zur Geraden $\overline{P_{0} P_{1}}$, endet im Stützpunkt $P_n$ tangential zur Geraden $\overline{P_{n-1} P_{n}}$ und verläuft innerhalb der konvexen Hülle der Stützpunkte. Somit können mehrere Bézier-Kurven aneinandergesetzt werden durch Identifikation von Endpunkt und Anfangspunkt aufeinanderfolgender Bézierkurven. Einen stetig differenzierbaren Übergang erreicht man bei Kollinearität der Punkte $P_{n - 1},P_{n} = Q_0, Q_1$.

Berechnung der Bézier-Kurve nach de Casteljau

Um die aufwendige Auswertung der Bernsteinpolynome zu vermeiden, wurde von de Casteljau ein Iterationsverfahren vorgeschlagen, welches durch fortgesetztes Zerteilen von Linien den gewünschten Kurvenpunkt approximieren kann.

Es gilt:

$$P(t)_{0, n} = (1 - t) \cdot P(t)_{0, n -1} + t \cdot P(t)_{1, n}$$

wobei die tiefgestellten Indizes angeben, welche Stützpunkte in die Berechnung einfließen. D.h. eine Bézier-Kurve vom Grad $n$ läßt sich durch zwei Bézier-Kurven vom Grad $n-1$ definieren, indem für ein festes $t$ die Punkte beider Kurven berechnet werden, und die Verbindungsstrecke im Verhältnis $t$ geteilt wird.

Beispiel für $t=1/2$:

$\left( \begin{array}{c}0 \\ 0 \end{array} \right)$
$\left( \begin{array}{c}0 \\ 2 \end{array} \right)$	$\left( \begin{array}{c}0 \\ 1 \end{array} \right)$
$\left( \begin{array}{c}8 \\ 2 \end{array} \right)$	$\left( \begin{array}{c}4 \\ 2 \end{array} \right)$	$\left( \begin{array}{c}2 \\ \frac{3}{2} \end{array} \right)$
$\left( \begin{array}{c}4 \\ 0 \end{array} \right)$	$\left( \begin{array}{c}6 \\ 1 \end{array} \right)$	$\left( \begin{array}{c}5 \\ \frac{3}{2} \end{array} \right)$	$\left( \begin{array}{c}\frac{7}{2} \\ \frac{3}{2} \end{array} \right)$

Abbildung 7.3: Approximation einer Bezier-Kurve nach de Casteljau

Abbildung 7.3 zeigt die Berechnung eines Kurvenpunktes für $t= \frac{1}{3}$. Die Indizes geben an, welche Stützpunkte beteiligt sind. Abbildung zeigt das Ergebnis dieser Iteration für zwei aneinanderliegende kubische Bézierkurven (Rekursionstiefe 3).

Abbildung 7.4: Vom De Casteljau-Algorithmus mit Rekursionstiefe 3 gezeichnete Bezierkurven

/**************************************************************************/
/*                                                                        */
/*        Zeichnen einer Bezierkurve 3. Grades nach De Casteljau          */
/*                                                                        */
/**************************************************************************/
/** Zeichne Bezierkurve 3. Grades */
private void bezier(
  double px0, double py0,                        // mit Stuetzpunkt p0
  double px1, double py1,                        // mit Stuetzpunkt p1
  double px2, double py2,                        // mit Stuetzpunkt p2
  double px3, double py3,                        // mit Stuetzpunkt p3
  int depth)                                     // aktuelle Rekursionstiefe
{
  double qx01,qy01,qx12,qy12,qx23,qy23,          // Hilfspunkte
         qx012,qy012,qx123,qy123,qx0123,qy0123;

  if (depth > iter)                              // Iterationstiefe erreicht
    drawLine(new Point( (int)px0, (int)py0),     // Linie zeichnen
             new Point( (int)px3, (int)py3));
    else {
      depth++;

      qx01   = (px0+px1)/2;     qy01   = (py0+py1)/2;
      qx12   = (px1+px2)/2;     qy12   = (py1+py2)/2;
      qx23   = (px2+px3)/2;     qy23   = (py2+py3)/2;
      qx012  = (qx01+qx12)/2;   qy012  = (qy01+qy12)/2;
      qx123  = (qx12+qx23)/2;   qy123  = (qy12+qy23)/2;
      qx0123 = (qx012+qx123)/2; qy0123 = (qy012+qy123)/2;

      bezier(px0,py0,qx01,qy01,qx012,qy012,qx0123,qy0123,depth);
      bezier(qx0123,qy0123,qx123,qy123,qx23,qy23,px3,py3,depth);
  }
}