Abstract
We present the first exact and robust implementation of the 3D Minkowski sum of two non-convex polyhedra. Our implementation decomposes the two polyhedra into convex pieces, performs pairwise Minkowski sums on the convex pieces, and constructs their union. We achieve exactness and the handling of all degeneracies by building upon 3D Nef polyhedra as provided by Cgal. The implementation also supports open and closed polyhedra. This allows the handling of degenerate scenarios like the tight passage problem in robot motion planning.
The bottleneck of our approach is the union step. We address efficiency by optimizing this step by two means: we implement an efficient decomposition that yields a small number of convex pieces, and develop, test and optimize multiple strategies for uniting the partial sums by consecutive binary union operations.
The decomposition that we implemented as part of the Minkowski sum is interesting in its own right. It is the first robust implementation of a decomposition of polyhedra into convex pieces that yields at most O(r 2) pieces, where r is the number of edges whose adjacent facets comprise an angle of more than 180 degrees with respect to the interior of the polyhedron.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agarwal, P.K., Flato, E., Halperin, D.: Polygon decomposition for efficient construction of Minkowski sums. Comput. Geom.: Theory Appl. 21, 39–61 (2002)
Aronov, B., Sharir, M.: Triangles in space or building (and analyzing) castles in the air. Combinatorica 10(2), 137–173 (1990)
Bajaj, C.L., Dey, T.K.: Convex decomposition of polyhedra and robustness. SIAM J. Comput. 21(2), 339–364 (1992)
Berberich, E., Fogel, E., Halperin, D., Mehlhorn, K., Wein, R.: Sweeping and maintaining two-dimensional arrangements on surfaces: A first step. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) 15th European Symposium on Algorithms, ESA 07, Eilat, Israel, October 2007. Lecture Notes in Computer Science, vol. 4698, pp. 645–656. Springer, Berlin (2007)
The CGAL Homepage. http://www.cgal.org/
Chazelle, B.: Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm. SIAM J. Comput. 13(3), 488–507 (1984)
Chazelle, B., Dobkin, D., Shouraboura, N., Tal, A.: Strategies for polyhedral surface decomposition: an experimental study. Comput. Geom.: Theory Appl. 7(5–6), 327–342 (1997)
Chazelle, B., Palios, L.: Triangulating a nonconvex polytope. Discrete Comput. Geom. 5, 505–526 (1990)
de Berg, M., Guibas, L.J., Halperin, D.: Vertical decompositions for triangles in 3-space. Discrete Comput. Geom. 15(1), 35–61 (1996)
Ehmann, S.A., Lin, M.C.: Accurate and fast proximity queries between polyhedra using convex surface decomposition. In: Computer Graphics Forum, Proc. Eurographics 2001, vol. 20(3), pp. 500–510 (2001)
Elber, G., Kim, M.-S. (eds.): Special Issue of Computer Aided Design: Offsets, Sweeps and Minkowski Sums, vol. 31 (1999)
Evans, R.C., O’Connor, M.A., Rossignac, J.R.: Construction of Minkowski sums and derivatives morphological combinations of arbitrary polyhedra in CAD/CAM systems. US Patent 5159512 (1992)
Fogel, E., Halperin, D.: Exact and efficient construction of Minkowski sums of convex polyhedra with applications. Comput. Aided Des. 39(11), 929–940 (2007)
Guibas, L.J., Ramshaw, L., Stolfi, J.: A kinetic framework for computational geometry. In: 24th Symposium on Foundations of Computer Science (FOCS), pp. 100–111 (1983)
Hachenberger, P., Kettner, L., Mehlhorn, K.: Boolean operations on 3D selective Nef complexes: Data structure, algorithms, optimized implementation and experiments. Comput. Geom.: Theory Appl. 38(1–2), 64–99 (2007)
Joe, B.: A software package for the generation of meshes using geometric algorithms. Adv. Eng. Softw. Workst. 13(5–6), 325–331 (1991)
Kaul, A., Rossignac, J.R.: Solid-interpolating deformations: Construction and animation of pips. Computers & Graphics 16(1), 107–115 (1992)
Kim, Y.J., Otaduy, M.A., Lin, M.C., Manocha, D.: Fast penetration depth computation using rasterization hardware and hierarchical refinement. In: Proc. of Workshop on Algorithmic Foundations of Robotics (2002)
Latombe, J.-C.: Robot Motion Planning. Kluwer Academic, Norwell (1991)
Lin, M.C., Manocha, D.: Collision and proximity queries. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 787–808. CRC Press LLC, Boca Raton (2004), Chap. 35
O’Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, New York (1987)
Rossignac, J.R.: Private communication (2007)
Rossignac, J.R., Requicha, A.A.G.: Offsetting operations in solid modelling. Comput. Aided Geom. Des. 3(2), 129–148 (1986)
Rössl, C., Kobbelt, L., Seidel, H.-P.: Extraction of feature lines on triangulated surfaces using morphological operators. In: Proc. of the 2000 AAAI Symp. (2000)
Shaul, H., Halperin, D.: Improved construction of vertical decompositions of three-dimensional arrangements. In: SCG ’02: Proceedings of the eighteenth annual symposium on Computational geometry, New York, NY, USA, pp. 283–292. ACM Press, New York (2002)
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: 14th European Symposium on Algorithms (ESA 06), pp. 829–840 (2006)
Wesley, M.A., Lozano-Prez, T., Lieberman, L.I., Lavin, M.A., Grossman, D.D.: A geometric modeling system for automated mechanical assembly. IBM J. Res. Dev. 24(1), 64–74 (1980)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was partially supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Hachenberger, P. Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra into Convex Pieces. Algorithmica 55, 329–345 (2009). https://doi.org/10.1007/s00453-008-9219-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-008-9219-6