“Contributing Vertices-Based Minkowski Sum of a Nonconvex–Convex Pair of Polyhedra” by Barki, Denis and Dupont

  • ©Hichem Barki, Florence Denis, and Florent Dupont

Conference:


Type:


Title:

    Contributing Vertices-Based Minkowski Sum of a Nonconvex--Convex Pair of Polyhedra

Presenter(s)/Author(s):


Abstract:


    The exact Minkowski sum of polyhedra is of particular interest in many applications, ranging from image analysis and processing to computer-aided design and robotics. Its computation and implementation is a difficult and complicated task when nonconvex polyhedra are involved. We present the NCC-CVMS algorithm, an exact and efficient contributing vertices-based Minkowski sum algorithm for the computation of the Minkowski sum of a nonconvex–convex pair of polyhedra, which handles nonmanifold situations and extracts eventual polyhedral holes inside the Minkowski sum outer boundary. Our algorithm does not output boundaries that degenerate into a polyline or a single point. First, we generate a superset of the Minkowski sum facets through the use of the contributing vertices concept and by summing only the features (facets, edges, and vertices) of the input polyhedra which have coincident orientations. Secondly, we compute the 2D arrangements induced by the superset triangles intersections. Finally, we obtain the Minkowski sum through the use of two simple properties of the input polyhedra and the Minkowski sum polyhedron itself, that is, the closeness and the two-manifoldness properties. The NCC-CVMS algorithm is efficient because of the simplifications induced by the use of the contributing vertices concept, the use of 2D arrangements instead of 3D arrangements which are difficult to maintain, and the use of simple properties to recover the Minkowski sum mesh. We implemented our NCC-CVMS algorithm on the base of CGAL and used exact number types. More examples and results of the NCC-CVMS algorithm can be found at: http://liris.cnrs.fr/hichem.barki/mksum/NCC-CVMS

References:


    1. Cgal. Computational geometry algorithms library. http://www.cgal.org.
    2. GNU MP. the GNU MP bignum library. http://gmplib.org.
    3. Agarwal, P. and Sharir, M. 1998. Arrangements and their applications. In Handbook of Computational Geometry, Elsevier Science Publishers B.V. North-Holland, 49–119.
    4. Aronov, B., Sharir, M., and Tagansky, B. 1997. The union of convex polyhedra in three dimensions. SIAM J. Comput. 26, 6, 1670–1688.
    5. Barki, H., Denis, F., and Dupont, F. 2009a. Contributing vertices-based minkowski sum computation of convex polyhedra. Comput. Aid. Des. 41, 7, 525–538.
    6. Barki, H., Denis, F., and Dupont, F. 2009b. Contributing vertices-based minkowski sum of a non-convex polyhedron without fold and a convex polyhedron. In Proceedings of the IEEE International Conference on Shape Modeling and Applications (SMI’09). IEEE Computer Society, 73–80.
    7. Basch, J., Guibas, L., Ramkumar, G., and Ramshaw, L. 1996. Polyhedral tracings and their convolution. In Proceedings of 2nd Workshop on the Algorithmic Foundations of Robotics. 171–184.
    8. Bekker, H. and Roerdink, J. 2001. An efficient algorithm to calculate the Minkowski sum of convex 3d polyhedra. In Proceedings of the International Conference on Computational Sciences-Part I (ICCS’01). Springer, 619–628.
    9. Chazelle, B. 1981. Convex decompositions of polyhedra. In Proceedings of the 13th Annual ACM Symposium on Theory of Computing (STOC’81). ACM, New York, 70–79.
    10. Evans, R., OòConnor, M., and Rossignac, J. 1992. Construction of Minkowski sums and derivatives morphological combinations of arbitrary polyhedra in CAD/CAM systems. US Patent 5159512.
    11. Fabri, A. and Pion, S. 2006. A generic lazy evaluation scheme for exact geometric computations. In Proceedings of the 2nd Library-Centric Software Design.
    12. Fogel, E. and Halperin, D. 2007. Exact and efficient construction of Minkowski sums of convex polyhedra with applications. Comput. Aid. Des. 39, 11, 929–940.
    13. Fogel, E., Wein, R., Zukerman, B., and Halperin, D. 2008. 2d regularized boolean set-operations. In CGAL User and Reference Manual, 3.4 Ed., C. E. Board, Ed.
    14. Ghosh, P. 1993. A unified computational framework for Minkowski operations. Comput. Graph. 17, 4, 357–378.
    15. Guibas, L. and Seidel, R. 1987. Computing convolutions by reciprocal search. Discrete Comput. Geom. 2, 175–193.
    16. Guibas, L. J., Ramshaw, L., and Stolfi, L. 1983. A kinetic framework for computational geometry. In Proceedings of 24th annual IEEE Symposium on the Foundation of Computer Science. 100–111.
    17. Hachenberger, P. 2007. Exact Minkowski sums of polyhedra and exact and efficient decomposition of polyhedra in convex pieces. In Proceedings 15th Annual European Symposium on Algorithms. 669–680.
    18. Hachenberger, P. and Kettner, L. 2008. 3d boolean operations on Nef polyhedra. In CGAL User and Reference Manual. 3.4 Ed., C. E. Board, Ed.
    19. Hachenberger, P., Kettner, L., and Mehlhorn, K. 2007. Boolean operations on 3d selective nef complexes: data structure, algorithms, optimized implementation and experiments. Comput. Geom. Theory Appl. 38, 1-2, 64–99.
    20. Halperin, D. 2002. Robust geometric computing in motion. Int. J. Robotics Res. 21, 3, 219–232.
    21. Hertel, S. and Mehlhorn, K. 1983. Fast triangulation of simple polygons. In Proceedings of the International FCT-Conference on Fundamentals of Computation Theory. Springer, 207–218.
    22. Kaul, A. and Rossignac, J. 1992. Solid-interpolating deformations: construction and animation of PIPs. Comput. Graph. 16, 1, 107–115.
    23. Kettner, L. 1999. Using generic programming for designing a data structure for polyhedral surfaces. Comput. Geom. Theory Appl. 13, 1, 65–90.
    24. Kim, Y., Otaduy, M., Lin, M., and Manocha, D. 2003. Fast penetration depth estimation using rasterization hardware and hierarchical refinement. In Proceedings of the 19th Annual Symposium on Computational Geometry (SCG’03). ACM, New York, 386–387.
    25. Lee, I.-K., Kim, M.-S., and Elber, G. 1998. Polynomial/rational approximation of Minkowski sum boundary curves. Graph. Models Image Process. 60, 2, 136–165.
    26. Lien, J.-M. 2007. Point-based Minkowski sum boundary. In Proceedings of the 15th Pacific Conference on Computer Graphics and Applications (PG’07). IEEE Computer Society, 261–270.
    27. Lien, J.-M. 2008. A simple method for computing Minkowski sum boundary in 3d using collision detection. In Proceedings of 8th Workshop on the Algorithmic Foundations of Robotics.
    28. Lozano-Pérez, T. 1983. Spatial planning: A configuration space approach. IEEE Trans. Comput. 32, 2, 108–120.
    29. Möller, T. 1997. A fast triangle-triangle intersection test. J. Graph. Tools 2, 2, 25–30.
    30. Serra, J. 1982. Image Analysis and Mathematical Morphology, vol. 1. Academic Press, London.
    31. Serra, J. 1988. Image Analysis and Mathematical Morphology, vol. 2. Academic Press, New York.
    32. Tuzikov, A., Roerdink, J., and Heijmans, H. 2000. Similarity measures for convex polyhedra based on Minkowski addition. Patt. Recogn. 33, 979–995.
    33. Varadhan, G. and Manocha, D. 2006. Accurate Minkowski sum approximation of polyhedral models. Graph. Models 68, 4, 343–355. 
    34. Weibel, C. Minkowski sums. http://roso.epfl.ch/cw/poly/public.php.
    35. Wein, R., Fogel, E., Zukerman, B., and Halperin, D. 2008. 2d arrangements. In CGAL User and Reference Manual 3.4 ed., C. E. Board, Ed. http://www.cgal.org/Manual/lotest/doc.html/cgal_manual/contents.html
    36. Wu, Y., Shah, J., and Davidson, J. 2003. Improvements to algorithms for computing the Minkowski sum of 3-polytopes. Comput. Aid. Des. 35, 13, 1181–1192.
    37. Yvinec, M. 2008. 2d triangulations. In CGAL User and Reference Manual 3.4 Ed., C. E. Board, Ed. http://www.cgal.org/Manual/lotest/doc.html/cgal_manual/contents.html
    38. Zomorodian, A. and Edelsbrunner, H. 2002. Fast software for box intersections. Int. J. Comput. Geom. Appl. 12, 1-2, 143–172.

ACM Digital Library Publication:


Overview Page: