3D Minkowski Sum Made Simple
by Jyh-Ming Lien, George Mason University
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 appear
Software
m+3d version 0.5 (Dec 2008)
Note:
- You may need to have glut library if you want to visualize the results.
- .Net platform is needed for running the win32 version.
- Source code (in C++) is available on request
- Report bugs to jmlien@cs.gmu.edu
Related work
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) |