Splines ( Einführung )

Wenn wenige feste Punkte bekannt sind, wie sollte ein interolierende Funktion gefunden werden, mit der interpolierende Zwischenpunkt ( in gewünschtem Verlauf ) berechnet werden lönnen? Splines ( Name für "dünne Latte" ) basieren auf der Idee, daß eine "dünne Latte" vielfach "in gewünschter Form" gegen feste Punkte anschmiegt. Splines werden verwndet bei der Computergrafik, der Modellierung eines Pfades anhand weniger Punkte ( de.wikipedia Kategorie: Geometrische Modellierung ), dynamische Präsentation von kurzen Scenen, Kurz-Animationen mit dynamisch gesteuerten Clipart-Elementen, beschleunigte Bewegungen gemäß P(t) = P0 + V0·t + 0.5·a·t^2, nutzbar sein und möglichst hohen Für Computerkunst, Computerspielen, die ästetischen Ansprüchen genügen, dynamische Präsentationsdiagramme, usw.

Grafik und Parameterdarstellung Gewichte einer Geraden

In der Grafik wird vielfach die Parameter-Darststellung verwendet. Beispiel: g1,g2 sind "Gewichte" der Geraden. P(t) sind "Zwischen-" Punkte auf der Geraden durch P0 und P1.

x(t) =       x0 + t·(x1-x0) 
x(t) = (1-t)·x0 + t·x1 

x(t) = g0(t)·x0 + g1(t)·x1
y(t) = g0(t)·y0 + g1(t)·y1

P(t) = g0(t)·P0 + g1(t)·P1    mit t = 0...1  läuft  P(t) = P1 ... P2
Beispiel: Richtungsvektor ( Steigung ) dichte Punktfolge

Beispiel: Schaut eine Kamera parallel zum Kurvenverlauf, so wird der Richtungsvektor der Kurve gebraucht. Liegt z.B. eine berechnete, dichte Punktfolge des Kurvenverlaufes vor, so kann numerisch ( genähert ) der jeweilige Richtungsvektor berechnet werden. Bei 3 aufeinander folgenden Punkten P0, P1, P2 geht eine Parabel ( Polygon 2. Grades ). Der Richtungsvektor S1 in P1 ist

s1x = ( x2 - x0 ) / 2
s1y = ( y2 - y0 ) / 2     Vektor  S1 = ( P2 - P0 ) / 2
Beispiel: Bézier-Interpolation Gewichte

Bézier-Kurven verwenden als Interpolationsgewichte Bernsteinpolynom n-ten Grades ( siehe z.B. de.wikipedia Bézier-Kurve ). Die Kurve liegt innerhalb der konvexen Hülle des Kontrollpolygons, d.h. Die Kurve geht nicht durch alle vorgegenen Kontrokkpunkte. Die Interpolationsgewichte ergeben sich z.B. gemäß

 1   = ( t + (1-t) )
 1^2 = ( t + (1-t) )^2  
     =  (1-t)^2  + 2·t·(1-t)   +  t^2

P(t) = g0(t)·P0  +  g1(t)·P1  + g2(t)·P2

 1^3 = ( t + (1-t) )^3 
     =  (1-t)^3  + 3·t·(1-t)^2 + 3·t^2·(1-t) + t^3

 P(t) = g0(t)·P0  +  g1(t)·P1  + g2(t)·P2   +  g3(t)·P3 
Beispiel: Hermiteinterpolation Prinzip

Wie kann ein Pfad anhand weniger Punkte modelliert werden? Welche Annahmen führen zu den Gewichten der Hermiteinterpolation? Siehe z.B. de.wikipedia Kubisch_Hermitescher_Spline , Hermiteinterpolation . Gewichte sind:

gm(t) = (-1·t^3 + 2·t^2 - t)/2
g0(t) = ( 3·t^3 - 5·t^2 + 2)/2
g1(t) = (-3·t^3 + 4·t^2 + t)/2
g2(t) = ( 1·t^3 - 1·t^2    )/2

Wie kann ein Pfad anhand weniger Punkte modelliert werden? Die Lösung kann sowohl für den einfachen Aufbau von geometrischen Objekten und auch für weitere Verfeinerungen von Animationscenen als auch deren Darstellung ( grafsches Rendern ) verwendet werden.

Informativ sind z.B. das Kochanek–Bartels-Verfahren und das SVG-Bild ( wikimedia ) zur TCB-Interpolation .

 Achtung! noch fehlerhaft, wird übearbeitet
Catmull–Rom:  

  m0 = (P2 - P0)/2;        ( Parabelsteigungen )
  m1 = (P3 - P1)/2;

Cardinal:  

    m0 = (1-C)·(P2 - P0) / 2;   mit C = 0 ... 1
    m1 = (1-C)·(P3 - P1) / 2;

    speziell C = 0 ergibt Catmull–Rom 

Kochanek–Bartels: ( TBC )

  m0 = (1-T)·(1+B)·(1+C)/2 ·(P0 - Pm)  +  (1-T)·(1-B)·(1-C)/2 ·(P1 - P0)
  m1 =                                    (1-T)·(1+B)·(1-C)/2 ·(P1 - P0)  +  (1-T)·(1-B)·(1+C)/2 ·(P2 - P1)

  Tension      T = +1 → Tight
               T = −1 → Round
  Bias         B = +1 → Post Shoot
               B = −1 → Pre Shoot
  Continuity   C = +1 → Inverted corners
               C = −1 → Box corners

    speziell T = 0.5 und B = 0.5 liefern
    m0 = (-3·Pm + 2·P0 + P1  + C·(-3·Pm + 4·P0 - P1 ) ) / 8; 
    m1 = (-3·P0 + 2·P1 + P2  - C·(-3·P0 + 4·P1 - P2 ) ) / 8;

    speziell T = 0 und B = 0 liefern
    m0 = ( P1 - Pm - C·( Pm - 2·P0 + P1) ) / 2; 
    m1 = ( P2 - P0 + C·( P0 - 2·P1 + P2) ) / 2

    speziell T = 0 und C = 0 liefern
    m0 = ( P1 - Pm - B·(Pm - 2·P0 + P1) )/2; 
    m1 = ( P2 - P0 - B·(P0 - 2·P1 + P2) )/2;

    speziell T = 0 und B = 0 und C = 0 liefern
    m0 = ( P1 - Pm)/2; 
    m1 = ( P2 - P0)/2;
Wie kann in P(t) = g0(t)·Pm + m0(t)·S0 + g1(t)·P1 + m1(t)·S1 ( mit Hilfe des Vorgängerpunktes Pm ) die Tangenten-Steigung S0 vorgegen werden? Wie kann in P(t) = g0(t)·Pm + m0(t)·S0 + g1(t)·P1 + m1(t)·S1 ( mit Hilfe des Nachfolgerpunktes Pn ) die Tangenten-Steigung S1 vorgegen werden?

Wie wird bei einem geschlossenen Polygonzug verfahren? Ist die Punktfolge P0, P1, P2, P2, ... Pn-1 vorgegeben und soll das Polygon geschlossenen werden, so kann die Punktfolge erweitert zu
Pm = Pn-1;                                  Pn = P0;
Pm,  P0 --- P1 --- P2 --- P2, ..., Pn-1 --- Pn 

Gezeichnet werden die gestrichelten Bereiche.
Wie wird bei einem offenen Polygonzug verfahren?
Für einen linken Geradenanschluß kann gesetzt werden:

Pm = 2·P0 - P1;

Für einen rechten Geradenanschluß kann gesetzt werden:

Pn = 2·P[n-1] - P[n-2];
Für einen linken Parbelanschluß kann gesetzt werden: 

Pm = 3 * (P0 - P1) + P2;

Für einen rechten Parbelanschluß 
kann gesetzt werden:

Pn = 3 * ( P[n-1] - P[n-2] ) + P[n-3];

Wie kann einen automatische, adaptive Schrittweitensteuerung für t eingeführt werden?

Beispiel: Interpolation mit transzendenten Funktionen Prinzip

Als Beispiel seien 4 gewählte Punkt Pt mit t = 0, 1, 2, 3 gegeben: P0(x0,y0), P1(x1,y1), P2(x2,y2), P3(x3,y3)

Als Grundelemente werden Wurzel-Funktionen verwendet. Wie sehen dann die approximierenden Funktionen ( x(t), y(t) ) aus, wobei t in feinen Schritten von 0 bis 3 ( und darüber hinaus ) laufen kann? Gesucht sind die x-Gewichte u0, u1, u2, u3 ( und analog die y-Gewichte für v0, v1, v2, v3 ) für die Gewichtsfunktionen
gi( t ) := √( min + (t - ti)^2 ) Hierbei entspricht die Variable t einem "kontinuierlichen" Index. t0, t1, t2, t3 sind ganzzahlige ( fortlaufende ) Index-Werte.

Das folgenden Gleichungssystem für u0, u1, u2, u3:
x0  = u0 · g1(t0 ) +  u1 · g1(t0) + u2 · g1(t0) + u3 · g1(t0)
x1  = u0 · g1(t1 ) +  u1 · g1(t1) + u2 · g1(t1) + u3 · g1(t1)
x2  = u0 · g1(t2 ) +  u1 · g1(t2) + u2 · g1(t2) + u3 · g1(t2)
x3  = u0 · g1(t3 ) +  u1 · g1(t3) + u2 · g1(t3) + u3 · g1(t3)

vereinfacht ergibt sich

x0 = u0·√(m)   + u1·√(m+1) + u2·√(m+4) + u3·√(m+9)
x1 = u0·√(m+1) + u1·√(m)   + u2·√(m+1) + u3·√(m+4)
x2 = u0·√(m+4) + u1·√(m+1) + u2·√(m)   + u3·√(m+1)
x3 = u0·√(m+9) + u1·√(m+4) + u2·√(m+1) + u3·√(m)

Aus den Gleichungssystemen werden die Lösungen u0, u1, u2, u3 und die Lösungen v0, v1, v2, v3 berechnet. Damit sind die aprroximierenden Funktionen x(t), y(t) bekannt.

x(t) = u0·√(m+(t-0)^2) + u1·√(m+(t-1)^2) + u2·√(m+(t-2)^2) + u3·√(m+(t-3)^2)
y(t) = v0·√(m+(t-0)^2) + v1·√(m+(t-1)^2) + v2·√(m+(t-2)^2) + v3·√(m+(t-3)^2)

Die approximierende Zwischenpunkte P( x(t), y(t) ) ergeben sich dann
für t in feinen Schritten von 0 bis 3 ( und darüber hinaus ), 
wobei für m = 0.5 ( oder experimentell auch 0.2 ... 3 ) gesetzt wird.
Beispiel: Interpolation mit trigonometrischen Funktionen Prinzip

Trigonometrische Funktionen stehen im engen Zusammenhang mit dem Einheitskreis und sind neben NURBS ( nicht-uniforme rationale B-Splines ) für Kurven, Flächen im Computergrafik-Bereich, CGI, CAD und zur Modellierung beliebiger geometrischer Formen geeignet.

Wegen der günstigeren Kontinuumbedingungen werden die Polynom-Gewichtsfunktionen durch trigonometrische Gewichtsfunktionen ersetzt. Zur einfachen Einführung gebe es zunächst lediglich eine Folge von 4 Punkte ( P0, P1 --- P2, P3 ). Bei mehr 4 Punkten werden die Indizes der 4 Punkte jeweils um 1 erhöht. Gezeichnet wird der Bereich zwischen P0 --- P1, indem t = 0 ... 1 durchläuft. P(t) = g0(t)·P0 + g1(t)·P1 + g2(t)·P2 + g3(t)·P3, wobei S0, S1 "Tangenten-Steigungen" entsprechen. Als Gewichte für die Interpolation ( Bild ) werden gewählt:

t-spline.png
Interpolation ( siehe Bild )
co = cos(π·t/2); 
si = sin(π·t/2);

g0(t) = co·(co - 1)/2     rosa 
g1(t) = si·(si + 1)/2     rot 
g2(t) = co·(co + 1)/2     blau 
g3(t) = si·(si - 1)/2     schwarz 

  Zeichenbereich     P1 --- P2  für t = 0 ... 1 
  Punktfolge    P0,  P1 --- P2, P3  

P(t) = g0(t)·P0 + g1(t)·P1 + g2(t)·P2 + g3(t)·P3  


Analog "Extrapolation" ( ohne Bild ):

g0 = (1 - co) / 4;
g1 = (1 + si) / 4;
g2 = (1 + co) / 4;
g3 = (1 - si) / 4; 

Der Seiten-Quelltext enthält den Code. Die Funktion calc_kreis_x_y_arr() verwendet zur Berechnung der Kreispunkte Math.cos(t),Math.sin(t) und wird als schwarzer Kreis dargestellt.

Z.B. mit o={calc_modus:0/1, r0:95, idx:[0, 1, 2, 3, 4], xxx:[95, 0, -95, 0, 95], yyy:[ 0, -95, 0, 95, 95 ]}; berechnet calc_tsplines_x_y_arr(o) aus den 4 Punkten in xxx, yyy einen Array mit x-y-Wertefolgen, die auf einem Kreis liegen. Die interpolierten Punkte werden mit der Funktion draw_tsplines(o) gezeichnet.

Die rechten Darstellungen verwenden idx: [0, 1, 2, 3, 4], xxx: [0, -95, 0, 95, 0], yyy: [95, 0, -120, 0, 95] und idx: [0, 1, 2, 3, 4], xxx: [0, -70, 0, 70, 0], yyy: [120, 0, -120, 0, 120]

Die Darstellung unten verwenden idx: [0, 1, 2, 3, 4], xxx: [ -200, -100, 0, 100, 200], yyy: [ 0, -50, 0, -50, 0]

Die grünen Linien sind mit calc_modus: 0 berechnet (interpoliert). Die roten Linien sind mit den grünen Stützpunkten und mit calc_modus: 1 berechnet (extropoliert). Zu den offenen Linien gehört draw_modus: 'line' ( ansonsten geschlossenes Polygon ).