Unterteilungsalgorithmen gehoeren zu den zuverlaessigsten Algorithmen für den Schnitt zweier parametrischer Flaechenpatches. Sie erfuellen vier der fünf Anforderungen an einen guten Schnittalgorithmus: sie sind genau, zuverlaessig, selbstaendig und auf alle Arten von parametrischen Flaechen anwendbar - eine Kombination von Eigenschaften, die kaum ein anderer Schnittalgorithmus besitzt. Die hohe Laufzeit und ein großer Speicherverbrauch bei steigenden Anforderungen an die Genauigkeit der Ergebnisse, verhinderten allerdings weitgehend den praktischen Einsatz reiner Unterteilungsalgorithmen. In dieser Arbeit werden mehrere Verbesserungen für Unterteilungsalgorithmen vorgeschlagen, deren zentrales Element eine neue Form von Huellkoerpern bildet: die Linearen Intervallabschaetzungen (LIEs). Für sie werden, neben einer formalen Definition und Charakterisierung, zwei unterschiedliche sichere Berechnungsmethoden vorgestellt, die auf speziellen Taylor Modellen und Intervallarithmetik, bzw. auf der Ausnutzung der inneren Struktur von Affinformen und der damit verbundenen affinen Arithmetik basieren. LIEs unterscheiden sich durch ihre parametrische Form essentiell von herkoemmlichen kompakten Huellkoerpern. Sie erlauben eine voellig neue Behandlung der bei Unterteilungsalgorithmen auftretenden Teilprobleme, wie Schnittest, Parametergebietsreduzierung, Unterteilungsstrategie und der Verfeinerung der Ergebnisse. Fuer diese Teilprobleme werden neue Algorithmen entwickelt, die an die speziellen Eigenschaften der LIEs angepaßt sind und deren Gesamtheit einen neuen effizienten Unterteilungsalgorithmus bildet.
de
dc.description.abstract
Subdivision algorithms are amongst the most reliable algorithms for the intersection of two parametric surface patches. They fit four of the five requirements on a good intersection algorithm: They are exact, reliable, independent and applicable to all kinds of parametric surfaces - a combination of properties that is hardly provided by any other type of algorithms to solve this problem. Though, the increasing consumption of memory and time in connection with higher requirements on the precision of the results inhibits the application of subdivision algorithms in practice up to now. Several improvements for subdivision algorithms are proposed in this work. The center of these improvements is build by a new kind of bounding volumes: {\em Linear Interval Estimations} (LIEs). Besides of a formal definition and characterization of LIEs, two reliable methods for the computation of LIEs are introduced based on a new understanding of the use of affine arithmetic and a special application of Taylor Models and interval arithmetic. LIEs differ in an essential way from conventional compact bounding volumes due to their parametric form. They allow a complete reconsideration of all occurring subproblems of subdivision algorithms, like the intersection test, the reduction of the parameter domains, subdivision strategies and the refinement of results. For all subproblems new algorithms adapted to the special characteristics of LIEs are proposed and combined to a new and efficient subdivision algorithm.
en
dc.language
Deutsch
-
dc.language.iso
de
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Fläche
de
dc.subject
Parameterdarstellung
de
dc.subject
Schnitt
de
dc.subject
Algorithmus
de
dc.title
Ein neuer Unterteilungsalgorithmus zur Schnittkurvenberechnung für parametrische Flächen
de
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Katja Bühler
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen
-
dc.type.qualificationlevel
Doctoral
-
dc.identifier.libraryid
AC03247686
-
dc.description.numberOfPages
121
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-10031
-
dc.thesistype
Dissertation
de
dc.thesistype
Dissertation
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
item.languageiso639-1
de
-
item.mimetype
application/pdf
-
item.openairecristype
http://purl.org/coar/resource_type/c_db06
-
item.fulltext
with Fulltext
-
item.openairetype
doctoral thesis
-
item.grantfulltext
open
-
item.openaccessfulltext
Open Access
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E186 - Institut für Computergraphik und Algorithmen