Nef polyhedra in 3-dimensional Space

Definition

Nef polyhedra in CGAL

Publications

• 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. Proc. of the 11th Annu. European Sympos. Algorithms (ESA'03), Budapest, Hungary. LNCS 2832, Springer, pp. 654-666, September, 2003.
• Boolean Operations on 3D Selective Nef Complexes: Optimized Implementation and Experiments. Peter Hachenberger and Lutz Kettner. To appear in Proc. of 2005 ACM Symposium on Solid and Physical Modeling (SPM)

Experiment Tetgrid

1. Create a regular N³ grid T of random tetrahedra:
• Generate four vertices for each tetrahedron randomly in a half-open fixed-size cube.
• Let these cubes form a regular N³ grid.
2. Create a regular (N-1)³ 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 N³.
2. Create a N × N × 1 grid of tetrahedra G:
• Generate four vertices for each tetrahedron randomly in a half-open unit cube, but at least one vertex in the lower half and one vertex in the upper half of the cube.
• Let the cubes form a regular N × N × 1 grid and place the grid such that each tetrahedron penetrates the top surface of C.
3. ComplexFacet: Measure time for C'=C ∪ G.
4. Create a cube c of size 2³ such that its vertices match centers of the grid cells.
5. ComplexMinusSimple: Measure time for C'-c

Experiment ComplexSphereMap

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

Experiment RotCylinders

1. Create a right cylinder C:
• the base of C is a regular polygon with N sides.
• the base is parallel to the xy-plane.
2. Create a copy C' of C.
3. Rotate C' around its vertical centerline by α degrees.
4. Measure time for C ∪ C'.