Polyhedral Surfaces (Polyhedron_3)

Definition

A polyhedral surface Polyhedron_3<Traits,HDS> in three dimensions consists of vertices $$V, edges $$E, facets $$F and an incidence relation on them. Each edge is represented by two halfedges with opposite orientations.

Vertices represent points in space. Edges are straight line segments between two endpoints. Facets are planar polygons without holes defined by the circular sequence of halfedges along their boundary. The polyhedral surface itself is allowed to have holes. The halfedges along the boundary of a hole are called border halfedges and have no incident facets. An edge is a border edge if one of its halfedges is a border halfedge. A surface is closed if it contains no border halfedges. A closed surface is a boundary representation for polyhedra in three dimensions. The convention is that the halfedges are oriented counterclockwise around facets as seen from the outside of the polyhedron. An implication is that the halfedges are oriented clockwise around the vertices. The notion of the solid side of a facet as defined by the halfedge orientation extends to polyhedral surfaces with border edges although they do not define a closed object. If normal vectors are considered for the facets, normals point outwards (following the right hand rule).

One implication of the definition is that the polyhedral surface is always an orientable and oriented 2-manifold with border edges, i.e. the neighborhood of each point on the polyhedral surface is either homeomorphic to a disc or to a half disc, except for vertices where many holes and surfaces can meet. Another implication is that the smallest representable surface is a triangle (for polyhedral surfaces with border edges) or a tetrahedron (for polyhedra). Boundary representations of orientable 2-manifolds are closed under Euler operations. They are extended with operations that create or close holes in the surface.

Other intersections besides the incidence relation are not allowed, although they are not automatically handled, since self intersections are not easy to check efficiently. Polyhedron_3<Traits,HDS> does only maintain the combinatorial integrity of the polyhedral surface (using Euler operations) and does not consider the coordinates of the points or any geometric information.

The class Polyhedron_3<Traits,HDS> can represent polyhedral surfaces as well as polyhedra. The interface is designed in such a way that it is easy to ignore border edges and work only with polyhedra.

The sequence of edges can be ordered in the data structure on request such that the sequence starts with the non-border edges and ends with the border edges. Border edges are then itself ordered such that the halfedge which is incident to the facet came first and the halfedge incident to the hole came thereafter. This normalization step counts simultaneously the number of border edges. This number is zero if and only if the surface is a closed polyhedron. Note that this class does not maintain this counter during further modifications. There is no automatic caching done for auxiliary information.

The class Polyhedron_3<Traits,HDS> expects a model of the Polyhedron_traits concept from Section  as a first template argument, and a model of the Halfedge_data_structure concept from Section  with the additional requirements from Section  as a second template argument.

#include <CGAL/Polyhedron_3.h>

Types

Polyhedron_3<Traits,HDS>::Traits
	traits class.
Polyhedron_3<Traits,HDS>::Halfedge_data_structure
	halfedge data structure HDS.
Polyhedron_3<Traits,HDS>::Vertex
	vertex type.
Polyhedron_3<Traits,HDS>::Halfedge
	halfedge type.
Polyhedron_3<Traits,HDS>::Facet
	facet type.
Polyhedron_3<Traits,HDS>::Size
	type for size values.
Polyhedron_3<Traits,HDS>::Difference
	type for difference values.

Types for the (optionally) associated geometry. If the specific item is not supported the type is void*.

Polyhedron_3<Traits,HDS>::Point
	point stored in vertices.
Polyhedron_3<Traits,HDS>::Plane
	plane equation stored in facets.
Polyhedron_3<Traits,HDS>::Normal
	normal vector stored in facets.

The following handles, iterators and circulators have appropriate non-mutable counterparts. The mutable types are assignable to their non-mutable counterparts. Both circulators are assignable to the Halfedge_iterator. The iterators are assignable to the respective handle types. Wherever the handles appear in function parameter lists, the appropriate iterator can be used as well.

The iterator category is defined through the polyhedron traits class for all iterators. The circulators are bidirectional if the halfedge in the polyhedron traits class provides a member function prev(), otherwise they are of the forward category.

Polyhedron_3<Traits,HDS>::Vertex_handle
	handle to vertex.
Polyhedron_3<Traits,HDS>::Halfedge_handle
	handle to halfedge.
Polyhedron_3<Traits,HDS>::Facet_handle
	handle to facet.
Polyhedron_3<Traits,HDS>::Vertex_iterator
	iterator over all vertices.
Polyhedron_3<Traits,HDS>::Halfedge_iterator
	iterator over all halfedges.
Polyhedron_3<Traits,HDS>::Facet_iterator
	iterator over all facets.
Polyhedron_3<Traits,HDS>::Halfedge_around_vertex_circulator
	circulator of halfedges around a vertex.
Polyhedron_3<Traits,HDS>::Halfedge_around_facet_circulator
	circulator of halfedges around a facet.
Polyhedron_3<Traits,HDS>::iterator_category
	iterator category of all the iterators.
Polyhedron_3<Traits,HDS>::circulator_category
	circulator category of all the circulators.

Creation

Polyhedron_3<Traits,HDS> P ( Traits traits = Traits());
Polyhedron_3<Traits,HDS> P ( Size v, Size h, Size f, Traits traits = Traits());
	a polyhedron P with storage reserved for $$v vertices, $$h halfedges, and $$f facets. The reservation sizes are a hint for optimizing storage allocation.

void	P.reserve ( Size v, Size h, Size f)
		reserves storage for $$v vertices, $$h halfedges, and $$f facets. The reservation sizes are a hint for optimizing storage allocation. If the capacity is already greater than the requested size nothing happens. If the capacity changes all iterators and circulators might invalidate.
Halfedge_handle	P.make_tetrahedron ()
		adds a new tetrahedron to the polyhedral surface. Returns an arbitrary halfedge of the tetrahedron.
Halfedge_handle	P.make_tetrahedron ( Point p1, Point p2, Point p3, Point p4)
		adds a new tetrahedron to the polyhedral surface with its vertices initialized with $$p1, p2, p3 and $$p4. Returns that halfedge of the tetrahedron which incident vertex is initialized with $$p1, the incident vertex of the next halfedge with $$p2, and the vertex thereafter with $$p3. The remaining fourth vertex is initialized with $$p4
Halfedge_handle	P.make_triangle ()	adds a new triangle with border edges to the polyhedral surface. Returns an arbitrary, non-border halfedge of the triangle.
Halfedge_handle	P.make_triangle ( Point p1, Point p2, Point p3)
		adds a new triangle with border edges to the polyhedral surface with its vertices initialized with $$p1, p2 and $$p3. Returns that non-border halfedge of the triangle which incident vertex is initialized with $$p1, the incident vertex of the next halfedge with $$p2, and the vertex thereafter with $$p3.

Access Member Functions

Size	P.size_of_vertices ()
		number of vertices.
Size	P.size_of_halfedges ()
		number of halfedges (incl. border halfedges).
Size	P.size_of_facets ()
		number of facets.
Size	P.capacity_of_vertices ()
		space reserved for vertices.
Size	P.capacity_of_halfedges ()
		space reserved for halfedges.
Size	P.capacity_of_facets ()
		space reserved for facets.
std::size_t	P.bytes ()	bytes used for the polyhedron.
std::size_t	P.bytes_reserved ()
		bytes reserved for the polyhedron.
Vertex_iterator	P.vertices_begin ()
		iterator over all vertices.
Vertex_iterator	P.vertices_end ()	past-the-end iterator and null-handle.
Halfedge_iterator	P.halfedges_begin ()
		iterator over all halfedges.
Halfedge_iterator	P.halfedges_end ()	past-the-end iterator and null-handle.
Facet_iterator	P.facets_begin ()	iterator over all facets (excluding holes).
Facet_iterator	P.facets_end ()	past-the-end iterator and null-handle.
Traits	P.traits ()	returns the traits class.

Geometric Predicates

bool	P.is_triangle ( Halfedge_const_handle h)
		true iff the connected component denoted by $$h is a triangle.
bool	P.is_tetrahedron ( Halfedge_const_handle h)
		true iff the connected component denoted by $$h is a tetrahedron.

Euler Operators (Combinatorial Modifications)

The following Euler operations modify consistently the combinatorial structure of the polyhedral surface. The geometry remains unchanged.

Halfedge_handle	P.split_facet ( Halfedge_handle h, Halfedge_handle g)
		splits the facet incident to h and g into two facets with a new diagonal between the two vertices denoted by h and g respectively. The second (new) facet is a copy of the first facet. It returns the new diagonal. The time is proportional to the distance from h to g around the facet. Precondition: h and g are incident to the same facet. h != g (no loops). h->next() != g and g->next() != h (no multi-edges).
Halfedge_handle	P.join_facet ( Halfedge_handle h)
		joins the two facets incident to $$h. The facet incident to h->opposite() gets removed. Both facets might be holes. Returns the predecessor of $$h around the facet. The invariant join_facet( split_facet( h, g)) returns $$h and keeps the polyhedron unchanged. The time is proportional to the size of the facet removed and the time to compute h->prev(). Precondition: HDS supports removal of halfedges and facets. The degree of both vertices incident to $$h is at least three (no antennas).

Halfedge_handle	P.split_vertex ( Halfedge_handle h, Halfedge_handle g)
		splits the vertex incident to h and g into two vertices and connects them with a new edge. The second (new) vertex is a copy of the first vertex. It returns the new edge. The time is proportional to the distance from h to g around the vertex. Precondition: h and g are incident to the same vertex. h != g (no antennas).
Halfedge_handle	P.join_vertex ( Halfedge_handle h)
		joins the two vertices incident to $$h. The vertex denoted by h->opposite() gets removed. Returns the predecessor of $$h around the vertex. The invariant join_vertex( split_vertex( h, g)) returns $$h and keeps the polyhedron unchanged. The time is proportional to the degree of the vertex removed and the time to compute h->prev(). Precondition: HDS supports removal of vertices and halfedges. The size of both facets incident to $$h is at least four (no multi-edges).

Euler Operators Modifying Genus

Halfedge_handle	P.split_loop ( Halfedge_handle h, Halfedge_handle i, Halfedge_handle j)
		cuts the polyhedron into two parts along the cycle $$(h,i,j). Three new vertices (one copy for each vertex in the cycle) and three new halfedges (one copy for each halfedge in the cycle), and two new triangles will be created. $$h,i,j will be incident to the first new triangle. The return value will be a halfedge iterator denoting the new halfedge of the second new triangle which was h->opposite() beforehand. Precondition: $$h,i,j are distinct, consecutive halfedges of the polyhedron and form a cycle: i.e. h->vertex() == i->opposite()->vertex(), ..., j->vertex() == h->opposite()->vertex(). The six facets incident to $$h,i,j are all distinct.
Halfedge_handle	P.join_loop ( Halfedge_handle h, Halfedge_handle g)
		glues the boundary of two facets together. Both facets and the vertices of the facet loop $$g gets removed. Returns $$h. Both facets might be holes. The invariant join_loop( h, split_loop( h, i, j)) returns $$h and keeps the polyhedron unchanged. Precondition: HDS supports removal of vertices, halfedges, and facets. The facets denoted by $$h and $$g are different and have an equal degree (i.e. number of edges) $$ 3.

Modifying Facets and Holes

Halfedge_handle	P.make_hole ( Halfedge_handle h)
		removes the incident facet of $$h and changes all halfedges incident to the facet into border edges. Returns $$h. See erase_facet(h) for a more generalized variant. Precondition: HDS supports removal of facets. None of the incident halfedges of the facet is a border edge.
Halfedge_handle	P.fill_hole ( Halfedge_handle h)
		fills a hole with a newly created facet. Makes all border halfedges of the hole denoted by $$h incident to the new facet. Returns $$h. Precondition: h.is_border().

Halfedge_handle	P.add_vertex_and_facet_to_border ( Halfedge_handle h, Halfedge_handle g)
		creates a new facet within the hole incident to $$h and $$g by connecting the tip of $$g with the tip of $$h with two new halfedges and a new vertex and filling this separated part of the hole with a new facet, such that the new facet is incident to $$g. Returns the halfedge of the new edge that is incident to the new facet and the new vertex. Precondition: h->is_border(), g->is_border(), h != g, and $$g can be reached along the same hole starting with $$h.

Halfedge_handle	P.add_facet_to_border ( Halfedge_handle h, Halfedge_handle g)
		creates a new facet within the hole incident to $$h and $$g by connecting the tip of $$g with the tip of $$h with a new halfedge and filling this separated part of the hole with a new facet, such that the new facet is incident to $$g. Returns the halfedge of the new edge that is incident to the new facet. Precondition: h->is_border(), g->is_border(), h != g, h->next() != g, and $$g can be reached along the same hole starting with $$h.

Erasing

void	P.erase_facet ( Halfedge_handle h)
		removes the incident facet of $$h and changes all halfedges incident to the facet into border edges or removes them from the polyhedral surface if they were already border edges. See make_hole(h) for a more specialized variant. Precondition: HDS supports removal.
void	P.erase_connected_component ( Halfedge_handle h)
		removes the vertices, halfedges, and facets that belong to the connected component of $$h. Precondition: HDS supports removal.
void	P.erase_all ()	removes all vertices, halfedges, and facets.

Operations with Border Halfedges

Halfedges incident to an hole are called border halfedges. An edge is a border edge if one of its two halfedges is a border halfedges. The only requirement to work with border halfedges is that the Halfedge class provides a member function is_border() returning a bool. Usually, the halfedge data structure supports facets and a NULL facet pointer will indicate a border halfedge, but this is not the only possibility. The is_border() predicate divides the edges into two classes, the border edges and the non-border edges. The following normalization reorganizes the sequential storage of the edges such that the non-border edges precedes the border edges, and that for each border edge the latter one of the two halfedges is a border halfedge (the first one is a non-border halfedge in conformance with the polyhedral surface definition). The normalization stores the number of border halfedges and the halfedge iterator the border edges start at within the data structure. Halfedge insertion or removal and changing the border status of a halfedge may invalidate these values, which are not automatically updated.

void	P.normalize_border ()
		sorts halfedges such that the non-border edges precedes the border edges. For each border edge the halfedge iterator will reference the halfedge incident to the facet right before the halfedge incident to the hole.
Size	P.size_of_border_halfedges ()
		number of border halfedges. Precondition: normalize_border() has been called and no halfedge insertion or removal and no change in border status of the halfedges have occurred since then.
Size	P.size_of_border_edges ()
		number of border edges. Since each border edge of a polyhedral surface has exactly one border halfedge, this number is equal to size_of_border_halfedges(). Precondition: normalize_border() has been called and no halfedge insertion or removal and no change in border status of the halfedges have occurred since then.
Halfedge_iterator	P.border_halfedges_begin ()
		halfedge iterator starting with the border edges. The range [halfedges_begin(), border_halfedges_begin()) denotes all non-border edges. The range [border_halfedges_begin(), halfedges_end()) denotes all border edges. Precondition: normalize_border() has been called and no halfedge insertion or removal and no change in border status of the halfedges have occurred since then.

Miscellaneous

void

P.inside_out ()

reverses facet orientation (incl. normal or plane equations).

void	P.delegate ( Modifier_base<HDS>& m)
		calls the operator() of the modifier $$m. See Modifier_base in the Support Library Manual for a description of modifier design and its usage. Precondition: The polyhedral surface must be valid when the modifier returns from execution.

bool	P.is_valid ( bool verbose = false, int level = 0)
		returns true if the polyhedral surface is combinatorially consistent. If verbose is true, statistics are printed to std::cerr. For level == 1 the normalization of the border edges is checked too. This method checks in particular level 3 of Halfedge_data_structure_decorator::is_valid from Section  and that each facet is at least a triangle and that the two incident facets of a non-border edge are distinct.
bool	P.normalized_border_is_valid ( HDS hds, bool verbose = false)
		returns true if the border halfedges are in normalized representation, which is when enumerating all halfedges with the iterator: The non-border edges precedes the border edges and for border edges, the second halfedge is the border halfedge. The halfedge iterator border_halfedges_begin() denotes the first border edge. If verbose is true, statistics are printed to std::cerr.

Types for Tagging Optional Features

The following types are equal to either Tag_true or Tag_false, depending on whether the named feature is supported or not.

Polyhedron_3<Traits,HDS>::Supports_vertex_halfedge
	Vertex::halfedge().
Polyhedron_3<Traits,HDS>::Supports_vertex_point
	Vertex::point().
Polyhedron_3<Traits,HDS>::Supports_halfedge_prev
	Halfedge::prev().
Polyhedron_3<Traits,HDS>::Supports_halfedge_vertex
	Halfedge::vertex().
Polyhedron_3<Traits,HDS>::Supports_halfedge_facet
	Halfedge::facet().
Polyhedron_3<Traits,HDS>::Supports_facet_halfedge
	Facet::halfedge().
Polyhedron_3<Traits,HDS>::Supports_facet_plane
	Facet::plane().
Polyhedron_3<Traits,HDS>::Supports_facet_normal
	Facet::normal().
Polyhedron_3<Traits,HDS>::Supports_removal
	supports the removal of individual elements of a surface.