A sweep and translate algorithm for computing voxelized 3D Minkowski sums on the GPU

Computing the Minkowski sum of two arbitrary polyhedra in R^3 is difficult because of high combinatorial complexity. We present an algorithm for directly computing a voxelization of the Minkowski sum of two closed watertight input polyhedra for applications such as path planning that do not require a boundary representation as output. We introduce a new decomposition formula for computing the Minkowski sum and prove its correctness. We describe an efficient Graphics Processing Unit (GPU) implementation of the algorithm using stencil shadow volumes to create a solid voxelization of the Minkowski sum.