Efficient retrieval of Minkowski sum of rotating polytopes
A subset of the Criticality map of two identical tetrahedra for two axes rotation 


The Gaussian map  A subset of the Criticality map 
Abstract
We present a novel method for fast retrieval of exact Minkowski sums of pairs of convex polytopes in ^{3}, where one of the polytopes rotates. The algorithm is based on precomputing a socalled criticality map, which records the changes in the underlying graphstructure of the Minkowski sum, while one of the polytopes rotates. We give tight combinatorial bounds on the complexity of the criticality map when the rotating polytope rotates about one, two, or three axes. The criticality map can be rather large already for rotations about one axis, even for summand polytopes with a moderate number of vertices each. We therefore focus on the restricted case of rotations about a single, though arbitrary, axis.
Our work targets applications that require exact collision detection such as motion planning with narrow corridors and assembly maintenance where high accuracy is required. Our implementation handles all degeneracies and produces exact results. It eﬃciently handles the algebra of exact rotations about an arbitrary axis in ^{3}, and it well balances between preprocessing time and space on the one hand, and query time on the other.
Links
 Naama Mayer, Efi Fogel, and Dan Halperin
Fast and Robust Retrieval of Minkowski Sums of Rotating Convex Polyhedra in 3Space
Computer Aided Design, 43(10): 12581269, 2011 [link] [bibtex]
A preliminary version appeared in Proceedings of the 14th ACM Symposium on Solid and Physical Modeling (SPM), Pages 110, Haifa, Israel 2010 [link] [bibtex]
Contacts
Naama Mayer  
Efi Fogel  
Dan Halperin 