CGAL homepage   ACG at TAU  
TAU Members   People   Projects  

Exact and Efficient Construction of Minkowski Sums of Convex Polyhedra with Applications

Minkowski sum of 2 orthogonal dioctagonal pyramids
[primal] [dual] [dual-unfolded]
PrimalDualDual Unfolded

Abstract

We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in dioctal pyramid3. Our implementation is complete in the sense that it does not assume general position, namely, it can handle degenerate input, and produces exact results. We also present applications of the Minkowski-sum computation to answer collision and proximity queries about the relative placement of two convex polyhedra in dioctal pyramid3. The algorithms use a dual representation of convex polyhedra, and their implementation is mainly based on the Arrangement package of \cgal, the Computational Geometry Algorithm Library. We compare our Minkowski-sum construction with a \naive\ approach that computes the convex hull of the pairwise sums of vertices of two convex polyhedra. Our method is significantly faster; in some cases it is fifty times faster than the convex-hull approach. The results of experimentation with a broad family of convex polyhedra are reported. The relevant programs, source code, data sets, and documentation are available at collision_detection

Links

Contact

Efi Fogel http://www.cs.tau.ac.il/~efif efif@post.tau.ac.il
Dan Halperin http://www.math.tau.ac.il/~halperin halperin@post.tau.ac.il

[Projects Page] [Top]
Site is maintained by Efi Fogel. Last modified: May 14 2006.