Vorlesung Algorithmen für hochkomplexe Virtuelle Szenen · alle anderen werden durch Grafik-Pipeline dargestellt (Z-Buffer-Algorithmus) Visibility Culling Grundbegriffe . Vorlesung

© 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


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


■ 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


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


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


© 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


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


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


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


© 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


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


© 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


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


■ 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


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


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


[Quelle: David Luebke, University of Virginia]

Von diesem

Standpunkt aus

sind nur vier

Räume sichtbar


■ 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



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


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



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



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


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


© 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


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


© 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


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


A

D

H

F C B

E

G

H

B C D F G

E A

Der Betrachter steht in

einem Raum: E



© 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


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



© 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


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



© 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


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



© 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


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?



© 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


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



© 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


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.



© 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


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



© 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


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


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


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


© 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


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


© 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


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


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?


© 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


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


© 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


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.


© 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


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


© 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


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.


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


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


© 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


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!


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


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.


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


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.


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


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


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


© 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



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


Heuristik 2: Tiefensuche mit Zellentest


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


■ 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


© 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


Heuristik 3: Tiefensuche mit Portaltest


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


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


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


Heuristik 4: Exakte Eye-to-Cell Visiblity


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


■ H fällt in (3) jetzt auch weg.


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


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


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


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


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


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

Documents

Vorlesung Algorithmen für hochkomplexe Virtuelle Szenen · alle anderen werden durch Grafik-Pipeline dargestellt (Z-Buffer-Algorithmus) Visibility Culling Grundbegriffe . Vorlesung