Robust polyhedral Minkowski sums with GPU implementation. (October 2015)

• Record Type: Journal Article
• Authors: Kyung, Min-Ho; Sacks, Elisha; Milenkovic, Victor
• Is Part Of: Computer aided design. Volume 67/68(2015)
• Page Start: 48
• Page End: 57
• Publication Date: 2015-10
• Subjects: Minkowski sums -- Robust computational geometry -- GPU algorithms; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2015.04.012
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: We present a Minkowski sum algorithm for polyhedra based on convolution. We develop robust CPU and GPU implementations, using our ACP strategy to eliminate degeneracy and to enforce a user-specified backward error bound. We test the programs on 45 inputs with an error bound of 1 0 − 8 . The CPU program outperforms prior work, including non-robust programs. The GPU program using 2688 CUDA cores exhibits a median speedup factor of 36, which increases to 68 on the 6 hardest tests. For example, it computes a Minkowski sum with a million features in 20 seconds. Highlights: We compute Minkowski sum boundaries of two input polyhedra. Sum polygons from convolution are created, subdivided, and traversed for boundary construction. The algorithm is robustly implemented on CPU and GPU both. The performance on GPU is orders-of-magnitude higher than previous works.