一个高效可靠的三维AFT四面体网格生成算法

A Reliable and Effective Tetrahedral Meshing Algorithm

针对三维推进波前算法(AFT-Advancing Front Technique)存在的效率与收敛性问题,文中提出了一整套改进方案,给出了基于拓扑连接的网格数据结构和基于Hash表的网格元素的插入、查找、删除算法,提高了整个算法的效率.通过在网格生成过程中动态维护前沿的尺寸信息,提高四面体单元的整体质量.在内核回退求解时通过引入前沿优先因子,改变前沿推进的路径,大大增加了回退求解的成功概率;对于极少数不能回退求解的内核采用基于线性规划的插点方法加以解决,这样就基本保证了整个算法的收敛.在网格生成以后,通过删除不必要的内部节点、合并相关四面体单元以及对所有内部节点进行基于角度的优化,从而进一步有效提高了网格质量.数值算例表明,文中提出的改进算法具有接近线性的时间复杂度,生成网格质量好.该算法已经得到工程应用.

A reliable and effective tetrahedral meshing algorithm is proposed based on advancing front method. The detailed design of the data structure is given which representing a mesh topology connection. The operators such as insert, query and delete like a database are implemented by using hash table which accelerates the whole algorithm. Instead of preparing a background mesh for mesh spacing control, this information is estimated at the beginning of each layer at each node from the area of connecting triangles on the front and a user-specified stretching factor. A Cell Searcher is prepared to correct the mesh spacing information and to perform geometric search efficiently. During rolling back the advancing path is changed by changing preferential factor of front, as a result the times of rolling back is decreased significantly. Node inserting based on linear programming technique guarantees the convergence of the algorithm. At the end of the mesh generation process, unwanted node removing and angle-based smoothing are employed to enhance the resulting mesh quality. The examples demonstrate that high quality tetrahedral meshes can be generated within a reasonable time limit.