Non-Uniform Rational B-Spline

Grundidee und Bedeutung

Non-uniform rational B-Splines, deutsch nicht-uniforme rationale B-Splines und kurz NURBS, sind mathematisch definierte Kurven und Flächen. Sie dienen in der Computergrafik, besonders in CGI, CAD und CAM, zur Modellierung nahezu beliebiger Formen. Ein NURBS kann jeden beliebigen nicht verzweigenden, stetigen Linienzug darstellen. In praktischen Modellen wird eine komplexe Gesamtform jedoch meist aus mehreren stückweise definierten Geometrieelementen beziehungsweise Patches zusammengesetzt, weil der Rechenaufwand mit der Komplexität stark wächst.

Die Form wird durch Kontrollpunkte beeinflusst. Diese liegen nicht unbedingt auf der Kurve oder Fläche, sondern ziehen sie anschaulich wie über Gummibänder in bestimmte Richtungen. Jedem Kontrollpunkt kann ein Gewicht zugeordnet werden, das die Stärke seines Einflusses bestimmt. Außerdem legt ein Knotenvektor fest, in welchen Parameterbereichen die einzelnen Teile der Kurve wirksam sind.

NURBS bilden analytische Standardformen wie Kegelschnitte ebenso wie freie, organische Formen in einem gemeinsamen mathematischen System ab. Sie sind Verallgemeinerungen nicht-rationaler B-Splines sowie nicht-rationaler und rationaler Bézierkurven und -flächen. Deshalb ist jede Bézierkurve eine NURBS-Kurve, aber nicht jede NURBS-Kurve eine Bézierkurve. NURBS sind invariant gegenüber projektiven Transformationen, benötigen gegenüber einfacheren Darstellungsverfahren vergleichsweise wenig Speicher und können mit numerisch stabilen, präzisen Algorithmen verhältnismäßig schnell ausgewertet werden.

Entwicklung und Einsatz

In den 1950er Jahren benötigten besonders der Automobil- und Schiffbau mathematisch exakte Beschreibungen von Freiformflächen, damit technische Bauteile fehlerfrei reproduziert werden konnten. Zuvor beschrieb man solche Oberflächen mithilfe einzelner physischer Modelle. Pierre Étienne Bézier bei Renault und Paul de Casteljau bei Citroën arbeiteten unabhängig voneinander an mathematischen Lösungen. Bézier veröffentlichte seine Ergebnisse; de Casteljaus Name lebt im de-Casteljau-Algorithmus zur numerischen Verarbeitung parametrischer Flächen fort. In den 1960er Jahren wurde erkannt, dass NURBS eine Verallgemeinerung von Bézier-Splines sind.

Zunächst kamen NURBS nur in proprietären CAD-Systemen von Automobilunternehmen zum Einsatz, später auch in verbreiteten Computergrafik-Anwendungen wie OpenGL. 1989 ermöglichten Systeme von Silicon Graphics erstmals die Echtzeitverarbeitung und das interaktive Rendering von NURBS-Kurven und -Flächen. Auf der Cebit 1994 präsentierten CAS Berlin und CAA gemeinsam mit der TU Berlin den interaktiven PC-NURBS-Modellierer „NöRBS“. Heute ist NURBS-Technologie in den meisten professionellen Computergrafik-Anwendungen enthalten.

Für die computergestützte Konstruktion und Fertigung sind NURBS beinahe unersetzlich. Sie gehören zu Industriestandards wie IGES, STEP und PHIGS. Kontrollpunkte ermöglichen eine intuitive und vorhersagbare Bearbeitung; alternativ können übergeordnete Werkzeuge die Geometrie verändern. In der industriellen Produktion lassen sich damit herzustellende Gegenstände wie Joghurtbecher, Motorgehäuse oder Sonnenbrillen mathematisch exakt abbilden.

Mathematischer Aufbau einer Kurve

Eine NURBS-Kurve C(u) wird durch den Grad k ihrer Basispolynome, gewichtete Kontrollpunkte Pᵢ mit Gewichten wᵢ und einen Knotenvektor U definiert. Der Grad ist um eins kleiner als die Ordnung p, also k = p − 1 beziehungsweise p = k + 1. Die Kurve lautet

C(u) = ∑ᵢ₌₀ⁿ Rᵢ,ₖ(u)Pᵢ.

Dabei sind Rᵢ,ₖ die rationalen B-Spline-Basisfunktionen:

Rᵢ,ₖ(u) = Nᵢ,ₖ(u)wᵢ / ∑ⱼ₌₀ⁿ Nⱼ,ₖ(u)wⱼ.

Nᵢ,ₖ sind die gewöhnlichen B-Spline-Basisfunktionen des Grades k. Die Gewichte wᵢ machen die Darstellung rational und regeln den Einfluss der einzelnen Kontrollpunkte. Der Parameter u ∈ [a,b] durchläuft den Bereich des Knotenvektors und aktiviert dabei die verschiedenen Segmente der Spline-Kurve.

Für die Kontrollpunktmenge 𝓟 = {Pᵢ | Pᵢ = (x,y), x,y ∈ ℝ, i = 0,…,n} gilt |𝓟| = m = n + 1. Entsprechend enthält die Gewichtsmenge 𝓦 = {wᵢ ∈ ℝ, i = 0,…,n} ebenfalls m = n + 1 Elemente.

Knoten, Ordnung und Stetigkeit

Der Knotenvektor U besteht aus aufsteigend angeordneten Parameterwerten uᵢ. Sie bestimmen, wie die Kontrollpunkte auf die Kurve einwirken. Die Zahl der Knoten ist gleich der Zahl der Kontrollpunkte plus Kurvengrad plus eins:

|U| = r = m + k + 1 = n + p + 1.

Eine Kurve dritten Grades mit vier Kontrollpunkten besitzt daher acht Knoten: 4 + 3 + 1 = 8. Die einzelnen Knotenwerte sind für sich nicht entscheidend; nur die Verhältnisse ihrer Differenzen zählen. Deshalb erzeugen (0,0,1,2,3), (0,0,2,4,6) und (1,1,2,3,4) dieselbe Kurve. Eine nicht aufsteigende Folge wie (0,0,2,1,3) ist ungültig. Die Vielfachheit eines Knotens darf höchstens dem Grad der Kurve entsprechen. Für NURBS ersten Grades ist jeder Knoten einem Kontrollpunkt zugeordnet.

Die Ordnung p gibt an, wie viele benachbarte Kontrollpunkte die Kurve beeinflussen. Die Zahl m der Kontrollpunkte muss mindestens so groß wie p sein. Kurven zweiter Ordnung beruhen auf linearen Polynomen und heißen linear; Kurven dritter Ordnung sind quadratisch, Kurven vierter Ordnung kubisch. In der Praxis werden vor allem kubische Kurven verwendet. Kurven fünften oder sechsten Grades können besonders für Ableitungen nützlich sein. Noch höhere Grade werden praktisch nicht eingesetzt, weil sie numerische Probleme und einen unverhältnismäßig hohen Rechenaufwand verursachen können.

Beim Verbinden von Kurven oder Flächen werden verschiedene Grade geometrischer Stetigkeit unterschieden:

• 𝓖⁰, Positionsstetigkeit: Die Endpunkte treffen zusammen. Ein Winkel und damit eine sichtbare Kante oder Ecke ist trotzdem möglich.

• 𝓖¹, tangentiale Stetigkeit: Die Endvektoren sind parallel, sodass keine scharfe Kante auftritt. Dies genügt häufig für eine kontinuierlich und natürlich wirkende Beleuchtung.

• 𝓖², Krümmungsstetigkeit: Angrenzende Kurven besitzen am gemeinsamen Punkt beziehungsweise Flächen entlang ihrer gemeinsamen Linie gleiche Krümmungswerte. Dies ist etwa bei überströmten Flächen erforderlich, um ein Ablösen der Strömung auszuschließen.

Höhere Stetigkeitsgrade sind ebenfalls möglich. Glatte Oberflächen benötigen mindestens 𝓖¹-Stetigkeit. Kleine Oberflächenfehler lassen sich durch Beleuchtung und Reflexion erkennen, beispielsweise durch weiße reflektierte Streifen. Im Automobil-Prototypenbau wird dazu die Spiegelung eines Neonlichthimmels auf der Karosserie geprüft.

Flächen und Kreis als Beispiel

Eine NURBS-Kurve besitzt eine parametrische Richtung u. Eine NURBS-Fläche wird dagegen durch zwei Parameter u und v aufgespannt und über ein zweidimensionales Kontrollgitter Pᵢ,ⱼ gesteuert. Ihre Definition lautet

S(u,v) = ∑ᵢ₌₀ⁿ ∑ⱼ₌₀ᵐ Rᵢ,ⱼ(u,v)Pᵢ,ⱼ,

mit

Rᵢ,ⱼ(u,v) = Nᵢ,ₚ(u)Nⱼ,ᵩ(v)wᵢ,ⱼ / [∑ₖ₌₀ⁿ ∑ₗ₌₀ᵐ Nₖ,ₚ(u)Nₗ,ᵩ(v)wₖ,ₗ].

Dabei bildet wᵢ,ⱼ eine zweidimensionale Gewichtematrix. Zusätzlich zum Knotenvektor U für u gibt es für v einen analog aufgebauten Knotenvektor V. Durch die Auswertung verschiedener Parameterwerte wird die Kurve im zwei- oder dreidimensionalen kartesischen Raum beziehungsweise die Fläche im kartesischen Raum abgebildet.

Ein wichtiges Beispiel ist der Kreis: Nicht-rationale Kurven können Kreise nicht exakt darstellen, NURBS dagegen schon. Der Einheitskreis in der xy-Ebene lässt sich als NURBS-Kurve zweiten Grades mit dem Knotenvektor (0,0,0,1,1,2,2,3,3,4,4,4) konstruieren. Die neun Kontrollpunkte sind (1,0,0), (1,1,0), (0,1,0), (−1,1,0), (−1,0,0), (−1,−1,0), (0,−1,0), (1,−1,0) und erneut (1,0,0). Die vier auf den Koordinatenachsen liegenden Zwischenpunkte und der wiederholte Endpunkt haben das Gewicht 1; die diagonalen Punkte (±1,±1,0) erhalten jeweils das Gewicht √2/2. So entsteht trotz des polygonalen Kontrollpunktgerüsts ein mathematisch exakter Kreis.