Multi resolution representations and interactive visualization of huge unstructured volume meshes

Abstract

Modern scientists must consume ever bigger volumes of data gushing out of supercomputer simulations or high-powered sensors. Often, the data are represented as vast blocks of numbers which need to be transformed into a graphic representation which enables and improves understanding and analyzation. On their way from raw data to interactive visualizion, huge scientific datasets need algorithms out of three areas of research: reduction with a controllable approximation error, out-of-core techniques for huge datasets and interactive visualization of huge datasets with no visual error. All three topics are addressed by this thesis.

At the beginning, an automatic simplification technique is presented which reduces the number of elements of a dataset and controls the approximation error between the original dataset and the reduced dataset. The algorithm consists of a sequence of three steps which work globally on the dataset and improves all known approaches that use a sequence of many small local steps by increasing numerical stability and avoiding runs into local minima. With an achieved approximation error that is comparable to other known approaches, the reducer is about 3-5 times faster.

Next, an out-of-core data structure is introduced which allows for an efficient work on even biggest unstructured datasets with a low consumption of main memory and minimal accesses to secondary storage like hard discs. Based on the out-of-core data structure, two additional data structures are proposed in order to store huge datasets with multiple levels of resolution. The first data structure stores all levels of resolutions in a binary hierarchy whereas the second data structure uses the concept of multi triangulations on unstructured volume datasets. A rendering framework uses these data structures to achieve an interactive visualization with a visual error controllable by the user. Both structures run on computers with limited ressources even with no visual error.

The last chapter introduces three different visualization techniques addressing fundamental problems of occlusion during rendering. A point-based visualization technique is proposed for scalar fields. A set of isosurfaces is point sampled and the resulting points are rendered with a lighting scheme adapted to the scalar field. A ghosting technique is proposed for vector fields. A dense set of stream lines is calculated but only a few of them are visualized opaque whereas all others are visualized semi-transparent. The user has full control over the selection of the opaque lines. Finally, diffusion surfaces are introduced and it is shown how they can improve the visualization of medical MRI data.

Moderne Simulationen erzeugen immer größer werdende Datensätze und stellen Wissenschaftler vor die Aufgabe, diese Datensätze auszuwerten und zu analysieren. Oft liegen die Daten als reine Zahlenkolonnen vor und erschweren so eine Auswertung. Die Transformation der Daten in eine graphische Darstellung ist ein wichtiges Hilfsmittel, um das Ergebnis einer Simulation oder eine Sammlung gemessener Werte richtig zu interpretieren und auszuwerten. Die vorliegende Arbeit stellt neue Verfahren zur Aufbereitung solch großer Datensätze vor mit dem Ziel, eine interaktive graphische Darstellung zu ermöglichen. Dabei steht insbesondere die Aufbereitung auf Computern mit begrenzten Resourcen im Mittelpunkt der vorgestellten Algorithmen.

Diese Arbeit liefert Beiträge zu drei wichtigen Themen auf dem Gebiet der Aufbereitung von wissenschaftlichen Daten: Reduktion mit garantiertem maximalem Fehler, Bearbeitung großer Datensätze mit begrenzten Ressourcen und interaktive Visualisierung.

Zu Beginn wird ein automatischer Reduzierer vorgestellt, welcher die Anzahl der gespeicherten Elemente verringert und dabei den Approximationsfehler zwischen dem originalen Datensatz und dem reduzierten Datensatz kontrolliert. Der Reduzierer arbeitet global auf der Domäne des Datensatzes, und nicht, wie fast alle bisher bekannten Verfahren, mit vielen kleinen, lokal auf dem Datensatz arbeitenden Schritten. Damit behebt er den Nachteil dieser Verfahren, in lokale Minima zu laufen, und ist bei einem zu den anderen Verfahren vergleichbaren Approximationsfehler ungefähr um den Faktor 3-5 schneller.

Anschließend wird eine Out-of-core Datenstruktur vorgeschlagen, welche ein schnelles Bearbeiten selbst größter Datensätze erlaubt mit einem geringen Bedarf an Hauptspeicher und minimalen Zugriffen auf Sekundärspeicher. Darauf aufbauend werden zwei Datenstrukturen vorgestellt, welche den Datensatz in mehreren Auflösungsstufen speichern. Die erste Struktur speichert die Auflösungen in einer binären Hierarchie während die zweite Struktur das Konzept der Multitriangulation auf Volumennetze anwendet. Eine graphische Darstellung bedient sich dieser zwei Datenstrukturen und erreicht eine interaktive Visualisierung von sehr großen Datensätzen ohne sichtbaren Fehler, auch auf Computern mit begrenzten Resourcen.

Das letzte Kapitel der Arbeit stellt drei Techniken für die Visualisierung vor, welche grundlegende Probleme bei gegenseitigen Verdeckungen adressieren. Für Skalarfelder wird eine punktbasierte Visualisierung vorgeschlagen, welche einen Satz von Isoflächen mit Punkten abtastet und diese Punkte mit Beleuchtung zeichnet. Für Vektorfelder stellt die Arbeit eine Ghosting-Technik vor, welche einen dichten Satz von Stromlinien semi-transparent darstellt und nur wenige, vom Benutzer wählbare Stromlinien hervorhebt. Im letzten Abschnitt werden Diffusionsflächen eingeführt und ihre Anwendung für die Tensorfeld-Visualisierung mit dem Spezialfall medizinisches MRI diskutiert.