“Tetrahedral meshing in the wild”
Conference:
Type:
Entry Number: 60
Title:
- Tetrahedral meshing in the wild
Presenter(s)/Author(s):
Abstract:
We propose a novel tetrahedral meshing technique that is unconditionally robust, requires no user interaction, and can directly convert a triangle soup into an analysis-ready volumetric mesh. The approach is based on several core principles: (1) initial mesh construction based on a fully robust, yet efficient, filtered exact computation (2) explicit (automatic or user-defined) tolerancing of the mesh relative to the surface input (3) iterative mesh improvement with guarantees, at every step, of the output validity. The quality of the resulting mesh is a direct function of the target mesh size and allowed tolerance: increasing allowed deviation from the initial mesh and decreasing the target edge length both lead to higher mesh quality.Our approach enables “black-box” analysis, i.e. it allows to automatically solve partial differential equations on geometrical models available in the wild, offering a robustness and reliability comparable to, e.g., image processing algorithms, opening the door to automatic, large scale processing of real-world geometric data.
References:
1. Frédéric Alauzet and David L. Marcum. 2013. A Closed Advancing-Layer Method with Changing Topology Mesh Movement for Viscous Mesh Generation. In 22nd International Meshing Roundtable, IMR 2013, October 13-16, 2013, Orlando, FL, USA.Google Scholar
2. Pierre Alliez, David Cohen-Steiner, Mariette Yvinec, and Mathieu Desbrun. 2005. Variational tetrahedral meshing. In ACM Transactions on Graphics (TOG), Vol. 24. ACM. Google ScholarDigital Library
3. Marco Attene. 2010. A Lightweight Approach to Repairing Digitized Polygon Meshes. Vis. Comput. 26, 11 (Nov. 2010), 1393–1406. Google ScholarDigital Library
4. Marco Attene. 2017. ImatiSTL – Fast and Reliable Mesh Processing with a Hybrid Kernel. In LNCS on Transactions on Computational Science XXIX – Volume 10220. Springer-Verlag New York, Inc., New York, NY, USA, 86–96. Google ScholarDigital Library
5. Marco Attene, Marcel Campen, and Leif Kobbelt. 2013. Polygon Mesh Repairing: An Application Perspective. ACM Comput. Surv. 45, 2, Article 15 (March 2013), 33 pages. Google ScholarDigital Library
6. Michael Bartoň, Iddo Hanniel, Gershon Elber, and Myung-Soo Kim. 2010. Precise Hausdorff distance computation between polygonal meshes. Computer Aided Geometric Design 27, 8 (2010), 580 — 591. Advances in Applied Geometry. Google ScholarDigital Library
7. Jean-Daniel Boissonnat and Steve Oudot. 2005. Provably good sampling and meshing of surfaces. Graphical Models 67, 5 (2005), 405–451. Google ScholarDigital Library
8. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, Marco Tarini, and Denis Zorin. 2012. State of the Art in Quad Meshing. In Eurographics STARS.Google Scholar
9. Mario Botsch and Leif Kobbelt. 2004. A Remeshing Approach to Multiresolution Modeling. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP ’04). ACM, New York, NY, USA, 185–192. Google ScholarDigital Library
10. Robert Bridson and Crawford Doran. 2014. Quartet: A tetrahedral mesh generator that does isosurface stuffing with an acute tetrahedral tile. https://github.com/crawforddoran/quartet.Google Scholar
11. Hervé Brönnimann, Andreas Fabri, Geert-Jan Giezeman, Susan Hert, Michael Hoffmann, Lutz Kettner, Sylvain Pion, and Stefan Schirra. 2017. 2D and 3D Linear Geometry Kernel. In CGAL User and Reference Manual (4.11 ed.). CGAL Editorial Board. http://doc.cgal.org/4.11/Manual/packages.html#PkgKernel23SummaryGoogle Scholar
12. Jonathan R. Bronson, Joshua A. Levine, and Ross T. Whitaker. 2012. Lattice Cleaving: Conforming Tetrahedral Meshes of Multimaterial Domains with Bounded Quality. In Proceedings of the 21st International Meshing Roundtable, IMR 2012, October 7-10, 2012, San Jose, CA, USA. 191–209.Google Scholar
13. Graham F Carey. 1997. Computational grids: generations, adaptation & solution strategies. CRC Press.Google Scholar
14. Long Chen and Jin-chao Xu. 2004. Optimal delaunay triangulations. Journal of Computational Mathematics (2004), 299–308.Google Scholar
15. Xiaoshen Chen, Dewen Peng, and Shuming Gao. 2012. SVM-Based Topological Optimization of Tetrahedral Meshes. In Proceedings of the 21st International Meshing Roundtable, IMR 2012, October 7-10, 2012, San Jose, CA, USA. 211–224.Google Scholar
16. Siu-Wing Cheng, Tamal K Dey, Herbert Edelsbrunner, Michael A Facello, and Shang-Hua Teng. 2000. Silver exudation. Journal of the ACM (JACM) 47, 5 (2000), 883–904. 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. Springer, 477–494.Google ScholarCross Ref
18. Siu-Wing Cheng, Tamal K Dey, and Jonathan Shewchuk. 2012. Delaunay mesh generation. CRC Press. Google ScholarDigital Library
19. L Paul Chew. 1989. Constrained delaunay triangulations. Algorithmica 4( 1989).Google Scholar
20. L Paul Chew. 1993. Guaranteed-quality mesh generation for curved surfaces. In Proceedings of the ninth annual symposium on Computational geometry. ACM, 274–280. Google ScholarDigital Library
21. David Cohen-Steiner, Eric Colin De Verdiere, and Mariette Yvinec. 2002. Conforming Delaunay triangulations in 3D. In Proceedings of the eighteenth annual symposium on Computational geometry. ACM, 199–208. Google ScholarDigital Library
22. Jean-Christophe Cuillière, Vincent François, and Jean-Marc Drouet. 2012. Automatic 3D Mesh Generation of Multiple Domains for Topology Optimization Methods. In Proceedings of the 21st International Meshing Roundtable, IMR 2012, October 7-10, 2012, San Jose, CA, USA. 243–259.Google Scholar
23. Tamal K Dey and Joshua A Levine. 2008. DelPSC: a Delaunay mesher for piecewise smooth complexes. In Proceedings of the twenty-fourth annual symposium on Computational geometry. ACM, 220–221. Google ScholarDigital Library
24. Crawford Doran, Athena Chang, and Robert Bridson. 2013. Isosurface Stuffing Improved: Acute Lattices and Feature Matching. In ACM SIGGRAPH 2013 Talks (SIGGRAPH ’13). ACM, New York, NY, USA, Article 38, 1 pages. Google ScholarDigital Library
25. Qiang Du and Desheng Wang. 2003. Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations. International journal for numerical methods in engineering 56, 9 (2003), 1355–1373.Google ScholarCross Ref
26. Marion Dunyach, David Vanderhaeghe, Loïc Barthe, and Mario Botsch. 2013. Adaptive Remeshing for Real-Time Mesh Deformation. In Eurographics 2013 – Short Papers, M.-A. Otaduy and O. Sorkine (Eds.). The Eurographics Association.Google Scholar
27. Darren Engwirda. 2016. Conforming restricted Delaunay mesh generation for piecewise smooth complexes. CoRR (2016). http://arxiv.org/abs/1606.01289Google Scholar
28. David Eppstein. 2001. Global optimization of mesh quality. Tutorial at the 10th Int. Meshing Roundtable (2001).Google Scholar
29. Noura Faraj, Jean-Marc Thiery, and Tamy Boubekeur. 2016. Multi-material Adaptive Volume Remesher. Comput. Graph. 58, C (Aug. 2016), 150–160. Google ScholarDigital Library
30. Gerald Farin. 2002. The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling. In Curves and Surfaces for CAGD (fifth edition ed.), Gerald Farin (Ed.). Morgan Kaufmann, San Francisco.Google Scholar
31. Lori A. Freitag and Carl Ollivier-Gooch. 1997. Tetrahedral mesh improvement using swapping and smoothing. Internat. J. Numer. Methods Engrg. 40, 21 (1997).Google ScholarCross Ref
32. Xifeng Gao, Wenzel Jakob, Marco Tarini, and Daniele Panozzo. 2017. Robust Hexdominant Mesh Generation Using Field-guided Polyhedral Agglomeration. ACM Trans. Graph. 36, 4, Article 114 (July 2017), 13 pages. Google ScholarDigital Library
33. Abel Gargallo-Peiró, Xevi Roca, Jaime Peraire, and Josep Sarrate. 2013. Defining Quality Measures for Validation and Generation of High-Order Tetrahedral Meshes. In Proceedings of the 22nd International Meshing Roundtable, IMR 2013, October 13-16, 2013, Orlando, FL, USA. 109–126.Google Scholar
34. RobertHaimes.2015. MOSS: multiple orthogonal strand system. Eng. Comput. (Lond.) 31, 3 (2015), 453–463. Google ScholarDigital Library
35. K. Hu, D. M. Yan, D. Bommes, P. Alliez, and B. Benes. 2017. Error-Bounded and Feature Preserving Surface Remeshing with Minimal Angle Improvement. IEEE Transactions on Visualization and Computer Graphics 23, 12 (Dec 2017), 2560–2573.Google ScholarCross Ref
36. Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung. 2013. Robust Inside-outside Segmentation Using Generalized Winding Numbers. ACM Trans. Graph. 32, 4, Article 33 (July 2013), 12 pages. Google ScholarDigital Library
37. Alec Jacobson, Daniele Panozzo, et al. 2016. libigl: A simple C++ geometry processing library. http://libigl.github.io/libigl/.Google Scholar
38. Wenzel Jakob, Marco Tarini, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Instant Field-Aligned Meshes. ACM Transactions on Graphics (Proceedings of SIGGRAPH ASIA) 34, 6 (Nov. 2015). Google ScholarDigital Library
39. Clément Jamin, Pierre Alliez, Mariette Yvinec, and Jean-Daniel Boissonnat. 2015. CGALmesh: a generic framework for delaunay mesh generation. ACM Transactions on Mathematical Software (TOMS) 41, 4 (2015), 23. Google ScholarDigital Library
40. Bhautik J. Joshi and Sébastien Ourselin. 2003. BSP-Assisted Constrained Tetrahedralization. In Proceedings of the 12th International Meshing Roundtable, IMR 2003, Santa Fe, New Mexico, USA, September 14-17, 2003. 251–260.Google Scholar
41. Bryan Matthew Klingner and Jonathan Richard Shewchuk. 2007. Agressive Tetrahedral Mesh Improvement. In Proceedings of the 16th International Meshing Roundtable. Seattle, Washington, 3–23. http://graphics.cs.berkeley.edu/papers/Klingner-ATM-2007-10/Google Scholar
42. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Trans. Graph. 35, 4, Article 134 (July 2016), 11 pages. Google ScholarDigital Library
43. François Labelle and Jonathan Richard Shewchuk. 2007. Isosurface stuffing: fast tetrahedral meshes with good dihedral angles. In ACM Transactions on Graphics (TOG), Vol. 26. ACM, 57. Google ScholarDigital Library
44. Bruno Lévy. 2018. Geogram. http://alice.loria.fr/index.php/software/4-library/75-geogram.html.Google Scholar
45. Manish Mandad, David Cohen-Steiner, and Pierre Alliez. 2015. Isotopic Approximation Within a Tolerance Volume. ACM Trans. Graph. 34, 4, Article 64 (July 2015), 12 pages. Google ScholarDigital Library
46. Marek Krzysztof Misztal and Jakob Andreas Bærentzen. 2012. Topology-adaptive interface tracking using the deformable simplicial complex. ACM Trans. Graph. 31, 3 (2012), 24:1–24:12. Google ScholarDigital Library
47. Neil Molino, Robert Bridson, and Ronald Fedkiw. 2003. Tetrahedral mesh generation for deformable bodies. In Proc. Symposium on Computer Animation.Google Scholar
48. Michael Murphy, David M Mount, and Carl W Gable. 2001. A point-placement strategy for conforming Delaunay tetrahedralization. International Journal of Computational Geometry & Applications 11, 06 (2001), 669–682.Google ScholarCross Ref
49. Steven J Owen. 1998. A survey of unstructured mesh generation technology.. In IMR.Google Scholar
50. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 2, Article 16 (April 2017), 16 pages. Google ScholarDigital Library
51. Jean-François Remacle. 2017. A two-level multithreaded Delaunay kernel. Computer-Aided Design 85 (2017), 2–9. Google ScholarDigital Library
52. Jim Ruppert. 1995. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. Journal of algorithms 18, 3 (1995), 548–585. Google ScholarDigital Library
53. Hanan Samet. 2005. Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. Google ScholarDigital Library
54. Erich Schönhardt. 1928. Über die zerlegung von dreieckspolyedern in tetraeder. Math. Ann. 98, 1 (1928), 309–312.Google ScholarCross Ref
55. Thomas W. Sederberg, Jianmin Zheng, Almaz Bakenov, and Ahmad Nasri. 2003. T-splines and T-NURCCs. ACM Trans. Graph. 22, 3 (July 2003), 477–484. Google ScholarDigital Library
56. Donald R Sheehy. 2012. New Bounds on the Size of Optimal Meshes. Comput. Graph. Forum 31, 5 (2012). Google ScholarDigital Library
57. Chen Shen, James F. O’Brien, and Jonathan R. Shewchuk. 2004. Interpolating and Approximating Implicit Surfaces from Polygon Soup. In Proceedings of ACM SIGGRAPH 2004. ACM Press, 896–904. http://graphics.cs.berkeley.edu/papers/Shen-IAI-2004-08/ Google ScholarDigital Library
58. Jonathan Richard Shewchuk. 1998. Tetrahedral mesh generation by Delaunay refinement. In Proceedings of the fourteenth annual symposium on Computational geometry. ACM, 86–95. Google ScholarDigital Library
59. Jonathan Richard Shewchuk. 2002a. Constrained Delaunay Tetrahedralizations and Provably Good Boundary Recovery.. In IMR. 193–204.Google Scholar
60. Jonathan Richard Shewchuk. 2002b. What Is a Good Linear Finite Element? – Interpolation, Conditioning, Anisotropy, and Quality Measures. Technical Report. In Proc. of the 11th International Meshing Roundtable.Google Scholar
61. Hang Si. 2015. TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator. ACM Trans. Math. Softw. 41, 2, Article 11 (Feb. 2015), 36 pages. Google ScholarDigital Library
62. Hang Si and Klaus Gärtner. 2005. Meshing Piecewise Linear Complexes by Constrained Delaunay Tetrahedralizations.. In IMR. Springer, 147–163.Google Scholar
63. Hang Si and Jonathan Richard Shewchuk. 2014. Incrementally constructing and updating constrained Delaunay tetrahedralizations with finite-precision coordinates. Eng. Comput. (Lond.) 30, 2 (2014), 253–269. Google ScholarDigital Library
64. Min Tang, Minkyoung Lee, and Young J. Kim. 2009. Interactive Hausdorff Distance Computation for General Polygonal Models. ACM Trans. Graph. 28, 3, Article 74 (July 2009), 9 pages. Google ScholarDigital Library
65. Jane Tournois, Camille Wormser, Pierre Alliez, and Mathieu Desbrun. 2009. Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation. ACM Transactions on Graphics 28, 3 (2009), Art-No. Google ScholarDigital Library
66. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models, https://ten-thousand-models.appspot.com. Technical Report. New York University.Google Scholar
