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

Nef_polyhedron_3 minkowski_sum_3 ( Nef_polyhedron_3 N0, Nef_polyhedron_3 N1)


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


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