Dynamic Scaling of Minkowski Sums


Evan 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, Evan 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

Software

Downloads

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
ellipseGS3GS4TIv-rod
ellipse17.23116.65332.31214.63619.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

Related Work/Links
Computer Science @ George Mason University