“Computing a high-dimensional euclidean embedding from an arbitrary smooth riemannian metric” by Zhong, Wang, Levy, Hua and Guo
Conference:
Type:
Entry Number: 62
Title:
- Computing a high-dimensional euclidean embedding from an arbitrary smooth riemannian metric
Session/Category Title: Cleaning Up the Mesh We Made
Presenter(s)/Author(s):
Moderator(s):
Abstract:
This article presents a new method to compute a self-intersection free high-dimensional Euclidean embedding (SIFHDE2) for surfaces and volumes equipped with an arbitrary Riemannian metric. It is already known that given a high-dimensional (high-d) embedding, one can easily compute an anisotropic Voronoi diagram by back-mapping it to 3D space. We show here how to solve the inverse problem, i.e., given an input metric, compute a smooth intersection-free high-d embedding of the input such that the pullback metric of the embedding matches the input metric. Our numerical solution mechanism matches the deformation gradient of the 3D → higher-d mapping with the given Riemannian metric. We demonstrate the applicability of our method, by using it to construct anisotropic Restricted Voronoi Diagram (RVD) and anisotropic meshing, that are otherwise extremely difficult to compute. In SIFHDE2-space constructed by our algorithm, difficult 3D anisotropic computations are replaced with simple Euclidean computations, resulting in an isotropic RVD and its dual mesh on this high-d embedding. Results are compared with the state-of-the-art in anisotropic surface and volume meshings using several examples and evaluation metrics.
References:
1. F. Alauzet and A. Loseille. 2010. High-Order Sonic Boom Modeling Based on Adaptive Methods. J. Comput. Phys. 229, 3 (2010), 561–593. Google ScholarDigital Library
2. F. Alauzet and A. Lozeille. 2016. A Decade of Progress on Anisotropic Mesh Adaptation for Computational Fluid Dynamics. Computer-Aided Design 72 (2016), 13–39. Google ScholarDigital Library
3. P. Alliez, D. Cohen-Steiner, O. Devillers, B. Lévy, and M. Desbrun. 2003. Anisotropic Polygonal Remeshing. ACM Trans. Graph. 22, 3 (2003), 485–493. Google ScholarDigital Library
4. P. Alliez, D. Cohen-Steiner, M. Yvinec, and M. Desbrun. 2005. Variational Tetrahedral Meshing. ACM Trans. Graph. 24, 3 (2005), 617–625. Google ScholarDigital Library
5. J-D. Boissonnat, K. Shi, J. Tournois, and M. Yvinec. 2015a. Anisotropic Delaunay Meshes of Surfaces. ACM Trans. Graph. 34, 2 (2015), 14. Google ScholarDigital Library
6. J-D. Boissonnat, C. Wormser, and M. Yvinec. 2008a. Anisotropic Diagrams: Labelle Shewchuk Approach Revisited. Theoretical Computer Science 408, 2-3 (2008), 163–173. Google ScholarDigital Library
7. J-D. Boissonnat, C. Wormser, and M. Yvinec. 2008b. Locally Uniform Anisotropic Meshing. In Proceedings of the 24th annual symposium on Computational geometry. 270–277. Google ScholarDigital Library
8. J-D. Boissonnat, C. Wormser, and M. Yvinec. 2015b. Anisotropic Delaunay Mesh Generation. SIAM J. Comput. 44, 2 (2015), 467–512.Google ScholarCross Ref
9. H. Borouchaki, P. George, F. Hecht, P. Laug, and E. Saltel. 1997b. Delaunay Mesh Generation Governed by Metric Specifications. Part I. Algorithms. Finite Elements in Analysis and Design 25, 1-2 (1997), 61–83. Google ScholarDigital Library
10. H. Borouchaki, P. George, and B. Mohammadi. 1997a. Delaunay Mesh Generation Governed by Metric Specifications. Part II. Applications. Finite Elements in Analysis and Design 25, 1-2 (1997), 85–109. Google ScholarDigital Library
11. V. Borrelli, S. Jabrane, F. Lazarus, and B. Thibert. 2012. Flat Tori in Three-dimensional Space and Convex Integration. Proceedings of the National Academy of Sciences of the United States of America 109, 19 (2012).Google Scholar
12. F. Bossen and P. Heckbert. 1996. A Pliant Method for Anisotropic Mesh Generation. In 5th International Meshing Roundtable. 63–76.Google Scholar
13. M. Bronstein, A.Bronstein, R. Kimmel, and I. Yavneh. 2000. Multigrid Multidimensional Scaling. Numerical Linear Algebra with Applications 0 (2000), 1–6.Google Scholar
14. M. Bronstein, A. Bronstein, R. Kimmel, and I. Yavneh. 2005. A Multigrid Approach For Multi-Dimensional Scaling. In Proceedings of the Copper Mountain Conference on Multigrid Methods.Google Scholar
15. M. Budninskiy, B. Liu, F. de Goes, Y. Tong, P. Alliez, and M. Desbrun. 2016. Optimal Voronoi Tessellations with Hessian-based Anisotropy. ACM Trans. Graph. 35, 6 (2016), 242:1–242:12. Google ScholarDigital Library
16. G. Canas and S. Gortler. 2006. Surface Remeshing in Arbitrary Codimensions. Visual Computer 22, 9 (2006), 885–895. Google ScholarDigital Library
17. L. Chen, P. Sun, and J. Xu. 2007. Optimal Anisotropic Meshes for Minimizing Interpolation Errors in Lp-Norm. Math. Comp. 76 (2007), 179–204.Google ScholarCross Ref
18. L. Chen and J. Xu. 2004. Optimal Delaunay Triangulations. Journal of Computational Mathematics 22 (2004), 299–308.Google Scholar
19. Z. Chen, W. Wang, B. Lévy, L. Liu, and F. Sun. 2014. Revisiting Optimal Delaunay Triangulation for 3D Graded Mesh Generation. SIAM Journal Scientific Computing (2014).Google Scholar
20. H-L. Cheng, T. Dey, H. Edelsbrunner, and J. Sullivan. 2001. Dynamic Skin Triangulation. ACM-SIAM symposium on Discrete algorithms 25 (2001), 525–568. Google ScholarDigital Library
21. S. Cheng, T. Dey, and E. Ramos. 2006. Anisotropic Surface Meshing. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms. 202–211. Google ScholarDigital Library
22. F. Courty, D. Leservoisier, P-L. George, and A. Dervieux. 2006. Continuous Metric and Mesh Adaptation. Applied Numerical Mathematics 55 (2006), 117–145. Google ScholarDigital Library
23. J. Dardenne, S. Valette, N. Siauve, N. Burais, and R. Prost. 2009. Variational Tetrahedral Mesh Generation from Discrete Volume Data. The Visual Computer 25, 5 (2009), 401–410. Google ScholarDigital Library
24. F. Dassi, A. Mola, and H. Si. 2014. Curvature-Adapted Remeshing of CAD Surfaces. In 23rd International Meshing Roundtable. 253–265.Google Scholar
25. F. Dassi, H. Si, S. Perotto, and T. Streckenbach. 2015. Anisotropic Finite Element Mesh Adaptation via Higher Dimensional Embedding. In 24th International Meshing Roundtable. 265–277.Google Scholar
26. C. Dobrzynski and P. Frey. 2008. Anisotropic Delaunay Mesh Adaptation for Unsteady Simulations. In 17th International Meshing Roundtable. 177–194.Google Scholar
27. Q. Du, V Faber, and M. Gunzburger. 1999. Centroidal Voronoi Tessellations: Applications and Algorithms. SIAM Rev. 41, 4 (1999), 637–676. Google ScholarDigital Library
28. Q. Du and D. Wang. 2005a. Anisotropic Centroidal Voronoi Tessellations and Their Applications. SIAM Journal on Scientific Computing 26, 3 (2005), 737–761. Google ScholarDigital Library
29. Q. Du and D. Wang. 2005b. The Optimal Centroidal Voronoi Tessellations and the Gersho’s Conjecture in the Three-dimensional Space. Computers & Mathematics with Applications 49, 9 (2005), 1355–1373. Google ScholarDigital Library
30. M. Freidlin. 1968. On the Factorization of Non-Negative Definite Matrices. Theory of Probability and Its Applications 13, 2 (1968), 354–356.Google ScholarCross Ref
31. P. Frey and F. Alauzet. 2005. Anisotropic Mesh Adaptation for CFD Computations. Computer Methods in Applied Mechanics and Engineering 194, 48-49 (2005), 5068–5082.Google ScholarCross Ref
32. P. Frey and H. Borouchaki. 1997. Surface Mesh Evaluation. In 6th International Meshing Roundtable. 363–373.Google Scholar
33. X. Fu, Y. Liu, J. Snyder, and B. Guo. 2014. Anisotropic Simplicial Meshing using Local Convex Functions. ACM Trans. Graph. 33, 6 (2014), 182:1–182:11. Google ScholarDigital Library
34. G. Golub and C. Loan. 1996. Matrix Computations (3rd Ed.). Johns Hopkins University Press, Baltimore, Maryland. Google ScholarDigital Library
35. M. Gromov. 2017. Geometric, Algebraic, and Analytic Descendants of Nash Isometric Embedding Theorems. Bull. Amer. Math. Soc. 54, 2 (2017), 173–245.Google ScholarCross Ref
36. M. Gromov and V Rokhlin. 1970. Embeddings and Immersions in Riemannian Geometry. Russian Mathematical Surveys 25, 5 (1970), 1–57.Google ScholarCross Ref
37. Q. Han and J-X. Hong. 2006. Isometric Embedding of Riemannian Manifolds in Euclidean Spaces. Vol. 13. American Mathematical Society.Google Scholar
38. P. Heckbert and M. Garland. 1999. Optimal Triangulation and Quadric-Based Surface Simplification. Computational Geometry 14, 1-3 (1999), 49–65. Google ScholarDigital Library
39. J-X. Hong. 1993. Realization in R3 of Complete Riemannian Manifolds with Negative Curvature. Communications in Analysis and Geometry 1, 4 (1993), 487–514.Google ScholarCross Ref
40. K. Itô. 1950. Stochastic Differential Equations in a Differentiable Manifold. Nagoya Mathematical Journal 1 (1950), 35–47.Google ScholarCross Ref
41. B. Klingner. 2008. Tetrahedral Mesh Improvement. Ph.D. Thesis, Dep. of Elec. Eng. and Comp. Sciences U. of California at Berkeley.Google Scholar
42. B. Klingner and J. Shewchuk. 2007. Agressive Tetrahedral Mesh Improvement. In Proceedings of 16th International Meshing Roundtable. 3–23.Google Scholar
43. D. Kovacs, A. Myles, and D. Zorin. 2010. Anisotropic Quadrangulation. In Proceedings of the 14th ACM Symposium on Solid and Physical Modeling (SPM ’10). 137–146. Google ScholarDigital Library
44. N. Kuiper. 1955. On C1-isometric Embeddings I. In Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen. 545–556.Google Scholar
45. B. Lévy. 2016. Robustness and Efficiency of Geometric Programs: The Predicate Construction Kit (PCK). Computer-Aided Design 72 (2016), 3–12. Google ScholarDigital Library
46. B. Lévy and N. Bonneel. 2012. Variational Anisotropic Surface Meshing with Voronoi Parallel Linear Enumeration. In 21st International Meshing Roundtable. 349–366.Google Scholar
47. D. Liu and J. Nocedal. 1989. On the Limited Memory BFGS Method for Large Scale Optimization. Mathematical Programming 45, 3 (1989), 503–528.Google ScholarCross Ref
48. Y. Liu, W. Wang, B. Lévy, F. Sun, D. Yan, L. Lu, and C. Yang. 2009. On Centroidal Voronoi Tessellation – Energy Smoothness and Fast Computation. ACM Trans. Graph. 28, 4 (2009), 101:1–101:17. Google ScholarDigital Library
49. S. Lloyd. 1982. Least Squares Quantization in PCM. IEEE Transactions on Information Theory 28, 2(1982), 129–137. Google ScholarDigital Library
50. A. Loseille and R. Löhner. 2016. Anisotropic Mesh Generation for High-fidelity Simulations in CFD. INRIA (2016). preprint.Google Scholar
51. E. Marchandise, C. Geuzaine, and J.F. Remacle. 2013. Cardiovascular and Lung Mesh Generation Based on Centerlines. International Journal for Numerical Methods in Biomedical Engineering 29, 6 (2013), 665–682.Google ScholarCross Ref
52. R. Narain, A. Samii, and J. F. O’Brien. 2012. Adaptive Anisotropic Remeshing for Cloth Simulation. ACM Trans. Graph. 31, 6 (2012), 147:1–147:10. Google ScholarDigital Library
53. J. Nash. 1954. C1-isometric embeddings. Annals of Mathematics 60, 3 (1954), 383–396.Google ScholarCross Ref
54. S. Ni, Z. Zhong, Y. Liu, W. Wang, Z. Chen, and X. Guo. 2017. Sliver-suppressing Tetrahedral Mesh Optimization with Gradient-based Shape Matching Energy. Computer Aided Geometric Design 52 (2017), 247–261. Google ScholarDigital Library
55. D. Panozzo, E. Puppo, M. Tarini, and O. Sorkine-Hornung. 2014. Frame Fields: Anisotropic and Non-Orthogonal Cross Fields. ACM Trans. Graph. 33, 4 (2014), 134:1–134:11. Google ScholarDigital Library
56. M. Rouxel-Labbé, M. Wintraecken, and J-D. Boissonnat. 2016. Discretized Riemannian Delaunay Triangulations. Procedia Engineering 163 (2016), 97–109.Google ScholarCross Ref
57. E. Sauvage, J. Remacle, and E. Marchandise. 2014. Metric Field Construction for Anisotropic Mesh Adaptation with Application to Blood Flow Simulations. International Journal for Numerical Methods in Biomedical Engineering 30, 11 (2014), 1326–1346.Google ScholarCross Ref
58. K. Shimada and D. Gossard. 1995. Bubble Mesh: Automated Triangular Meshing of Non-manifold Geometry by Sphere Packing. In Proceedings of the 3rd ACM Symposium on Solid Modeling and Applications. 409–419. Google ScholarDigital Library
59. K. Shimada, A. Yamada, and T. Itoh. 1997. Anisotropic Triangular Meshing of Parametric Surfaces via Close Packing of Ellipsoidal Bubbles. In 6th International Meshing Roundtable. 375–390.Google Scholar
60. R. Simpson. 1994. Anisotropic Mesh Transformations and Optimal Error Control. Applied Numerical Mathematics 14, 1-3 (1994), 183–198. Google ScholarDigital Library
61. O. Sorkine-Hornung and M. Alexa. 2007. As-rigid-as-possible Surface Modeling. In Proceedings of the fifth Eurographics symposium on Geometry processing. 109–116. Google ScholarDigital Library
62. R. Sumner and J. Popović. 2004. Deformation Transfer for Triangle Meshes. ACM Trans. Graph. 23, 3 (2004), 399–405. Google ScholarDigital Library
63. J. Tournois, R. Srinivasan, and P. Alliez. 2009. Perturbing Slivers in 3D Delaunay Meshes. Proceedings of the 18th international meshing roundtable (2009), 157–173.Google ScholarCross Ref
64. S. Valette, J. Chassery, and R. Prost. 2008. Generic Remeshing of 3D Triangular Meshes with Metric-Dependent Discrete Voronoi Diagrams. IEEE Trans. Vis. Comput. Graph. 14, 2 (2008), 369–381. Google ScholarDigital Library
65. N. Verma. 2012. Distance Preserving Embeddings for General n-Dimensional Manifolds. Journal of Machine Learning Research volume 14 (2012), 2415–2448. Google ScholarDigital Library
66. S. Yamakawa and K. Shimada. 2000. High Quality Anisotropic Tetrahedral Mesh Generation via Packing Ellipsoidal Bubbles. In 9th International Meshing Roundtable. 263–273.Google Scholar
67. D. Yan, B. Lévy, Y Liu, F. Sun, and W. Wang. 2009. Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram. Computer Graphics Forum 28, 5 (2009), 1445–1454. Google ScholarDigital Library
68. D. Yan, W. Wang, B. Lévy, and Y. Liu. 2013. Efficient Computation of Clipped Voronoi Diagram for Mesh Generation. Computer-Aided Design 45, 4 (2013), 843–852. Google ScholarDigital Library
69. Z. Zhong, X. Guo, W Wang, B. Lévy, F. Sun, Y. Liu, and W. Mao. 2013. Particle-Based Anisotropic Surface Meshing. ACM Trans. Graph. 32, 4 (2013), 99:1–99:14. Google ScholarDigital Library
70. Z. Zhong, L. Shuai, M. Jin, and X. Guo. 2014. Anisotropic Surface Meshing with Conformal Embedding. Graphical Models 76, 5 (2014), 468–483. Google ScholarDigital Library
