Yixin Hu
Skip Abstract Section
Skip Supplemental Material SectionAbstract
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.
Supplemental Material
Available for Download
zip
repository.zip (15.3 MB)
This is an implementation of the algorithm described in "Tetrahedral Meshing in the Wild", published in ACM Trans. Graph. Vol. 37(4), 2018. The software is quite easy to use. Basically, users only need to provide a surface triangle mesh as input and our mesher would output a tetrahedral mesh by using default settings. If you want to customize your own tetmeshes, we also provide some options.The code is also available on GitHub: https://github.com/Yixin-Hu/TetWild
- 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
- 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
- Marco Attene. 2010. A Lightweight Approach to Repairing Digitized Polygon Meshes. Vis. Comput. 26, 11 (Nov. 2010), 1393--1406. Google ScholarDigital Library
- 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
- 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
- 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
- Jean-Daniel Boissonnat and Steve Oudot. 2005. Provably good sampling and meshing of surfaces. Graphical Models 67, 5 (2005), 405--451. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- 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
- Graham F Carey. 1997. Computational grids: generations, adaptation & solution strategies. CRC Press.Google Scholar
- Long Chen and Jin-chao Xu. 2004. Optimal delaunay triangulations. Journal of Computational Mathematics (2004), 299--308.Google Scholar
- 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
- 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
- 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
- Siu-Wing Cheng, Tamal K Dey, and Jonathan Shewchuk. 2012. Delaunay mesh generation. CRC Press. Google ScholarDigital Library
- L Paul Chew. 1989. Constrained delaunay triangulations. Algorithmica 4( 1989).Google Scholar
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Darren Engwirda. 2016. Conforming restricted Delaunay mesh generation for piecewise smooth complexes. CoRR (2016). http://arxiv.org/abs/1606.01289Google Scholar
- David Eppstein. 2001. Global optimization of mesh quality. Tutorial at the 10th Int. Meshing Roundtable (2001).Google Scholar
- 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
- 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
- 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
- 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
- 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
- RobertHaimes.2015. MOSS: multiple orthogonal strand system. Eng. Comput. (Lond.) 31, 3 (2015), 453--463. Google ScholarDigital Library
- 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
- 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
- Alec Jacobson, Daniele Panozzo, et al. 2016. libigl: A simple C++ geometry processing library. http://libigl.github.io/libigl/.Google Scholar
- 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
- 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
- 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
- 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
- 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
- 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
- Bruno Lévy. 2018. Geogram. http://alice.loria.fr/index.php/software/4-library/75-geogram.html.Google Scholar
- 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
- 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
- Neil Molino, Robert Bridson, and Ronald Fedkiw. 2003. Tetrahedral mesh generation for deformable bodies. In Proc. Symposium on Computer Animation.Google Scholar
- 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
- Steven J Owen. 1998. A survey of unstructured mesh generation technology.. In IMR.Google Scholar
- 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
- Jean-François Remacle. 2017. A two-level multithreaded Delaunay kernel. Computer-Aided Design 85 (2017), 2--9. Google ScholarDigital Library
- Jim Ruppert. 1995. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. Journal of algorithms 18, 3 (1995), 548--585. Google ScholarDigital Library
- 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
- Erich Schönhardt. 1928. Über die zerlegung von dreieckspolyedern in tetraeder. Math. Ann. 98, 1 (1928), 309--312.Google ScholarCross Ref
- 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
- Donald R Sheehy. 2012. New Bounds on the Size of Optimal Meshes. Comput. Graph. Forum 31, 5 (2012). Google ScholarDigital Library
- 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
- 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
- Jonathan Richard Shewchuk. 2002a. Constrained Delaunay Tetrahedralizations and Provably Good Boundary Recovery.. In IMR. 193--204.Google Scholar
- 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
- 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
- Hang Si and Klaus Gärtner. 2005. Meshing Piecewise Linear Complexes by Constrained Delaunay Tetrahedralizations.. In IMR. Springer, 147--163.Google Scholar
- 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
- 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
- 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
- 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
Index Terms
- Tetrahedral meshing in the wild
Recommendations
Fast tetrahedral meshing in the wild
We propose a new tetrahedral meshing method, fTetWild, to convert triangle soups into high-quality tetrahedral meshes. Our method builds on the TetWild algorithm, replacing the rational triangle insertion with a new incremental approach to construct and ...
Delaunay meshing of isosurfaces
We present an isosurface meshing algorithm, DelIso, based on the Delaunay refinement paradigm. This paradigm has been successfully applied to mesh a variety of domains with guarantees for topology, geometry, mesh gradedness, and triangle shape. A ...
2-manifold surface meshing using dual contouring with tetrahedral decomposition
The Dual Contouring algorithm (DC) is a grid-based process used to generate surface meshes from volumetric data. The advantage of DC is that it can reproduce sharp features by inserting vertices anywhere inside the grid cube, as opposed to the Marching ...
Comments