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(n3m3) 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.
- 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
- The input polyhedra must be bounded (selected outer volume is ignored).
- 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).
- All facets of lower-dimensional features need to be convex and
must not have holes (non-convex facets and holes are ignored).
If either of the input polyhedra is non-convex, it is modified during
the computation, i.e., it is decomposed into convex pieces.