Sichtbarkeitsberechnungen mit dem Visibility Skeleton

Diplomarbeit von Serdal Kaya

Einleitung:

Mit zunehmender Leistung der zur Verfügung stehenden Hardware steigen auch die Erwartungen bei 3D-Grafik-Anwendungen - egal ob es darum geht animierte Sequenzen in Filme einzubauen oder gar ganze Filme mithilfe von Computern zu erstellen, Web-Basierte Wanderungen durch dynamische Welten zur Verfügung zu stellen oder aktionsreiche Spiele zu spielen - schneller und realitätsnäher lautet die stets gleiche Devise. Die Geschwindigkeit und die Realitätsnähe ist auch vielen ein Maßstab zur Messung der Qualität von 3D-Anwendnungen. Realitätsnähe kann in erster Linie dadurch erreicht werden, indem noch detailliertere Informationen in den Erstellungsprozess mit einfließen. Geschwindigkeit kann hingegen dadurch erreicht werden, indem die Informationen für den Erstellungsprozess effizient zur Verfügung gestellt werden. Sowohl Geschwindigkeit als auch die Realitätsnähe hängt in 3D-Grafik-Anwendungen zum großen Teil von Sichtbarkeit und deren Berechnung ab.

Wenn z.B. realitätsnahe Filmsequenzen generiert werden sollen, so ist man darauf angewiesen, dass Licht- und Schattenverläufe detailliert wiedergegeben werden um den Realitätseindruck zu erhöhen, Licht- und Schattenverläufe hängen aber größtenteils von Sichtbarkeitseigenschaften ab. Oder wenn in einer Web-Anwendung in Echtzeit gewandert werden soll, so ist es erforderlich, dass ein schneller Zugriff auf Sichtbarkeitsinformationen ermöglicht wird, da sich bei Bewegungen die relative Sichtbarkeit der Objekte zum Betrachter ständig ändert.

Gang der Untersuchung:

Diese Arbeit beschäftigt sich mit dem Visibility Skeleton, einer Datenstruktur, die in [DDP97] eingeführt wurde. In erster Linie dient das Visibility Skeleton der Modellierung von Sichtbarkeitsinformation. Bevor das Visibility Skeleton beschrieben wird, werde ich zunächst in Kapitel 2 auf die Grundlagen dieser Arbeit eingehen. Hierzu werden allgemeine Grundlagen zur 3D-Grafik eingeführt und verschiedene Themen - wie z.B. Sichtbarkeit, Radiosity-Verfahren und Plücker-Koordinaten - auf die diese Arbeit beruht, diskutiert. In Kapitel 3 wird dann das Visibility Skeleton in der von mit implementierten Form beschrieben, dabei werden die grundlegenden Elemente des Visibility Skeletons sowie die verwendete Datenstruktur erklärt. Eine detaillierte Beschreibung der Implementierung und die dabei aufgetretenen Probleme werden ebenfalls Thema dieses Kapitels sein. In Kapitel 4 werden einige Messwerte vorgestellt und in Kapitel 5 findet dann eine zusammenfassende Diskussion und ein Ausblick statt.

Die in der Studie erwähnte CD ist nicht im Lieferumfang enthalten, da sie für das Verständnis der Studie nicht notwendig ist.

Inhaltsverzeichnis:

	ABBILDUNGSVERZEICHNIS	I
	FORMELVERZEICHNIS	III
	TABELLENVERZEICH	IV
	SYMBOLVERZEICHNIS	V
1.	EINLEITUNG	1
2.	GRUNDLAGEN	2
2.1	GRUNDBEGRIFFE UND VORAUSSETZUNGEN	2
2.2	RADIOSITY	3
2.3	SICHTBARKEIT	11
2.3.1	Lokale Sicht	12
2.3.2	Globale Sicht	21
2.4	PLÜCKER-KOORDINATEN	23
3.	VISIBILITY SKELETON	28
3.1	ALLGEMEINES	28
3.2	DATENSTRUKTUR	31
3.3	DIE KANTEN (SICHTBARKEITSWECHSEL)	35
3.3.1	VE-Kante	36
3.3.2	FE-Kante	37
3.3.3	Fv-Kante	38
3.3.4	EEE-Kante	39
3.3.5	Die Ordnung auf den Generator AVL-Bäumen	39
3.4	DIE KNOTEN (ESL)	41
3.4.1	Triviale Knot	41
3.4.2	Semi-Triviale Knoten	42
3.4.3	Non-Triviale Knoten	42
3.5	DER AUFBAU DES VISIBILITY SKELETONS	42
3.5.1	Voraussetzungen	43
3.6	TRIVIALE KNOTEN	44
3.6.1	VV-Knoten	44
3.6.2	Fvv-Knoten	53
3.6.3	E-Knoten	59
3.6.4	FvE-Knoten	62
3.7	SEMI-TRIVIALE KNOTEN	69
3.7.1	VEE-Knoten	69
3.7.2	EVE-Knoten	74
3.7.3	FF-Knoten	76
3.7.4	FEE-Knoten	78
3.7.5	EFE-Knoten	81
3.8	NON-TRIVIALE	83
3.8.1	E4-Knoten	83
3.9	OFFENE PROBLEME	85
4.	MESSUNGEN UND ERGEBNISSE	88
4.1	MESSWERTE	88
5.	ZUSAMMENFASSUNG UND AUSBLICK	91
	ERKLÄRUNG	93
	CD-ROM INHALT	94
	PROGRAMMBESCHREIBUNG GLOVE V0.3	95
	LITERATUR	96