Contributing vertices-based Minkowski sum of a nonconvex-convex pair of polyhedra

Hichem Barki, Florence Denis, Florent Dupont

Research output: Contribution to journalArticlepeer-review


The exact Minkowski sum of polyhedra is of particular interest in many applications, ranging from image analysis and processing to computer-aided design and robotics. Its computation and implementation is a difficult and complicated task when nonconvex polyhedra are involved. We present the NCC-CVMS algorithm, an exact and efficient contributing vertices-based Minkowski sum algorithm for the computation of the Minkowski sum of a nonconvex-convex pair of polyhedra, which handles nonmanifold situations and extracts eventual polyhedral holes inside the Minkowski sum outer boundary. Our algorithm does not output boundaries that degenerate into a polyline or a single point. First, we generate a superset of theMinkowski sum facets through the use of the contributing vertices concept and by summing only the features (facets, edges, and vertices) of the input polyhedra which have coincident orientations. Secondly, we compute the 2D arrangements induced by the superset triangles intersections. Finally, we obtain the Minkowski sum through the use of two simple properties of the input polyhedra and the Minkowski sum polyhedron itself, that is, the closeness and the two-manifoldness properties. The NCC-CVMS algorithm is efficient because of the simplifications induced by the use of the contributing vertices concept, the use of 2D arrangements instead of 3D arrangements which are difficult to maintain, and the use of simple properties to recover the Minkowski sum mesh. We implemented our NCC-CVMS algorithm on the base of CGAL and used exact number types.

Original languageEnglish
Article number3
JournalACM Transactions on Graphics
Issue number1
Publication statusPublished - Jan 2011


  • 2D arrangement computation
  • 3D intersection
  • Computer-aided design
  • Contributing vertices
  • Minkowski sum


Dive into the research topics of 'Contributing vertices-based Minkowski sum of a nonconvex-convex pair of polyhedra'. Together they form a unique fingerprint.

Cite this