覃先云+张见明

摘要： 为提高传统波前法（Advancing Front Method，AFM）的网格生成效率，利用多维搜索二叉树数据结构实现临近前沿和节点的快速查找，使整个网格生成的时间复杂度接近线性.针对周期曲面网格的生成，提出2种点修正算子，避免传统算法添加虚边界导致局部网格单元质量较差和虚边界计算复杂的问题.网格生成实例表明：多维搜索二叉树提高网格生成速度，引进点修正算子的波前法改善周期曲面网格质量.

关键词： 曲面网格生成； 波前法； 多维搜索二叉树； 点修正算子； 周期曲面

中图分类号： O241.82文献标志码： A

Abstract： To get better efficiency of mesh generation using Advancing Front Method（AFM）， the data structure of multidimensional binary search trees is used to implement fast query of the associative fronts and nodes， and the total meshing time complexity is nearly close to linearity. Two kinds of pointmodification operations are proposed to construct mesh on periodic surfaces， with which the problems generated by constructing additional virtual boundaries are avoided， such as poor local mesh quality and complicated calculation on virtual boundaries. The examples of mesh generation indicate that， the multidimensional binary search trees can improve mesh generation efficiency， and the AFM with pointmodification operations can improve the mesh quality of periodic surfaces.

Key words： surface mesh generation； advancing front method； multidimensional binary search tree； pointmodification operation； periodic surface

0引言

曲面网格生成是工程和科学计算及计算机图形学等领域的基础支撑技术.一方面，曲面网格可直接用于板和壳等结构的有限元分析以及作为边界元分析的实体表面网格，其网格质量直接影响数值计算精度；另一方面，曲面网格是有限元分析前处理三维实体网格生成的基础，很大程度地决定三维网格质量.另外，曲面网格在计算机图形学和地理信息系统等领域也有重要应用.[1]由此看来，研究曲面网格生成技术具有重要意义.

生成曲面网格的方法主要有Delaunay三角剖分算法[23]、波前法（Advancing Front Method， AFM）[410]和四叉树算法[11]等3种.AFM生成的网格单元质量最好，而且容易控制网格尺寸实现自适应网格生成，从而成为曲面网格生成技术的研究热点.[1，45]AFM的基本流程为：首先将待剖分曲面的边界离散为首尾相连的若干有向线段，得到初始前沿；然后在前沿集合中选择一个线段作为当前前沿，根据当前前沿插入一个新节点或连接已有节点，形成一个新单元；……