{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:28:15Z","timestamp":1750307295062,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-07-MDCO-015"],"award-info":[{"award-number":["ANR-07-MDCO-015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>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<\/jats:p>","DOI":"10.1145\/1899404.1899407","type":"journal-article","created":{"date-parts":[[2011,1,25]],"date-time":"2011-01-25T19:12:52Z","timestamp":1295982772000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Contributing vertices-based Minkowski sum of a nonconvex--convex pair of polyhedra"],"prefix":"10.1145","volume":"30","author":[{"given":"Hichem","family":"Barki","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Lyon, CNRS, Universit\u00e9 Lyon 1, LIRIS UMR5205, Villeurbanne, France"}]},{"given":"Florence","family":"Denis","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lyon, CNRS, Universit\u00e9 Lyon 1, LIRIS UMR5205, Villeurbanne, France"}]},{"given":"Florent","family":"Dupont","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lyon, CNRS, Universit\u00e9 Lyon 1, LIRIS UMR5205, Villeurbanne, France"}]}],"member":"320","published-online":{"date-parts":[[2011,2,2]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Cgal. Computational geometry algorithms library. http:\/\/www.cgal.org.  Cgal. Computational geometry algorithms library. http:\/\/www.cgal.org."},{"key":"e_1_2_2_2_1","unstructured":"GNU MP. the GNU MP bignum library. http:\/\/gmplib.org.  GNU MP. the GNU MP bignum library. http:\/\/gmplib.org."},{"key":"e_1_2_2_3_1","unstructured":"Agarwal P. and Sharir M. 1998. Arrangements and their applications. In Handbook of Computational Geometry Elsevier Science Publishers B.V. North-Holland 49--119.  Agarwal P. and Sharir M. 1998. Arrangements and their applications. In Handbook of Computational Geometry Elsevier Science Publishers B.V. North-Holland 49--119."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250755"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2009.03.008"},{"volume-title":"Proceedings of the IEEE International Conference on Shape Modeling and Applications (SMI'09)","author":"Barki H.","key":"e_1_2_2_6_1","unstructured":"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. 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."},{"volume-title":"Proceedings of 2nd Workshop on the Algorithmic Foundations of Robotics. 171--184","author":"Basch J.","key":"e_1_2_2_7_1","unstructured":"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 . 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."},{"volume-title":"Proceedings of the International Conference on Computational Sciences-Part I (ICCS'01)","author":"Bekker H.","key":"e_1_2_2_8_1","unstructured":"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. 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."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802459"},{"key":"e_1_2_2_10_1","unstructured":"Evans R. O\u00f2Connor M. and Rossignac J. 1992. Construction of Minkowski sums and derivatives morphological combinations of arbitrary polyhedra in CAD\/CAM systems. US Patent 5159512.  Evans R. O\u00f2Connor M. and Rossignac J. 1992. Construction of Minkowski sums and derivatives morphological combinations of arbitrary polyhedra in CAD\/CAM systems. US Patent 5159512."},{"volume-title":"Proceedings of the 2nd Library-Centric Software Design.","author":"Fabri A.","key":"e_1_2_2_11_1","unstructured":"Fabri , A. and Pion , S . 2006. A generic lazy evaluation scheme for exact geometric computations . In Proceedings of the 2nd Library-Centric Software Design. Fabri, A. and Pion, S. 2006. A generic lazy evaluation scheme for exact geometric computations. In Proceedings of the 2nd Library-Centric Software Design."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2007.05.017"},{"key":"e_1_2_2_13_1","unstructured":"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.  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."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-8493(93)90023-3"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187878"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.1"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings 15th Annual European Symposium on Algorithms. 669--680","author":"Hachenberger P.","year":"2007","unstructured":"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 . 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."},{"key":"e_1_2_2_18_1","unstructured":"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.  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."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.11.009"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556412"},{"volume-title":"Proceedings of the International FCT-Conference on Fundamentals of Computation Theory. Springer, 207--218","author":"Hertel S.","key":"e_1_2_2_21_1","unstructured":"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 . 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."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-8493(92)90077-9"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00007-3"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/777792.777856"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/gmip.1998.0464"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/PG.2007.47"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of 8th Workshop on the Algorithmic Foundations of Robotics.","author":"Lien J.-M.","year":"2008","unstructured":"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. 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."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676196"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1080\/10867651.1997.10487472"},{"volume-title":"Image Analysis and Mathematical Morphology","author":"Serra J.","key":"e_1_2_2_30_1","unstructured":"Serra , J. 1982. Image Analysis and Mathematical Morphology , vol. 1 . Academic Press , London . Serra, J. 1982. Image Analysis and Mathematical Morphology, vol. 1. Academic Press, London."},{"volume-title":"Image Analysis and Mathematical Morphology","author":"Serra J.","key":"e_1_2_2_31_1","unstructured":"Serra , J. 1988. Image Analysis and Mathematical Morphology , vol. 2 . Academic Press , New York . Serra, J. 1988. Image Analysis and Mathematical Morphology, vol. 2. Academic Press, New York."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(99)00159-4"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2005.11.003"},{"key":"e_1_2_2_34_1","unstructured":"Weibel C. Minkowski sums. http:\/\/roso.epfl.ch\/cw\/poly\/public.php.  Weibel C. Minkowski sums. http:\/\/roso.epfl.ch\/cw\/poly\/public.php."},{"key":"e_1_2_2_35_1","unstructured":"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  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"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4485(03)00023-X"},{"key":"e_1_2_2_37_1","unstructured":"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  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"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195902000785"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1899404.1899407","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1899404.1899407","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:46Z","timestamp":1750244386000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1899404.1899407"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1145\/1899404.1899407"],"URL":"https:\/\/doi.org\/10.1145\/1899404.1899407","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2011,1]]},"assertion":[{"value":"2009-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-02-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}