Robust and Efficient Boolean Operations |
Mads Dueholm, Esben Erland
|
| Abstract | This thesis presents a thorough study of Boolean operations on triangle based boundary representations. A complete algorithm for performing the operations is developed with special emphasis on speed and robustness. To achieve proper speed it is necessary to reduce the complexity of the Boolean operation. To achieve this reduction spatial data structures are considered and a thorough analysis of four different data structures is performed with respect to geometric tests and construction time. Robustness is achieved by eliminating redundancies in the intersection part of the algorithm and by isolating geometrical predicates in all parts of the algorithm. These predicates are made exact by using arbitrary precision arithmetic based on so-called expansions that only employ normal floating point operations. The expansions are implemented independently of the predicates allowing for flexible use within general floating point computation. A mesh decimation scheme is applied to remove degenerate triangles from the output of the algorithm, thereby increasing robustness when meshes are involved in several Boolean operations. Aspects of Delaunay triangulations and closest distance computations are also considered in the design of the algorithm to provide flexibility and consistency.
We shed light upon the limitations of the arbitrary precision approach and argue why the algorithm - as a result of these limitations - is unable to provide infinite robustness. Despite these limitations we argue that the algorithm has superior robustness when compared to similar tolerance based algorithms and is able to perform Boolean operations very efficiently even when Boolean operations involve complicated meshes. |
| Type | Master's thesis [Industrial collaboration] |
| Year | 2006 |
| Publisher | Informatics and Mathematical Modelling, Technical University of Denmark, DTU |
| Address | Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby |
| Series | IMM-Thesis-2006-89 |
| Note | |
| BibTeX data | [bibtex] |
| IMM Group(s) | Image Analysis & Computer Graphics |