GPU-Based Computation of Voxelized Minkowski Sums with Applications

Wei Li
University of California, Berkeley
University of California, 2011


   title={GPU-Based Computation of Voxelized Minkowski Sums with Applications},

   author={Li, W.},


   school={University of California}


Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

Featured events

Hida Takayama, Japan

The Third International Workshop on GPU Computing and AI (GCA), 2018

Nagoya University, Japan

The 5th International Conference on Power and Energy Systems Engineering (CPESE), 2018

MediaCityUK, Salford Quays, Greater Manchester, England

The 10th International Conference on Information Management and Engineering (ICIME), 2018

No. 1037, Luoyu Road, Hongshan District, Wuhan, China

The 4th International Conference on Control Science and Systems Engineering (ICCSSE), 2018

Nanyang Executive Centre in Nanyang Technological University, Singapore

The 2018 International Conference on Cloud Computing and Internet of Things (CCIOT’18), 2018

HGPU group © 2010-2018 hgpu.org

All rights belong to the respective authors

Contact us: