Hierarchical methods for filtering and visualization based on graphics hardware

Abstract

Interactive visualization of large data sets is only possible with efficient algorithms for all parts of the visualization pipeline. This thesis analyzes the filtering and the rendering steps of this pipeline for several fundamentally different data types. Two key techniques that are employed throughout this work are the use of hierarchical methods and graphics-hardware-based implementations of the presented algorithms.

In order to improve the efficiency of filtering, both linear and nonlinear filters are accelerated using graphics hardware for the computation. For many algorithms hierarchical filters based on wavelets are needed and, therefore, inspected as well. Finally, the quality of the achieved results is analyzed, as the accuracy of graphics-card-based approaches is limited by register sizes and framebuffer depths.

During rendering hierarchical approaches allow for a compact representation of partially detailed data. Additionally, the user can trade visualization speed for quality. Sparse grids allow for extremely compact representations, thus interpolated data from sparse grids would no longer fit into main memory. This raises the need for visualization algorithms working directly on the sparse grid coefficients. The interpolation process is expensive, but graphics hardware is usually too inaccurate to be used for acceleration. Thus, the rendering process is parallelized with MPI, using a ray distribution scheme that implicitly generates previews with lower resolution during rendering. For unstructured data a compact hierarchical representation with radial basis functions is introduced that can be employed for rendering at interactive frame rates using graphics hardware.

Completely uncorrelated data like astrophysical n-body problems have high spatial resolution which is lost during resampling for volume rendering. A new hierarchical splatting approach is presented that is able to visualize tens of millions of points interactively for steady and time-dependent data sets.

The used data representations have different approximation capabilities, thus the properties of the different data encodings are analyzed by comparing several data sets that exhibit different amounts of features.

Die interaktive Visualisierung großer Datensätze kann nur durch den Einsatz effizienter Algorithmen in allen Teilen der Visualisierungspipeline gelingen. In dieser Dissertation werden die Schritte Filterung und Rendering für einige fundamental unterschiedliche Datentypen analysiert. Die beiden Haupttechniken, die in dieser Arbeit eingesetzt werden, sind die Verwendung hierarchischer Methoden sowie die Anpassung der präsentierten Algorithmen für die Ausführung des Programmcodes auf Graphikkarten.

Um die Effizienz von Filtertechniken zu steigern, können sowohl lineare als auch nichtlineare Filter mit Hilfe von Graphikhardware beschleunigt werden. Viele Algorithmen bauen auf hierarchischen Filtern wie den Wavelets auf, deshalb werden auch diese untersucht. Ein weiteres Augenmerk liegt auf der Qualität der erreichten Ergebnisse, da alle Ansätze, die Graphikkarten für ihre Berechnungen benutzen, bezüglich ihrer Genauigkeit durch die Registerbreite und die Framebuffertiefe limitiert sind.

Hierarchische Ansätze können bei nur partiell hochaufgelösten Daten helfen, diese in einer kompakten Repräsentation zu speichern. Außerdem kann der Benutzer / die Benutzerin sich zugunsten einer schnelleren Darstellung für niedrigere Qualitätsstufen entscheiden. Dünne Gitter erlauben eine extrem kompakte Speicherung und würden auf vollen Gittern interpoliert nicht mehr in den Hauptspeicher passen. Deshalb müssen Datensätze auf diesen Gittern direkt dargestellt werden. Die Interpolation ist aufwändig, und Graphikhardware ist normalerweise zu ungenau, um für die Beschleunigung der Berechnungen benutzt werden zu können. Deshalb wird der Rendering-Prozess mit Hilfe von MPI parallelisiert. Dabei wird ein Strahlverteilungsverfahren benutzt, das während der Berechnung implizit eine progressive Vorschau in niedrigerer Auflösung erzeugt. Für unstrukturierte Daten wird eine kompakte hierarchische Repräsentation eingeführt, die radiale Basisfunktionen einsetzt. Diese Darstellung kann für die Visualisierung mit Hilfe von Graphikhardware verwendet werden, wobei interaktive Frameraten erzielt werden.

Vollkommen unkorrelierte Daten, wie sie in der Astrophysik bei n-Körper-Problemen auftreten, haben eine hohe Ortsauflösung, welche bei der Neuabtastung für die direkte Volumenvisualisierung verloren geht. Ein neuer Splatting-basierter hierarchischer Ansatz wird vorgestellt, der es ermöglicht, mehrere Millionen Punkte interaktiv zu visualisieren, sowohl für den statischen als auch den zeitabhängigen Fall.

Die benutzten Datenrepräsentationen haben unterschiedliche Näherungseigenschaften. Aus diesem Grund werden die Charakteristiken dieser Repräsentationen mit Hilfe verschiedener Datensätze mit unterschiedlich vielen Merkmalen untersucht.