This chapter presents polyhedral surfaces in three dimensions. They are a collection of vertices, edges and facets with an incidence relationship on them. The organization beneath is a halfedge data structure which restricts the class of representable surfaces to orientable 2-manifolds - with and without boundary. In the case of a closed surface we call it a polyhedron.
Chapter 
gives a design overview of the
Halfedge_data_structure concept, its flexibility, predefined
models and their potential use in data structures such as polyhedral
surfaces, see also [Ket98]. A halfedge data structure is an
edge-centered data structure. Each edge is decomposed into two
halfedges with opposite orientations. Functions are provided to access
incident facets and vertices. For a facet or a vertex one of the
incident halfedges can be accessed. A halfedge data structure is
responsible of storing the halfedges, vertices and facets, as well as
maintaining their incidences through a pointer based interface.
A polyhedral surface is based on a model of the Halfedge_data_structure concept and adds combinatorial integrity (e.g. internal pointers cannot be simply written), abstract concepts to access the items, such as iterators and circulators, high level operations and ease-of-use, for example Euler operators. It also adds knowledge about the geometric information kept in the data structure, such as points or plane equations, with a traits class.
The class Polyhedron can store polyhedra and polyhedral surfaces. The template argument for the Halfedge_data_structure allows to choose among the different possible models, for example a list or a vector based representation. Using a vector provides random access for the elements in the polyhedral surface and is more space efficient, but elements cannot be deleted arbitrarily. Using a list allows arbitrary deletions, but provides only bidirectional iterators and is less space efficient. The provided default model for the halfedge data structure Halfedge_data_structure_polyhedron_default_3<R> chooses the list representation and Point_3<R> for the geometric information stored with vertices and Plane_3<R> for the geometric information stored with facets.
A utility class Polyhedron_incremental_builder_3 helps in creating polyhedral surfaces from a list of points followed by a list of facets represented as indices into the point list. This is particularly useful in combination with usual file formats for polyhedra.
Section introduces the polyhedral surface
class Polyhedron_3, its three local classes Vertex,
Halfedge, and Facet. Section
defines the Polyhedron_traits concept, which adds the geometric
knowledge to the polyhedral surface, and
Section names the provided models for
this concept. Section presents additional
requirements for the Halfedge_data_structure concept that were
recognized by the polyhedral surface and states the default models
that fulfills these requirements, see also Chapter on
halfedge data structure. Section
continues with the description of the utility class for incremental
construction of polyhedral surfaces.
Section concludes this chapter with examples
using polyhedral surfaces.
The additional requirements allow to work with normal vectors or plane equations associated to facets as flexible as with the point type associated to vertices. The storage of either a normal vector or a plane equation in a facet is optional.
A halfedge data structure used for polyhedral surfaces must be a model
of the Halfedge_data_structure concept as described in
Section and additionally provides the following types
and operations for the local Facet type to support optionally
surface normals or plane equations for facets.
Types for (optionally) associated geometry in facets. If they are not supported the respective types are void*.
|
| |
|
surface normal vector stored in facets.
| |
|
| |
|
plane equation stored in facets.
| |
The member functions for the normal vector or the plane equation are only needed if the respective feature is supported. If plane equations are supported, a member function for the normal vector is necessary, though only with a value semantic of the return value (no reference as return value).
|
|
| the surface normal vector. |
|
|
|
|
|
|
| the plane equation. |
|
|
|
|
The nested types below are either equal to Tag_true or Tag_false, depending on whether the named member function is supported or not.
|
| |
|
normal().
| |
|
| |
|
plane().
| |
The following dependencies among these options and those of the Halfedge type must be regarded:
Supports_facet_normal Tag_true
Supports_halfedge_facet Tag_true.
Supports_facet_plane Tag_true
Supports_halfedge_facet Tag_true.
CGAL currently provides a model for the Facet_base concept
specifically tailored for polyhedral surfaces. Other models can be found
in Section .
|
| |
|
| |
|
defines the maximal facet functionality for polyhedra including
halfedge pointer and a plane equation of type Plane_3<R>.
| |
Vertex_min_base, ..., Facet_max_base, and
Halfedge_data_structure_polyhedron_default_3.
Examples of different halfedge data structures can be found in
Section .
The first example instantiates a polyhedron using the default traits class, the default halfedge data structure, and creates a tetrahedron.
// polyhedron_prog_simple.C
// -----------------------------------------------------------
#include <CGAL/Cartesian.h>
#include <CGAL/Halfedge_data_structure_polyhedron_default_3.h>
#include <CGAL/Polyhedron_default_traits_3.h>
#include <CGAL/Polyhedron_3.h>
typedef CGAL::Cartesian<double> R;
typedef CGAL::Halfedge_data_structure_polyhedron_default_3<R> HDS;
typedef CGAL::Polyhedron_default_traits_3<R> Traits;
typedef CGAL::Polyhedron_3<Traits,HDS> Polyhedron;
typedef Polyhedron::Halfedge_handle Halfedge_handle;
int main() {
Polyhedron P;
Halfedge_handle h = P.make_tetrahedron();
CGAL_assertion( P.is_tetrahedron( h));
return 0;
}
This example creates a tetrahedron initialized with four points. In addition it demonstrates the use of the vertex iterator and the access to the point in the vertices. The output of the program will be (1 0 0) (0 1 0) (0 0 1) (0 0 0).
// polyhedron_prog_tetra.C
// -----------------------------------------------------------
#include <CGAL/Cartesian.h>
#include <iostream>
#include <CGAL/Halfedge_data_structure_polyhedron_default_3.h>
#include <CGAL/Polyhedron_default_traits_3.h>
#include <CGAL/Polyhedron_3.h>
typedef CGAL::Cartesian<double> R;
typedef CGAL::Halfedge_data_structure_polyhedron_default_3<R> HDS;
typedef CGAL::Polyhedron_default_traits_3<R> Traits;
typedef CGAL::Polyhedron_3<Traits,HDS> Polyhedron;
typedef Polyhedron::Point Point;
typedef Polyhedron::Vertex_iterator Vertex_iterator;
int main() {
Point p( 1.0, 0.0, 0.0);
Point q( 0.0, 1.0, 0.0);
Point r( 0.0, 0.0, 1.0);
Point s( 0.0, 0.0, 0.0);
Polyhedron P;
P.make_tetrahedron( p, q, r, s);
CGAL::set_ascii_mode( std::cout);
Vertex_iterator begin = P.vertices_begin();
for ( ; begin != P.vertices_end(); ++begin)
std::cout << "(" << begin->point() << ") ";
std::cout << std::endl;
return 0;
}
This example computes the plane equations for the facets of a tetrahedron. The actual plane computation is provided in the user defined function compute_plane_equations. We assume here strictly convex facets and exact arithmetic. In our example a homogeneous representation with int coordinates is sufficient. The output of the program are the four plane equations.
// polyhedron_prog_normals.C
// -----------------------------------------------------------
#include <CGAL/Homogeneous.h>
#include <iostream>
#include <algorithm>
#include <CGAL/Halfedge_data_structure_polyhedron_default_3.h>
#include <CGAL/Polyhedron_default_traits_3.h>
#include <CGAL/Polyhedron_3.h>
typedef CGAL::Homogeneous<int> R;
typedef CGAL::Halfedge_data_structure_polyhedron_default_3<R> HDS;
typedef CGAL::Polyhedron_default_traits_3<R> Traits;
typedef CGAL::Polyhedron_3<Traits,HDS> Polyhedron;
typedef Polyhedron::Point Point;
typedef Polyhedron::Plane Plane;
typedef Polyhedron::Halfedge_handle Halfedge_handle;
typedef Polyhedron::Facet Facet;
typedef Polyhedron::Facet_iterator Facet_iterator;
void compute_plane_equations( Facet& f) {
Halfedge_handle h = f.halfedge();
f.plane() = Plane( h->opposite()->vertex()->point(),
h->vertex()->point(),
h->next()->vertex()->point());
};
int main() {
Point p( 1, 0, 0);
Point q( 0, 1, 0);
Point r( 0, 0, 1);
Point s( 0, 0, 0);
Polyhedron P;
P.make_tetrahedron( p, q, r, s);
std::for_each( P.facets_begin(), P.facets_end(), compute_plane_equations);
CGAL::set_pretty_mode( std::cout);
Facet_iterator begin = P.facets_begin();
for ( ; begin != P.facets_end(); ++begin)
std::cout << begin->plane() << std::endl;
return 0;
}
It might be preferable to have an iterator enumerating all points directly instead of all vertices as in the previous example. Such an iterator could be used in other algorithms, for example a convex hull computation. The following declaration gives us such a point iterator.
#include <CGAL/Iterator_project.h>
#include <CGAL/function_objects.h>
typedef Polyhedron::Vertex Vertex;
typedef Polyhedron::Vertex_iterator Vertex_iterator;
typedef Polyhedron::Point Point;
typedef Polyhedron::Difference Difference;
typedef Polyhedron::iterator_category iterator_category;
typedef Project_point<Vertex> Project_point;
typedef Iterator_project<Vertex_iterator, Project_point,
Point&, Point*, Difference, iterator_category> Point_iterator;
The for-loop of the previous example could now be replaced with the following loop:
Point_iterator begin = P.vertices_begin();
for ( ; begin != P.vertices_end(); ++begin)
cout << "(" << (*begin) << ") ";
The following example creates a tetrahedron and writes it to cout using the Object File Format (OFF) [Phi94]. The example makes advanced use of STL algorithms (copy, distance), STL ostream_iterator and CGAL circulators.
// polyhedron_prog_off.C
// -----------------------------------------------------------
#include <CGAL/Cartesian.h>
#include <iostream>
#include <CGAL/Halfedge_data_structure_polyhedron_default_3.h>
#include <CGAL/Polyhedron_default_traits_3.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/Iterator_project.h>
#include <CGAL/function_objects.h>
typedef CGAL::Cartesian<double> R;
typedef CGAL::Halfedge_data_structure_polyhedron_default_3<R> HDS;
typedef CGAL::Polyhedron_default_traits_3<R> Traits;
typedef CGAL::Polyhedron_3<Traits,HDS> Polyhedron;
typedef Polyhedron::Difference Difference;
typedef Polyhedron::iterator_category Iterator_category;
typedef Polyhedron::Point Point;
typedef Polyhedron::Vertex Vertex;
typedef Polyhedron::Vertex_iterator Vertex_iterator;
typedef Polyhedron::Facet_iterator Facet_iterator;
typedef Polyhedron::Halfedge_around_facet_circulator
Halfedge_around_facet_circulator;
typedef CGAL::Project_point<Vertex> Project;
typedef CGAL::Iterator_project<Vertex_iterator, Project,
Point&, Point*, Difference, Iterator_category> Point_iterator;
int main() {
Point p( 0.0, 0.0, 0.0);
Point q( 1.0, 0.0, 0.0);
Point r( 0.0, 1.0, 0.0);
Point s( 0.0, 0.0, 1.0);
Polyhedron P;
P.make_tetrahedron( p, q, r, s);
// Write polyhedron on Object File Format (OFF).
CGAL::set_ascii_mode( std::cout);
std::cout << "OFF" << std::endl;
std::cout << P.size_of_vertices() << ' '
<< P.size_of_facets() << " 0" << std::endl;
std::copy( Point_iterator( P.vertices_begin()),
Point_iterator( P.vertices_end()),
std::ostream_iterator<Point>( std::cout, "\n"));
for ( Facet_iterator i = P.facets_begin(); i != P.facets_end(); ++i) {
Halfedge_around_facet_circulator j = i->facet_begin();
// Facets in polyhedral surfaces are at least triangles.
CGAL_assertion( CGAL::circulator_size(j) >= 3);
std::cout << CGAL::circulator_size(j) << " ";
do {
std::size_t d = 0;
std::distance( P.vertices_begin(), j->vertex(), d);
std::cout << " " << d;
} while ( ++j != i->facet_begin());
std::cout << std::endl;
}
return 0;
}
The Polyhedron_incremental_builder_3 class is used to create a triangle using the modifier mechanism as described in the Support Library Manual.
// polyhedron_prog_incr_builder.C
// -----------------------------------------------------------
#include <CGAL/Cartesian.h>
#include <CGAL/Halfedge_data_structure_polyhedron_default_3.h>
#include <CGAL/Polyhedron_default_traits_3.h>
#include <CGAL/Polyhedron_incremental_builder_3.h>
#include <CGAL/Polyhedron_3.h>
typedef CGAL::Cartesian<double> R;
typedef CGAL::Halfedge_data_structure_polyhedron_default_3<R> HDS;
typedef CGAL::Polyhedron_default_traits_3<R> Traits;
typedef CGAL::Polyhedron_3<Traits,HDS> Polyhedron;
using CGAL::Modifier_base;
// A modifier creating a triangle using the incremental builder.
template < class HDS>
class Build_triangle : public Modifier_base<HDS> {
public:
Build_triangle() {}
void operator()( HDS& hds) {
// Postcondition: `hds' is a valid polyhedral surface.
CGAL::Polyhedron_incremental_builder_3<HDS> B( hds, true);
B.begin_surface( 3, 1, 6);
typedef typename HDS::Point Point;
B.add_vertex( Point( 0, 0, 0));
B.add_vertex( Point( 1, 0, 0));
B.add_vertex( Point( 0, 1, 0));
B.begin_facet();
B.add_vertex_to_facet( 0);
B.add_vertex_to_facet( 1);
B.add_vertex_to_facet( 2);
B.end_facet();
B.end_surface();
}
};
int main() {
Polyhedron P;
Build_triangle<HDS> triangle;
P.delegate( triangle);
CGAL_assertion( P.is_triangle( P.halfedges_begin()));
return 0;
}