Delaunay Triangulations Efficiency for Conduction-Convection Problems

Authors: Bashar Albaalbaki, Roger E. Khayat

Abstract:

This work is a comparative study on the effect of Delaunay triangulation algorithms on discretization error for conduction-convection conservation problems. A structured triangulation and many unstructured Delaunay triangulations using three popular algorithms for node placement strategies are used. The numerical method employed is the vertex-centered finite volume method. It is found that when the computational domain can be meshed using a structured triangulation, the discretization error is lower for structured triangulations compared to unstructured ones for only low Peclet number values, i.e. when conduction is dominant. However, as the Peclet number is increased and convection becomes more significant, the unstructured triangulations reduce the discretization error. Also, no statistical correlation between triangulation angle extremums and the discretization error is found using 200 samples of randomly generated Delaunay and non-Delaunay triangulations. Thus, the angle extremums cannot be an indicator of the discretization error on their own and need to be combined with other triangulation quality measures, which is the subject of further studies.

Keywords: Conduction-convection problems, Delaunay triangulation, discretization error, finite volume method.

References:

[1] Delaunay, B., 1934. Sur la sphere vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 7(793-800), pp.1-2.
[2] Weatherill, N.P. and Hassan, O., 1994. Efficient three‐dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints. International journal for numerical methods in engineering, 37(12), pp.2005-2039.
[3] Shewchuk, J.R., 2002. Delaunay refinement algorithms for triangular mesh generation. Computational geometry, 22(1-3), pp.21-74.
[4] Lo, S., 1985. A new mesh generation scheme for arbitrary planar domains. International journal for numerical methods in engineering, 21(8), pp.1403-1426.
[5] Lo, D.S. H., 2014. Finite element mesh generation. CRC Press.
[6] Bern, M., Eppstein, D. and Gilbert, J., 1994. Provably good mesh generation. Journal of computer and system sciences, 48(3), pp.384-409.
[7] Bern, M., Mitchell, S. and Ruppert, J., 1994, June. Linear-size nonobtuse triangulation of polygons. In Proceedings of the tenth annual symposium on Computational geometry (pp. 221-230).
[8] Üngör, A., 2009. Off-centers: A new type of Steiner points for computing size-optimal quality-guaranteed Delaunay triangulations. Computational Geometry, 42(2), pp.109-118.
[9] Dorado, R., Pivec, B. and Torres-Jimenez, E., 2013. Advancing front circle packing to approximate conformal strips. Computational Geometry, 46(1), pp.105-118.
[10] Bern, M. and Plassmann, P., 2000. Mesh generation. In Handbook of computational geometry, pp. 291–332.
[11] Cheng, S.W., Dey, T.K., Shewchuk, J. and Sahni, S., 2013. Delaunay mesh generation (p. 65). Boca Raton: CRC Press.
[12] Bentley, J.L. and Ottmann, T.A., 1979. Algorithms for reporting and counting geometric intersections. IEEE Transactions on computers, 28(09), pp.643-647.
[13] Yerry, M. and Shephard, M., 1983. A modified quadtree approach to finite element mesh generation. IEEE Computer Graphics and Applications, 3(1), pp.39-46.
[14] Du, Q., Faber, V. and Gunzburger, M., 1999. Centroidal Voronoi tessellations: Applications and algorithms. SIAM review, 41(4), pp.637-676.
[15] Du, Q. and Gunzburger, M., 2002. Grid generation and optimization based on centroidal Voronoi tessellations. Applied mathematics and computation, 133(2-3), pp.591-607.
[16] Nguyen, H., Burkardt, J., Gunzburger, M., Ju, L. and Saka, Y., 2009. Constrained CVT meshes and a comparison of triangular mesh generators. Computational geometry, 42(1), pp.1-19.
[17] Persson, P.O. and Strang, G., 2004. A simple mesh generator in MATLAB. SIAM review, 46(2), pp.329-345.
[18] Patankar, S.V., 2018. Numerical heat transfer and fluid flow. CRC press.
[19] Versteeg, H.K. and Malalasekera, W., 2007. An introduction to computational fluid dynamics: the finite volume method. Pearson education.
[20] Brooks, A.N. and Hughes, T.J., 1982. Streamline upwind/Petrov-Galerkin formulations for convection dominated flows with particular emphasis on the incompressible Navier-Stokes equations. Computer methods in applied mechanics and engineering, 32(1-3), pp.199-259.
[21] Mizukami, A. and Hughes, T.J., 1985. A Petrov-Galerkin finite element method for convection-dominated flows: an accurate upwinding technique for satisfying the maximum principle. Computer methods in applied mechanics and engineering, 50(2), pp.181-193.
[22] Martinez, M.J., 2006. Comparison of Galerkin and control volume finite element for advection–diffusion problems. International journal for numerical methods in fluids, 50(3), pp.347-376.
[23] Patankar, S.V. and Spalding, D.B., 1983. A calculation procedure for heat, mass and momentum transfer in three-dimensional parabolic flows. In Numerical prediction of flow, heat transfer, turbulence and combustion (pp. 54-73). Pergamon.
[24] Barth, T., 1994. Aspects of unstructured grids and finite volume solvers for the Euler and Navier-Stokes equations. 25th Computational Fluid Dynamics Lecture Series. Von Karman Institute.
[25] Winslow, A.M., 1966. Numerical solution of the quasilinear Poisson equation in a nonuniform triangle mesh. Journal of computational physics, 1(2), pp.149-172.
[26] Baliga, B.R. and Patankar, S.V., 1980. A new finite-element formulation for convection-diffusion problems. Numerical Heat Transfer, 3(4), pp.393-409.
[27] Baliga, B.R. and Patankar, S.V., 1983. A control volume finite-element method for two-dimensional fluid flow and heat transfer. Numerical Heat Transfer, 6(3), pp.245-261.
[28] Baliga, B.R., Pham, T.T. and Patankar, S.V., 1983. Solution of some two-dimensional incompressible fluid flow and heat transfer problems, using a control volume finite-element method. Numerical Heat Transfer, 6(3), pp.263-282.
[29] Prakash, C., 1986. An Improved Control Volume Finite-Element Method Ifor Heat and Mass Transfer, and for Fluid Flow Using Equal-Order Velocity-Pressure Interpolation. Numerical Heat Transfer, Part A: Applications, 9(3), pp.253-276.
[30] Hookey, N.A., Baliga, B.R. and Prakash, C., 1988. Evaluation and enhancements of some control volume finite-element methods—Part 1. Convection-diffusion problems. Numerical Heat Transfer, Part A: Applications, 14(3), pp.255-272.
[31] Babuška, I. and Aziz, A.K., 1976. On the angle condition in the finite element method. SIAM Journal on numerical analysis, 13(2), pp.214-226.
[32] Song, T., Wang, J., Xu, D., Wei, W., Han, R., Meng, F., Li, Y. and Xie, P., 2021. Unsupervised Machine Learning for Improved Delaunay Triangulation. Journal of Marine Science and Engineering, 9(12), p.1398.
[33] Fan, H. and Ollivier Gooch, C.F., 2017. The Impact of Unstructured Mesh Generation Approach on Errors. In 23rd AIAA Computational Fluid Dynamics Conference (p. 3105).
[34] Ruppert, J., 1995. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. Journal of algorithms, 18(3), pp.548-585.
[35] Marcum, D.L. and Weatherill, N.P., 1995. Unstructured grid generation using iterative point insertion and local reconnection. AIAA journal, 33(9), pp.1619-1625.
[36] Engwirda, D., 2014. Locally optimal Delaunay-refinement and optimisation-based mesh generation. PhD Thesis, University of Sydney.
[37] Gao, X., Huang, J., Xu, K., Pan, Z., Deng, Z. and Chen, G., 2017, August. Evaluating Hex‐mesh Quality Metrics via Correlation Analysis. In Computer Graphics Forum 36(5), pp. 105-116.
[38] Devadoss, S.L. and O'Rourke, J., 2011. Discrete and computational geometry. Princeton University Press.
[39] Su, P. and Drysdale, R.L.S., 1995, September. A comparison of sequential Delaunay triangulation algorithms. In Proceedings of the eleventh annual symposium on Computational geometry (pp. 61-70).
[40] Freitag, L.A. and Ollivier-Gooch, C., 2000. A cost/benefit analysis of simplicial mesh improvement techniques as measured by solution efficiency. International Journal of Computational Geometry & Applications, 10(4), pp.361-382.
[41] Chew, L.P., 1989. Guaranteed-quality triangular meshes. Cornell Univ Ithaca NY Dept of Computer Science.
[42] Chew, L.P., 1993, July. Guaranteed-quality mesh generation for curved surfaces. In Proceedings of the ninth annual symposium on Computational geometry (pp. 274-280).
[43] Mavriplis, D.J., 1990. Adaptive mesh generation for viscous flows using triangulation. Journal of computational Physics, 90(2), pp.271-291.
[44] Pirzadeh, S., 1996. Three-dimensional unstructured viscous grids by the advancing-layers method. AIAA journal, 34(1), pp.43-49.
[45] Wang, Z., Quintanal, J. and Corral, R., 2019. Accelerating advancing layer viscous mesh generation for 3D complex configurations. Computer-Aided Design, 112, pp.35-46.
[46] Bird, R.B., Stewart, W.E. and Lightfoot, E.N. (2006), Transport phenomena, 1. John Wiley & Sons.
[47] Runchal, A.K., 1972. Convergence and accuracy of three finite difference schemes for a two‐dimensional conduction and convection problem. International Journal for Numerical Methods in Engineering, 4(4), pp.541-550.
[48] Weber, H.J. and Arfken, G.B., 2022. Mathematical methods for physicists, A Comprehensive Review. Elsevier.
[49] Gareth, J., Daniela, W., Trevor, H. and Robert, T., 2019. An introduction to statistical learning: with applications in R. Spinger.