Hardware-assisted occlusion culling for scene graph systems

Abstract

This thesis describes different aspects of occlusion culling algorithms for the efficient rendering of 3D scenes with rasterization hardware. Scene graphs are used as data structures for the scenes to support a wide range of different applications. All presented algorithms permit modifications of the graphs at runtime and therefore the algorithms are suitable for dynamic scenes.

The thesis consists of three parts. The first part compares different techniques to determine the visibility of a single scene graph node. All techniques have the same characteristic in that they utilize the depth information on the graphics hardware in some way. Unfortunately, each access to the hardware requires some latency. Therefore the second part of this thesis presents some algorithms to reduce the number of these accesses to the graphics hardware. The algorithms take advantage of a lower resolution representation of the scene graph nodes in screen-space on the one hand, and they also use the informations of previous occlusion queries on the other. Because all the presented algorithms use the depth values of the currently rendered scene, the order of the rendering and the occlusion tests is important. Hence the third part of this thesis presents a novel algorithm for the traversal of a scene graph which efficiently utilizes hardware occlusion queries. Therefore the algorithm uses screen-space coherence in combination with a front-to-back sorted traversal of the scene graph in object-space. To determine the occlusion, the algorithm bundles individual occlusion tests in multiple occlusion queries. These can be asynchronously performed to reduce the latency.

All presented algorithms deliberately do not use special -- spatial -- data structures for the scene to avoid long preprocessing times or restrictions in the use of dynamic scenes. Also, the algorithms do not exploit temporal coherence between the frames, because this results in limitations for dynamic and interactive scenes. However, the presented algorithms admit an efficient rendering of scenes with high depth complexity.

Die vorliegende Arbeit behandelt verschiedene Aspekte der Verdeckungsrechnung zur effizienteren Darstellung dreidimensionaler Szenen mit Hilfe von Rasterisierungshardware. Alle betrachteten Algorithmen verwenden einen herkömmlichen Szenegraphen als grundlegende Datenstruktur. Dadurch lassen sie sich unmittelbar zahlreichen Anwendungen zur Verfügung stellen. Alle Algorithmen erlauben es, den Szenegraphen zur Laufzeit zu modifizieren, und lassen sich somit auch auf dynamische Szenen anwenden.

Die Arbeit teilt sich auf in drei Bereiche. Im ersten Abschnitt wird auf die verschiedenen Möglichkeiten eingegangen, die Verdeckung eines einzelnen Knotens aus dem Szenegraphen zu ermitteln. Die vorgestellten Algorithmen implementieren dabei verschiedene Methoden, um die auf der Graphikhardware gespeicherte Tiefeninformation auszunutzen. Allerdings benötigt jeder Zugriff auf die Graphikhardware eine kurze Zeitspanne. Der zweite Abschnitt beschäftigt sich daher damit, Zugriffe auf die Hardware zu reduzieren. Dabei wird einerseits eine vereinfachte Repräsentation der Szenengraphknoten im Bildraum und andererseits die Informationen von bereits durchgeführten Verdeckungstests verwendet. Da alle vorgestellten Algorithmen in irgendeiner Form von den Tiefenwerten von bereits gezeichneten Teilen der Szene abhängen, ist die Reihenfolge der Darstellung und der Verdeckungstests von zentraler Bedeutung. Im dritten Teil der Arbeit wird daher ein neuer Traversierungsalgorithmus für den Szenengraphen vorgestellt, der die von der Graphikhardware zur Verfügung gestellten Verdeckungstests besonders effizient ausnutzen kann. Dazu sucht der Algorithmus nach Kohärenzen im Bildraum in Kombination mit einer sortierten Traversierung der Knoten im Objektraum. Um letztendlich die Verdeckung eines Objekts zu bestimmen, bündelt der Algorithmus die Verdeckungstests in Mehrfachanfragen, die es erlauben, mehrere unabhängige Verdeckungstests asynchron durchzuführen.

Ganz bewusst wurde auf die Verwendung von speziellen -- räumlichen -- Datenstrukturen für die Szene verzichtet, um lange Vorberechnungszeiten oder Einschränkungen für dynamische Szenen zu vermeiden. Ebenso wurde darauf verzichtet, zeitliche Kohärenz zwischen einzelnen Bildfolgen auszunutzen, da dies Einschränkungen für interaktive Szenen zur Folge hätte. Gleichwohl erlauben die vorgestellten Algorithmen eine effiziente Darstellung beliebiger Szenen mit hoher Tiefenkomplexität.