“Alpha wrapping with an offset” by Portaneri, Rouxel-Labbé, Hemmer, Cohen-Steiner and Alliez

Given an input 3D geometry such as a triangle soup or a point set, we address the problem of generating a watertight and orientable surface triangle mesh that strictly encloses the input. The output mesh is obtained by greedily refining and carving a 3D Delaunay triangulation on an offset surface of the input, while carving with empty balls of radius alpha. The proposed algorithm is controlled via two user-defined parameters: alpha and offset. Alpha controls the size of cavities or holes that cannot be traversed during carving, while offset controls the distance between the vertices of the output mesh and the input. Our algorithm is guaranteed to terminate and to yield a valid and strictly enclosing mesh, even for defect-laden inputs. Genericity is achieved using an abstract interface probing the input, enabling any geometry to be used, provided a few basic geometric queries can be answered. We benchmark the algorithm on large public datasets such as Thingi10k, and compare it to state-of-the-art approaches in terms of robustness, approximation, output complexity, speed, and peak memory consumption. Our implementation is available through the CGAL library.

1. Rémi Allegre, Raphaëlle Chaine, and Samir Akkouche. 2005. Convection-driven dynamic surface reconstruction. In International Conference on Shape Modeling and Applications. IEEE, IEEE, Cambridge, Massachusetts, USA., 33–42.Google ScholarDigital Library
2. Pierre Alliez, Stéphane Tayeb, and Camille Wormser. 2021. 3D Fast Intersection and Distance Computation. In CGAL User and Reference Manual (5.3.1 ed.). CGAL Editorial Board, Sophia Antipolis, France. https://doc.cgal.org/5.3.1/Manual/packages.html#PkgAABBTreeGoogle Scholar
3. Marco Attene, Marcel Campen, and Leif Kobbelt. 2013. Polygon mesh repairing: An application perspective. ACM Computing Surveys (CSUR) 45, 2 (2013), 1–33.Google ScholarDigital Library
4. Gino van den Bergen. 1997. Efficient collision detection of complex deformable models using AABB trees. Journal of graphics tools 2, 4 (1997), 1–13.Google ScholarDigital Library
5. 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. Computer Graphics Forum 36 (2017), 301–329.Google ScholarDigital Library
6. Fausto Bernardini and Chandrajit L Bajaj. 1997. Sampling and reconstructing manifolds using alpha-shapes. In Proceedings of Canadian Conference on Computational Geometry. Unknown publisher, Kingston, Ontario, Canada, 193–198.Google Scholar
7. Fausto Bernardini, Chandrajit L Bajaj, Jindong Chen, and Daniel R Schikore. 1999. Automatic reconstruction of 3D CAD models from digital scans. International Journal of Computational Geometry and Applications 9, 04n05 (1999), 327–369.Google ScholarCross Ref
8. Stefan Bischoff, Darko Pavic, and Leif Kobbelt. 2005. Automatic Restoration of Polygon Models. ACM Transactions on Graphics 24 (2005), 1332–1352.Google ScholarDigital Library
9. Jean-Daniel Boissonnat. 1984. Geometric structures for three-dimensional shape representation. ACM Transactions on Graphics (TOG) 3, 4 (1984), 266–286.Google ScholarDigital Library
10. Jean-Daniel Boissonnat and Steve Oudot. 2005. Provably good sampling and meshing of surfaces. Graph. Models 67, 5 (2005), 405–451.Google ScholarDigital Library
11. Mario Botsch and Leif Kobbelt. 2001. A Robust Procedure to Eliminate Degenerate Faces from Triangle Meshes. In Proceedings of the Vision Modeling and Visualization conference. Aka GmbH, Stuttgart, Germany, 283–290.Google Scholar
12. Hervé Brönnimann, Christoph Burnikel, and Sylvain Pion. 2001. Interval arithmetic yields efficient dynamic filters for computational geometry. Discrete Applied Mathematics 109, 1–2 (2001), 25–47.Google ScholarDigital Library
13. Fatih Calakli and Gabriel Taubin. 2011. SSD: Smooth signed distance surface reconstruction. Computer Graphics Forum 30, 7 (2011), 1993–2002.Google ScholarCross Ref
14. Stéphane Calderon and Tamy Boubekeur. 2017. Bounding proxies for shape approximation. ACM Transactions on Graphics (TOG) 36, 4 (2017), 1–13.Google ScholarDigital Library
15. Marcel Campen and Leif Kobbelt. 2010. Exact and robust (self-) intersections for polygonal meshes. Computer Graphics Forum 29, 2 (2010), 397–406.Google ScholarCross Ref
16. Chia-Tche Chang, Bastien Gorissen, and Samuel Melchior. 2011. Fast oriented bounding box optimization on the rotation group SO (3, R). ACM Transactions on Graphics (TOG) 30, 5 (2011), 1–16.Google ScholarDigital Library
17. Siu-Wing Cheng, Tamal K Dey, and Joshua A Levine. 2008. A practical Delaunay meshing algorithm for a large class of domains. In Proceedings of the 16th International Meshing Roundtable. IMR, Springer, USA, 477–494.Google ScholarCross Ref
18. Siu-Wing Cheng, Tamal K Dey, and Edgar A Ramos. 2010. Delaunay refinement for piecewise smooth complexes. Discrete & Computational Geometry 43, 1 (2010), 121–166.Google ScholarDigital Library
19. Siu-Wing Cheng, Tamal K. Dey, and Jonathan Shewchuk. 2012. Delaunay Mesh Generation (1st ed.). Chapman and Hall/CRC, Florida, USA.Google Scholar
20. Tamal Dey. 2010. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis by Tamal K. Dey Cambridge University Press. SIGACT News 41, 1 (mar 2010), 24–27.Google Scholar
21. Lorenzo Diazzi and Marco Attene. 2021. Convex Polyhedral Meshing for Robust Solid Modeling. ACM Transactions on Graphics 40, 6, Article 259 (dec 2021), 16 pages.Google ScholarDigital Library
22. Herbert Edelsbrunner. 2003. Surface reconstruction by wrapping finite sets in space. In Discrete and computational geometry. Springer, USA, 379–404.Google Scholar
23. Herbert Edelsbrunner and Ernst P Mücke. 1994. Three-dimensional alpha shapes. ACM Transactions on Graphics (TOG) 13, 1 (1994), 43–72.Google ScholarDigital Library
24. Joachim Giesen, Frédéric Cazals, Mark Pauly, and Afra Zomorodian. 2006. The conformal alpha shape filtration. The Visual Computer 22, 8 (2006), 531–540.Google ScholarCross Ref
25. Joachim Giesen and Matthias John. 2002. Surface reconstruction based on a dynamical system. Computer graphics forum 21, 3 (2002), 363–371.Google Scholar
26. Stefan Gumhold, Pavel Borodin, and Reinhard Klein. 2003. Intersection free simplification. International Journal of Shape Modeling 9, 02 (2003), 155–176.Google ScholarCross Ref
27. Baining Guo, Jai Menon, and Brian Willette. 1997. Surface reconstruction using alpha shapes. Computer graphics forum 16, 4 (1997), 177–190.Google Scholar
28. Yixin Hu, Teseo Schneider, Bolun Wang, Denis Zorin, and Daniele Panozzo. 2020. Fast tetrahedral meshing in the wild. ACM Transactions on Graphics (TOG) 39, 4 (2020), 117–1.Google ScholarDigital Library
29. Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2018. Tetrahedral Meshing in the Wild. ACM Trans. Graph. 37, 4, Article 60 (July 2018), 14 pages. Google ScholarDigital Library
30. Jingwei Huang, Hao Su, and Leonidas J. Guibas. 2018. Robust Watertight Manifold Surface Generation Method for ShapeNet Models. CoRR abs/1802.01698 (2018), 1–10. http://arxiv.org/abs/1802.01698Google Scholar
31. Jingwei Huang, Yichao Zhou, and Leonidas J. Guibas. 2020. ManifoldPlus: A Robust and Scalable Watertight Manifold Surface Generation Method for Triangle Soups. CoRR abs/2005.11621 (2020), 1–10. arXiv:2005.11621 https://arxiv.org/abs/2005.11621Google Scholar
32. Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung. 2013. Robust inside-outside segmentation using generalized winding numbers. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–12.Google ScholarDigital Library
33. Tao Ju. 2004. Robust Repair of Polygonal Models. ACM Transactions on Graphics 23, 3 (2004), 888–895.Google ScholarDigital Library
34. Franjo Juretić and Norbert Putz. 2011. A Surface-Wrapping Algorithm with Hole Detection Based on the Heat Diffusion Equation. In Proceedings of the 20th International Meshing Roundtable. Springer, New York, USA, 405–418.Google ScholarCross Ref
35. Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. 2006. Poisson Surface Reconstruction. In Proceedings of EUROGRAPHICS Symposium on Geometry Processing. Eurographics Association, Cagliari, Sardinia, Italy, 61–70.Google Scholar
36. Leif Kobbelt, Jens Vorsatz, Ulf Labsik, and Hans-Peter Seidel. 1999. A shrink wrapping approach to remeshing polygonal surfaces. Computer Graphics Forum 18, 3 (1999), 119–130.Google ScholarCross Ref
37. Sebastian Koch, Albert Matveev, Zhongshi Jiang, Francis Williams, Alexey Artemov, Evgeny Burnaev, Marc Alexa, Denis Zorin, and Daniele Panozzo. 2019. ABC: A Big CAD Model Dataset For Geometric Deep Learning. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, USA, 1–10.Google Scholar
38. YK Lee, Chin K Lim, Hamid Ghazialam, Harsh Vardhan, and Erling Eklund. 2010. Surface mesh generation for dirty geometries by the Cartesian shrink-wrapping technique. Engineering with Computers 26, 4 (2010), 377–390.Google ScholarDigital Library
39. Peter Liepa. 2003. Filling holes in meshes. In Proceedings of the ACM/Eurographics Symposium on Geometry Processing. ACM, Aachen, 200–205.Google Scholar
40. Alexander Malyshev, Artem Zhidkov, Vadim Turlapov, and France Guyancourt. 2018. Adaptive mesh generation using shrink wrapping approach. In Proceedings of GraphiCon’2018. GraphiCon Scientific Society, Tomsk, Russia, 479–483.Google Scholar
41. D Martineau, J Gould, and J Papper. 2016. An integrated framework for wrapping and mesh generation of complex geometries. In European Congress on Computational Methods in Applied Sciences and Engineering (Greece). ECCOMAS, Europe, 6938–6954.Google ScholarCross Ref
42. Fakir Nooruddin and Greg Turk. 2003. Simplification and Repair of Polygonal Models Using Volumetric Techniques. IEEE Transactions on Visualization and Computer Graphics 9, 2 (2003), 191–205.Google ScholarDigital Library
43. Leonardo Sacht, Etienne Vouga, and Alec Jacobson. 2015. Nested cages. ACM Transactions on Graphics (TOG) 34, 6 (2015), 1–14.Google ScholarDigital Library
44. Pedro V Sander, Xianfeng Gu, Steven J Gortler, Hugues Hoppe, and John Snyder. 2000. Silhouette clipping. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques. ACM Press, USA, 327–334.Google ScholarDigital Library
45. Silvia Sellán, Noam Aigerman, and Alec Jacobson. 2021. Swept Volumes via Spacetime Numerical Continuation. ACM Transactions on Graphics 40, 4 (2021), 11 pages.Google ScholarDigital Library
46. Chen Shen, James F. O’Brien, and Jonathan R. Shewchuk. 2004. Interpolating and Approximating Implicit Surfaces from Polygon Soup. ACM Transactions on Graphics 23, 3 (2004), 896–904.Google ScholarDigital Library
47. David A Stuart, Joshua A Levine, Ben Jones, and Adam W Bargteil. 2013. Automatic construction of coarse, high-quality tetrahedralizations that enclose and approximate surfaces for animation. In Proceedings of Motion on Games. ACM, USA, 213–222.Google ScholarDigital Library
48. Marek Teichmann and Michael Capps. 1998. Surface reconstruction with anisotropic density-scaled alpha shapes. In Proceedings of Visualization (Research Triangle Park, North Carolina, USA). IEEE, IEEE, USA, 67–72.Google ScholarCross Ref
49. The CGAL Project. 2021. CGAL User and Reference Manual (5.3 ed.). CGAL Editorial Board, Sophia Antipolis, France. https://doc.cgal.org/5.3/Manual/packages.htmlGoogle Scholar
50. Andreas Von Dziegielewski, Michael Hemmer, and Elmar Schömer. 2013. High precision conservative surface mesh generation for swept volumes. IEEE Transactions on Automation Science and Engineering 12, 1 (2013), 183–191.Google ScholarCross Ref
51. Karl D. D. Willis, Yewen Pu, Jieliang Luo, Hang Chu, Tao Du, Joseph G. Lambourne, Armando Solar-Lezama, and Wojciech Matusik. 2021. Fusion 360 Gallery: A Dataset and Environment for Programmatic CAD Construction from Human Design Sequences. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–10.Google ScholarDigital Library
52. Hongyi Xu and Jernej Barbič. 2014. Signed Distance Fields for Polygon Soup Meshes. In Proceedings of Graphics Interface 2014 (Montreal, Quebec, Canada) (GI ’14). Canadian Information Processing Society, CAN, 35–41.Google ScholarDigital Library
53. Wang Yifan, Noam Aigerman, Vladimir G Kim, Siddhartha Chaudhuri, and Olga Sorkine-Hornung. 2020. Neural cages for detail-preserving 3D deformations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. IEEE, Nashville, 75–83.Google ScholarCross Ref
54. Tong Zhao, Pierre Alliez, Tamy Boubekeur, Laurent Busé, and Jean-Marc Thiery. 2021. Progressive Discrete Domains for Implicit Surface Reconstruction. Computer Graphics Forum 40, 5 (2021), 143–156.Google ScholarCross Ref
55. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv:1605.04797 [cs.GR]Google Scholar