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

Web Site / Paper (pdf) / BibTeX

*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

- 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.0Motion 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 |