Dynamic Minkowski sums under scaling

• Published in: Computer aided design 2013-02, Vol.45 (2), p.331-341
• Main Authors: Behar, Evan, Lien, Jyh-Ming
• Format: Article
• Language: English
• Subjects: Computation; Computer aided design; Geometry processing; Kinematic geometry; Minkowski sum; Motion planning; Polyhedra; Polyhedrons; Reuse; Robotics; Sums
• ISSN: 0010-4485; 1879-2685
• DOI: 10.1016/j.cad.2012.10.016

In many common real-world and virtual environments, there are a significant number of repeated objects, primarily varying in size. Similarly, in many complex machines, there are a significant number of parts which also vary in size rather than shape. This repetition saves in both design and production costs. Recent research in robotics has also shown that exploiting workspace repetition can significantly increase efficiency. In this paper, we address the need to support computation reuse in fundamental operations. To this end, we propose an algorithm to reuse the computation of the Minkowski sum when an object is transformed by uniform scaling. The Minkowski sum is a fundamental operation in many areas of robotics, such as motion planning, computer vision, and mathematical morphology, and has been studied extensively over the last four decades. 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 results show speed gains between one and two orders of magnitude over recomputing the Minkowski sum from scratch for each repeated object, and we discuss applications for motion planning, CAD, rapid prototyping, and shape decomposition. ► In real/virtual worlds, there are many repeated objects, primarily varying in size. ► We propose to update the Minkowski sum when input is transformed by uniform scaling. ► Our results show orders of magnitude speed gains over recomputing from scratch.