GPU-Based Super-union for Minkowski Sum

Yuen- Shan Leung, Charlie C. L. Wang, Yong Chen
The Chinese University of Hong Kong
Computer-Aided Design and Applications, Volume 10, Number 3, Pages 475-487, 2013


   title={GPU-Based Super-union for Minkowski Sum},

   author={Leung, Y.S. and Wang, C.C.L. and Chen, Y.},



Download Download (PDF)   View View   Source Source   



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

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: