© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 187 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Vorlesung
Algorithmen für hochkomplexe
Virtuelle Szenen
Sommersemester 2012
Matthias Fischer [email protected]
Vorlesung 6,7
15.5.12, 22.5.12
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 188 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Visibility Culling – Einführung und Übersicht
■ Motivation
■ Grundbegriffe
Übersicht
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 189 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
■ Tomas Akenine-Möller, Eric Haines
Real-Time Rendering
AK Peters, 2002
■ Frédo Durand
A multidisciplinary survey of visibility
SIGGRAPH 2000 course notes:Visibility, Problems, Techniques, and Applications
auch zu finden im 2.Teil der Dissertation von Durand:
Frédo Durand. 3D Visibility: Analytical Study and Applications. PhD thesis, Université
Joseph Fourier, 1999 (siehe Web)
■ Daniel Cohen-Or, Yiorgos L. Chrysanthou, Cláudio T. Silva, Frédo Durand
A survey of visibility for walkthrough applications
IEEE Transactions on Visualization and Computer Graphics, 9(3):412–431, 2003.
Literatur
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 190 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Sichtbarkeitsalgorithmen
Problem
■ Es sind nicht immer alle Teile eines Objektes sichtbar.
■ Trotzdem hängt der zeitliche Aufwand von allen Objekten ab,
man muss jedes Polygon einmal anfassen und prüfen, ob es sichtbar ist.
■ → Verschwendung von Rechenzeit
Lösungsansatz: Visibility Culling
Vermeide die Darstellung redundanter Geometrie
■ berechne einen Teil der unsichtbaren Polygone
■ alle anderen werden durch Grafik-Pipeline dargestellt
(Z-Buffer-Algorithmus)
Visibility Culling Grundbegriffe
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 191 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Wir unterscheiden drei Arten des Visibility Culling
object objectpoly gon
Frustum Culling Backface Culling Occlusion Culling
■ Frustum Culling
Objekte oder Polygone außerhalb des Sichtkegels werden nicht gezeichnet
■ Backface Culling
Polygone, die von hinten zu sehen sind, werden nicht gezeichnet
■ Occlusion Culling
Objekte, die im Sichtkegel hinter anderen Polygonen verdeckt liegen, werden nicht
gezeichnet
Visibility Culling Grundbegriffe
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 192 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Sichtbarkeitsprüfung
■ zusätzlicher Arbeitsprozess zwischen Anwendung und Rendering-Pipeline
■ durchgeführt vom Prozessor
(evtl. zusammen mit Funktionen der Grafikhardware,
bspw. Hardware-Occlusion-Test)
Anwendung Geometrie-
Transformation Rasterung
Visibility Culling
Visibility Culling Motivation
Grafikhardware, Library
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 193 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Warum führen wir Occlusion Culling durch?
■ Geometrie außerhalb des Frustums → wird durch Clipping entfernt
■ andere verdeckte Geometrie → wird durch den Z-Buffer gelöst
Der Grund ist Effizienz!
Wir wollen schneller sein als der Z-Buffer-Algorithmus !
Entscheidend für einen lohnenden Einsatz
■ Die Berechnung der unsichtbaren
Polygone durch die CPU darf nicht länger
dauern, als ihre „Darstellung“ durch die
Rendering-Pipeline (Z-Buffer-Algorithmus)
kosten würde!
■ Denn der Z-Buffer-Algorithmus löst das
Sichtbarkeitsproblem ja auch!
Visibility Culling Motivation
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 194 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Potentially Visible Sets
Wir berechnen keine exakte Sichtbarkeitslösung!
Vorgehensweise
1. Berechne schnell eine konservative Überschätzung der sichtbaren Primitive.
Die Menge nennen wir Potentially Visible Set (PVS).
2. Berechne die exakte Sichtbarkeit des PVS durch die Rendering-Pipeline (Z-Buffer, Clipping).
Visibility Culling Grundbegriffe
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 195 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Sei O die Menge der Objekte/Primitive in der virtuellen Szene
Für einen gegebenen Standpunkt sei:
■ S die Menge der sichtbaren Teile,
■ U die Menge der unsichtbaren Teile.
Man unterscheidet Methoden nach der Art,
wie sie das Visibility Culling-Problem lösen:
■ Exact Visibility
die Menge S wird berechnet
■ Conservative Visibility
die Menge S plus etwas aus U wird berechnet
(der Teil aus U soll möglichst klein sein)
■ Approximative Visibility
ein Teil von S plus etwas aus U wird berechnet
(der Teil aus S soll möglichst groß
der Teil aus U soll möglichst klein sein)
U S
U S
U S
Visibility Culling Grundbegriffe
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 196 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Occlusion Culling für
architektonische Modelle mit
Potentially Visible Sets
■ Ziele
■ Eigenschaften architektonischer Modelle
■ Idee der Methode
■ Berechnungsbeispiel
■ Schritte des Algorithmus
■ Adjazenzgraph
■ Cell-to-Cell Visibility
■ Eye-to-Cell Visibility
■ Objekte in Räumen
■ Beispiele
Übersicht
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 197 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
■ Tomas Akenine-Möller, Eric Haines
Real-Time Rendering
AK Peters, 2002
■ Frédo Durand
A multidisciplinary survey of visibility
SIGGRAPH 2000 course notes:Visibility, Problems, Techniques, and Applications
auch zu finden im 2.Teil der Dissertation von Durand:
Frédo Durand. 3D Visibility: Analytical Study and Applications. PhD thesis, Université
Joseph Fourier, 1999 (siehe Web)
■ Daniel Cohen-Or, Yiorgos L. Chrysanthou, Cláudio T. Silva, Frédo Durand
A survey of visibility for walkthrough applications
IEEE Transactions on Visualization and Computer Graphics, 9(3):412–431, 2003.
■ Seth J. Teller, Carlo H. Séquin
Visibility preprocessing for interactive walkthroughs
Proc. 18th Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '91),
p. 61—70, 1991.
http://doi.acm.org/10.1145/122718.122725
Literatur
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 198 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Ziele
■ ein Walkthrough durch architektonische Modelle
(Gebäude, Räume)
■ wir möchten Occlusion Culling durchführen
und dabei möglichst wenig Objekte rendern
Wir nutzen die besonderen Eigenschaften architektonischer Modelle aus!
Was sind die besonderen Eigenschaften?
Occlusion Culling mit Potentially Visible Sets Ziele
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 199 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Eigenschaften architektonischer Modelle
■ relativ hoher Verdeckungsgrad durch Wände und Stockwerke
■ „regelmäßige“ Aufteilung in:
▪ verdeckende Elemente
Räume, Flure, Nischen
▪ nicht verdeckende Elemente
Durchgänge, Türen (offen), Fenster
Occlusion Culling mit Potentially Visible Sets Eigenschaften architektonischer Modelle
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 200 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
[Quelle: David Luebke, University of Virginia]
Von diesem
Standpunkt aus
sind nur vier
Räume sichtbar
Occlusion Culling mit Potentially Visible Sets Eigenschaften architektonischer Modelle
■ Menschen erkennen gut,
was Räume und Türen sind.
■ Aber wie erkennt und
berechnet man Räume und
Türen ?
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 201 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Occlusion Culling mit Potentially Visible Sets Eigenschaften architektonischer Modelle
Menschen haben eine Vorstellung davon, was Räume und Türen sind!
Wie erkennt und berechnet unser Algorithmus Räume und Türen ?
Gibt es hier 2 Räume mit Tür oder ist es 1 Raum mit Eckpfeilern?
Wie viel Räume haben wir hier?
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 202 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Wir führen zwei elementare strukturelle Elemente ein:
Zelle
■ definiert einen „Raum“, der durch Wände und Portale umschlossen ist
■ Wände sind grundsätzlich undurchsichtig
■ z.B.: Räume, Flure, Nischen
Portal
■ definiert den durchsichtigen oder offenen Teil eines Raumes
■ z.B.: Durchgänge, Türen (offen), Fenster
Die 3D-Szene setzt sich aus Portalen und Zellen zusammen
Occlusion Culling mit Potentially Visible Sets Idee der Methode
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 203 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Occlusion Culling mit Potentially Visible Sets Idee der Methode
Eine Berechnungsidee
Zellen und Portale entsprechen nicht immer unserer Vorstellung von Räumen und Türen.
Wie erkennen und berechnen wir Räume und Türen ?
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 204 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Occlusion Culling mit Potentially Visible Sets Idee der Methode
Eine Berechnungsidee
Partitioniere in der 2D-Grundrissansicht den Raum:
Kennzeichne alle „Öffnungen“ als Portale.
Füge auch da Portale ein, wo wir keine Öffnungen definieren würden,
um den Raum in konvexe Zellen zu aufzuteilen.
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 205 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Idee der Methode
Wir teilen die Sichtbarkeitsberechnungen auf:
Cell-to-Cell Visibility
■ wird im Preprocessing berechnet, also vor dem Walkthrough
■ wir berechnen standpunktunabhängige Sichtbarkeitsaussagen
Eye-to-Cell Visibility
■ wird während des Walkthrough berechnet
■ wir berechnen standpunktabhängige Sichtbarkeitsaussagen
Occlusion Culling mit Potentially Visible Sets Idee der Methode
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 206 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Idee des Verfahrens
Im Preprocessing:
■ Zellen sind die elementaren Elemente des PVS
■ berechne einen Adjazenzgraphen, der benachbarte Zellen verbindet
Während des Walkthrough:
1. starte mit der Zelle, in der der Beobachter steht
2. traversiere den Adjazenzgraph / Stabtree (einen Teil davon)
3. rendere die sichtbaren Zellen:
eine Zelle ist nur sichtbar, wenn sie durch eine Folge von Portalen zu sehen ist
→ die Sichtbarkeit einer Zelle reduziert sich auf das
Testen von Sichtlinien durch eine Folge von Portalen
Occlusion Culling mit Potentially Visible Sets Idee der Methode
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 207 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
A
D
H
F C B
E
G
H
B C D F G
E A
Zellen
Räume A bis H
Portale
Fenster, Türen in rot
Adjazenzgraph
verbindet benachbarte
Räume, die über Portale
„verbunden“ sind
[Bilder: David Luebke, University of Virginia]
Occlusion Culling mit Potentially Visible Sets Berechnungsbeispiel
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 208 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
A
D
H
F C B
E
G
H
B C D F G
E A
Der Betrachter steht in
einem Raum: E
[Bilder: David Luebke, University of Virginia]
Occlusion Culling mit Potentially Visible Sets Berechnungsbeispiel
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 209 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
A
D
H
F C B
E
G
H
B C D F G
E A
Der Betrachter sieht
■ alles in seinem Raum
■ und die drei Portale
zu den
Räumen D, F, und G
[Bilder: David Luebke, University of Virginia]
Occlusion Culling mit Potentially Visible Sets Berechnungsbeispiel
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 210 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
A
D
H
F C B
E
G
H
B C D F G
E A
Durch die Portale sieht er
in die benachbarten
Räume D, F, G
[Bilder: David Luebke, University of Virginia]
Occlusion Culling mit Potentially Visible Sets Berechnungsbeispiel
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 211 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
A
D
H
F C B
E
G
H
B C D F G
E A
… und von dort zu deren
benachbarten Räumen: A
[Bilder: David Luebke, University of Virginia]
Occlusion Culling mit Potentially Visible Sets Berechnungsbeispiel
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 212 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
A
D
H
F C B
E
G
H
B C D F G
E A
So wie A ist auch H ein
Nachbar von D
Kann man in alle
benachbarten Räume
sehen?
[Bilder: David Luebke, University of Virginia]
Occlusion Culling mit Potentially Visible Sets Berechnungsbeispiel
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 213 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
A
D
H
F C B
E
G
H
B C D F G
E A
… nein,
nur wenn es eine direkte
Sichtlinie von E nach H
geben würde
[Bilder: David Luebke, University of Virginia]
Occlusion Culling mit Potentially Visible Sets Berechnungsbeispiel
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 214 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
A
D
H
F C B
E
G
H
B C D F G
E A
Wir müssen unterscheiden:
Von Zelle E aus ist
■ Raum H für den gelben
Betrachter unsichtbar,
■ aber der grüne
Betrachter sieht H
■ Raum B ist jedoch für
beide Betrachter
unsichtbar.
■ Es gibt keine
Standpunkte in Zelle E,
von denen aus Zelle B
sichtbar ist.
[Bilder: David Luebke, University of Virginia]
Occlusion Culling mit Potentially Visible Sets Berechnungsbeispiel
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 215 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
A
D
H
F C B
E
G
H
B C D F G
E A
Für einen Betrachter in
Zelle E, kann die
Sichtbarkeit von
■ Raum H
während des
Walkthroughs zur
Laufzeit
standpunktabhängig
berechnet werden
(Eye-to-Cell Visibility),
■ Raum B
im Preprocessing
standpunktunabhängig
berechnet werden
(Cell-to-Cell Visibility).
[Bilder: David Luebke, University of Virginia]
Occlusion Culling mit Potentially Visible Sets Berechnungsbeispiel
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 216 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Welche Probleme sind jetzt zu lösen?
Preprocessing
1. wie wird der Adjazenzgraph berechnet?
2. Cell-to-Cell Visibility:
▪ Wie berechnen wir die Menge der Zellen,
die von mindestens einem Standpunkt einer Zelle aus sichtbar sind?
▪ Wir betrachten alle Standpunkte der Zelle (standpunktunabhängig).
Walkthrough
3. Eye-to-Cell Visibility:
▪ Wie berechnen wir die Menge der Zellen,
die von einem festen Standpunkt der Zelle sichtbar sind?
▪ Wir betrachten einen Standpunkt der Zelle (standpunktabhängig)?
4. wie werden Objekte in den Räumen behandelt (Inventar, Ausstattung, …)?
Occlusion Culling mit Potentially Visible Sets Schritte des Algorithmus
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 217 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
1. Wie wird der Adjazenzgraph berechnet?
Modellierung
■ Wir modellieren das Stockwerk eines Gebäudes durch die Grundrisse.
■ Die Wände und Portale werden auf die Grundrisse projiziert.
■ Wir nehmen einschränkend an, dass alle Wände senkrecht zueinander stehen.
■ Grundrisse sind jetzt eine Menge von 2D Liniensegmenten.
→ wir erhalten ein 2D-Problem mit achsenparallelen Liniensegmenten
Lösungsansatz
■ zur räumlichen Aufteilung der Szene verwenden wir einen 2D-BSP-Baum
■ die Blätter des BSP-Baum stellen räumliche Bereiche dar, die unsere Zellen bilden
Occlusion Culling mit Potentially Visible Sets Adjazenzgraph
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 218 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Wie bauen wir aus den Liniensegmenten einen
2D-BSP-Baum?
Die Segmente werden als Splittinggeraden gewählt
(automatische Aufteilung).
Wie wählen wir die Splittinggeraden?
Wenn „Spanning faces“ existieren,
wähle davon das mittlere Segment.
Spanning Faces: sind Segmente,
die eine Zelle teilen ohne andere Segmente zu schneiden.
Anderenfalls:
■ Wähle ein Segment, das möglichst wenig andere
Segmente schneidet.
■ Bei gleicher Anzahl wähle das mittlere Segment.
0
0
0 0 0 0
2 2
1 1 1 1 1 1
Spanning Face
Occlusion Culling mit Potentially Visible Sets Adjazenzgraph
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 219 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Aus dem BSP-Baum konstruieren wir den Adjazenzgraph
■ Die Regionen der Blätter des BSP-Baums bilden die Zellen.
■ Jedes Blatt ist ein Knoten im Adjazenzgraph.
■ Knoten werden genau dann durch eine Kante verbunden, wenn die
Zellen benachbart sind und zwischen beiden Zellen ein Portal existiert.
Beispiel: Zellen mit Adjazenzgraph
Occlusion Culling mit Potentially Visible Sets Adjazenzgraph
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 220 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
2. Wie werden die von einer Zelle aus sichtbaren Nachbarzellen berechnet?
Was bedeutet Cell-to-Cell Visibility?
■ Welche direkt oder indirekt benachbarten Zellen sind von den Positionen einer fest gewählten
Zelle C sichtbar?
■ Das entspricht einem 360° Beobachter,
der an allen Positionen einer Zelle C steht und alle sichtbaren Zellen notiert.
■ Eine Zelle gehört dazu, sobald es einen Standpunkt
in C gibt, von dem sie sichtbar ist.
Beispiel:
■ Für Zelle E besteht die „Cell-to-Cell Visibility“
aus den Zellen F,G,H,D,A.
■ Die Zellen B und C sind für alle Standpunkte
in Zelle E unsichtbar.
Occlusion Culling mit Potentially Visible Sets Cell-to-Cell Visibility
E F H
G
C
B A D
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 221 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Cell-to-Cell Visibility
→ Positionsunabhängige Berechnung der Sichtbarkeit im Preprocessing möglich!
Welche Datenstruktur wählen wir zur Speicherung/Repräsentation der „Cell-to-Cell Visibility“ ?
Einfache Möglichkeit
speichere zu jeder Zelle C, eine Liste mit allen von C aus sichtbaren Zellen
Besser: Stabtree
Was ist das?
Und warum ist das besser?
Occlusion Culling mit Potentially Visible Sets Cell-to-Cell Visibility
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 222 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Wir speichern die „Cell-to-Cell Visibility“ einer festgewählten Zelle C als:
Stabtree
■ Der Stabtree ist ein Baum mit der fest gewählten Zelle C als Wurzel.
■ Jeder Knoten im Stabtree entspricht einer Zelle, die von mindestens einer Position in C
sichtbar ist.
■ Zwei Knoten sind durch eine Kante verbunden, wenn sie durch ein Portal direkt
benachbart sind.
Dies ist aus dem Adjazensgraphen bekannt!
■ Ein Pfad von der Wurzel zu einem beliebigen inneren Knoten oder Blatt entspricht einer
Portalsequenz, durch die der Betrachter von C aus durch alle Zellen sieht
(Knoten des Pfades).
Occlusion Culling mit Potentially Visible Sets Cell-to-Cell Visibility
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 223 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
E
F
H
D
A
E F
H
G
C
B A D
G
Beispiel: Stabtree
■ Die Zellen B und C können von
keiner Position in Zelle E
eingesehen werden.
■ In rot die Sichtline und
Protalsequenz über die Knoten
E,F,G.
Occlusion Culling mit Potentially Visible Sets Cell-to-Cell Visibility
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 224 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Berechnung einer Sichtlinie, die durch eine Folge von
Portalen läuft
■ Eine Folge von Portalen entsteht durch traversieren des
Adjazenzgraphen.
■ Für jedes traversierte Portal speichern wir die Endpunkte des
Portals in den Mengen 𝐿𝑝 und 𝑅𝑝.
Eine Sichtlinie kann die Folge von Portalen nur durchstechen,
wenn die Mengen 𝐿𝑝 und 𝑅𝑝 linear trennbar sind.
Wir reduzieren also:
■ die Sichtbarkeit einer Zelle,
■ auf das Testen von Sichtlinien durch eine Folge von Portalen.
L
L
L L
L
L
R
R
R
R
R
R
Occlusion Culling mit Potentially Visible Sets Cell-to-Cell Visibility
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 225 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Lineare Separierbarkeit
Zwei Mengen A,B von Punkten im 2D heißen linear trennbar
(separierbar),
■ wenn es eine Gerade gibt,
■ sodass die Punktmenge A vollständig auf der einen Seite von der
Geraden liegt
■ und die Punktemenge B vollständig auf der anderen Seite liegt.
→ Lineare Separierbarkeit kann in linearer Zeit gelöst werden
Nimrod Megiddo
Linear-Time Algorithms for Linear Programming in ℝ𝟑 and Related Problems
SIAM Journal on Computing,12(4): 759-776, 1983.
Übersichtsartikel:
D. Elizondo
The linear separability problem: some testing methods
IEEE Transactions on Neural Networks, 17(2): 330 - 344, 2006.
Occlusion Culling mit Potentially Visible Sets Cell-to-Cell Visibility
A
B
L
L
L L
L
L
R
R
R
R
R
R
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 226 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Das finden einer Geraden 𝑆 durch eine Portalsequenz,
die in zwei Mengen aufgeteilt ist, lässt sich als lineares
Programm formulieren und lösen
𝑆 ∗ 𝐿 ≥ 0, ∀𝐿 ∈ 𝐿𝑝
𝑆 ∗ 𝑅 ≤ 0, ∀𝑅 ∈ 𝑅𝑝
Für eine Folge von 𝑚 Portalen ist dies ein Problem der
linearen Programmierung mit 2𝑚 Randbedingungen
→ kann in linearer Zeit 𝑂(𝑚) gelöst werden
L
L
L L
L
L
R
R
R
R
R
R
Occlusion Culling mit Potentially Visible Sets Cell-to-Cell Visibility
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 227 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Wie komme ich an die beiden Mengen?
Woher wissen wir,
welche Eckpunkte eines Portal
in welche der beiden Mengen 𝐿𝑝 und 𝑅𝑝 kommen?
→ Portalsequenz legt eine Richtung fest!
Occlusion Culling mit Potentially Visible Sets Cell-to-Cell Visibility
A
B
L
L
L L
L
L
R
R
R
R
R
R
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 228 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Wie berechnen wir für eine gegebene Zelle C alle von C
aus sichtbaren Zellen und den Stabtree für C?
■ Wir starten mit der Zelle C und
■ berechnen in einer Art Tiefensuche über den
Adjazensgraphen Portalsequenzen, durch die sich eine
Sichtlinie legen lässt.
■ Dabei bauen wir sukzessive den Stabtree für Zelle C auf.
■ Jede Portalsequenz entspricht einem Pfad im Stabtree,
der immer bei der Wurzel startet und
bei einem Blatt oder inneren Knoten endet.
■ Nicht verlängerbare Portalsequenzen entsprechen
Pfade von der Wurzel bis zu einem Blatt.
■ Verlängerbare Pfade entsprechen
Pfade von der Wurzel zu einem inneren Knoten.
Occlusion Culling mit Potentially Visible Sets Cell-to-Cell Visibility
E F H
G
C
B A D
E
F
H
D
A G
nicht
verlängerbare
Portalsequenz
verlängerbare
Portalsequenz
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 229 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Wie berechnen wir für eine gegebene Zelle C alle von C aus sichtbaren Zellen V
und den Stabtree S für C?
Algorithmus: Berechnung des Stabtree
Wir rufen initial auf: Find_Visible_Cells( C, ∅ , ∅, C)
Find_Visible_Cells( cell C, Portal-Sequenz P, visible-cell-set V, stabtree S)
V := V+C
for each Nachbar N von C
for each Portal p, das C und N verbindet
• orientiere p von C nach N
• P* := P + p (füge p hinten an die Portalsequenz P)
• if Stabbing_Line(P*) existiert
then füge N als Kind von C in Stabtree S ein
Find_Visible_Cells(N, P*, V)
Stabbing_Line(P):
Berechnet, ob für eine gegebene Folge von Portalen P
eine Sichtlinie existiert, die alle Portale durchquert.
Occlusion Culling mit Potentially Visible Sets Cell-to-Cell Visibility
C
N N N
p p p p
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 230 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
3. Wie berechnen wir die Eye-to-Cell Visibility?
Was passiert während dem Walkthrough durch die Szene?
■ Wir verwenden den Stabtree von der Zelle, in der der Beobachter steht.
■ Wir rendern alle Zellen des Stabtree ! ???
Aber:
■ Dies entspricht einem 360 Grad Beobachter,
■ der an allen Positionen in seiner Zelle steht!
Wie können wir die Anzahl sichtbarer Zellen weiter reduzieren?
Occlusion Culling mit Potentially Visible Sets Eye-to-Cell Visibility
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 231 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Beispiel
■ O ist die Zelle, die den Betrachter enthält,
■ C ist das Frustum,
■ S ist der Stabtree und
■ V die Menge aller von O sichtbaren Zellen
also O, D, E, F, G, H
Eye-to-Cell Visibility
■ Wir führen ein Culling aller Zellen V des Stabtree mit dem Frustum C durch,
■ prüfen welche davon vom Beobachter aus sichtbar sind
■ und rendern nur diese Zellen.
Wie prüfen wir,
welche Zellen des Stabtree im Frustum liegen und vom Beobachter aus sichtbar sind?
O E
G
H
D
F
Occlusion Culling mit Potentially Visible Sets Eye-to-Cell Visibility
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 232 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Occlusion Culling mit Potentially Visible Sets Eye-to-Cell Visibility
Heuristik 1: Zellentest mit Frustum
■ Alle Zellen des Stabtree werden unsortiert in einer Liste
gespeichert.
■ Mehrfach auftretende Zellen werden nur einfach
gespeichert.
Während dem Walkthrough
■ Durchlaufe in jedem Frame die vollständige Liste und prüfe
jede einzelne Zelle, ob sie sich mit dem Frustum schneidet.
■ Der Stabtree selbst wird während dem Walkthrough nicht
benutzt.
Beobachtung: Mit dieser Heuristik
■ fallen in (1) E, F und D weg,
■ aber G und H bleiben, obwohl sie unsichtbar sind.
O E
G
H
D
F
1
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 233 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Heuristik 2: Tiefensuche mit Zellentest
Während dem Walkthrough
■ Wir führen eine Tiefensuche im Stabtree S durch und
starten an der Wurzel in der Zelle O, in der der Betrachter
steht.
■ An jedem Stabtree-Knoten testen wir, ob die dazugehörige
Zelle das Frustum schneidet.
■ Wir brechen die Tiefensuche an jedem Knoten ab, dessen
Zelle außerhalb des Frustum liegt.
Beobachtung: Mit dieser Heuristik
■ fallen in (1) auch G und H weg,
■ aber G und H bleiben in (2), obwohl sie unsichtbar sind.
O E
G
H
D
F
O E
G
H
D
F
1
2
Occlusion Culling mit Potentially Visible Sets Eye-to-Cell Visibility
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 234 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Heuristik 3: Tiefensuche mit Portaltest
Während dem Walkthrough
■ Wir führen eine Tiefensuche im Stabtree S durch und
starten an der Wurzel in der Zelle O, in der der Betrachter
steht.
■ An jedem Stabtree-Knoten testen wir, ob das Portal
(Stabtreekante), über das wir die Zelle des Knotens erreicht
haben, das Frustum schneidet.
■ Wir brechen die Suche an jedem Knoten ab,
wenn das getestete Portal außerhalb des Frustum liegt.
Beobachtung: Mit dieser Heuristik
■ fallen in (2) jetzt G und H weg
(Portal G-F ist außerhalb des Frustum),
■ aber H bleibt in (3), obwohl H unsichtbar ist.
Occlusion Culling mit Potentially Visible Sets Eye-to-Cell Visibility
O E
G
H
D
F
2
O E
G
H
D
F
3
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 235 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Heuristik 4: Exakte Eye-to-Cell Visiblity
Während dem Walkthrough
■ Wir führen eine Tiefensuche im Stabtree S durch und starten
an der Wurzel in der Zelle O, in der der Betrachter steht.
■ An jedem Stabtree-Knoten testen wir für die Portalsequenz
von der Wurzel zu dem Knoten, ob eine Sichtlinie durch alle
Portale existiert.
■ Wir brechen die Suche an jedem Knoten ab, wenn keine
solche Sichtlinie existiert.
Beobachtung: Mit dieser Heuristik
■ H fällt in (3) jetzt auch weg.
Occlusion Culling mit Potentially Visible Sets Eye-to-Cell Visibility
O E
G
H
D
F
3
Wie berechnen wir die Sichtlinie?
■ so wie beim Aufbau des Stabtree
■ lineare Separierbarkeit anwenden
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 236 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
Die vier vorgestellten Möglichkeiten unterscheiden sich in:
■ Genauigkeit:
Wie viele unsichtbare Zellen werden als unsichtbar erkannt?
■ Geschwindigkeit:
Wie lange dauert die Berechnung?
Abhängig von der Topologie der virtuellen Szene sind unterschiedliche
Verfahren sinnvoll !
Welche Methode wendet man für welchen Szenentyp an?
Vergleiche mit der Laufzeit.
→ siehe Übung
Occlusion Culling mit Potentially Visible Sets Eye-to-Cell Visibility
O E
G
H
D
F
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 237 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
4. Was passiert mit Objekten, die in Räumen enthalten sind?
Woraus besteht eine virtuelle Szene?
■ Zellen (s.o.)
■ Portalen (s.o.)
■ der Einrichtung, die in einer Zelle vorhanden ist
(Stühle, Tische, Schränke, ….)
Wie wird die Einrichtung behandelt?
■ wird zusammen mit einer Zelle gerendert
■ geht hier in die Sichtbarkeitsberechnungen nicht ein
Occlusion Culling mit Potentially Visible Sets Objekte in Räumen
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 238 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
mit Stabtree
Occlusion Culling mit Potentially Visible Sets Beispiele
mit Sichtlinien
Zelle des Betrachters in dunkelblau
© P
rof.
Dr.
math
. F
. M
eyer
auf
der
Heid
e,
Hein
z N
ixdorf
Institu
t, U
niv
ers
ität P
aderb
orn
, B
ild: ©
Fo
tolia
, to
m
Matthias Fischer 239 Vorlesung » Algorithmen für hochkomplexe Virtuelle Szenen «, SS 2012
60 Grad Betrachter
■ hellblau: Eye-to-Cell Visibility
■ grün: durch Eye-to-Cell Visibility weggefallen
Occlusion Culling mit Potentially Visible Sets Beispiele
360 Grad Betrachter