Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation. Miguel Granados, Peter Hachenberger, Susan Hert, Lutz Kettner, Kurt Mehlhorn and Michael Seel. In: Proc. of the 11th Annu. European Sympos. Algorithms (ESA'03), Budapest, Hungary. LNCS 2832, Springer, pp. 654-666, September, 2003.
We describe a data structure for three-dimensional Nef complexes, algorithms for boolean operations on them, and our implementation of data structure and algorithms. Nef polyhedra were introduced by W. Nef in his seminal 1978 book on polyhedra. They are the closure of half-spaces under boolean operations and can represent non-manifold situations, open and closed boundaries, and mixed dimensional complexes. Our focus lies on the generality of the data structure, the completeness of the algorithms, and the exactness and efficiency of the implementation. In particular, all degeneracies are handled.
[PDF]
[PostScript]
[CGAL Home Page]