Accurate Minkowski sum approximation of polyhedral models

We present an algorithm to approximate the 3D Minkowski sum of polyhedral objects. Our algorithm decomposes the polyhedral objects into convex pieces, generates pairwise convex Minkowski sums, and computes their union. We approximate the union by generating a voxel grid, computing signed distance on the grid points, and performing isosurface extraction from the distance field. The accuracy of the algorithm is mainly governed by the resolution of the underlying volumetric grid. Insufficient resolution can result in unwanted handles or disconnected components in the approximation. We use an adaptive subdivision algorithm that overcomes these problems by generating a volumetric grid at an appropriate resolution. We guarantee that our approximation has the same topology as the exact Minkowski sum. We also provide a two-sided Hausdorff distance bound on the approximation. Our algorithm is relatively simple to implement and works well on complex models. We have used it for exact 3D translation motion planning, offset computation, mathematical morphological operations, and bounded-error penetration depth estimation.