Boolean operations on 3D selective Nef complexes : data structure, algorithms, optimized implementation, experiments and applications

Abstract

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.