CGAL 4.5  3D Polyhedral Surface

#include <CGAL/Polyhedron_incremental_builder_3.h>
The auxiliary class Polyhedron_incremental_builder_3
supports the incremental construction of polyhedral surfaces, which is for example convenient when constructing polyhedral surfaces from file formats, such as the Object File Format (OFF)
[5], OpenInventor [7] or VRML [1], [6]. Polyhedron_incremental_builder_3
needs access to the internal halfedge data structure of type HDS
of the polyhedral surface. It is intended to be used within a modifier, see Modifier_base
.
The incremental builder might be of broader interest for other uses of the halfedge data structures, but it is specifically bound to the definition of polyhedral surfaces given here. During construction all conditions of polyhedral surfaces are checked and in case of violation an error status is set. A diagnostic message will be issued to std::cerr
if the verbose
flag has been set at construction time.
The incremental construction starts with a list of all point coordinates and concludes with a list of all facet polygons. Edges are not explicitly specified. They are derived from the vertex incidence information provided from the facet polygons. The polygons are given as a sequence of vertex indices. The halfedge data structure HDS
must support vertices (i.e., Supports_halfedge_vertex
\( \equiv\) Tag_true
). Vertices and facets can be added in arbitrary order as long as a call to add_vertex_to_facet()
refers only to a vertex index that is already known. Some methods return already handles to vertices, facets, and halfedges newly constructed. They can be used to initialize additional fields, however, the incidences in the halfedgedata structure are not stable and are not allowed to be changed.
The incremental builder can work in two modes: RELATIVE_INDEXING
(the default), in which a polyhedral surface already contained in the halfedge data structure is ignored and all indices are relative to the newly added surface, or ABSOLUTE_INDEXING
, in which all indices are absolute indices including an already existing polyhedral surface. The former mode allows to create easily independent connected components, while the latter mode allows to to continue the construction of an existing surface, the absolute indexing allows to address existing vertices when creating new facets.
CGAL::Polyhedron_3<Traits>
HalfedgeDS
CGAL::Modifier_base
Example
A modifier class creates a new triangle in the halfedge data structure using the incremental builder.
File Polyhedron/polyhedron_prog_incr_builder.cpp
Types  
typedef unspecified_type  HalfedgeDS 
halfedge data structure HDS .  
typedef unspecified_type  Point_3 
point type of the vertex.  
typedef unspecified_type  size_type 
size type.  
typedef HalfedgeDS::Vertex_handle  Vertex_handle 
typedef HalfedgeDS::Halfedge_handle  Halfedge_handle 
typedef HalfedgeDS::Face_handle  Facet_handle 
Constants  
enum  { RELATIVE_INDEXING, ABSOLUTE_INDEXING } 
two different indexing modes. More...  
Creation  
Polyhedron_incremental_builder_3 (HDS &hds, bool verbose=false)  
stores a reference to the halfedge data structure hds of a polyhedral surface in its internal state. More...  
Surface Creation  
To build a polyhedral surface, the following regular expression gives the correct and allowed order and nesting of method calls from this section:  
void  begin_surface (size_type v, size_type f, size_type h=0, int mode=RELATIVE_INDEXING) 
starts the construction. More...  
Vertex_handle  add_vertex (const Point_3 &p) 
adds a new vertex for p and returns its handle.  
Facet_handle  begin_facet () 
starts a new facet and returns its handle.  
void  add_vertex_to_facet (size_type i) 
adds a vertex with index i to the current facet. More...  
Halfedge_handle  end_facet () 
ends a newly constructed facet. More...  
void  end_surface () 
ends the construction.  
Additional Operations  
template<class InputIterator >  
Halfedge_handle  add_facet (InputIterator first, InputIterator beyond) 
is a synonym for begin_facet() , a call to add_vertex_to_facet() for each value in the range [first,beyond) , and a call to end_facet() . More...  
template<class InputIterator >  
bool  test_facet (InputIterator first, InputIterator beyond) 
returns true if a facet described by the vertex indices in the range [first,beyond) can be successfully inserted, e.g., with add_facet(first,beyond) . More...  
Vertex_handle  vertex (std::size_t i) 
returns handle for the vertex of index i , or Vertex_handle if there is no i th vertex.  
bool  error () const 
returns error status of the builder.  
void  rollback () 
undoes all changes made to the halfedge data structure since the last begin_surface() in relative indexing, and deletes the whole surface in absolute indexing. More...  
bool  check_unconnected_vertices () 
returns true if unconnected vertices are detected. More...  
bool  remove_unconnected_vertices () 
returns true if all unconnected vertices could be removed successfully. More...  
anonymous enum 
CGAL::Polyhedron_incremental_builder_3< HDS >::Polyhedron_incremental_builder_3  (  HDS &  hds, 
bool  verbose = false 

) 
stores a reference to the halfedge data structure hds
of a polyhedral surface in its internal state.
An existing polyhedral surface in hds
remains unchanged. The incremental builder appends the new polyhedral surface. If verbose
is true
, diagnostic messages will be printed to cerr
in case of malformed input data.
Halfedge_handle CGAL::Polyhedron_incremental_builder_3< HDS >::add_facet  (  InputIterator  first, 
InputIterator  beyond  
) 
is a synonym for begin_facet()
, a call to add_vertex_to_facet()
for each value in the range [first,beyond)
, and a call to end_facet()
.
Returns the return value of end_facet()
.
InputIterator
is std::size_t
. All indices must refer to vertices already added. void CGAL::Polyhedron_incremental_builder_3< HDS >::add_vertex_to_facet  (  size_type  i) 
adds a vertex with index i
to the current facet.
The first point added with add_vertex()
has the index 0 if mode
was set to RELATIVE_INDEXING
, otherwise the first vertex in the referenced hds
has the index 0.
void CGAL::Polyhedron_incremental_builder_3< HDS >::begin_surface  (  size_type  v, 
size_type  f,  
size_type  h = 0 , 

int  mode = RELATIVE_INDEXING 

) 
starts the construction.
v
is the number of new vertices to expect, f
the number of new facets, and h
the number of new halfedges. If h
is unspecified (== 0
) it is estimated using Euler's equation (plus 5% for the so far unknown holes and genus of the object). These values are used to reserve space in the halfedge data structure hds
. If the representation supports insertion these values do not restrict the class of constructible polyhedra. If the representation does not support insertion the object must fit into the reserved sizes.
If mode
is set to ABSOLUTE_INDEXING
the incremental builder uses absolute indexing and the vertices of the old polyhedral surface can be used in new facets (needs preprocessing time linear in the size of the old surface). Otherwise relative indexing is used starting with new indices for the new construction.
bool CGAL::Polyhedron_incremental_builder_3< HDS >::check_unconnected_vertices  (  ) 
returns true
if unconnected vertices are detected.
If verbose
was set to true
(see the constructor above) debug information about the unconnected vertices is printed.
Halfedge_handle CGAL::Polyhedron_incremental_builder_3< HDS >::end_facet  (  ) 
ends a newly constructed facet.
Returns the handle to the halfedge incident to the new facet that points to the vertex added first. The halfedge can be safely used to traverse the halfedge cycle around the new facet.
bool CGAL::Polyhedron_incremental_builder_3< HDS >::remove_unconnected_vertices  (  ) 
returns true
if all unconnected vertices could be removed successfully.
This happens either if no unconnected vertices had appeared or if the halfedge data structure supports the removal of individual elements.
void CGAL::Polyhedron_incremental_builder_3< HDS >::rollback  (  ) 
undoes all changes made to the halfedge data structure since the last begin_surface()
in relative indexing, and deletes the whole surface in absolute indexing.
It needs a new call to begin_surface()
to start inserting again.
bool CGAL::Polyhedron_incremental_builder_3< HDS >::test_facet  (  InputIterator  first, 
InputIterator  beyond  
) 
returns true
if a facet described by the vertex indices in the range [first,beyond)
can be successfully inserted, e.g., with add_facet(first,beyond)
.
InputIterator
is std::size_t
. All indices must refer to vertices already added.