Point-based Minkowski Sum Boundary
Jyh-Ming Lien
Overview
Minkowski sum is a fundamental operation in many geometric applications, including robotics, penetration depth estimation, solid modeling, and virtual prototyping. 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.Benefits of point-based Minkowski sum
- efficiency,
- robustness (can even work for non-manifold models with open surfaces),
- easy implementation (i.e., no convex decomposition and no need to perform union),
- easy parallelization,
- multiresolution representations, and
- similar functionality as mesh-based representations
Publications
Jyh-Ming Lien. "Covering Minkowski Sum Boundary Using Points with Applications", Computer Aided Geometric Design (CAGD), Volume 25, Issue 8, November 2008, Pages 652–666.[pdf]
Jyh-Ming Lien. "Point-Based Minkowski Sum Boundary", Proceedings of the Pacific Conference on Computer Graphics and Applications (Pacific Graphics), Maui, Hawaii, Nov. 2007, page 261--270.
[pdf]
Related Work
(If mesh-based representation is prefer, you may be more interested in this work.)Software
- Source code and pre-compiled binary can be found on the Software page
Examples
Input models: dancing children+unit cube | Minkowski sum |
![]() | ![]() |
Input models: pig+path | Minkowski sum |
![]() | ![]() |
Input models: baby+torus | Minkowski sum |
![]() | ![]() |
Input models: hooks | Minkowski sum |
![]() | ![]() |
Input models: octpus+(-dragon) | Minkowski sum |
![]() | ![]() |
Related Links
- Definition of Minkowski sum from the Stony Brook algorithm repository or Wikipedia
- Video on exact Minkowski sum and its applications (see this page by Dan Halperin et al.)
- Approximate Minkowski sum by Gokul Varadhan, Dinesh Manocha
- CGAL 3D Minkowski Sum of Polyhedra by Peter Hachenberger
List of MASC Research Pages