Splines: Theorie und Praxis

In diesem Tutorial dreht sich alles um Splines. Splines sind nichts weiter als Kurven, die durch eine Funktion zwischen mehreren Knoten (Wegpunkte) repräsentiert werden. Vor allem in der Computergrafik sind Splines häufig verwendete Konstrukte.
Das Tutorial ist in zwei Abschnitte eingeteilt. In dem ersten Abschnitt werden die theoretischen Grundlagen erläutert. In dem zweiten Abschnitt wird anhand von Codebeispielen die Implementierung eines Splines demonstriert.

Theorie

Ein Spline besteht aus einer polynomischen Funktion, deren Koeffizienten das Aussehen der daraus gewonnenen Kurve bestimmen.  Für einen Spline ist es also entscheidend wie viele Koeffizienten er hat und welchen wert sie besitzen.
Der einfachste Spline ist der lineare Spline. Dieser wird durch ein Polynom ersten grades beschrieben und verläuft durch zwei Knoten. Er ist letztendlich nur eine Gerade, die zwei Knoten miteinander verbindet. Je mehr Knoten durch die Kurve verbunden werden sollen, desto höheren grades muss das Polynom sein. Für sieben Knoten beispielsweise wird ein Polynom sechsten Grades benötigt. Das liegt daran, dass jeder Knoten
eine neue Information für die Kurve liefert. Diese Information muss letztendlich in in das Polynom einfließen, damit das Polynom diesen Knoten durchlaufen kann. Das geschieht durch die einzelnen Koeffizienten. Als Beispiel sind hier einmal drei verschiedene Kurven mit ihren Wegpunkten dargestellt:
Gut zu erkennen ist, dass der Grad des Polynoms zunehmen muss, da die einzelnen Knoten sonst nicht passiert werden können.
Wenn alle Knoten die man passieren möchte bekannt sind so kann man diese in ein Lineares Gleichungssystem einsetzen und damit die Koeffizienten berechnen. Nehmen wir an, wir haben die Knoten K1(3,4), K2(5,2) und K3(8,4), so würde unser LGS wie folgt aussehen:
Jedem wird schnell klar, dass je mehr Knoten die Kurve durchlaufen muss, desto höheren Grades wird das Polynom und desto aufwändiger wird der dazu benötigte Rechenaufwand. Um dieses Problem zu umgehen wird ein einfacher Trick angewandt: Ein Polynom hohen Grades wird in mehrere kleine Polynome niedrigen grades Aufgeteilt. Am einfachsten geht das indem jeweils zwischen zwei Knoten ein eigenes Polynom berechnet wird. In der Praxis wird hierfür meist ein kubisches Polynom (dritten Grades) benutzt. Ein kubisches Polynom ist das Polynom mit dem niedrigsten Grad, das einen Wendepunkt besitzt. Wendepunkte sind extrem nützlich um beispielsweise von einer Links- in eine Rechtskurve zu wechseln.
Wie bereits beschrieben benötigt ein kubisches Polynom  vier Koeffizienten a, b, c und d. Da jedoch nur noch zwei Knoten. Es werden also noch zusätzliche Informationen benötigt um das LGS aufzustellen.
Zuerst einmal muss sichergestellt werden, dass die Kurve durch beide Wegpunkte verläuft. Es gilt also:
Zusätzlich sollen die beiden Funktionen, die sich an einem Knoten treffen die gleiche Steigung und Krümmung aufweisen. Dies ist wichtig um keine Kanten an den Knoten entstehen zu lassen.
Damit sind alle Informationen die für das LGS benötigt werden gegeben.

Das letzte Problem das gelöst werden muss ist die Beschränkung der Kurve auf die Variable x. Jede Funktion f(x) besitzt nur einen Wert für eine bestimmte Zahl x. Der Spline soll jedoch beliebige Kurven in dem zweidimensionalen Raum machen können.
Dazu ist eine dritte Variable u nötig. sowohl der x- wie auch der y-Wert sind von dieser Variablen abhängig. Für beide Achsen muss nun eine eigene Funktion berechnet werden. Für die x-Achse ist es die Veränderung des x-Wertes im Bezug auf u und für die y-Achse die Veränderung des y-Wertes. Für jeden Knotenpunkt wird dabei immer angenommen, dass u von 0 bis 1 Verläuft. Die jeweiligen x- und y-Werte verlaufen von einem Knoten bis zum Anderen Knoten.
Wenn beispielsweise die Knoten K1(3,4) und K2(5,2) gegeben sind, so gilt für die Funktion des x-Wertes:
Für beide Achsen werden dabei unterschiedliche Funktionen aufgestellt die nichts miteinander zu tun haben. Um die letztendliche Position im Koordinatensystem zu bestimmen werden die Funktionen für beide Achsen kombiniert.
Da die Achsen unabhängig voneinander sind kann man dieses für beliebig viele Dimensionen fortsetzen. Ein 3D-Spline ist somit auch kein Problem. Das ist auch schon alles. Wer das ganze noch einmal ausführlicher beschrieben haben möchte, der kann sich folgendes PDF einmal anschauen.

Praxis

Das hier gezeigte Beispiel ist eine C#-Portierung des Java-Algorithmus für natürliche Splines von Tim Lambert. Auf seiner Homepage hat er weitere Beispiele die man sich ansehen sollte. Der Algorithmus kann natürlich ohne Probleme in Basic oder C++ portiert werden.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Spline
{
    class CubicFunction
    {
        public float a { get; set; }
        public float b { get; set; }
        public float c { get; set; }
        public float d { get; set; }

        public CubicFunction(float a, float b, float c, float d)
        {
            this.a = a;
            this.b = b;
            this.c = c;
            this.d = d;
        }

        public float eval(float u)
        {
            return (((d * u) + c) * u + b) * u + a;
        }
    }
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Spline
{
    class CubicSpline
    {
        private float[] XValues { get; set; }
        private float[] YValues { get; set; }

        public CubicFunction[] XCubic { get; private set; }
        public CubicFunction[] YCubic { get; private set; }

        public void setKnots(float[] x, float[] y)
        {
            XValues = x;
            YValues = y;
        }

        private CubicFunction[] CalcNaturalFunction(float[] values)
        {
            int n = values.Length - 1;

            float[] gamma = new float[n + 1];
            float[] delta = new float[n + 1];
            float[] D = new float[n + 1];


            gamma[0] = 1.0f / 2.0f;
            for (int i = 1; i < n; i++)
            {
                gamma[i] = 1 / (4 - gamma[i - 1]);
            }
            gamma[n] = 1 / (2 - gamma[n - 1]);

            delta[0] = 3 * (values[1] - values[0]) * gamma[0];
            for (int i = 1; i < n; i++)
            {
                delta[i] = (3 * (values[i + 1] - values[i - 1]) - delta[i - 1]) * gamma[i];
            }
            delta[n] = (3 * (values[n] - values[n - 1]) - delta[n - 1]) * gamma[n];

            D[n] = delta[n];
            for (int i = n - 1; i >= 0; i--)
            {
                D[i] = delta[i] - gamma[i] * D[i + 1];
            }

            CubicFunction[] C = new CubicFunction[n];
            for (int i = 0; i < n; i++)
            {
                C[i] = new CubicFunction(values[i], D[i], 3 * (values[i + 1] - values[i]) - 2 * D[i] - D[i + 1],
                       2 * (values[i] - values[i + 1]) + D[i] + D[i + 1]);

            }
            return C;
        }

        public void CalcSpline()
        {
            XCubic = CalcNaturalFunction(XValues);
            YCubic = CalcNaturalFunction(YValues);
        }
    }
}
Viele Algorithmen für Catmull-Rom-Splines ignorieren den ersten und letzten knoten des Spline. Mit diesem Algorithmus habe ich versucht eine Funktion für alle Knoten berechnen zu lassen. Die Tension des Splines ist dabei einstellbar. Für kleine Werte der Tension funktioniert der Algorithmus, bei großen Werten kann es zu Kringelbildung kommen. Ich stelle ihn jedoch trotzdem online.
private CubicFunction[] CalcCatmulRomFunction(float[] values, float tension)
        {
            int n = values.Length -1;

            float[] slope = new float[n+1];
            slope[0] = tension * (values[1] - values[0]);
            slope[n-1] = tension * (values[n] - values[n-1]);

            for (int i = 1; i < n - 1; i++)
            {
                slope[i] = tension * (values[i + 1] - values[i - 1]) / 2;
            }

            CubicFunction[] returnvalue = new CubicFunction[n];

            for (int i = 0; i < n; i++)
            {
                returnvalue[i] = new CubicFunction(values[i],
                                                   slope[i],
                                                   3 * (values[i + 1] - values[i]) - 2 * slope[i] - slope[i + 1],
                                                   2 * (values[i] - values[i + 1]) + slope[i] + slope[i + 1]);
            }

            return returnvalue;
        }
Bookmark and Share

1 Kommentare:

Mayray hat gesagt…

If you are facing problems in Computer Science please visit http://unn.edu.ng/departments/computer-science of the University of Nigeria to get them solved via e-mail communication.

Kommentar veröffentlichen