3D Minkowski Sum Made Simple
Jyh-Ming Lien
Overview
Computing the Minkowski sum of two general polyhedra is known to be difficult. We propose a simple strategy to compute the Minkowski sums efficiently. Here we show some results generated by our method.Publications
Jyh-Ming Lien "A Simple Method for Computing Minkowski Sum Boundary in 3D Using Collision Detection", The Eighth International Workshop on the Algorithmic Foundations of Robotics (WAFR), Guanajuato, Mexico, Dec. 2008, to appearSoftware
- Source code and pre-compiled binary can be downloaded from the Software page
Related work
- Point-based Minkowski Sum boundary
- [external] Definition of Minkowski sum from the Stony Brook algorithm repository or Wikipedia
- [external] Video on exact Minkowski sum and its applications (see this page by Dan Halperin et al.)
- [external] Approximate Minkowski sum by Gokul Varadhan, Dinesh Manocha
- [external] CGAL 3D Minkowski Sum of Polyhedra by Peter Hachenberger
Note
- Models are all in OBJ format
- A simple OBJ viewer: win32, linux, OS X (glut is needed)
- Download (452 MB) all OBJ files listed below.
Sample results #1
- The cell_{i,j} contains the Minkowski sum of input i and input j.
| P+Q |  obj (78) |  obj (36) |  obj (96) |  obj (992) |  obj (772) |  obj (2116) |  obj (12396) |  obj (32236) |
 obj (992) |  obj (1035) |  obj (1282) |  obj (1962) |  obj (12232) |  obj (4076) |  obj (13947) |  obj (55953) |  obj (79316) |
| obj (78) |  obj (619) |  obj (440) |  obj (1308) |  obj (7537) |  obj (2714) |  obj (11237) |  obj (43091) |  obj (58995) |
| obj (36) |  obj (380) |  obj (1320) |  obj (3893) |  obj (2564) |  obj (6032) |  obj (29893) |  obj (47374) | |
| obj (96) |  obj (3822) |  obj (11070) |  obj (3689) |  obj (5994) |  obj (42690) |  obj (51033) | ||
| obj (992) |  obj (9387) |  obj (10811) |  obj (14740) |  obj (73245) |  obj (92992) |
Sample results #2
| P | Q | P+Q |
 horse obj (39694 facets) |  path obj (28 facets) |  obj (73942 facets) |
 spoon obj (89822 facets) | path obj (28 facets) |  obj (148280 facets) |
 pig obj (2784 facets) | path obj (28 facets) |  obj (9571 facets) |
 U1 obj (44 facets) |  U2 obj (44 facets) |  obj (344 facets) |
 blocks obj (44 facets) |  cube obj (344 facets) |  obj (336 facets) |
 baby obj (12 facets) |  torus obj (12 facets) |  obj (1081 facets) |
 kids obj (200028 facets) |  sphere obj (500 facets) |  obj (325808 facets) |
 octopus obj (8276 facets) |  dragon obj (2328 facets) |  obj (100807 facets) |
 grate1 obj (540 facets) |  grate2 obj (942 facets) |  obj (72168 facets) |
List of MASC Research Pages