Object Hierarchies for Efficient Rendering

Abstract

The efficient synthesis of computer generated images for large three-dimensional modelsis one of the major challenges of computer graphics research. Despite the rapid growth ofavailable computational power of todays microprocessors and highly optimized graphics chipsused for efficient rendering of graphical primitives, this growth was even outbeaten by the sheerincrease of complexity of three-dimensional data sets to be visualized.This growth of complexity made it necessary to invent acceleration schemes for differenttypes of rendering algorithms. A common basic idea is to build spatial data structures thatallow for efficient spatial retrieval of primitives in the rendering process. This retrieval may beused to detect visible objects efficiently or to detect invisible objects prior before sending themthrough the graphics pipeline, such that expensive computations like shading or rasterizationmay be omitted.This thesis examines different acceleration schemes in detail and analyses related data structuresfor their utility within several rendering algorithms. We focus on acceleration schemes thatmake use of object hierarchies, i.e. scene geometry that is managed hierarchically.We also present a novel technique for automated generation of object hierarchies. The essentialidea of our algorithm is to build the hierarchy such that the average rendering costs whentraversing the scene hierarchy are minimized. This technique applies successfully in the fieldsof photorealisitic visualization using ray tracing and radiosity. First, we achieve a significantimprovement of run-time efficiency by accelerating the visibility tests. Also, we demonstratethat the generated object hierarchies may ideally be used to approximate the computation oflight exchange between complex distant scene objects for radiosity with clustering. Only theuse of objects clusters made it feasible to run an radiosity computation on huge data sets.This thesis also covers the area of real-time rendering, especially with a deeper look at occlusionculling algorithms, which have attracted much attention in the recent past. Occlusionculling schemes try to detect occluded scene geometry early to remove these objects from thegraphics pipeline. We describe the usefulness of object hierarchies within the occlusion cullingprocess and compare different hierarchy generation schemes. By the utilization of our new hierarchygeneration scheme we could achieve a significant increase in frame rate when renderingcomplex scenes.Finally, we present a system for interactive visualization of huge data sets by combiningocclusion culling and ray casting. This system increases the frame rate further compared toclassical occlusion culling. Additionally, our method has only a minimal overhead for sceneswith almost no occlusion. Occlusion tests are automatically activated and de-activated whenneeded. - Die effiziente Bildsynthese für die computergenerierte Darstellung grosser dreidimensionalerDatenmodelle, ist nach wie vor eine der grössten Herausforderungen für die Forschungim Bereich der Computergrafik. Trotz des starken Wachstums der verfügbaren Rechenresourcendurch neue Mikroprozessoren und hochgradig optimierte Grafikchips, welche die effizienteDarstellung einfacher grafischer Grundobjekte beschleunigen, wurde doch dieses Wachstumnoch durch den noch gewaltigeren Anstieg der Komplexität der 3D-Modelle geschlagen, dievisualisiert werden sollen.Dieses Problem hat es notwendig gemacht, Beschleuningungstechniken für unterschiedlicheRenderingverfahren zu entwickeln. Eine Grundidee hierbei besteht darin, Datenstrukturen aufzubauen,die es dem Darstellungsprozess ermöglichen, effizient die relative räumliche Lage vonDarstellungsobjekten abzuleiten. Sichtbare Objekte lassen sich so leichter identifizieren, bzw.nicht-sichtbare Objekte frühzeitig vor der Weiterverarbeitung eliminieren, um dadurch weitereaufwendige Berechnungen, wie etwa die Beleuchtungsrechnung oder die Rasterisierung, zuunterdrücken.Diese Dissertation untersucht detailliert unterschiedliche Beschleunigungstechniken sowiedie jeweils benötigten Datenstrukturen bezüglich ihrer Nützlichkeit in vielfältigen Darstellungsalgorithmen.Hierbei wird der Fokus auf Verfahren gelegt, die Objekt-Hierarchien ausnutzen,also eine Szenengeometrie hierarchisch verwalten.In Rahmen dieser Arbeit wird ein neues Verfahren zur automatischen Hierarchiegenerierungpräsentiert, wobei die Grundidee darin liegt, die Hierarchie derart aufzubauen, dass die erwartetenspäteren Rendering-Kosten beim Traversieren der Szenengeometrie minimiert werden. SolcheHierarchien werden erfolgreich in dem Bereich der fotorealistischen Visualisierung mittelsRay-Tracing und Radiosity eingesetzt. Hierbei wird zum einen eine deutliche Verbesserung derLaufzeit durch eine Beschleunigung der Sichtbarkeitsberechnungen erzielt. Zum anderen wirdfür das Radiosity-Verfahren gezeigt, dass die erzeugten Objekt-Hierarchien ideal zur effizientenBerechnung des Lichtflusses zwischen entfernten, komplexen Szenenobjekten verwendet werdenkönnen (Radiosity Clustering). Hierdurch wurde die Verwendung sehr grosser Datensätzeinnerhalb der Radiosity-Berechnung überhaupt erst ermöglich.Diese Arbeit geht ebenso auch auf den Bereich des Echtzeit-Renderings ein, dabei insbesondereauf Occlusion Culling-Algorithmen, denen in letzter Zeit viel Aufmerksamkeit zuteilwurde. Hierbei wird versucht, von anderen Objekten verdeckte Szenengeometrien frühzeitigzu entdecken, um sie aus der Graphikpipeline zu entfernen. Dabei wird die Nützlichkeit vonObjekt-Hierarchien für den Prozess des Occlusion Cullings hervorgehoben und es werden unterschiedlicheGenerierungsalgorithmen für solche Hierarchien verglichen. Als Resultat konntedurch Einsatz eines neuen Verfahrens zu Hierarchieerzeugung eine deutliche Erhöhung derBildgenerierungsrate bei komplexen Szenen erzielt werden.Schliesslich wird ein System zur interaktiven Visualisierung grosser Szenenmodelle präsentiert,welches durch Kombination von Occlusion Culling und Strahlschnitttests wiederum eineErhöhung der Bildgenerierungsrate im Vergleich zu klassischem Occlusion Culling erreicht. Es wird zudem aufgezeigt, dass dieses Verfahren in Szenen mit geringer Verdeckung nahezu keinenOverhead beinhaltet. Die Occlusion-Tests werden hierbei genau dann automatisch aktiviertbzw. deaktiviert, wenn es notwendig ist.