“Navigating intrinsic triangulations” by Sharp, Soliman and Crane
Conference:
Type:
Title:
- Navigating intrinsic triangulations
Session/Category Title: Meshing
Presenter(s)/Author(s):
Abstract:
We present a data structure that makes it easy to run a large class of algorithms from computational geometry and scientific computing on extremely poor-quality surface meshes. Rather than changing the geometry, as in traditional remeshing, we consider intrinsic triangulations which connect vertices by straight paths along the exact geometry of the input mesh. Our key insight is that such a triangulation can be encoded implicitly by storing the direction and distance to neighboring vertices. The resulting signpost data structure then allows geometric and topological queries to be made on-demand by tracing paths across the surface. Existing algorithms can be easily translated into the intrinsic setting, since this data structure supports the same basic operations as an ordinary triangle mesh (vertex insertions, edge splits, etc.). The output of intrinsic algorithms can then be stored on an ordinary mesh for subsequent use; unlike previous data structures, we use a constant amount of memory and do not need to explicitly construct an overlay mesh unless it is specifically requested. Working in the intrinsic setting incurs little computational overhead, yet we can run algorithms on extremely degenerate inputs, including all manifold meshes from the Thingi10k data set. To evaluate our data structure we implement several fundamental geometric algorithms including intrinsic versions of Delaunay refinement and optimal Delaunay triangulation, approximation of Steiner trees, adaptive mesh refinement for PDEs, and computation of Poisson equations, geodesic distance, and flip-free tangent vector fields.
References:
1. Gavin Barill, Neil Dickson, Ryan Schmidt, David I.W. Levin, and Alec Jacobson. 2018. Fast Winding Numbers for Soups and Clouds. ACM Transactions on Graphics (2018). Google ScholarDigital Library
2. Marshall W. Bern, Herbert Edelsbrunner, David Eppstein, Scott A. Mitchell, and Tiow Seng Tan. 1993. Edge Insertion for Optimal Triangulations. Discrete & Computational Geometry 10 (1993). Google ScholarDigital Library
3. A. I. Bobenko and B. A. Springborn. 2005. A discrete Laplace-Beltrami operator for simplicial surfaces. ArXiv Mathematics e-prints (March 2005). arXiv:math/0503219Google Scholar
4. Jean-Daniel Boissonnat, Ramsay Dyer, and Arijit Ghosh. 2013. Constructing Intrinsic Delaunay Triangulations of Submanifolds. Research Report RR-8273. INRIA.Google Scholar
5. Jean-Daniel Boissonnat and Steve Oudot. 2005. Provably good sampling and meshing of surfaces. Graphical Models 67, 5 (2005). Google ScholarDigital Library
6. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, Marco Tarini, and Denis Zorin. 2013. Quad-Mesh Generation and Processing: A Survey. Computer Graphics Forum 32, 6 (2013). Google ScholarDigital Library
7. Long Chen and Michael J. Holst. 2011. Efficient Mesh Optimization Schemes based on Optimal Delaunay Triangulations. Comput. Methods Appl. Mech. Engrg. 200 (2011).Google Scholar
8. Long Chen and Jin-chao Xu. 2004. Optimal delaunay triangulations. Journal of Computational Mathematics (2004).Google Scholar
9. Siu-Wing Cheng, Tamal K. Dey, and Jonathan Shewchuk. 2012. Delaunay Mesh Generation (1st ed.). Chapman & Hall/CRC.Google Scholar
10. L. P. Chew. 1987. Constrained Delaunay Triangulations. In Proceedings of the Third Annual Symposium on Computational Geometry (SCG ’87). ACM. Google ScholarDigital Library
11. L. P. Chew. 1993. Guaranteed-quality Mesh Generation for Curved Surfaces. In Proceedings of the Ninth Annual Symposium on Computational Geometry (SCG ’93). ACM. Google ScholarDigital Library
12. 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. The Eurographics Association.Google Scholar
13. Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2013. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Transactions on Graphics (TOG) 32, 5 (2013). Google ScholarDigital Library
14. Fernando de Goes, Mathieu Desbrun, Mark Meyer, and Tony DeRose. 2016. Subdivision exterior calculus for geometry processing. ACM Trans. Graph. 35, 4 (2016). Google ScholarDigital Library
15. Alan Demlow and Maxim A Olshanskii. 2012. An adaptive surface finite element method based on volume meshes. SIAM J. Numer. Anal. 50, 3 (2012).Google ScholarCross Ref
16. Jeff Erickson and Sariel Har-Peled. 2004. Optimally Cutting a Surface into a Disk. Discrete & Computational Geometry 31, 1 (2004). Google ScholarDigital Library
17. Leman Feng, Pierre Alliez, Laurent Busé, Hervé Delingette, and Mathieu Desbrun. 2018. Curved optimal delaunay triangulation. ACM Trans. Graph. 37, 4 (2018). Google ScholarDigital Library
18. M. Fisher, B. Springborn, P. Schröder, and A. I. Bobenko. 2007. An algorithm for the construction of intrinsic delaunay triangulations with applications to digital geometry processing. Computing 81, 2 (01 Nov 2007). Google ScholarDigital Library
19. Steven Fortune. 1993. A note on Delaunay diagonal flips. Pattern Recognition Letters 14, 9 (1993). Google ScholarDigital Library
20. Free Software Foundation. 2008. GCC libquadmath.Google Scholar
21. Michael T Goodrich and Roberto Tamassia. 1997. Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations. Journal of Algorithms 23, 1 (1997). Google ScholarDigital Library
22. Leonidas Guibas and Jorge Stolfi. 1985. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi. ACM Trans. Graph. 4, 2 (April 1985). Google ScholarDigital Library
23. A. Hatcher. 2002. Algebraic Topology. Cambridge University Press.Google Scholar
24. 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). Google ScholarDigital Library
25. 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). Google ScholarDigital Library
26. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013. Globally optimal direction fields. ACM Transactions on Graphics (TOG) 32, 4 (2013), 59. Google ScholarDigital Library
27. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2015. Stripe patterns on surfaces. ACM Transactions on Graphics (TOG) 34, 4 (2015), 39. Google ScholarDigital Library
28. Jon W. Van Laarhoven and Jeffrey W. Ohlmann. 2011. A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in ℜd. J. Heuristics 17, 4 (2011). Google ScholarDigital Library
29. Yong-Jin Liu, Dian Fan, Chun-Xu Xu, and Ying He. 2017. Constructing Intrinsic Delaunay Triangulations from the Dual of Geodesic Voronoi Diagrams. ACM Trans. Graph. 36, 2, Article 15 (April 2017). Google ScholarDigital Library
30. Yong-Jin Liu, Chun-Xu Xu, Dian Fan, and Ying He. 2015. Efficient Construction and Simplification of Delaunay Meshes. ACM Trans. Graph. 34, 6, Article 174 (Oct. 2015). Google ScholarDigital Library
31. Albert T. Lundell and Stephen Weingram. 1969. Regular and Semisimplicial CW Complexes. 77–115.Google Scholar
32. Richard MacNeal. 1949. The Solution of Partial Differential Equations by Means of Electrical Networks. Ph.D. Dissertation. California Institute of Technology.Google Scholar
33. Khamron Mekchay and Ricardo H Nochetto. 2005. Convergence of adaptive finite element methods for general second order linear elliptic PDEs. SIAM J. Numer. Anal. 43, 5 (2005). Google ScholarDigital Library
34. Pedro Morin, Ricardo H Nochetto, and Kunibert G Siebert. 2002. Convergence of adaptive finite element methods. SIAM review 44, 4 (2002). Google ScholarDigital Library
35. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust field-aligned global parametrization. ACM Transactions on Graphics (TOG) 33, 4 (2014). Google ScholarDigital Library
36. Giuseppe Patané. 2016. STAR: Laplacian Spectral Kernels and Distances for Geometry Processing and Shape Analysis. In Proceedings of the 37th Annual Conference of the European Association for Computer Graphics: State of the Art Reports. Eurographics Association. Google ScholarDigital Library
37. Konrad Polthier and Markus Schmies. 1998. Straightest Geodesics on Polyhedral Surfaces. (1998).Google Scholar
38. Samuel Rippa. 1990. Minimal roughness property of the Delaunay triangulation. Computer Aided Geometric Design 7, 6 (1990). Google ScholarDigital Library
39. Max Schindler and Evan Chen. 2012. Barycentric Coordinates in Olympiad Geometry.Google Scholar
40. Teseo Schneider, Yixin Hu, Jeremie Dumas, Xifeng Gao, Daniele Panozzo, and Denis Zorin. 2018. Decoupling Simulation Accuracy from Mesh Quality. 37, 5 (2018).Google Scholar
41. Silvia Sellán, Herng Yi Cheng, Yuming Ma, Mitchell Dembowski, and Alec Jacobson. 2019. Solid Geometry Processing on Deconstructed Domains. Computer Graphics Forum (2019).Google Scholar
42. Nicholas Sharp, Yousuf Soliman, and Keenan Crane. 2019. The Vector Heat Method. ACM Trans. Graph. 38, 2 (2019). Google ScholarDigital Library
43. Alla Sheffer and John C. Hart. 2002. Seamster: Inconspicuous Low-distortion Texture Seam Layout. In Proceedings of the Conference on Visualization ’02 (VIS ’02). IEEE Computer Society. Google ScholarDigital Library
44. Jonathan Shewchuk. 1999. Lecture Notes on Geometric Robustness. Technical Report. University of California at Berkeley.Google Scholar
45. Jonathan Richard Shewchuk. 1997. Delaunay Refinement Mesh Generation. Ph.D. Dissertation. Carnegie Mellon University. Tech Report CMU-CS-97-137.Google Scholar
46. Philip Shilane, Patrick Min, Michael Kazhdan, and Thomas Funkhouser. 2004. The Princeton Shape Benchmark. In Shape Modeling International.Google Scholar
47. J. Macgregor Smith, D. T. Lee, and Judith S. Liebman. 1981. An O(n log n) heuristic for steiner minimal tree problems on the euclidean metric. Networks 11, 1 (1981).Google Scholar
48. Daniel A Spielman. 2010. Algorithms, Graph Theory, and Linear Equations in Laplacian Matrices. In Proceedings of the International Congress of Mathematicians, Vol. 4.Google Scholar
49. Jane Tournois, Camille Wormser, Pierre Alliez, and Mathieu Desbrun. 2009. Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation. 28, 3 (2009), 75. Google ScholarDigital Library
50. Godfried Toussaint. 1980. The Relative Neighborhood Graph of a Finite Planar Set. Pattern Recognition 12 (1980).Google Scholar
51. Shi-Qing Xin, Shuang-Min Chen, Ying He, Guo-Jin Wang, Xianfeng Gu, and Hong Qin. 2011. Isotropic Mesh Simplification by Evolving the Geodesic Delaunay Triangulation. In ISVD. IEEE Computer Society. Google ScholarDigital Library
52. Shi-Qing Xin, Xiang Ying, and Ying He. 2012. Constant-time All-pairs Geodesic Distance Queryon Triangle Meshes. In Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D ’12). ACM. Google ScholarDigital Library
53. Ran Yi, Yong-Jin Liu, and Ying He. 2018. Delaunay Mesh Simplification with Differential Evolution. In ACM Transactions on Graphics, Vol. 37. Google ScholarDigital Library
54. Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. 2016. Mesh Arrangements for Solid Geometry. ACM Transactions on Graphics (TOG) 35, 4 (2016). Google ScholarDigital Library
55. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).Google Scholar
