CGAL 4.7 - 3D Boolean Operations on Nef Polyhedra: User Manual

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - 3D Boolean Operations on Nef Polyhedra

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
User Manual

\( \newcommand{\pyr}{\operatorname{Pyr}} \newcommand{\aff}{\operatorname{aff}} \)

Authors
  Peter Hachenberger and Lutz Kettner

# Introduction

In solid modeling, two major representation schemes are used: constructive solid geometry (CSG) and boundary representations (B-rep). Both have inherent strengths and weaknesses, see [3] for a discussion.

In CSG a solid is represented as a set-theoretic Boolean combination of primitive solid objects, such as blocks, prisms, cylinders, or toruses. The Boolean operations are not evaluated, instead, objects are represented implicitly with a tree structure; leaves represent primitive objects and interior nodes represent Boolean operations or rigid motions, e.g., translation and rotation. Algorithms on such a CSG-tree first evaluate properties on the primitive objects and propagate the results using the tree structure.

A B-rep describes the incidence structure and the geometric properties of all lower-dimensional features of the boundary of a solid. Surfaces are oriented to decide between the interior and exterior of a solid.

The class of representable objects in a CSG is usually limited by the choice of the primitive solids. A B-rep is usually limited by the choice for the geometry of the supporting curves for edges and the supporting surfaces for surface patches, and, in addition, the connectivity structure that is allowed. In particular, a B-rep is not always closed under Boolean set operations. As an example, the class of orientable 2-manifold objects is a popular and well understood class of surfaces commonly used for B-reps. They can be represented and manipulated efficiently, the data structures are compact in storage size, and many algorithms are simple. On the other side, this object class is not closed under Boolean set operations, as many examples can illustrate, such as the Figure shown above that can be generated using Boolean set operations on cubes. The vertices bounding the tunnel, or the edge connecting the "roof" with the cube are non-manifold situations.

In our implementation of Nef polyhedra in 3D, we offer a B-rep data structure that is closed under Boolean operations and with all their generality. Starting from halfspaces (and also directly from oriented 2-manifolds), we can work with set union, set intersection, set difference, set complement, interior, exterior, boundary, closure, and regularization operations (see Section Regularized Set Operations for an explaination of regularized set operations). In essence, we can evaluate a CSG-tree with halfspaces as primitives and convert it into a B-rep representation.

In fact, we work with two data structures; one that represents the local neighborhoods of vertices, which is in itself already a complete description, and a data structure that connects these neighborhoods up to a global data structure with edges, facets, and volumes. We offer a rich interface to investigate these data structures, their different elements and their connectivity. We provide affine (rigid) transformations and a point location query operation. We have a custom file format for storing and reading Nef polyhedra from files. We offer a simple OpenGL-based visualizer for debugging and illustrations.

# Definition

The theory of Nef polyhedra has been developed for arbitrary dimensions. The class `Nef_polyhedron_3` implements a boundary representation for the 3-dimensional case.

Definition: A Nef-poly-he-dron in dimension \( d\) is a point set \( P \subseteq \mathbb{R}^d\) generated from a finite number of open halfspaces by set complement and set intersection operations.

Set union, difference and symmetric difference can be reduced to intersection and complement. Set complement changes between open and closed halfspaces, thus the topological operations boundary, interior, exterior, closure and regularization are also in the modeling space of Nef polyhedra.

A face of a Nef polyhedron is defined as an equivalence class of local pyramids that are a characterization of the local space around a point.

Definition: A point set \( K \subseteq \mathbb{R}^d\) is called a cone with apex \( 0\), if \( K = \mathbb{R}^{+} K\) (i.e., \( \forall p \in K, \forall \lambda > 0: \lambda p \in K\)) and it is called a cone with apex \( x\), \( x \in \mathbb{R}^d\), if \( K = x + \mathbb{R}^{+} (K - x)\). A cone \( K\) is called a pyramid if \( K\) is a polyhedron.

Now let \( P \in \mathbb{R}^d\) be a polyhedron and \( x \in \mathbb{R}^d\). There is a neighborhood \( U_0(x)\) of \( x\) such that the pyramid \( Q := x + \mathbb{R}^{+} ((P \cap U(x)) - x)\) is the same for all neighborhoods \( U(x) \subseteq U_0(x)\). \( Q\) is called the local pyramid of \( P\) in \( x\) and denoted \( \pyr_P(x)\).

Definition: Let \( P \in \mathbb{R}^d\) be a polyhedron and \( x, y \in \mathbb{R}^d\) be two points. We define an equivalence relation \( x \sim y\) iff \( \pyr_P(x) = \pyr_P(y)\). The equivalence classes of \( \sim\) are the faces of \( P\). The dimension of a face \( s\) is the dimension of its affine hull, \( \dim s := \dim \aff s\).

In other words, a face \( s\) of \( P\) is a maximal non-empty subset of \( \mathbb{R}^d\) such that all of its points have the same local pyramid \( Q\) denoted \( \pyr_P(s)\). This definition of a face partitions \( \mathbb{R}^d\) into faces of different dimension. A face \( s\) is either a subset of \( P\), or disjoint from \( P\). We use this later in our data structure and store a selection mark in each face indicating its set membership.

Faces do not have to be connected. There are only two full-dimensional faces possible, one whose local pyramid is the space \( \mathbb{R}^d\) itself and the other with the empty set as a local pyramid. All lower-dimensional faces form the boundary of the polyhedron. As usual, we call zero-dimensional faces vertices and one-dimensional faces edges. In the case of polyhedra in space we call two-dimensional faces facets and the full-dimensional faces volumes. Faces are relative open sets, e.g., an edge does not contain its end-vertices.

We illustrate the definitions with an example in the plane. Given the closed halfspaces

\[ \begin{array}{lllll} h_1: y \ge 0,\ \ \ & h_2: x - y \ge 0,\ \ \ & h_3: x + y \le 3,\ \ \ & h_4: x - y \ge 1,\ \ \ & h_5: x + y \le 2, \end{array} \]

we define our polyhedron \( P := ( h_1 \cap h_2 \cap h_3) - ( h_4 \cap h_5)\).

The left figure illustrates the polyhedron with its partially closed and partially open boundary, i.e., vertex \( v_4, v_5, v_6\), and edges \( e_4\) and \( e_5\) are not part of \( P\). The local pyramids for the faces are \( \pyr_P(f_1) = \emptyset\) and \( \pyr_P(f_2) = \mathbb{R}^2\). Examples for the local pyramids of edges are the closed halfspace \( h_2\) for the edge \( e_1\), \( \pyr_P(e_1) = h_2\), and the open halfspace that is the complement of \( h_4\) for the edge \( e_5\), \( \pyr_P(e_5) = \{(x,y) | x - y < 1\}\). The edge \( e_3\) consists actually of two disconnected parts, both with the same local pyramid \( \pyr_P(e_3) = h_1\). In our data structure, we will represent the two connected components of the edge \( e_3\) separately. The figure on the right lists all local pyramids for this example.

The local pyramids of each vertex are represented by conceptually intersecting the local neighborhood with a small \( \varepsilon\)-sphere. This intersection forms a planar map on the sphere (see next two figures), which together with the set-selection mark for each item (i.e. vertices, edges, loops and faces) forms a two-dimensional Nef polyhedron embedded in the sphere. We add the set-selection mark for the vertex and call the resulting structure the sphere map of the vertex. We use the prefix \( s\) to distinguish the elements of the sphere map from the three-dimensional elements. See Chapter Chapter_2D_Boolean_Operations_on_Nef_Polygons_Embedded_on_the_Sphere for further details.

Having sphere maps for all vertices of our polyhedron is a sufficient but not easily accessible representation of the polyhedron. We enrich the data structure with more explicit representations of all the faces and incidences between them.

We depart slightly from the definition of faces in a Nef polyhedron; we represent the connected components of a face individually and do not implement additional bookkeeping to recover the original faces (e.g., all edges on a common supporting line with the same local pyramid) as this is not needed in our algorithms. We discuss features in the increasing order of dimension.

edges:
  We store two oppositely oriented edges for each edge and have a pointer from one oriented edge to its opposite edge. Such an oriented edge can be identified with an svertex in a sphere map; it remains to link one svertex with the corresponding opposite svertex in the other sphere map.
edge uses:
  An edge can have many incident facets (non-manifold situation). We introduce two oppositely oriented edge-uses for each incident facet; one for each orientation of the facet. An edge-use points to its corresponding oriented edge and to its oriented facet. We can identify an edge-use with an oriented sedge in the sphere map, or, in the special case also with an sloop. Without mentioning it explicitly in the remainder, all references to sedge can also refer to sloop.
facets:
  We store oriented facets as boundary cycles of oriented edge-uses. We have a distinguished outer boundary cycle and several (or maybe none) inner boundary cycles representing holes in the facet. Boundary cycles are linked in one direction. We can access the other traversal direction when we switch to the oppositely oriented facet, i.e., by using the opposite edge-use.
shells:
  The volume boundary decomposes into different connected components, the shells. A shell consists of a connected set of facets, edges, and vertices incident to this volume. Facets around an edge form a radial order that is captured in the radial order of sedges around an svertex in the sphere map. Using this information, we can trace a shell from one entry element with a graph search. We offer this graph traversal (to the user) in a visitor design pattern.
volumes:
  A volume is defined by a set of shells, one outer shell containing the volume and several (or maybe none) inner shells separating voids which are excluded from the volume.

For each face we store a label, e.g., a set-selection mark, which indicates whether the face is part of the solid or if it is excluded. We call the resulting data structure Selective Nef Complex, SNC for short [2]. However, in CGAL we identify the names and call the SNC data structure `Nef_polyhedron_3`.

# Infimaximal Box

We call a Nef polyhedron bounded if its boundary is bounded, i.e., finite, and unbounded otherwise. Note that unbounded point sets can have a bounded boundary, for example, the complement of a cube has an unbounded outer volume, but its boundary remains bounded.

Using a boundary representation, it is convenient (conceptually and in our implementation) to consider bounded Nef polyhedra only. Bounded Nef polyhedra are also closed under Boolean set operations. However, one needs to start with bounded primitives; the conceptually nice halfspaces cannot be used. Instead, we offer a construction from oriented 2-manifolds represented in a `Polyhedron_3`, see Section subsectionNef_3Polyhedron below.

In order to handle unbounded Nef polyhedra conceptually in the same way as we handle bounded Nef polyhedra, we intersect them with a bounding cubical volume of size \( [-R,R]^3\), where \( R\) is a symbolical unspecified value, which is finite but larger than all coordinate values that may occur in the bounded part of the polyhedron. As a result, each Nef polyhedron becomes bounded. We call the boundary of the bounding volume the infimaximal box [5].

We clip lines and rays at the infimaximal box. The intersection points with the infimaximal box are called non-standard points, which are points whose coordinates are \( -R\) or \( R\) in at least one dimension, and linear functions \( f(R)\) for the other dimensions. Such extended points (and developed from there also extended segments etc) are provided in CGAL with extended kernels - `Extended_cartesian` and `Extended_homogeneous`. They are regular CGAL kernels with a polynomial type as coordinate number type.

As long as an extended kernel is used, the full functionality provided by the `Nef_polyhedron_3` class is available. If a kernel that does not use polynomials to represent coordinates is used, it is not possible to create or load unbounded Nef polyhedra, but all other operations work as expected. We provided both possibilities, since the restriction to bounded Nef polyhedra improves considerably space requirements (plain number type instead of polynomial), and runtime performance.

# Regularized Set Operations

Since manifolds are not closed under Boolean operations, Requicha proposes to use regularized set operations [4], cgal:r-rrstm-80. A set is regular, if it equals the closure of its interior. A regularized set operation is defined as the standard set operation followed by a regularization of the result. Regularized sets are closed under regularized set operations.

Regularized set operations are important since they simplify the class of solids to exclude lower dimensional features and the boundary belongs to the point set. These properties are considered to reflect the nature of physical solids more closely.

Regularized polyhedral sets are a subclass of Nef polyhedra. We provide the `regularization` operation as a shortcut for the consecutive execution of the `interior` and the `closure` operations.

# Example Programs

The following example gives a first impression of how to instantiate and use `Nef_polyhedron_3`. We use the `Cartesian` kernel. All Cartesian and homogeneous kernels of CGAL are suitable if the number type parameter follows the usual requirements of being a model of the `FieldNumberType` concept for the Cartesian kernels, or the `RingNumberType` concept for the homogeneous kernels, respectively. Note however, that in the current state, the Nef polyhedron works only with CGAL kernels. The implementation makes use of CGAL specific functions in kernel objects, and does not yet offer a designed interface to a clean kernel concept that could be offered by an external kernel as well.

The example creates two Nef polyhedra - `N0` is the empty set, while `N1` represents the full space, i.e., the set of all points in the 3-dimensional space. The assertion assures that the empty set is the complement of the full space.

File Nef_3/nef_3_simple.cpp

#include <CGAL/Exact_integer.h>
#include <CGAL/Homogeneous.h>
#include <CGAL/Nef_polyhedron_3.h>
typedef CGAL::Homogeneous<CGAL::Exact_integer> Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron;
int main() {
Nef_polyhedron N0(Nef_polyhedron::EMPTY);
Nef_polyhedron N1(Nef_polyhedron::COMPLETE);
CGAL_assertion (N0 == N1.complement());
return 0;
}

## Construction and Comparison

This example shows the various constructors. We can create the empty set, which is also the default constructor, and the full space, i.e. all points of \( \mathbb{R}^3\) belong to the polyhedron. We can create a halfspace defined by a plane bounding it. It is only available if an extended kernel is used. The halfspace constructor has a second parameter that specifies whether the defining plane belongs to the point set (`Nef_polyhedron_3::INCLUDED`) or not (`Nef_polyhedron_3::EXCLUDED`). The default value is `Nef_polyhedron_3::INCLUDED`. Additionally, we can create a `Nef_polyhedron_3` from a `Polyhedron_3`, see the Section subsectionNef_3Polyhedron below.

We can compute the point sets of two Nef polyhedra for equality and proper subset relationships. We offer the usual comparison operators `==`, `!=`, `<=`, `>=`, `<` and `>`.

Nef polyhedra have the important feature that a representation that is called the reduced Würzburg structure is unique, i.e., two point sets of Nef polyhedra are equal if and only if the representations are equal. The proof for the reduced Würzburg structure carries over to our representation and the comparison operators are therefore trivial to implement.

File Nef_3/nef_3_construction.cpp

#include <CGAL/Exact_integer.h>
#include <CGAL/Extended_homogeneous.h>
#include <CGAL/Nef_polyhedron_3.h>
typedef CGAL::Extended_homogeneous<CGAL::Exact_integer> Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron;
typedef Nef_polyhedron::Plane_3 Plane_3;
int main() {
Nef_polyhedron N0;
Nef_polyhedron N1(Nef_polyhedron::EMPTY);
Nef_polyhedron N2(Nef_polyhedron::COMPLETE);
Nef_polyhedron N3(Plane_3( 1, 2, 5,-1));
Nef_polyhedron N4(Plane_3( 1, 2, 5,-1), Nef_polyhedron::INCLUDED);
Nef_polyhedron N5(Plane_3( 1, 2, 5,-1), Nef_polyhedron::EXCLUDED);
CGAL_assertion(N0 == N1);
CGAL_assertion(N3 == N4);
CGAL_assertion(N0 != N2);
CGAL_assertion(N3 != N5);
CGAL_assertion(N4 >= N5);
CGAL_assertion(N5 <= N4);
CGAL_assertion(N4 > N5);
CGAL_assertion(N5 < N4);
N5 = N5.closure();
CGAL_assertion(N4 >= N5);
CGAL_assertion(N4 <= N5);
return 0;
}

## Point Set Operations

As explained in the introduction, Nef polyhedra are closed under all Boolean set operations. The class `Nef_polyhedron_3` provides functions and operators for the most common ones: complement (`operator!`), union (`operator+`), difference (`operator-`), intersection (`operator*`) and symmetric difference (`operator^`). Additionally, the operators `*=`, `-=`, `*=` and `^=` are defined.

`Nef_polyhedron_3` also provides the topological operations `interior()`, `closure()` and `boundary()`. With `interior()` one deselects all boundary items, with `boundary()` one deselects all volumes, and with `closure()` one selects all boundary items.

File Nef_3/point_set_operations.cpp

#include <CGAL/Exact_integer.h>
#include <CGAL/Extended_homogeneous.h>
#include <CGAL/Nef_polyhedron_3.h>
typedef CGAL::Extended_homogeneous<CGAL::Exact_integer> Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron;
typedef Kernel::Plane_3 Plane_3;
int main() {
Nef_polyhedron N1(Plane_3( 1, 0, 0,-1));
Nef_polyhedron N2(Plane_3(-1, 0, 0,-1));
Nef_polyhedron N3(Plane_3( 0, 1, 0,-1));
Nef_polyhedron N4(Plane_3( 0,-1, 0,-1));
Nef_polyhedron N5(Plane_3( 0, 0, 1,-1));
Nef_polyhedron N6(Plane_3( 0, 0,-1,-1));
Nef_polyhedron I1(!N1 + !N2); // open slice in yz-plane
Nef_polyhedron I2(N3 - !N4); // closed slice in xz-plane
Nef_polyhedron I3(N5 ^ N6); // open slice in yz-plane
Nef_polyhedron Cube1(I2 * !I1);
Cube1 *= !I3;
Nef_polyhedron Cube2 = N1 * N2 * N3 * N4 * N5 * N6;
CGAL_assertion(Cube1 == Cube2); // both are closed cube
CGAL_assertion(Cube1 == Cube1.closure());
CGAL_assertion(Cube1 == Cube1.regularization());
CGAL_assertion((N1 - N1.boundary()) == N1.interior());
CGAL_assertion(I1.closure() == I1.complement().interior().complement());
CGAL_assertion(I1.regularization() == I1.interior().closure());
return 0;
}

## Transformation

Using the `std::transform` function, a Nef polyhedron can be translated, rotated and scaled. The usage is shown in the following example:

File Nef_3/transformation.cpp

#include <CGAL/Exact_integer.h>
#include <CGAL/Extended_homogeneous.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
//instead of
//typedef CGAL::Extended_homogeneous<CGAL::Exact_integer> Kernel;
// workaround for VC++
struct Kernel : public CGAL::Extended_homogeneous<CGAL::Exact_integer> {};
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron;
typedef Nef_polyhedron::Plane_3 Plane_3;
typedef Nef_polyhedron::Vector_3 Vector_3;
typedef Nef_polyhedron::Aff_transformation_3 Aff_transformation_3;
int main() {
Nef_polyhedron N(Plane_3(0,1,0,0));
Aff_transformation_3 transl(CGAL::TRANSLATION, Vector_3(5, 7, 9));
Aff_transformation_3 rotx90(1,0,0,
0,0,-1,
0,1,0,
1);
Aff_transformation_3 scale(3,0,0,
0,3,0,
0,0,3,
2);
N.transform(transl);
CGAL_assertion(N == Nef_polyhedron(Plane_3(0,1,0,-7)));
N.transform(rotx90);
CGAL_assertion(N == Nef_polyhedron(Plane_3(0,0,1,-7)));
N.transform(scale);
CGAL_assertion(N == Nef_polyhedron(Plane_3(0,0,2,-21)));
return 0;
}

## The Interface between Polyhedron_3 and Nef_polyhedron_3

`Nef_polyhedron_3` provides an interface for the conversion between polyhedral surfaces represented with the `Polyhedron_3` class and `Nef_polyhedron_3`. `Polyhedron_3` represents orientable 2-manifold objects with boundaries. However, we exclude surfaces with boundaries from the conversion to `Nef_polyhedron_3` since they have no properly defined volume.

Both conversion directions can only be performed if the boundary of the point set is an oriented closed 2-manifold. `Nef_polyhedron_3` provides the function `is_simple()` and `Polyhedron_3` provides the function `is_closed()` to test for this property. The usage is illustrated by the example program below.

The conversion gives us the possibility to use several file formats. `Polyhedron_3` can read the (`.off`) file format and can write the (`.off`), OpenInventor (`.iv`), VRML 1.0 and 2.0 (`.wrl`) and Wavefront Advanced Visualizer object format (`.obj`), see Section sectionPolyIO.

File Nef_3/interface_polyhedron.cpp

#include <CGAL/Exact_integer.h>
#include <CGAL/Homogeneous.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
#include <iostream>
typedef CGAL::Homogeneous<CGAL::Exact_integer> Kernel;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron;
typedef Kernel::Vector_3 Vector_3;
typedef Kernel::Aff_transformation_3 Aff_transformation_3;
int main() {
Polyhedron P;
std::cin >> P;
if(P.is_closed()) {
Nef_polyhedron N1(P);
Nef_polyhedron N2(N1);
Aff_transformation_3 aff(CGAL::TRANSLATION, Vector_3(2,2,0,1));
N2.transform(aff);
N1 += N2;
if(N1.is_simple()) {
N1.convert_to_polyhedron(P);
std::cout << P;
}
else
std::cerr << "N1 is not a 2-manifold." << std::endl;
}
}

## Using an Extended Kernel

The provided extended kernels are used the same way as any other CGAL kernel. The essential difference is, that coordinates are not represented by the number type that was used to parameterize the kernel type, but by a `Nef_polynomial` parametrized by that number type.

The example iterates all vertices of a given Nef polyhedron and decides whether it is an standard vertex or a vertex on the infimaximal box. Furthermore, it tests whether any of the vertices is at \( (R,R,R)\). Recall that \( R\) was the symbolical value, large but finite, for the size of the infimaximal box.

File Nef_3/extended_kernel.cpp

#include <CGAL/Exact_integer.h>
#include <CGAL/Extended_homogeneous.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
typedef CGAL::Exact_integer NT;
//instead of
//typedef CGAL::Extended_homogeneous<NT> Kernel;
// workaround for VC++
struct Kernel : public CGAL::Extended_homogeneous<NT> {};
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron;
typedef Nef_polyhedron::RT RT;
typedef Nef_polyhedron::Point_3 Point_3;
typedef Nef_polyhedron::Plane_3 Plane_3;
typedef Nef_polyhedron::Vertex_const_iterator Vertex_const_iterator;
int main() {
Nef_polyhedron N;
std::cin >> N;
Vertex_const_iterator v;
for(v = N.vertices_begin(); v != N.vertices_end(); ++v) {
Point_3 p(v->point());
if(p.hx().degree() > 0 || p.hy().degree() > 0 || p.hz().degree() > 0)
std::cout << "extended vertex at " << p << std::endl;
else
std::cout << "standard vertex at " << p << std::endl;
if(p == Point_3(RT(0,1), RT(0,1), RT(0,1)))
std::cout << " found vertex (right,back,top) of the infimaximal box"
<< std::endl;
}
return 0;
}

# File I/O

`Nef_polyhedron_3` provides an input and an output operator for a proprietary file format. It includes the complete incidence structure, the geometric data, and the marks of each item. The output depends on the output operators of the geometric primitives provided by the traits class, and on the output operators of the used number type. Therefore, it is necessary to use the same kernel and the same number type for input and output operations.

We recommend the use of the CGAL kernels `Homogeneous`, `Exact_predicates_exact_constructions_kernel`, or `Extended_homogeneous`. The homogeneous kernel provides reliable fast performance. In combination with `leda_integer` it is the fastest kernel for `Nef_polyhedron_3`. The `Exact_predicates_exact_constructions_kernel` uses filtering. In non-degenerate scenarios it's faster than the Homogeneous kernel. The most important advantage of the filtered kernel is that it is a Cartesian kernel, which allows the proper handling of OFF files using floating-point coordinates.

For effective filtering we had to change some concepts. The new concepts must be activated by using the `SNC_indexed_items`, because they don't apply for the extended kernels, yet. The new concepts also speed up `Nef_polyhedron_3` also in combination with all other standard kernels. The following example illustrates their usage.

File Nef_3/handling_double_coordinates.cpp

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron;
int main() {
Polyhedron P;
std::cin >> P;
Nef_polyhedron N(P);
std::cout << "Exact_predicates_exact_constructions_kernel + SNC_indexed_items"
<< std::endl
<< " allows efficient handling of input "
"using floating point coordinates"
<< std::endl;
if(N.is_simple()) {
N.convert_to_polyhedron(P);
std::cout << P;
}
else {
std::cout << N;
}
}

We provide compatibility between the input and output of various kernels. For most of the CGAL kernels it is possible to write a file constructed with one kernel and reread it with another. Also, it is possible to write a bounded Nef polyhedron using the `Extended_homogeneous` kernel and to read it afterwards using a standard kernel.

File Nef_3/nefIO.cpp

#include <CGAL/Exact_integer.h>
#include <CGAL/Homogeneous.h>
#include <CGAL/Extended_homogeneous.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
#include <fstream>
typedef CGAL::Exact_integer NT;
typedef CGAL::Homogeneous<NT> SK;
typedef CGAL::Extended_homogeneous<NT> EK;
typedef CGAL::Nef_polyhedron_3<SK> Nef_polyhedron_S;
typedef CGAL::Nef_polyhedron_3<EK> Nef_polyhedron_E;
int main() {
Nef_polyhedron_E E;
Nef_polyhedron_S S;
std::cin >> E;
if(E.is_bounded()) {
std::ofstream out("temp.nef3");
out << E;
std::ifstream in("temp.nef3");
in >> S;
}
}

# Further Example Programs

## Exploring a Sphere Map

A sphere map is explored by using the function `get_sphere_map()`, which returns the sphere map of the specified vertex as a `Nef_polyhedron_S2`. `Nef_polyhedron_S2` provides the functionality necessary for the exploration. Note, that one has to use the type `Nef_polyhedron_S2` as specified in `Nef_polyhedron_3` as is shown in the following example.

File Nef_3/exploration_SM.cpp

#include <CGAL/Exact_integer.h>
#include <CGAL/Homogeneous.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
typedef CGAL::Homogeneous<CGAL::Exact_integer> Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron_3;
int main() {
// We've put the typedefs here as VC7 gives us an ICE if they are global typedefs
typedef Nef_polyhedron_3::Vertex_const_iterator Vertex_const_iterator;
typedef Nef_polyhedron_3::Nef_polyhedron_S2 Nef_polyhedron_S2;
typedef Nef_polyhedron_S2::SVertex_const_handle SVertex_const_handle;
typedef Nef_polyhedron_S2::SHalfedge_const_handle SHalfedge_const_handle;
typedef Nef_polyhedron_S2::SHalfloop_const_handle SHalfloop_const_handle;
typedef Nef_polyhedron_S2::SFace_const_iterator SFace_const_iterator;
typedef Nef_polyhedron_S2::SFace_cycle_const_iterator
SFace_cycle_const_iterator;
Nef_polyhedron_3 N;
std::cin >> N;
Vertex_const_iterator v = N.vertices_begin();
Nef_polyhedron_S2 S(N.get_sphere_map(v));
int i=0;
SFace_const_iterator sf;
for(sf = S.sfaces_begin(); sf != S.sfaces_end(); sf++) {
SFace_cycle_const_iterator it;
std::cout << "the sface cycles of sface " << i++ << " start with an\n";
for(it = sf->sface_cycles_begin(); it != sf->sface_cycles_end(); it++) {
if (it.is_svertex())
std::cout << " svertex at position "
<< SVertex_const_handle(it)->point() << std::endl;
else if (it.is_shalfedge())
std::cout << " shalfedge from "
<< SHalfedge_const_handle(it)->source()->point() << " to "
<< SHalfedge_const_handle(it)->target()->point() << std::endl;
else if (it.is_shalfloop())
std::cout << " shalfloop lying in the plane "
<< SHalfloop_const_handle(it)->circle() << std::endl;
// other cases can not occur.
}
}
return 0;
}

## Exploring Shells

A shell of a Nef polyhedron is the connected part of the surface incident to a certain volume. Each halffacet, sface and shalfedge belongs to a single shell. The figure below illustrates the notion of a shell. It shows a Nef polyhedron with two volumes and three shells.

The first volume is the outer volume and the second volume is the interior of the cube. The first shell is the whole surface of the left object. The second shell is the outer surface of the right object, and the third shell is the inner surface of the right object.

In detail, the first shell consists of two halffacets, eight halfedges and four vertices. The second shell consists of the eight vertices of the cube plus the two endpoints of the antenna, all halffacets oriented outwards, and all halfedges. The third shell consists of the same eight vertices of the cube, plus the endpoint of the antenna that is in contact with the cube, all halffacets oriented inwards, and all halfedges (the same as for the second shell).

We discuss how sfaces, shalfedges, and sloops belong to the shells with a closeup view of the situation at the antenna foot. As you can see, there are three items on the sphere map - a shalfloop for each halffacet which intersects the sphere, and an svertex where the antenna intersects the sphere. The upper shalfloop lies on the halffacet which is oriented outwards and is therefore also oriented outwards. This shalfloop and the svertex belong to the second shell. The other shalfloop lies on the inwards oriented halffacet and is oriented inwards, too. This shalfloop belongs to the third shell.

`Nef_polyhedron_3` offers a visitor interface to explore a shell following the well-known visitor pattern [1]. The interface is illustrated by the following example.

File Nef_3/shell_exploration.cpp

#include <CGAL/Exact_integer.h>
#include <CGAL/Homogeneous.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
typedef CGAL::Homogeneous<CGAL::Exact_integer> Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron;
typedef Nef_polyhedron::Vertex_const_handle Vertex_const_handle;
typedef Nef_polyhedron::Halfedge_const_handle Halfedge_const_handle;
typedef Nef_polyhedron::Halffacet_const_handle Halffacet_const_handle;
typedef Nef_polyhedron::SHalfedge_const_handle SHalfedge_const_handle;
typedef Nef_polyhedron::SHalfloop_const_handle SHalfloop_const_handle;
typedef Nef_polyhedron::SFace_const_handle SFace_const_handle;
typedef Nef_polyhedron::Volume_const_iterator Volume_const_iterator;
typedef Nef_polyhedron::Shell_entry_const_iterator Shell_entry_const_iterator;
typedef Kernel::Point_3 Point_3;
class Shell_explorer {
bool first;
Vertex_const_handle v_min;
public:
Shell_explorer()
: first(true) {}
void visit(Vertex_const_handle v) {
if(first || CGAL::lexicographically_xyz_smaller(v->point(),v_min->point())) {
v_min = v;
first=false;
}
}
void visit(Halfedge_const_handle ) {}
void visit(Halffacet_const_handle ) {}
void visit(SHalfedge_const_handle ) {}
void visit(SHalfloop_const_handle ) {}
void visit(SFace_const_handle ) {}
Vertex_const_handle& minimal_vertex() { return v_min; }
void reset_minimal_vertex() { first = true; }
};
int main() {
Nef_polyhedron N;
std::cin >> N;
int ic = 0;
Volume_const_iterator c;
Shell_explorer SE;
CGAL_forall_volumes(c,N) {
std::cout << "Volume " << ic++ << std::endl;
int is = 0;
Shell_entry_const_iterator it;
CGAL_forall_shells_of(it,c) {
SE.reset_minimal_vertex();
N.visit_shell_objects(SFace_const_handle(it),SE);
Point_3 p(SE.minimal_vertex()->point());
std::cout << " minimal vertex of shell " << is++
<< " is at " << p << std::endl;
}
}
}

The function `visit_shell_objects(SFace_const_handle sf, Visitor& V)` explores a shell starting at the `sf`. The second argument expects any class providing the (possibly empty) functions `visit(Vertex_const_handle)`, `visit(Halfedge_const_handle)` (remember that Halfedge is the same type as SVertex), `visit(Halffacet_const_handle)`, `visit(SHalfedge_const_handle)`, `visit(SHalfloop_const_handle)` and `visit(SFace_const_handle)`. The `visit_shell_objects` function will call `visit` for each item belonging to the shell once. There are no further requirements on that class.

In the example, the class `Shell_explorer` is passed as second argument to `visit_shell_objects`. Its task is to find the lexicographically smallest vertex of a shell. Its internal state consists of three variables. The first one is a reference to the explored Nef polyhedron. This reference is often necessary to retrieve information from the Nef polyhedron. The second variable `v_min` stores the smallest vertex found so far, and the third variable `first` is initialized to `false` to signal that no vertex has been visited so far. After the first vertex has been visited `first` is changed to `true`.

`Shell_explorer` provides further member functions. After the exploration of a shell the `minimal_vertex` function retrieves the smallest vertex. The `reset_minimal_vertex` function allows one to use the same instance of `Shell_explorer` on multiple shells. In this case, the `reset_minimal_vertex` function has to be called between the exploration of two shells.

The example program uses the `Shell_explorer` for each shell of the given Nef polyhedron once and reports the smallest vertex of each shell to the standard output.

## Point Location

The `locate(Point_3 p)` function locates the point `p` in the Nef polyhedron and returns the item the point belongs to. The `locate` function returns an instance of `Object_handle`, which is a polymorphic handle type representing any handle type, no matter if it is mutable or const. For further usage of the result, the `Object_handle` has to be casted to the concrete handle type. The `assign()` function performs such a cast. It returns a Boolean that reports the success or the failure of of the cast. Looking at the possible return values of the `locate` function, the `Object_handle` can represent a `Vertex_const_handle`, a `Halfedge_const_handle`, a `Halffacet_handle`, or a `Volume_const_handle`. One of the four casts will succeed.

File Nef_3/nef_3_point_location.cpp

#include <CGAL/Exact_integer.h>
#include <CGAL/Homogeneous.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
typedef CGAL::Homogeneous<CGAL::Exact_integer> Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron_3;
typedef Kernel::Point_3 Point_3;
int main() {
//We've put the typedefs here as VC7 gives us an ICE if they are global typedefs
typedef Nef_polyhedron_3::Vertex_const_handle Vertex_const_handle;
typedef Nef_polyhedron_3::Halfedge_const_handle Halfedge_const_handle;
typedef Nef_polyhedron_3::Halffacet_const_handle Halffacet_const_handle;
typedef Nef_polyhedron_3::Volume_const_handle Volume_const_handle;
typedef Nef_polyhedron_3::Object_handle Object_handle;
Nef_polyhedron_3 N;
std::cin >> N;
Vertex_const_handle v;
Halfedge_const_handle e;
Halffacet_const_handle f;
Volume_const_handle c;
Object_handle o = N.locate(Point_3(0,0,0));
if(CGAL::assign(v,o))
std::cout << "Locating vertex" << std::endl;
else if(CGAL::assign(e,o))
std::cout << "Locating edge" << std::endl;
else if(CGAL::assign(f,o))
std::cout << "Locating facet" << std::endl;
else if(CGAL::assign(c,o))
std::cout << "Locating volume" << std::endl;
//other cases can not occur
return 0;
}

# Visualization

With the `Qt_widget_OpenGL` class an interface to OpenGL visualization via Qt is offered. The class knows how to handle mouse movements and clicks and how to move and scale the 3D object displayed in the widget. `Qt_widget_OpenGL` is a basis for writing Qt widgets displaying 3D objects. A user can derive a new class from `Qt_widget_OpenGL` which implements the drawing method and configures the context menus.

## Visualizing a 3D Nef polyhedron

`Qt_widget_Nef_3` implements the drawing methods for displaying instances of `Nef_polyhedron_3`. The following example shows how to set up an QApplication with a main widget of type `Qt_widget_Nef_3` and how to start the viewer.

File Nef_3/visualization_SNC.cpp

// Copyright (c) 2002 Max-Planck-Institute Saarbruecken (Germany)
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org).
// You can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation,
// either version 3 of the License, or (at your option) any later version.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL$
// $Id$
//
//
// Author(s) : Peter Hachenberger
#include <CGAL/basic.h>
#include <CGAL/Exact_integer.h>
#include <CGAL/Homogeneous.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
#include <CGAL/IO/Qt_widget_Nef_3.h>
#include <qapplication.h>
typedef CGAL::Homogeneous<CGAL::Exact_integer> Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron_3;
int main(int argc, char* argv[]) {
Nef_polyhedron_3 N;
std::cin >> N;
QApplication a(argc, argv);
CGAL::Qt_widget_Nef_3<Nef_polyhedron_3>* w =
new CGAL::Qt_widget_Nef_3<Nef_polyhedron_3>(N);
a.setMainWidget(w);
w->show();
return a.exec();
}

## Visualizing a Sphere Map

`Qt_widget_Nef_S2` is a widget implemented on the basis of `Qt_widget_OpenGL`. It can be used to visualize the sphere map of a vertex in a `Nef_polyhedron_3` using the interface between `Nef_polyhedron_S2` and `Nef_polyhedron_3`.

File Nef_3/visualization_SM.cpp

// Copyright (c) 2002 Max-Planck-Institute Saarbruecken (Germany)
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org).
// You can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation,
// either version 3 of the License, or (at your option) any later version.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL$
// $Id$
//
//
// Author(s) : Peter Hachenberger
#include <CGAL/basic.h>
#include <CGAL/Exact_integer.h>
#include <CGAL/Homogeneous.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
#include <CGAL/IO/Qt_widget_Nef_S2.h>
#include <qapplication.h>
typedef CGAL::Homogeneous<CGAL::Exact_integer> Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron_3;
int main(int argc, char* argv[]) {
// We've put the typedefs here as VC7 gives us an ICE if they are global typedefs
typedef Nef_polyhedron_3::Vertex_const_iterator Vertex_const_iterator;
typedef Nef_polyhedron_3::Nef_polyhedron_S2 Nef_polyhedron_S2;
Nef_polyhedron_3 N;
std::cin >> N;
Vertex_const_iterator v = N.vertices_begin();
Nef_polyhedron_S2 S(N.get_sphere_map(v));
QApplication a(argc, argv);
CGAL::Qt_widget_Nef_S2<Nef_polyhedron_S2>* w =
new CGAL::Qt_widget_Nef_S2<Nef_polyhedron_S2>(S);
a.setMainWidget(w);
w->show();
return a.exec();
}