Peter Hachenberger
This package provides a function, which computes the Minkowski sum of two point sets in \( \mathbb{R}^3\). These point sets may consist of isolated vertices, isolated edges, surfaces with convex facets without holes, and open and closed solids. Thus, it is possible to compute the configuration space of translational robots (even in tight passage scenarios) as well as several graphics operations, like for instance the glide operation, which computes the point set swept by a polyhedron that moves along a polygonal line.
Functions
◆ minkowski_sum_3()
#include <CGAL/minkowski_sum_3.h>
The function minkowski_sum_3()
computes the Minkowski sum of two given 3D Nef polyhedra \( N0\) and \( N1\).
Note that the function runs in \(O(n^3m^3)\) time in the worst case, where \( n\) and \( m\) are the complexities of the two input polyhedra (the complexity of a Nef_polyhedron_3
is the sum of its Vertices
, Halfedges
and SHalfedges
).
An input polyhedron may consist of:

singular vertices

singular edges

singular convex facets without holes

surfaces with convex facets that have no holes.

threedimensional features, whose coplanar facets have common selection marks (this includes open and closed solids)
Taking a different viewpoint, the implementation is restricted as follows:

The input polyhedra must be bounded (selected outer volume is ignored).

All sets of coplanar facets of a fulldimensional feature must have the same selection mark (in case of different selection marks, unselected is assumed).

All facets of lowerdimensional features need to be convex and must not have holes (nonconvex facets and holes are ignored).
 Postcondition
 If either of the input polyhedra is nonconvex, it is modified during the computation, i.e., it is decomposed into convex pieces.
 See also
CGAL::Nef_polyhedron_3<Traits>

CGAL::convex_decomposition_3()
 Examples
 Minkowski_sum_3/cube_offset.cpp, and Minkowski_sum_3/glide.cpp.