Point-based Minkowski Sum Boundary

Jyh-Ming Lien

Overview

Minkowski sum is a fundamental operation in many geometric applications, including robotics, penetration depth estimation, solid modeling, and virtual prototyping. In this work, we propose to represent the boundary of the Minkowski sum approximately using only points. Our results show that this point-based representation can be generated efficiently. An important feature of our method is its straightforward implementation and parallelization.

Benefits of point-based Minkowski sum

efficiency,
robustness (can even work for non-manifold models with open surfaces),
easy implementation (i.e., no convex decomposition and no need to perform union),
easy parallelization,
multiresolution representations, and
similar functionality as mesh-based representations

Publications

Jyh-Ming Lien. "Covering Minkowski Sum Boundary Using Points with Applications", Computer Aided Geometric Design (CAGD), Volume 25, Issue 8, November 2008, Pages 652–666.
[pdf]

Jyh-Ming Lien. "Point-Based Minkowski Sum Boundary", Proceedings of the Pacific Conference on Computer Graphics and Applications (Pacific Graphics), Maui, Hawaii, Nov. 2007, page 261--270.
[pdf]

Related Work

3D Minkowski Sum Made Simple

(If mesh-based representation is prefer, you may be more interested in this work.)

Software

Source code and pre-compiled binary can be found on the Software page

Examples

Input models: dancing children+unit cube	Minkowski sum

Input models: pig+path	Minkowski sum

Input models: baby+torus	Minkowski sum

Input models: hooks	Minkowski sum

Input models: octpus+(-dragon)	Minkowski sum