An Incremental Builder for Polyhedral Surfaces

Definition

Polyhedron_incremental_builder_3<HDS> is an auxiliary class that supports the incremental construction of polyhedral surfaces. This is for example convenient when constructing polyhedral surfaces from file formats like the Object File Format (OFF) [Phi94], OpenInventor [Wer94] or VRML [BPP95, VRM96]. Polyhedron_incremental_builder_3<HDS> 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 in the Support Library Manual.

The incremental builder might be of broader interest for other halfedge data structures as well, 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 printed 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 $$ Tag_true). The correct protocol of method calls to build a polyhedral surface is given as a regular expression below. Vertices and facets can be added in arbitrary order as long as add_vertex_to_facet() refers only to vertex indices that are already known.

begin_surface $$(add_vertex $$| $$(begin_facet add_vertex_to_facet$$* end_facet$$))* end_surface

Types

Polyhedron_incremental_builder_3<HDS>::Halfedge_data_structure
	halfedge data structure HDS.
Polyhedron_incremental_builder_3<HDS>::Point
	its point type.
Polyhedron_incremental_builder_3<HDS>::Size
	its size type.

Creation

Polyhedron_incremental_builder_3<HDS> B ( 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 std::cerr in case of malformed input data.

Operations

void	B.begin_surface ( Size v, Size f, Size h = 0)
		starts the construction. $$v is the number of vertices to expect, $$f the number of facets, and $$h the number of 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.
void	B.add_vertex ( Point p)
		adds $$p to the vertex list.
void	B.begin_facet ()	starts a facet.
void	B.add_vertex_to_facet ( Size i)
		adds a vertex with index $$i to the current facet. The first point added with add_vertex() has the index 0.
void	B.end_facet ()	ends a facet.
void	B.end_surface ()	ends the construction.
bool	B.error ()	returns error status of the builder.
void	B.rollback ()	undoes all changes made to the halfedge data structure since the last begin_surface().
bool	B.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.
bool	B.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.