high performance computing on graphics processing units: hgpu.org

Minkowski sums are a fundamental operation for many applications in Computer-Aided Design and Manufacturing, such as solid modeling (offsetting and sweeping), collision detection, toolpath planning, assembly/disassembly planning, and penetration depth computation. Configuration spaces (C-spaces) are closely related to Minkowski sums; we analyze accessibility for waterjet cleaning processes as an example to illustrate the important relationship between them. We describe an algorithm for finding all the cleanable regions given the geometry of a workpiece. Minkowski sums are used to compute the C-spaces and cleanable regions are then found by visibility analysis. Computing the Minkowski sum of two arbitrary polyhedra in R^3 is difficult because of high combinatorial complexity. We present two algorithms for directly computing a voxelization of the Minkowski sum of two closed watertight polyhedra that run on the Graphics Processing Unit (GPU) and do not need to compute a complete boundary representation (B-rep). For the first voxelization algorithm, we put forward a new formula that decomposes the Minkowski sum of two polyhedra into the union of the Minkowski sum of their boundaries and a translation of each input polyhedron. The union is then voxelized on the GPU using the stencil shadow volume technique. The performance of this algorithm depends on the numbers of faces of the two polyhedra. For Minkowski sums in cases where we do not need to consider enclosed voids, we propose the second voxelization algorithm, which has much faster running times and also achieves higher resolution. It first robustly culls primitives that cannot contribute to the final boundary of the Minkowski sum, and then uses ood fiill to find all the outer voxels. The performance of this algorithm depends on both the numbers of faces of the input polyhedra and the shape complexity of the Minkowski sum. We demonstrate applications of the voxelized Minkowski sums in solid modeling, motion planning, and penetration depth computation. Compared with existing B-rep based algorithms, our voxelization algorithms are easy to implement and avoid the extra sampling process required in many applications.