Optimierungsverfahren zur Isoflächen-Extraktion in der wissenschaftlichen Visualisierung
Optimierungsverfahren zur Isoflächen-Extraktion in der wissenschaftlichen Visualisierung
Date
2006
Authors
Toelke, Jürgen
Editors
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
URI (citable link)
International patent number
Link to the license
EU project number
Project
Open Access publication
Collections
Title in another language
Optimization methods of isosurface extraction in scientific visualization
Publication type
Dissertation
Publication status
Published in
Abstract
Die Aufgabenstellung der Isoflächen-Extraktion ist es, für einen
vorgegebenen Satz von Volumendaten, der eine Funktion repräsentiert,
zu jedem so genannten Isowert die Grenzfläche zu finden,
die die Bereiche mit Funktionswerten über und unter diesem Wert
voneinander trennt.
Mit der Hilfe von zusätzlichen Datenstrukturen lässt sich diese
Aufgabe schneller lösen als durch eine vollständige Durchsuchung
des Datensatzes. Dafür lassen sich Datenstrukturen verwenden, die
mit wenig Speicher eine grobe Übersicht über den Datensatz
geben (z. B. Partitionsbäume) oder alle Intervalle in ein schnelles,
aber speicherintensives Suchschema eintragen (Intervallbäume, KD-Trees).
Zu jeder Methode, insbesondere zur Brute-Force-Suche,
Partitionsbaum-, Intervallbaum-, KD-Tree- und einer
hier beschriebenen Out-of-Core-Methode lässt sich
ein Verfahren angeben, mit dem man abhängig von den Volumendaten
die mittlere Extraktionszeit bei Annahme einer gegebenen
Wahrscheinlichkeitsverteilung der Isowerte analytisch und meist
rekursiv über den Aufbau der jeweiligen Datenstruktur bestimmen kann.
Die Berechnung der Extraktionszeiten ist in dieser Arbeit beschrieben.
Mit Hilfe dieser Extraktionszeiten lässt sich
eine parameterabhängige Methode entwickeln,
die zu jeder vorgegebenen Hauptspeichergröße einen so genannten
Conditioned Tree konstruiert, der den Speicher optimal zugunsten
der Extraktionsgeschwindigkeit ausnutzt. Dieser ist eine hybride
Datenstruktur, die auf einem Partitionsbaum basiert, der in einigen
seiner Blätter Verweise auf andere Datenstrukturen enthält.
Das Optimierungsverfahren zur Bildung der besten Conditioned
Trees läuft darauf hinaus, eine Kostenfunktion C_l(T)=M(T)+l*T(T)
über alle Bäume T einer vorgegebenen Klasse zu minimieren,
wobei M(T) der Speicherbedarf des Baums und aller
angehängten Datenstrukturen ist und T(T) die mittlere
Extraktionszeit, die zu diesem Zweck unter Benutzung der
erwähnten Näherungsformeln geschätzt wird.
Aus einer Arbeit von Hugh Everett geht
hervor, dass ein mit dieser Minimierungsmethode erhaltener
Optimalbaum stets auch die Zeitfunktion T(T) minimiert
unter der Nebenbedingung, dass der Speicherbedarf M(T)
den Wert des Optimums nicht überschreiten darf.
Die Lagrange-Optimierung hat also den Vorteil, dass wir durch
Variation des Lagrange-Faktors l eine Serie von jeweils
optimalen Bäumen erhalten, die sich für Rechner-Konfigurationen
mit verschiedenem zur Verfügung stehendem Speicher eignen
und fast jede Speichervorgabe optimal zugunsten der
Extraktionsgeschwindigkeit ausnutzen.
Ebenso wird ein Verfahren beschrieben, mit dem auch
die Rechenzeit komplexer Algorithmen - in diesem Fall
Extraktionsmethoden - experimentell ermittelt werden
kann. Hierfür wird das Vorhandensein einer lineare Formel
zur Bestimmung der Rechenzeit vorausgesetzt, in der
aber noch unbestimmte Zeitkonstanten vorkommen. Für
eine Reihe von Rechendurchläufen mit verschiedenen
Datenstrukturen gleichen Typs werden die Koeffizienten
in dieser Formel analytisch und die tatsächliche
Rechenzeit durch Messung bestimmt. Dann werden die
noch fehlenden Zeitkonstanten in der Formel approximiert,
indem der Fehler zwischen dem Wert theoretischen
Formel und der praktischen Messung minimiert wird.
vorgegebenen Satz von Volumendaten, der eine Funktion repräsentiert,
zu jedem so genannten Isowert die Grenzfläche zu finden,
die die Bereiche mit Funktionswerten über und unter diesem Wert
voneinander trennt.
Mit der Hilfe von zusätzlichen Datenstrukturen lässt sich diese
Aufgabe schneller lösen als durch eine vollständige Durchsuchung
des Datensatzes. Dafür lassen sich Datenstrukturen verwenden, die
mit wenig Speicher eine grobe Übersicht über den Datensatz
geben (z. B. Partitionsbäume) oder alle Intervalle in ein schnelles,
aber speicherintensives Suchschema eintragen (Intervallbäume, KD-Trees).
Zu jeder Methode, insbesondere zur Brute-Force-Suche,
Partitionsbaum-, Intervallbaum-, KD-Tree- und einer
hier beschriebenen Out-of-Core-Methode lässt sich
ein Verfahren angeben, mit dem man abhängig von den Volumendaten
die mittlere Extraktionszeit bei Annahme einer gegebenen
Wahrscheinlichkeitsverteilung der Isowerte analytisch und meist
rekursiv über den Aufbau der jeweiligen Datenstruktur bestimmen kann.
Die Berechnung der Extraktionszeiten ist in dieser Arbeit beschrieben.
Mit Hilfe dieser Extraktionszeiten lässt sich
eine parameterabhängige Methode entwickeln,
die zu jeder vorgegebenen Hauptspeichergröße einen so genannten
Conditioned Tree konstruiert, der den Speicher optimal zugunsten
der Extraktionsgeschwindigkeit ausnutzt. Dieser ist eine hybride
Datenstruktur, die auf einem Partitionsbaum basiert, der in einigen
seiner Blätter Verweise auf andere Datenstrukturen enthält.
Das Optimierungsverfahren zur Bildung der besten Conditioned
Trees läuft darauf hinaus, eine Kostenfunktion C_l(T)=M(T)+l*T(T)
über alle Bäume T einer vorgegebenen Klasse zu minimieren,
wobei M(T) der Speicherbedarf des Baums und aller
angehängten Datenstrukturen ist und T(T) die mittlere
Extraktionszeit, die zu diesem Zweck unter Benutzung der
erwähnten Näherungsformeln geschätzt wird.
Aus einer Arbeit von Hugh Everett geht
hervor, dass ein mit dieser Minimierungsmethode erhaltener
Optimalbaum stets auch die Zeitfunktion T(T) minimiert
unter der Nebenbedingung, dass der Speicherbedarf M(T)
den Wert des Optimums nicht überschreiten darf.
Die Lagrange-Optimierung hat also den Vorteil, dass wir durch
Variation des Lagrange-Faktors l eine Serie von jeweils
optimalen Bäumen erhalten, die sich für Rechner-Konfigurationen
mit verschiedenem zur Verfügung stehendem Speicher eignen
und fast jede Speichervorgabe optimal zugunsten der
Extraktionsgeschwindigkeit ausnutzen.
Ebenso wird ein Verfahren beschrieben, mit dem auch
die Rechenzeit komplexer Algorithmen - in diesem Fall
Extraktionsmethoden - experimentell ermittelt werden
kann. Hierfür wird das Vorhandensein einer lineare Formel
zur Bestimmung der Rechenzeit vorausgesetzt, in der
aber noch unbestimmte Zeitkonstanten vorkommen. Für
eine Reihe von Rechendurchläufen mit verschiedenen
Datenstrukturen gleichen Typs werden die Koeffizienten
in dieser Formel analytisch und die tatsächliche
Rechenzeit durch Messung bestimmt. Dann werden die
noch fehlenden Zeitkonstanten in der Formel approximiert,
indem der Fehler zwischen dem Wert theoretischen
Formel und der praktischen Messung minimiert wird.
Summary in another language
Many methods are known for the problem of isosurface
extraction, but they are either slow (brute force method,
partition trees) or memory consuming (interval trees, KD trees),
or they need a lot of preprocessing time and external memory
(out-of-core methods). In this dissertation, a hybrid data
structure, the Conditioned Tree, is described, which can
be modified and optimized depending from the given main memory.
The Conditioned Tree is based on a partition tree
with pointers to other data structures of already known
methods.
In this way, various main memory sizes can be used for
extracting the isosurface within the lowest possible time.
extraction, but they are either slow (brute force method,
partition trees) or memory consuming (interval trees, KD trees),
or they need a lot of preprocessing time and external memory
(out-of-core methods). In this dissertation, a hybrid data
structure, the Conditioned Tree, is described, which can
be modified and optimized depending from the given main memory.
The Conditioned Tree is based on a partition tree
with pointers to other data structures of already known
methods.
In this way, various main memory sizes can be used for
extracting the isosurface within the lowest possible time.
Subject (DDC)
004 Computer Science
Keywords
Isofläche,Optimierung,Computergraphik,isosurface,optimization,computer graphics
Conference
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690
TOELKE, Jürgen, 2006. Optimierungsverfahren zur Isoflächen-Extraktion in der wissenschaftlichen Visualisierung [Dissertation]. Konstanz: University of KonstanzBibTex
@phdthesis{Toelke2006Optim-6382,
year={2006},
title={Optimierungsverfahren zur Isoflächen-Extraktion in der wissenschaftlichen Visualisierung},
author={Toelke, Jürgen},
address={Konstanz},
school={Universität Konstanz}
}
RDF
<rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/6382">
<dcterms:issued>2006</dcterms:issued>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:alternative>Optimization methods of isosurface extraction in scientific visualization</dcterms:alternative>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6382"/>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dc:format>application/pdf</dc:format>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:12:21Z</dcterms:available>
<dc:contributor>Toelke, Jürgen</dc:contributor>
<dcterms:title>Optimierungsverfahren zur Isoflächen-Extraktion in der wissenschaftlichen Visualisierung</dcterms:title>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6382/1/Diss_Toelke.pdf"/>
<dc:rights>terms-of-use</dc:rights>
<dc:language>deu</dc:language>
<dc:creator>Toelke, Jürgen</dc:creator>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6382/1/Diss_Toelke.pdf"/>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:12:21Z</dc:date>
<dcterms:abstract xml:lang="deu">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.</dcterms:abstract>
</rdf:Description>
</rdf:RDF>
Internal note
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Examination date of dissertation
July 24, 2006