AlgorithmenDerComputergraphik (PDF)

Universität Paderborn

Sommersemester 2009

S KRIPT ZUR VORLESUNG

Algorithmen der Computergraphik
Dozent: Dr. Matthias Fischer

Christian Heinzemann
15. Dezember 2009

Inhaltsverzeichnis
1 Walkthrough-Problem
1.1 Rendering Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Z-Buffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Walkthrough-Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Trees
2.1 kd-Bäume . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Konstruktion . . . . . . . . . . . . . . . . .
2.1.2 Bereichsanfragen . . . . . . . . . . . . . . .
2.1.3 Zusammenfassung der Eigenschaften . . . .
2.2 BSP-Bäume . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Grundidee . . . . . . . . . . . . . . . . . . .
2.2.2 Anwendungsbeispiel: Painter’s Algorithmus
2.2.3 Konstruktion - 2D . . . . . . . . . . . . . .
2.2.4 Konstruktion - 3D . . . . . . . . . . . . . .
2.3 Quadtrees und Octrees . . . . . . . . . . . . . . . .
2.3.1 Speichern von Elementen . . . . . . . . . .
2.3.2 Aufbau . . . . . . . . . . . . . . . . . . . .
2.3.3 Suche im Quadtree . . . . . . . . . . . . . .
2.3.4 Balancierte Quadtrees . . . . . . . . . . . .
2.4 Loose Octrees . . . . . . . . . . . . . . . . . . . . .
2.4.1 Konstruktion . . . . . . . . . . . . . . . . .
2.4.2 Nutzen . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

3 Visibility Culling
3.1 Potentially Visible Sets . . . . . . . . . . . . . . . . . . . .
3.2 Occlusion Culling mit Potentially Visible Sets . . . . . . . .
3.2.1 Idee der Methode . . . . . . . . . . . . . . . . . . .
3.2.2 Berechnung des Adjazenzgraphen . . . . . . . . . .
3.2.3 Berechnung der Cell-to-Cell Visibility . . . . . . . .
3.2.4 Berechnung der Eye-to-Cell Visibility . . . . . . . .
3.2.5 Objekte in Räumen . . . . . . . . . . . . . . . . . .
3.3 Dynamische Berechnung von Potentially Visible Sets (PVS)
3.4 Hierarchischer Z-Buffer . . . . . . . . . . . . . . . . . . . .
3.4.1 Grundideen . . . . . . . . . . . . . . . . . . . . . .
3.4.2 Z-Pyramide . . . . . . . . . . . . . . . . . . . . . .

I

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

1
1
2
3

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

4
4
4
6
10
10
10
11
13
16
19
20
21
23
23
29
30
33

.
.
.
.
.
.
.
.
.
.
.

35
37
38
38
39
40
41
43
43
45
45
46

Inhaltsverzeichnis

3.5

3.6

3.4.3 Verwendung der Z-Pyramide . . . . . . . . .
3.4.4 Rendering mit dem Hierarchischen Z-Buffer
3.4.5 Hardwareunterstützung . . . . . . . . . . . .
Hierarchical Occlusion Maps (HOM) . . . . . . . .
3.5.1 Der HOM-Algorithmus . . . . . . . . . . . .
3.5.2 Betrachtung der Teilschritte . . . . . . . . .
3.5.3 Approximatives Visibility Culling . . . . . .
Zusammenfassung . . . . . . . . . . . . . . . . . .

4 Replacement
4.1 Rendering mit Color-Cubes . . . . . . .
4.1.1 Datenstruktur . . . . . . . . . .
4.1.2 Rendering . . . . . . . . . . . .
4.1.3 Aufbau der Hierarchie . . . . .
4.1.4 Aufwandsabschätzung . . . . .
4.1.5 Bildqualität . . . . . . . . . . .
4.2 Hierarchical Image Caching . . . . . .
4.2.1 Erster Rendering Durchlauf . .
4.2.2 Zweiter Rendering Durchlauf .
4.2.3 Partitionierung der Szene . . . .
4.2.4 Berechnung der Splittingebenen
4.2.5 Fehlermetrik . . . . . . . . . .
4.2.6 Artefakte . . . . . . . . . . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

47
49
50
50
51
52
55
55

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

56
56
56
57
57
59
60
62
63
64
64
66
67
68

5 Paralleles Rendering
5.1 Paralelles Rendering als Sortierproblem . . . . . . .
5.1.1 Sort-First . . . . . . . . . . . . . . . . . . .
5.1.2 Sort-Middle . . . . . . . . . . . . . . . . . .
5.1.3 Sort-Last . . . . . . . . . . . . . . . . . . .
5.2 Hybrides Sort-First / Sort-Last Rendering . . . . . .
5.2.1 Grundidee der Partitionierung . . . . . . . .
5.2.2 Ablauf des Rendering . . . . . . . . . . . .
5.2.3 Partitionierungs-Algorithmus . . . . . . . .
5.2.4 Abschätzung des Kommunikations-Overhead

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

69
70
70
71
72
74
74
75
76
77

6 Level of Detail
6.1 Arten des Level of Detail . . . . . . . . .
6.1.1 Discrete Level of Detail . . . . .
6.1.2 Continuous Level of Detail . . . .
6.1.3 View-Dependent Level Of Detail .
6.2 LOD - Hierarchie . . . . . . . . . . . . .
6.3 Automatische Frameratenregulierung . .
6.4 Vereinfachung von Polygonmodellen . . .
6.4.1 Decimation . . . . . . . . . . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

79
80
80
80
80
80
81
82
82

AlgoCG 09

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

II

Inhaltsverzeichnis
.
.
.
.
.
.
.
.
.

83
84
84
85
85
86
87
87
88

7 Aspect Graph und Viewpoint Space Partition
7.1 Viewpoint Space Partition . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 Aspect Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

89
89
91

AlgoCG 09

III

6.5

6.4.2 Sampling . . . . . . . . . . . . . . . . . .
6.4.3 Vertex Merging . . . . . . . . . . . . . . .
6.4.4 Adaptive Subdivision . . . . . . . . . . . .
Schrittweise Verfeinerung mit Progressive Meshes .
6.5.1 Vergröberung . . . . . . . . . . . . . . . .
6.5.2 Verfeinerung . . . . . . . . . . . . . . . .
6.5.3 Messung der Qualität . . . . . . . . . . . .
6.5.4 Verfeinerungsalgorithmus . . . . . . . . .
6.5.5 Anwendungen . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

1 Walkthrough-Problem
Das Ziel ist die effiziente Berechnung von 3D-Ansichten in einem Walkthrough-System, d.h.
die Ansicht wird durch die Bewegung des Anwenders bestimmt und kann nicht im Voraus
berechnet werden, wie dies bei Animationsfilmen möglich ist. Die Berechnung muss deshalb
in Echtzeit erfolgen, wodurch besondere Anforderungen an die Effizienz der verwendeten
Algorithmen entstehen. Die einzelnen Algorithmen sind in einer sogenannten RenderingPipeline angeordnet und werden nacheinander ausgeführt.

1.1 Rendering Pipeline
Das Rendering ist der Vorgang zum Erstellen von 2D Bildern aus einer 3D-Szene zum Anzeigen auf einem Display. Die Rendering Pipeline in Abbildung 1.1 beschreibt die Anordnung
der dafür notwendigen Algorithmen.
3D-Modell erstellen
(Modellierung)

3D → 2D
Transformation

Versteckte Kanten
entfernen
(Culling, Z-Buffer)

Rasterung,
Anti-Aliasing

Beleuchtung

Abbildung 1.1: Rendering Pipeline.
Zunächst wird ein 3D-Modell der Szene erstellt. Oberflächen werden durch ein feines Zusammensetzen von Polygonen (Dreiecken) modelliert. Dadurch entsteht ein feines Netz von Polygonen. Jedes Dreieck ist durch die 3D-Koordinaten seiner drei Eckpunkte gegeben. Anschließend wird das 3D-Objekt über Geometrietransformationen auf 2DBildschirmkoordinaten abgebildet und dann beleuchted. Danach werden die nicht-sichtbaren
Kanten entfernt und das entstandene Bild wird gerastert, d.h. es wird auf eine 2D-Pixel-Fläche
abgebildet.
Die Rendering-Pipeline nutzt als Primitiven nur Dreiecke, Linien und Punkte. Oberflächen
und Kurven werden über NURBS (Non-Uniform Rational B-Spline) aus den Grundprimitiven
approximiert.
Die auf dem Prozessor ausgeführte Anwendung berechnet die Objekte der Szene über Libraries wie OpenGL oder DirectX, die Grafikkarte übernimmt die Geometrietransformationen
und die Rasterung.

1

Kapitel 1. Walkthrough-Problem

1.2 Z-Buffer
Für die Darstellung einer Szene braucht man zwei Puffer: den Z-Buffer und den Framebuffer.
Der Z-Buffer ist ein 2-dimensionales Feld in der Größe der Bildschirmauflösung, dass für
jedes Pixel den Tiefenwert (z-Wert) speichert. Dies ist die Entfernung zum Betrachter.
Der Framebuffer enthält die Pixel der vordersten Oberfläche, je Pixel mindestens einen
Farbwert.
Algorithmus 1 Z-Buffer Algorithmus
1: function Z-B UFFER( )
2:
Setze alle Einträge im z-Buffer auf Hintergrundentfernung
3:
Setze alle Einträge im Frame-Buffer auf Hintergrundfarbe
4:
for all Polygone P do
5:
Projiziere Polygon P auf Bildschirmebene
6:
Transformiere Resultat in Rasterkoordinaten (Pixel)
7:
for all Pixel (u, v) des Polygons do
8:
p := z - Koordinate des Polygons im Pixel (u, v)
9:
z := Eintrag im z-Buffer für das Pixel (u, v)
10:
if p < z then
11:
z-Buffer (u, v) := p
12:
Frame-Buffer (u, v) := Farbe(P, u, v)
13:
end if
14:
end for
15:
end for
16:
return success
17: end function
Die äußere For-Schleife für die Geometrietransformation aus, die innere die Rasterung.
Eine Szene, bei der die Geometrietransformation die Laufzeit dominiert, ist eine Szene mit
sehr vielen kleinen Objekten, von denen viele vielleicht gar nicht sichtbar sind. Diese müssen
alle explizit gerendert werden, obwohl sie jeweils nur eine kleine Anzahl von Pixeln haben.
Im Gegensatz dazu ist bei einer großen Fläche der Aufwand für die Geometrietransformation
gering, während viele Pixel gerastert werden müssen.
Vorteile
Nachteile
• einfach, keine Sortierung

• Alle Polygone werden gerendert

• gute Hardware-Unterstützung

• Lineare Laufzeit

• einfach zu parallelisieren

• Keine Zusammenhänge im Objektraum
• Größe der Szene beschränkt (für Echtzeitrendering)

AlgoCG 09

2

Kapitel 1. Walkthrough-Problem

1.3 Walkthrough-Systeme
Zunächst hat man eine 3D-Szene, die aus Objekten besteht, die über Polygone modelliert sind.
In einem Walkthrough-System kann sich der Betrachter frei durch die Szene bewegen. Dazu
werden die Position und die Orientierung der Kamera verändert. Die Bilder können damit
nicht vorberechnet werden, sollen aber dennoch eine hohe Qualität aufweisen. Das Rendering
muss somit in Echtzeit passieren.
Damit eine Bilderzeugung als ruckelfrei empfunden wird, benötigt man mindestens eine
Framerate von 20-30 fps. Werden alle Polygone zur Graphikkarte geschickt, erhält man ab einer bestimmten Anzahl von Polygonen keine akzeptablen Renderingzeiten mehr. Dafür benötigt man Verfahren mit sublinearer Laufzeit. Die Laufzeit soll abhängig von der Bildschirmauflösung, aber unabhängig von der Anzahl der Polygone sein.
Eine Beschleunigung der Laufzeit erreicht man durch:
1. Vermeide alle Polygone an die Graphikkarte zu schicken.
2. Vermeide häufige „Zustandswechsel“ (Farbe, Transformationen, ...)
3. Nutze spezielle CPU/GPU Befehle
Über (1) wird die Größe der darzustellenden Szene reduziert, d.h. es wird nur noch der
relevante Teil gerendert. Über (2) und (3) wird die Anzahl der Rechenschritte reduziert und
beschleunigt, die für die Darstellung eines Polygons notwendig sind.
Damit
verbessern (2) und (3)-die
Konstanten der Laufzeit, (1) hingegen
verbessert
die asymHEINZ NIXDORF
INSTITUT
Walkthrough-Problem
Echtzeit-Rendering
!"#$%&'#()(*+,-%&./&"
ptotische
Laufzeit.
gibt zwei Ansätze, dies zu erreichen:
012/&#(34%"*5"-*6/471%8#()(
Entlastung
der Es
Rendering-Pipeline
• Approximation (Level of Detail)
9:%#*0"')(;%*5"-*<%#'7#%1%
Ein weniger komplexes Modell wird erzeugt, das (fast) genauso gut aussieht wie das
= Approximation
- Level
Detail
ursprüngliche
Modell
(sieheofdazu
auch Kapitel 6).
>(%11%*%#"*:%"#2%&*?/471%8%'*@/-%11*-,&A*-,'*BC,'(D*2%",5'/*25(*,5''#%3(*
:#%*-,'*5&'7&E"21#F3%*@/-%11
• Sichtbarkeitsprüfung
(Visibility Culling)

Schicke
möglichst nur sichtbare
Polygone
zur Rendering Pipeline (siehe dazu auch Ka= Sichtbarkeitsprüfung
- Visibility
Culling
pitel>F3#F?%*4G21#F3'(*"5&*'#F3(.,&%*+/1H2/"%*;5&*I%"-%&#"2*+#7%1#"%
3).
077&/8#4,(#/"

2%/4%(&#'F3%'
JKL@/-%11

0":%"-5"2

I%"-%&%&
+#7%1#"%

<#1-

>#F3(.,&?%#('7&EC5"2
O/&1%'5"2*P012/&#(34%"*#"*-%&*Q/475(%&2&,C#?RA*>>*STTU

@,((3#,'*M#'F3%&

JN

Abbildung 1.2: Entlastung der Rendering Pipeline.

AlgoCG 09

3

2 Trees
Die in diesem Kapitel beschriebenen Datenstrukturen dienen zur effizienten Speicherung von
Punkten. Das Ziel ist es, basierend auf einem sichtbaren Ausschnitt die nicht-sichtbaren Objekte effizient berechnen zu können, um diese nicht zum Rendern an die Grafikkarte schicken
zu müssen.

2.1 kd-Bäume
kd-Bäume dienen zur Sortierung von Objekten bzw. Punkten im k-dimensionalen Raum. Sie
werden für (orthogonale) Bereichsanfragen, d.h. für die Berechnung aller Punkte, die sich
innerhalb eines Rechtecks oder Würfels befinden, eingesetzt. Eine weitere Anwendung sind
Verdeckungsberechnungen. Im Folgenden wird nur der 2D-Fall betrachtet.
Ein Punkt p = (px , py ) im 2-dimensionalen Raum liegt in einem Rechteck [x : x0 ] × [y : y 0 ]
genau dann, wenn px in [x : x0 ] und py in [y : y 0 ] liegt. Es sollen nun wie in Abbildung 2.1
dargestellt alle Punkte bestimmt werden, die im Rechteck liegen.

Abbildung 2.1: Orthogonale Bereichsanfrage: Punkte bestimmen, die im Rechteck liegen.

2.1.1 Konstruktion
Es wird ein Binärbaum aufgebaut, der als Blätter die Objekte bzw. Punkte enthält und als innere Knoten sogenannte Splitting-Geraden. Eine Splitting-Gerade teilt die Menge der Punkte
in zwei gleich große Teile, indem der Median der x-Koordinaten bzw. der y-Koordinaten berechnet wird. Dabei wird abwechselnd in x-Richtung und in y-Richtung unterteilt. Die ent-

4

Kapitel 2. Trees
stehenden Teilmengen werden über das linke bzw. rechte Kind des Baums gespeichert. Ein
Beispiel zeigt Abbildung 2.2.

Abbildung 2.2: Beispiel für einen kd-Baum.
Die Wurzel besitzt Tiefe 0, somit hat der Baum in Tiefe k immer 2k Knoten. Die SplittingGeraden verlaufen achsenparallel zur x- bzw. y-Achse. In einer geraden Baumtiefe wird immer vertikal unterteilt (bzgl. der x-Koordinate), in einer ungeraden Baumtiefe horizontal (bzgl.
der y-Koordinate). Abbildung 2.3 stellt die Unterteilung der Punktemenge dem aufgebauten
Binärbaum gegenüber.

Abbildung 2.3: Zweites Beispiel für einen kd-Baum.
Den Algorithmus zum Aufbau des kd-Baums zeigt Algorithmus 2. Der Algorithmus erhält
als Eingabe eine Menge von Punkten und gibt die Wurzel des kd-Baums als Ergebnis zurück.
Der Aufbau eines kd-Baumes mit n Punkten benötigt Platz O(n). Die Laufzeit eines Aufrufs wird von der Bestimmung der Splitting-Geraden dominiert. Dabei benötigt die Bestim-

AlgoCG 09

5

Kapitel 2. Trees
Algorithmus 2 Algorithmus zum Aufbau eines kd-Baumes
1: function B UILD KDT REE(Set of Points P , depth)
2:
if P enthält nur einen Punkt p then
3:
return Blattknoten, der p speichert
4:
else
5:
if depth gerade then
6:
Teile P mit vertikaler Linie I durch den Median bzgl. x-Koordinate in Mengen
P1 , P2
7:
else
8:
Teile P mit horizontaler Linie I durch den Median bzgl. y-Koordinate in
Mengen P1 , P2
9:
end if
10:
vlef t = BuildKDTree(P1 , depth + 1)
11:
vright = BuildKDTree(P2 , depth + 1)
12:
Erzeuge Knoten v mit linkem Nachfolger vlef t und rechtem Nachfolger vright und
Splittinggerade I
13:
end if
14:
return v
15: end function
mung des Medians Zeit O(n). Da diese Algorithmen kompliziert sind, wird in der Regel der
Punktemenge in zwei Liste (eine für x-Koordinate, eine für y-Koordinate) sortiert. Damit läuft
die Bestimmung des Medians in Zeit O(1), man benötigt aber Zeit O(n) für das Erzeugen der
Teillisten. Der Aufbau kann damit über folgende Rekurrenzgleichung beschrieben werden:

O(1)
,n = 1
T (n) =
n
O(n) + 2T (d 2 e) , n > 1
Da sich Eingabegröße in jedem Schritt halbiert, sind log(n)-Aufrufe notwendig, die jeweils
Laufzeit O(n) besitzen. Damit folgt insgesamt Laufzeit O(n log(n)). Da der Baum aber nur
einmal vor Beginn des Walkthroughs aufgebaut werden muss und dann während des gesamten
Walkthroughs benutzt werden kann, ist dies nicht schlimm. Allgemein benötigt die Konstruktion für k-Dimensionen und n Punkte Zeit O(n(k + log(n))).

2.1.2 Bereichsanfragen
Bereichsanfragen sollen zu einem achsenparallelen Rechteck alle Punkte zurückgeben, die in
dem Rechteck enthalten sind. Dazu wird geprüft, welche Regionen des kd-Baumes in dem
Rechteck enthalten sind oder sich mit diesem schneiden. Eine Region ist die Punktemenge,
die auf mindestens einer Seite durch eine Splittinggerade begrenzt ist. Für einen Knoten v des
Baums sind dies alle Splittinggeraden entlang des Pfads zur Wurzel. Eine Region kann damit
geschlossen (Rechteck) oder an mehreren Seiten offen sein. Abbildung 2.4 zeigt ein Beispiel.
Bei der Berechnung wird nun unterschieden zwischen Regionen, die vollständig im Rechteck enthalten sind, und Regionen, die von dem Rechteck geschnitten werden. Bei ersteren

AlgoCG 09

6

Kapitel 2. Trees

Abbildung 2.4: Regionen in einem kd-Baum.
werden alle Punkte ausgegeben, bei letzteren muss für jeden Punkt geprüft werden, ob er in
dem Rechteck enthalten ist. Abbildung 2.5 zeigt ein Beispiel.
Die türkis umrandete Region ist vollständig im roten Rechteck enthalten. Die im Baum
hellgrau hervorgehobenen Regionen werden durch das Rechteck geschnitten. In diesem Fall
ergibt die Einzelprüfung, dass die Punkte p6 und p11 im Rechteck enthalten sind, die Punkte
p3, p12 und p13 hingegen nicht. Das generelle Vorgehen beschreibt Algorithmus 3.
Die Funktion ReportSubTree(v) gibt den vollständigen Teilbaum mit Wurzel v aus. Die
Funktionen lc(v) bzw. rc(v) geben das linke bzw. rechte Kind des Knotens zurück. Die
Funktion p(v) liefert den Punkt, der in Knoten v gespeichert ist. Die Berechnung der Regionen
kann entweder in einem Preprocessing für alle Knoten durchgeführt werden oder „live“ bei der
Traversierung des Baums, indem die jeweilige Region mit dem Halbraum der Splittinggerade
des aktuellen Knotens ver-∩-det wird.
Um die Laufzeit der Bereichsanfrage zu bestimmen, müssen vorher output-sensitive Algorithmen definiert werden.
Definition 2.1.1 (Output-sensitiv)
Ein Algorithmus ist output-sensitiv, wenn seine Laufzeit von der Größe der Ausgabe abhängt.
Sei nun k die Anzahl aller Punkte im Rechteck [x : x0 ] × [y : y 0 ]. Eine lineare Suche
würde Zeit O(n) benötigen. Dies ist jedoch nicht notwendig. Die Ausgabe wird zum einen
durch die Aufrufe der ReportSubTree() Methode bestimmt und zum anderen durch die Anzahl
der SearchKDTree() Aufrufe für geschnittene Regionen. Die Summe aller ReportSubTree()
Aufrufe ist O(k), da maximal k Knoten ausgegeben werden.
Für die Bestimmung der Anzahl der rekursiven Aufrufe von SearchKDTree muss man wissen, wie viele Regionen das Rechteck schneidet. Das direkte Zählen ist durch die freie Platzierung nicht möglich, stattdessen zählt man, wie viele Regionen eine unendlich lange Gerade schneidet (stellvertretend für eine Seite des Rechtecks, muss für jede Seite einmal ausgeführt werden um den Gesamtaufwand zu erhalten.) Betrachtet man eine vertikale Gerade

AlgoCG 09

7

Kapitel 2. Trees

Abbildung 2.5: Auswertung von Regionen in einem kd-Baum.

Algorithmus 3 Algorithmus zur Durchführung von Bereichsanfragen auf einem kd-Baum
1: function S EARCH KDT REE(Node v, Range R)
2:
if v ist Blattknoten then
3:
wenn p(v) in R, gib p(v) aus
4:
else
5:
if region(lc(v)) vollständig in R then
6:
ReportSubTree(lc(v))
7:
else
8:
if region(lc(v)) schneidet R then
9:
SearchKDTree(lc(v), R)
10:
end if
11:
end if
12:
if region(rc(v)) vollständig in R then
13:
ReportSubTree(rc(v))
14:
else
15:
if region(rc(v)) schneidet R then
16:
SearchKDTree(rc(v), R)
17:
end if
18:
end if
19:
end if
20: end function

AlgoCG 09

8

Kapitel 2. Trees
und vertikale Splittinggeraden, so kann die Gerade immer nur einen der beiden Halbräume
der Splittinggeraden schneiden, aber nie beide (vgl. auch Abbildung 2.6)!
vertikale Gerade
vertikale Splittinggerade

Abbildung 2.6: Geschnittene Regionen bei vertikaler Gerade und vertikaler Splittinggerade.
Es beschreibt nun T (n) die Anzahl der geschnittenen Regionen eines kd-Baums, dessen
Wurzel eine vertikale Splittinggerade enthält. Da sich eine Rekursionsstufe tiefer eine horizontale Splittinggerade befindet, steigt man immer 2 Rekursionsstufen auf einmal ab, muss
dort aber beide gefundenen Knoten überprüfen wie in Abbildung 2.7 dargestellt. Jede dieser
Regionen enthält nach Konstruktion n4 Punkte.

Abbildung 2.7: Geschnittene Regionen im kd-Baum.
Damit ergibt sich insgesamt für die Anzahl der Aufrufe:

O(1)
,n = 1
T (n) =
2 + 2T (d n4 e) , n > 1
√
Dies ergibt O( n)√Aufrufe der SearchKDTree-Funktion und zusammen mit der Ausgabe
eine Laufzeit von O( n + k).

AlgoCG 09

9

Kapitel 2. Trees

2.1.3 Zusammenfassung der Eigenschaften
kd-Bäume sind Binärbäume, die über die Berechnung von Achsenparallelen Splitting-Geraden
gebildet werden. Die Teilmengen, in die die Objektmenge zerlegt wird, sind ungefähr gleich
groß (Teilung am Median der jeweiligen Schnittrichtung). In gerader Tiefe gibt es vertikale Splitting-Geraden (Unterteilung nach x-Koordinate), in ungerader Tiefe gibt es horizontale Splitting-Geraden (Unterteilung nach y-Koordinate).
Die Konstruktion benötigt Zeit
√
O(n log(n)), eine achsenparallele Bereichsanfrage O( n + k). Die Platzkomplexität beträgt
O(n).

2.2 BSP-Bäume
BSP-Bäume sind eine Form des Preprocessing, die es für statische Szenen erlaubt, den
Painter’s Algorithmus effizient und zur Laufzeit unabhängig vom Standpunkt anzuwenden.
Der Painter’s Algorithmus dient zum Hidden Surface Removal, zur Verdeckungsberechnung
(Occlusion-Culling, Kap. 3) und zur Darstellung transparenter Objekte HEINZ
bzw. NIXDORF
Schatten.
INSTITUT
!"#$!%&'
!"#$%&'#()(*+,-%&./&"
Das
Verfahren
ist
im
Vergleich
zu
anderen
Preprocessingverfahren
Zeitund
speicherinten012/&#(34%"*5"-*6/471%8#()(
!"##
siv. Dafür ist es effizient für statische Szenen und erlaubt das Display in linearer Zeit.
9#&*.%(&,:3(%"*;<+=;)54%*$/"*

2.2.1
Grundidee
> ?#"#%"*#4*@A=B,54
Es wird
eine Paritionierung der Dreiecke in einer Szene durchgeführt, die einer Tiefensortie> A&%#%:C%"*D+/1E2/"%"F*#4*GA=B,54
rung entspricht. Findet man nun eine Gerade oder Ebene, die eine Gruppierung von DreiGrundlegende Idee:
ecken (der Szene) aufteilt, dann weiß man automatisch, dass Elemente auf der gleichen Seite
H#%I%"'/&(#%&5"2*5"-*J&577#%&5"2
wie >dem
Betrachterstandpunkt nicht von Dreiecken auf der anderen Seite verdeckt werden
können.
Umgekehrt
jedoch schon. Dies stellt Abbildung 2.8 dar.
> ;%(&,:3(%*%#"%*<K%"%*,1'*J&577#%&5"2*$/"*?#"#%"LA&%#%:C%"

9%""*%#"%*Gerade/Ebene 2%I5"-%"*M%&-%"*C,""N*-#%*%#"%*J&577#%&5"2*,5I(%#1(*
Abbildung 2.8: Aufteilung einer Gruppierung von Dreiecken durch eine Splittinggerade.
-,""*2#1(O
?#"#%"LA&%#%:C%*,5I*-%&*21%#:3%"*<%#(%*M#%*-%4*;%(&,:3(%&'(,"-75"C(
Durch
die weitere Aufteilung der Gruppen erhält man einen Binärbaum dessen innere KnoM%&-%"*"#:3(*$%&-%:C(*$/"*?#"#%"LA&%#%:C%"*,5I*-%&*,"-%&%"*<%#(%*D542%C%3&(*X,F
ten Splittinggeraden (2D) bzw. -ebenen (3D) sind. Die Blätter entsprechen Regionen im
@R
P,((3#,'*Q#':3%&
S/&1%'5"2*T012/&#(34%"*#"*-%&*U/475(%&2&,I#CVN*<<*@WWR
Raum, die eine vollständige, disjunkte Aufteilung (Partionierung) der Ebene bzw. des Raums
darstellen. Jedes Blatt enthält ein Dreieck bzw. ein Fragment. Abbildung 2.9 zeigt ein Beispiel, in dem die Splittinggeraden durch die Geraden der Szene gelegt wurden, d.h. ein innerer
Knoten kodiert nicht nur die Region sondern speichert auf die Gerade. Alle übrigen Liniensegmente werden in den Blättern gespeichert. Man nennt diesen Vorgang auch Autopartition.
Es bezeichnet h- den linken und h+ den rechten Halbraum der Splittinggerade.

AlgoCG 09

10

F 1%2%"*@#&*G71#((#"22%&,-%"*-5&B3*H#"#%"%1%4%"(%:
1%2%" @#& G71#((#"22%&,-%" -5&B3 H#"#%"%1%4%"(%
F '7%#B3%&"*'#%*#"*#""%&%"*6"/(%":
F 5"-*'7%#B3%&"*&%'(1#B3%*H#"#%"%1%4%"(%*#"*E1)((%&"
5"- '7%#B3%&" &%'(1#B3% H#"#%"%1%4%"(% #" E1)((%&"

Kapitel 2. Trees

39
3;

39

3;

I,((3#,'*J#'B3%&

M/&1%'5"2*N012/&#(34%"*#"*-%&*O/475(%&2&,P#>Q:*GG*RSST

KL

Abbildung 2.9: Autopartition einer Menge von Geraden im 2D.
Es ist auch möglich, die Splittinggeraden unabhängig von den Objekten zu legen. Dieses
Verfahren ist jedoch komplizierter, da gute Geraden berechnet werden müssen, die eine kleine
Partitionierung erreichen ohne Dreiecke in Fragmente zu teilen.

2.2.2 Anwendungsbeispiel: Painter’s Algorithmus

Der Painter’s Algorithmus dient zum Zeichnen von Dreiecken. Der naive Algorithmus führt
eine Sortierung der Dreiecke nach ihrer Entfernung vom Betrachter durch (Tiefensortierung).
Anschließend zeichnet er (wie ein Maler) von hinten nach vorne das Bild. Es lassen sich
so jedoch keine zyklischen Überdeckungen auflösen. Diese bedingen, ein Dreieck in zwei
HEINZ NIXDORF INSTITUT
Fragmente zu teilen.
!"#$!%&'
!"#$%&'#()(*+,-%&./&"
zu traversieren und die Dreiecke so von
012/&#(34%"*5"-*6/471%8#()(
"#$"%&"'()$*(+*$,Die Lösung mit dem BSP besteht darin, den Baum
hinten nach vorne zu zeichnen. Der Vorteil gegenüber dem Painters Algorithmus besteht darin,
weiter Versuch dass
einerman
Lösung
nicht9+,#"(%&:'*012/&#(345';
für jeden Frame alle Dreiecke nach Tiefe sortieren muss. Hat man die Dreiecke
in den BSP einsortiert, weiß man für jeden Standpunkt, was vorne und was hinten ist.
=&,$%&'#%&% -%"einmal
=&,$%&'#%&%*-%"*>?+
>?+@>,54
>,54
Der Baum muss nur einmal im Preprocessing für die gesamte Szene aufgebaut werden.
A&%#%BC%*$/"*3#"(%"*",B3*$/&"%*D%#B3"%"
Es bezeichnet nun die Menge S(v) die Fragmente, die im Knoten des BSP-Baums gespeiE
EA&%#%BC%F*CG""%"*,5B3*H&,24%"(%*'%#"I*
2 zuvor ist Ivp der Standort des Betrachters, sowie T- der linke Teilbaum und T+
chert sind. Wie
-#%*$/4*>?+@>,54*2%(%#1(*J5&-%"
der rechte Teilbaum wie in Abbildung 2.10 dargestellt.

()*

=@

KL* H&,24%"(%I*-#%*#4*6"/(%"*-%'
>?+@>,54'*2%'7%#B3%&(*'#"-

+

KL ?(,"-/&(*-%'*>%(&,B3(%&'
KL*
?(,"-/&( -%' >%(&,B3(%&'

-.,$

KL 1#"C%&*.DJN*&%B3(%&*=%#1.,54

3@
3M

=M

$7

?9$;

Abbildung 2.10: Benennung der Elemente des BSP für den Painter’s Algorithmus.
R/&1%'5"2*S012/&#(34%"*#"*-%&*T/475(%&2&,U#CVI*??*WXXY

O,((3#,'*H#'B3%&

PQ

Der Painter’s Algorithmus ist in Algorithmus 4 aufgeführt.

AlgoCG 09

11

Kapitel 2. Trees

Algorithmus 4 Painter’s Algorithmus auf einem BSP-Baum
1: function PAINTERS(Tree T , ViewPoint vp)
2:
Sei v die Wurzel von T .
3:
if v ist Blattknoten then
4:
zeichne die Fragmente S(v) des Knotens v
5:
else
6:
if vp in h+ then
. 1. Fall
7:
Painters(T-, vp)
8:
Fragmente S(v) des Knotens v zeichnen
9:
Painters(T+, vp)
10:
else
11:
if vp in h- then
. 2. Fall, umgekehrt wie 1. Fall
12:
Painters(T+, vp)
13:
Fragmente S(v) des Knotens v zeichnen
14:
Painters(T-, vp)
15:
else
. 3. Fall
16:
Painters(T-, vp)
17:
Fragmente sind von dieser Seite unsichtbar.
18:
Painters(T+, vp)
19:
end if
20:
end if
21:
end if
22: end function

AlgoCG 09

12

Kapitel 2. Trees
Im ersten Fall liegt T- weiter hinten wie die Splittinggerade/-ebene. Da von hinten nach
vorne gezeichnet wird, wird somit zuerst T-, dann das Element im Knoten und zuletzt T+
gezeichnet. Im zweiten Fall liegt der Standort im T-, d.h. um von hinten nach vorne zu
zeichnen muss Fall 1 invertiert werden. Im 3. Fall ist der Standort weder im h+ noch im hder Splittinggerade, d.h. man befindet sich auf der Splittinggerade bzw. -ebene. Die Punkte
bzw. Dreiecke, die direkt auf der Splittinggerade/-ebene liegen sind somit nicht sichtbar.

2.2.3 Konstruktion - 2D
Im 2D Fall wird der BSP-Baum über eine Menge von Liniensegmenten aufgebaut. Eingabe
ist eine Menge von n Segmenten S = {s1 , . . . , sn }. Die Ausgabe ist ein BSP-Baum für S.
Als Splittinggerade wählen wir in jedem Schritt eine unendlich lange Gerade l(s) durch das
Segment s (Autopartition).
Das Vorgehen beschreibt Algorithmus 5.

Algorithmus 5 Aufbau eines BSP-Baums im 2D
1: function 2 D BSP(Segmente S)
2:
if |S| ≤ 1 then
3:
Erzeuge Baum T , der aus einem Blatt besteht, das S enthält.
HEINZ NIXDORF INSTITUT
4:
return T
!"#$%&'#()(*+,-%&./&"
5:
else
. Nehme erstes Segment s1
012/&#(34%"*5"-*6/471%8#()(
'+,-".,/*'
6:
Benutze l(s1 ) als Splittinggerade
7:
S + := {s ∩ l(s1 )+ |∀s ∈ S}; T + := 2dBSP(S + )
dBSP(S)
8:
S − := {s ∩ l(s1 )− |∀s ∈ S}; T − := 2dBSP(S − )
9:
Erzeuge BSP-Baum T mit Wurzel v, linkem Teilbaum T − und rechtem Teilbaum
2%*%#"%"*:,54*0;*-%&*,5'*%#"%4*:1,((*.%'(%3(;*-,'*1
%"(3)1(
+
T
.
0
10:
Speichere im Knoten v S(v) = {s ∈ S|s ⊂ l(s1 )}
%"5(9%"
%"5(9%"*23+
23+54 ,1'*=%&,-%*954*05>(%#1%"
,1'11:
=%&,-%
954
end if 05>(%#1%"?
12: end function

Abbildung 2.11 illustriert die einzelnen Variablen.
2%*%#"%"*:B+C:,54*0 4#(*6"/(%"*6

%" F%#1.,54 07
%"*F%#1.,54*0

3(%"*F%#1.,54*08

+

G3%&% #4 6"/(%" 6
G3%&%*#4*6"/(%"*6

3C
3H

0
23+4
3+4

M/&1%'5"2*N012/&#(34%"*#"*-%&*O/475(%&2&,>#EP;*BB*QRRS

AlgoCG 09

KL
I,((3#,'*J#'G3%&
Abbildung 2.11: Aufbau
eines 2D BSP-Baums.

13

Kapitel 2. Trees
2.2.3.1 Größe des BSP-Baums
Durch die Nutzung der Autopartition hängt die Größe des Baumes zum einen von der Reihenfolge der Segmentwahl ab und zum anderen von der Anzahl der aufgeteilten Segmente (je
weniger Segmente zerteilt werden, desto kleiner der Baum).
Definition 2.2.1 (Größe eines BSP-Baums)
Die Größe eines BSP-Baums bemisst sich in der Anzahl aller erzeugten Segmente.
Um einen möglichst kleinen Baum zu erzeugen, wäre eine Möglichkeit, in jedem Schritt
ein Segment zu wählen, dass möglichst wenige andere Segmente schneidet. Dieser Greedy
Ansatz kann große Bäume allerdings nicht verhindern und ist zudem rechenaufwändig. Man
wählt deshalb das Segment zufällig aus (zufällig kann gut sein, wenn die Auswahl schwer
fällt). Man kann nun die Eingabeliste S von Segmenten zuerst zufällig zu S 0 permutieren
und dann Algorithmus 5 unverändert auf der permutierten Liste ausführen. Alternativ kann
man den Algorithmus so verändern, dass in jedem Schritt ein zufälliges Element aus der Liste
genommen wird und nicht immer das erste.
Lemma 2.2.1
Die erwartete Anzahl von Fragmenten, die der Algorithmus 2dRandomBSP(S) berechnet, ist
O(n log n).

Beweis 2.2.1
Bei n Fragmenten gibt es n! viele Permutationen.
HEINZ NIXDORFWähle
INSTITUTsi beliebig aber fest. Analysiere
!%&'
!"#$%&'#()(*+,-%&./&"
nun die erwartete Anzahl von Segmenten, die
von si geschnitten werden, wenn l(si ) als Split012/&#(34%"*5"-*6/471%8#()(
"&"'(&)*'+,-".,/*'
tingsegment gewählt wird wie in Abbildung 2.12 dargestellt.
ein festes Segment !
+0

",1:'#%&%"*
",1:'#%&%"

#%*%&<,&(%(%*0"=,31*$/"*>%24%"(%"?*-#%*
%'@3"#((%"*<%&-%"?

<%""*12+/3 ,1'*>71#((#"2'%24%"(*2%<)31(*<#&-

A

Fragen:
+/

9#%*$#%1%*>%24%"(%*1#%2%"*D$/&E*+/

9,""*<#&-*%#"*>%24%"(*+0 ?*-,''*D$/&E*+/ 1#%2(?*
%'@3"#((%"A

12+/3

Abbildung 2.12: Anzahl zerteilter Segmente bei Wahl von si .
1. Wie viele Segmente liegen „vor“ si ?
Wir definieren zunächst die Distanz eines Segmentes sj zu einem Segment si :
K/&1%'5"2*L012/&#(34%"*#"*-%&*M/475(%&2&,N#OP?*>>*FQQR

G,((3#,'*H#'@3%&

IJ

dist(sj ) := Anzahl Segmente, die l(si ) zwischen si und sj schneiden.
Im Beispiel ist dist(sj ) = 2.

AlgoCG 09

14

Kapitel 2. Trees
2. Wann wird ein Segment sj , dass „vor“ si liegt, tatsächlich geschnitten?
Ein Segment s „schützt“ ein anderes Segment sj , wenn es vor dem Element si als Splittingsegment gewählt wurde. Das Segment sj wird dann nicht geschnitten. Abbildung
2.13 gibt ein Beispiel.

Abbildung 2.13: Ein Splittingsegment schützt ein anderes Segment.
In (a) wird s3 nicht von s2 geschützt, da beide zuvor durch s1 geteilt wurden. In (b) wird
s3 durch s1 geschützt, wenn s2 als Splittingsegment gewählt wird.
3. Wie hoch ist die Wahrscheinlichkeit, dass l(si ) das Segment sj schneidet, wenn si als
Splittingelement gewählt wird?
Es wird nur dann geschnitten, wenn kein Element sk , das sj schützen würde, vorher
gewählt wird. Sei nun k := dist(sj ) und seien sj1 , sj2 , . . . , sjk die Segmente zwischen si
und sj . si muss nun als erstes gewählt werden, da sj sonst geschützt würde. Somit hat
es den kleinsten Index in S. Für die Wahrscheinlichkeit folgt damit:
P r(„l(si ) schneidet sj “) ≤

1
dist(sj ) + 2

dist(sj ) ist die Anzahl der Elemente zwischen si und sj , die 2 sind si und sj selbst.
Wenn keine Elemente zwischen si und sj liegen, beträgt die Wahrscheinlichkeit 21 , da si
nur dann schneidet, wenn es vor sj liegt. Mit jedem Element dazwischen verringert sich
die Wahrscheinlichkeit, dass sj geteilt wird, da die Wahrscheinlichkeit, dass sj geschützt
wird, immer größer wird.
Für ein Segment s ergibt sich die erwartete Anzahl von Schnitten, die s erzeugt, wie
folgt:
P
1
E(„Anzahl der Schnitte erzeugt durch s“) ≤
s0 6=s dists (s0 )+2
P
n−2 1
≤ 2 i=0
i+2
≤ 2 ln n
Es wird die Summe über die Wahrscheinlichkeit eines Schnitts für alle Segmente s0 berechnet. Je nachdem welche Position si in der Permutation einnimmt variiert die Anzahl der möglichen Schnitte, die si vornehmen kann, zwischen 0 und n − 2. Man kann
also auch über alle möglichen Distanzen aufsummieren, da jede mögliche Distanz für
jede Richtung höchstens einmal auftauchen kann. Dabei summiert man in beide Richtungen auf, d.h. links und rechts des betrachteten Segments. Dies ist möglich, da hier

AlgoCG 09

15

Kapitel 2. Trees
nur eine Abschätzung nach oben betrachtet wird. Die entstehende Summe ist eine harmonische Reihe, die nach oben näherungsweise mit ln(n) plus einer kleinen Konstanten
abgeschätzt werden kann.
Die Anzahl der Schnitte für n Elemente fügt zu diesem Wert noch einen Faktor n hinzu,
so dass die gesamte Anzahl von möglichen Schnitten 2n ln(n) beträgt. Zusammen mit
den n als Eingabe gegebenen Segmenten ergibt sich eine erwartete Größe von n +
2n ln(n) = O(n log n) Segmenten für den BSP-Baum.
Es ist wichtig zu beachten, dass es sich hierbei nur um einen Erwartungswert handelt, der
über die Wahrscheinlichkeit eines Schnitts gebildet wird. Es kann somit auch BSP Bäume
geben, in denen eine höhere Anzahl von Segmentierungen passiert.
2.2.3.2 Laufzeit des Konstruktionsalgorithmus
Die Laufzeit für die Konstruktion des BSP-Baums hängt von seiner Größe ab. Die Aufteilung
in S + und S − kostet Zeit O(n), da nie mehr als n Fragemente bei der Aufteilung entstehen
können Die Anzahl der rekursiven Aufrufe ist gleich der Anzahl
der erzeugten Fragmente.
HEINZ NIXDORF INSTITUT
!"#$!%&'
!"#$%&'#()(*+,-%&./&"
Somit ergibt sich zusammen mit der zuvor berechneten erwarteten
Größe des BSP-Baums die
012/&#(34%"*5"-*6/471%8#()(
!"#$!%&'()'(*+(,%&' 2
erwartete Laufzeit O(n log n).
9#%*.%&%:3"%"*;#&*%#"%"*<=+><,54*?@&*A&%#%:B%*C+/1D2/"%E*F

2.2.4 Konstruktion - 3D
Die
besteht hier aus Polygonen (Dreiecken). Für ein Dreieck t beschreibt nun h(t)
=%#*-Eingabe
%#"*A&%#%:BG
./-0Ebene
HI*#'(*-#%*J.%"%G*#"*-%&*-,'*A&%#%:B*die
in der das Dreieck liegt wie in1#%2(
Abbildung 2.14 dargestellt.
3K
-

3>

./-0

L-%%H

Abbildung 2.14: Polygone als Splittingebenen im 3D.

M ;#&*"%34%"*",:3%#","-%&*-#%*A&%#%:B%*N54*05?(%#1%"*-%'*OA>P,54%'

MAnalog
Q%-%'*A&%#%:B*-%?#"#%&(*%#"%*=71#((#"2%.%"%*-%'*<=+><,54'
zu den Geraden im 2D werden nun die Ebenen der Polygone zur Aufteilung des
Raums
verwendet. Jedes Dreieck definiert eine Splittingebene,5"-*.1
die den Raum in zwei HalbM -#%*=71#((#"2%.%"%*(%#1(*-%"*<=+><,54*#"*N;%#*\,1.&)54%*.$

räume h+ und h− aufteilt. Der Algorithmus ist damit sehr ähnlich zum 2D Fall wie AlgorithTU
R,((3#,'*S#':3%&
mus 6 zeigt.
Für den Aufbau kann dieselbe Autopartionsvorschrift kombiniert mit Randomisierung verwendet werden, wie im 2D. Die Analyse der Größe eines 3D BSP-Baums ist bislang unbekannt. Für die weiteren Betrachtungen definieren wir zunächst Free-Splits.
V/&1%'5"2*W012/&#(34%"*#"*-%&*X/475(%&2&,?#BYG*==*ZUU[

Definition 2.2.2 (Free-Split)
Ein Dreieck (Liniensegment), das eine Zelle (Region) in zwei nicht zusammenhängende Teile
aufteilt ist ein Free-Split.

AlgoCG 09

16

Kapitel 2. Trees
Algorithmus 6 Aufbau eines BSP-Baums im 3D
1: function 3 D BSP(Segmente S)
2:
if |S| ≤ 1 then
3:
Erzeuge Baum T , der aus einem Blatt besteht, das S enthält.
4:
return T
5:
else
. Nehme erstes Dreieck t1
6:
Benutze h(t1 ) als Splittingebene
7:
S + := {t ∩ h(t1 )+ |∀t ∈ S}; T + := 3dBSP(S + )
8:
S − := {t ∩ h(t1 )− |∀t ∈ S}; T − := 3dBSP(S − )
−NIXDORF INSTITUT
!"#$!%&'
9:
Erzeuge BSP-Baum T mit Wurzel v, linkem TeilbaumHEINZ
T !"#$%&'#()(*+,-%&./&"
und rechtem Teilbaum
+
012/&#(34%"*5"-*6/471%8#()(
T !"#$!%&'()'(*+(,%&'
.
10:
Speichere im Knoten v S(v) = {t ∈ S|t ⊂ h(t1 )}
Definition:
11:
end if -.//$"01)2
12: end function
9#"*:&%#%;<*=>#"#%"'%24%"(?@*-,'*%#"%*A%11%*=B%2#/"?*#"*CD%#*
"#;3(*C5',44%"3)"2%"-%*E%#1%*,5F(%#1(

Abbildung 2.15 zeigt ein Beispiel für 2D und 3D. Ein Free-Split schneidet die Begrenzung
der Region auf allen Seiten. [TODO:Wieso ist das nicht zusammenhängend?]

F
F&%%*'71#((
1#((

K/&1%'5"2*L012/&#(34%"*#"*-%&*M/475(%&2&,F#<N@*OO*PQQR

G,((3#,'*H#';3%&

IJ

Abbildung 2.15: Beispiele für Free-Splits.

Eine Erweiterung des Algorithmus besteht nun darin, dass man immer einen Free-Split
durchführt, wenn dies möglich ist, und ansonsten ein zufälliges Dreieck als Splittingebene
auswählt. Ein weiterer Unterschied ist, dass alle möglichen (sinnvollen) Teilungen ausgeführt
werden, d.h. h(ti ) wird zum Schnitt aller Zellen verwendet, die es schneiden kann. Bislang
wurde immer nur eine Zelle geschnitten. [TODO:Das ist jetzt wirklich nicht mehr zusammenhängend, aber nicht spezifisch für den Free-Split, oder?]
Dieses Vorgehen kann jetzt nicht mehr rekursiv formuliert werden. Algorithmus 7 fasst das
iterative Vorgehen zusammen.
Die Unterschiede in der Arbeitsweise zeigt Abbildung 2.16.
Es lässt sich nun zeigen, dass für den angegebenen Algorithmus unter Verwendung aller
möglichen Free-Splits die erwartete Anzahl von Fragmenten O(n2 ) ist. Eine Analyse ohne
Free-Splits ist unbekannt. Das folgende Lemma zeigt, dass diese Grenze hart ist.

AlgoCG 09

17

Kapitel 2. Trees
Algorithmus 7 Iterativer Aufbau eines BSP-Baums im 3D mit Free-Splits
1: function 3 D R ANDOM F REE S PLIT BSP(Segmente S)
2:
Erzeuge zufällige Permutation S 0 = t1 , . . . , tn
3:
for i := 1 to n do
4:
Verwende h(ti ) zur Teilung aller Zellen, die h(ti ) schneiden (nur sinnvolle Teilungen)
HEINZ NIXDORF INSTITUT
!"#$!%&'
5:
Verwende alle möglichen Free-Splits
!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(
6:
end!"#$!%&'()'(*+(,%&'
for
7: end function
!"(%&'93#%-1#93%*0&.%#(':%#'%;
&%<5&'#$%& 012/&#(345'
&%<5&'#$%&*012/&#(345'

#(%&,(#$%& 012/&#(345'
#(%&,(#$%&*012/&#(345'
-/

-.

-*

-.

-/

-*

Abbildung 2.16: Unterschiede in der Arbeitsweise zwischen rekursivem und iterativem
Algorithmus.
=,"*<,""*>%#2%";

K#%*%&:,&(%(%*0">,31*$/"*?&,24%"(%"*#'(*DL&*-%"*&,"-/4#'#%&(%"*012/&#(345'*
Lemma 2.2.2
3dRandomFreeSplitBSP(S) 4#(*?&%%MG71#(*012/3
Es gibt Mengen von n sich nicht überschneidenden Dreiecken im 3D-Raum,
für die jede
Auto@@
=,((3#,'*?#'93%&
2
matische Aufteilung (Autopartition) Ω(n ) Fragmente hat.
A/&1%'5"2*B012/&#(34%"*#"*-%&*C/475(%&2&,D#<EF*GG*HIIJ

Beweis 2.2.2
Wir ordnen eine Menge R1 von n1 Rechtecken parallel zur xy-Ebene und eine Menge R2 von
n2 Rechtecken parallel zur yz-Ebene an (für Dreiecke ebenso möglich) wie in Abbildung 2.17
dargestellt.
Sei nun G(n1 , n2 ) die minimale Größe einer automatischen Aufteilung. Der Beweis erfolgt
durch Induktion über n1 + n2 .
Behauptung: G(n1 , n2 ) = (n1 + 1)(n2 + 1) − 1
Anfang: G(1, 0) = 1, G(0, 1) = 1
Schritt: n1 + n2 > 1
O.B.d.A. wählt die automatische Aufteilung ein Rechteck r aus R1 als Splittingebene.
Dies teilt alle Rechtecke aus R2 . Die entstehenden Teilszenen sehen alle so aus, wie
die Ausgangssituation. Sei nun m die Anzahl der Dreiecke von R1 , die oberhalb von r
liegen. Dann gilt:
G(n1 , n2 ) = 1 + G(m, n2 ) + G(n1 − m − 1, n2 )
= 1 + ((m + 1)(n2 + 1) − 1) + ((n1 − m)(n2 + 1) − 1)
= (n1 + 1)(n2 + 1) − 1

AlgoCG 09

18

Kapitel 2. Trees

Abbildung 2.17: Nachweis einer unteren Schranke für die Anzahl von Fragmenten.
Man kann aber auch zeigen, dass für jede Menge von n sich nicht überschneidenden Dreiecken ein BSP der Größe O(n2 ) existiert.

2.3 Quadtrees und Octrees

Quadtrees und Octrees sind Datenstrukturen, um eine räumliche Sortierung und Bereichsanfragen durchzuführen. Sie werden z.B. bei der Finite Elemente Methode, bei der Berechnung
von Meshes und bei der Verdeckungsberechnung eingesetzt.
Quadtrees werden im 2D eingesetzt. Jeder Knoten entspricht einem Quadrat. Ein innerer
Knoten hat vier Kinder, die einer Aufteilung HEINZ
des Quadrats
vier gleichgroße Quadrate entNIXDORFin
INSTITUT
+%&''(
!"#$%&'#()(*+,-%&./&"
sprechen. Die Quadrate sind entsprechend der Himmelsrichtungen mit NW, NE, SW, SE be012/&#(34%"*5"-*6/471%8#()(
"-.%/'-0'- zeichnet. Alle Quadrate auf einer Ebene des Baums
sind gleich groß. Abbildung 2.18 zeigt
ein Beispiel.
;=

/",1

;<

(%"*@/&&%'7/"-#%&(*4#(*
,-&,(

/(%"*3,.%"*$#%&*6#"-%&

,(%*#"*-%&'%1.%"*<.%"%*
*2&/C
C

D=

D<

Abbildung 2.18: Aufbau eines Quadtrees.

Octrees sind eine analoge Datenstruktur im 3D Raum. Dabei wird ein Würfel in acht gleich
große Würfel unterteilt, so dass jeder Knoten 8 Kinder besitzt. Alle Würfel auf einer Ebene
des Baums sind gleich groß. Abbildung 2.19 zeigt ein Beispiel.
/",1
Die Unterteilung kann so lange fortgesetzt werden, bis entweder eine maximale Tiefe erreicht
(%"
(%"*@/&&%'7/"-#%&(*4#(*
@/&&%'7/"-#%&( wurde
4#( oder bis in einer Box maximal c Elemente enthalten sind. Die Elemente selbst

&H%1

/(%"*3,.%"*,E3(*6#"-%&
AlgoCG 09

19

1*#"*-%&'%1.%"*<.%"%*'#"-*
C

M/&1%'5"2*N012/&#(34%"*#"*-%&*O/475(%&2&,H#@PQ*DD*:RRS

I,((3#,'*J#'E3%&

KL

,-&,(%*#"*-%&'%1.%"*<.%"%*
%#E3*2&/C
# 3
C

D=

Kapitel 2. Trees

"'#/",1

6"/(%"
6"/(%"*@/&&%'7/"-#%&(*4#(*
@/&&%'7/"-#%&( 4#(
=G&H%1

6"/(%"*3,.%"*,E3(*6#"-%&

G&H%1*#"*-%&'%1.%"*<.%"%*'#"-*
2&/C
M/&1%'5"2*N012/&#(34%"*#"*-%&*O/475(%&2&,H#@PQ*DD*:RRS

Abbildung 2.19: Aufbau
eines Octrees.
I,((3#,'*J#'E3%&

KL

werden in den Blättern gespeichert, bei Speicherung von Dreiecken je nach Implementierung
auch in inneren Knoten. Die Elemente sind damit in der Box, in der sie enthalten sind, gespeichert.
!"#$%&''()*+%&''(

!"#$%&#'()*+,-)+.'#$#%/#)

HEINZ NIXDORF INSTITUT
!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

2.3.1 Speichern von Elementen
Praktikable Lösungsansätze

Die Eingabe ist eine Menge von Punkten bzw. Dreiecken. Im Fall von Punkten wird jeder
9 +/1:2/"*,5;(%#1%"
+/1:2/" ,5;(%#1%"
Punkt in genau einem
Quadrat gespeichert, das ein Blatt des Quadtrees ist. Jedes Blatt enthält
!*+/1:2/","<,31*%&3=3(*'#>3
maximal k Punkte. Durch die exakte Aufteilung enthalten innere Knoten nur die geometri9 +/1:2/"*&%-5"-,"(*'7%#>3%&"
schen Informationen
des Quadrats, aber keine Punkte.
!*?%&@,1(5"2',5;@,"-A*-,*"5&*B8*<%#>3"%"*'#""$/11
Das Speichern von Polygonen (Dreiecken) führt häufig dazu, dass Dreiecke die Begren9 +/1:2/"*#"*-%4*6"/(%"*'7%#>3%&"A*;C&*-%"*'#%*"/>3*"#>3(*5"(%&(%#1(*@%&-%"*
zungslinien bzw. 4C''%"
-flächen schneiden. Es gibt drei Möglichkeiten, damit umzugehen, die in
Abbildung 2.20 dargestellt
sind.
!*?#%1%*+/1:2/"%*1#%2%"*3=3%&*#4*D,54A*,1'*%'*#3&%&*E&=F%*%"('7&#>3(

G,((3#,'*H#'>3%&
Abbildung 2.20: Speicherung von Dreiecken in einem Quadtree.
?/&1%'5"2*K012/&#(34%"*#"*-%&*L/475(%&2&,;#MNA*OO*PQQR

IJ

Die erste Variante besteht darin, dass Polygon entlang der Begrenzungslinien in mehrere
Polygone aufzuteilen. Dadurch erhöht sich allerdings die Anzahl der Polygone. Die zweite
Möglichkeit ist, dass Dreieck in jedem Quadrat zu speichern, in dem es enthalten ist. Diese
Redundanz führt jedoch zu zusätzlichem Aufwand beim Zeichnen, da das Dreieck obwohl
mehrfach gespeichert nur einmal gezeichnet werden soll. Die dritte Möglichkeit besteht darin,
das Polygon in einem Knoten zu speichern, für den es nicht unterteilt werden muss. Damit
können auch innere Knoten Dreiecke enthalten. Es passiert so jedoch häufig, dass Dreiecke
weiter oben im Baum liegen, als dies ihrer Größe entspricht. Eine weitere Möglichkeit sind
die in Abschnitt 2.4 beschriebenen Loose Octrees, bei denen die Ebene nur von der Größe

AlgoCG 09

20

Kapitel 2. Trees
des Elements abhängt. Hier entscheidet der Mittelpunkt des Polygons darüber, in welchem
Knoten ein Objekt liegt.
Quadtrees und Octrees sind insbesondere für dynamische Daten geeignet. Durch die dynamische Unterteilung der Quadrate/Würfel können Polygone beliebig ungünstig positioniert
sein, da die Struktur nur bedingt von der Dichte der Objekte abhängig ist.

2.3.2 Aufbau
Der Aufbau eines Quadtrees beginnt mit einem Quadrat, das alle Punkte enthält (BoundingBox von allen Punkten). Dieses Quadrat wird dann in vier gleich große Teile zerteilt und die
Punkte werden aufgeteilt. Punkte, die auf der Trennlinie liegen, werden im dem linken bzw.
unteren Quadrat zugeordnet. Man unterteilt solange, bis maximal k Punkte enthalten sind oder
eine maximale Tiefe erreicht wurde. Algorithmus 8 stellt die Konstruktion für k = 1 dar. Der
Wert für k ist für die Laufzeit entscheidend und liegt deshalb in praktischen Anwendungen in
der Regel über 1.
Algorithmus 8 Aufbau eines Quadtrees
1: function BUILD Q UADTREE(Punkte P )
2:
σ := [xσ : x0σ ] × [yσ : yσ0 ] ist das oberste Quadrat für Punktemenge P
3:
if |P | ≤ 1 then
4:
Erstelle einen Knoten, der σ und P speichert und gibt diesen zurück.
5:
else
. |P | > 1
6:
Es sind σN E , σN W , σ0SE und σSW die vier0 Quadranten von σ.
σ)
σ)
7:
Es gilt xmid := (xσ +x
und ymid := (yσ +y
2
2
8:
PN E := {p ∈ P |px > xmid ∧ py > ymid }
. Berechnung der Punktemengen
9:
PN W := {p ∈ P |px ≤ xmid ∧ py > ymid }
10:
PSE := {p ∈ P |px > xmid ∧ py ≤ ymid }
11:
PSW := {p ∈ P |px ≤ xmid ∧ py ≤ ymid }
12:
Erstelle Knoten v, in dem σ gespeichert ist, die Kinder des Knotens sind PN E ,
PN W , PSE und PSW .
13:
end if
14: end function

2.3.2.1 Tiefe des Quadtrees
Die Größe und Tiefe eines Quadtrees ist nicht über die Anzahl der Punkte beschränkt, da
immer nur in Einheiten fester Größe aufgeteilt wird. Die Tiefe entspricht der Anzahl der
Aufteilungsschritte. Diese ist wiederum abhängig von der Größe s des äußersten Quadrats
und vom geringsten Abstand c zwischen zwei benachbarten Punkten.
Lemma 2.3.1
Die Tiefe eines Quadtrees für eine Punktemenge P in der Ebene ist höchstens log( sc ) + 32 .

AlgoCG 09

21

Kapitel 2. Trees
Beweis 2.3.1
Die Tiefe eines Quadrates in Tiefe i ist 2si wie in Abbildung 2.21 dargestellt. Die maximale mögliche Entfernung zweier Punkte
√ in einem Quadrat dieser Seitenlänge ist entlang
der Hauptdiagonalen und beträgt somit 2 · 2si .

Abbildung 2.21: Größe von Qudraten in Ebene i in einem Quadtree.
Jedes innere Quadrat umfasst mindestens zwei Punkte, die mindestens c voneinander entfernt sind. Für jedes Quadrat auf Tiefe i gilt damit:
√ s
s
1
2 · i ≥ c ⇒ i ≤ log( ) +
2
c
2
Da die Tiefe des Baums aufgrund der Blätter noch um eins Tiefer ist als die maximale Tiefe
eines inneren Knotens, ergibt sich die Schranke.
2.3.2.2 Größe eines Quadtrees
Die Größe des Quadtree ist abhängig von der Tiefe. Durch eine ungeschickte Anordnung von
Punkten kann der Quadtree sehr unbalanciert sein.
Lemma 2.3.2
Ein Quadtree mit n Punkten und Tiefe d hat
1. O((d + 1)n) Knoten und kann in
2. Zeit O((d + 1)n) aufgebaut werden.
Beweis 2.3.2
1. Jeder innere Knoten hat vier Kinder. Damit erhält man die Anzahl der Blätter als 3 ×
Anzahl innerer Knoten + 11 . Jeder innere Knoten umfasst mindestens einen Punkt (in
seinem Quadrat). Die Knoten auf einer Ebene sind aber alle disjunkt und überdecken
alle Knoten. Daraus folgt direkt, dass die Anzahl der inneren Knoten auf einer Ebene
nicht größer als O(n) sein kann. Da dies für alle Ebenen gilt, folgt dass der Baum
O((d + 1)n) Knoten besitzt.
2. In jedem inneren Knoten werden die Punkte auf die vier Kinder verteilt. Dies benötigt
lineare Zeit in Abhängigkeit von der Anzahl der Punkte in jedem Quadrat. Damit kostet
der Aufbau O((d + 1)n) für alle Level.
1

Für einen Binärbaum mit Tiefe d erhält man entsprechend 2d Blätter und 1 × 2d − 1 innere Knoten.

AlgoCG 09

22

%&''(

-%%

dtree

Kapitel 2. Trees

2.3.3 Suche im Quadtree

HEINZ NIXDORF INSTITUT
!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

Gegeben ist ein Knoten v des Quadtrees und gesucht wird sein nördlicher Nachbar
N ordN achbar(v, T ). Die Idee, diesen zu finden, besteht darin, bis zu einem gemeinsamen
Vorgänger von v und N ordN achbar(v, T ) im Baum hochzugehen. Dieses Vorgehen ist in
Abbildung 2.22 dargestellt. Die farbige Umrandung kennzeichnet jeweils den gemeinsamen
Vorfahren. Die Pfeile kennzeichnen den Knoten bzw. den Nachbarn, die auch einheitlich
farblich gekennzeichnet sind.

"
"*6"/(%"*.
6"/(%" . #4*:5,-(&%%*5"-*
#4 :5,-(&%% 5""=&-1#;3%">*?,;3.,&"*
23

/ +/ $0 1 23
/4-+/*#$0*-1.523

&%%*3/;3*.#'*B5*%#"%4*6"/(%"C*-%&*
3 3 .#
#
6 (
/&A,3&%*$/"*. 5"-*
23 #'(
6"/(%"*.

E,((3#,'*F#';3%&

D/&1%'5"2*H012/&#(34%"*#"*-%&*I/475(%&2&,A#JKC*LL*MNNO

GG

Abbildung 2.22: Nordnachbar eines Knotens v.
Der Algorithmus zur Berechnung des N ordN achbar(v, T ) ist in Algorithmus 9 angegeben.
Die verwendeten Variablen sind in Abbildung 2.23 illustriert.
Satz 2.3.1
Der Nachbar eines Knotens v im Quadtree der Tiefe d wird in Zeit O(d + 1) gefunden.
Man läuft solange in der Hierarchie hoch, bis man einen gemeinsamen Vorfahren gefunden
hat. Dabei kann man maximal bis zur Wurzel hochlaufen und auf der Wurzel nochmal rekursiv
aufrufen. Bei einer maximalen Tiefe d ergibt sich somit die Laufzeit.

2.3.4 Balancierte Quadtrees
Eine ungünstige Anordnung der Punkte kann dazu führen, dass in einem Quadtree ein großes
Quadrat sehr viele kleine Nachbarn besitzt, wie dies in Abbildung 2.24 dargestellt ist.
Definition 2.3.1 (Balancierter Quadtree)
Ein Quadtree ist balanciert, wenn sich zwei benachbarte Quadrate in der Seitenlänge höchstens um einen Faktor zwei unterscheiden.

AlgoCG 09

23

&''(

%%

Kapitel 2. Trees

Algorithmus 9 Berechnung der nördlichen Nachbarn eines Knotens
1: function N ORD NACHBAR(Knoten v, Quadtree T )
2:
if v = root(T ) then
3:
return nil
4:
end if
5:
if v = SW-Kind von Eltern(v) then
6:
return NW-Kind von Eltern(v)
7:
end if
8:
if v = SE-Kind von Eltern(v) then
9:
return NE-Kind von Eltern(v)
10:
end if
11:
µ = NordNachbar(Eltern(v, T ))
12:
if µ = nil oder µ ist Blatt then
13:
return µ
14:
else
15:
if v = NW-Kind von Eltern(v) then
16:
return SW-Kind von µ
17:
else
18:
return SE-Kind von µ
19:
end if
20:
end if
HEINZ NIXDORF INSTITUT
21: end function
!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

/(%"*. #"*%#"%4*:5,-(&%%*/

%&*6"/(%"*.0 -%''%"*;#%<%*3=>3'(%"'*'/*(#%<*
*'/-,''*!1.02 A/&-A,>3.,&*$/"*!1.2 #'(D*E,11'*
2#.(C*2#.*"#1*,5'

? @*A/&-A,>3.,&
$/"*34,%-51.2

,#+./#&01234

%"*&%(5&"*"#1

$/"*34,%-51.2 (3%"*&%(5&"*AKL6#"-*$/"*34,%-51.2
!1.2

$/"*34,%-51.2 (3%"*&%(5&"*A9L6#"-*$/"*34,%-51.2

$9*-134,%-51.2 /2
$9*-134,%-51.2:&/2

'(*%#"*Q1,((*
"*?
AKL6#"-*$/"*34,%-51.2
AK 6#"- $/" 34,%-51.2

"*&%(5&"*JKL6#"-*$/"*?
*&%(5&"*J9L6#"-*$/"*?

!;<='5+

34,%-51.2

!3<='5+

Abbildung 2.23: Suche des Nordnachbarn zu einem Knoten v.
"/(%"'*. #4*:5,-(&%%*-%&*;#%<%*+ B#&-*#"*[%#(*>1+?@2 2%<5"-%"

1%'5"2*V012/&#(34%"*#"*-%&*W/475(%&2&,<#FXC*JJ*IYYZ

AlgoCG 09

R,((3#,'*E#'>3%&

ST

24

9 B,'*$%&'(%3%"*C#&*5"(%&*%#"%&*D,1,"A%E
9 B#%*C#&-*%#"%*D,1,"A%*=/"'(&5#%&(E*

Kapitel 2. Trees

3,(*$#%1%*=1%#"%*@,A3.,&"

!"#$%&''()*+%&''(
!"#"$%&'()$*

HEINZ NIXDORF INSTITUT
!"#$%&'#()(*+,-%&./&"

Abbildung 2.24: Unbalancierter Quadtree. 012/&#(34%"*5"-*6/471%8#()(

Definition

J/&1%'5"2*K012/&#(34%"*#"*-%&*L/475(%&2&,M#=NO*??*PQQI
Das bedeutet,
die Nachbarn
eines Quadrates sind höchstens eine Ebene im BaumF,((3#,'*G#'A3%&
höher oder
9#" :5,-(&%% #'( +"#"$%&'(, ;%"" '#<3 =;%# .%",<3.,&(% :5,-&,(%
9#"*:5,-(&%%*#'(*+"#"$%&'(,>*;%""*'#<3*=;%#*.%",<3.,&(%*:5,-&,(%*
tiefer. Abbildung
2.25
zeigt
ein
Beispiel.
#"*-%&*?%#(%"1)"2%*3@<3'(%"'*54*%#"%"*A,B(/&*=;%#*5"(%&'<3%#-%"C

G/&1%'5"2*H012/&#(34%"*#"*-%&*I/475(%&2&,J#BK>*??*LFFM

D,((3#,'*A#'<3%&

EF

Abbildung 2.25: Balancierter Quadtree.
Das Vorgehen zum Aufbau eines balancierten Quadtrees besteht darin, zunächst einen unbalancierten Quadtree aufzubauen und dann alle unbalancierten Blätter solange aufzuteilen,
bis der Baum balanciert ist. Die Details zeigt Algorithmus 10.
Die Aufteilung eines Knotens kann dazu führen, dass jetzt auch ein Nachbarn aufgeteilt
werden muss, obwohl dies vor der Aufteilung nicht notwendig gewesen wäre. Zur Überprüfung, ob ein Knoten aufgeteilt werden muss, kann man den Algorithmus N ordN achbar(v, T )
benutzen.
Ein Knoten v hat einen unbalancierten Nordnachbarn, wenn der Nordnachbar von v ein SWoder SE-Kind hat, dass kein Blatt ist. Diese Situation ist in Abbildung 2.26(a) dargestellt.
Nach dem Aufteilen eines Knotens v muss der Nordnachbar von σ(v) dann aufgeteilt werden, wenn der Nordnachbar vor dem Split schon größer ist als σ(v). In diesem Fall liegen
nach dem Split zwei Baumebenen zwischen den Knoten. Dies zeigt Abbildung 2.26(b)
Satz 2.3.2
Sei T ein Quadtree mit m Knoten. Die balancierte Version T ∗ von T hat O(m) Knoten.

AlgoCG 09

25

HI

Kapitel 2. Trees

Algorithmus 10 Balancieren eines Quadtrees
1: function BALANCE Q UADTREE(Knoten v, Quadtree T )
2:
Füge alle Blätter in eine lineare Liste L.
3:
while L ist nicht leer do
4:
Entferne ein Blatt v aus L HEINZ NIXDORF INSTITUT
!"#$%&'#()(*+,-%&./&"
5:
if σ(v) muss aufgeteilt werden then
012/&#(34%"*5"-*6/471%8#()(
6:
Ersetze Blatt v als internen Knoten mit vier Kindern
7:
Falls v einen Punkt enthält, füge ihn in das entsprechende Blatt ein
8:
alle vier Kinder von v in L ein.
att aufgeteilt
werdenFüge
muss?
9:
Prüfe ob σ(v) jetzt Nachbarn enthält, die aufzuteilen sind und füge diese in L
ein.
&#(345'
&#(345'*:5&*;,<3.,&'5<3%*
:5& ;,<3.,&'5<3%
10:
end if
11:
end while
12: end function

-",<3.,&"*:5*%#"%4*6"/(%"*1>*9%""*
"*?@A /-%&*?=A6#"-*3,(>*-,''*B%#"*

!014

HEINZ NIXDORF INSTITUT
!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

rden muss?
einem Split
p von , die Nachbarn von
.,&'5<3%
.,&'5<3%*
üssen?

&#(345'*:5&*;,<3.,&'5<3%*
%4*6"/(%"*1>*9%""*
"-*3,(>*-,''*B%#"*
(%"*;/&-",<3.,&"*:5*%#"%4*6"/(%"*1>*
!014
&DE%&*#'(*,1'*!014
(a)

*#"*-%&*L/475(%&2&,M#BN>*??*OPPQ

, die Nachbarn
von
Abbildung
2.26: Unbalancierte

!014
0 4
(b)
F,((3#,'*G#'<3%&

HI

Quadtree Situationen. In (a) ist die Ausgangssituation unbalanciert, in (b) entsteht die unbalancierte Situation durch Aufteilung von
σ(v).

.,&'5<3%*

"*:5*%#"%4*6"/(%"*1>*
AlgoCG 09

!014
0 4
F,((3#,'*G#'<3%&

26

HI

Kapitel 2. Trees
Zum Beweis zeigen wir, dass nur O(m) Aufteilungen notwendig sind, um T zu balancieren.
Daraus folgt dann automatisch die Größe von T . Vorher muss folgendes Lemma gezeigt
werden.
Lemma 2.3.3
Seien v1 , v2 , v3 drei benachbarte Knoten auf gleicher Tiefe, wobei v2 , v3 Blätter in T sind. Für
jede beliebige Unterteilung von σ(v1 ) bewirken die balancierenden Aufteilungen durch den
Algorithmus in σ(v2 ) keine Aufteilung in σ(v3 ).
Das bedeutet, wenn der Nachbar eines Knotens v1 unbalanciert ist, dann wirkt sind die Balancierung des Knotens nur auf den direkten Nachbarn aus, aber nicht transitiv auf Nachbarn
des Nachbarn. Damit lässt sich zeigen, dass Balancierungen nur lokal vorgenommen werden
müssen. Abbildung 2.27 illustriert die Ausgangssituation.

Abbildung 2.27: Balancierung eines Quadtree.
Beweis 2.3.3
Der Beweis des Lemmas erfolgt per Induktion über die Tiefe d des Teilbaums unter v1 .
Anfang: Für d = 1 hat σ(v1 ) eine Unterteilung, σ(v2 ) und σ(v3 ) werden nicht unterteilt.
Schritt: Habe jetzt v1 Tiefe d > 1.
– Nach Voraussetzung verursacht die Balancierung im SW-Quadrat von σ(v2 ) (notwendig wegen kleiner SE-Quadrate in σ(v1 )) keine Aufteilung im SE-Quadrat von
σ(v2 ). Dies zeigt Abbildung 2.28.
– Das gleiche gilt nach Voraussetzung auch für das NE-Quadrat von σ(v2 ) bei einer
Balancierung im NE-Quadrat von σ(v1 ).
– ⇒ NE und SE in σ(v2 ) werden nicht aufgeteilt.
– ⇒ σ(v3 ) braucht nicht aufgeteilt zu werden.
Mit dem Lemma kann nun auch Satz 2.3.2 bewiesen werden.

AlgoCG 09

27

Kapitel 2. Trees

Abbildung 2.28: Auswirkung der Balancierung eines SE-Quadrats.

Abbildung 2.29: Auswirkung der Balancierung eines Quadrats auf benachbarte Knoten.

AlgoCG 09

28

Kapitel 2. Trees
Beweis 2.3.4
Die Unterteilung eines Quadrates σ(v) verursacht in anderen Quadraten σ(v 0 ) gleicher Größe
nur dann eine weitere Aufteilung, wenn v 0 eins der 8 benachbarten Quadrate von v ist. (Beweis
siehe Lemma) Abbildung 2.29 illustriert diesen Zusammenhang.
Die alten Quadrate seien die Quadrate von T . Die neuen Quadrate die zusätzlichen Quadrate von T ∗ . Betrachte nun den Split eines Quadrates σ:
• Der Split kostet 4 neue Knoten (die Kinder von σ).
• Eines der umgebenden Quadrate muss ein altes Quadrat σ ∗ sein, das den Split verursacht hat.
• Die Kosten des Splits (4) werden dem alten Quadrat σ ∗ zugewiesen.
⇒ Ein Quadrat kann nur maximal 8-mal (von jedem seiner 8 Nachbarn) Kosten zugewiesen bekommen. Damit ist die Steigerung der Knotenanzahl linear und die Größe des
balancierten Quadtrees folgt.
2.3.4.1 Laufzeit
Zuletzt soll noch die Laufzeit für die Balancierung berechnet werden.
Lemma 2.3.4
Sei T ein Quadtree mit m Knoten. Die balancierte Version kann in Zeit O((d + 1)m) konstruiert werden.
Beweis 2.3.5
Es wird nur eine konstante Anzahl von Nachbarschaftssuchen durchgeführt, weil ein Knoten
nur eine Konstante Anzahl von Nachbarn besitzt. Ein Blatt der Liste L kann damit in Zeit
O(d + 1) behandelt werden. Da es maximal O(m) Knoten gibt, beträgt die Laufzeit O((d +
1)m).

2.4 Loose Octrees
Quadtrees und Octrees führen eine vollständige Partitionierung des Raumes durch, die keine
Redundanz enthält und die Lage der Objekte nicht berücksichtigt. Der Nachteil der Vorgehensweise ist, dass nur Punkte eindeutig einsortiert werden können. Objekte, die eine Ausdehnung besitzen wie z.B. Dreiecke, müssen gesondert behandelt werden (siehe auch Abschnitt 2.3.1). Bevorzugt wird in der Regel die Variante, bei der ein Objekt in die tiefstgelegene Bounding-Box einsortiert wird, in die es vollständig hineinpasst. Falls aber ein sehr
kleines Objekt genau auf der Splittinggerade oder -ebene von zwei großen Boxen liegt, wie
in Abbildung 2.30 dargestellt, dann wird es sehr weit oben im Baum einsortiert. Man spricht
hierbei von sog. „Sticky Planes“. Dies kann durch Loose Octrees vermieden werden. Im folgenden werden alle Abbildungen im 2D gezeigt, da das Verfahren für Loose Quadtrees auf
die gleiche Weise funktioniert.

AlgoCG 09

29

HEINZ NIXDORF INSTITUT

$$

!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

(+,-."."/#"'-'#("0(12.-''

Kapitel 2. Trees

"*$/"*9.:%;(%"*-5&<3*%#"%"*9<(&%%

2*-%'*?,54%'*%&>/12(
2 -%' ?,54%' %&>/12(

-5"-,"A%"

-#2

&C<;'#<3(#25"2*,5>*-#%*D,2%*-%&*9.:%;(%

&*9.:%;(%*%#"G

Abbildung 2.30: Objekte, die Splittinggeraden schneiden, liegen in großer Bounding-Box.

Ein Knoten eines Octrees enthält immer den Mittelpunkt der Bounding-Box, Referenzen
auf alle 8 Kinder, sowie einen Vektor mit allen enthaltenen Objekten. Für das Einfügen eines
;(%*1,''%"*'#<3*%#">,<3*5"-*%#"-%5(#2*%#"'/&(#%&%"
Objektes wird zunächst eine Klassifikation durchgeführt, die in Algorithmus 11 dargestellt ist.
;(%*4#(*05'-%3"5"2*'#"-*A5')(A1#<3%*DH'5"2%"*2%>&,2(
2
2 2
2
Algorithmus 11 Klassifikation eines Knotens beim Einfügen in einen Octree
1: function C LASSIFY(Plane p, Volume v)
Lösung
2:
if v ist vollständig hinter p then
3:
return 0;
9.:%;(*'/*(#%>*F#%*4H21#<3*%#"*
4:
else if v ist vollständig vor p then
KL
I,((3#,'*J#'<3%&
M/&1%'5"2*N012/&#(34%"*#"*-%&*O/475(%&2&,>#;PQ*RR*LSSK
5:
return 1;
6:
else
. v wird von p durchtrennt
7:
return 2;
8:
end if
9: end function
Die Funktion zum Einfügen eines Objektes prüft nun das Bounding Volume des Objektes
gegen Ebenen durch den Mittelpunkt der Octree-Box, die parallel zur x-Achse, zur y-Achse
und zur z-Achse liegen. Falls das Objekt eine der Ebenen schneidet, wird es im Knoten
gespeichert. Falls nicht, passt es in einen Kindknoten.

2.4.1 Konstruktion
Das Ziel der Loose Octree Konstruktion ist es, dass kleine Objekte nicht mehr auf den StickyPlanes großer Boxen liegen bleiben, sondern tiefer durchfallen. Dies wird durch eine Vergrößerung der Bounding-Boxen erreicht. In einem herkömmlichen Octree gilt für die Größe der
Boxen und die Abstände der Mittelpunkte (in x, y, z Richtung):
L(d) =

W
2d

S(d) =

W
2d

Dabei beschreibt W die Größe der äußersten, alles umschließenden Box, sowie d die Tiefe
des Octree. Das bedeutet, die Seitenlängen der Boxen und die Abstände der Mittelpunkte sind
gleich groß wie in Abbildung 2.31 dargestellt.
In einem Loose-Octree wird die Kantenlänge der Bounding-Box um einen Faktor k vergrößert, ohne jedoch den Abstand zwischen den Boxen anzupassen. Dies führt dazu, dass sich
die Boxen überlappen wie in Abbildung 2.32 dargestellt.

AlgoCG 09

30

HEINZ NIXDORF INSTITUT

"#$%&'()$$

!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

#$%&'(%)"#

Kapitel 2. Trees

HEINZ NIXDORF INSTITUT

*3%&:;441#<3%"*=<(&%%*2#1(>
!""#$%&'()$$
!"#$%&'(%)"#
antenlänge
der Octree-Box
Octree Box

!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

),-,./0/1/2/3%),-,
Loose Octrees

?

9%&2&:;%&% -%" $/" -%" 6"/(%" .%1%2(%" <,54 #" ,11%"
9%&2&:;%&%*-%"*$/"*-%"*6"/(%"*.%1%2(%"*<,54*#"*,11%"
bstände =#4%"'#/"%"
der Boundingboxen
*8ABACDE#<3(5"2F

%),-,./0/1/2/3
> %),-,
?#&*$%&)"-%&"*-#%*6,"(%"1)"2%*-%&*@A(&%%BC/8%"
*+%),-,./0/(/1/2/3/4%),-,
( DE*%#"*F,G(/&*H*I
HEINZ NIXDORF INSTITUT
$$
-, >H*I#%J%*-%'*=<(&%%
!"#$%&'#()(*+,-%&./&"

G

012/&#(34%"*5"-*6/471%8#()(

Abbildung 2.31: Größe der Bounding-Box
>H*G)"2%*-%&*K/5"-#"2DK/8A*-#%*-#%*$#&(5%11%*?C%"%*54'<31#%L(
> ?#&*1,''%"*-#%*0.'()"-%*21%#A3
%),-,
es
5+%),-,./0/2/3/4
+
.

und Abstand der Mittelpunkte.

%"
%"*$/"*-%"*6"/(%"*.%1%2(%"*<,54*#"*,11%"
$/" -%" 6"/(%" .%1%2(%" <,54 #" ,11%"

> ?#&*1,''%"*J5K*-,''*'#A3*-#%*L//'%BC/5"-#"2./8%"*
-%& 6#"-%& M.%&1,77%"
-%&*6#"-%&*M.%&1,77%"

"-%&"*-#%*6,"(%"1)"2%*-%&*@A(&%%BC/8%"
/(/1/2/3/4%),-, Q/&1%'5"2*R012/&#(34%"*#"*-%&*S/475(%&2&,J#:TA*??*UVVO
F,G(/&*H*I

%"*-#%*0.'()"-%*21%#A3
0/2/3/4%),-,

M,((3#,'*N#'<3%&

9/&1%'5"2*Q012/&#(34%"*#"*-%&*R/475(%&2&,S#GTK*UU*VWWO

Abbildung
%"*J5K*-,''*'#A3*-#%*L//'%BC/5"-#"2./8%"*
%&
%&*M.%&1,77%"
M.%&1,77%"

(a)

OP

(b)

N,((3#,'*F#'A3%&

OP

2.32: Vergrößerte Bounding-Boxen im Loose Octree

Für die Kantenlänge und den Abstand der Mittelpunkte gilt damit:
L(d) = k ·
9/&1%'5"2*Q012/&#(34%"*#"*-%&*R/475(%&2&,S#GTK*UU*VWWO

N,((3#,'*F#'A3%&

W
2dOP

S(d) =

W
2d

Falls ein Objekt im Überlappungsbereich zweier Boxen liegt, entscheidet die Lage des Objektmittelpunktes bezogen auf die ursprünglichen Octree Boxen über die Einordnung. Das
Objekt wird in die Box einsortiert, in der ihr Mittelpunkt liegt. Durch die Redundanz wären
theoretisch auch andere Lösungen denkbar.
Über den Faktor k wird die Größe der Überlappung gesteuert. In der Literatur wird ein Faktor k = 2 als guter Kompromiss beschrieben. Er sorgt dafür, dass kleine Objekte tiefer im Octree durchfallen. Über die tatsächliche Tiefe entscheidet nun die Größe des Objektes und nicht
seine Position bezüglich der Splittingebenen. Abbildung 2.33 zeigt die Überlappungsbereich
ist grau für zwei verschiedene k-Werte.
Lemma 2.4.1
Ein Objekt mit Radius (k−1)· L4 fällt mindestens bis auf Tiefe d, wobei L =
der Octree Bounding-Box ist.

W
2d

die Kantenlänge

Beweis 2.4.1
Die Objekte bleiben nur im grau schraffierten Bereich liegen. Liegt das Objekt komplett im
weißen Bereich, wird es noch eine Ebene tiefer einsortiert. Die Größe des grau schraffierten

AlgoCG 09

31

(

123

%%/)0

E#"*<.=%:(*4#(*F,-#5'*41+56&7&(&8&9 ;)11(*4#"-%'(%"'*.#'*
HEINZ NIXDORF INSTITUT
,5;*@#%;%*'?*>/.%#*(&:&;&8&3' -#%*6,"(%"1)"2%*-%&*
!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(
<G(&%%HI/5"-#"2./8
<G(&%%
I/5"-#"2./8*#'(
#'(

Kapitel 2. Trees
3"

I%>%#'J

%:(*>%&-%"?*54*,5;*%#"%4*
K <.=%:(%*.1%#.%"*"5&*#4*2&,5*'G3&,;;#%&(%"*I%&%#G3*
=
2
%2%"*B5*.1%#.%"CD
2

1#%2%"

(

123
K 3"&:&174(836&< 4(836&:&41+567&4(836
" : 41 567(89
"&:&41+56
(89
'*41+56&7&(&8&9 ;)11(*4#"-%'(%"'*.#'*
&;&8&3' -#%*6,"(%"1)"2%*-%&*
3"
#'(

1:3

(a)

(b)

"5&*#4*2&,5*'G3&,;;#%&(%"*I%&%#G3*
2
Q/&1%'5"2*R012/&#(34%"*#"*-%&*S/475(%&2&,;#:T?*UU*POOV

L,((3#,'*M#'G3%&

NOP

Abbildung 2.33: Überlappungsbereiche in Abhängigkeit des Parameters k.

36&:&41+567&4(836

Bereichs ist:

1:3

2r = k · L2 − L2 = (k − 1) ·
⇒ r = (k − 1) · L4

L
2

Der grau schraffierte Bereich entspricht dem Überstand der Bounding-Box. Eine original
L
Bounding-Box hat Größe L,((3#,'*M#'G3%&
. MultipliziertNOPman mit k erhält man die neue Größe, subtrahiert
2
L
man dann 2 erhält man nur den Überstand.
Wählt man k < 2 fallen nur ganz kleine Objekte in die nächste Ebene. Für k = 2 passen
alle Objekte, deren Kantenlänge gleich der original Octree Bounding-Box ist, in den entspreHEINZ NIXDORF INSTITUT
""#$%&'()$$ chenden Knoten. Für k > 2 werden die Überlappungen
zu groß.
!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(
"#$%&'%"&())*%+,-."%%/)0
Ein Nachteil des Loose Octrees ist, dass der Raum, den die Elternknoten inklusive ihrer
vergrößerten Bounding-Box aufspannen, nicht mehr vollständig von den Kindern abgedeckt
Verlust der vollständigen
wird. DieAufteilung
ist in Abbildung 2.34 dargestellt.

2/&#(34%"*#"*-%&*S/475(%&2&,;#:T?*UU*POOV

9 :%&
:%&*2%',4(%*;,54*-%'*<1(%&"="/(%"*
2%',4(% ;,54 -%' <1(%&"="/(%"
123.%"4 >#&-*"#?3(*4%3&*-5&?3*-#%*
@544%*,11%&*6#"-%&*1564'%" ,.2%-%?=(

AB

A<1(%&"

A6#"-%&

A

C,'*4,?3%"*>#&*4#(*D.E%=(%"*,F*-#%*"#?3(*
2&GH%& '#"- ,1' -#% D?(&%%IA/5"-#"2./8
2&GH%&*'#"-*,1'*-#%*D?(&%%
A/5"-#"2./8*1
1
-%&*6#"-%&*1564'%" F*-#%*"#?3(*#"*-%4*
,.2%-%?=(%"*A%&%#?3*1#%2%"J
9 :#
:#%'%*K#"-%"*#"*-%"*6#"-%&"*-%&*
K# - # - 6# L%'?3>#'(%&*-%&*<1(%&"*+1,(M*
NO/5'#"P%Q

D

Abbildung 2.34: Kinder decken den Raum der Eltern nicht mehr vollständig ab.
TUV
B ist die Bounding-Box des Kindes, währendR,((3#,'*S#'?3%&
BL die Bounding-Box
des Elternknotens ist.
BKinder und BEltern bezeichnen jeweils die vergrößerten Bounding-Boxen. Es kann nun Objekte O geben, die innerhalb der Bounding-Box des Elternknotens liegen und von der Größe
her in einen Kindknoten hineinpassen, aber nicht vollständig innerhalb der von den Kindern

W/&1%'5"2*X012/&#(34%"*#"*-%&*O/475(%&2&,K#=YF*@@*ZUU[

AlgoCG 09

32

Kapitel 2. Trees
abgedeckten Fläche liegen. Diese Knoten werden dann in einem Kind eines Geschwisterknotens des Elternknotens gespeichert (Cousin/e). Im Beispiel ist dies ein Kind des linken
Geschwisters von BL.
2.4.1.1 Direkte Platzierung
Die Vergrößerung der Bounding-Boxen um den Faktor k = 2 kann man eine direkte Platzierung der Objekte in Zeit O(1) im Loose Octree durchführen. Eine Traversierung des Baums
ist nicht mehr notwendig.
Wie zuvor gezeigt passen alle Objekte mit einem Radius von weniger 14 der Seitenlänge
(Durchmesser halbe Seitenlänge) der originalen Bounding-Box in den entsprechenden LooseOctree-Knoten. Dies ist unabhängig von der Position, da die Bounding-Box durch den Faktor
k = 2 in alle Richtungen um ein Viertel der orginalen Seitenlänge vergrößert wurde. Ein
Knoten mit Radius von weniger als 18 der Ausgangsbox sollte eine Ebene tiefer gespeichert
werden.
Sei nun Rmax (d) der maximale Objektradius, der in Tiefe d gespeichert werden kann. Es
wird nun von unten nach oben die erste Ebene gesucht, die ein Objekt mit Radius R aufnehmen
kann. Diese Ebene habe Tiefe d(R).
. Damit ergibt sich
Die Kantenlänge einer Box in Tiefe d ist L(d) = 2 · W
2d
1
1W
Rmax (d) = L(d) =
4
2 2d
Damit ein Objekt in eine Ebene passt, muss sein Radius kleiner als der maximal mögliche
Radius sein. Damit ergibt sich:
R ≤ Rmax (d(R))
≤ 12 W
2d
d(R) ≤ log( W
)−1
R
Die direkte Platzierung speichert einen Knoten jedoch nicht immer auf der tiefst möglichen
Ebene. Dies liegt daran, dass abhängig von seiner Position auch ein Knoten mit Durchmesser
L(d) in einer Box gespeichert werden könnte. Dieser wird jedoch höher im Baum abgelegt.
Eine Optimierung ist daher, über die Berechnungsformel die passende Ebene auszurechnen
und dann die Kinder abzutesten, ob diese das Objekt aufnehmen können. Falls ja, wird das
Objekt in den Kindknoten geschoben, sonst bleibt es auf der berechneten Ebene.

2.4.2 Nutzen
Das Frustum Culling funktioniert mit Loose Octrees genauso wie mit normalen Octrees. Dazu
wird der Baum von der Wurzel aus traversiert. Falls ein Knoten nicht sichtbar ist, wird die
Traversierung direkt abgebrochen, ohne die Kinder zu berücksichtigen. Ansonsten werden
die Objekte des Knoten ausgegeben und die Kinder werden betrachtet (bei vollständiger oder
teilweiser Sichtbarkeit).

AlgoCG 09

33

Kapitel 2. Trees
Messungen haben gezeigt, dass durch die Verwendung von Loose Octrees und die damit
verbundene tiefere Einsortierung von kleinen Objekten bei einer Sichtbarkeitsanalyse weniger „möglich sichtbare“ Objekte zurückgegeben werden. Der Nachteil ist, dass durch die vergrößerten Bounding-Boxen mehr Knoten untersucht werden müssen.

AlgoCG 09

34

3 Visibility Culling
HEINZ NIXDORF INSTITUT
Walkthrough-Problem - Echtzeit-Rendering
!"#$%&'#()(*+,-%&./&"
In einer
Szene
sind
nicht
immer
alle
Teile
eines
Objektes
sichtbar.
Man
muss aber jedes
012/&#(34%"*5"-*6/471%8#()(
Visibility Culling
Objekt einmal anfassen und prüfen, ob es sichtbar ist. Der zeitliche Aufwand hängt damit von
allen Objekten ab und nicht nur von den sichtbaren. Dies ist ineffizient. Deshalb möchte man
Lösungsansatz
nicht sichtbare Objekte oder nicht sichtbare Teile von Objekten nicht explizit rendern. Eine
9#& .%&%:3"%"
9#&*.%&%:3"%"*,11%*/-%&*,5:3*"5&*%#"#2%*5"'#:3(.,&%*+/1;2/"%
,11% /-%&
,5:3 "5&
%#"#2%
5"'#:3(.,&%
Übersicht
über mögliche
Verfahren
zeigt
Abbildung
3.1. +/1;2/"%

/.<%:(

7/1;2/"

Frustum Culling

/.<%:(

Backface Culling

Occlusion Culling

Abbildung 3.1: Übersicht über verschiedene Culling Techniken.

= Frustum Culling
>.<%?(%*/-%&*+/1;2/"%*,5@%&3,1.*-%'*A#:3(?%2%1'*B%&-%"*"#:3(*2%C%#:3"%(

Der Sichtkegel des Benutzers wird Frustum genannt. Alles was außerhalb dieses Kegels
= nicht
Backface
Culling
liegt ist
sichtbar
und muss nicht betrachtet werden. Diese Funktion ist in jedem einfa+/1;2/"%D*-#%*$/"*3#"(%"*C5*'%3%"*'#"-D*B%&-%"*"#:3(*2%C%#:3"%(
chen Renderer implementiert und wird auch Clipping genannt. Von einem Polygon können
Occlusion
Culling
einige= Flächen
nur von
hinten betrachtet werden (backfaces). Diese sind dann nicht sichtbar
>.<%?(%D*-#%*#4*A#:3(?%2%1*3#"(%&*,"-%&%"*+/1;2/"%"*$%&-%:?(*1#%2%"D*B%&-%"*
und werden
nicht gezeichnet. Diese Funktion wird typischerweise von der Grafiklibrary oder
Hardware"#:3(*2%C%#:3"%(
unterstützt.Die schwierigste Technik ist das Occlusion Culling. Dabei werden PoGH
E,((3#,'*F#':3%&
I/&1%'5"2*J012/&#(34%"*#"*-%&*K/475(%&2&,L#?MD*AA*NOOP
lygone berechnet, die von anderen Polygonen verdeckt werden. Diese Technik befindet sich
noch in der Erforschung. Man bezeichnet die Techniken des Backface Culling und des Occlusion Culling auch als Hidden Surface Removal, da hier nicht sichtbare Oberflächen entfernt
werden.
Eine Berechnung der Sichtbarkeit für jedes Polygon ist zu aufwändig. Dies kann von der
Rendering Pipeline mit dem Z-Buffer-Algorithmus schneller durchgeführt werden. Der Grund
für den Einsatz von Occlusion Culling ist Effizienz, d.h. man möchte noch schneller sein als
der Z-Buffer. Man benutzt deshalb Datenstrukturen wie die in Kapitel 2 vorgestellten Octrees,
BSP-Trees oder kd-Bäume, die einen schnellen Zugriff auf Teile der Szene erlauben. Sie
erlauben es, schnell große Mengen von Objekten als nicht sichtbar zu klassifizieren.
Ein wichtiges Maß für dafür, ob sich ein Culling lohnt ist die Tiefenkomplexität. Die Tiefenkomplexität beschreibt die Anzahl der verdeckten Dreiecke, die hinter einem sichtbaren
Dreieck liegen. Sie ist standpunktabhängig und fällt für unterschiedliche Szenen unterschiedlich hoch aus. Für eine Wiese ist sie sehr gering, in einer Stadtszene abhängig vom Standpunkt
hoch (vgl. Abbildung 3.2).

35

Kapitel 3. Visibility Culling

Abbildung 3.2: Abhängigkeit der Tiefenkomplexität vom Standpunkt.

AlgoCG 09

36

ility Culling

dbegriffe

Kapitel 3. Visibility Culling
Probleme für das Culling entstehen, wenn nur wenige unsichtbare Dreiecke existieren. In
diesem Fall ist der Aufwand für die Berechnung der unsichtbaren Dreiecke höher als die tatsächliche Einsparung. Falls die Anzahl der unsichtbaren Dreiecke stark schwankt, z.B. die
Kamera fährt dicht hinter einem Pfahl entlang, entstehen ebenfalls Probleme. Der Algorithmus kann dann unter Umständen nicht alle Dreiecke in akzeptabler Zeit klassifizieren. Man
muss somit einen Trade-off zwischen Culling-Test und Renderingzeit finden:
• Eine Szene hat n0 Dreiecke, davon werden n durch den Cullingalgorithmus in Zeit tc (n)
als unsichtbar klassifiziert.
• Das Rendering von n Dreiecken kostet Zeit tr (n), für die restlichen n0 − n Dreiecke
kostet tr (n0 − n).
• Man erhält die Gesamtlaufzeit tges (n) = tr (n0 − n) + tc (n)
Falls tc (n) ≥ tr (n) gilt, dann lohnt sich das Culling offensichtlich nicht, d.h. die auf der
HEINZ
NIXDORF
INSTITUT
CPU durchgeführte
Berechnung der unsichtbaren Polygone darf nicht
länger
dauern
als ihre
Visibility Culling
!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(
„Darstellung“
durch die Rendering Pipeline.
Grundbegriffe
9%#*O -#%*:%"2%*-%&*;.<%=(%>+&#4#(#$%*#"*-%&*$#&(5%11%"*9?%"%*
@A&*%#"%"*2%2%.%"%"*9(,"-75"=(*'%#B
3.1 Potentially
Visible Sets

HEINZ NIXDORF INSTITUT

!"#$%&'#()(*+,-%&./&"
C S -#%*:%"2%*-%&*'#D3(.,&%"*E%#1%F012/&#(34%"*5"-*6/471%8#()(

Ein Potentially Visible Set (PVS) enthält die Objekte, die wahrscheinlich sichtbar sind. Dies
C keine
U -#%*:%"2%*-%&*5"'#D3(.,&%"*E%#1%G
9
ist jedoch
exakte Sichtbarkeitslösung. Man berechnet schnell!eine konservative
Über-#%*:%"2%*-%&*;.<%=(%>+&#4#(#$%*#"*-%&*$#&(5%11%"*9?%"%*
schätzung der sichtbaren Primitive, das PVS. Die exakte Sichtbarkeit wird durch die Anwen"%"*2%2%.%"%"*9(,"-75"=(*'%#B
HEINZ NIXDORF INSTITUT
dung des
Z-Buffer
Algorithmus auf dem PVS in der Rendering-Pipeline berechnet.
:,"*5"(%&'D3%#-%(*:%(3/-%"*",D3*-%&*0&(F
!"#$%&'#()(*+,-%&./&"
S -#%*:%"2%*-%&*'#D3(.,&%"*E%#1%F
012/&#(34%"*5"-*6/471%8#()(
ManI#%*'#%*-,'*9#D3(.,&=%#('7&/.1%4*1H'%"B
kann
drei
Arten
für eine Menge O von Objekten einer
# # - 9# 3(.von
= #(Sichtbarkeitsberechnungen
.1
1H
U -#%*:%"2%*-%&*5"'#D3(.,&%"*E%#1%G
virtuellenC Szene
durchführen. Für einen!gegebenen
und U
9
9 Standpunkt sind!S die sichtbaren
$%*#"*-%&*$#&(5%11%"*9?%"%*
!"#$%&'()(*(+(%,
die unsichtbaren
Objekte.
Die verschiedenen Ansätze sind in Abbildung 3.3 dargestellt.
-#%*:%"2%*S
2
I#&-*.%&%D3"%(G

#B
5"(%&'D3%#-%(*:%(3/-%"*",D3*-%&*0&(F
C -./)012#%(20&'()(*(+(%,
%F
%*-,'*9#D3(.,&=%#('7&/.1%4*1H'%"B
- 9# 3(. = #(
.1
1H-#%*:%"2%*S 715'*%(I,'*,5'*U I#&-*.%&%D3"%(F
%#1%G
J-%& E%#1 ,5'
J-%&*E%#1*,5'*U
'/11 4H21#D3'( =1%#" '%#"K 9
9 U '/11*4H21#D3'(*=1%#"*'%#"K*
9
!
!
!
!"#$%&'()(*(+(%,
#%*:%"2%*S
2
I#&-*.%&%D3"%(G
C 3441."(5#%(20&'()(*(+(%,
%#"*E%#1*$/"*S 715'*%(I,'*,5'*U I#&-*.%&%D3"%(
%&*0&(F
-./)012#%(20&'()(*(+(%,
(a)
(c)
J-%&*E%#1*,5'*S
'/11*4H21#D3'(*2&/UF* (b)
%"B
#%*:%"2%*S 715'*%(I,'*,5'*U I#&-*.%&%D3"%(F
-%&*E%#1*,5'*U '/11*4H21#D3'(*=1%#"*'%#"K*
-%&*E%#1*,5'*U
-%& E%#1 ,5' U '/11*4H21#D3'(*=1%#"*'%#"K*
'/11 4H21#D3'( =1%#" '%#"K 9
9
!
:,((3#,'*@#'D3%&
Abbildung !
3.3: (a) zeigt
einen exact visibility
Test, (b) einen conservative
Test und (c)LMeinen
N/&1%'5"2*O012/&#(34%"*#"*-%&*P/475(%&2&,Q#=RF*99*SMMT
3441."(5#%(20&'()(*(+(%,
approximative Test.
#"*E%#1*$/"*S 715'*%(I,'*,5'*U I#&-*.%&%D3"%(
-%&*E%#1*,5'*S '/11*4H21#D3'(*2&/UF*
I#&-*.%&%D3"%(F
%&*E%#1*,5'*U '/11*4H21#D3'(*=1%#"*'%#"K*
#" '%#"K
#"*'%#"K*
• Exact! Visibility9
LM
:,((3#,'*@#'D3%&
N/&1%'5"2*O012/&#(34%"*#"*-%&*P/475(%&2&,Q#=RF*99*SMMT

I#&-*.%&%D3"%(
/UF*
"*'%#"K*

Berechne nur die sichtbaren Objekte.
• Conservative Visibility
Berechne die sichtbaren und einen (möglichst kleinen) Teil der unsichtbaren Objekte.
:,((3#,'*@#'D3%&

RF*99*SMMT

AlgoCG 09

LM

37

Kapitel 3. Visibility Culling
• Approximative Visibility
Berechne einen (möglichst großen) Teil der sichtbaren und einen (möglichst kleinen)
Teil der unsichtbaren Objekte.

3.2 Occlusion Culling mit Potentially Visible Sets
Es soll ein Occlusion Culling durchgeführt werden, so dass beim Walkthrough möglichst wenig Objekte gerendert werden müssen. Dazu sollen die architektonischen Eigenschaften der
Szene ausgenutzt werden. Dazu gehören verdeckende Elemente wie Räume, Flüre, Nischen,
Stockwerke (Wände) und nicht verdeckende Elemente wie Durchgänge, offene Türen, sowie
Fenster. Während Menschen eine natürliche Vorstellung davon haben, was eine Tür ist und
was ein Raum, muss dies für einen PC berechnet werden. Es werden daher zwei strukturelle
Elemente eingeführt.
Definition 3.2.1 (Zelle)
Eine Zelle definiert einen „Raum“, der von Wänden und Portalen
umschlossen
ist. Wände
HEINZ NIXDORF
INSTITUT
Occlusion Culling mit Potentially Visible Sets
!"#$%&'#()(*+,-%&./&"
sind grundsätzlich
undurchsichtig.
012/&#(34%"*5"-*6/471%8#()(
Eigenschaften architektonischer Modelle
Definition 3.2.2
(Portal)
!"#$%#"&"'()*'+"&&",'-,.'/0*12&"
Ein Portal definiert einen durchsichtigen oder offenen Teil eines Raums. Portale verbinden die
9%11%"*5"-*+/&(,1%*%"('7&%:3%"*"#:3(*#44%&*5"'%&%&*;/&'(%115"2*$/"*<)54%"*
einzelnen Räume
miteinander.
5"-*=>&%"?

Eine 3D-Szene
besteht nun aus Zellen und Portalen, die wie in Abbildung 3.4 dargestellt
@#%*%&A%""(*5"-*.%&%:3"%(**4,"*<)54%*5"-*=>&%"*B
nicht immer der menschlichen Vorstellung von einem Raum entsprechen.

EF
Abbildung 3.4: Wände (schwarz) und Portale (rot gestrichelt),C,((3#,'*D#':3%&
die verschiedene
Zellen
definieren.
;/&1%'5"2*G012/&#(34%"*#"*-%&*H/475(%&2&,I#AJK*LL*MNNF

3.2.1 Idee der Methode
Die Sichtbarkeitsberechnung wird in zwei Schritte aufgeteilt.
1. Cell-to-Cell Visibility (C2C-Visibility)
Wird im Preprocessing (vor dem Walkthrough) berechnet und umfasst sichtpunktunabhängige Sichtbarkeitsaussagen. Dazu wird ein Adjazenzgraph berechnet, der benachbarte Zellen verbindet.

AlgoCG 09

38

Kapitel 3. Visibility Culling
2. Eye-to-Cell Visibility (E2C-Visibility)
Wird während des Walkthrough berechnet und umfasst sichtpunktabhängige Sichtbarkeitsaussagen. Dazu wird der Adjazenzgraph traviersiert und die Sichtlinien des Beobachters gegen eine Folge von Portalen geprüft. Dadurch erhält man sichbare Zellen.
Die Zellen sind die Grundelemente des PVS über HEINZ
die NIXDORF
der Adjazenzgraph
berechnet wird.
INSTITUT
Occlusion Culling mit Potentially Visible Sets
Während
des Walkthroughs ist eine Zelle nur dann sichtbar, wenn sie durch eine Folge von
Berechnungsbeispiel
Portalen sichtbar ist, wie in Abbildung 3.5 dargestellt.
!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

;/*<#%*0*#'(*,5=3*>*%#"*
?,=3.,&*$/"*9
6,"" 4," #" ,11%
6,""*4,"*#"*,11%*
.%",=3.,&(%"*D)54%*
'%3%"E

:

0
9
B

@

A

C

>
0
B

:
A

9

@

C

>
QB#1-%&R*9,$#-*S5%.L%N*!"#$%&'#(T*/K*I#&2#"#,U
I/&1%'5"2*J012/&#(34%"*#"*-%&*A/475(%&2&,K#LMN*;;*GOOP

F,((3#,'*@#'=3%&

GH

Abbildung 3.5: Sichtbarkeit verschiedener Räume mit einem gegebenen Adjazenzgraphen.
Die Sichtbarkeit einer Zelle reduziert sich auf das Testen von Sichtlinien durch eine Folge
von Portalen. Der Adjazenzgraph enthält für jede Zelle einen Zustand und eine Kante zwischen zwei Knoten, wenn die entsprechenden Räume durch ein Portal verbunden sind. Ausgehend von Raum E, in dem der Betrachter steht, sieht der Betrachter natürlich Raum E, aber
auch alle direkt benachbarten Räume durch die Portale in Raum E. Dies sind die Räume D,
F und G. Die zu diesen Räumen adjazenten Räume werden nur gesehen, wenn eine Sichtverbindung durch Portale besteht. Dies ist für Raum A der Fall, für Raum H kreuzen die
Sichtbarkeitslinien undurchsichtige Wände. H ist somit nicht sichtbar.

3.2.2 Berechnung des Adjazenzgraphen
Es wird eine 2D-Projektion eines Gebäudes oder Stockwerks auf die Grundrisse bestehend
aus Wänden und Portalen durchgeführt. Dabei wird eingeschränkt angenommen, dass alle
Wände senkrecht zueinander stehen. Damit sind alle Liniensegmente achsenparallel. Für
das entstehende 2D-Problem wird ein BSP-Baum zur räumlichen Aufteilung berechnet. Die
Blätter des BSP-Baums stellen räumliche Bereiche dar, die die Zellen bilden. Die Wurzel des
BSP ist die Bounding-Box der Eingabe. Abbildung 3.6 zeigt ein Beispiel für die Berechnung
des Adjazengraphen.
Die Elemente der Szene werden als Splittinggeraden gewählt. Dabei wird zunächst auf
die Existenz von spanning faces geprüft. Diese teilen eine Zelle ohne andere Segmente zu

AlgoCG 09

39

@ >%-%'*91,((*#'(*%#"*6"/(%"*#4*9,54
@ .%",B3.,&(%*6"/(%"*=%&-%"*-,""*$%&.5"-%"C*=%""*%#"*+/&(,1*
HEINZ NIXDORF INSTITUT
%8#'(#%&(
mit Potentially Visible
Sets
!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

Kapitel 3. Visibility Culling

%"*;#"#%"'%24%"(%"*%#"%"*<=>

:%&-%"*,1'*B71#((#"22%&,-%"

B71#((#"22%&,-%"@

(a)

*C,E%'D*%8#'(#%&%"G*-,""*:)31%*
C
D # (#
)31
%&%*B%24%"(
Abbildung 3.6:

'7,""#"2 C,E%
'7,""#"2*C,E%

(b)
A%11%"*4#(*0->,?%"?2&,73

Für einen Grundriss zeigt (a) eine spanning face und (b) die Zellen mit dem
FG
D,((3#,'*E#'B3%&
Adjazenzgraphen.

H/&1%'5"2*I012/&#(34%"*#"*-%&*J/475(%&2&,K#<LC*::*GMMN

E%*(%#1(*%#"%*H%11%G*/3"%*,"-%&%*
( #1( # H 11
3
E3"%#-%"*JC&%%*'71#(KL

N

<
schneiden (Free-Split!).
Falls mehrere existieren, wird die mittlere ausgewählt. Ansonsten
<
wird das Segment verwendet, das möglichst wenige andere Segmente schneidet. Falls mehrere
%"(G*-,'*4O21#E3'(*:%"#2*,"-%&%* N
zur Auswahl stehen, wird das mittlere verwendet.
%#-%(P
N Q
N Q Q N Q einer
Q Q NZelle und wird somit zu einem Knoten des AdjazenzJedes Blatt des BSP
entspricht
I,31*:)31%*-,'*4#((1%&%*B%24%"(
graphen. Banachbarte Knoten werden dann verbunden, wenn ein Portal existiert. Dazu muss
es möglich sein, Nachbarn zu
identifizierenTQund die Portale der Szene zu enumerieren.
R,((3#,'*S#'E3%&
Der Algorithmus führt eine Klassifikation der Eingabesegmente durch.

012/&#(34%"*#"*-%&*W/475(%&2&,C#XYG*BB*<NNZ

• disjunkt: Segment hat keinen Schnitt mit der (Wurzel-)Zelle
• spanning: Ein Segment F partitioniert die Zelle in Komponenten, die sich nur an den
Rändern schneiden.
• covering: Ein Segment F liegt auf dem Rand einer Zelle.
• incident: sonst
Falls eine Zelle keine inzidenten Segmente hat und somit leer ist, wird die rekursive Berechnung abgebrochen.

3.2.3 Berechnung der Cell-to-Cell Visibility
Es wird an Hand des Adjazenzgraphen für eine Zelle C eine Berechnung der direkt oder
indirekt von C aus sichtbaren Zellen durchgeführt. Dabei ist der Standpunkt innerhalb von
C egal. Die Berechnung wird über einen Stabtree durchgeführt. Jeder Knoten im Stabtree
entspricht einer von C aus sichtbaren Zelle. Die Knoten werden im Stabtree mit einer Kante
verbunden, wenn sie durch ein Portal direkt benachbart sind und die Sichtlinie durch dieses
Portal verläuft. Ein Beispiel für einen Stabtree zu einer Szene zeigt Abbildung 3.7.
Die Räume F, H und G, sowie die Räume D und A sind über direkte Sichtlinien von E
aus zu sehen. Die konkrete Position des Beobachters in E wird dabei in diesem Schritt nicht
berücksichtigt. Die Räume B und C sind nicht sichtbar.
Die Berechnung des Stabtrees wird nun über eine Tiefensuche im Adjanzenzgraphen durchgeführt. Für jedes gefundene Portal werden die Endpunkte des Portals in einer Menge Lp für
die linken und Rp für die rechten Endpunkte gespeichert. Eine Sichtlinie kann die Folge von

AlgoCG 09

40

HEINZ NIXDORF INSTITUT

Occlusion Culling mit Potentially Visible Sets

!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

Cell-to-Cell Visibility - 2

Kapitel 3. Visibility Culling

!"#$%#"&'()*+,*-""

:

:

9

9

;
<

=

HEINZ NIXDORF INSTITUT

Occlusion Culling mit Potentially Visible Sets
Cell-to-Cell Visibility - 3

;

<

!"#$%&'#()(*+,-%&./&"
>012/&#(34%"*5"-*6/471%8#()(

0

!"#"$%&'&()*"#)+,$%-.,&,"&)*'#$%)",&")/0.(")10&)
=#%*@%11%"*?*5"-*>*AB""%"*$/"*A%#"%&*
+/'#(#/"*#"*9*%#"2%'%3%"*C%&-%"
20#-3."&

=

0

?

9 %#"%*:/12%*$/"*+/&(,1%"*%"('(%3(*-5&;3*(&,$%&'#%&%"*
Abbildung 3.7: Stabtree
zu einer Menge von Zellen.
HEINZ NIXDORF INSTITUT
ulling -%'*0-<,=%"=2&,73%"
mit Potentially Visible Sets
!"#$%&'#()(*+,-%&./&"

D,((3#,'*:#'E3%&

H/&1%'5"2*I012/&#(34%"*#"*-%&*>/475(%&2&,J#AKL*MM*NOOP

sibility - 3

FG

012/&#(34%"*5"-*6/471%8#()(

Portalen nur durchstechen, wenn Lp und Rp linear trennbar sind, d.h. es existiert eine Gerade
9 >?&*<%-%'*(&,$%&'#%&(%*+/&(,1*'7%#;3%&"*@#&*-#%*
S
für die gilt
A"-75"B(%*-%'*+/&(,1'*#"*%#"%&*C%"2%*D
7 5"-*E7

)*"#)+,$%-.,&,"&)*'#$%)",&")/0.(")10&)

S · L ≥ 0, ∀L ∈ Lp
S · R ≤ 0, ∀R ∈ Rp
D
HEINZ NIXDORF INSTITUT
Visible
Sets
!"#$%&'#()(*+,-%&./&"
2%*$/"*+/&(,1%"*%"('(%3(*-5&;3*(&,$%&'#%&%"*
A#"%*F#;3(1#"#%*B,""*-#%*:/12%*$/"*+/&(,1%"*"5&*
Ein Beispiel für
eine solche lineare Trennung zeigt Abbildung 3.8. Für eineD Menge von m
012/&#(34%"*5"-*6/471%8#()(
D
=%"=2&,73%"
-5&;3'(%;3%"G*@%""*D
5"-*E
'#"-G*-H3H*%'*mit 2m Randbedingungen,
7
7 linear
Portalen ist dies ein Problem
der trennbar
linearen Programmierung
dass in
E
E
%8#'(#%&(*%#"%*I%&,-%*FG*'/*-,''*2#1(J
Zeit
O(m)
für
eine
Linie
lösbar
ist.
Für
die
Berechnung
des
Stabtree
muss
dieses
Problem
*(&,$%&'#%&(%*+/&(,1*'7%#;3%&"*@#&*-#%*
&")/0.(")10&)also mehrfach gelöst werden.
B(%*-%'*+/&(,1'*#"*%#"%&*C%"2%*D
7 5"-*E7
E

5&;3*(&,$%&'#%&%"*
%*B,""*-#%*:/12%*$/"*+/&(,1%"*"5&*
"G*@%""*D7 5"-*E7 linear trennbar '#"-G*-H3H*%'*
%&"*@#&*-#%*
*I%&,-%*FG*'/*-,''*2#1(J
"2%*D7 5"-*E7
D

(a)

M/&1%'5"2*N012/&#(34%"*#"*-%&*O/475(%&2&,>#BPG*FF*QRRS

D

D
E E

D D
E

(b)

D

D D

E E

E
(c)
C,((3#,'*:#';3%&

KL

,1%"*"5&*
Abbildung 3.8: Für den Grundriss
in (a) zeigtD(b)
D D
D eine existierende lineare Trennung und (c)
ennbar '#"-G*-H3H*%'*

RS

eine
E Ezweite.

E E

E
Das Vorgehen fasst Algorithmus
12 zusammen.
E
Der Algorithmus Stabbing_Line(P ) berechnet,
ob für eine gegebene
Folge von Portalen
KL
C,((3#,'*:#';3%&
M/&1%'5"2*N012/&#(34%"*#"*-%&*O/475(%&2&,>#BPG*FF*QRRS
eine Sichtlinie existiert, die Dalle Portale durchquert. Falls diese existiert, wird versucht, eine
weitere Zelle anzufügen.
D

D

E E

3.2.4 Berechnung der Eye-to-Cell Visibility
E

Mit dem berechneten
Stabtree für dieKL Zelle, in der der Beobachter steht, müssen nur die von
C,((3#,'*:#';3%&
dort aus sichtbaren Zellen gerendert werden. Dies entspricht jedoch einer 360 Grad Sicht

AlgoCG 09

41

Kapitel 3. Visibility Culling
Algorithmus 12 Algorithmus zum Berechnen eines Stabtree
1: function F IND _V ISIBLE _C ELLS(Cell C, Portal-Sequenz P , Visible-Cell-Set V )
2:
V := V + C
3:
for each Nachbar N von C do
4:
for each Portal p, das C und N verbindet do
5:
Orientiere p von C nach N
6:
P0 = P ◦ p
7:
if Stabbing_Line(P 0 ) exists then
8:
Find_Visible_Cells(N , P 0 , V )
9:
end if
10:
end for
11:
end for
12: end function
von allen möglichen Standorten innerhalb der Zelle ausgehend. Dies lässt sich jedoch weiter
optimieren, indem man zusätzlich den Sichtkegel (Frustum) des Beobachters mit in Betracht
zieht.
Es gibt vier Verfahren, um den Standpunkt und den Sichtkegel des Beobachters auszunutzen. Die Verfahren steigen in Effektivität und Komplexität von oben nach unten an. Sei im
Folgenden S der Stabtree und C das Frustum des Beobachters. Wir schneiden nun das Frustum gegen den Stabtree und rendern nur die Zellen, die der Beobachter wirklich sehen kann.
1. Zellentest mit Frustum
Prüfe für jede Zelle den Schnitt mit dem Frustum wie in Abbildung 3.9 (a) dargestellt.
Der Schnitt mit dem Frustum ergibt die Zellen O, G und H, von denen G und H jedoch
unsichtbar sind. Die übrigen Zellen fallen weg. Die Laufzeit dieser Methode ist O(|V |),
wobei V die Menge der Zellen ist.
2. Tiefensuche mit Zellentest
Führe eine Tiefensuche von O in S durch mit der Abbruchbedingung, dass alle traversierten Zellen im Frustum liegen. Ist eine Zelle nicht sichtbar, wird die Suche an dieser Stelle abgebrochen. Das Beispiel in Abbildung 3.9(b) zeigt, dass F, G, H und O zurückgegeben werden, obwohl G und H unsichtbar sind. Die Laufzeit dieser Methode ist
O(|S|), d.h. die Laufzeit ist linear in der Größe des Stabtrees. Diese ist abhängig von
der Anzahl der Pfade, die jedoch größer als die Anzahl der Knoten sein kann.
3. Tiefensuche mit Portaltest
Suche von O aus alle Zellen in S, die über Portale erreichbar sind und im Frustum liegen.
Damit fällt in Abbildung 3.9(c) die Zelle G weg, die Zelle H bleibt jedoch erhalten,
obwohl sie unsichtbar ist. Die Laufzeit dieser Methode ist O(|S|), wobei S wiederum
die Größe des Stabtree ist.
4. Exakte Eye-To-Cell Visibility
Prüfe für die erreichbaren Portalsequenzen, ob eine im Frustum liegende Sichtlinie vom
Beobachter existiert. Damit fällt in 3.9(c) die Zelle H auch weg. Die Laufzeit dieser

AlgoCG 09

42

HEINZ NIXDORF INSTITUT

Occlusion Culling mit Potentially Visible Sets

HEINZ NIXDORF INSTITUT

!"#$%&'#()(*+,-%&./&"
Occlusion
Culling mit Potentially Visible Sets
012/&#(34%"*5"-*6/471%8#()(

Eye-to-Cell Visibility - 3

!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

Eye-to-Cell Visibility - 4

9%1:3%*;%11%"*-%'*<(,.(&%%*'#"-*'#:3(.,&=
C

>%&':3#%-%"% ?@21#:3A%#(%"B
>%&':3#%-%"%*?@21#:3A%#(%"B

Kapitel 3. Visibility Culling

!"#$#%&'()#*+",*-./,01,#&,
9

?

'5:3% $/" ; #" < -#% =%11%" -#% >.%& +/&(,1%
E'5:3%*$/"*;*#"*<*-#%*=%11%"@*-#%*>.%&*+/&(,1%*
%&&%#:3.,&*'#"-*5"-*#4*A&5'(54*1#%2%"
F

C

G

D
Methode ist O(|V | · |S|),9 wobei
V Länge der Portalsequenzen beschreibtB (maximal
alle
A
B@*C*D,11%"*#"*EFG*H%(I(*IJ,&*J%2@*
S
Zellen
hintereinander)
undO,.%&*C*.1%#.(*#"*E?G@*/.J/31*5"'#:3(.,&
S Visible
dieQ Anzahl
Stabtree.
HEINZim
NIXDORF
INSTITUT
7&HI%*J%-%*%#"K%1"%*;%11%*4#(*<:3"#((*-%'*F&5'(54
Occlusion
Culling mit Potentially
Sets der Pfade

G

!"#$%&'#()(*+,-%&./&"
Visibility - 4
L" MCN I,11%" OP FP Q R%2 Eye-to-Cell
L"*MCN*I,11%"*OP*FP*Q*R%2
012/&#(34%"*5"-*6/471%8#()(

!"##"$%"&% '(% )*+&%+'
!"##"$%"&%,'(%,)*+&%+'

ially Visible Sets

HEINZ NIXDORF INSTITUT

!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

K

2 3,
2603,#*#7#8,.8(#11*4"&"51",7
,
11 4" "51",
G DP*E*.1%#.%"*/.R/31*'#%*5"'#:3(.,&*'#"!"#$#%&'()#*+",*-./,01,#&,
'#:3(.,&=
9
7&>D%*D>&*-#%*%&&%#:3.,&%"*+/&(,1'%M5%"I%"@*/.*
?
T
9 '5:3%*$/"*;*#"*<*-#%*=%11%"@*-#%*>.%&*+/&(,1%*
'5:3% $/" ; #" < -#% =%11%" -#%%#"%*<#:3(1#"#%*$/4*N%(&,:3(%&*%8#'(#%&(
>.%& +/&(,1%
C
%&&%#:3.,&*'#"-*5"-*#4*A&5'(54*1#%2%"
-("."$&+/0",'(%,!"##"$%"&%
C
E
E
9 C*D)11(*#"*E?G*H%(I(*,5:3*J%2
A
F
F
9 D B@*C*D,11%"*#"*EFG*H%(I(*IJ,&*J%2@*
B
D
G IH3&%*U#%I%"'5:3% $/"*S*#"*<*-5&:3
,.%&*C*.1%#.(*#"*E?G@*/.J/31*5"'#:3(.,&
G 4#(*-%&*0..&5:3.%-#"25"2P*-,''*,11%*(&,$%&'#%&(%"*
;
S
S
K
O
O
*<:3"#((*-%'*F&5'(54
;%11%"*#4*F&5'(54*1#%2%"
Q
L
Q

2 3,
2603,#*#7#8,.8(#11*4"&"51",7
,
11 4" "51",
D*5"-*E*I,11%"*#"*MCN*,5:3*R%2P
(a)
(b)
,.%&*DP*E*.1%#.(*#"*MTN*/.R/31*5"'#:3(.,&
:3(.,&*'#"9 7&>D%*D>&*-#%*%&&%#:3.,&%"*+/&(,1'%M5%"I%"@*/.*
?,((3#,'*F#':3%&
>/&1%'5"2*X012/&#(34%"*#"*-%&*Y/475(%&2&,I#AZP*<<*TWW[
%#"%*<#:3(1#"#%*$/4*N%(&,:3(%&*%8#'(#%&(
T
G

<*-5&:3

-,''*,11%*(&,$%&'#%&(%"*

%2P
31*5"'#:3(.,&

2&,I#AZP*<<*TWW[

;

O
C
B

A

K

(c)
VW

L

L

(d)

O

P,((3#,'*A#':3%&

C
3.9: Vier Methoden für die Berechnung
der Eye-to-cell visibility.
9 Abbildung
C*D)11(*#"*E?G*H%(I(*,5:3*J%2
R/&1%'5"2*S012/&#(34%"*#"*-%&*T/475(%&2&,D#UV@*<<*FWWX

B

E

;

OQ

A

F

D

;
K
In praktischen Anwendungen wird man sich wahrscheinlich
L für Variante 2 oder 3 entscheiS
O
Q
den, da hier das
Verhältnis von Laufzeit zu Nutzen am besten ist. Bei sehr komplexer Geometrie in jedem Raum kann sich der zusätzliche Aufwand für die exakte Eye-To-Cell Visibility
Bestimmung jedoch auszahlen.
?,((3#,'*F#':3%&

R/&1%'5"2*S012/&#(34%"*#"*-%&*T/475(%&2&,D#UV@*<<*FWWX

VW

P,((3#,'*A#':3%&

OQ

3.2.5 Objekte in Räumen
Die Einrichtung einer Zelle (z.B. Stühle, Tische, Schränke, etc.) wird zusammen mit der Zelle
gerendert und geht nicht in die Sichtbarkeitsberechnung mit ein.

3.3 Dynamische Berechnung von Potentially Visible
Sets (PVS)
Das Ziel ist eine dynamische, sichtpunktabhängige Berechnung der PVS zur Laufzeit während
des Walkthrough. Dadurch wird es möglich, durchsichtige Bereiche während des Walkthrough
zu verschieben. Für die Berechnung wird zunächst eine räumliche Aufteilung mit einem BSPBaum in Zellen und Portale durchgeführt und anschließend eine sichtpunktabhängige Berechnung der PVS durchgeführt.
Die Idee besteht darin, die Zelle des Betrachters zu rendern und von dort ausgehend nur
doch die Zellen, die durch Portale zu sehen sind. Algorithmus 13 beschreibt das Vorgehen zur
Berechnung der PVS. Abbildung 3.10 zeigt ein Beispiel.
Die rote Cullbox geht vom Standpunkt des Beobachters aus. In dieser Box liegen nur die
Portale zu den Zellen C und F, d.h. D wird nicht gerendert. Der Schnitt der Cullbox mit
den Portalen ergibt die blauen Cullboxen. Innerhalb dieser Boxen liegt nur das Portal zu H,
weshalb die Boxen B und G unsichtbar sind. Der nächste Schnitt des blauen Kegels mit dem
Portal F-H erzeugt die grüne Cullbox.

AlgoCG 09

43

Kapitel 3. Visibility Culling

Algorithmus 13 Algorithmus zur dynamischen PVS Berechnung
1: function DYN PVS
2:
Bestimme die Zelle V des Betrachters
3:
Initialisiere eine 2-dimensionale Boundingbox P in der Größe des Bildschirms.
4:
Rendere die Geometrie der Zelle V , führe dabei Frustum Culling durch, wobei die
Spitze des Frustum vom Betrachter zum Rechteck P geht.
5:
Verfahre rekursiv für alle Nachbarn der Zelle V .
6:
for all Portal der aktuellen Zelle V do
7:
Projiziere das Portal auf den Schirm und bestimme die Boundingbox BB der Projektion.
8:
Bestimme die Schnittmenge von P und BB.
9:
for all Schnittmenge von P und BB. do
10:
if Schnittmenge leer then
11:
Benachbartes Portal unsichtbar
12:
else
13:
Führe Culling der Nachbarzelle mit Frustum durch, das durch die Schnittmenge begrenzt ist.
14:
end if
15:
Falls die Schnittmenge nicht leer war, können die Nachbarn sichtbar sein.
Setze P := Schnittmenge von P und BB und fahre rekursiv in Schritt 3 fort.
16:
end for
17:
end for
18: end function
HEINZ NIXDORF INSTITUT

Dynamische Berechnung von PVS

!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

Berechnungsbeispiel - 6
!"#$%#"&
9 - : 11. ; < # = - 3
9"*-%&*:511./8*;?<*#'(*=%-/@3*
-,'*+/&(,1*A5*>*A5*'%3%"B

<

;

>
C

D,&54*E#&-*F%11%*>*2%&%"-%&(

:

D

0

G

Abbildung 3.10: Dynamische Berechnung der PVS.
K/&1%'5"2*L012/&#(34%"*#"*-%&*:/475(%&2&,M#NOP*QQ*RSSJ

AlgoCG 09

H,((3#,'*<#'@3%&

IJ

44

Kapitel 3. Visibility Culling

3.4 Hierarchischer Z-Buffer

Die bisher vorgestellten Occlusion Techniken über PVS eignen sich gut für Szenen in Gebäuden. Für Waldszenen, sich bewegende Menschmassen oder anderes, offenes Gelände eignen
sie sich jedoch nicht. Unter den Annahme, dass Zweige, Blätter und Nadeln der Bäume ausmodelliert sind, erhält man einen großen Occluder, der aus sehr vielen kleinen, jeweils wenig verdeckenden Objekten besteht. Man spricht dabei auch von aggregierter Verdeckung.
Hier lassen sich Zellen mit beschränkter Sichtbarkeit nur sehr schlecht bilden und der Stabtree
würde sehr groß.
Der hierarchische Z-Buffer ist ein weiterer Occlusion Culling Algorithmus. Die Idee ist,
von vorne nach hinten zu rendern und alles was verdeckt ist, nicht zu zeichnen. Dabei geht das
Verfahren konservativ vor, d.h. jedes sichtbare Dreieck wird auch garantiert gezeichnet. Das
Ziel ist, die Redundanzen bei der Sichtbarkeitsabfrage (Abfrage der Z-Werte) zu reduzieren
und die Redundanzen bei der Darstellung von HEINZ
verdeckten
Dreiecken
NIXDORF
INSTITUT zu reduzieren.
rchischer Z-Buffer
!"#$%&'#()(*+,-%&./&"
012/&#(34%"*5"-*6/471%8#()(

3.4.1 Grundideen

%"&'$%()**"&+,--".&/)(&01($%2,%(".3

Im klassischen Z-Buffer Algorithmus wird die Sichtbarkeit für jeweils ein Pixel gelöst. Dabei

5'
5'*:%(&,;3(%&'#;3(*$/"*$/&"%*",;3*3#"(%"*&%"-%&"=
:%(&,;3(%&'#;3(
$/" $/&"%
",;3
3#"(%"
werden
auch die
Pixel
von &%"-%&"
Objekten bzw. Gruppen von Objekten betrachtet, die vollständig

hinter einem anderen Objekt liegen. In Abbildung 3.11 werden die Smileys komplett von
%&%;3"%"=*?@,""*%#"*A.B%C(*$%&-%;C(*#'(D=
dem Zylinder verdeckt, da der tiefste Z-Wert des Zylinders näher am Betrachter liegt als der

"%*%#"F#2%
"%
%#"F#2% 0.G&,2%*GH&*4I21#;3'(
0.G&,2%
GH& 4I21#;3'(
A.B%C(%
A.B%C(%*
naheste
Z-Wert der$#%1%
Smileys.
5&;3GH3&%"

.%&%#('
2%F%#;3"%(
2

.B%C(*#'(*2%",5*-,""*$%&-%;C(=*@%""*'%#"*4#"#4,1%&*
(*2&IN%&*#'(*,1'*-%&*4,8#4,1%*KLM%&(*.%&%#('*
;3"%(%&*A.B%C(%
B

"/;3*F5
F%#;3"%"

F4,8*
P
Q
4,8 OOKP1#"-%&Q
F4#"*OY4#1%P2&577%Q
U/&1%'5"2*V012/&#(34%"*#"*-%&*W/475(%&2&,G#CX=*YY*>ZZ[

R,((3#,'*S#';3%&

TE

Abbildung 3.11: Vollständige Verdeckung von Objekten durch ein größeres Objekt.
Man rendert nun von vorne nach hinten um schnell abfragen zu können, ob Objekte von bereits gezeichneten Objekten verdeckt werden. Ein Objekt ist genau dann verdeckt, wenn sein
minimaler Z-Wert größer ist als der maximale Z-Wert bereits gezeichneter Objekte. Um die
Berechnung effizienter als den normalen Z-Buffer Algorithmus zu machen, wird eine solche
Abfrage immer für eine Menge von Objekten auf einmal durchgeführt. Dazu wird ein Octree

AlgoCG 09

45

Kapitel 3. Visibility Culling
HEINZ NIXDORF INSTITUT

rchischer Z-Buffer

!"#$%&'#()(*+,-%&./&"

est

für die Szene aufgebaut, der die einzelnen Dreiecke enthält.
Ein Dreieck wird so tief wie mög012/&#(34%"*5"-*6/471%8#()(
lich einsortiert. Das Vorgehen im Paper speichert kleine Dreiecke, die auf den Sticky-Planes
zwischen großen Oktanten hängen bleiben, mehrfach in allen geschnitteten Oktanten. Dabei
%&$'&
enthält eine Octree-Box höchstens k Dreiecke. Passt ein Dreieck nicht in eines der 8 Kinder,
wird es im Elternknoten gespeichert.
Anstatt die Sichtbarkeit einzelner Dreiecke zu testen wird immer die ganze Box auf ihre
3&%"*%#"%*%1%4%"(,&%*<%'(/7%&,(#/"*%#"=
Sichtbarkeits geprüft. Dazu werden die Flächen der BoundingBox genutzt. Falls die Box unist, sind auch alleA/5"-#"2./8
Objekte in der Box und in allen Kindern unsichtbar. Der entschei?%2%.%" #'( sichtbar
?%2%.%"*#'(*%#"%*,@3'%"7,&,11%1%*A/5"-#"2./8*
%#"% ,@3'%"7,&,11%1%
dende
Faktor
für
die
Laufzeit
ist die Anzahl der Elemente, die unterhalb einer Box im OcBAA/8C
tree hängen. Der Test
Boundingbox
darf nicht länger dauern als das Rendern der Objekte
HEINZ der
NIXDORF
INSTITUT
!"#$%&'#()(*+,-%&./&"
+&;:%*#4*A#1-&,54D*/.*<%#1%*-%&*A/8*'#@3(.,&*'#"unterhalb der Box. 012/&#(34%"*5"-*6/471%8#()(
Sonst
würde sich der Test nicht mehr lohnen.
Die Testoperation prüft für eine achsenparallele Boundingbox, ob Teile von ihr im Bildraum
sichtbar sind wie in Abbildung 3.12 dargestellt.
$Funktion !"%&'(&)(*$!!"%$++,

f
*++$-)($-.$!-#/012.$)-34(+10,
%'(/7%&,(#/"*%#"=
0&(20'$(02&
'%"7,&,11%1%
'%"7,&,11%1%*A/5"-#"2./8*
A/5"-#"2./8

lse

*<%#1%*-%&*A/8*'#@3(.,&*'#"0&(20'$51#)&
(a)

)(*$!!"%$++,

(b)

012.$)-34(+10,

Abbildung 3.12: Prüfe für eine achsenparallele Boundingbox ob Teile von ihr unsichtbar sind.
E,((3#,'*F#'@3%&

I/&1%'5"2*J012/&#(34%"*#"*-%&*K/475(%&2&,:#LMD*NN*OPPH

GH

Mögliche Verfahren zur Durchführung des Boxentests sind die folgenden:
• Die Boundingbox kann aus 6 × 2 Dreiecken modelliert werden (2 Dreiecke pro Seite).
Man kann nun die Boundingbox in einem extra Puffer rendern und prüfen, wie viele
Pixel sichtbar sind.
E,((3#,'*F#'@3%&

K/475(%&2&,:#LMD*NN*OPPH

GH

• Projiziere die 8 Eckpunkte der Boundingbox in den Bildraum und berechne davon im
Bildraum die 2D Boundingbox.
• Unterstütze die Operation in spezieller Hardware.
Man prüft dann Pixelweise für die Z-Werte der Boundingbox gegen den Z-Buffer. Falls
alle Werte des Z-Buffers größer sind, ist die Box unsichtbar. Der Nachteil dieses Verfahrens
ist, dass Kosten in Größe der projizierten Box entstehen (in Anzahl der Pixel). Dies ist insbesondere für große Boxen ineffizient. Man verwendet daher die im nachfolgenden Abschnitt
vorgestellte Z-Pyramide.

3.4.2 Z-Pyramide
Die Z-Pyramide bildet eine Hierarchie von Z-Werten. Auf der untersten Ebene hat man die
Werte des normalen Z-Buffers. Für die nächst höhere Ebene werden jeweils vier benachbarte

AlgoCG 09

46