“Conforming weighted delaunay triangulations” by Alexa
Conference:
Type(s):
Title:
- Conforming weighted delaunay triangulations
Session/Category Title: Meticulous Meshes
Presenter(s)/Author(s):
Abstract:
Given a set of points together with a set of simplices we show how to compute weights associated with the points such that the weighted Delaunay triangulation of the point set contains the simplices, if possible. For a given triangulated surface, this process provides a tetrahedral mesh conforming to the triangulation, i.e. solves the problem of meshing the triangulated surface without inserting additional vertices. The restriction to weighted Delaunay triangulations ensures that the orthogonal dual mesh is embedded, facilitating common geometry processing tasks.We show that the existence of a single simplex in a weighted Delaunay triangulation for given vertices amounts to a set of linear inequalities, one for each vertex. This means that the number of inequalities for a given triangle mesh is quadratic in the number of mesh elements, making the naive approach impractical. We devise an algorithm that incrementally selects a small subset of inequalities, repeatedly updating the weights, until the weighted Delaunay triangulation contains all constrained simplices or the problem becomes infeasible. Applying this algorithm to a range of triangle meshes commonly used graphics demonstrates that many of them admit a conforming weighted Delaunay triangulation, in contrast to conforming or constrained Delaunay that require additional vertices to split the input primitives.
References:
1. Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S. Ebeida, Ahmed H. Mahmoud, Scott A. Mitchell, John D. Owens, and Ahmad A. Rushdi. 2020. VoroCrust: Voronoi Meshing Without Clipping. ACM Trans. Graph. 39, 3, Article 23 (May 2020), 16 pages. Google ScholarDigital Library
2. Marc Alexa, Philipp Herholz, Maximilian Kohlbrenner, and Olga Sorkine-Hornung. 2020. Properties of Laplace Operators for Tetrahedral Meshes. Computer Graphics Forum 39, 5 (2020), 55–68. Google ScholarCross Ref
3. Pierre Alliez, David Cohen-Steiner, Mariette Yvinec, and Mathieu Desbrun. 2005. Variational Tetrahedral Meshing. ACM Trans. Graph. 24, 3 (July 2005), 617–625. Google ScholarDigital Library
4. Pierre Alliez, Clément Jamin, Laurent Rineau, Stéphane Tayeb, Jane Tournois, and Mariette Yvinec. 2020. 3D Mesh Generation. In CGAL User and Reference Manual (5.0.2 ed.). CGAL Editorial Board. https://doc.cgal.org/5.0.2/Manual/packages.html#PkgMesh3Google Scholar
5. Nina Amenta, Dominique Attali, and Olivier Devillers. 2007. Complexity of Delaunay Triangulation for Points on Lower-Dimensional Polyhedra. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, USA, 1106?1113.Google ScholarDigital Library
6. Nina Amenta and Marshall Bern. 1998. Surface Reconstruction by Voronoi Filtering. In Proceedings of the Fourteenth Annual Symposium on Computational Geometry. Association for Computing Machinery, New York, NY, USA, 39–48. Google ScholarDigital Library
7. Nina Amenta, Sunghee Choi, and Ravi Krishna Kolluri. 2001. The Power Crust. In Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications. Association for Computing Machinery, New York, NY, USA, 249–266. Google ScholarDigital Library
8. Dominique Attali, Jean-Daniel Boissonnat, and André Lieutier. 2003. Complexity of the Delaunay Triangulation of Points on Surfaces the Smooth Case. In Proceedings of the Nineteenth Annual Symposium on Computational Geometry. Association for Computing Machinery, New York, NY, USA, 201–210. Google ScholarDigital Library
9. Franz Aurenhammer. 1987a. A Criterion for the Affine Equivalence of Cell Complexes In Rd and Convex Polyhedra In Rd+1. Discrete Comput. Geom. 2, 1 (Dec. 1987), 49–64. Google ScholarDigital Library
10. Franz Aurenhammer. 1987b. Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16, 1 (1987), 78–96.Google ScholarDigital Library
11. Franz Aurenhammer and Rolf Klein. 2000. Voronoi Diagrams. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia (Eds.). North-Holland, Amsterdam, Chapter 5, 201–290. Google ScholarCross Ref
12. Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee. 2013. Voronoi Diagrams and Delaunay Triangulations. WORLD SCIENTIFIC. Google ScholarCross Ref
13. Frédéric Chazal and André Lieutier. 2005. The “λ Medial Axis”. Graph. Models 67, 4 (July 2005), 304âĂŞ331. Google ScholarDigital Library
14. Bernard Chazelle and Leonidas Palios. 1990. Triangulating a Nonconvex Polytope. Discrete Comput. Geom. 5, 5 (Dec. 1990), 505–526. Google ScholarDigital Library
15. Long Chen. 2004. Mesh Smoothing Schemes Based on Optimal Delaunay Triangulations.. In Proceedings, 13th International Meshing Roundtable. Sandia National Laboratories, Williamburg, VA, USA, 109–120.Google Scholar
16. Long Chen and Jinchao Xu. 2004. Optimal Delaunay Triangulations. Journal of Computational Mathematics 22, 2 (2004), 299–308.Google Scholar
17. Zhonggui Chen, Wenping Wang, Bruno Lèvy, L.igang Liu, and Feng Sun. 2014. Revisiting Optimal Delaunay Triangulation for 3D Graded Mesh Generation. SIAM Journal on Scientific Computing 36, 3 (2014), A930–A954. Google ScholarCross Ref
18. Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, and Shang-Hua Teng. 2000. Sliver Exudation. J. ACM 47, 5 (Sept. 2000), 883–904. Google ScholarDigital Library
19. Siu-Wing Cheng, Tamal K. Dey, and Jonathan Shewchuk. 2012. Delaunay Mesh Generation (1st ed.). Chapman & Hall/CRC.Google Scholar
20. L. Paul Chew. 1987. Constrained Delaunay Triangulations. In Proceedings of the Third Annual Symposium on Computational Geometry. ACM, New York, NY, USA, 215–222. Google ScholarDigital Library
21. L. Paul Chew. 1993. Guaranteed-Quality Mesh Generation for Curved Surfaces. In Proceedings of the Ninth Annual Symposium on Computational Geometry. Association for Computing Machinery, New York, NY, USA, 274?280. Google ScholarDigital Library
22. John W. Chinneck. 2007. Feasibility and Infeasibility in Optimization: Algorithms and Computational Methods (1st ed.). Springer Publishing Company, Incorporated.Google Scholar
23. Paolo Cignoni, Marco Callieri, Massimiliano Corsini, Matteo Dellepiane, Fabio Ganovelli, and Guido Ranzuglia. 2008. MeshLab: an Open-Source Mesh Processing Tool. In Eurographics Italian Chapter Conference, Vittorio Scarano, Rosario De Chiara, and Ugo Erra (Eds.). The Eurographics Association. Google ScholarCross Ref
24. David Cohen-Steiner, Éric Colin de Verdière, and Mariette Yvinec. 2002. Conforming Delaunay Triangulations in 3D. In Proceedings of the Eighteenth Annual Symposium on Computational Geometry. Association for Computing Machinery, New York, NY, USA, 199?208. Google ScholarDigital Library
25. Keenan Crane, Fernando de Goes, Mathieu Desbrun, and Peter Schröder. 2013. Digital Geometry Processing with Discrete Exterior Calculus. In ACM SIGGRAPH 2013 Courses. Association for Computing Machinery, New York, NY, USA, Article Article 7, 126 pages. Google ScholarDigital Library
26. Fernando de Goes, Pierre Alliez, Houman Owhadi, and Mathieu Desbrun. 2013. On the Equilibrium of Simplicial Masonry Structures. ACM Trans. Graph. 32, 4, Article Article 93 (July 2013), 10 pages. Google ScholarDigital Library
27. Fernando de Goes, Pooran Memari, Patrick Mullen, and Mathieu Desbrun. 2014. Weighted Triangulations for Geometry Processing. ACM Trans. Graph. 33, 3, Article Article 28 (June 2014), 13 pages. Google ScholarDigital Library
28. Fernando de Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, and Mathieu Desbrun. 2015. Power Particles: An Incompressible Fluid Solver Based on Power Diagrams. ACM Trans. Graph. 34, 4, Article Article 50 (July 2015), 11 pages. Google ScholarDigital Library
29. Jesus A. De Loera, Jorg Rambau, and Francisco Santos. 2010. Triangulations: Structures for Algorithms and Applications (1st ed.). Springer Publishing Company, Incorporated.Google ScholarCross Ref
30. Olivier Devillers, Sylvain Pion, and Monique Teillaud. 2001. Walking in a triangulation. Technical Report RR-4120. INRIA. https://hal.inria.fr/inria-00072509Google Scholar
31. Tamal K. Dey and Wulue Zhao. 2003. Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee. Algorithmica 38, 1 (Oct. 2003), 179–200. Google ScholarDigital Library
32. Qiang Du, Vance Faber, and Max Gunzburger. 1999. Centroidal Voronoi Tessellations: Applications and Algorithms. SIAM Rev. 41, 4 (Dec. 1999), 637âĂŞ676. Google ScholarDigital Library
33. Herbert Edelsbrunner and Nimish R. Shah. 1992. Incremental Topological Flipping Works for Regular Triangulations. In Proceedings of the Eighth Annual Symposium on Computational Geometry. ACM, New York, NY, USA, 43–52. Google ScholarDigital Library
34. K. Ruben Gabriel and Robert R. Sokal. 1969. A New Statistical Approach to Geographic Variation Analysis. Systematic Biology 18, 3 (09 1969), 259–278. Google ScholarCross Ref
35. Jean Gallier and Jocelyn Quaintance. 2017. Aspects of Convex Geometry Polyhedra, Linear Programming, Shellings, Voronoi Diagrams, Delaunay Triangulations. Book in progress, earlier version available as arXiv:0805.0292.Google Scholar
36. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.Google Scholar
37. LLC Gurobi Optimization. 2019. Gurobi Optimizer Reference Manual. http://www.gurobi.comGoogle Scholar
38. David Hartvigsen. 1992. Recognizing Voronoi Diagrams with Linear Programming. ORSA Journal on Computing 4, 4 (1992), 369–374. Google ScholarCross Ref
39. Anil Nirmal Hirani. 2003. Discrete exterior calculus. Ph.D. Dissertation. California Institute of Technology.Google ScholarDigital Library
40. Yixin Hu, Teseo Schneider, Bolun Wang, Denis Zorin, and Daniele Panozzo. 2019. Fast Tetrahedral Meshing in the Wild. arXiv:cs.GR/1908.03581Google Scholar
41. 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
42. 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
43. Clément Jamin, Sylvain Pion, and Monique Teillaud. 2018. 3D Triangulations. In CGAL User and Reference Manual (4.13 ed.). CGAL Editorial Board. https://doc.cgal.org/4.13/Manual/packages.html#PkgTriangulation3SummaryGoogle Scholar
44. François Labelle and Jonathan Richard Shewchuk. 2007. Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles. ACM Trans. Graph. 26, 3, Article 57 (July 2007), 10 pages. Google ScholarDigital Library
45. Lin Lu, Andrei Sharf, Haisen Zhao, Yuan Wei, Qingnan Fan, Xuelin Chen, Yann Savoye, Changhe Tu, Daniel Cohen-Or, and Baoquan Chen. 2014. Build-to-Last: Strength to Weight 3D Printed Objects. ACM Trans. Graph. 33, 4, Article Article 97 (July 2014), 10 pages. Google ScholarDigital Library
46. Gary H. Meisters. 1975. Polygons Have Ears. The American Mathematical Monthly 82, 6 (1975), 648–651. http://www.jstor.org/stable/2319703Google ScholarCross Ref
47. Balint Miklos, Joachim Giesen, and Mark Pauly. 2010. Discrete Scale Axis Representations for 3D Geometry. ACM Trans. Graph. 29, 4, Article Article 101 (July 2010), 10 pages. Google ScholarDigital Library
48. Ernst P. Mücke, Isaac Saias, and Binhai Zhu. 1999. Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations. Computational Geometry 12, 1 (1999), 63 — 83. Google ScholarDigital Library
49. Patrick Mullen, Pooran Memari, Fernando de Goes, and Mathieu Desbrun. 2011. HOT: Hodge-Optimized Triangulations. ACM Trans. Graph. 30, 4, Article Article 103 (July 2011), 12 pages. Google ScholarDigital Library
50. Michael Murphy, David M. Mount, and Carl W. Gable. 2000. A Point-Placement Strategy for Conforming Delaunay Tetrahedralization. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, USA, 67?74.Google Scholar
51. Oleg R. Musin. 1997. Properties of the Delaunay Triangulation. In Proceedings of the Thirteenth Annual Symposium on Computational Geometry. ACM, New York, NY, USA, 424–426. Google ScholarDigital Library
52. Jim Ruppert. 1995. A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation. J. Algorithms 18, 3 (May 1995), 548?585. Google ScholarDigital Library
53. Jim Ruppert and Raimund Seidel. 1992. On the Difficulty of Triangulating Three-Dimensional Nonconvex Polyhedra. Discrete Comput. Geom. 7, 3 (Dec. 1992), 227?253. 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. Jonathan Richard Shewchuk. 1998a. A Condition Guaranteeing the Existence of Higher-Dimensional Constrained Delaunay Triangulations. In Proceedings of the Fourteenth Annual Symposium on Computational Geometry. Association for Computing Machinery, New York, NY, USA, 76?85. Google ScholarDigital Library
56. Jonathan Richard Shewchuk. 1998b. Tetrahedral Mesh Generation by Delaunay Refinement. In Proceedings of the Fourteenth Annual Symposium on Computational Geometry. Association for Computing Machinery, New York, NY, USA, 86?95. Google ScholarDigital Library
57. Jonathan Richard Shewchuk. 2008. General-Dimensional Constrained Delaunay and Constrained Regular Triangulations, I: Combinatorial Properties. Discrete & Computational Geometry 39, 1 (01 Mar 2008), 580–637. Google ScholarCross Ref
58. Jonathan Richard Shewchuk and Hang Si. 2014. Higher-Quality Tetrahedral Mesh Generation for Domains with Small Angles by Constrained Delaunay Refinement. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry. Association for Computing Machinery, New York, NY, USA, 290?299. Google ScholarDigital Library
59. Hang Si. 2010. Constrained Delaunay Tetrahedral Mesh Generation and Refinement. Finite Elem. Anal. Des. 46, 1?2 (Jan. 2010), 33?46. Google ScholarDigital Library
60. Hang Si. 2015. TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator. ACM Trans. Math. Softw. 41, 2, Article Article 11 (Feb. 2015), 36 pages. Google ScholarDigital Library
61. The CGAL Project. 2019. CGAL User and Reference Manual (5.0 ed.). CGAL Editorial Board. https://doc.cgal.org/5.0/Manual/packages.htmlGoogle Scholar
62. Evan VanderZee, Anil N. Hirani, and Damrong Guoy. 2008. Triangulation of Simple 3D Shapes with Well-Centered Tetrahedra. In Proceedings of the 17th International Meshing Roundtable, Rao V. Garimella (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 19–35.Google ScholarCross Ref
63. Evan VanderZee, Anil N. Hirani, Damrong Guoy, and Edgar A. Ramos. 2010. Well-Centered Triangulation. SIAM Journal on Scientific Computing 31, 6 (2010), 4497–4523. Google ScholarDigital Library
64. Etienne Vouga, Mathias Höbinger, Johannes Wallner, and Helmut Pottmann. 2012. Design of Self-Supporting Surfaces. ACM Trans. Graph. 31, 4, Article Article 87 (July 2012), 11 pages. Google ScholarDigital Library
65. Dong-Ming Yan, Wenping Wang, Bruno Lévy, and Yang Liu. 2010. Efficient Computation of 3D Clipped Voronoi Diagram. In Advances in Geometric Modeling and Processing, Bernard Mourrain, Scott Schaefer, and Guoliang Xu (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 269–282.Google Scholar
66. Yajie Yan, David Letscher, and Tao Ju. 2018. Voxel Cores: Efficient, Robust, and Provably Good Approximation of 3D Medial Axes. ACM Trans. Graph. 37, 4, Article 44 (July 2018), 13 pages. Google ScholarDigital Library
67. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797.Google Scholar
