CGAL::minkowski_sum_3

Definition

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³m³) 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).

Precondition

An input polyhedron may consist of:

1. singular vertices
2. singular edges
3. singular convex facets without holes
4. surfaces with convex facets that have no holes.
5. three-dimensional features, whose coplanar facets have common selection marks (this includes open and closed solids)

Taking a different viewpoint, the implementation is restricted as follows:

1. The input polyhedra must be bounded (selected outer volume is ignored).
2. All sets of coplanar facets of a full-dimensional feature must have the same selection mark (in case of different selection marks, unselected is assumed).
3. All facets of lower-dimensional features need to be convex and must not have holes (non-convex facets and holes are ignored).

Postcondition

If either of the input polyhedra is non-convex, it is modified during the computation, i.e., it is decomposed into convex pieces.

See Also