Post on 06-Apr-2015
transcript
§2-1
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
Aufgabe
Modellieren Sie mittels Bézier-Kurven einen Kreis.
Hinweis: Beginnen Sie mit einem Viertelkreis
Modellieren Sie anschließend eine Kugel aus Bézier-Patches
§2-2
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Rationale Kurven
Rationale Bézier-Kurven
Mit polynomialen Segmenten lassen sich Kegelschnitte, wie z.B.
Kreise und Ellipsen, nicht exakt darstellen. Um dies zu
ermöglichen, betrachten wir Bézier-Kurven in projektiven Räumen
unter Verwendung von homogenen Koordinaten. Als Gewichte der Kontrollpunkte bi führen wir die Größen wi ein.
Somit erhalten wir die Darstellung für rationale Bézier-Kurven.
Letztere sind gebrochen-rationale Funktionen, d.h. Zähler und
Nenner sind Polynome. Mit dieser Technik wird es möglich,
Kegelschnitte exakt darzustellen.
§2-3
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Rationale Kurven
Wir erhalten folgende rationale Bézier-Kurvendarstellung:
)(
)()(
~
0
tBw
tBwtB
njj
n
j
niin
i
),(~
)(
)()(
0
0
0 tBbtBw
tBbwtX n
ii
n
inii
n
i
niii
n
i
§2-4
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Rationale Kurven
1
101
1
1
1
1
11
10
1010
Einfluss unterschiedlicherPunktgewichte
§2-5
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Rationale Kurven
Beispiel:
Darstellung eines Viertelkreises
b0 = (0,1) b1 = (1,1)
b2 = (1,0)
w0 = 1w1 =
w2 = 1
5.0
§2-6
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Bei der Interpolation mit Polynomen treten insbesondere bei hohen
Polynomgraden starke Oszillationen auf. Um diese Oszillationen
einzudämmen, setzt man Kurven aus mehreren Segmenten von
niedrigem Polynomgrad zusammen. Von den einzelnen
Teilpolynomen verlangt man, dass sie sich in den Nahtstellen (die
hier mit den Stützstellen übereinstimmen) „glatt“ aneinander-
fügen.
§2-7
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Definition: Ck-Stetigkeit
Eine Funktion f(t) ist Ck-stetig (k 0), wenn die Funktion und ihre k Ableitungen stetig sind. Ck [t0 ,tn] ist die Klasse der Ck-stetigen
Funktionen auf dem Intervall [t0 ,tn].
Definition: Spline
= {t0, t1, , tn} sei ein monotoner (Knoten-)Vektor mit reellen
Stützstellen ti< ti+1. Eine Funktion S heißt Spline vom Grad k-1 (von
der Ordnung k), wenn gilt:
(1) S ist ein Polynom vom Grad k-1 in jedem Teilintervall [ti, ti+1]
(2) S ist Ck-2-stetig auf [t0, tn].
§2-8
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Bemerkungen:
1. Der Spline S wird als interpolierender Spline bezeichnet, wenn
für gegebene Interpolationspunkte (Ordinaten).
2. Der interpolierende Spline ist i.a. nicht eindeutig bestimmt. Er
hat noch k-2 Freiheitsgrade, d.h. eine Vorgabe von Rand-
bedingungen ist nötig.
Für kubische Spines (k=4) wählt man oft die natürlichen Randbedingungen S´´(t0) = 0 und S´´(tn) = 0.
Identifiziert man die Knoten t0 und tn miteinander, so entsteht ein
geschlossener Spline (ohne Randbedingungen).
§2-9
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Kubische Splines
Statt die Form der interpolierenden Funktion vorzuschreiben, z.B.
als Polynom eines bestimmten Höchstgrades, kann man auch
Eigenschaften vorschreiben, wie z.B. einen möglichst „glatten“
Verlauf.
Fordern wir
[1]
unter den Nebenbedingungen
[2] , und
so ergibt sich folgendes Resultat:
dtt
t
tgn
0
2
,n, jp)g(t jj )0(
minimal
00 '' p)(tg nn p)(tg ''
§2-10
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Satz: minimum-norm property
Unter allen Funktionen , die die Bedingung [2]
erfüllen, erteilt die interpolierende kubische Splinefunktion dem
Integral [1] den kleinsten Wert.
Es gibt verschiedene Möglichkeiten, die beiden Freiheitsgrade der
Spline-Funktionen zu nutzen. Hier werden die beiden am häufig-
sten verwendeten Fälle behandelt.
und natürlicher Spline
0)( 0 tS 0)( ntS
)()();()();()( 000 nnn tStStStStStS
],[ 02
nttCgS
periodischer Spline
§2-11
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Um den Weg zu Algorithmen für Splinekurven aufzuzeigen, berechnen wir hier zunächst einmal die Koeffizienten eines
natürlichen kubischen Splines:
für Dies führt auf folgende Bedingungen für die Polynome Si:
32 )t(td)t(tc)t(tba(t)SS(t) iiiiiiii
ni p) (tS iii ,...,0
1,...,0;, 1 nittt ii
iiii dcba ,,,
11
1
1
1
,n,i
)(t S'') ''(tS
)(t S') '(tS
)(t S) (tS
iiii
iiii
iiii
§2-12
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Dies hat folgende Auswirkungen auf die Koeffizienten:
211111 32 )t(td)t(tcbb iiiiiiii
)(622 111 iiiii ttdcc
nittdttcttbaa iiiiiiiiiii ,...,1,311
211111
1,...,1 ni
1,...,1 ni
nipa ii ,...,0
§2-13
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Wir setzen i:=ti+1-ti und erhalten nach einigen Umformungen:
)(c))((c)(c iiiiiii 1111 2
)a(aΔ
)a(aΔ ii
iii
i1
11
33
)(3
11 ii
ii ccd
)c(c)a(ab iii
iii
i 23
111
1,...,0 ni
1,...,0 ni
1,...,1 ni
§2-14
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Da gilt, die also bekannt sind, ist im Wesentlichen ein
lineares Gleichungssystem mit n-1 Gleichungen und bislang n+1 Unbekannten ci (i=0,...,n) zu lösen.
Für einen natürlichen kubischen Spline gilt ,
was c0=cn=0 bedeutet.
Fassen wir nun die Erkenntnisse zu einem Algorithmus zusammen:
0)()( 0 ntStS
ii pa ia
§2-15
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Algorithmus für natürliche kubische Splines
Gegeben seien n+1 Stützstellen ti mit t0 < t1 < ... < tn
und die Funktionswerte (bzw. Interpolationspunkte) .
Gesucht ist der zugehörige natürliche kubische Spline S in
der Darstellung
für und
Berechnung der Koeffizienten :
[3]
32 )t(td)t(tc)t(tba(t)S iiiiiiii 1, ii ttt
iiii dcba ,,,
ii pa
00 ncc
ni ,...,0
1,...,0 ni
npp ,...,0
§2-16
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
[4]
[5]
[6]
Bemerkungen:
1. Die Gleichungen [4] lauten in Matrizenschreibweise
)c(cd iii
i
13
1
)c(c)a(ab iii
iii
i 23
111
bAc
)a(a)a(a iii
iii
11
133
)(c)(c)(c iiii-ii-i- 1111 22
iii tt 1
1,...,1 ni
1,...,0 ni
1,...,0 ni
(Gleichungssystem für ci )
§2-17
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
mit
1
1
.
.
.
:
nc
c
c
2
21
1
1
0
01
1
12
.
.
.3:
n
nn
n
nn aaaa
aaaa
b
)(..
..
.)(
..
A:
nnn
n
122
22
2211
110
20
0
02
02
§2-18
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
2. Die Matrix A ist tridiagonal, symmetrisch, diagonal-dominant,
positiv definit und besitzt nur positive Elemente. A ist damit
regulär und das lineare Gleichungssystem hat eine ein-
deutige Lösung. Als Lösungsverfahren sollte man die direkte
LU-Zerlegung für tridiagonale Matrizen verwenden, da der
Algorithmus Komplexität O(n) hat.
Im Fall periodischer Splines entfallen die Randbedingungen und
es ergibt sich ein analoger Algorithmus.
§2-19
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Algorithmus für periodische kubische Splines
Identifiziert man die Stützstellen t0 und tn miteinander, d.h., p0 = pn ,
die Interpolationskurve ist geschlossen und besitzt auch bei t0
(bzw. tn) einen C2-stetigen Übergang, so ändert sich an dem o.g.
Algorithmus nur die Matrix A des Systems [4]:
)(
)(A
nn
n
0110
1
2211
0110
20
0
02
02
§2-20
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Diese Matrix A ist zyklisch tridiagonal, symmetrisch, diagonal-
dominant, positiv definit und besitzt nur positive Elemente; d.h. A ist
gut konditioniert. Das System kann wiederum in 0(n) gelöst
werden.
§2-21
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Da die Aufgabe der Splines in CAD im Wesentlichen in der
Modellierung ebener oder räumlicher Kurven besteht, benötigen
wir im folgenden den Begriff des vektorwertigen oder
parametrischen Splines.
Definition : Ist eine
Zerlegung des Intervalls so heißt eine Abbildung
parametrischer Spline vom Grad k-1 (Ordnung k),
wenn die Komponentenfunktionen Splines vom Grad k-1 sind.
Insbesondere gilt für die „Komponenten-Splines“ xi :
, wofür
wir im folgenden kurz schreiben.
bt...ttat...t: nn 100 ,, ,
],[2 baCX k )3,2,1(],[2 ibaCx k
i
;, IRba 3,: IRbaX
§2-22
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Lokale Glattheitseigenschaften räumlicher Kurven, die durch
Aneinanderhaftung von Teilkurven entstehen, belegt man
üblicherweise mit folgender Begriffsbildung:
Definition: Sind und
parametrische Kurven mit und und haben den gemeinsamen Punkt X(t1)=Y(s0), so sprechen wir
genau dann von einem Ck-Übergang der Kurven in ihrem
gemeinsamen Punkt, wenn gilt:
für alle r mit 1 r k.
(Unstetigkeiten werden als C-1-stetig bezeichnet.)
],[ 10 ttCX m ],[ 10 ssCY n
)()( 01 sYds
dtX
dt
dr
r
r
r
310 ,: IRttX 3
10 ,: IRssY
§2-23
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Algorithmus für parametrische kubische Splines
Gegeben seien von einer Raumkurve die Interpolationspunkte
Gesucht ist ein interpolierender parametrischer kubischer Spline.
1. Schritt: Parametrisierung: Festlegung der Parameterwerteti (i = 0,...,n) zu den Interpolationspunkten
2. Schritt: Festlegung der Randbedingungen
3. Schritt: Berechnung der Spline Komponenten Sx,Sy,Sz so dass Sx(ti)=xi,
Sy(ti)=yi, Sz(ti)=zi, (i=0,...,n) mit Hilfe des jeweiligen Spline-Algorithmus,
.,...,0,,: nizyxp iiii
§2-24
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Bemerkung:
Bei geschlossenen Kurven eignen sich periodische Splines, sofern
die Kurve überall „glatt“ ist. Liegen eine oder mehrere „Spitzen“ vor
(C0-Übergängen, z.B. beim Querschnitt einer Tragfläche), dann
eignen sich natürliche Splines mit den Spitzen als Anfangs- und
Endpunkten.
32 )()()()()( ixiixiixixixix ttdttcttbatStS 32 )()()()()( iyiiyiiyiyiyiy ttdttcttbatStS 32 )()()()()( iziiziiziziziz ttdttcttbatStS
1,...,0 , , 1 nittt ii
§2-25
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Parametrisierungen
Die Parameterwahl bestimmt sehr stark das Aussehen und damit
auch die Qualität der Kurven (und Flächen).
Gleiche Interpolationsaufgabe mit unterschiedlichen Parametrisierungen
§2-26
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Parametrisierungen
Die Wirkung der Parameterwahl kann durch folgende kinematische
Interpretation visualisiert werden: Der Kurvenparameter t wird als
Zeitparameter aufgefasst, der angibt, wie lange ein Punkt X benötigt,
um die Kurve X(t) zu durchlaufen.
Wir betrachten zunächst die Interpolation einer Punktmenge durch eine
Kurve; d.h. wir legen ein Parameterintervall [a,b] zugrunde und
interpolieren n+1 Punkte.
§2-27
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Äquidistante Parametrisierung
Bei der äquidistanten Parametrisierung steht nun für jedes zu interpolierende Punktepaar (Pi,Pi+1) die gleiche Durchlaufzeit zur
Verfügung.
Sind die Abstände zwischen den Punkten sehr unterschiedlich, so muss
der Kernpunkt X die Interpolationskurve mit unterschiedlicher
Geschwindigkeit durchlaufen. Folgt einem großen Abstand ein kleiner
Abstand, so muss die größere Geschwindigkeit stark „abgebremst“
werden, was zu einem „Überschwingen“ der Interpolationskurve führen
kann.
0; ; ,...,nitiatn
abt i
§2-28
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Chordale Parametrisierung
Die Parametrisierung sollte der „Struktur der Punktmenge“ in
gewissem Sinne angepasst werden. Einen solchen Zugang liefert
die chordale Parametrisierung,
Die Parameterintervalle werden proportional zu den Abständen
benachbarter Stütz- bzw. Interpolationspunkte gewählt mit s als Normierungsfaktor (z.B. s = Gesamtlänge des von den Pi
erzeugten Polygons).
.: 11 s
PPttt ii
iii
§2-29
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
Zentripetale Parametrisierung
Eine weitere Möglichkeit der Parameterwahl, welche die Struktur
der Daten nachbildet, ist die so genannte zentripetale Parametri-
sierung [Lee 1975]:
Hier wird die zentripetale Beschleunigung näherungsweise
minimiert. Sinnvoll sind auch Kombinationen dieser drei Typen.
Eine Parametrisierung, die nicht nur Abstände, sondern auch noch
Winkeländerungen in den Interpolationspunkten berücksichtigt,
wurde von T. Foley entwickelt (siehe [Foley 1989]).
s
PPt
ii
i
1:
§2-30
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splinekurven
§2-31
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
Basis Splines
Bei der Konstruktion von Splines haben wir bisher polynomiale
Basisfunktionen (z.B. Bernsteinpolynome) für die Darstellung der
einzelnen Segmente betrachtet. Dies führt zur Konstruktion von
Übergangsbedingungen an den Segmenttrennstellen.
Ein eleganterer Ansatz zur Konstruktion von Splinekurven besteht
darin, Ck-2-stetige Basisfunktionen aus mehreren Segmenten der
Ordnung k zu konstruieren. Bei Verwendung dieser Basis Splines
(B-Splines) entfallen die Übergangsbedingungen und es werden
zudem weniger Kontrollpunkte (Koeffizienten) benötigt.
§2-32
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
Beispiel: Quadratische B-Splinekurve mit Kontrollpunkten d0...d5.
d0
t0=t1= t2 t3 t6= t7= t8t4
2 43
t5
5
d5 d4
d3
d2
d1 2 :
3
5
: 4
3 :
4
§2-33
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
Eine offene B-Splinekurve der Ordnung k (vom Grad k-1) ist
gegeben durch
m+1 Kontrollpunkte d0,...,dm (de Boor-Punkte) und
m+k+1 Knoten x0x1 ... .xm+k (Knotenvektor).
Das Definitionsgebiet der B-Spline Kurve ist das Intervall [xk-1, xm+1], welches m-k+2 Segmente enthält. Die übrigen Knoten
bestimmen das Verhalten der Kurve an den Rändern.
Für das erste Splinesegment benötigt man k de Boor-Punkte, für
jedes weitere Segment nur einen zusätzlichen de Boor-Punkt.
§2-34
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
de Boor-Algorithmus
Analog zum de Casteljau-Algorithmus für Bézier-Kurven ermöglicht
der de Boor-Algorithmus die effiziente Auswertung von
B-Splinekurven (ohne die einzelnen Segmente herzuleiten).
Zu gegebenem Parameter t bestimmt man zunächst den Index r, so dass t [xr , xr+1).
Der zugehörige Punkt f ( t ) der Splinekurve wird dann aus den de Boor-Punkten dr-k+1,...,dr wie folgt ermittelt:
§2-35
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
De Boor-Algorithmus
Für t [xr , xr+1) berechnet sich die B-Splinekurve aus
mit
),...,1(0 rkridd ii
)1,..,1;,...,1()1( 111 kjrjkriddd j
ij
ij
ij
ij
i 1)( k
rdtf
ijki
iji xx
xt
)(110
12
02
01
tfddd
dd
d
krrr
krkr
kr
Schema des de Boor-Algorithmus
§2-36
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
De Boor-Algorithmus
1. Beispiel: k=4, m=4
m-k+2 = 2 polynomiale Segmente
d0
dm
d2d1
d3
...
x0 x1 xk-1 xm+1 xm+k
§2-37
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
De Boor-Algorithmus
1. Beispiel: k=4, m=4
d0
dm
d2d1
d3
x0 x1 xk-1 xm+1 xm+kt
d4
d3
d21
1
1
21
31
41
t [x4 , x5) r=4
§2-38
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
De Boor-Algorithmus
1. Beispiel: k=4, m=4
d0
dm
d2d1
d3
x0 x1 xk-1 xm+1 xm+kt
d4
d3
d21
1
1
32
42
d4
d32
2
§2-39
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
De Boor-Algorithmus
1. Beispiel: k=4, m=4
d0
dm
d2d1
d3
x0 x1 xk-1 xm+1 xm+kt
d4
d3
d21
1
1
43
d4
d32
2
f(t)=d43
§2-40
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
2. Beispiel (k=5):
dr-4
dr
dr-2dr-3
dr-1
...
xr xr+1
rr-1 r+1r-2r-3 r+2 r+3
t
),...,3(1 rridi
§2-41
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
2. Beispiel (k=5):
dr-4
dr
dr-2dr-3
dr-1
...
xr xr+1
rr-1 r+1r-2r-3 r+2 r+3
t
),...,2(2 rridi
§2-42
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
2. Beispiel (k=5):
dr-4
dr
dr-2dr-3
dr-1
...
xr xr+1
rr-1 r+1r-2r-3 r+2 r+3
t
),1(3 rridi
§2-43
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
2. Beispiel (k=5):
dr-4
dr
dr-2dr-3
dr-1
...
xr xr+1
rr-1 r+1r-2r-3 r+2 r+3
t
)(4 tfdr
§2-44
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
3. Beispiel (k=5):
dr-4
dr
dr-2dr-3
dr-1
...
t=xr xr+1
rr-1 r+1r-2r-3 r+2 r+3
Auswerten an einem
Knoten
),...,3(1 rridi
§2-45
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
3. Beispiel (k=5):
dr-4
dr
dr-2dr-3
dr-1
...
t=xr xr+1
rr-1 r+1r-2r-3 r+2 r+3
Auswerten an einem
Knoten
),...,2(2 rridi
§2-46
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
3. Beispiel (k=5):
dr-4
dr
dr-2dr-3
dr-1
...
t=xr xr+1
rr-1 r+1r-2r-3 r+2 r+3
Auswerten an einem
Knoten3rd
)(431 tfdd rr
§2-47
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
B-Splines
Aus dem de Boor-Algorithmus ergeben sich die Basisfunktionen Ni,k(t) (B-Splines) zu den einzelnen de Boor-Punkten di (analog zu
den Bernstein-Polynomen für Bézier-Kurven).
[1] Rekursionsformel von de Boor und Cox
sei eine nichtfallende Folge von Knoten.
0INiix
sonst 0
1:)( 1
1,
iii
xtxtN
)()(:)( 1,11
1,1
, tNxx
txtN
xx
xttN ki
iki
kiki
iki
iki
§2-48
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
Beispiel 1: = {0,1,2,3,4}, k=1,...,3
sonst 0
)1,0[ 11,0
t
N
sonst 0
)3,2[ 11,2
t
N
sonst 0
)2,1[ 11,1
t
N
sonst 0
)4,3[ 11,3
t
N
sonst 0
1,2)[t -2
)1,0[
2,0
t
N
sonst 0
[2,3)t -3
1,2)[ 1
2,1
t
N
sonst 0
)4,3[t -4
2,3)[ 2
2,2
t
N
§2-49
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
[3,4) 0
[2,3) 2
t-3
)2,1[ 2
1-tt-3t-2
0,1)[ 2
2
2
3,0
t
t
N
3,4)[ 2
t-4
)3,2[ 2
2-tt-41-tt-3
)2,1[ 2
1
)1,0[ 0
2
2
3,1
t
N
§2-50
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
Beispiel 2: ={0,0,0,1,2,3,4,4,4}, k=1,...,3
01,11,0 NN sonst 0
)1,0[ t11,2
N sonst 0
)2,1[ t11,3
N
01,71,6 NN sonst 0
)4,3[ t11,5
N sonst 0
)3,2[ t11,4
N
§2-51
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
02,0 N sonst0
)1,0[121
t N ,
sonst0
)2,1[2
)1,0[
22
-t
t
N ,
sonst 0
[3,4) 32,5
t
N
sonst0
)4,3[4
)3,2[2
24
-t
t-
N ,
sonst 0
)3,2[3
)2,1[1
23
-t
t-
N ,
02,6 N
sonst 0
)1,0[1 2
3,0
tN
sonst 0
1,2)[ 2
2
0,1)[ 2
21
2
31
-t)(
-t)(t-t)(t
N ,
§2-52
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
[3,4) 2
4
)3,2[2
2431
1,2)[ 2
1
sonst 0
2
2
33
-t)(
)(tt)()t()-t(
)(t-
N ,
3,4)[ 3
sonst 023,5
tN
)4,3[16102
3
)3,2[ 2
2
sonst 0 2
34
tt²-
)(t-
N ,
sonst 0
)3,2[ 2
3
)2,1[ 2
132
)1,0[ 2
2
2
32
-t)(
)(tt)()t(t
t
N ,
§2-53
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
].,[,)(:)( 110
,
mk
m
ikii xxttNdtf
Mit Hilfe dieser Basis Splines erhalten wir nun folgende
Darstellung:
[2] Definition: B (Basis)-Splinekurven
(a) Das Kontrollpolygon d0,...,dm, die Ordnung k (Grad k-1) und
die m+k+1 Knoten x0x1 ... xm+k definieren eine
offene B-Splinekurve, gegeben durch
§2-54
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
(b) Das Kontrollpolygon d0,...,dm, die Ordnung k (Grad k-1) und
die m+2 Knoten x0x1 ... xm+1 definieren eine
geschlossene B-Splinekurve, gegeben durch
wobei die fehlenden Knoten periodisch ergänzt werden:
Diejenigen B-Splines, welche aus dem Intervall [x0,xm+1]
herausragen, müssen am jeweils anderen Rand des Intervalls
angetragen werden.
],,[,)(:)( 100
,
m
m
ikii xxttNdtf
.1 iii xx ,12 iimim xx
,1 imii xx ,2,1,0i
§2-55
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
Beispiel (k=3, m=4):
x0 xk-1 xm+1 xm+k
d0 dk
offene B-Splinekurve
x0 xm+1
geschlossene B-Splinekurve
d0 dm
0 m 0m ... ......
...
...
2.9 Freiformkurven und -flächen – B-Splines
§2-56
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
Bemerkungen:
1. Jede Kontrollpunktänderung hat nur lokalen Einfluss.
2. Bei offenen B-Splinekurven werden die Randpunkte d0 und dm interpoliert, wenn gilt: x0=...=xk-1 und xm+1=...=xm+k.
Die Knoten x0 und xm+k haben keinen Einfluss auf den
Kurvenverlauf.
3. Die Trägerintervalle der B-Splines sind wie folgt definiert:
kmmkk
m,km,k,k
,x,x,x,x,x,x
NdNdNdsf
110
1100
2.9 Freiformkurven und -flächen – B-Splines
§2-57
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
Satz: Convex-Hull und Variation-Diminishing Property
(a) Jede Gerade schneidet eine ebene B-Splinekurve nicht öfter
als das zugehörige B-Splinepolygon.
(b) Die B-Splinekurve liegt in der konvexen Hülle des
zugehörigen B-Splinepolygons. Genau genommen liegt jeder
Kurvenpunkt in der konvexen Hülle von k lokalen
Kontrollpunkten.
Beweis: siehe [Lane:1983]
Bemerkung:
Liegen k aufeinander folgende Kontrollpunkte auf einer Geraden,
so enthält auch die Kurve ein Geradensegment.
2.9 Freiformkurven und -flächen – B-Splines
§2-58
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splines
Man kann B-Splinekurven in Bézier-Segmente umwandeln, indem
man die Vielfachheit aller Knoten durch sukzessives
Knoteneinfügen auf k-1 erhöht. Die B-Splines degenerieren
dadurch zu Bersteinpolynomen.
§2-59
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – NURBS
NURBS (non-uniform rational B-splines)
Wegen der geringeren Datenmenge empfiehlt es sich oft, die
B-Splinedarstellung einzusetzen. NURBS sind rationale, nicht-
uniforme B-Splines, die besonders im CAD-Bereich Anwendung
finden:
Knoten-Sequenz {x0 ,...., xn+k}
Kontrollpunktmenge {d0 ,....,dn}
Gewichtesequenz {w0 ,....,wn}
)(
)()(
tNw
tNdwtf
kii
kiii
§2-60
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Splineflächen
Splineflächen
Splineflächen sind aus mehreren Patches (Flächensegmenten)
zusammengesetzt. An den Trennkurven der Patches sind gewisse
Stetigkeitsbedingungen für glatte Übergänge einzuhalten.
§2-61
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splineflächen
B-Splineflächen
Aus dem Tensorprodukt der Darstellung für B-Splinekurven
gewinnt man B-Splineflächen. Für die Definition einer B-
Splinefläche benötigt man also
- zwei Ordnungen k und l
- de Boor Punkte dij (i=0,...,m; j=0,...,n)
- zwei Knotenvektoren (x0, ..., xm+k) und (y0, ..., yn+l)
B-Splineflächen können auch in eine oder beide Richtungen
geschlossen sein (Zylindermantel, Torus).
§2-62
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splineflächen
B-Splineflächen
Die B-Spline-Darstellung ist erheblich kompakter als eine
Darstellung der entsprechenden Patches. Die Parametrisierung ist
durch die beiden Knotenvektoren festgelegt.
yn+1
yl-1
xk-1xm+1 ...
... (Definitions-
bereich)
§2-63
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – B-Splineflächen
B-Splineflächen
Die Auswertung einer B-Splinefläche f(s,t) erfolgt mit dem
de Boor-Algorithmus. Zuerst wertet man für jede Zeile von de Boor-Punkten eine B-Splinekurve dj := fj (s) aus, welche dann
die Kontrollpunkte einer Flächenkurve f(t) (s = konst.) liefert.
Alternativ dazu kann man auch folgende Summe auswerten:
§2-64
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Darstellung
Darstellung von NURBS in OpenGL
Erzeugung eines NURBS-Objekts und Rückgabe des Zeigers darauf:
GLUnurbsObj* gluNewNurbsRenderer(void);
Definition der NURBS-Eigenschaften
void gluNurbsProperty(GLUnurbsObj* nurbs,
// erzeugtes NURBS-Objekt
GLenum property,
// Eigenschaft
GLfloat value
// Eigenschaftswert
);
§2-65
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Darstellung
NURBS-Eigenschaften und Eigenschaftswerte (Auswahl)
Eigenschaft mögliche Werte
GLU_SAMPLING_TOLERANCE value>0
GLU_DISPLAY_MODE GLU_FILL |
GLU_OUTLINE_POLYGON |
GLU_OUTLINE_PATCH
GLU_CULLING GL_TRUE | GL_FALSE
GLU_AUTO_LOAD_MATRIX GL_TRUE | GL_FALSE
§2-66
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Darstellung
Spezifikation eines Callbacks zur Fehlerbehandlung
void gluNurbsCallback(GLUnurbsObj* nurbs,
// erzeugtes NURBS-Objekt
GLenum which,
// Art des Callbacks:
// GLU_ERROR
void (*fn)(GLenum errorCode)
// Funktionspointer des
// Callbacks
);
§2-67
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Darstellung
Beispiel einer Callback-Funktion
void CALLBACK nurbsError(GLenum errorCode)
{
const GLubyte *estring;
estring = gluErrorString(errorCode);
fprintf (stderr, "Nurbs Error: %s\n", estring);
exit (0);
}
§2-68
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Darstellung
Spezifikation der NURBS- / B-Spline-Kurve
Definition der NURBS-Eigenschaftenvoid gluNurbsCurve(GLUnurbsObj* nurbs, // NURBS-Objekt
GLint knotCount, // KnotenanzahlGLfloat *knots, // KnotenvektorGLint stride, // Offset zwischen
// de Boor PunktenGLfloat *control, // de Boor PunkteGLint order, // Ordnung der
// KurveGLenum type // Typ der
// darzustellenden// Kurve, z.B.// GL_MAP1_VERTEX3
// GL_MAP1_VERTEX4);
§2-69
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Darstellung
Spezifikation der NURBS- / B-Spline-Fläche
Definition der NURBS-Eigenschaftenvoid gluNurbsSurface(GLUnurbsObj* nurbs, // NURBS-Objekt
GLint uKnotNum, GLfloat* uknots, // Knotenvektor uGLint vKnotNum, GLfloat* vknots, // Knotenvektor vGLint ustride, GLint vstride // Offset zwischen // de Boor PunktenGLfloat *controlArray, // de Boor PunkteGLint uorder, GLint vorder // Ordnung der
// KurveGLenum type // Typ der
// darzustellenden// Kurve, z.B.// GL_MAP1_VERTEX3// GL_MAP1_VERTEX4 );
§2-70
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Darstellung
Darstellung der NURBS- / B-Spline-Kurve / -Fläche
void gluBeginCurve(GLUnurbsObj* nurbs);gluNurbsCurve(........);void gluEndCurve(GLUnurbsObj* nurbs);
bzw.void gluBeginSurface(GLUNnurbsObj* nurbs);gluNurbsSurface(........);void gluEndSurface(GLUnurbsObj* nurbs);
§2-71
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
2.9 Freiformkurven und -flächen – Darstellung
Darstellung von NURBS in OpenGL
Löschen eines NURBS-Renderer-Objekts:
void gluDeleteNurbsRenderer(GLUnurbsObj* nurbs);
§2-72
§2 Darstellung geometrischer Objekte, Farbe, Beleuchtung
Visualisierung mit C++ / OpenGL - SS 2005
Aufgabe
Ergänzen Sie das Beispielprogramm surface.c von der Website um folgende Eigenschaften:
- Ermöglichen Sie eine Navigation um die Fläche mit Hilfe der Maus
- Ermöglichen Sie eine Modifikation einzelner Kontrollpunkte z.B. mit Hilfe der Tastatur
(z.B. Springen von einem Kontrollpunkt zum anderen auf Tastendruck, Einfärben des jeweils aktiven Kontrollpunkts, Verschieben des Kontrollpunkts auf Tastendruck.)