Kurs:Maßtheorie auf topologischen Räumen/Interpolation von Gittern - NURBS

Einführung

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. Ein NURBS kann jeden beliebigen nicht-verzweigenden stetigen Linienzug darstellen. Im Computergrafik-Bereich wird die Geometrieinformation jedoch meist über stückweise funktional definierte Geometrie-Elemente dargestellt, statt die komplette Formgebung über einen einzigen NURBS abzubilden.

Abbildung - Gitter mit NURBS-Flächen

Kontrollpunkte mit NURBS-Fläche

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.

Pierre Étienne Bézier

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.

Paul de Casteljau

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.

Generalisierung B-Splines

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.

Einsatz in statische Konstruktionen

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).

Einsatz in dynamischen interaktiven Konstruktionen

Auf Systemen von Silicon Graphics wurde erstmals 1989 die Echtzeitverarbeitung und interaktives Rendering von NURBS-Kurven und NURBS-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.

Einsatz in Computergrafik

Heutzutage enthalten die meisten professionellen Computergrafik-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.

OpenSource 3D-Modellierung

Im OpenSource-Bereich kann beispielhaft Blender genannt werden, mit dem z.B. professionelle Animationsfilme hergestellt werden können, die zu Demonstrationszwecken der Qualität der Renderengine im Open-Bereich dient:

• Agent 327 - Blender Open Movie
• Spring - Blender Open Movie
• Big Buck Bunny - Blender Open Movie

Siehe auch 3D-Modellierung.

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 und PHIGS. 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 (am offensichtlichsten bei Bézierkurven) 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 Stetigkeit darstellen zu können.

Stetigkeitsanforderungen

Hierbei werden unterschiedlich starke Stetigkeitsforderungen gestellt. Neben der üblichen ${\mathcal {C}}$-Stetigkeit wird hier auch die geometrische Stetigkeit betrachtet:

• ${\mathcal {G}}^{0}:$ Positions-Stetigkeit
• ${\mathcal {G}}^{1}:$ tangentiale Stetigkeit
• ${\mathcal {G}}^{2}:$ Krümmungsstetigkeit

Positions-Stetigkeit

${\mathcal {G}}^{0}:$ 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.

tangentialer Stetigkeit

${\mathcal {G}}^{1}:$ 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.

Krümmungsstetigkeit

${\mathcal {G}}^{2}:$ Krümmungsstetigkeit herrscht bei gleichen Krümmungswerten im gemeinsamen Punkt von aneinander grenzender Kurven, respektive gemeinsamen Linien aneinander grenzender Flächen. 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

Höhere Stetigkeitsgrade sind mit NURBS ebenfalls möglich. Die Stetigkeitsgrade stehen im Zusammenhang mit dem Grad der Polynome bei Bernsteinpolynome oder der [Konvexkombination|[Ordnung der Konvexkombination]].

Glatte Oberflächen

Die Realisierung glatter Oberflächen erfordert NURBS-Flächen, die wenigstens ${\mathcal {G}}^{1}$-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.

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.

Bemerkung - Verallgemeinerung

NURBS-Kurven und -Flächen 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.

Grad der Basispolynome

Eine NURBS-Kurve $\textstyle C(u)$ ist definiert durch den Grad $\textstyle k$ ihrer Basispolynome (= Ordnung p der NURBS-Kurve – 1), eine Menge $\textstyle \mathbb {P}$ gewichteter ($\textstyle w_{i}$) Kontrollpunkte $\textstyle P_{i}$ und einen Knotenvektor $\textstyle U$. NURBS-Kurven und -Flächen sind Verallgemeinerungen von sowohl B-Splines als auch Bézierkurven und -flächen.

Unterschied zwischen Splinearten

Der hauptsächliche Unterschied zu diesen beiden Splinearten ist die Gewichtung der Kontrollpunkte mit den Gewichten $\textstyle w_{i}$. Durch die $\textstyle w_{i}$ werden NURBS-Kurven rational.

NURBS-Kurve

Sei $V$ eine $\mathbb {R}$ mit $P_{0},\ldots ,P_{n}\in V$ Kontrollpunkten in dem Vektorraum. Ferner sei $[a,b]\subset \mathbb {R}$ ein Intervall. Eine NURBS-Kurve $C:[a,b]\to V$ vom Grad $k\in \mathbb {N}$ ordnet jedem $t\in [a,b]$ die Linearkombination $C(t)\in V$

$C(t):=\sum _{i=0}^{n}R_{i,k}(t)\cdot P_{i}$

mit $R_{i,k}(t)\in \mathbb {R}$ und $\sum _{i=0}^{n}R_{i,k}(t)=1$ zu.

Rationale Basisfunktionen

Die rationale B-Spline-Basisfunktion $R_{i,p}:[a,b]\to \mathbb {R}$ errechnet sich aus B-Spline-Basisfunktionen $\textstyle N_{i,p,\tau }$ des maximalen Grads der Basispolynome $\textstyle p$ und den zu den Kontrollpunkten zugehörigen Gewichten $\textstyle w_{i}$ zu

$R_{i,p}(t)={\frac {N_{i,p,\tau }(t)\cdot w_{i}}{\displaystyle \sum _{j=0}^{n}N_{j,p,\tau }(t)\cdot w_{j}}}$.

B-Spline-Basisfunktionen

Für die rationalen Basisfunktionen werden B-Spline-Basisfunktionen verwendet, die folgende Eigenschaften besitzen. Die B-Spline-Basisfunktion $N_{i,p,\tau }(t)$ mit $i=0,\ldots ,n-p-2$ im Raum der Splines $S_{k,\tau }$ mit Knotenvektor $\tau =(\tau _{i})_{i=0}^{n-1}$ und Maximalgrad $p$ aus:

• Nicht-Negativität: $N_{i,p,\tau }(t)\geq 0$
• Lokaler Träger: $N_{i,p,\tau }(t)>0$ falls $t\in {]\tau _{i},\tau _{i+p+1}[}$ und $N_{i,p,\tau }(t)=0$ falls $t\not \in [\tau _{i},\tau _{i+p+1}[$
• Zerlegung der Eins: $\sum _{i=0}^{n-p-2}N_{i,p,\tau }(t)=1$ für $t\in [\tau _{p},\tau _{n-p-1}[$

Veranschaulichung - Zerlegung der Eins

Vier Funktionen $N_{1},N_{2},N_{3},N_{4}$, die zu jedem Zeitpunkt $t$ eine Zerlegung der Eins darstellen, d.h. für alle $t\in [a,b]$ gilt:

$N_{1}(t)+N_{2}(t)+N_{3}(t)+N_{4}(t)=1$

Effiziente Berechnung der B-Spline Basisfunktionen

Die Basis-Splines können effektiv mit der Rekursionsformel von de Boor/Cox/Mansfield berechnet werden:

Zerlegung des Definitionsbereiches in Teilintervalle

Die NURBS-Kurve soll auf dem Intervall $[a,b]\subset \mathbb {R}$ definiert werden. Dazu zerlegt man das Intervall $[a,b]$ in Teilintervalle $\left[\tau _{i},\tau _{i+1}\right[$, wobei $\tau _{0}=a$ und $\tau _{n+p+1}=b$ ist.

Polynome vom Grad 0 - Indikatorfunktion

Die B-Spline-Basisfunktion werden induktiv berechnet. Als Polynome vom 0 sind dies konstante Indikatorfunktionen für das Intervall $\left[\tau _{i},\tau _{i+1}\right[$ mit:

$N_{i,0,\tau }(t):={\begin{cases}1,&t\in \left[\tau _{i},\tau _{i+1}\right[\\0,&{\text{sonst}}\end{cases}}$

Induktive Berechnung der Polynome höheren Grades

Seien die B-Spline-Basisfunktionen für den Grad $p-1\in \mathbb {N} _{0}$ bereits definiert, dann erhält man die B-Spline-Basisfunktionen für den Grad $p>0$ wie folgt für $t\in [\tau _{i},\tau _{i+p+1}[$:

$N_{i,p,\tau }(t)=\textstyle {\frac {t-\tau _{i}}{\tau _{i+p}-\tau _{i}}}\displaystyle \cdot N_{i,p-1,\tau }(t)\;+\;\textstyle {\frac {\tau _{i+p+1}-t}{\tau _{i+p+1}-\tau _{i+1}}}\displaystyle \cdot N_{i+1,p-1,\tau }(t)$

Basisfunktionen vom Grad 1

Vom Grad 0 erhält man Indikatorfunktionen für ein Intervall. Für Grad 1 und äquidistanter Zerlegung der Intervallgrenzen entsteht aus zwei Indikatorfunktionen vom Grad 0 eine Dreiecksfunktion als B-Spline-Basisfunktion vom Grad 1 analog zur Faltung von zwei Funktionen f und g.

Aufgabe 1 - B-Spline-Basispolynome

Plotten/Zeichnen Sie den Graph für eine nicht äquidistante Zerlegung in Intervalle mit:

• $\tau _{0}:=1,\ \tau _{1}:=4,\ \tau _{2}:=5,\ \tau _{3}:=7$
• Berechnen Sie alle B-Spline-Basispolynome.

Bemerkung zur Bezeichnung

Die Elemente des Knotenvektors heißen auch Knotenpunkte (engl. knots) und müssen die Bedingungen $\tau _{i}\leq \tau _{i+1}$ und $\tau _{i}<\tau _{i+p}$ erfüllen.

Ableitung der B-Spline-Basisfunktionen

Zur Berechnung der Ableitung eines B-Splines kann man obige Rekursionsformel mit der folgenden Vorschrift für $p\geq 1$ kombinieren:

${\begin{array}{rcl}{\frac {d}{dt}}N_{i,p,\tau }(t)&=&N'_{i,p,\tau }(t)\\&=&{\frac {p}{\tau _{i+p}-\tau _{i}}}N_{i,p-1,\tau }(t)-{\frac {p}{\tau _{i+p+1}-\tau _{i+1}}}N_{i+1,p-1,\tau }(t)\end{array}}$

Aufgabe 2 - Ableitungen der B-Spline-Basispolynome

Berechnen Sie die Ableitungen für die Basispolynome der nicht-äquidistante Zerlegung in Intervalle mit:

• $\tau _{0}:=1,\ \tau _{1}:=4,\ \tau _{2}:=5,\ \tau _{3}:=7$
• Berechnen Sie alle stückweise definierten Ableitung der B-Spline-Basispolynome mit $p\geq 1$!

Bemerkung

Die Bedingungen an die Knotenpunkte $\tau _{i}$ erlauben es, dass in der Rekursionsformel unter Umständen Null als Nenner auftritt (nämlich wenn $\tau _{i+p}=\tau _{i}$ bzw. $\tau _{i+p+1}=\tau _{i+1}$ gilt). Allerdings ist dann die Funktion $N_{i,p,\tau }$ bzw. $N_{i+1,p,\tau }$ automatisch die Nullfunktion. Auf die entsprechende Fallunterscheidung wird hier verzichtet, man ignoriere die entsprechenden Summanden in diesen Fällen (ersetze sie durch Null). Dies entspricht auch dem Grenzverhalten für z. B. $\tau _{i+p}\to \tau _{i}.$

Zerlegung der Eins

Die rationale Basisfunktionen $R_{i,p}:[a,b]\to \mathbb {R}$ stellen bei positiven Gewichten $w_{i}$ Gewichtsanteil aus dem Interval $[0,1]$ dar, mit dem der jeweilige Punkt $P_{i}\in V$ in der Konvexkombination $C(t)$ gewichtet wird.

• $s(t):=\displaystyle \sum _{j=0}^{n}N_{j,p}(t)\cdot w_{j}$ ist die mit den B-Spline-Basisfunktionen $\textstyle N_{i,p}$ errechnet Summe und
• $R_{i,k}(t)=\displaystyle {\frac {N_{i,p}(t)\cdot w_{j}}{s(t)}}$ ist dann der Anteil an der Summe $s(t)$

Die $R_{i,p}(t)$ und die Summe $s(t)$ ändert sich mit der Zeit $t$.

Einfluss auf die Kontrollpunkte

• Wenn $R_{i,k}(t)=1$ ist, läuft die Kurve durch den Kontrollpunkt $P_{i}$. Dies gilt immer für $i=0$ und $i=n$, dem Startpunkt bzw. Endpunkt der Kurve $C:[a,b]\to V$.
• Wenn $R_{i,k}(t)=0$ gilt, hat der Kontrollpunkt $P_{i}$ zum Zeitpunkt $t$ keinen Einfluss auf den Kurvenverlauf von $C:[a,b]\to V$.

Aufgabe 3 - Rationale B-Spline-Basispolynome

Berechnen Sie die alle rationale B-Spline-Basispolynome $R_{i,p}$ der obigen nicht-äquidistante Zerlegung in den Intervallgrenzen und mit $p=1$:

• $\tau _{0}:=1,\ \tau _{1}:=4,\ \tau _{2}:=5,\ \tau _{3}:=7$ und
• $w_{0}:=3,\ w_{1}:=2,\ w_{2}:=3,\ w_{3}:=1$ als Gewichte

Stellen Sie die Funktionen mit Fallunterscheidung in den Intervallgrenzen dar.

Knotenvektoren

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

$\displaystyle U=\{\underbrace {a_{(0)},\ldots ,a_{(p-1)}} _{p},t_{p},\ldots ,t_{n},\underbrace {b_{(n+1)},\ldots ,b_{(n+p)}} _{p}\}$

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

Randbedingungen und Definitionen

Kontrollpunkte

$\mathbb {P} =\{P_{i}\mid P_{i}=(x,y){\text{ mit }}x,y\in \mathbb {R} {\text{ und }}i=0..n\in \mathbb {N} \}$

$|\mathbb {P} |=m=(n+1)$

$\mathbb {W} =\{w_{i}\in \mathbb {R} ,i=0..n\in \mathbb {N} \}$

$|\mathbb {W} |=m=(n+1)$

Knotenvektor

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

Monotonie der Werte im Knotenvektor

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.

Äquivalenz von Knotenvektoren

Sei $v,w\in \mathbb {R} ^{n}$ zwei Knotenvektoren mit monoton steigenden Komponenten d.h. $v_{i}\leq v_{i+1}$, $w_{i}\leq w_{i+1}$ für $i\in \{1,\ldots n-1\}$ heißen äquivalent, wenn mit $v_{1}<v_{n}$ und $w_{1}<w_{n}$ gilt:

$v\equiv w:\Longleftrightarrow \forall _{i\in \{1,\ldots ,n\}}\,:\,{\frac {v_{k}-v_{1}}{v_{n}-v_{1}}}={\frac {w_{k}-w_{1}}{w_{n}-w_{1}}}$

Beispiele für äquivalente Knotenvektoren

Als Beispiel für äquivalente Knotenvektoren kann man (0, 0, 1, 2, 3), (0, 0, 2, 4, 6), und (1, 1, 2, 3, 4) wählen, die alle die gleiche Kurve erzeugen:

$\left(0,0,{\frac {1}{3}},{\frac {2}{3}},1\right)\equiv (0,0,1,2,3)\equiv (0,0,2,4,6)\equiv (1,1,2,3,4)$

Vielfachheit von Knotenvektoren

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 $\textstyle p=k+1$, sie besteht aus Polynomen vom Grad $k$. Die Ordnung $p$ einer NURBS-Kurve ist festgelegt durch die Anzahl benachbarter Kontrollpunkte, die die Kurve beeinflussen. Die Kurve setzt sich mathematisch aus Polynomen zusammen, deren Grad $k$ eins kleiner als die Ordnung der Kurve ist ($k=p-1$).

Beispiel - Ordnung einer NURBS-Kurve

• Also werden Kurven 2. Ordnung durch Polynome 1. Grades $P(x)=p_{1}\cdot x+p_{0}$ dargestellt.
• Kurven dritter Ordnung werden durch quadratische Polynome 2. Grades $P(x)=p_{2}\cdot x^{2}+p_{1}\cdot x+p_{0}$ und
• Kurven vierter Ordnung, auch kubische Kurven genannt, werden mit Polynomen 3. Grades $P(x)=p_{3}\cdot x^{3}+p_{2}\cdot x^{2}+p_{1}\cdot x+p_{0}$ dargestellt.

Die Anzahl $m$ der Kontrollpunkte muss größer oder gleich der Ordnung $p$ der Kurve sein.

Berechnungszeit - Kurven höherer Ordnung

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 2 mit Knotenvektor (0,0,0,1,1,2,2,3,3,4,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

NURBS-Flächen

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.

$S(u,v)=\sum _{i=0}^{n}\sum _{j=0}^{m}R_{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}^{m}N_{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 den 1950er-Jahren hat Bézier die mathematische Formel entdeckt, mit der sich eine geschwungene Kurve beschreiben lässt. Die Kurve wird dabei durch wenige sogenannte Kontrollpunkte definiert. In der Folge hat sich herausgestellt, 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.

Schiffsbau und Splines

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.

Entstehung von B-Splines

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“. 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 gekrümmte Flächen entsprechend des polynomialen Grades dargestellt werden.

Berechnungsaufwand für NURBS

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

• TinySpline – Open Source C-Programmbibliothek mit Bindings für verschiedene Sprachen

Siehe auch

• Zerlegung der Eins
• Konvexkombination
• B-Spline-Basisfunktionen

Seiteninformation

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Maßtheorie auf topologischen Räumen' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Ma%C3%9Ftheorie%20auf%20topologischen%20R%C3%A4umen/Interpolation%20von%20Gittern%20-%20NURBS
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.

Wikipedia2Wikiversity

Diese Seite wurde auf Basis der folgenden Wikipedia-Quelle erstellt:

• NURBS https://de.wikipedia.org/wiki/NURBS
• Datum: 8.11.2022
• Wikipedia2Wikiversity-Konverter: https://niebert.github.com/Wikipedia2Wikiversity