Dynamic Scaling of Minkowski Sums
Emily Behar and Jyh-Ming Lien
Overview
We present two methods for dynamically updating Minkowski sums under scaling, the first of which updates the sum under uniform scaling of arbitrary polygons and polyhedra, and the second of which updates the sum under non-uniform scaling of convex polyhedra. Ours are the first methods that study the Minkowski sum under this type of transformation. Our idea is based on the notion that the structure of the Minkowski sum does not change completely as the inputs are smoothly transformed. Using this idea, we can avoid recomputing parts of the structure that do not change, and thus save significant computation effort.Publications
Dynamic Minkowski Sums Under Scaling, Emily Behar and Jyh-Ming Lien, Computer-Aided Design, November 2012, Also appear in Proc. of Symposium on Solid and Physical Modeling, Dijon, France, Oct. 2012.
Web Site / Paper (pdf) / BibTeX
Web Site / Paper (pdf) / BibTeX
Software
- Software and source code available upon request. Please send an email to jmlien@cs.gmu.edu
Downloads
- The input models will be uploaded shortly. If you need them presently, please email ebehar@gmu.edu
Overview of Our Method
The first of our two methods is an enumeration method for uniform scaling of arbitrary polygons and polyhedra. It works by identifying the scales at which primitives in the reduced convolution (see Reduced Convolution for a brief overview) intersect with each other. A data structure allows us to quickly determine which primitives are in contact at any given scale and recompute the arrangement quickly. However, the data structure becomes very expensive to compute for complex inputs.Our second method attempts to address this model by applying the methodology from DYMSUM. This allows us to perform non-uniform scaling quickly on non-convex objects at speeds similar to that at which DYMSUM updates under arbitrary rotations.
Examples
Deer dilated with a circle at scale 0.5, 1.0, 1.5, 2.0
Motion planning environment and resulting configuration space: start position is the robot marked with red, the robot not filled in is the goal position.
Experimental Results
Uniform Scaling 2D
Inputs bird & monkey:
As we can see, the enumeration method works quite well in 2D, gaining quite a lot of speed-up over the brute force method.
Uniform Scaling 3D
Inputs clutch + knot:
Speed-up of convolution step:
Overall speed-up, including collision detection time:
In 3D, the method does not gain us as much. Furthermore, the data structure is much more expensive to compute in 3D. This motivated the development of the non-uniform method, adapted from DYMSUM.
Non-Uniform Scaling 3D
Inputs:Ellipse, geodesic sphere 3, geodesic sphere 4, truncated isocidodecahedron, v-rod
Average speed-up over brute force for 100 random non-uniform rescalings
| ellipse | GS3 | GS4 | TI | v-rod | |
|---|---|---|---|---|---|
| ellipse | 17.231 | 16.653 | 32.312 | 14.636 | 19.060 |
| GS3 | 44.475 | 18.311 | 17.584 | 17.423 | 29.902 |
| GS4 | 13.109 | 17.273 | 13.050 | 18.026 | 34.342 |
| TI | 18.685 | 20.332 | 19.669 | 24.952 | 37.960 |
| v-rod | 24.471 | 40.246 | 40.691 | 44.757 | 97.410 |