{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T01:56:15Z","timestamp":1782784575604,"version":"3.54.5"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2020,6,15]],"date-time":"2020-06-15T00:00:00Z","timestamp":1592179200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Luxcarta Technology"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2020,10,31]]},"abstract":"<jats:p>Converting point clouds into concise polygonal meshes in an automated manner is an enduring problem in computer graphics. Prior works, which typically operate by assembling planar shapes detected from input points, largely overlooked the scalability issue of processing a large number of shapes. As a result, they tend to produce overly simplified meshes with assembling approaches that can hardly digest more than 100 shapes in practice. We propose a shape assembling mechanism that is at least one order of magnitude more efficient, both in time and in number of processed shapes. Our key idea relies upon the design of a kinetic data structure for partitioning the space into convex polyhedra. Instead of slicing all the planar shapes exhaustively as prior methods, we create a partition where shapes grow at constant speed until colliding and forming polyhedra. This simple idea produces a lighter yet meaningful partition with a lower algorithmic complexity than an exhaustive partition. A watertight polygonal mesh is then extracted from the partition with a min-cut formulation. We demonstrate the robustness and efficacy of our algorithm on a variety of objects and scenes in terms of complexity, size, and acquisition characteristics. In particular, we show the method can both faithfully represent piecewise planar structures and approximate freeform objects while offering high resilience to occlusions and missing data.<\/jats:p>","DOI":"10.1145\/3376918","type":"journal-article","created":{"date-parts":[[2020,6,15]],"date-time":"2020-06-15T22:07:36Z","timestamp":1592258856000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":104,"title":["Kinetic Shape Reconstruction"],"prefix":"10.1145","volume":"39","author":[{"given":"Jean-Philippe","family":"Bauchet","sequence":"first","affiliation":[{"name":"Universit\u00e9 C\u00f4te d\u2019Azur, Inria, Sophia Antipolis, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florent","family":"Lafarge","sequence":"additional","affiliation":[{"name":"Universit\u00e9 C\u00f4te d\u2019Azur, Inria, Sophia Antipolis, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,15]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1810984"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2421636.2421642"},{"key":"e_1_2_2_3_1","volume-title":"Kinetic collision detection between two simple polygons. Comput. Geom. 27, 3","author":"Basch Julien","year":"2004","unstructured":"Julien Basch , Jeff Erickson , Leonidas J. Guibas , John Hershberger , and Li Zhang . 2004. Kinetic collision detection between two simple polygons. Comput. Geom. 27, 3 ( 2004 ). Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, and Li Zhang. 2004. Kinetic collision detection between two simple polygons. Comput. Geom. 27, 3 (2004)."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00332"},{"key":"e_1_2_2_6_1","volume-title":"Silva","author":"Berger Matthew","year":"2017","unstructured":"Matthew Berger , Andrea Tagliasacchi , Lee M. Seversky , Pierre Alliez , Gael Guennebaud , Joshua A. Levine , Andrei Sharf , and Claudio T . Silva . 2017 . A survey of surface reconstruction from point clouds. Comput. Graph. Forum 36, 1 (2017). Matthew Berger, Andrea Tagliasacchi, Lee M. Seversky, Pierre Alliez, Gael Guennebaud, Joshua A. Levine, Andrei Sharf, and Claudio T. Silva. 2017. A survey of surface reconstruction from point clouds. Comput. Graph. Forum 36, 1 (2017)."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2015.7298812"},{"key":"e_1_2_2_8_1","volume-title":"Polygon Mesh Processing","author":"Botsch Mario","unstructured":"Mario Botsch , Leif Kobbelt , Mark Pauly , Pierre Alliez , and Bruno L\u00e9vy . 2010. Polygon Mesh Processing . CRC Press . Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno L\u00e9vy. 2010. Polygon Mesh Processing. CRC Press."},{"key":"e_1_2_2_9_1","volume-title":"Martin De La Gorce, and Renaud Marlet","author":"Boulch Alexandre","year":"2014","unstructured":"Alexandre Boulch , Martin De La Gorce, and Renaud Marlet . 2014 . Piecewise-planar 3D reconstruction with edge and corner regularization. Comput. Graph. Forum 33, 5 (2014). Alexandre Boulch, Martin De La Gorce, and Renaud Marlet. 2014. Piecewise-planar 3D reconstruction with edge and corner regularization. Comput. Graph. Forum 33, 5 (2014)."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.60"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2010.5539824"},{"key":"e_1_2_2_12_1","volume-title":"Computing and fabricating multiplanar models. Comput. Graph. Forum","author":"Chen Desai","unstructured":"Desai Chen , Pitchaya Sitthi-Amorn , Justin T. Lan , and Wojciech Matusik . 2013. Computing and fabricating multiplanar models. Comput. Graph. Forum Vol. 32 . Desai Chen, Pitchaya Sitthi-Amorn, Justin T. Lan, and Wojciech Matusik. 2013. Computing and fabricating multiplanar models. Comput. Graph. Forum Vol. 32."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-007-0105-5"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186562.1015817"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the Conference on Neural Information Processing Systems.","author":"James","unstructured":"James M. Coughlan and Alan L. Yuille. 2000. The Manhattan world assumption: Regularities in scene statistics which enable Bayesian inference . In Proceedings of the Conference on Neural Information Processing Systems. James M. Coughlan and Alan L. Yuille. 2000. The Manhattan world assumption: Regularities in scene statistics which enable Bayesian inference. In Proceedings of the Conference on Neural Information Processing Systems."},{"key":"e_1_2_2_16_1","unstructured":"Guillaume Damiand. 2018. Combinatorial maps. In CGAL User and Reference Manual (4.14 ed.). CGAL Editorial Board.  Guillaume Damiand. 2018. Combinatorial maps. In CGAL User and Reference Manual (4.14 ed.). CGAL Editorial Board."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00313"},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of the SIGGRAPH Conference.","author":"Garland Michael","unstructured":"Michael Garland and Paul S. Heckbert . 1997. Surface simplification using quadric error metrics . In Proceedings of the SIGGRAPH Conference. Michael Garland and Paul S. Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the SIGGRAPH Conference."},{"key":"e_1_2_2_19_1","unstructured":"Simon Giraudot and Florent Lafarge. 2019. Classification. In CGAL User and Reference Manual (4.14 ed.). CGAL Editorial Board.  Simon Giraudot and Florent Lafarge. 2019. Classification. In CGAL User and Reference Manual (4.14 ed.). CGAL Editorial Board."},{"key":"e_1_2_2_20_1","volume-title":"Handbook of Data Structures and Applications","author":"Guibas Leonidas J.","unstructured":"Leonidas J. Guibas . 2004. Kinetic data structures . In Handbook of Data Structures and Applications . Routledge . Leonidas J. Guibas. 2004. Kinetic data structures. In Handbook of Data Structures and Applications. Routledge."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.1"},{"key":"e_1_2_2_22_1","unstructured":"Gurobi Optimization LLC. 2019. Gurobi Optimizer Reference Manual. http:\/\/www.gurobi.com.  Gurobi Optimization LLC. 2019. Gurobi Optimizer Reference Manual. http:\/\/www.gurobi.com."},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of the European Conference on Computer Vision (ECCV\u201918)","author":"Holzmann Thomas","year":"2018","unstructured":"Thomas Holzmann , Michael Maurer , Friedrich Fraundorfer , and Horst Bischof . 2018 . Semantically aware urban 3D reconstructionwith plane-based regularization . In Proceedings of the European Conference on Computer Vision (ECCV\u201918) . Thomas Holzmann, Michael Maurer, Friedrich Fraundorfer, and Horst Bischof. 2018. Semantically aware urban 3D reconstructionwith plane-based regularization. In Proceedings of the European Conference on Computer Vision (ECCV\u201918)."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602141"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2015.156"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818077"},{"key":"e_1_2_2_27_1","volume-title":"Freeform honeycomb structures. Comput. Graph. Forum 33","author":"Jiang Caigui","year":"2014","unstructured":"Caigui Jiang , Jun Wang , Johannes Wallner , and Helmut Pottmann . 2014. Freeform honeycomb structures. Comput. Graph. Forum 33 ( 2014 ). Caigui Jiang, Jun Wang, Johannes Wallner, and Helmut Pottmann. 2014. Freeform honeycomb structures. Comput. Graph. Forum 33 (2014)."},{"key":"e_1_2_2_28_1","volume-title":"Jose Alonso Ybanez Zepeda, and Tamy Boubekeur","author":"Kaiser Adrien","year":"2018","unstructured":"Adrien Kaiser , Jose Alonso Ybanez Zepeda, and Tamy Boubekeur . 2018 . A survey of simple geometric primitives detection methods for captured 3D data. Comput. Graph. Forum 37 (2018). Adrien Kaiser, Jose Alonso Ybanez Zepeda, and Tamy Boubekeur. 2018. A survey of simple geometric primitives detection methods for captured 3D data. Comput. Graph. Forum 37 (2018)."},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of the Symposium on Geometry Processing.","author":"Kazhdan Michael","year":"2006","unstructured":"Michael Kazhdan , Matthew Bolitho , and Hughes Hoppe . 2006 . Poisson surface reconstruction . In Proceedings of the Symposium on Geometry Processing. Michael Kazhdan, Matthew Bolitho, and Hughes Hoppe. 2006. Poisson surface reconstruction. In Proceedings of the Symposium on Geometry Processing."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487228.2487237"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073599"},{"key":"e_1_2_2_32_1","volume-title":"Robust and efficient surface reconstruction from range data. Comput. Graph. Forum 28, 8","author":"Labatut Patrick","year":"2009","unstructured":"Patrick Labatut , Jean-Philippe Pons , and Renaud Keriven . 2009. Robust and efficient surface reconstruction from range data. Comput. Graph. Forum 28, 8 ( 2009 ). Patrick Labatut, Jean-Philippe Pons, and Renaud Keriven. 2009. Robust and efficient surface reconstruction from range data. Comput. Graph. Forum 28, 8 (2009)."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12042"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2019.00276"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964947"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.344912"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.910883"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766995"},{"key":"e_1_2_2_39_1","volume-title":"Piecewise-planar reconstruction of multi-room interiors with arbitrary wall arrangements. Comput. Graph. Forum 35, 7","author":"Mura Claudio","year":"2016","unstructured":"Claudio Mura , Oliver Mattausch , and Renato Pajarola . 2016. Piecewise-planar reconstruction of multi-room interiors with arbitrary wall arrangements. Comput. Graph. Forum 35, 7 ( 2016 ). Claudio Mura, Oliver Mattausch, and Renato Pajarola. 2016. Piecewise-planar reconstruction of multi-room interiors with arbitrary wall arrangements. Comput. Graph. Forum 35, 7 (2016)."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/253284.253326"},{"key":"e_1_2_2_41_1","volume-title":"Luc Van Gool, and Werner Purgathofer","author":"Musialski Przemyslaw","year":"2013","unstructured":"Przemyslaw Musialski , Peter Wonka , Daniel G. Aliaga , Manuel Wimmer , Luc Van Gool, and Werner Purgathofer . 2013 . A survey of urban reconstruction. Comput. Graph. Forum 32, 6 (2013). Przemyslaw Musialski, Peter Wonka, Daniel G. Aliaga, Manuel Wimmer, Luc Van Gool, and Werner Purgathofer. 2013. A survey of urban reconstruction. Comput. Graph. Forum 32, 6 (2013)."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2017.258"},{"key":"e_1_2_2_43_1","volume-title":"Planar shape detection and regularization in tandem. Comput. Graph. Forum","author":"Oesau Sven","unstructured":"Sven Oesau , Florent Lafarge , and Pierre Alliez . 2016. Planar shape detection and regularization in tandem. Comput. Graph. Forum Vol. 35 . Sven Oesau, Florent Lafarge, and Pierre Alliez. 2016. Planar shape detection and regularization in tandem. Comput. Graph. Forum Vol. 35."},{"key":"e_1_2_2_44_1","unstructured":"Sven Oesau Yannick Verdie Cl\u00e9ment Jamin Pierre Alliez Florent Lafarge and Simon Giraudot. 2018. Point set shape detection. In CGAL User and Reference Manual (4.14 ed.). CGAL Editorial Board.  Sven Oesau Yannick Verdie Cl\u00e9ment Jamin Pierre Alliez Florent Lafarge and Simon Giraudot. 2018. Point set shape detection. In CGAL User and Reference Manual (4.14 ed.). CGAL Editorial Board."},{"key":"e_1_2_2_45_1","volume-title":"Proceedings of the International Society for Photogrammetry and Remote Sensing Conference 36","author":"Rabbani Tahir","year":"2006","unstructured":"Tahir Rabbani , Frank Van Den Heuvel , and George Vosselman . 2006 . Segmentation of point clouds using smoothness constraint . Proceedings of the International Society for Photogrammetry and Remote Sensing Conference 36 , 5 (2006). Tahir Rabbani, Frank Van Den Heuvel, and George Vosselman. 2006. Segmentation of point clouds using smoothness constraint. Proceedings of the International Society for Photogrammetry and Remote Sensing Conference 36, 5 (2006)."},{"key":"e_1_2_2_46_1","volume-title":"Structure-aware mesh decimation. Comput. Graph. Forum 34, 6","author":"Salinas David","year":"2015","unstructured":"David Salinas , Florent Lafarge , and Pierre Alliez . 2015. Structure-aware mesh decimation. Comput. Graph. Forum 34, 6 ( 2015 ). David Salinas, Florent Lafarge, and Pierre Alliez. 2015. Structure-aware mesh decimation. Comput. Graph. Forum 34, 6 (2015)."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCVW.2011.6130251"},{"key":"e_1_2_2_48_1","volume-title":"Completion and reconstruction with primitive shapes. Comput. Graph. Forum","author":"Schnabel Ruwen","unstructured":"Ruwen Schnabel , Patrick Degener , and Reinhard Klein . 2009. Completion and reconstruction with primitive shapes. Comput. Graph. Forum Vol. 28 . Ruwen Schnabel, Patrick Degener, and Reinhard Klein. 2009. Completion and reconstruction with primitive shapes. Comput. Graph. Forum Vol. 28."},{"key":"e_1_2_2_49_1","volume-title":"Efficient RANSAC for point-cloud shape detection. Comput. Graph. Forum","author":"Schnabel Ruwen","unstructured":"Ruwen Schnabel , Roland Wahl , and Reinhard Klein . 2007. Efficient RANSAC for point-cloud shape detection. Comput. Graph. Forum Vol. 26 . Ruwen Schnabel, Roland Wahl, and Reinhard Klein. 2007. Efficient RANSAC for point-cloud shape detection. Comput. Graph. Forum Vol. 26."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.445"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015810"},{"key":"e_1_2_2_52_1","volume-title":"Thijs Van Lankveld, and Remco C. Veltkamp","author":"Kreveld Marc Van","year":"2011","unstructured":"Marc Van Kreveld , Thijs Van Lankveld, and Remco C. Veltkamp . 2011 . On the shape of a set of points and lines in the plane. Comput. Graph. Forum 30 (2011). Marc Van Kreveld, Thijs Van Lankveld, and Remco C. Veltkamp. 2011. On the shape of a set of points and lines in the plane. Comput. Graph. Forum 30 (2011)."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2732527"},{"key":"e_1_2_2_54_1","article-title":"LSD: A fast line segment detector with a false detection control","volume":"32","author":"Gioi Rafael Von","year":"2010","unstructured":"Rafael Von Gioi , Jeremie Jakubowicz , Jean-Michel Morel , and Gregory Randall . 2010 . LSD: A fast line segment detector with a false detection control . Trans. Pattern Anal. Mach. Intell. 32 , 4 (2010). Rafael Von Gioi, Jeremie Jakubowicz, Jean-Michel Morel, and Gregory Randall. 2010. LSD: A fast line segment detector with a false detection control. Trans. Pattern Anal. Mach. Intell. 32, 4 (2010).","journal-title":"Trans. Pattern Anal. Mach. Intell."},{"key":"e_1_2_2_55_1","volume-title":"Thingi10K: A dataset of 10, 000 3D-printing models. arXiv:1605.04797","author":"Zhou Qingnan","year":"2016","unstructured":"Qingnan Zhou and Alec Jacobson . 2016. Thingi10K: A dataset of 10, 000 3D-printing models. arXiv:1605.04797 ( 2016 ). Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A dataset of 10, 000 3D-printing models. arXiv:1605.04797 (2016)."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3376918","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3376918","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:48Z","timestamp":1750202628000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3376918"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,15]]},"references-count":54,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,10,31]]}},"alternative-id":["10.1145\/3376918"],"URL":"https:\/\/doi.org\/10.1145\/3376918","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,15]]},"assertion":[{"value":"2019-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}