Reference Manual

Peter Hachenberger, Sven Oesau

This packages provides two functions for computing a set of convex volumes that cover a bounded polyhedron. The CGAL::convex_decomposition_3() splits provides a decomposition into \(O(r^2)\) convex pieces, where \( r\) is the number of edges, whose adjacent facets form an angle of more than 180 degrees with respect to the polyhedron's interior. This bound is worst-case optimal. The CGAL::approximate_convex_decomposition() instead splits the convex hull of the polyhedron into a set of convex volumes. While these convex volumes cover additional space outside of the polyhedron, the computation is fast for any chosen number of convex volumes.

Introduced in: CGAL 3.5
BibTeX: cgal:h-emspe-25b
License: GPL
Windows Demo: CGAL Lab

Classified Reference Pages

Functions

• CGAL::approximate_convex_decomposition(FaceGraph)
• CGAL::convex_decomposition_3(NefPolyhedron_3)

Functions
template<typename NefPolyhedron_3 >
void	CGAL::convex_decomposition_3 (NefPolyhedron_3 &N)
	The function convex_decomposition_3() inserts additional facets into the given Nef polyhedronN`, such that each bounded marked volume (the outer volume is unbounded) is subdivided into convex pieces.
template<typename FaceGraph , typename OutputIterator , typename NamedParameters = parameters::Default_named_parameters>
std::size_t	CGAL::approximate_convex_decomposition (const FaceGraph &tmesh, OutputIterator out_volumes, const NamedParameters &np=parameters::default_values())
	approximates the closed input mesh by a number of convex volumes.

Function Documentation

approximate_convex_decomposition()

template<typename FaceGraph , typename OutputIterator , typename NamedParameters = parameters::Default_named_parameters>

std::size_t CGAL::approximate_convex_decomposition	(	const FaceGraph &	tmesh,
		OutputIterator	out_volumes,
		const NamedParameters &	np = parameters::default_values()
	)

#include </home/runner/work/cgal/cgal/Surface_mesh_decomposition/include/CGAL/approximate_convex_decomposition.h>

approximates the closed input mesh by a number of convex volumes.

The input mesh is voxelized and the voxels intersecting with the mesh are labeled as surface. The remaining voxels are labeled as outside or inside. In a next step, the convex hull of the mesh is hierarchically split until the volume_error threshold is satisfied or the maximum_depth is reached. Finally, a greedy pairwise merging combines smaller convex volumes until maximum_number_of_convex_volumes is met.

Template Parameters

FaceGraph	a model of HalfedgeListGraph, and FaceListGraph
OutputIterator	must be an output iterator accepting variables of type std::pair<std::vector<geom_traits::Point_3>, std::vector<std::array<unsigned int, 3> > >.
NamedParameters	a sequence of Named Parameters

Parameters

tmesh	the input triangle mesh to approximate by convex volumes
out_volumes	output iterator into which convex volumes are recorded
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

maximum_number_of_voxels gives an upper bound of the number of voxels. The longest bounding box side will have a length of the cubic root of maximum_number_of_voxels rounded down. Cannot be smaller than 512. Type: unsigned int Default: 1,000,000
maximum_depth maximum depth of hierarchical splits Type: unsigned int Default: 10
refitting refitting of convex volumes after split phase Type: Boolean Default: true
maximum_number_of_convex_volumes maximum number of convex volumes produced by the method Type: unsigned int Default: 16
volume_error maximum difference in fraction of volumes of the local convex hull with the sum of voxel volumes. If surpassed, the convex hull will be split if the maximum_depth has not been reached yet. Type: double Default: 0.01
split_at_concavity If true, the local box of a convex hull is split at the concavity along the longest axis of the bounding box. Otherwise, it is split in the middle of the longest axis, which is faster, but less precise. Type: Boolean Default: true
vertex_point_map a property map associating points to the vertices of tmesh Type: a class model of ReadablePropertyMap with boost::graph_traits<FaceGraph>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, tmesh) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in FaceGraph.
concurrency_tag a tag indicating if the task should be done using one or several threads. Type: Either CGAL::Sequential_tag, or CGAL::Parallel_tag, or CGAL::Parallel_if_available_tag Default: CGAL::Parallel_if_available_tag
geom_traits an instance of a geometric traits class Type: a class model of Kernel Default: a CGAL Kernel deduced from the value type of the vertex-point map, using CGAL::Kernel_traits Extra: The geometric traits class must be compatible with the vertex point type.

Returns

the number of convex hulls. Note that this value may be lower than the maximum_number_of_convex_volumes, for example if the specified volume_error is quickly met.

Precondition

tmesh is a triangle mesh.

tmesh is not self-intersecting.

CGAL::is_closed(tmesh).

See also

CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh()

Examples

Convex_decomposition_3/approximate_convex_decomposition.cpp.

convex_decomposition_3()

template<typename NefPolyhedron_3 >

void CGAL::convex_decomposition_3

(

NefPolyhedron_3 &

N

)

#include <CGAL/convex_decomposition_3.h>

The function convex_decomposition_3() inserts additional facets into the given Nef polyhedronN`, such that each bounded marked volume (the outer volume is unbounded) is subdivided into convex pieces.

The modified polyhedron represents a decomposition into \(O(r^2)\) convex pieces, where \( r\) is the number of edges that have two adjacent facets that span an angle of more than 180 degrees with respect to the interior of the polyhedron.

The worst-case running time of our implementation is \(O(n^2r^4\sqrt[3]{nr^2}\log{(nr)})\), where \( n\) is the complexity of the polyhedron (the complexity of a Nef polyhedron is the sum of its Vertices, Halfedges and SHalfedges) and \( r\) is the number of reflex edges.

Template Parameters

NefPolyhedron_3

an object of type Nef_polyhedron_3.

Precondition

The polyhedron N is bounded. Otherwise, the outer volume is ignored.

Postcondition

If the polyhedron N is non-convex, it is modified to represent the convex decomposition. If N is convex, it is not modified.

See also

CGAL::Nef_polyhedron_3<Traits>

Examples

Convex_decomposition_3/list_of_convex_parts.cpp.