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