Abstract
Computing the Minkowski sum of two polyhedra exactly has been shown difficult. Despite its fundamental role in many geometric problems in robotics, to the best of our knowledge, no 3-d Minkowski sum software for general polyhedra is available to the public. One of the main reasons is the difficulty of implementing the existing methods. There are two main approaches for computing Minkowski sums: divide-and-conquer and convolution. The first approach decomposes the input polyhedra into convex pieces, computes the Minkowski sums between a pair of convex pieces, and unites all the pairwise Minkowski sums. Although conceptually simple, the major problems of this approach include: (1) The size of the decomposition and the pairwise Minkowski sums can be extremely large and (2) robustly computing the union of a large number of components can be very tricky. On the other hand, convolving two polyhedra can be done more efficiently. The resulting convolution is a superset of the Minkowski sum boundary. For non-convex inputs, filtering or trimming is needed. This usually involves computing (1) the arrangement of the convolution and its substructures and (2) the winding numbers for the arrangement subdivisions. Both computations are difficult to implement robustly in 3-d. In this paper we present a new approach that is simple to implement and can efficiently generate accurate Minkowski sum boundary. Our method is convolution based but it avoids computing the 3-d arrangement and the winding numbers. The premise of our method is to reduce the trimming problem to the problems of computing 2-d arrangements and collision detection, which are much better understood in the literature. To maintain the simplicity, we intentionally sacrifice the exactness. While our method generates exact solutions in most cases, it does not produce low dimensional boundaries, e.g., boundaries enclosing zero volume. We classify our method as ‘nearly exact’ to distinguish it from the exact and approximate methods.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agarwal, P.K., Flato, E., Halperin, D.: Polygon decomposition for efficient construction of minkowski sums. In: Paterson, M. (ed.) ESA 2000. LNCS, vol. 1879, pp. 20–31. Springer, Heidelberg (2000)
Bajaj, C., Dey, T.K.: Convex decomposition of polyhedra and robustness. SIAM J. Comput. 21, 339–364 (1992)
Flato, E.: Robuts and efficient construction of planar minkowski sums. M.Sc. thesis, Dept. Comput. Sci., Tel-Aviv Univ., Israel (2000)
Fogel, E., Halperin, D.: Exact and efficient construction of Minkowski sums of convex polyhedra with applications. In: Proc. 8th Wrkshp. Alg. Eng. Exper. (Alenex 2006), pp. 3–15 (2006)
Fukuda, K.: From the zonotope construction to the minkowski addition of convex polytopes. Journal of Symbolic Computation 38(4), 1261–1272 (2004)
Ghosh, P.K.: A unified computational framework for Minkowski operations. Computers and Graphics 17(4), 357–378 (1993)
Gottschalk, S., Lin, M.C., Manocha, D.: OBBTree: A hierarchical structure for rapid interference detection. Computer Graphics 30(Annual Conference Series), 171–180 (1996)
Gritzmann, P., Sturmfels, B.: Minkowski addition of polytopes: computational complexity and applications to Gröbner bases. SIAM J. Discret. Math. 6(2), 246–269 (1993)
Guibas, L.J., Ramshaw, L., Stolfi, J.: A kinetic framework for computational geometry. In: Proc. 24th Annu. IEEE Sympos. Found. Comput. Sci., pp. 100–111 (1983)
Guibas, L.J., Seidel, R.: Computing convolutions by reciprocal search. Discrete Comput. Geom. 2, 175–193 (1987)
Hachenberger, P.: Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra in Convex Pieces. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 669–680. Springer, Heidelberg (2007)
Halperin, D.: Robust geometric computing in motion. The International Journal of Robotics Research 21(3), 219–232 (2002)
Kaul, A., Rossignac, J.: Solid-interpolating deformations: construction and animation of PIPs. In: Proc. Eurographics 1991, pp. 493–505 (1991)
Lien, J.-M.: Point-based minkowski sum boundary. In: PG 2007: Proceedings of the 15th Pacific Conference on Computer Graphics and Applications, Washington, DC, USA, pp. 261–270. IEEE Computer Society, Los Alamitos (2007)
Lien, J.-M.: Hybrid motion planning using Minkowski sums. In: Proc. Robotics: Sci. Sys. (RSS), Zurich, Switzerland (2008)
Lozano-Pérez, T.: Spatial planning: A configuration space approach. IEEE Trans. Comput. C-32, 108–120 (1983)
Peternell, M., Pottmann, H., Steiner, T.: Minkowski sum boundary surfaces of 3d-objects. Technical report, Vienna Univ. of Technology (August 2005)
Raab, S.: Controlled perturbation for arrangements of polyhedral surfaces with application to swept volumes. In: SCG 1999: Proceedings of the fifteenth annual symposium on Computational geometry, pp. 163–172. ACM, New York (1999)
Varadhan, G., Manocha, D.: Accurate Minkowski sum approximation of polyhedral models. Graph. Models 68(4), 343–355 (2006)
Wein, R.: Exact and efficient construction of planar Minkowski sums using the convolution method. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 829–840. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Lien, JM. (2009). A Simple Method for Computing Minkowski Sum Boundary in 3D Using Collision Detection. In: Chirikjian, G.S., Choset, H., Morales, M., Murphey, T. (eds) Algorithmic Foundation of Robotics VIII. Springer Tracts in Advanced Robotics, vol 57. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00312-7_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-00312-7_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00311-0
Online ISBN: 978-3-642-00312-7
eBook Packages: EngineeringEngineering (R0)