Quelltext der Seite Non-Uniform Rational B-Spline

[[Datei:NURBS 3-D surface.gif|mini|400px|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.]]
[[Datei:NURBS surface.png|mini|NURBS-Fläche (grün) vom Grad 4, definiert durch 36 Kontrollpunkte (rot) über einem zweidimensionalen Parametergebiet (unteres Gitter).]]
{{lang|en|'''Non-uniform rational [[B-Spline]]s'''}} (deutsch: ''nicht-uniforme rationale B-Splines'', kurz ''NURBS'') sind [[Mathematik|mathematisch]] definierte [[Kurve (Mathematik)|Kurven]] oder [[Fläche (Mathematik)|Flächen]], die im [[Computergrafik]]-Bereich, beispielsweise im [[Computer Generated Imagery|CGI]] oder [[CAD]], zur Modellierung beliebiger Formen verwendet werden. Ein NURBS kann jeden beliebigen nicht-verzweigenden stetigen Linienzug darstellen.
Im Computergrafik-Bereich wird die Geometrieinformation jedoch meist über ''stückweise'' [[Funktion (Mathematik)|funktional]] definierte Geometrie-Elemente dargestellt, statt die komplette Formgebung über einen einzigen NURBS abzubilden.

== Entwicklung ==
In den [[1950er|1950er Jahren]] wurden besonders im [[Automobilbau|Automobil-]] und [[Schiffbau]] für die fehlerfreie Reproduzierbarkeit technischer Bauteile mathematisch exakte Beschreibungen von [[Freiformfläche]]n benötigt. Vor dieser Zeit wurden derartige Oberflächen durch einzelne von einem [[Konstrukteur]] hergestellte [[physik]]alische [[Modell]]e beschrieben.

So begann unter anderem der [[Ingenieur]] [[Pierre Bézier|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 [[Spline]]s, deren Kontrollpunkte nicht auf der [[Funktionsgraph|Kurve]] selbst liegen, als „Bézier-Spline“ bezeichnet, während der Name von de Casteljau in dem nach ihm benannten [[De-Casteljau-Algorithmus|Algorithmus]] fortlebt, der für die [[Numerik|numerische]] Verarbeitung [[Reguläre Fläche|parametrischer Flächen]] eingesetzt wird. In den 1960er Jahren wurde klar, dass {{lang|en|'''non-uniform rational B-Splines'''}} (''NURBS'') eine Generalisierung von Bézier-Splines sind, die als {{lang|en|uniform non-rational [[B-Spline]]s}} angesehen werden können.

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

Auf Systemen von [[Silicon Graphics]] wurde erstmals 1989 die [[Echtzeit]]verarbeitung und [[interaktiv]]es [[Bildsynthese|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 Computergrafik-Anwendungen NURBS-Technologie, die in den meisten Fällen durch die Integration einer [[Grafik-Engine|NURBS-Engine]] realisiert ist, die von einer darauf spezialisierten Firma bereitgestellt wird.

== Anwendung ==
NURBS sind bei der computergestützten Konstruktion (CAD) und Fertigung ([[Computer-aided manufacturing|CAM]]) beinahe unersetzlich und Teil zahlreicher [[Industriestandard]]s, wie [[Initial Graphics Exchange Specification|IGES]] ({{lang|en|Initial Graphics Exchange Specification}}), [[Standard for the exchange of product model data|STEP]] ({{lang|en|STandard for the Exchange of Product model data}}) und [[PHIGS]] ({{lang|en|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 seien sie mit einem Gummiband verbunden. Eine Manipulation der Geometrieelemente kann –&nbsp;am offensichtlichsten bei Bézierkurven&nbsp;– direkt an den Kontrollpunkten durchgeführt oder durch übergeordnete Werkzeuge realisiert werden. Derartige Werkzeuge basieren zum Teil auf der Eigenschaft von NURBS, Kurven und Flächen unterschiedlicher [[Stetige Funktion|Stetigkeit]] darstellen zu können.

Hierbei werden unterschiedlich starke Stetigkeitsforderungen gestellt. Neben der üblichen <math>\mathcal C</math>-Stetigkeit wird hier auch die geometrische Stetigkeit betrachtet:
* <math>\mathcal G^0:</math> ''Positions-Stetigkeit'' 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.
* <math>\mathcal G^1:</math> Bei ''tangentialer Stetigkeit'' verhindert die Parallelität der Endvektoren von Kurven oder Flächen das Auftreten scharfer Kanten. Tangentiale Stetigkeit ist oftmals ausreichend, da die Beleuchtung derartiger Geometrien kontinuierlich und damit natürlich erscheint.
* <math>\mathcal G^2:</math> ''Krümmungsstetigkeit'' herrscht bei [[Krümmung|gleichen Krümmungswerten]] im gemeinsamen Punkt von aneinander grenzender Kurven, respektive gemeinsamen Linien aneinander grenzender Flächen.<!-- 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. // Gilt bereits für G1-Stetigkeit. --> Diese Stetigkeit ist beispielsweise notwendig für überströmte Flächen, um ein Ablösen der Strömung ausschließen zu können.

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

Die Realisierung glatter Oberflächen erfordert NURBS-Flächen, die wenigstens <math>\mathcal G^1</math>-Stetigkeit erreichen. Fehler in der Oberfläche können durch [[Beleuchtung]] und [[Reflexion (Physik)|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 [[Prototyp (Technik)|Prototypenbau]] im Automobilbereich, wo die Oberflächenqualität durch Überprüfung der Reflexionen von einem [[Neonröhre|Neonlichthimmel]] auf der [[Karosserie]] sichergestellt wird.

== 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.&nbsp;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 <math>\textstyle C(u)</math> ist definiert durch den Grad <math>\textstyle k</math> ihrer Basispolynome (= ''Ordnung p'' der NURBS-Kurve – 1), eine Menge <math>\textstyle \mathbb{P}</math> gewichteter (<math>\textstyle w_{i}</math>) Kontrollpunkte <math>\textstyle P_{i}</math> und einen Knotenvektor <math>\textstyle U</math>. 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 <math>\textstyle w_{i}</math>. Durch die <math>\textstyle w_{i}</math> werden NURBS-Kurven rational.<!-- (nicht-rationale B-Splines sind ein Spezialfall rationaler B-Splines). // was auch immer dieser Satz aussagen soll ~ vmtl. fehlerhafte Übersetzung von non-uniform rational b-spline? -->

Eine NURBS-Kurve ist über die Summe der mit rationalen B-Spline-Basisfunktionen <math>\textstyle R_{i,k}</math> gewichteten Kontrollpunkte <math>\textstyle P_{i}</math> , also über die Formel

:<math>C(u)=\sum_{i=0}^{n}R_{i,k}(u)P_{i}</math>

vollständig definiert. Die rationale B-Spline-Basisfunktion errechnet sich aus [[B-Spline#Definition|B-Spline-Basisfunktionen <math>\textstyle N_{i,k}</math>]] des Grads der Basispolynome <math>\textstyle k</math> und den zu den Kontrollpunkten zugehörigen Gewichten <math>\textstyle w_{i}</math> zu

:<math>R_{i,k}(u)=\frac{N_{i,k}(u)w_{i}}{\sum_{j=0}^{n}N_{j,k}(u)w_{j}}</math>.

Der Parameter <math>\textstyle u \in [a,b]</math> schaltet im Bereich des Knotenvektors

:<math>\displaystyle U=\{\underbrace{a_{(0)},\ldots,a_{(p-1)}}_{p},u_{p},\ldots,u_{n},\underbrace{b_{(n+1)},\ldots,b_{(n+p)}}_{p}\}</math>

die einzelnen Segmente der Spline-Kurve aktiv. Die Elemente des Knotenvektors sind monoton steigend, wobei alle <math>\textstyle a_{(i)} = a_{(j)}</math> sowie alle <math>\textstyle b_{(i)} = b_{(j)}</math> sind.

=== Randbedingungen und Definitionen ===
'''Kontrollpunkte'''
:<math> \mathbb{ P } = \{ P_{i} \mid P_{i} = ( x , y ) \text{ mit } x,y \in \R \text{ und } i=0..n \in \N \} </math>
:<math> |\mathbb{ P }|  = m = (n+1) </math>
:<math> \mathbb{ W } = \{ w_{i} \in \R , i=0..n \in \N \} </math>
:<math> |\mathbb{ W }| = m = (n+1) </math>

'''Knotenvektor'''

Der Knotenvektor <math>\textstyle U</math> besteht aus Parameterwerten <math>\textstyle u_{i}</math>, die den Einfluss der Kontrollpunkte <math>\textstyle P_{i}</math> auf die NURBS-Kurve festlegen. Die Anzahl der Knoten ist immer gleich der Anzahl der Kontrollpunkte plus dem Grad der Kurve plus eins (<math>\textstyle |U| = r = m + k + 1 = n + p + 1</math>). 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.&nbsp;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.

'''Ordnung einer NURBS-Kurve'''

Eine NURBS-Kurve ist von der Ordnung <math>\textstyle p = k+1</math>, sie besteht aus Polynomen vom Grad <math>\textstyle k</math>.
Die Ordnung <math>\textstyle p</math> einer NURBS-Kurve ist festgelegt durch die Anzahl benachbarter Kontrollpunkte, die die Kurve beeinflussen. Die Kurve setzt sich mathematisch aus Polynomen zusammen, deren Grad <math>\textstyle k</math> eins kleiner als die Ordnung der Kurve ist (<math>\textstyle k = p -1</math>). 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 <math>\textstyle m</math> der Kontrollpunkte muss größer oder gleich der Ordnung <math>\textstyle p</math> 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.

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

{| class="wikitable" style="margin-left:2em"
|-
!style="width:3em;"| ''x''
!style="width:3em;"| ''y''
!style="width:3em;"| ''z''
!style="width:3em;"| 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
|}

=== NURBS-Flächen ===
Während eine NURBS-Kurve ausschließlich in eine parametrische Richtung <math>u</math> aufgespannt ist, wird eine NURBS-Fläche durch zwei Parameter, genannt <math>u</math> und <math>v</math>, 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.

:<math>S(u,v)=\sum_{i=0}^n\sum_{j=0}^mR_{i,j}(u,v)P_{i,j}</math>

sind definiert durch ein Kontrollgitter <math>P_{i,j}</math> und die rationale Basisfunktion

:<math>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}}</math>

mit einer zweidimensionalen Gewichtematrix <math>w_{i,j}</math>. Die zweite Dimension der Fläche <math>S(u,v)</math> mit dem Parameter <math>v</math> wird geschaltet durch den analog zu <math>U</math> aufgebauten Knotenvektor

:<math>V=\{\underbrace{c,\ldots,c}_{q},v_{q+1},\ldots,v_{s-q-1},\underbrace{d,\ldots,d}_{q}\}</math>

mit der Ordnung <math>q</math> und der Länge <math>s</math>.

== Einfache Erklärung eines komplexen Sachverhaltes ==
In den 1950er Jahren entdeckte Bézier eine mathematische Formel, mit der sich eine geschwungene Kurve beschreiben lässt. Die Kurve wird dabei durch wenige sogenannte Kontrollpunkte definiert. In der Folge stellte sich heraus, 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 (rational) auf den Kurvenverlauf einwirken können, die sogenannten B-Splines. Der Begriff [[Spline]] ist historisch und stammt aus dem Schiffbau. Linealartige biegsame Metallstreifen, sogenannte [[Straklatte]]n (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 uniform rational B-Splines“, die beinahe beliebigen Kurven darstellen können. Wenn man nicht nur eine Richtung („Länge“) wie bei einer Kurve, sondern eine zweite („Breite“) benutzt, 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, Motorgehäuse, 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.'' Springer Science+Business Media, 2006, ISBN 0-387-24196-5.

== Weblinks ==
* [https://github.com/retuxx/tinyspline TinySpline] – Open Source C-Programmbibliothek mit Bindings für verschiedene Sprachen

{{SORTIERUNG:NURBS}}
[[Kategorie:Geometrische Modellierung]]
[[Kategorie:Numerische Mathematik]]
[[Kategorie:Mathematische Funktion]]