“Computing a high-dimensional euclidean embedding from an arbitrary smooth riemannian metric” by Zhong, Wang, Levy, Hua and Guo

  • ©Zichun Zhong, Wenping Wang, Bruno Levy, Jing Hua, and Xiaohu Guo



Entry Number: 62


    Computing a high-dimensional euclidean embedding from an arbitrary smooth riemannian metric

Session/Category Title:   Cleaning Up the Mesh We Made




    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.


    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

ACM Digital Library Publication:

Overview Page: