Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25905
Titel: Boolean operations on 3D selective Nef complexes : data structure, algorithms, optimized implementation, experiments and applications
Verfasser: Hachenberger, Peter
Sprache: Englisch
Erscheinungsjahr: 2006
SWD-Schlagwörter: Nef-Polyeder
Datenstruktur
Freie Schlagwörter: Boolesche Operationen
nef polyhedra
data structure
Boolean operations
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: Nef polyhedra in d-dimensional space are the closure of half-spaces under boolean set operations. Consequently, they can represent non-manifold situations, open and closed sets, mixed-dimensional complexes, and they are closed under all boolean and topological operations, such as complement and boundary. The generality of Nef complexes is essential for some applications. In this thesis, we present a new data structure for the boundary representation of three-dimensional Nef polyhedra and efficient algorithms for boolean operations. We use exact arithmetic to avoid well known problems with floating-point arithmetic and handle all degeneracies. Furthermore, we present important optimizations for the algorithms, and evaluate this optimized implementation with extensive experiments. The experiments supplement the theoretical runtime analysis
Nef-Polyeder sind d-dimensionale Punktmengen, die durch eine endliche Anzahl boolescher Operationen über Halbräumen generiert werden. Sie sind abgeschlossen hinsichtlich boolescher und topologischer Operationen. Als Konsequenz daraus können sie nicht-mannigfaltige Situationen, offene und geschlossene Mengen und gemischt-dimensionale Komplexe darstellen. Die Allgemeinheit von Nef-Komplexen ist unentbehrlich für einige Anwendungen. In dieser Doktorarbeit stellen wir eine neue Datenstruktur vor, die eine Randdarstellung von dreidimensionalen Nef-polyedern und Algorithmen für boolesche Operationen realisiert. Wir benutzen exakte Arithmetik um die bekannten Probleme mit Gleitkommaarithmetik und Degeneriertheiten zu vermeiden. Außerdem präsentieren wir wichtige Optimierungen der Algorithmen und bewerten die optimierte Implementierung an Hand umfassender Experimente. Weitere Experimente belegen die theoretische Laufzeitanalyse und vergleichen unsere Implementation mit dem kommerziellen CAD kernel ACIS. ACIS is meistens bis zu sechs mal schneller, aber es gibt auch Beispiele bei denen ACIS scheitert. Nef-Polyeder können bei einer Vielzahl von Anwendungen eingesetzt werden. Wir präsentieren einfache Implementationen zweier Anwendungen - von der visuellen Hülle und von der Minkowski-Summe zwei abgeschlossener Nef-Polyeder.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-13357
hdl:20.500.11880/25961
http://dx.doi.org/10.22028/D291-25905
Erstgutachter: Mehlhorn, Kurt
Tag der mündlichen Prüfung: 1-Dez-2006
SciDok-Publikation: 16-Nov-2007
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Dissertation_1778_Hach_Pete_2006.pdf1,24 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.