high performance computing on graphics processing units: hgpu.org

We present an efficient and robust algorithm to approximate the 3D Minkowski sum of two arbitrary polyhedra on Graphics Processing Unit (GPU). Our algorithm makes use of the idea of super-union, in which we decompose the two polyhedra into convex pieces as usual, but the way we perform pairwise convex Minkowski sum and merge the pairwise sums one by one is changed to group by group on GPU. The core technique involved is to directly compute the convex hull of pairwise sum in image representation and utilize voxelization to perform massive union operations. Despite the lack of accuracy, we guarantee that the voxelization of Minkowski sum is conservative, and the inner voids are well preserved. Our algorithm is also scalable and fits well into GPU’s streaming architecture.