Non-Uniform Rational B-Spline

Dreidimensionale NURBS-Flächen können komplexe, organische Formen aufweisen. Kontrollpunkte beeinflussen die Richtungen der Oberfläche. Das äußerste Quadrat unten skizziert die X/Y-Ausdehnungen der Oberfläche.

NURBS-Fläche (grün) vom Grad 4, definiert durch 36 Kontrollpunkte (rot) über einem zweidimensionalen Parametergebiet (unteres Gitter).

Non-uniform rational B-Splines (deutsch: nicht-uniforme rationale B-Splines, kurz NURBS) sind mathematisch definierte Kurven oder Flächen, die im Computergrafik-Bereich, beispielsweise im CGI oder CAD, zur Modellierung beliebiger Formen verwendet werden. Die Darstellung der Geometrieinformation erfolgt über stückweise funktional definierte Geometrie-Elemente. Im Prinzip kann jede beliebige technisch herstellbare oder natürliche Form mit Hilfe von NURBS dargestellt werden.

Entwicklung

In den 1950er Jahren wurden besonders im Automobil- und Schiffbau für die fehlerfreie Reproduzierbarkeit technischer Bauteile mathematisch exakte Beschreibungen von Freiformflächen benötigt. Vor dieser Zeit wurden derartige Oberflächen durch einzelne von einem Konstrukteur hergestellte physikalische Modelle beschrieben.

So begann unter anderem der Ingenieur Pierre Étienne Bézier, zu dieser Zeit bei Renault in Frankreich, mit der Entwicklung der nach ihm benannten Bézierkurve. Unabhängig von Bézier arbeitete Paul de Casteljau, angestellt bei Citroën, zur gleichen Zeit auch an diesem mathematischen Problem. Weil Bézier die Ergebnisse seiner Arbeit veröffentlichte, werden heutzutage in der graphischen Datenverarbeitung Splines, deren Kontrollpunkte nicht auf der Kurve selbst liegen, als „Bézier-Spline“ bezeichnet, während der Name von de Casteljau in dem nach ihm benannten Algorithmus fortlebt, der für die numerische Verarbeitung parametrischer Flächen eingesetzt wird. In den 1960er Jahren wurde klar, dass non-uniform rational B-Splines (NURBS) eine Generalisierung von Bézier-Splines sind, die als uniform non-rational B-Splines angesehen werden können.

Zunächst wurden NURBS nur in proprietären CAD-Werkzeugen von Automobilunternehmen verwendet. Später hielten sie Einzug in weiter verbreitete Computergrafik-Anwendungen, beispielsweise die Open Graphics Library (OpenGL).

Auf Systemen von Silicon Graphics wurde erstmals 1989 die Echtzeitverarbeitung und interaktives Rendering von NURBS-Kurven und -Flächen möglich. Auf der CeBit 1994 stellten die Firmen CAS Berlin und CAA in Zusammenarbeit mit der TU Berlin den ersten, auf den Namen NöRBS getauften, interaktiven NURBS-Modellierer für PCs vor. Heutzutage enthalten die meisten professionellen Computergraphik-Anwendungen NURBS-Technologie, die in den meisten Fällen durch die Integration einer NURBS-Engine realisiert ist, die von einer darauf spezialisierten Firma bereitgestellt wird.

Anwendung

NURBS sind bei der computergestützten Konstruktion (CAD) und Fertigung (CAM) beinahe unersetzlich und Teil zahlreicher Industriestandards, wie IGES (Initial Graphics Exchange Specification), STEP (STandard for the Exchange of Product model data) und PHIGS (Programmer's Hierarchical Interactive Graphics System). Im Allgemeinen ist die interaktive Bearbeitung von NURBS-Kurven und -Flächen sehr intuitiv und vorhersagbar. Kontrollpunkte sind stets entweder direkt mit der Kurve oder Fläche verbunden oder wirken, als ob sie mit einem Gummiband verbunden sind. Eine Manipulation der Geometrieelemente kann - am offensichtlichsten bei Bézierkurven - direkt an den Kontrollpunkten durchgeführt werden oder durch übergeordnete Werkzeuge realisiert werden. Derartige Werkzeuge basieren zum Teil auf der Eigenschaft von NURBS, Kurven und Flächen unterschiedlicher Stetigkeit darstellen zu können. Der Begriff Stetigkeit kann in diesem Zusammenhang unterschiedlich definiert werden.

Positions-Stetigkeit (C0) gilt, wenn die Endpunkte zweier Kurven oder Flächen zusammentreffen. Trotzdem können Kurven oder Flächen sich in einem Winkel berühren, der zu einer scharfen Kante oder Ecke an dieser Stelle führt und Störungen bei Lichteffekten verursacht. Die Parallelität der Endvektoren von Kurven oder Flächen bei tangentialer Stetigkeit (C1) führt zu einer Unterbindung scharfer Kanten. Tangentiale Stetigkeit ist oftmals ausreichend, da die Beleuchtung derartiger Geometrien kontinuierlich und damit natürlich erscheint. Bei gleichem Betrag der Endvektoren herrscht Krümmungsstetigkeit (C2). Ein beleuchteter krümmungsstetiger Übergang zeigt keine Veränderung, so dass die zwei Flächen als eine einzige Fläche erscheinen, und wird als optisch perfekt glatt wahrgenommen. Diese Stetigkeitsstufe ist sehr nützlich, wenn die zu realisierende kontinuierliche Oberfläche aus vielen bikubischen Flächenstücken bestehen soll.

Für praktische Belange sind geometrische Stetigkeiten ersten und zweiten Grads (G0 und G1) identisch mit Positions- und tangentialer Stetigkeit (C0 und C1). Geometrische Stetigkeit dritten Grads (G2) unterscheidet sich jedoch von Krümmungsstetigkeit, da die Parametrisierung in diesem Fall ebenfalls stetig ist. In der Praxis kann G2-Stetigkeit einfacher durch die Anwendung von gewöhnlichen (uniform) B-Splines erreicht werden.

Eine andere Definition der Stetigkeit Cn wird in Computer Graphics - Principles and Practice, Abschnitt 11.2, gegeben. Diese Art der Definition gilt zusätzlich für Kurven und Flächen mit einer Basisfunktion höherer als dritter Ordnung. Sowohl Richtung als auch Betrag der n-ten Ableitung der Kurve ($\frac{\partial}{\partial u}C(u)$) oder Fläche müssen in diesem Fall an der Verbindung den gleichen Wert haben. Die Forderung nach gleichem Betrag ist der Hauptunterschied zur oberen Definition. Zusätzlich wird G1-Stetigkeit auf die Forderung nach Parallelität der Tangentenvektoren reduziert, während C1-Stetigkeit den gleichen Betrag erfordert (dies wird in der oberen Spezifikation als C2-Stetigkeit bezeichnet). C2-Stetigkeit nach der letzteren Definition schreibt gleiche Richtung und Betrag für den Krümmungsvektor vor. Dies ist eine wichtige Unterscheidung zur vorherigen Definition, wenn Basisfunktionen höherer Ordnung (als kubisch) für die Kurvendefinition verwendet werden.

Höhere Stetigkeitsgrade sind mit NURBS ebenfalls möglich.

Die Realisierung perfekt glatt aussehender Oberflächen erfordert NURBS-Flächen, die wenigstens C2-Stetigkeit erreichen. Fehler in der Oberfläche können durch Beleuchtung und Reflexion detektiert werden. Eine Methode zur Bewertung einer Fläche basiert auf der Auswertung eines durch Ray Tracing oder Reflexion und Abbildung aufgenommenen Bilds einer Fläche mit weißen auf sie reflektierten Streifen, womit selbst die kleinsten Abweichungen der Fläche aufgedeckt werden können. Diese Methode stammt aus dem Prototypenbau im Automobilbereich, wo die Oberflächenqualität durch Überprüfung der Reflexionen von einem Neonlichthimmel auf der Karosserie sichergestellt wird.

Nachahmungen

Leider sind auch kommerzielle computergrafische Anwendungsprogramme am Markt, die tatsächlich keine NURBS enthalten, dieses aber dennoch behaupten. Diese plumpen Nachahmungen sind erkennbar am Fehlen der Kontrollpunkte auf den Flächen und den damit verbundenen drastischen Einschränkungen bei den Bearbeitungs- und Darstellungsmöglichkeiten. Die Flächen sind lediglich anhand der ursprünglichen Kurven zu bearbeiten und sind somit auch keine Freiformflächen. Darüber hinaus ist naturgemäß auch kein direkter Datenaustausch auf der Basis von NURBS mit anderen Systemen möglich, derartige Flächen müssen grundsätzlich in Polygone konvertiert werden.

Mathematische Beschreibung

NURBS-Kurven und -Flächen haben eine Reihe interessanter Eigenschaften:

• Sie sind invariant für projektive Transformationen.
• Sie bieten eine gemeinsame mathematische Darstellung für sowohl analytische Standardformen (z. B. Kegelschnitte) als auch Freiformflächen.
• Sie reduzieren den Speicheraufwand für geometrische Objekte (im Vergleich zu einfacheren Methoden).
• Sie können durch numerisch stabile und präzise Algorithmen verhältnismäßig schnell ausgewertet werden.
• Sie sind Verallgemeinerungen von nicht-rationalen B-Splines und nicht-rationalen und rationalen Bézier-Kurven und -Flächen. Die Aussage, dass NURBS-Kurven eine Verallgemeinerung von Bézierkurven sind, bedeutet, dass alle Bézierkurven NURBS-Kurven, aber nicht alle NURBS-Kurven Bézierkurven sind.

Eine NURBS-Kurve C(u) ist definiert durch ihren Grad k, eine Menge gewichteter Kontrollpunkte P_i und einen Knotenvektor U. NURBS-Kurven und -Flächen sind Verallgemeinerungen von sowohl B-Splines als auch Bézierkurven und -flächen. Der hauptsächliche Unterschied zu diesen beiden Splinearten ist die Gewichtung der Kontrollpunkte mit den Gewichten w_i. Durch die w_i werden NURBS-Kurven rational (nicht-rationale B-Splines sind ein Spezialfall rationaler B-Splines).

Eine NURBS-Kurve ist über die Summe der mit rationalen B-Spline-Basisfunktionen R_i,p gewichteten Kontrollpunkte

$C(u)=\sum_{i=0}^{n}R_{i,p}(u)P_{i}$

vollständig definiert. Die rationale B-Spline-Basisfunktion errechnet sich aus B-Spline-Basisfunktionen N_i,p der Ordnung des NURBS p und den zu den Kontrollpunkten zugehörigen Gewichten w_i zu

$R_{i,p}(u)=\frac{N_{i,p}(u)w_{i}}{\sum_{j=0}^{n}N_{j,p}(u)w_{j}}$.

Der Parameter $u\in[a,b]$ schaltet im Bereich des Knotenvektors

$\displaystyle U=\{\underbrace{a,\ldots,a}_{p},u_{p+1},\ldots,u_{r-p-1},\underbrace{b,\ldots,b}_{p}\}$

der Länge r die einzelnen Segmente der Spline-Kurve aktiv. Die Elemente des Knotenvektors sind monoton steigend.

Der Knotenvektor besteht aus Parameterwerten, die den Einfluss der Kontrollpunkte auf die NURBS-Kurve festlegen. Die Anzahl der Knoten ist immer gleich der Anzahl der Kontrollpunkte plus dem Grad der Kurve plus eins. Beispielsweise hat eine Kurve dritten Grades mit vier Kontrollpunkten acht Knoten (4 + 3 + 1 = 8). Für den Graphik-Designer sind Knoten gewöhnlich nicht hilfreich; sie werden nur für interne Berechnungen benötigt. Aus diesem Grund sind Knoten in vielen Graphik-Design-Programmen nicht änderbar oder überhaupt sichtbar. Neuere Versionen von NURBS-Software (z. B. Alias Maya) erlauben interaktive Änderungen an Knotenpositionen, was allerdings bedeutend weniger intuitiv ist als Änderungen an Kontrollpunkten.

Die Werte des Knotenvektors müssen in aufsteigender Reihenfolge vorliegen. Damit ist (0, 0, 1, 2, 3) gültig, (0, 0, 2, 1, 3) dagegen nicht. Die einzelnen Knotenwerte haben keine Aussage für sich selbst; einzig und allein die Verhältnisse der Differenzen zwischen den Knotenwerten haben eine Bedeutung. Demzufolge ergeben die Knotenvektoren (0, 0, 1, 2, 3), (0, 0, 2, 4, 6), und (1, 1, 2, 3, 4) alle die gleiche Kurve. Weiterhin muss die Vielfachheit eines Knotens kleiner gleich sein als der Grad der Kurve (kein Knoten darf öfter als der Grad der Kurve auftauchen). Für NURBS ersten Grades ist jeder Knoten gepaart mit einem Kontrollpunkt.

Die Ordnung einer NURBS-Kurve ist festgelegt durch die Anzahl benachbarter Kontrollpunkte, die die Kurve beeinflussen. Die Kurve setzt sich mathematisch aus Polynomen zusammen, deren Grad eins kleiner als die Ordnung der Kurve ist (k = p − 1). Also werden Kurven zweiter Ordnung (die durch lineare Polynome dargestellt werden) lineare Kurven, Kurven dritter Ordnung quadratische Kurven und Kurven vierter Ordnung kubische Kurven genannt. Die Anzahl der Kontrollpunkte muss größer oder gleich der Ordnung der Kurve sein.

In der Praxis werden am häufigsten kubische Kurven gebraucht. Kurven fünften oder sechsten Grades sind manchmal nützlich, gerade für Ableitungen, Kurven höheren Grades werden in der Praxis aber nie benutzt, da sie zu internen numerischen Problemen führen und ihre Berechnung tendenziell unverhältnismäßig viel Berechnungszeit erfordert.

Im Gegensatz zu nicht-rationalen Kurven, die nicht geeignet sind, um Kreise darzustellen, klappt dies mit NURBS problemlos. Der Einheitskreis in der x-y-Ebene kann beispielsweise als NURBS-Kurve vom Grad 2 mit Knotenvektor (0,0,1,1,2,2,3,3,4,4) und folgenden Kontrollpunkten und Gewichten konstruiert werden.

x	y	z	Gewicht
1	0	0	1
1	1	0	√2 / 2
0	1	0	1
−1	1	0	√2 / 2
−1	0	0	1
−1	−1	0	√2 / 2
0	−1	0	1
1	−1	0	√2 / 2
1	0	0	1

Während eine NURBS-Kurve ausschließlich in eine parametrische Richtung u aufgespannt ist, wird eine NURBS-Fläche durch zwei Parameter, genannt u und v, aufgespannt. Die Kurve kann durch Auswertung an unterschiedlichen Parametern im kartesischen zwei- oder dreidimensionalen Raum abgebildet werden. Analog erfolgt die Abbildung einer NURBS-Fläche im kartesischen Raum durch Auswertung mit verschiedenen Werten für zwei Parameter.

NURBS-Flächen

$S(u,v)=\sum_{i=0}^n\sum_{j=0}^mR_{i,j}(u,v)P_{i,j}$

sind definiert durch ein Kontrollgitter P_i,j und die rationale Basisfunktion

$R_{i,j}(u,v)=\frac{N_{i,p}(u)N_{j,q}(v)w_{i,j}}{\sum_{k=0}^n\sum_{l=0}^mN_{k,p}(u)N_{l,q}(v)w_{k,l}}$

mit einer zweidimensionalen Gewichtematrix w_i,j. Die zweite Dimension der Fläche S(u,v) mit dem Parameter v wird geschaltet durch den analog zu U aufgebauten Knotenvektor

$V=\{\underbrace{c,\ldots,c}_{q},v_{q+1},\ldots,v_{s-q-1},\underbrace{d,\ldots,d}_{q}\}$

mit der Ordnung q und der Länge s.

Einfache Erklärung eines komplexen Sachverhaltes

In der griechischen Antike hat Pythagoras die mathematische Formel entdeckt, mit der sich ein rechtwinkliges Dreieck berechnen lässt. In den Fünzigern des 20. Jahrhunderts hat Bézier die mathematische Formel entdeckt, mit der sich eine geschwungene Kurve beschreiben lässt. Die Kurve wird damit durch wenige sogenannte Kontrollpunkte definiert.

In der Folge haben Forscher entdeckt, dass diese Bézierkurven noch nicht ausreichend sind, um beispielsweise einen Kreis exakt darzustellen. Daraufhin wurden mathematische Formeln entwickelt, bei denen die einzelnen Kontrollpunkte unterschiedlich stark (Non uniform) auf den Kurvenverlauf einwirken können, die sogenannten B-Splines. Der Begriff Splines ist historisch und stammt aus dem Schiffbau. Linealartige biegsame Metallstreifen, sogenannte Straklatten (engl. splines), wurden seitlich mit Gewichten beschwert und konnten somit eine definierte Kurve darstellen. Mehrere dieser Kurven hintereinander stellten die Spanten dar, die wiederum den Rumpf des Schiffes ergaben.

Später wurden dann mathematische Formeln entwickelt, die sowohl Béziers Formel als auch die B-Splines verallgemeinerten, die sogenannten Non uniformen rationalen B-Splines. Damit kann man also beliebige Kurven darstellen und wenn man nicht nur eine Richtung („Länge“) wie bei einer Kurve, sondern eine zweite („Breite“) hinzufügt, können damit beliebige Flächen dargestellt werden. Theoretisch können diese Flächen beliebig komplex und groß sein. Da der Aufwand zur Berechnung der Formeln allerdings mit zunehmender Komplexität stark ansteigt und auch mit einem leistungsfähigen Computer nicht mehr in angemessener Zeit berechnet werden kann, werden kompliziertere Flächen durch mehrere aneinandergesetzte sogenannte Patches dargestellt. In der industriellen Produktion werden mittlerweile fast ausschließlich NURBS eingesetzt, um jede Art von herzustellendem Objekt (Joghurtbecher, Raketentriebwerke, Sonnenbrillen, usw.) mathematisch exakt abbilden zu können.

Literatur

• Les Piegl, Wayne Tiller: The NURBS Book. Monographs in Visual Communication. Springer, 2000.
• David F. Rogers: An Introduction to NURBS With Historical Perspective. Academic Press, 2001.
• Lyle Ramshaw: Blossoming: A connect-the-dots approach to splines. Research Report 19, Compaq Systems Research Center, Palo Alto, CA, June 1987.
• James D. Foley, Andries van Dam, Steven K. Feiner, John F. Hughes: Computer Graphics - Principles and Practice. 2nd ed. Addison Wesley 1996.
• David Salomon: Curves and Surfaces for Computer Graphics. 2006 Springer Science+Business Media Inc. ISBN 0-387-24196-5.