密度场控制的四面体网格自适应生成算法

doi:10.16182/j.issn1004731x.joss.201801006

摘要/Abstract

摘要： 通过构造表面模型的密度场,提出一种四面体网格自适应生成算法。在表面模型的轴向包围盒内均匀点采样;以模型表面为边界定义一个非均匀的密度场来构建采样点集的质心Voronoi结构,同时动态地增删采样点以优化点集分布;以模型内部的采样点为基础,以模型表面为边界约束,进行四面体网格划分。实验表明,算法能够处理具有不同拓扑和几何复杂度的表面模型,生成的体网格整体质量较高,网格单元形状规整、尺寸自适应且疏密可调。算法可用于有限元分析、动态仿真等领域。

关键词: 计算几何, 四面体网格化, 密度场, 质心Voronoi结构, 网格优化

Abstract: We present an algorithm for adaptively generating tetrahedral mesh by constructing the density field of a surface model. A uniform sampled point set is first generated inside the axial bounding box of the surface model. A non-uniform density field is defined according to the surface boundary of the model. Under the control of the density field, the centroidal Voronoi tessellation of the point set is constructed by using iterative method, and the distribution of the point set is optimized adaptively via dynamically adding or deleting points. Taking the points inside the surface model as the insertion points, a tetrahedral mesh is generated with the surface mode being the boundary-constraint condition. The experimental results show that our algorithm can handle a variety of surface models with different complexity of topology and geometry, and can adaptively generate tetrahedral mesh with different density distribution by adjusting the density field. Most of the generated tetrahedral cells are more regular and the overall quality of the mesh is higher. Our algorithm can be used for finite element analysis, dynamic simulation, and so on.

Key words: computational geometry, tetrahedral meshing, density field, centroidal Voronoi tessellation, mesh optimization

中图分类号:

TP391

王继东, 范丽鹏, 庞明勇. 密度场控制的四面体网格自适应生成算法[J]. 系统仿真学报, 2018, 30(1): 45-52.

Wang Jidong, Fan Lipeng, Pang Mingyong. Adaptive Generation Algorithm of Tetrahedral Meshes Based on Density Field[J]. Journal of System Simulation, 2018, 30(1): 45-52.

参考文献

[1] 贾世宇, 潘振宽. 先细分后分裂的新式四面体网格交互切割方法[J]. 系统仿真学报, 2011, 23(12): 2704-2708. Jia Shiyu, Pan Zhenkuan. A new interactive tetrahedral mesh cutting method basedon splitting after subdivision [J]. Journal of System Simulation, 2011, 23(12): 2704-2708.
[2] 刘雪梅, 王瑞艺, 郭松. 基于质点—弹簧体模型与改进欧拉算法的力反馈[J]. 系统仿真学报, 2013, 25(9): 2234-2238. Liu Xuemei, Wang Ruiyi, Guo Song. Force feedback based on mass-spring volume model and improved euler algorithm [J]. Journal of System Simulation, 2013, 25(9): 2234-2238.
[3] 王冰玲, 刘军. 爆炸载荷下混凝土坝溃坝过程的连续仿真[J]. 系统仿真学报, 2014, 26(1): 159-162. Wang Bingling, Liu Jun. Numerical simulation of process of concrete dam-break under explosive loading [J]. Journal of System Simulation, 2014, 26(1): 159-162.
[4] 吴占雄, 朱善安, Bin He.基于扩散张量成像利用一阶有限元方法计算脑白质各向异性电导率对脑电位分布的影响[J]. 航天医学与医学工程, 2009 22(6): 434-436. Wu Zhanxiong, Zhu Shan,an, Bin He. Effects of brain white matter anisotropic conductivity on distribution of eeg calculated with finite element method based on diffusion tensorimage of nuclear magnetic resonance [J]. Space Medicine & Medical Engineering, 2009, 22(6): 434-436.
[5] 王震, 赵阳, 杨学林. 基于向量式有限元的实体结构非线性行为分析[J]. 建筑结构学报, 2015, 36(3): 133-140. Wang Zhen, Zhao Yang, Yang Xuelin. Nonlinear behavior analysis of entity structure based on vector form intrinsic finite element [J]. Journal of Building Structures, 2015, 36(3): 133-140.
[6] 黄晓东, 杜群贵, 叶帮彦. 三维实体有限元自适应网格规划生成[J]. 计算机辅助设计与图形学学报, 2005, 17(7): 1446-1451. Huang Xiaodong, Du Qungui, Ye Bangyan. 3D finite element adaptive mesh generation [J]. Journal of Computer-Aided Design & Computer Graphics, 2005, 17(7): 1446-1451.
[7] 关振群, 宋超, 顾元宪, 等. 有限元网格生成方法研究的新进展[J]. 计算机辅助设计与图形学学报, 2003, 15(1): 1-14. Guan Zhenqun, Song Chao , Gu Yuanxian, et al. Recent advances of research on finite element mesh generation method [J]. Journal of Computer-Aided Design & Computer Graphics, 2003, 15(1): 1-14.
[8] 单菊林, 关振群, 宋超. 一个高效可靠的三维AFT四面体网格生成算法[J]. 计算机学报, 2007, 30(11): 1989- 1997. Shan Julin, Guan Zhenqun, Song Cao. A reliable and effective tetrahedral meshing algorithm [J]. Chinese Journal of Computers, 2007, 30(11): 1989-1997.
[9] Watson D.Computing the n-dimensional Delaunay tessellation with applications to Voronoi polytopes[J]. Computer Journal(S0010-4620), 1981, 24(2): 167-172.
[10] Bowyer A.Computing Dirichlet tessellations[J]. Computer Journal(S0010-4620), 1981, 24(2): 162-166.
[11] Cavendish J C, Field D A, Frey W B.An approach to automatic three-dimensional finite element mesh generation[J]. International Journal for Numerical Methods in Engineering(S0029-5981), 1985, 21(2): 329-347.
[12] Weatherill N P, Hassan O.Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints[J]. International Journal for Numerical Methods in Engineering (S0029-5981), 1994, 37(12): 2005-2039.
[13] 杜群贵, 邓达华. 三维实体的四面体有限元网格自动生成[J]. 计算机学报, 1997, 20(12): 1057-1062. Du Qungui, Deng Dahua. Automatic generation of tetrahedron finite element mesh for three dimension solid [J]. Chinese Journal of Computers, 1997, 20(12): 1057-1062.
[14] Du Q, Wang D.Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations.[J]. International Journal for Numerical Methods in Engineering(S0029-5981), 2003, 56(9): 1355-1373.
[15] Dobrzynski C, Frey P.Anisotropic Delaunay mesh adaptation for unsteady simulations[C]// Proceedings of the 17th International Meshing Roundtable. Berlin Heidelberg: Springer, 2007: 177-194.
[16] 骆冠勇, 曹洪, 房营光. 用逐点插入法生成Delaunay四面体自适应网格[J]. 计算力学学报, 2007, 24(6): 917-922. Luo Guanyong, Cao Hong, Fang Yingguang. An adaptive Delaunay tetrahedron mesh generation method through point by point insertion[J]. Chinese Journal of Computational Mechanics, 2007, 24(6): 917-922.
[17] 吴火珍, 焦玉勇, 李海波, 等. 复杂区域三维有限元四面体网格自动生成研究[J]. 岩土力学, 2011, 32(11): 3479-3486. Wu Huozhen, Jiao Yuyong, Li Haibo, et al. Study of 3D finite element tetrahedral mesh automatic generation for complex regions [J]. Rock and Soil Mechanics, 2011, 32(11): 3479-3486.
[18] Si H.TetGen, a Delaunay-based quality tetrahedral mesh generator[J]. ACM Transactions on Mathematical Software(S0098-3500), 2015, 41(2): 1-36.
[19] Schöberl J. Netgen mesh generator [DB/OL]. (2015-10-20) [2015-12-30]. http://sourceforge.net/projects/ netgen-mesher/
[20] Du Q, Faber V, Gunzburger M.Centroidal Voronoi tessellations: Applications and Algorithms[J]. Siam Review(S0036-1445), 1999, 41(4): 637-676.
[21] Loop C T.Smooth subdivision surfaces based on triangles [D]. Salt Lake City: Department of Mathematics, University of Utah, 1987.
[22] Liu A, Joe B.Relationship between tetrahedron shape measures[J]. BIT Numerical Mathematics(S0006-3835), 1994, 34(2): 268-287.