Optimierungsverfahren zur Isoflächen-Extraktion in der wissenschaftlichen Visualisierung

Abstract

Die Aufgabenstellung der Isoflächen-Extraktion ist es, für einen<br />vorgegebenen Satz von Volumendaten, der eine Funktion repräsentiert,<br />zu jedem so genannten Isowert die Grenzfläche zu finden,<br />die die Bereiche mit Funktionswerten über und unter diesem Wert<br />voneinander trennt.<br />Mit der Hilfe von zusätzlichen Datenstrukturen lässt sich diese<br />Aufgabe schneller lösen als durch eine vollständige Durchsuchung<br />des Datensatzes. Dafür lassen sich Datenstrukturen verwenden, die<br />mit wenig Speicher eine grobe Übersicht über den Datensatz<br />geben (z. B. Partitionsbäume) oder alle Intervalle in ein schnelles,<br />aber speicherintensives Suchschema eintragen (Intervallbäume, KD-Trees).<br /><br />Zu jeder Methode, insbesondere zur Brute-Force-Suche,<br />Partitionsbaum-, Intervallbaum-, KD-Tree- und einer<br />hier beschriebenen Out-of-Core-Methode lässt sich<br />ein Verfahren angeben, mit dem man abhängig von den Volumendaten<br />die mittlere Extraktionszeit bei Annahme einer gegebenen<br />Wahrscheinlichkeitsverteilung der Isowerte analytisch und meist<br />rekursiv über den Aufbau der jeweiligen Datenstruktur bestimmen kann.<br />Die Berechnung der Extraktionszeiten ist in dieser Arbeit beschrieben.<br /><br />Mit Hilfe dieser Extraktionszeiten lässt sich<br />eine parameterabhängige Methode entwickeln,<br />die zu jeder vorgegebenen Hauptspeichergröße einen so genannten<br />Conditioned Tree konstruiert, der den Speicher optimal zugunsten<br />der Extraktionsgeschwindigkeit ausnutzt. Dieser ist eine hybride<br />Datenstruktur, die auf einem Partitionsbaum basiert, der in einigen<br />seiner Blätter Verweise auf andere Datenstrukturen enthält.<br />Das Optimierungsverfahren zur Bildung der besten Conditioned<br />Trees läuft darauf hinaus, eine Kostenfunktion C_l(T)=M(T)+l*T(T)<br />über alle Bäume T einer vorgegebenen Klasse zu minimieren,<br />wobei M(T) der Speicherbedarf des Baums und aller<br />angehängten Datenstrukturen ist und T(T) die mittlere<br />Extraktionszeit, die zu diesem Zweck unter Benutzung der<br />erwähnten Näherungsformeln geschätzt wird.<br /><br />Aus einer Arbeit von Hugh Everett geht<br />hervor, dass ein mit dieser Minimierungsmethode erhaltener<br />Optimalbaum stets auch die Zeitfunktion T(T) minimiert<br />unter der Nebenbedingung, dass der Speicherbedarf M(T)<br />den Wert des Optimums nicht überschreiten darf.<br />Die Lagrange-Optimierung hat also den Vorteil, dass wir durch<br />Variation des Lagrange-Faktors l eine Serie von jeweils<br />optimalen Bäumen erhalten, die sich für Rechner-Konfigurationen<br />mit verschiedenem zur Verfügung stehendem Speicher eignen<br />und fast jede Speichervorgabe optimal zugunsten der<br />Extraktionsgeschwindigkeit ausnutzen.<br /><br />Ebenso wird ein Verfahren beschrieben, mit dem auch<br />die Rechenzeit komplexer Algorithmen - in diesem Fall<br />Extraktionsmethoden - experimentell ermittelt werden<br />kann. Hierfür wird das Vorhandensein einer lineare Formel<br />zur Bestimmung der Rechenzeit vorausgesetzt, in der<br />aber noch unbestimmte Zeitkonstanten vorkommen. Für<br />eine Reihe von Rechendurchläufen mit verschiedenen<br />Datenstrukturen gleichen Typs werden die Koeffizienten<br />in dieser Formel analytisch und die tatsächliche<br />Rechenzeit durch Messung bestimmt. Dann werden die<br />noch fehlenden Zeitkonstanten in der Formel approximiert,<br />indem der Fehler zwischen dem Wert theoretischen<br />Formel und der praktischen Messung minimiert wird.