Beispiel

3/17/08
C
G
C
Erweiterung
C
G
C
Beispiel
 Problem: welche Fläche zu welcher Kante benachbart ist, kann
nicht direkt beantwortet werden.
 Lösung: die Kanten erhalten je einen Zeiger auf die zugehörige
e11
Fläche bei positivem bzw. negativem Durchlauf, e.fcw, e.fccw
auf die Vorgänger-
v5
e8
e6
e7
e.ncw
e5
e4
Kanten
e.pccw
 Abstrakte
e.dest
4
Notation der
Half-EdgeDatenstruktur:
2
e.fcw
e
2
v0
v3
e0
v2
e2
e1
v1
e.pcw
1, sign
V
e3
e.org
e.fccw
E
v6
e9
v4
 Zusätzlich: speichere Zeiger
G. Zachmann
e10
v7
e.nccw
F
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
G. Zachmann
25
Vertexliste
v
coord
0 0.0
0.0
1 1.0
0.0
2 1.0
1.0
3 0.0
1.0
4 0.0
0.0
5 1.0
0.0
6 1.0
1.0
7 0.0
1.0
0.0
0.0
0.0
0.0
1.0
1.0
1.0
1.0
Kantenliste
e org dest
0 0
1
1 1
2
2 2
3
3 3
0
4 0
4
5 1
5
6 2
6
7 3
7
8 4
5
9 5
6
10 6
7
11 7
4
nccw
e4
e5
e6
e7
e3
e0
e1
e2
e11
e8
e9
e10
ncw
e1
e2
e3
e0
e8
e9
e10
e11
e5
e6
e7
e4
Facetten
0 e0 +
1 e8 +
2 e5 +
3 e6 +
4 e11 +
5 e8 -
pvw
e3
e0
e1
e2
e0
e1
e2
e3
e4
e5
e6
e7
Computer-Graphik 1 - WS 07/08
pccw
e5
e6
e7
e4
e11
e8
e9
e10
e9
e10
e11
e8
fcw
f0
f0
f0
f0
f1
f2
f3
f4
f1
f2
f3
f4
fccw
f1
f2
f3
f4
f4
f1
f2
f3
f5
f5
f5
f5
Randrepräsentationen
26
C
G
C
 Noch ein kleines Problem:
Abfragen der Form "welche
Kanten sind inzident zu einem
best. Vertex?" sind ein Problem
 Lösung: speichere zu jedem
Vertex einen Index auf eine
beliebige inzidente Kante
e11
e10
v7
v6
e9
v4
v5
e8
e6
e7
e5
e4
e3
v0
G. Zachmann
v3
e0
v2
e2
e1
v1
Computer-Graphik 1 - WS 07/08
Vertexliste
v
coord
0 0.0
0.0
1 1.0
0.0
2 1.0
1.0
3 0.0
1.0
4 0.0
0.0
5 1.0
0.0
6 1.0
1.0
7 0.0
1.0
Kantenliste
e org dest
0 0
1
1 1
2
2 2
3
3 3
0
4 0
4
5 1
5
6 2
6
7 3
7
8 4
5
9 5
6
10 6
7
11 7
4
ncw
e1
e2
e3
e0
e8
e9
e10
e11
e5
e6
e7
e4
C
G
C
4
0.0
0.0
0.0
0.0
1.0
1.0
1.0
1.0
e
0
1
2
3
8
9
10
11
nccw
e4
e5
e6
e7
e3
e0
e1
e2
e11
e8
e9
e10
pvw
e3
e0
e1
e2
e0
e1
e2
e3
e4
e5
e6
e7
Facetten
0 e0 +
1 e8 +
2 e5 +
3 e6 +
4 e11 +
5 e8 -
 Abstrakte Notation der endgülten
Winged-Edge-Datenstruktur:
E
2
 Alle Nachbarschafts-Abfragen lassen sich in Zeit
O(k) durchführen! (k = Größe der Ausgabe)
fcw
f0
f0
f0
f0
f1
f2
f3
f4
f1
f2
f3
f4
fccw
f1
f2
f3
f4
f4
f1
f2
f3
f5
f5
f5
f5
Randrepräsentationen
27
F
 Problem: wenn man sich an einer Kante entlang
"hangeln" möchte, muß man jedesmal testen,
wie die Kante orientiert ist, um zu wissen, ob
man ncw oder nccw verfolgen muß!
e.ncw
e.pccw
e.dest
G. Zachmann
Computer-Graphik 1 - WS 07/08
e.fcw
e
e.fccw
if ( e.pcw.dest == e.org )
e = e.ncw;
else
e = e.nccw;
1, sign
V
 3 direkte Abfragen und 6 Abfragen durch lokales
Umrunden einer Facette oder eines Vertex
pccw
e5
e6
e7
e4
e11
e8
e9
e10
e9
e10
e11
e8
1 2
e.org
e.pcw
e.nccw
Randrepräsentationen
28
1
3/17/08
Doubly-Connected Edge List
[Preparata & Müller, 1978]
C
G
C
 In der Computer-Graphik eher bekannt als "half-edge data
C
G
C
2
 Abstrakte Notation:
structure"
 Hier kein eigener Zeiger Start-Vertex
 Ist die effizienteste und einfachste Nachbarschaftsdatenstruktur
E
für Start-Vertex
1
 Benötigt doppelt so viele Einträge in der
 Idee:
E-Tabelle wie die Winged-Edge-DS
 Wie Winged-Edge-DS, aber mit "gespaltenen" Kanten
V
1 1
1
F
 Eine Kante (= Eintrag in der Kantentabelle) ist nur noch für eine Richtung
und eine Seite zuständig
e.next
 Zeiger pro Halb-Kante:
e.dest
- "Twin" (twin | opposite)
- Start- (org) und End-Vertex (dest)
e.face
e
e.twin
- Inzident face (zur Rechten)
e.org
e.prev
- Next und previous edge (im Umlaufsinn)
- Start-Vertex kann man einsparen, da e.org = e.twin.dest
G. Zachmann
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
Vertexliste
v
coord
0 0.0
0.0
1 1.0
0.0
2 1.0
1.0
3 0.0
1.0
4 0.0
0.0
5 1.0
0.0
6 1.0
1.0
7 0.0
1.0
22
v7
21
v6
23
16
v5
20
19
17
V1
13
10
14
9
12
4
15
2
3
1
5
8
7
6
11
0
G. Zachmann
Randrepräsentationen
30
e
0
1
2
3
4
9
13
16
0.0
0.0
0.0
0.0
1.0
1.0
1.0
1.0
Facetten
0 e20
1 e4
2 e0
3 e15
4 e16
5 e8
C
G
C
 Visualisierung für ein Quad-Mesh:
18
v2
v3
V0
Computer-Graphik 1 - WS 07/08
C
G
C
Beispiel
v4
G. Zachmann
29
Computer-Graphik 1 - WS 07/08
Halbkantenliste
e org nxt prv
0 0
1
3
1 1
2
0
2 2
3
1
3 3
0
2
4 4
5
7
5 5
6
4
6 1
7
5
7 0
4
6
8 1
9
11
9 5
10
8
10 6
11
9
11 2
8
10
twin
6
11
15
18
20
8
0
17
5
23
12
1
e
12
13
14
15
16
17
18
19
20
21
22
23
org
2
6
7
3
7
4
0
3
5
4
7
6
nxt prv twin
13 15 10
14 12 22
15 13 19
12 14 2
17 19 21
18 16 7
19 17 3
16 18 14
21 23 4
22 20 16
23 21 13
20 22 9
Randrepräsentationen
31
G. Zachmann
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
32
2
3/17/08
C
G
C
Invarianten in einer DCEL
 Verwende im folgenden die "Funktionen-Notation", d.h.,
 Gesucht: alle Vertices, die inzident zu einem geg. Face f sind
twin(e) = e.twin
 Pseudo-Code:
 Invarianten (bzw. Axiome im ADT "DCEL"):
 twin( twin(e) ) = e , falls das Mesh geschlossen ist
 org( next(e) ) = dest(e)
 org(e) = dest( twin(e) )
[falls twin(e) existiert]
 v.edge.org = v
[v zeigt immer auf eine "abgehende" Kante!]
Computer-Graphik 1 - WS 07/08
 Pseudo-Code:
Randrepräsentationen
G. Zachmann
33
C
G
C
Anwendungsbeispiel
 Simplifizierung: Grobes Mesh aus einem gegebenen "feinen"
e_start ← f.edge
e ← e_start
repeat
output e.dest
e ← e.next
until e == e_start
e
f
 Aufgabe: zu geg. Vertex v alle benachbarten Vertices liefern
 etc. …
G. Zachmann
C
G
C
Beispiele für das "Abwandern" der Topologie
e_start ← v.edge
e ← e_start
repeat
output e
if e.org == v:
e ← e.twin
e ← e.next
until e == e_start
Computer-Graphik 1 - WS 07/08
v
e.next
e
Randrepräsentationen
34
C
G
C
Halbkanten DS für Nicht-Mannigfaltigkeiten
 Halbkanten DS repräsentiert 2-Mannigfaltigkeiten
Mesh erzeugen
 „Directed Edge DS“: Erweiterung von Halbkanten DS für
 Dabei Einhaltung bestimmter Kriterien (wird hier nicht weiter vertieft)
Dreiecksnetze, die an Ausnahmestellen keine Mannigfaltigkeit
 Elementare Operationen:
sind.
 Edge Collapse:
 Idee: Pointer auf Nachbar-Kanten als Integer Array-Index
 Benutze Vorzeichen des Index als Hinweis auf zusätzliche Information
- Benötigt alle Kanten adjazent zu e
 Interpretiere negative Indizes als Indizes zusätzlicher Arrays, z.B.
 Vertex Removal:
- Liste aller Kanten, die von Vertex ausgehen, oder
- Zusammenhangskomponenten an Vertex
- Benötigt alle Kanten inzident zu v
G. Zachmann
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
35
G. Zachmann
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
38
3
3/17/08
C
G
C
Die Euler-Formel
 Beschreibt Zusammenhang zwischen Anzahl #Vertices, #Kanten
C
G
C
Beweis (nach Cauchy)
 Gegeben: geschlossenes Mesh (Polyeder)
und #Facetten eines Polyeders:
 Erste Idee:
 V, E, F = Anzahl Vertices, Edges, Faces
 Entferne eine Facette (ergibt offenes Mesh; Rand ist genau der
 Beispiel:
Kantenzug der entfernten Facette)
V=8
E = 12
F =6
V=8
E = 12+1
F = 6 +1
 Ziehe Mesh an diesem Rand auseinander in planaren Graphen (geht
V = 8+1
E = 12+1+1
F = 6 +1
nur, wenn Polyeder homöomorph zu Kugel)
 Jetzt zu zeigen:
 Zweite Idee: trianguliere den Graphen (das Mesh)
 Satz (Eulerformel):
 Ziehe Diagonale in Facetten mit mehr als 3 Vertices ein
Für alle Polyeder, die homöomorph zu einer Kugel sind, gilt
 Es gilt weiterhin
G. Zachmann
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
G. Zachmann
45
C
G
C
 Der Graph hat einen Rand; Dreiecke haben 0, 1, oder 2 "Randkanten"
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
46
C
G
C
Anwendungen der Euler-Formel
 Zusammenhang zwischen #Dreiecken und
#Vertices in einem geschlossenen Dreiecks-Mesh:
 Wiederhole eine der folgenden beiden Transformartionen
 Jede Kante gehört zu genau 2 Dreiecken, also
 Falls es ein Dreieck mit genau 1 Randkante gibt,
lösche dieses Dreieck; es gilt
 Einsetzen in Euler-Formel:
 Falls es ein Dreieck mit genau 2 Randkanten gibt,
lösche dieses Dreieck; es gilt
 Bei großen Meshes gilt also
 Wiederhole, bis nur noch 1 Dreieck übrig
 Für das Dreieck gilt die Euler-Formel offensichtlich
 Da jede der obigen Transformationen den Wert von V-E+F unverändert
gelassen hat, gilt die Formel also auch für den ursprünglichen Graphen,
und damit auch für das ursprüngliche Mesh.
G. Zachmann
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
47
G. Zachmann
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
48
4
3/17/08
C
G
C
 Platonische Körper:
C
G
C
 Exkurs: die platonischen Polyeder waren mindest 1000 Jahre vor
Plato schon in Schottland bekannt
 Definition: ein konvexes Polyeder, das aus lauter gleichen
(kongruenten) regulären Polygonen besteht.
 Satz (Euklid):
Es gibt genau fünf platonische Körper.
G. Zachmann
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
G. Zachmann
49
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
50
C
G
C
Beweis
 Alle Facetten haben die gleiche Anzahl Kanten, n; also:
C
G
C
 Weitere Bedingung: m und n müssen jeweils > 3 sein
 Welche {m,n} erfüllen diese Bedingungen:
{3,3}
{3,4}
{4,3}
{5,3}
{3,5}
 An allen Vertices treffen sich die gleiche Anzahl Kanten, m; also
 Einsetzen in die Euler-Formel:
 Ergibt folgende Bedingung für m und n:
G. Zachmann
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
51
G. Zachmann
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
52
5
3/17/08
C
G
C
Die Euler-Charakteristik
 Achtung: die Euler-Formel gilt so nur für Polyeder, die topologisch
C
G
C
 Definition Euler-Charakteristik:
äquivalent zur Kugel sind!
 Beispiele:
Tetrahemihexahedron
Octahemioctahedron
 Beispiele:
Cubohemioctahedron
2
6 - 12 + 7 = 1
12 - 24 + 12 = 0
V
E
F
12 - 24 + 10 = -2
0
-4
-2
0
0
 Aber: die Größe V-E+F bleibt erhalten, egal wie man das Polyeder
verformt (homöomorph) → topologische Invariante
G. Zachmann
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
G. Zachmann
53
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
54
C
G
C
Die Euler-Poincaré-Formel
 Verallgemeinerung der Euler-Formel auf 2-mannigfaltige,
C
G
C
 Beispiele:
geschlossene Flächen:
 V = 16, E = 28, F = 14, S = 1, G = 0:
V - E + F = 2 = 2(S - G)
 G = # Henkel , S = # Shells (Schalen)
 Henkel (Loch, hole) = eine Schnur im Inneren eines Henkels kann man
nicht auf einen Punkt zusammenziehen
 V = 16, E = 32, F = 16, S = 1, G = 1:
 G = Genus
V - E + F = 0 = 2(S - G)
 Schale (shell) = durch Wandern auf der Schale kann man jeden Punkt
von jedem anderen aus erreichen
 Durch "innere" Schalen kann man sog. "Voids" (Aushöhlungen) aus
 V = 16+8, E = 32+12, F = 16+6,
einem Körper herausnehmen
G = 1, S = 2:
 Es gibt noch weitere Verallgemeinerungen!
G. Zachmann
Computer-Graphik 1 - WS 07/08
V - E + F = 2 = 2(S - G)
Randrepräsentationen
55
G. Zachmann
Computer-Graphik 1 - WS 07/08
Randrepräsentationen
56
6
3/17/08
C
G
C
 Achtung: der Genus ist manchmal nicht ganz einfach zu
bestimmen!
 Beispiel:
 Genus = 2
 "Beweis": topologisch
äquivalent deformieren,
bis Genus klar ist
1.
G. Zachmann
Computer-Graphik 1 - WS 07/08
2.
3.
Randrepräsentationen
57
7