M.Sc Student | Geller Shlomo |
---|---|

Subject | Computing Minkowski Sums for Freeform Geometry |

Department | Department of Mechanical Engineering |

Supervisor | Dr. Iddo Hanniel |

Full Thesis text |

Minkowski sums have
numerous applications in robot path planning, collision detection, assembly
planning and more. While there are algorithms and implementations for computing
Minkowski sums of polygons, implementing such algorithms for freeform geometry
(e.g., B-spline curves) presents new and difficult challenges.

In this work we have implemented algorithms for the computation of Minkowksi
sums of freeform curves. We present our symbolic representation of the boundary
of the Minkowski sum as an implicit bivariate polynomial equation in the
parameter space. The solution is a univariate curve in the parameter space that
is mapped to a curve in the Euclidean plane. This curve is further processed to
remove unwanted branches. The computations required for this processing are
performed by defining conditions on the curves, and applying a constraint
solver to compute the result based on these conditions.

We extend our results to
the computation of Minkowski sums of freeform surfaces in *R ^{3}*.
We represent the boundary of the Minkowski sum as a system of implicit multivariate
polynomial equations in the parameter space. The solution is a bivariate
manifold in the parameter space, which is sampled and mapped to the Euclidean
space.

Finally, we show how to compute a surface Minkowski sum that is constrained to a plane. Unlike the full surface Minkowski sum, the solution to this problem is a univariate curve and therefore easier to process. The result can be applied, for example, in path planning of a freeform robot moving on a floor while avoiding three-dimensional freeform obstacles.

**Keywords: **Minkowksi sums, freeform
geometry