Representing and rendering distant objects for real-time visualization

Abstract

Computer graphics is the art of creating believable images. The difficulty in many applications lies in doing so quickly. Architectural walkthroughs, urban simulation, computer games and many others require high quality representation of very large virtual models at interactive update rates. This usually means creating a new image at least 60 times a second. This is what real-time visualization is about. This thesis presents two methods to accelerate the rendering of very large environments. Both algorithms exploit a common property of many such environments: distant objects usually take up a significant amount of computation time during rendering, but contribute only little to the final image. Few pixels are affected by distant objects. This thesis shows how to represent and render distant objects with a complexity proportional to the image area they cover, and not to their actual complexity. The algorithms are destined for different scenarios: the first is an online algorithm that carries out all computation during runtime and does not require precomputation. The second algorithm makes use of preprocessing to speed up online rendering and to improve rendering quality. The first part of the thesis shows an output-sensitive rendering algorithm for accelerating walkthroughs of large, densely occluded virtual environments using a multi-stage image-based rendering pipeline. In the first stage of the pipeline, objects within a certain distance (the near field) are rendered using the traditional graphics pipeline. In the following stages, the remainder of the scene (the far field), which consists of all pixels not yet covered by near field geometry, is rendered by a pixel-based approach using a panoramic image cache, horizon estimation to avoid calculating sky pixels, and finally, ray casting. The time complexity of the approach does not depend on the total number of primitives in the scene. We have measured speedups of up to one order of magnitude compared to standard rendering with view frustum culling. In the second part of the thesis, a new data structure for encoding the appearance of a geometric model as seen from a viewing region (view cell) is presented. This representation can be used in interactive or real-time visualization applications to replace complex models - especially distant geometry - by an impostor, maintaining high-quality rendering while cutting down on rendering time. The approach relies on an object-space sampled representation similar to a point cloud or a layered depth image, but introduces two fundamental additions to previous techniques. First, the sampling rate is controlled to provide sufficient density across all possible viewing conditions from the specified view cell. Second, a correct, antialiased representation of the plenoptic function is computed using Monte Carlo integration. The system therefore achieves high quality rendering using a simple representation with bounded complexity. This thesis also contains a comprehensive overview of related work in the field of real-time visualization, and an in-depth discussion of the advantages and disadvantages of image-based and point-based representations for distant objects.

Computergraphik ist die Wissenschaft, die sich mit der Generierung glaubwuerdiger Bilder beschaeftigt. Eine der groessten Herausforderungen dabei ist, diese Bilder in ausreichender Geschwindigkeit zu erzeugen. Speziell bei der Simulation von Fahrzeugen in Stadtgebieten, bei der virtuellen Erforschung von (noch nicht gebauten, existierenden oder schon lange zerstoerten) Gebaeuden, bei Computerspielen und vielen anderen Anwendungen ist es wichtig, dass die Bilder in fluessiger Abfolge erscheinen. Ueblicherweise versteht man darunter eine Bildrate von mindestens 60 Bildern pro Sekunde. Das ist das Thema der Echtzeitvisualisierung. In dieser Dissertation werden zwei Algorithmen zur beschleunigten Darstellung von grossen virtuellen Szenen vorgestellt. Dabei wird bei beiden Algorithmen eine interessante Eigenschaft von vielen solchen Szenen ausgenuetzt: Objekte, die sich weiter weg vom Betrachter befinden, machen nur einen kleinen Teil des endgueltigen Bildes aus, benoetigen aber relativ viel Rechenzeit. Nur wenige Pixel sind von solchen Objekten bedeckt. In dieser Dissertation wird gezeigt, wie man entfernte Objekte mit einer Komplexitaet, die der ueberdeckten Bildflaeche und nicht ihrer eigentlichen geometrischen Komplexitaet entspricht, repraesentieren und darstellen kann. Die beiden Algorithmen sind fuer unterschiedliche Szenarien gedacht. Die erste Methode funktioniert zur Laufzeit, braucht also keine Vorberechnung. Die zweite Methode hingegen hat einen wichtigen Vorberechnungsschritt, der bei der Darstellung sowohl die Geschwindigkeit als auch die Qualitaet signifikant erhoeht. Der erste Teil der Dissertation beschaeftigt sich mit einem Algorithmus zur Darstellung von Szenen mit starker gegenseitiger Verdeckung von Objekten. Dabei kommen in mehreren Schritten bildbasierte Renderingmethoden zum Einsatz. Objekte bis zu einer bestimmten Entfernung vom Betrachter werden mit gewoehnlichen polygonbasierten Methoden gezeichnet. In einem weiteren pixelbasierten Schritt werden dann alle noch nicht bedeckten Pixel des Bildes identifiziert und in einem zylindrischen Zwischenspeicher fuer Farbwerte nachgeschaut. Sollte dort kein sinnvoller Wert vorhanden sein, wird die Farbe des Pixels mittels ray casting (einem Blickstrahl) ermittelt, sofern es sich nicht ueber dem Horizont befindet. Die Methode funktioniert praktisch unabhaengig von der Anzahl der verwendeten Objekte in der Szene und erreicht ca. zehnfache Beschleunigung gegenueber ueblichen Renderingmethoden. Im zweiten Teil der Dissertation wird eine Datenstruktur zur getrennten Speicherung von Geometrie- und Farbinformationen fuer ein Objekt praesentiert, die fuer die Betrachtung aus einem bestimmten raeumlich abgegrenzten Bereich eignet. Damit sollen komplexe Objekte in virtuellen Szenen - insbesondere weit entfernte Objekte - ersetzt werden, um eine schnellere und qualitativ bessere Darstellung dieser Objekte zu erreichen. Dabei wird das Objekt quasi mit einer Punktwolke dargestellt, deren Dichte sich nach den moeglichen Betrachterpositionen richtet. Das Aussehen der Punktwolke wird mittels eines Monte Carlo Verfahrens bestimmt, das eine artefaktfreie Darstellung von allen erlaubten Blickpunkten gestattet. Ausserdem gibt diese Dissertation einen ausfuehrlichen Ueberblick ueber schon publizierte Methoden im Bereich der Echtzeitvisualisierung, und enthaelt eine Analyse ueber Vor- und Nachteile von bild- und punktbasierten Renderingmethoden fuer die Darstellung von entfernten Objekten.