Chapter 25
3D Minkowski Sum of Polyhedra

Peter Hachenberger

25.1   Introduction

Minkowski sum example
Figure 25.1:  The Minkowski sum of a spoon and a star.

The Minkowski sum of two point sets P and Q in R d, denoted by P Q, is defined as the set {p+q:p in P, q in Q }. Minkowski sums are used in a wide range of applications such as robot motion planning [Lat91] and computer-aided design [EK99]. Figure 25.2 shows an example how Minkowski sums can be used to plan the motion of a translational robot. We want to know which are legal positions of the robot, and where can the robot go to from a specified starting position. If we model both, the robot and the obstacles as a polyhedron and compute the Minkowski sum of the inverted robot (robot reflected at the origin) and the obstacles, then this Minkowski sum represents all illegal positions of the robot, i.e., all positions where it intersects the obstacle. Of course, the complement of that polyhedron are all legal positions of the robot, i.e., all positions where it does not intersect an obstacle.

motion planning
Figure 25.2:  Can the robot enter the room? The Minkowski sum of the inverted robot and the obstacle represents all illegal positions of the robot with respect to the obstacle. The boundary of the Minkowski sum are legal positions. Thus, there is a path for the robot between the outer area and the room.

This package provides a function minkowski_sum_3 that computes the Minkowski sum of two Nef polyhedra. We do not support arbitrary Nef polyhedra, yet. The restrictions are discussed in detail in Section 25.3.

25.2   Decomposition Method

The decomposition method for computing the Minkowski sum of non-convex polyhedra makes use of the fact that Minkowski sums of convex polyhedra are rather easy to compute. It decomposes both polyhedra into convex pieces, computes all pairwise Minkowski sums of the convex pieces, and merges the pairwise sums [dBvKOS97].

decomposition method
Figure 25.3:  The decomposition method decomposes both input polyhedra into convex parts, computes all pairwise Minkowski sums of the convex parts, and merges the pairwise sums.

The Minkowski sum is an inherent complex method. Using the decomposition method, each polyhedron might be divided into a quadratic number of pieces, which is worst-case optimal. Then up to n2m2 pairwise sums have to be computed and merged, where n and m is the complexity of the two input polyhedra. In total the operation runs in O(n3m3) time.

Since the computation of the Minkowski sum takes quite some time, we give the running times of some Minkowski sum computations. The were computed with CGAL 3.3 on a machine with a 2.4 GHz AMD Opteron processor and 4 GB RAM. The code was compiled with g++ 3.2 and compiler options -O2. The Nef_polyhedron_3 class was instantiated with the geometric kernel Homogeneous<leda_integer>. The Minkowski sum of the spoon and the star is illustrated in Figure 25.1.


model 1 model 2 running
name facets conv. pcs. name facets conv. pcs. time

mushroom 448 255 cube 6 1 204s
mushrrom 448 255 ball1 128 1 553s
spoon 336 186 star 24 5 882s
cup 1000 774 ball2 1000 1 9851s

Table 25.0:  Performance of the function minkowski_sum_3.

25.3   Features and Restrictions

This package was written to allow the computation of Minkowski sums of full-dimensional polyhedra even in so-called tight-passage scenarios. Tight passage scenarios occur in robot motion planning, when a robot is just as wide as a passage it needs to traverse. In these scenarios at least one polyhedron - the obstacles or the robot - must be modeled as an open set. Then the Minkowski sum will also be an open set and tight passages will occurr as lower-dimensional exclusions, i.e., as facets, lines, or vertices that are, in contrast to the volume around them, not part of the resulting point set. Figure 25.2 shows such a tight passage scenario.

Our implementation uses Nef_polyhedron_3 to model the input polyhedra and the result polyhedron. A Nef_polyhedron_3 represents a subdivision of the three-dimensional space into vertices, edges, facets, and volumes. Each of these items contains set-selection mark, which indicates whether the item belongs to the represented point set or not.The represented polyhedron is the union of the point sets represented by the selected items. As an example, a cube is represented by 8 vertices, 12 edges, 6 facets, and 2 volumes, where one volume represents the interior of the cube and the other the volume outside of the cube. All of these items are selected, except for outer volume. Read the chapter on 3D Boolean operations on Nef polyhedra for more details 23.

The use of Nef_polyhedron_3 allows many scenarios beyond the Minkowski sum of two solids. First, they can model the input and the result of a tight passage scenario, i.e., they can model open and closed solids for the input, and they can model lower-dimensional exclusions by unselected facets, edges, and vertices. We strive for extending the package to work for arbitrary 3D Nef polyhedra. In addition to the Minkowski sums of two solids, we added several features, but are not complete. At the moment we allow an input polyhedron to consist of:

  1. singular vertices
  2. singular edges
  3. singular convex facets without holes
  4. surface 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).

25.4   Usage

The following example code illustrates the usage of the function minkowski_sum_3. Note that the two input polyhedra will be destroyed by the function. So, if they are needed further on, they need to be copied, first. The copying is not done by the function itself to keep the memory usage as small as possible.

File: examples/Minkowski_sum_3/cube_offset.cpp
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
#include <CGAL/minkowski_sum_3.h>
#include <fstream>
#include <iostream>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron;

int main() {

  Nef_polyhedron N0, N1;
  std::ifstream in("cube.nef3");
  in >> N0;
  std::cin >> N1;
  Nef_polyhedron result = CGAL::minkowski_sum_3(N0, N1);
}

25.5   Glide

glide operation
Figure 25.5:  The region swept by a star that moves along a polygonal path.

With the function minkowski_sum_3 it is also possible to realize other interesting geometric operations like the glide operation, which computes the point set swept by a polyhedron that moves along a polygonal path. The following example shows how to construct a polygonal path and then compute the glide operation by calling the function minkowski_sum_3.

File: examples/Minkowski_sum_3/glide.cpp
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
#include <CGAL/minkowski_sum_3.h>
#include <iostream>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel>     Nef_polyhedron;
typedef Kernel::Point_3 Point_3;
typedef Point_3* point_iterator;
typedef std::pair<point_iterator,point_iterator> 
  point_range;
typedef std::list<point_range> polyline;

int main(int argc, char* argv[]) 
{
  Nef_polyhedron N0;
  std::cin >> N0;
  Point_3 pl[6] = 
    {Point_3(-100,0,0), 
     Point_3(40,-70,0),
     Point_3(40,50,40),
     Point_3(-90,-60,60),
     Point_3(0, 0, -100),
     Point_3(30,0,150)
  };

  polyline poly;
  poly.push_back(point_range(pl,pl+6));
  Nef_polyhedron N1(poly.begin(), poly.end(), Nef_polyhedron::Polylines_tag());
  Nef_polyhedron result = CGAL::minkowski_sum_3(N0, N1);
}