Hardware-beschleunigte Volumenvisualisierung auf adaptiven Datenstrukturen

Abstract

In vielen Disziplinen und Anwendungsgebieten spielen Volumendaten heutzutage eine immer wichtigere Rolle und der Einsatz von Graphik-Hardware stellt eine gute Möglichkeit dar, den mit der Volumenvisualisierung verbundenen Berechnungsaufwand zu meistern. Die bisher auf Graphikkarten übliche relativ starre Verarbeitungspipeline beschränkt ihren Einsatz jedoch auf wenige Typen von Volumendaten, insbesondere uniforme 3D Gitter, deren Struktur sich effizient auf die Mechanismen auf der Graphikkarte abbilden lässt. Mit der kürzlich eingeführten freien Programmierbarkeit von Graphikkarten ist es zunehmend möglich, die massive Rechenleistung der Graphikchips, welche die Fähigkeiten aktueller Universalprozessoren bei weitem übersteigt, für die Visualisierung von Volumendaten auf adaptiven Datenstrukturen einzusetzen.

Am Beispiel dreier wichtiger Vertreter dieser Gattung von adaptiven Datenstrukturen, Finite-Elemente-Netze in ihrer Ausprägung als Tetraedergitter, lokale Gitterverfeinerungen sowie gitterlose Punktrepräsentationen, untersucht diese Arbeit, in wieweit sich die dafür erforderlichen komplexen Visualisierungsalgorithmen durch den Einsatz moderner Graphik-Hardware beschleunigen lassen. Ziel es dabei, möglichst viele Teile der Berechnung in den Verantwortungsbereich der Graphikkarte zu bringen, um auch in Zukunft von dem raschen Fortschritt bei der Entwicklung von Graphik-Hardware zu profitieren.

Ein wichtiges dabei zu untersuchendes Problemfeld stellt das Zusammenspiel der unterschiedlichen involvierten Berechnungseinheiten (Hauptprozessor, Vertexprozessor und Fragmentprozessor auf der Graphikkarte) dar. Die Geschwindigkeitsoptimierung durch ausgewogenene Balance wird in der vorliegenden Arbeit durch unterschiedliche Algorithmen zur Visualisierung von Tetraedergittern demonstriert, die sukzessive identifizierte Flaschenhälse bei der Berechnung und der Kommunikation mit nachgelagerten Einheiten und dem Speicher beseitigen. Am Ende steht ein Hardware-basierter Ray Casting-Algorithmus für Tetraedergitter, der vollständig auf der Graphik-Hardware abläuft.

Da Algorithmen, die auf der Graphikkarte ablaufen, ihre Daten aus dem Speicher der Graphikkarte beziehen, werden weiterhin Möglichkeiten zur Kompression betrachtet, um die maximale Größe der verarbeitbaren Datensätze zu erhöhen. Es wird eine neue kompakte Datenstruktur für Tetraedergitter vorgestellt, welche sowohl die Tetraederattribute als auch die Konnektivität der Tetraeder speichert und als Basis zur Visualisierung mittels Ray Casting dienen kann. Für punktbasierte Daten wird außerdem eine neue kompakte prozedurale Kodierung auf der Grundlage von radialen Basisfunktionen entwickelt, welche durch die Möglichkeit der Dekodierung mittels der programmierbaren Fragmenteinheit mit einer Vielzahl von Visualisierungslagorithmen kombinierbar ist und durch die vorgelagerte Kodierung anderer Datenstrukturen wie uniformer Gitter, Tetraedergitter oder gitterloser Daten eine universelle Visualisierungslösung darstellt.

Eine weitere Option zur interaktiven Visualisierung von Tetraedergittern bietet die Abtastung auf adaptiv verfeinerten uniformen Volumengittern, die besser für die Verarbeitung auf der Graphikkarte geeignet sind. Hier ermöglicht die Beschleunigung der Abtastung mittels Graphik-Hardware die dynamische Berechnung, jeweils entsprechend den Parametern des aktuell dargestellten Bildes. Die sonst beim Resampling auftretenden charakteristischen Probleme wie hoher Speicherbedarf, geringe Interaktionsraten oder niedrige Darstellungsqualität werden dadurch vermieden beziehungsweise minimiert.

Für typische Probleme, die bei der Visualisierung auf der Basis adaptiv verfeinerter uniformer Gitter auftreten, wie inkonsistente Interpolation zwischen unterschiedlichen Gitterbereichen oder Artefakte, die durch eine adaptive Abtastung auftreten, werden Lösungsansätze präsentiert.

Implementierungsaspekte einer adaptiven Volumendarstellung auf uniformen Gittern werden im Rahmen einer neuartigen Software-Architektur mit flexiblen und erweiterbaren Shadern betrachtet. Sie erlaubt es, die Visualisierungsalgorithmen einfach auf die spezielle Graphik-Hardware der Zielplattform anzupassen, was in Anbetracht der heterogenen Graphikkarten-Landschaft einen wichtigen Baustein für die Entwicklung effizienter Visualisierungslösungen darstellt. Darüberhinaus wird gezeigt, wie sich programmierbare Graphik-Hardwere im Umfeld von virtuellen Umgebungen durch Hardware-beschleunigte Bildkompression und -dekompression geschwindigkeitssteigernd einsetzen lässt.

Die Arbeit bringt alle vorgestellten Algorithmen in einen Gesamtzusammenhang, der es erlaubt gemeinsame Gestaltungsrichtlinien für die erfolgreiche Umsetzung von Visualisierungs-Algorithmen auf Graphik-Hardware zu extrahieren. Diese können anderen Forschern als Muster und zur Anregung dienen und so die Entwicklung weiterer Hardware-beschleunigter Algorithmen inspirieren.

In order to deal with the computational complexity of direct volume rendering several researchers exploit the massive computational power of graphics hardware nowadays available in almost every standard PC. Due to a relatively strict processing pipeline, the application of graphics hardware for visualization purposes was until recently restricted either to the rendering of visual representations computed by the main processor, e.g., extracted polygonal isosurfaces, or to data structures which map directly to mechanisms provided by the graphics hardware, e.g., three-dimensional regular meshes, which can be represented by 3D textures. This thesis discusses how the programmable vertex and fragment processing units of modern graphics hardware can now be exploited to implement visualization algorithms that work directly on adaptive data structures like unstructured meshes, adaptive refined structured meshes, or point-based data representations.

One major challenge for the implementation of optimized visualization algorithms is the consideration of three different processing units, the main processor, the vertex processor, and the fragment processor, including the communication between these units and the access to the local memory of each unit. This thesis addresses the balancing of these units in the context of hardware-accelerated visualization algorithms for adaptive data structures. New visualization algorithms are designed based on the identified bottlenecks in common visualization algorithms. Furthermore, design principles that have proven to be successful in the context of hardware-software synthesis of embedded systems are adapted. Their application to typical visualization problems leads to the successful development of several new hardware-accelerated visualization algorithms for tetrahedral meshes, point-based data representations, and adaptive structured meshes.

Among these algorithms are a hardware-accelerated cell projection algorithm, that exploits programmable vertex processing in order to remove the bottlenecks associated with the main processor and the data transfer between the main processor and the graphics adapter. The key idea is to remove view dependent computations from the responsibility of the main processor, thus, allowing for storing the tetrahedral mesh in a static array that can be either stored in the local memory of the graphics card or efficiently transferred to the graphics card exploiting typical optimization techniques for polygonal graphics. Further improvements of this idea lead to a hardware-based ray casting algorithm that run solely in the fragment unit of the graphics card.

Another important issue for algorithms that run on the graphics card is the compact data representation, since such approaches require that the data to be visualized resides in the limited texture memory of the graphics adapter. Therefore, the possibility for mesh compression exploiting a data representation based on tetrahedral strips is discussed and a new compact data structure is proposed, that can be employed for a variety of (hardware-based) visualization and filtering algorithms. An alternative approach exploits a compact universal data representation scheme based on a procedural encoding of the volumetric data with radial basis functions.

High framerates that are typically achieved for regular 3D grids employing texture-based volume rendering algorithms can be gained for tetrahedral meshes by resampling them on adaptively refined uniform meshes. Three resampling algorithms are presented that allow for the fast conversion of tetrahedral meshes into a hierarchy of adaptively refined uniform meshes. In this context an optimal balance for the workload distribution between the main processor and the graphics processor is investigated. Solutions for typical problems of volume rendering based on a hierarchy of adaptive refined texture maps, i.e., inconsistent interpolation over borders between areas represented at different levels of detail or artifacts at level-transitions, are presented.

Implementation aspects for the adaptive rendering of volumetric data on uniform meshes are covered by presenting a framework employing a flexible and extensible shader concept in order to achieve extensibility and to allow for adaptation of volume rendering algorithms to the capabilities of the specific graphics card an application runs on. Additionally, aspects for volume rendering in virtual environments are covered by presenting a distributed client server architecture and by discussing image compression/decompression algorithm computed by the graphics hardware.

Beside from these actual applicable algorithms, this thesis also identifies common strategies and principles which lead to successful algorithmic designs. The overview of these strategies will help other researchers to develop hardware-accelerated visualization and rendering algorithms for areas not covered by this thesis.