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 CGAL_Polyhedron can store polyhedrons 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 CGAL_Halfedge_data_structure_polyhedron_default_3<R> chooses the list representation and CGAL_Point_3<R> for the geometric information stored with vertices and CGAL_Plane_3<R> for the geometric information stored with facets.
A utility class CGAL_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 polyhedrons.
Section introduces the polyhedral surface class CGAL_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.
| |
surface normal vector stored in facets.
| |
| |
plane equation stored in facets.
|
|
| the surface normal vector. |
|
|
|
|
| the plane equation. |
|
|
The nested types below are either equal to CGAL_Tag_true or CGAL_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 CGAL_Tag_true
Supports_halfedge_facet
CGAL_Tag_true.
Supports_facet_plane
CGAL_Tag_true Supports_halfedge_facet
CGAL_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 polyhedrons including
halfedge pointer and a plane equation of type
CGAL_Plane_3<R>.
|
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.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::Point Point; typedef Polyhedron::Vertex_iterator Vertex_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); CGAL_set_ascii_mode( cout); Vertex_iterator begin = P.vertices_begin(); for ( ; begin != P.vertices_end(); ++begin) cout << "(" << begin->point() << ") "; cout << 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.h> #include <algo.h> #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); for_each( P.facets_begin(), P.facets_end(), compute_plane_equations); CGAL_set_pretty_mode( cout); Facet_iterator begin = P.facets_begin(); for ( ; begin != P.facets_end(); ++begin) cout << begin->plane() << 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 CGAL_Project_point<Vertex> Project_point; typedef CGAL_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.h> #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_point; typedef CGAL_Iterator_project<Vertex_iterator, Project_point, 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( cout); cout << "OFF" << endl; cout << P.size_of_vertices() << ' ' << P.size_of_facets() << " 0" << endl; copy( Point_iterator( P.vertices_begin()), Point_iterator( P.vertices_end()), ostream_iterator<Point>(cout,"\n")); Facet_iterator i = P.facets_begin(); for ( ; 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); cout << CGAL_circulator_size(j) << " "; do { size_t d = 0; distance( P.vertices_begin(), j->vertex(), d); cout << " " << d; } while ( ++j != i->facet_begin()); cout << endl; } return 0; }
The CGAL_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; /* A modifier creating a triangle with the incremental builder. */ template < class HDS> class Build_triangle : public CGAL_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; }