A new Subdivision Algorithm for the Intersection of Parametric Surfaces
No Thumbnail Available
Date
June 2001
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Bühler
Text.PhDThesis
Abstract
Unterteilungsalgorithmen gehören zu den zuverlässigsten Algorithmen für den Schnitt zweier parametrischer Flächenpatches. Sie erfüllen vier der fünf Anforderungen an einen guten Schnittalgorithmus: Sie sind genau, zuverlässig, selbständig und auf alle Arten von parametrischen Flächen 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 Hüllkörpern bildet: die Linearen Intervallabschätzungen (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 herkömmlichen kompakten Hüllkörpern. Sie erlauben eine völlig neue Behandlung der bei Unterteilungsalgorithmen auftretenden Teilprobleme, wie Schnittest, Parametergebietsreduzierung, Unterteilungsstrategie und der Verfeinerung der Ergebnisse. Für diese Teilprobleme werden neue Algorithmen entwickelt, die an die speziellen Eigenschaften der LIEs angepaßt sind und deren Gesamtheit einen neuen effizienten Unterteilungsalgorithmus bildet. - 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: 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 occuring 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.
Description