Generating 3D Anisotropic Centroidal Voronoi Tessellations

Authors: Alexandre Marin, Alexandra Bac, Laurent Astart

Abstract:

New numerical methods for PDE resolution (such as Finite Volumes (FV) or Virtual Element Method (VEM)) open new needs in terms of meshing of domains of interest, and in particular polyhedral meshes have many advantages. One way to build such meshes consists in constructing Restricted Voronoi Diagrams (RVDs) whose boundaries respect the domain of interest. By minimizing a function defined for RVDs, the shapes of cells can be controlled, i.e. elongated according to user-defined directions or adjusted to comply with given aspect ratios (anisotropy) and density variations. In this paper, our contribution is threefold: first, we present a gradient formula for the Voronoi tessellation energy under a continuous anisotropy field. Second, we describe a meshing algorithm based on the optimisation of this function that we validate against state-of-the-art approaches. Finally, we propose a hierarchical approach to speed up our meshing algorithm.

Keywords: Anisotropic Voronoi Diagrams, Meshes for Numerical Simulations, Optimisation, Volumic Polyhedral Meshing.

References:

[1] J. Droniou, “Finite Volume Schemes For Diffusion Equations: Introduction to and Review of Modern Methods,” Mathematical Models and Methods in Applied Sciences, vol. 24, no. 8, pp. 1575–1619, 2014. Online. Available: https://hal.archives-ouvertes.fr/hal-00813613
[2] Levy, Bruno and Liu, Yang, “Lp Centroidal Voronoi Tessellation and its Applications,” ACM TRANSACTIONS ON GRAPHICS, vol. 29, no. 4, JUL 2010.
[3] M. Iri, K. Murota, and T. Ohya, A Fast Voronoi-Diagram Algorithm with Applications to Geographic Optimization. , 01 2006, ch. , pp. 273–288.
[4] V. Nivoliers and B. Levy, “Approximating Functions on a Mesh with Restricted Voronoi Diagrams,” COMPUTER GRAPHICS FORUM, vol. 32, no. 5, pp. 83–92, AUG 2013.
[5] F. de Goes, K. Breeden, V. Ostromoukhov, and M. Desbrun, “Blue Noise through Optimal Transport,” ACM TRANSACTIONS ON GRAPHICS, vol. 31, no. 6, NOV 2012.
[6] V. Nivoliers, B. Levy, and C. Geuzaine, “Anisotropic and Feature Sensitive Triangular Remeshing using Normal Lifting,” JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, vol. 289, pp. 225–240, DEC 1 2015.
[7] R. Merland, “G´en´eration de grilles de type volumes finis : adaptation `a un mod`ele structural, p´etrophysique et dynamique,” Ph.D. dissertation, Universit´e de Lorraine, Apr. 2013.
[8] R. Merland, B. L´evy, G. Caumon, and P. Collon-Drouaillet, “Building Centroidal Voronoi Tessellations for Flow Simulation in Reservoirs using Flow Information,” in , vol. 1, 2011, p. 153 – 163.
[9] Z. Zhong, W. Wang, B. L´evy, J. Hua, and X. Guo, “Computing a High-Dimensional Euclidean Embedding from an Arbitrary Smooth Riemannian Metric,” ACM Trans. Graph., vol. 37, no. 4, jul 2018.
[10] M. Budninskiy, B. Liu, F. de Goes, Y. Tong, P. Alliez, and M. Desbrun, “Optimal Voronoi Tessellations with Hessian-Based Anisotropy,” ACM Trans. Graph., vol. 35, no. 6, dec 2016.
[11] Y. Xiao, Z. Chen, J. Cao, Y. J. Zhang, and C. Wang, “Optimal power diagrams via function approximation,” Computer-Aided Design, vol. 102, pp. 52–60, 2018, proceeding of SPM 2018 Symposium.
[12] Q. Du, V. Faber, and M. Gunzburger, “Centroidal Voronoi Tessellations: Applications and Algorithms,” SIAM Review, vol. 41, no. 4, p. 637 – 676, 1999.
[13] Y. Liu, W. Wang, B. L´evy, F. Sun, D.-M. Yan, L. Lu, and C. Yang, “On Centroidal Voronoi Tessellation – Energy Smoothness and Fast Computation,” ACM Transactions on Graphics, vol. 28, no. 4, p. 1 – 17, 2009.
[14] J. Hateley, H. Wei, and L. Chen, “Fast Methods for Computing Centroidal Voronoi Tessellations,” Journal of Scientific Computing, vol. 63, 04 2014.
[15] B. L´evy and N. Bonneel, “Variational Anisotropic Surface Meshing with Voronoi Parallel Linear Enumeration,” in Proceedings of the 21st International Meshing Roundtable. Springer Berlin Heidelberg, 2012, pp. 349–366. Online. Available: https://hal.inria.fr/hal-00804558
[16] J. Nocedal and S. J. Wright, Numerical Optimization. Springer New York, NY, 2006.
[17] H. Edelsbrunner, Geometry and Topology for Mesh Generation, ser. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2001.
[18] D.-M. Yan, W. Wang, B. Levy, and Y. Liu, “Efficient Computation of 3D Clipped Voronoi Diagram,” in ADVANCES IN GEOMETRIC MODELING AND PROCESSING, PROCEEDINGS, ser. Lecture Notes in Computer Science, B. Mourrain, S. Schaefer, and G. Xu, Eds., vol. 6130, 2010, pp. 269–282, 6th International Conference on Geometric Modeling and Processing (GMP 2010), Castro Urdiales, SPAIN, JUN 16-18, 2010.
[19] J. Cortes, S. Martinez, and F. Bullo, “Spatially-distributed Coverage Optimization and Control with Limited-range Interactions,” ESAIM-CONTROL OPTIMISATION AND CALCULUS OF VARIATIONS, vol. 11, no. 4, pp. 691–719, 2005.
[20] D.-M. Yan, B. Levy, Y. Liu, F. Sun, and W. Wang, “Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram,” COMPUTER GRAPHICS FORUM, vol. 28, no. 5, SI, pp. 1445–1454, JUL 2009, 7th Eurographics Symposium on Geometry Processing (SGP), Berlin, GERMANY, JUL 15-17, 2009.
[21] J. Ja´skowiec and N. Sukumar, “High-Order Cubature Rules for Tetrahedra,” International Journal for Numerical Methods in Engineering, vol. 121, no. 11, pp. 2418–2436, 2020.
[22] M. A. Taylor, B. A. Wingate, and L. P. Bos, “Several New Quadrature Formulas for Polynomial Integration in the Triangle,” 2005. Online. Available: https://arxiv.org/abs/math/0501496
[23] C. Geuzaine and J.-F. Remacle, “Gmsh: a Three-Dimensional Finite Element Mesh Generator with Built-In Pre- and Post-Processing Facilities,” International Journal for Numerical Methods in Engineering, pp. 1309–1331, 2009.
[24] R. Merland, G. Caumon, B. Levy, and P. Collon, “Voronoi Grids Conformal to 3D Structural Features,” Computational Geosciences, vol. 18, pp. 1–11, 08 2014.
[25] J. M. Lee, Introduction to Smooth Manifolds, 2nd ed., ser. Graduate Texts in Mathematics. Springer New York, NY, 2012.
[26] M. Reddiger and B. Poirier, “The Differentiation Lemma and the Reynolds Transport Theorem for Submanifolds with Corners,” 2019. Online. Available: https://arxiv.org/abs/1906.03330