close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

2. Modelle dreidimensionaler Körper, Transformationen Wie können

EinbettenHerunterladen
2. Modelle dreidimensionaler Körper, Transformationen
Wie können wir virtuelle Gegenstände und Szenen im Rechner
konstruieren?
3D-Modelle / solid modelling / Repräsentationen fester Körper
erster Ansatz:
analog zum Aufbau von 2D-Objekten aus Pixeln →
Aufbau aus würfelförmigen "Volumen-Pixeln" = Voxeln
Voxel space
spatial occupancy enumeration (SOE)
jedes Voxel wird durch die
Koordinaten seines Mittelpunkts
repräsentiert
Nachteile:
• hoher Speicherbedarf
• "Treppenstufen" (Aliasing)
• nach Drehung komplette Neuberechnung nötig
Speicherbedarf vermindern: Aufbau einer Baumstruktur (hierarchische
Raumaufteilung) →
"Octree" (Oktalbaum-Schema)
= 3D-Analogon zum "Quadtree" (Viererbaum) aus d. Kapitel über Bäume
Quadtree des Quadranten B:
in 3 Dimensionen: Aufteilung in jeweils 8 Oktanten
Vorteil: bessere Speicherausnutzung
Nachteile: immer noch Aliasing; Aufwand beim Drehen u. Verschieben.
"Constructive Solid Geometry" (CSG):
man geht von einfachen "Primitivobjekten" aus (Würfel, Kugel,
Zylinder...) und setzt diese mit Mengenoperationen zu komplizierteren
Objekten zusammen:
∪
–
∩
Beispiel:
Nachteile:
• Darstellung meist nicht
eindeutig
• es können komplizierte SchnittLinien entstehen: Aufwand bei
Berechnung und Darstellung
• Verschiebungen (allg.:
Transformationen) der
Primitivobjekte müssen mit
abgespeichert werden (siehe
später)
"Boundary Representation":
Darstellung eines Körpers mit Hilfe seiner Begrenzungsobjekte
Körper → Seitenflächen (Facetten)
Facette → Berandungskanten
Kante → Endpunkte
die Punkte werden als Koordinaten-Tripel abgespeichert.
Beispiel:
Genauer:
Ein Polygonnetz ist eine Menge M von endlich vielen geschlossenen,
ebenen und einfachen Polygonen im Raum mit folgenden Eigenschaften:
• die inneren Polygongebiete von je 2 Polygonen aus M haben keine
gemeinsamen Punkte
• je 2 Polygone aus M haben entweder keinen Punkt oder eine Ecke
oder eine ganze Kante gemeinsam
• jede Kante eines Polygons aus M gehört zu höchstens 2 Polygonen
• die Menge aller Kanten, die nur zu einem Polygon aus M gehören, ist
entweder leer (M heißt dann "geschlossen") oder bildet selbst ein
einziges, geschlossenes, einfaches Polygon ("Randpolygon").
Polygonnetze spielen eine wichtige Rolle in der Modellierung (Beisp. Finite-ElementeMethode, Kontrollpunkt-Netze von Bézier- und B-Spline-Flächen, elevation grids)
Def. Polyeder:
Ein Polygonnetz M heißt Polyeder, wenn gilt:
• M ist geschlossen (d.h. jede Kante gehört zu genau 2 Polygonen)
• M ist zusammenhängend
• jede Ecke gehört zu einer endlichen, zyklisch geordneten Menge von
Polygonen, in der aufeinanderfolgende Polygone jeweils eine zur Ecke
gehörende Kante gemeinsam haben
Beispiel, wo die dritte Bedingung verletzt ist:
Die inneren Polygongebiete von M heißen auch Facetten oder
Seitenflächen des Polyeders.
Der Abschluss der Vereinigung aller Facetten heißt die Oberfläche
(surface) des Polyeders.
Die Polyeder sind die 3D-Verallgemeinerungen der ebenen, einfachen,
geschlossenen Polygone.
• Jedes Polyeder teilt den Raum in zwei Bereiche, das Innere und das
Äußere.
• Das Innere kann wieder dadurch charakterisiert werden, dass die
Anzahl der Schnitte eines Strahls, der von einem Innenpunkt ausgeht,
mit der Oberfläche ungerade ist (wie bei geschlossenen Polygonen).
Das Innere eines Polyeders ist also vollständig durch seine Oberfläche
definiert!
→ Grundlage der Boundary Representation
Höherdimensionale Analoga zu Polyedern: Polytope
topologisch "einfachste" nichttriviale Polytope: Simplices
0-Simplex: Punkt
1-Simplex: Strecke
2-Simplex: Dreieck
3-Simplex: Tetraeder
...
math. Definition: m-Simplex
= konvexe Kombination von m+1 affin unabhängigen Punkten im Rm.
Die Folge der m-Simplices ab m=2:
....
wichtige topologische Eigenschaft:
Orientierbarkeit
Def. eines Umlaufsinns auf jeder Facette eines Polygonnetzes möglich
(sukzessive Kanten desselben Polygons in gleiche Richtung orientiert) –
zwei Facetten heißen gleich orientiert, wenn die durch die beiden
Orientierungen auf der gemeinsamen Kante induzierten Pfeile
entgegengesetzte Richtungen haben.
Ein Polygonnetz heißt orientierbar, wenn die Facetten (Polygone) so mit
Orientierungen versehen werden können, dass je 2 längs einer Kante
benachbarte Facetten gleich orientiert sind.
Beispiel einer nichtorientierbaren Fläche:
das Möbiusband
nichtorientierbare geschlossene Flächen sind im R3 nur mit Selbstdurchdringung
realisierbar.
Beispiel Kleinsche Flasche (auch: Kleinscher Schlauch)
(benannt nach Felix Klein):
links: Außenansicht eines Papiermodells der Kleinschen Flasche, rechts: Längsschnitt durch das
Modell
(aus Bungartz et al. 1996)
Kenngröße für Polyeder: die Eulersche Charakteristik χ
Seien v, e, f die Anzahlen der Ecken (vertices), Kanten (edges), bzw.
Facetten. Dann gilt:
Die Summe χ = v – e + f hängt nur von der Topologie der
zugrundeliegenden Fläche ab.
Beispiele:
Polyeder projizierbar auf Kugel ⇒ χ = 2
das gilt insbesondere für alle Polyeder ohne Löcher (Durchbohrungen);
man erhält den Eulerschen Polyedersatz:
v–e+f=2
für Polyeder vom Typ eines Torus (Reifen) ⇒ χ = 0
v–e+f=0
Polyeder vom Typ einer Kugel mit k Henkeln ⇒ χ = 2 – 2k;
Polyeder vom Typ der Kleinschen Flasche ⇒ χ = 0.
Günstige Datenstruktur für Polyeder in Boundary Representation:
kantenbasiert
Ecken werden durch ihre Koordinaten dargestellt
Facetten als Zyklen von Kanten
Kanten als Listen von Ecken und 1 oder 2 angrenzenden Facetten; für
jede Kante ist Orientierung durch Reihenfolge der Endpunkte festgelegt
Transformationen
wie beschreiben wir Veränderungen von Objekten im Raum wie z.B.
• Drehungen
• Verschiebungen
• Spiegelungen
• Vergrößern/Verkleinern ... ?
mathematisch: Funktionen (Abbildungen) des Raumes (R3) in sich.
"zahme" Klasse von Funktionen sind die linearen Abbildungen:
• sie erfüllen f(x+y) = f(x) + f(y) und f(cx) = cf(x)
• sie sind vollständig festgelegt, wenn man die Bilder der Standardbasisvektoren kennt:
Standard-Basisvektoren
 1
 0
 0
 
 
 
0
1
r  0
r   r  
e1 =  , e2 =  , K, en =  
M
M
M
 
 
 .
 0
 0
1
 
 
 
Darstellung der linearen Abb. f durch ihre zugehörige Matrix Mf :
in den Spalten von Mf stehen die Bilder der Standard-Basisvektoren
unter f.
Allgemein besteht eine Matrix aus p×q Skalaren (reellen Zahlen) mij .
 m00

 m10
M =
M

m
 p −1, 0
m01
m11
M
m p −1,1



 = (mij )

L m p −1,q −1 
L
L
O
m0,q −1
m1.q −1
M
r
Anwendung einer linearen Abbildung f auf einen Vektor v
durch Multiplikation der Matrix Mf mit dem Vektor
(dabei Schreibweise des Vektors als Spaltenvektor und Multiplikation der Matrix von links
an den Vektor wichtig!):
 m00
r
r
r 
w = f (v ) = M ⋅ v =  M
m
 p −1, 0

 q −1
L m0,q −1   v0   ∑ m0,k ⋅ v k   w0 
 

  k =0
 
O
M ⋅ M  = 
M
= M 
q −1


L m p −1,q −1   v q −1   ∑ m p −1,k ⋅ v k   w p −1 

 k =0


Rechenschema: "Zeile mal Spalte"
Nacheinander-Anwendung (Komposition)
zweier linearer Abbildungen f ° g: wende erst g an, dann f.
f ° g (x) = f(g(x))
Die Komposition wird beschrieben durch das Produkt der zugehörigen
Matrizen:
Mf ° g = Mf ⋅ Mg
mit
 m00 L m0,q −1   n00

 
M ⋅N = M
O
M ⋅ M
m
 n
L
m
p −1, q −1   q −1, 0
 p −1, 0
 q −1
L n0,r −1   ∑ m0,k n k , 0 L
  k =0
O
M =
M
O
q −1

L nq −1,r −1   ∑ m p −1,k n k , 0 L
 k =0


m0,k n k ,r −1 
∑

k =0
M

q −1

m
n
∑
p −1, k k , r −1 

k =0

q −1
Beachte: Das Matrizenprodukt ist nichtkommutativ (d.h. i. allg. ist N⋅M ≠ M⋅N).
damit lineare Abbildungen gut "im Griff"
aber: wichtige Transformationen sind keine linearen Abbildungen,
insbesondere: Verschiebungen
Translationen (Verschiebungen):
rechnerisch:
v ' = t(v) = v + dt, d.h. Addition eines konstanten Vektors dt.
kann keine lineare Abb. sein, da t(0) ≠ 0.
→ Affine Abbildungen :
alle Abbildungen a, die sich darstellen lassen als
a(v) = f(v) + d
mit einer linearen Abbildung f,
d.h. als Komposition einer linearen Abb. und einer Verschiebung.
Es gilt: d = a(0), f(v) = a(v) – a(0) ⇒ f und d sind eindeutig bestimmt.
Beispiele:
• Drehungen um beliebige Punkte
• Streckungen mit beliebigen Streckzentren
• Schraubungen im R3
• Spiegelungen an beliebigen Geraden im R2 oder an beliebigen Ebenen
im R3
• Parallelprojektionen auf beliebige Ebenen im R3
usw.
(lineare Abbildungen und Verschiebungen als Spezialfälle mit enthalten!)
wir hätten nun gern:
Darstellung auch der affinen Abbildungen in der Form "Matrix mal Vektor".
Dazu ein "Trick":
Hinzunahme einer weiteren Koordinate
• aus (x, y) wird (x, y, 1)
• aus (x, y, z) wird (x, y, z, 1)
dafür werden Vektoren, die sich nur um einen festen Faktor w≠0
unterscheiden, miteinander identifiziert (Klassenbildung).
"homogene Koordinaten"
In der Tat lassen sich nun die Verschiebungen gleichwertig mit allen
anderen affinen Abb. als Produkte "Matrix mal Vektor" berechnen:
Verschiebung
(Translation)
Skalierung
Drehung
(Rotation)
Beispiel:
Verschiebe mittels homogener Koordinaten den Punkt (2; 3) um den
Vektor (7; 5) und drehe anschließend das Ergebnis um 90° um den
Ursprung.
 1 0 7  2  9
    

 0 1 5 ⋅  3 =  8
T(7; 5): 
  1   1  , entspr. (9; 8)
0
0
1
    

R(90°): sin 90° = 1, cos 90° = 0, somit
 0 − 1 0   9   − 8
    

 1 0 0  ⋅  8  =  9  = v'
, entspr. (–8, 9)
 0 0 1  1  1 
    

zusammen: v‘ = R(90°)⋅T(7;9)⋅v.
Analog im dreidimensionalen Fall: vierte, homogenisierende Koordinate,
Darstellung der affinen Transformationen durch 4×4-Matrizen.
Anwendung dieser Transformationen in Szenengraphen
3D-Szenen werden oft in gerichteten, azyklischen Graphen abgelegt, den
sog. Szenengraphen, die durch Aufrufe einer Spezialbibliothek erzeugt
werden
z.B. in OpenInventor, VRML, Java3D
(→ siehe praktischer Teil)
Typisches Szenengraphen-Format (es gibt zahlreiche Varianten!):
• Graphische Primitive (grundlegende Objekte: Würfel, Kugel, Kegel etc.)
mit default-Eigenschaften (Position am Koordinatenursprung,
Einheitsvolumen...) bilden Blattknoten des Graphen
• Attribute (Farbe, Textur etc.) und Transformationen sind ebenfalls
Knoten des Graphen und werden auf Objektknoten je nach deren Lage
im Graphen angewandt.
Beispiel (aus vanDam 2001):
im folgenden Szenengraphen beeinflusst Transformation t0 alle Objekte,
aber t2 beeinflusst nur obj2 und eine Instanz von group3 (welche je eine
Instanz von obj3 und obj4 enthält).
t2 wirkt nicht auf obj1 und auf die andere Instanz von group3.
Transformationsknoten enthalten normalerweise mindestens eine Matrix
(für homogene Koordinatendarstellung), die die Transformation
beschreibt; evtl. noch weitere Parameter.
Bestimmung der Komposition der Transformationsmatrizen (CTM: composite
transformation matrix), die auf einen Objektknoten anzuwenden ist:
Multiplikation der Matrizen in den Transformationsknoten bei top-down-Durchlauf des
Baumes (Details abhängig vom Grafikpaket).
Beispiel (aus vanDam 2001):
CTM(o1) = m1
CTM(o2) = m2 ⋅ m3
CTM(o3) = m2 ⋅ m4 ⋅ m5
für einen Punkt v im Objekt o3
errechnet sich seine Position im
Weltkoordinatensystem (gültig
an der Wurzel des Baumes) als:
CTM⋅v = (m2 ⋅ m4 ⋅ m5) ⋅ v.
Document
Kategorie
Seele and Geist
Seitenansichten
2
Dateigröße
597 KB
Tags
1/--Seiten
melden