“Convex polyhedral meshing for robust solid modeling” by Diazzi and Attene
Conference:
Type(s):
Title:
- Convex polyhedral meshing for robust solid modeling
Session/Category Title: Meshing
Presenter(s)/Author(s):
Abstract:
We introduce a new technique to create a mesh of convex polyhedra representing the interior volume of a triangulated input surface. Our approach is particularly tolerant to defects in the input, which is allowed to self-intersect, to be non-manifold, disconnected, and to contain surface holes and gaps. We guarantee that the input surface is exactly represented as the union of polygonal facets of the output volume mesh. Thanks to our algorithm, traditionally difficult solid modeling operations such as mesh booleans and Minkowski sums become surprisingly robust and easy to implement, even if the input has defects. Our technique leverages on the recent concept of indirect geometric predicate to provide an unprecedented combination of guaranteed robustness and speed, thus enabling the practical implementation of robust though flexible solid modeling systems. We have extensively tested our method on all the 10000 models of the Thingi10k dataset, and concluded that no existing method provides comparable robustness, precision and performances.
References:
1. Marc Alexa. 2020. Conforming Weighted Delaunay Triangulations. ACM Trans. Graph. 39, 6, Article 248 (Nov. 2020), 16 pages.
2. N. Amenta, S. Choi, and G. Rote. 2003. Incremental Constructions con BRIO. In Proceedings of the Nineteenth Annual Symposium on Computational Geometry (San Diego, California). Association for Computing Machinery, 9 pages.
3. Marco Attene. 2020. Indirect predicates for Geometric Constructions. Computer-Aided Design (2020).
4. Marco Attene, Marcel Campen, and Leif Kobbelt. 2013. Polygon mesh repairing: An application perspective. ACM Computing Surveys (CSUR) 45, 2 (2013), 15.
5. Hichem Barki, Gael Guennebaud, and Sebti Foufou. 2015. Exact, robust, and efficient regularized Booleans on general 3D meshes. Computers & Mathematics with Applications 70, 6 (2015), 1235–1254.
6. Gilbert Bernstein and Don Fussell. 2009. Fast, Exact, Linear Booleans. In Proceedings of the Symposium on Geometry Processing (Berlin, Germany) (SGP ’09). Eurographics Association, Goslar, DEU, 1269–1278.
7. Adrian Bowyer. 1981. Computing Dirichlet tessellations. Comput. J. 24, 2 (1981), 162–166.
8. Yuri Boykov and Vladimir Kolmogorov. 2004. An experimental comparison of mincut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Analysis and Machine Intelligence 26, 9 (2004), 1124–1137.
9. Yuri Boykov, Olga Veksler, and Ramin Zabih. 2001. Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Analysis and Machine Intelligence 23, 11 (2001), 1222–1239.
10. Marcel Campen and Leif Kobbelt. 2010a. Exact and Robust (Self-)Intersections for Polygonal Meshes. Comput. Graph. Forum 29 (05 2010), 397–406.
11. Marcel Campen and Leif Kobbelt. 2010b. Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes. Computer Graphics Forum 29, 5 (2010), 1613–1622.
12. Gianmarco Cherchi, Marco Livesu, Riccardo Scateni, and Marco Attene. 2020. Fast and Robust Mesh Arrangements Using Floating-Point Arithmetic. ACM Trans. Graph. 39, 6, Article 250 (Nov. 2020), 16 pages.
13. Leila De Floriani and Annie Hui. 2005. Data Structures for Simplicial Complexes: An Analysis And A Comparison. In Eurographics Symposium on Geometry Processing 2005, Mathieu Desbrun and Helmut Pottmann (Eds.). The Eurographics Association.
14. Salles Viana Gomes de Magalhäes, W Randolph Franklin, and Marcus Vinícius Alvim Andrade. 2020. An Efficient and Exact Parallel Algorithm for Intersecting Large 3-D Triangular Meshes Using Arithmetic Filters. Computer-Aided Design 120 (2020), 102801.
15. Olivier Devillers, Sylvain Lazard, and William J. Lenhart. 2018. 3D Snap Rounding. In 34th International Symposium on Computational Geometry (SoCG 2018) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 99), Bettina Speckmann and Csaba D. Tóth (Eds.). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 30:1–30:14.
16. Herbert Edelsbrunner. 1987. Algorithms in Combinatorial Geometry. Springer-Verlag.
17. F. R. Feito, C. J. Ogayar, R. J. Segura, and M. L. Rivero. 2013. Fast and Accurate Evaluation of Regularized Boolean Operations on Triangulated Solids. Comput. Aided Des. 45, 3 (March 2013), 705–716.
18. D. L. Ferrario and R. A. Piccinini. 2011. Simplicial Structures in Topology. Vol. CMS Books in Mathematics. Springer-Verlag New York.
19. Steven Fortune. 1999. Vertex-rounding a three-dimensional polyhedral subdivision. Discrete and Computational Geometry 22, 4 (1999), 593–618.
20. Peter Hachenberger. 2009. Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra into Convex Pieces. Algorithmica 55, 2 (01 Oct 2009), 329–345.
21. Peter Hachenberger, Lutz Kettner, and Kurt Mehlhorn. 2007. Boolean operations on 3D selective Nef complexes: Data structure, algorithms, optimized implementation and experiments. Computational Geometry 38, 1 (2007), 64 — 99. Special Issue on CGAL.
22. Michael Hemmer, Susan Hert, Sylvain Pion, and Stefan Schirra. 2019. Number Types. In CGAL User and Reference Manual (5.0 ed.). CGAL Editorial Board. https://doc.cgal.org/5.0/Manual/packages.html#PkgNumberTypes
23. Alexander Hornung and Leif Kobbelt. 2006. Robust Reconstruction of Watertight 3D Models from Non-Uniformly Sampled Point Clouds without Normal Information (SGP ’06). Eurographics Association, 41–50.
24. Yixin Hu, Teseo Schneider, Bolun Wang, Denis Zorin, and Daniele Panozzo. 2020. Fast Tetrahedral Meshing in the Wild. ACM Trans. Graph. 39, 4 (July 2020).
25. 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.
26. 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.
27. Tao Ju. 2004. Robust Repair of Polygonal Models. ACM Trans. Graph. 23, 3 (2004), 888–895.
28. C. Li, S. Pion, and C.K. Yap. 2005. Recent progress in exact geometric computation. The Journal of Logic and Algebraic Programming 64, 1 (2005), 85 — 111. Practical development of exact real number computation.
29. Célestin Marot, Jeanne Pellerin, and Jean-Francois Remacle. 2019. One machine, one minute, three billion tetrahedra. Internat. J. Numer. Methods Engrg. 117, 9 (2019), 967–990.
30. Victor Milenkovic and Elisha Sacks. 2019. Geometric rounding and feature separation in meshes. Computer-Aided Design 108 (2019), 12–18.
31. Julius Nehring-Wirxel, Philip Trettner, and Leif Kobbelt. 2021. Fast Exact Booleans for Iterated CSG using Octree-Embedded BSPs. Computer-Aided Design (to appear) 135 (July 2021).
32. J. Podolak and S. Rusinkiewicz. 2005. Atomic Volumes for Mesh Completion. In Symposium on Geometry Processing.
33. Jonathan Richard Shewchuk. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 3 (1997), 305–363.
34. Jonathan Richard Shewchuk. 1998. Tetrahedral mesh generation by Delaunay refinement. (1998), 86–95.
35. J. R. Shewchuk. 2003. Updating and Constructing Constrained Delaunay and Constrained Regular Triangulations by Flips. In Proceedings of the Nineteenth Annual Symposium on Computational Geometry (San Diego, California). Association for Computing Machinery, 181–190.
36. Hang Si. 2015. TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Transactions on Mathematical Software (TOMS) 41, 2 (2015), 1–36.
37. M. Wan, Y. Wang, E. Bae, X. C. Tai, and D. Wang. 2013. Reconstructing Open Surfaces via Graph-Cuts. IEEE transactions on visualization and computer graphics 19, 2 (2013), 306–318.
38. Bolun Wang, Teseo Schneider, Yixin Hu, Marco Attene, and Daniele Panozzo. 2020. Exact and Efficient Polyhedral Envelope Containment Check. ACM Trans. Graph. 39, 4, Article 114 (July 2020), 14 pages.
39. W. Zhao, S. Gao, and H. Lin. 2007. A robust hole-filling algorithm for triangular mesh. Visual Computer 23 (2007), 987–997.
40. K. Zhou, E. Zhang, J. Bittner, and Wonka P. 2008. Visibility-driven mesh analysis and visualization through graph cuts. IEEE Trans Vis Comput Graph 14, 6 (2008), 1667–74.
41. Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. 2016. Mesh arrangements for solid geometry. ACM Transactions on Graphics (TOG) 35, 4 (2016), 39.
42. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10, 000 3D-Printing Models. CoRR abs/1605.04797 (2016). arXiv:1605.04797
