Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
440686 | Computer Aided Geometric Design | 2008 | 15 Pages |
Minkowski sum is a fundamental operation in many geometric applications, including robotic motion planning, penetration depth estimation, solid modeling, and virtual prototyping. However, due to its high computational complexity and several non-trivial implementation issues, computing the exact boundary of the Minkowski sum of two arbitrary polyhedra is generally a difficult task. In this work, we propose to represent the boundary of the Minkowski sum approximately using only points. Our results show that this point-based representation can be generated efficiently. An important feature of our method is its straightforward implementation and parallelization. We demonstrate that the point-based representation of the Minkowski sum boundary can indeed provide similar functionality as the mesh-based representations can. We show several applications in motion planning, penetration depth approximation and geometric modeling. An implementation of the proposed method can be obtained from our project webpage.