Institut für Informatik
	Michael Kortenjan

Michael Kortenjan:
Potentially Visible Sets

Betreuer: Prof. Dr. Oliver Vornberger

Zweitgutachter: Prof. Dr. Volker Sperschneider

Eine der Aufgaben der Computergraphik besteht in der Darstellung dreimensionaler Szenen. Die Komplextät dieser Aufgabe hängt dabei wesentlich von der Anzahl der darzustellenden Polygoneab . Durch Potentially Visible Sets können große Teile einer Szene als nicht sichtbar klassifiziert und damit die Anzahl der zu verarbeitenden Polygone deutlich reduziert werden. Diese Technik ist besonders gut anwendbar auf statische Szenen mit beschränkten Sichtweiten, wie etwa das innere von Gebäuden.

Dazu wird im ersten Schritt eine räumliche Unterteilung der Szene in Zellen erstellt. Danach werden Nachbarschaften zwischen den Zellen bestimmt und für nebeneinander liegende Zellen berechnet, wo diese nicht durch Polygone voneinander getrennt werden. Auf den Zellen entsteht so eine Graphenstruktur, in der zwischen zwei Zellen eine Kante besteht, falls sie zueinander benachbart sind und von einer Zelle aus die andere sichtbar ist. Durch eine Tiefensuche werden ausgehend von jeder Zelle die von ihr sichtbaren anderen Zellen festgestellt.

Da die Szene statisch ist kann die muss die Sichtbarkeit nicht zur Laufzeit berechnet werden, sondern läßt sich bereits vorher berechnet werden. Deshalb kann ein erhöhter Rechenaufwand für die Berechnungen in Kauf genommen werden. Zur Laufzeit muß nur festgestellt werden, in welcher Zelle sich der Standpunkt des Betrachters befindet, was durch die Art der Organisierung der räumlichen Unterteilung leicht möglich ist.

Das Ergebnis läßt sich nicht nur verwenden, um die Darstellung zu beschleunigen, sondern bietet noch weitere Möglichkeiten. Schon durch die räumliche Untereilung lassen sich Polygone in der Nähe einer gegebenen Position schnell auffinden. Dies kann zur effizienten Kollisionsabfrage genutzt werden. Da die Sichtbarkeit auf der Ebene der Zellen und nicht ausgehend von der exakten Position berechnet wird und die Nachbarschaftsbetuiehungen unter den Zellen bekannt ist, kann auch festgestellt werden, welche Teile der Szene als nächste sichtbar werden könnten. Bei Szenen, die nicht komplett in den Speicher geladen werden können, lassen sich wahrscheinlich die als nächstes benötigten Informationen schon im Vorraus identifizieren und laden.

Email: mkortenj@uos.de