A GPU-based voxelization approach to 3D Minkowski sum computation

We present a new approach for computing the voxelized Minkowski sum of two polyhedral objects using programmable Graphics Processing Units (GPUs). We first cull out surface primitives that will not contribute to the final boundary of the Minkowski sum. The remaining surface primitives are then rendered to depth textures along six orthogonal directions to generate an initial solid voxelization of the Minkowski sum. Finally we employ fast flood fill to find all the outside voxels. We generate both solid and surface voxelizations of Minkowski sums without holes and support high volumetric resolution of 1024 3 with low video memory cost. The whole algorithm runs on the GPU and is at least one order of magnitude faster than existing boundary representation (B-rep) based algorithms for computing Minkowski sums of objects with curved surfaces at similar accuracy. It avoids complex 3D Boolean operations and is easy to implement. The voxelized Minkowski sums can be used in a variety of applications including motion planning and penetration depth computation.