טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentGeller Shlomo
SubjectComputing Minkowski Sums for Freeform Geometry
DepartmentDepartment of Mechanical Engineering
Supervisor Dr. Iddo Hanniel
Full Thesis textFull thesis text - English Version


Abstract

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 R3. 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