Beschleunigtes Volume Rendering auf strukturierten, adaptiven Gittern

0\. Title, Table of Contents, and Acknowledgements 1 1\. Introduction 1 2\. Function Approximation on Discrete Grids 5 3\. Visualization Methods for Scalar Data 25 4\. Accelerated Volume Rendering 45 5.1 - 5.4 Visualization of Structured Adaptive Mesh Refinement Data 69 5.5 - 5.6 Direct Volume Rendering for Structured AMR Data 69 5.7 Rendering the First Star in the Universe - a case study 69 6\. Summary and Concluding Remarks 107 7\. Bibliography 110Multi-scale phenomena are abundant in many application fields. Representing and numerically simulating such processes is a challenging task since quite different scales have to be resolved, which often requires enormous amounts of storage and computational power. An important strategy in this context is adaptivity, i.e. local adjustment of the spatio-temporal resolution to the details to be resolved. A standard representation therefore are hierarchical, locally refined grids. A specific adaptive approach for solving partial differential equations, usually called AMR (Adaptive Mesh Refinement), was introduced in 1984. The basic idea is to combine the simplicity of structured grids and the advantages of local refinement. In this numerical scheme the computations are started on a set of coarse, potentially overlapping structured grids, that cover the computational domain. Local error criteria are applied to detect regions that require higher resolution. These are covered by subgrids with decreasing mesh spacing, which do not replace, but rather overlap the refined regions of the coarser patches. The equations are advanced on the finer subgrids and the refinement procedure recursively continues until all cells fulfill the considered error criteria, giving rise to a hierarchy of nested levels of refinement. In 1989 a variant of this scheme, called Structured Adaptive Mesh Refinement (SAMR), which reduces some of the complexity of the original approach, was proposed. While the separate subgrids in the AMR scheme could be rotated against each other, in SAMR they are aligned with the major axes of the coordinate system, which for example simplifies the computation of fluxes of (conserved) quantities through the cell faces. SAMR has become more and more popular in the last decade, and nowadays it is applied in many domains like hydrodynamics, meteorology and in particular in cosmology and relativistic astrophysics. Due to this growing popularity, an increasing number of scientists is in need of appropriate interactive visualization techniques to interpret and analyze AMR simulation data. Tools for both, 2D analysis to quantitatively convey the information within single slices and 3D representations to apprehend the overall structure are required. In this thesis we develop direct and indirect volume visualization algorithms for scalar fields that are defined on structured Adaptive Mesh Refinement (SAMR) grids. In particular algorithms for planar slicing and the display of height fields, C0-continuous isosurface extraction, software-, and hardware-based direct volume rendering and temporal interpolation for cell-, and vertex-centered data on unrestricted SAMR grids are proposed. Additionally we investigate the applicability of SAMR data structures for accelerated software-, and hardware-based volume rendering of large 3D scalar data.Multiskalenphänomene treten in vielen naturwissenschaftlichen Anwendungsgebieten auf. Die Modellierung und numerische Simulation solcher Prozesse ist sehr aufwendig und erfordert häufig große Mengen an Speicher- und Rechnerressourcen. Eine wichtige Rolle spielen in diesem Zusammenhang adaptive Verfahren, welche die räumliche und zeitliche Rechengenauigkeit lokal anpassen. Die zu lösenden Gleichungen werden hierzu auf lokal verfeinerten Gittern diskretisiert. Ein spezielles adaptives Verfahren zur Lösung partieller Differentialgleichungen ist das 1984 von M. Berger vorgestellte Adaptive Mesh Refinement (AMR) Schema. Dieser Ansatz kombiniert die Vorteile strukturierter Gitter mit denen lokaler Gitterverfeinerung. Hierbei werden die Gleichungen zunächst auf einem groben, strukturierten Gitter gelöst. Mittels lokaler Fehlerschätzer werden Regionen, die höhere Auflösung benötigen, detektiert und durch Untergitter geringerer Zellgröße überdeckt. Die Gleichungen werden dann erneut auf diesen Untergittern gelöst, und dieser Vorgang wird rekursiv fortgesetzt, bis alle Gitterzellen die jeweilige Fehlerschranke unterschreiten. Eine Variante dieses Verfahrens ist das sogenannte Structured Adaptive Mesh Refinement (SAMR). Während die Gitter im AMR Ansatz beliebig rotiert sein können, sind die einzelnen Untergitter im SAMR Ansatz parallel zu den Koordinatenachsen orientiert. SAMR wird heute in vielen Gebieten wie zum Beispiel der Hydrodynamik, Meteorologie und insbesonderen in der Kosmologie und relativistischen Astrophysik verwendet. Mit der wachsenden Verbreitung dieses numerischen Verfahrens, steigt auch die Zahl der Wissenschaftler die geeignete, interaktive zwei- und dreidimensionale Visualisierungsverfahren zur Analyse zeitabhängiger Simulationsdaten auf SAMR- Gittern benötigen. In dieser Arbeit werden direkte und indirekte Volumenvisualisierungsverfahren zur Visualisierung von skalaren Feldern auf strukturierten AMR Gittern entwickelt. Insbesondere werden Algorithmen zur Darstellung von Schnitten und Höhenfeldern und zur C0-stetigen Isoflächenextraktion beschrieben. Ferner werden Ansätze für beschleunigtes software- und hardwarebasiertes Volume Rendering und für die zeitliche Interpolation von vertex- und zellzentrierten Daten auf SAMR-Gittern vorgestellt. Außerdem wird die Anwendbarkeit von SAMR Datenstrukturen zum beschleunigtem Volume Rendering von 3D Daten auf uniformen Gittern untersucht