Occlusion Culling for Real-Time Rendering of Urban Environments

Abstract

Diese Dissertation besch¨aftigt sich mit der Visualisierung von dreidimensionalen Stadtmodellen f¨ur Anwendungen wie Stadtplanung und Fahrsimulation. F¨ur eine Simulation ist es wichtig, daß ein Benutzer interaktiv in der Stadt navigieren kann. Dabei versucht man, wie bei einem Film, den Eindruck einer fl¨ussigen Bewegung zu erzeugen. Um dieses Ziel zu erreichen, ist es notwendig, mehrere Bilder pro Sekunde auf einem graphischen Ausgabeger¨at, wie einem Monitor, darzustellen. Die großen Datenmengen, die f¨ur die Visualisierung eines Stadtmodells verarbeitet werden m¨ussen, machen Beschleunigungsverfahren notwendig, um gen¨ugend Bilder pro Sekunde anzeigen zu k¨onnen. Der Beitrag dieser Dissertation sind neue Verfahren der Sichtbarkeitsberechnung, um schnell diejenigen Teile des Stadtmodells zu finden, die von weiter vorne liegenden Teilen verdeckt werden. Die verdeckten Teile liefern keinen Beitrag zu dem erstellten Bild und m¨ussen deshalb nicht von der Graphikhardware weiterverarbeitet werden. Die erzielten Geschwindigkeitsverbesserungen der Darstellung sind in der Gr¨oßenordnung von zehn bis hundertfacher Beschleunigung f¨ur die verwendeten Testszenen. Es werden drei neue Algorithmen vorgestellt: Der erste Algorithmus berechnet die Sichtbarkeit f¨ur jedes neue Bild in einer Simulation. Der Algorithmus berechnet eine konservative Absch¨atzung der Objekte, die vom aktuellen Blickpunkt sichtbar sind, ohne dabei sichtbare Objekte als unsichtbar zu klassifizieren. Einige wenige unsichtbare Objekte k¨onnen allerdings als sichtbar klassifiziert werden. F¨ur die Sichtbarkeitsberechnung wird mit Unterst¨utzung von Graphikhardware ein Bild gezeichnet, das die Sichtbarkeitsinformation codiert. Mit Hilfe dieses Bildes kann man f¨ur Szenenteile schnell feststellen, ob sie unsichtbar sind. Der zweite Algorithmus verwendet Vorberechnungen f¨ur die Sichtbarkeit. Die Szene wird in viele Regionen unterteilt, f¨ur die jeweils eine Liste von sichtbaren Objekten bestimmt wird. Im Gegensatz zum ersten Algorithmus wird aber die Sichtbarkeit von einer Region und nicht von einem Punkt ausgerechnet. Bekannte analytische Verfahren f¨ur dieses Problem sind instabil und zu zeitaufwendig f¨ur gr¨oßere Szenen. Das vorgeschlagene Verfahren zeigt, wie man diese komplexen Berechnungen mit Hilfe von Graphikhardware effizient approximieren kann. Der dritte Algorithmus ist die Grundlage f¨ur ein System, bei dem die Sichtbarkeitsberechnungen paralell zur Darstellung durchgef¨uhrt werden k¨onnen. Diese k¨onnen somit auf einem anderen Rechner, einem Server, ausgef¨uhrt werden, der das Ergebnis der Sichtbarkeitsberechnung dann ¨uber das Netzwerk kommuniziert. Dieses paralelle Verfahren erlaubt es, ohne Vorberechnungen schnelle Simulationen zu erstellen. - This thesis makes a contribution to the field of three-dimensional visualization of urban environments, for applications like urban planning and driving simulation. In a simulation system a user interactively navigates through virtual cities in real-time. To give the impression of fluid motion, high frame rates are necessary, and new images have to be rendered several times each second. To cope with the large amounts of data, acceleration algorithms have to be used to sustain high frame rates. The contributions of this thesis are new algorithms for occlusion culling, that is to quickly identify parts of the scene that are occluded by other objects. These parts are invisible and therefore do not need to be sent to the graphics hardware. This thesis contains three new algorithms: The first algorithm calculates occlusion culling online for each frame of a walkthrough. The algorithm computes a tight superset of objects that are visible from the current viewpoint. Graphics hardware is exploited to be able to combine a large number of occluders. In contrast to other approaches, an occlusion map is calculated using an orthographic projection to obtain smaller algorithm calculation times. The second algorithm precalculates visibility. The scene is discretized into view cells for which cellto- object visibility is precomputed, making online overhead negligible. This requires the calculation of occlusion from a region in space. The occlusion boundaries from a region are complex, and analytical computation methods are not very robust and do not scale to the large scenes we envision. We demonstrate how to approximate those complex occlusion boundaries using simple point sampling and occluder shrinking. This approximation is conservative and accurate in finding all significant occlusion and occluder interactions. The third algorithm calculates occlusion in parallel to the rendering pipeline. We show how to use point visibility algorithms to quickly calculate a tight potentially visible set which is valid for several frames, by shrinking the occluders by an adequate amount. These visibility calculations can be performed on a visibility server, possibly a distinct computer communicating with the display host over a local network. The resulting system essentially combines the advantages of online visibility processing and region-based visibility calculations, in that it is based on a simple online visibility algorithm, while calculating a visibility solution that remains valid for a sufficiently large region of space.