Visibility computations for real-time rendering in general 3D environments

Abstract

Sichtbarkeitsberechnungen sind essentielle Verfahren im Bereich der Computergrafik, notwendig für verschnellerte Darstellung in der Form von Visibility Culling, wie auch für realistische Beleuchtung.<br />Visibility Culling, das den Hauptfokus dieser Arbeit darstellt, ist eine Technik die Ouput-Sensitivität erreichen will, indem nur die sichtbaren Primitive zur Grafikkarte gesandt werden. Trotz der rasanten Entwicklung der Grafikkarten ist Visibility Culling von großer Bedeutung für viele Applikationen, wie Spieleprogrammierung oder Architektur-Design, weil auch die Szenekomplexität entsprechend anwächst. Das Lösen des Sichtbarkeitsproblems war über viele Jahre hinweg ein wichtiges Thema, und unzählige Methoden wurden vorgeschlagen. Interessanterweise gibt es trotzdem immer noch offene Probleme wissenschaftlicher Art, und viele Algorithmen sind entweder unpraktisch oder nur verwendbar für bestimmte Szenenkonfigurationen, wodurch ihre weitläufige Verbreitung verhindert wurde. Sichtbarkeitsberechnungen werden auch benötigt um komplexe Lichtinteraktionen in der Szene zu lösen, von weichen und harten Schatten bis zu Ambient Occlusion und voller Globalen Beleuchtung. Es ist eine riesige Herausforderung, hunderte bis tausende Visibilityanfragen im Bruchteil einer Sekunde zu beantworten um Echtzeit-Laufzeiten zu erreichen. Jenes zu schaffen ist ein Ziel dieser Arbeit.<br />Der Beitrag dieser Arbeit sind vier neue Algorithmen, die Lösungen für effiziente Sichtbarkeits-Interaktionen anbieten um Ausgabe-sensitive Echtzeitdarstellung in hoher Qualität zu erreichen, und generell sind im Sinne daß sie mit jeder Art von 3D Szenenkonfiguration funktionieren.<br />Als erstes präsentieren wir zwei Methoden, die sich mit dem Problem beschäftigen, eine automatische Aufteilungen des Sichtraums beziehungsweise Objektraums in sinnvolle Entitäten zu erzeugen, die optimal ist für das nachfolgende Rendering. Interessanterweise wurde dieses Problem trotz seiner Wichtigkeit fast ignoriert, und Sichtzellen werden in der Praxis meistens manuell angepaßt, um optimale Geschwindigkeit zu erreichen - eine sehr zeitaufwendige Tätigkeit. Der erste Algorithmus beschäftigt sich speziell mit der Erzeugung einer optimalen Sichtraum-Aufteilung in Sichtzellen unter Benutzung von einer Kostenheuristik und spärlicher Abtastung. Der zweite Algorithmus erweitert diesen Ansatz, um eine gleichzeitige Optimierung sowohl vom Sicht- als auch vom Objektraum durchzuführen. Danach präsentieren wir einen Algorithmus, der hierarchisches Occlusion Culling zur Laufzeit ohne die Limitierungen von früheren Methoden ausführt, und sich gut in eine Rendering Engine einpaßt im Sinne daß er leicht zu integrieren ist und effizientes Material-Sortieren erlaubt. Der Algorithmus reduziert das Hauptproblem von den Vorgängermethoden - nämlich die Mehrkosten des Algorithmus durch viele teure Statuswechsel auf der Hardware und durch redundante hardware-basierte Sichtbarkeitsanfragen - auf ein Minimum. Als letztes präsentieren wir einen Ambient Occlusion Algorithmus im Bildschirmraum, und zeigen daß unter Ausnutzung von zeitlicher Koherenz Schattieren in hoher Qualität mit effektiv hunderten von Abtastungen pro Pixel sowohl für statische als auch für dynamische Szenen in Echtzeit möglich ist, indem man Resultate von alten Frames wiederverwendet.<br />

Visibility computations are essential operations in computer graphics, which are required for rendering acceleration in the form of visibility culling, as well as for computing realistic lighting.<br />Visibility culling, which is the main focus of this thesis, aims to provide output sensitivity by sending only visible primitives to the hardware. Regardless of the rapid development of graphics hardware, it is of crucial importance for many applications like game development or architectural design, as the demands on the hardware regarding scene complexity increase accordingly.<br />Solving the visibility problem has been an important research topic for many years, and countless methods have been proposed. Interestingly, there are still open research problems up to this day, and many algorithms are either impractical or only usable for specific scene configurations, preventing their widespread use. Visibility culling algorithms can be separated into algorithms for visibility preprocessing and online occlusion culling. Visibility computations are also required to solve complex lighting interactions in the scene, ranging from soft and hard shadows to ambient occlusion and full fledged global illumination. It is a big challenge to answer hundreds or thousands of visibility queries within a fraction of a second in order to reach real-time frame rates, which is one goal that we want to achieve in this thesis.<br />The contribution of this thesis are four novel algorithms that provide solutions for efficient visibility interactions in order to achieve high-quality output-sensitive real-time rendering, and are general in the sense that they work with any kind of 3D scene configuration. First we present two methods dealing with the issue of automatically partitioning view space and object space into useful entities that are optimal for the subsequent visibility computations. Amazingly, this problem area was mostly ignored despite its importance, and view cells are mostly tweaked by hand in practice in order to reach optimal performance - a very time consuming task. The first algorithm specifically deals with the creation of an optimal view space partition into view cells using a cost heuristics and sparse visibility sampling. The second algorithm extends this approach to optimize both view space subdivision and object space subdivision simultaneously. Next we present a hierarchical online culling algorithm that eliminates most limitations of previous approaches, and is rendering engine friendly in the sense that it allows easy integration and efficient material sorting. It reduces the main problem of previous algorithms - the overhead due to many costly state changes and redundant hardware occlusion queries - to a minimum, obtaining up to three times speedup over previous work. At last we present an ambient occlusion algorithm which works in screen space, and show that high-quality shading with effectively hundreds of samples per pixel is possible in real time for both static and dynamic scenes by utilizing temporal coherence to reuse samples from previous frames.