Lutz Kettner: Projects: 3D Nef Polyhedra in CGAL

Table of


Definition:   A Nef-polyhedron in dimension d is a point set P⊆ℜd generated from a finite number of open halfspaces by set complement and set intersection operations [Nef78].

This definition emcompasses many definitions of linearly bounded complexes and has the outstanding properties that it is closed under boolean operations and can represent non-manifold situations, that it supports faces of different dimensions at the same time and unbounded faces, and that can distinguish between open and closed sets.

We, i.e., Peter Hachenberger and Lutz Kettner, continued the work of Michael Seel to bring Nef polyhedra as defined by the Swiss mathematician Walter Nef into CGAL. While Michael Seel provided planar Nef polyhedra, we implemented Nef polyhedra in 3-dimensional space. The implementation was first released as part of CGAL 3.1 in December 2004. Our implementation follows the design spirit of CGAL and the Exact Geometric Computing paradigm. Our implementation is complete (it handles all degenerate cases) and correct (it does not suffer from rounding problems of floating point arithmetic), and it is efficient, which we document in the paper [2] below and with the corresponding data and results published on this page.

Selected Publications


Boolean Operations on 3D Selective Nef Complexes: Optimized Implementation and Experiments. Peter Hachenberger and Lutz Kettner. In: Proc. of 2005 ACM Symposium on Solid and Physical Modeling (SPM), Cambridge, MA. pp. 163-174, June, 2005. © ACM 2005. [Abstract] [PDF] [PostScript]


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. [Abstract] [PDF] [PostScript]


For each of the six experiments we give a short description, the complete timing results, and the complete input data sets. An addition to the short description of the experiment we refer to our paper [2] for more details. The timing results are shown in a graph and also available for download in the tabular .sus format of the ExpLab tools described here. The input data sets are given in the custom .nef3 format of our implementation and, where applicable, in the .sat format for the ACIS comparisons. In addition, since the data sets can be quit large, we provide also the CGAL generator program for these data sets and, where applicable, the ACIS Scheme program.

Experiment Tetgrid

  1. Create a regular N3 grid T of random tetrahedra:
  2. Create a regular (N-1)3 grid C of such cubes.
  3. Align T and C such that the grid nodes of C are at the centers of the grid cells of T.
  4. Measure time for T ∪ C.

Experiment Quadratic

  1. Construct N parallel cuboids of size 10000×1×100 spaced one unit apart in y-direction as object W.
  2. Construct N parallel cuboids of size 1× 10000×100 spaced one unit apart in x-direction as object W'.
  3. Align W and W' at their lower front left corner.
  4. Move W' along the z-axis for fifty units.
  5. Measure time for W ∪ W'

Experiment ComplexFacet + ComplexMinusSmall

  1. Create a cube C of size N3.
  2. Create a N × N × 1 grid of tetrahedra G:
  3. ComplexFacet: Measure time for C'=C ∪ G.
  4. Create a cube c of size 23 such that its vertices match centers of the grid cells.
  5. ComplexMinusSimple: Measure time for C'-c

Experiment ComplexSphereMap

  1. Create triangles ti,t'i,i=1,…, N+1 with the following properties:
    1. the first vertex of each triangle ti/t'i is located at the origin.
    2. the second vertex of each triangle ti/t'i has coordinates (N,-N+2*i,N)/(N,N,-N+2*i)
    3. the third vertex of each triangle ti has coordinates (N,-N+2*i,-N)/(N,-N,-N+2*i)
  2. unite triangles ti/t'i as object T/T'.
  3. Measure time for T ∪ T'

Experiment RotCylinders

  1. Create a right cylinder C:
  2. Create a copy C' of C.
  3. Rotate C' around its vertical centerline by α degrees.
  4. Measure time for C ∪ C'.

Lutz Kettner (<surname> Last modified on Friday, 11-Nov-2005 14:00:29 MET.