Dynamic Scaling of Minkowski Sums

Emily Behar and Jyh-Ming Lien

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.

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



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.

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
Ellipse, geodesic sphere 3, geodesic sphere 4, truncated isocidodecahedron, v-rod

Average speed-up over brute force for 100 random non-uniform rescalings
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