基于改进波前法的曲面网格生成算法(2)

　　（b）判断搜索区域内是否存在节点可以生成有效的单元.搜索的节点为组成新单元的候选节点，并且依次校核这些节点的有效性.有效性校核[1]包括：保证由候选节点和组成基边的任一节点形成的新边没有跟前沿相交；保证由候选节点和基边组成形状合适的单元；保证候选节点和新边距离前沿为有效远的距离.其中，第一种称为拓扑校核，后2种统称为几何校核.如果有若干个单元满足校核，将选择质量最好的单元为新单元，然后转到④；否则转到（c）. 

　　（c）根据（b）中的校核方法判断理想节点与基边是否组成合适的新单元.如果通过校核，那么生成新的单元后转到④，否则转到（d）. 

　　（d）由理想点和基边确定若干个候选节点，同样用b的方法校核这些节点组成单元的有效性.如果没有单元通过校核，那么把该基边存放在拒绝前沿链表中；如果有若干个单元都满足校核，那么选择质量最好的单元为新单元，然后转到④. 

　　④更新前沿管理数据.首先删掉不是前沿中的节点和边，然后添加新的节点和边到前沿管理数据结构中.当按层生成单元时，把新节点和边存放在非活动前沿链表中，否则存放在活动前沿链表中；当活动前沿链表为空时，把非活动前沿链表中的值添加到活动前沿链表中.如果活动前沿链表为非空转到①，否则转到⑤. 

　　⑤如果拒绝前沿链表为空，那么网格生成结束；否则，将拒绝前沿中的值添加到活动前沿链表中，再转到①.先重复1次上面过程，然后考虑拒绝前沿链表是否为空，如不为空再到①，直到拒绝前沿链表为空为止.只对新单元进行拓扑校核，保证新边没有跟前沿相交就生成新单元. 

　　3算例和分析 

　　采用面对象的C++语言实现本文算法，编制C++类将kD树和前沿管理的实现进行封装.完成算例所用的PC机配置为双核CPU，主频为2.33 Hz，内存为3.25 GB. 

　　3.1算例1：kD树加速AFM 

　　以边长为2的正方形简单区域的网格生成为例，比较采用和不采用kD树这2种方案网格生成的速度.2种方案对不同数量的单元所消耗CPU时间见图5（a）.图5 （b）所示的网格单元为5 748个.从图5（a）可以明显看出，在不采用kD树时CPU时间消耗随单元数量增加呈平方趋势增长，但在采用kD树时CPU消耗时间随单元数量增加呈近似线性增长.采用kD树在单元数量相对较少的情况下优势不明显，但对大规模网格生成（10万个以上）可以明显提高效率.例如，在生成近60万个单元时，采用kD树只需要20 s左右，而不采用kD树需要多达130 s. 

　　4结论

　　为实现高效、稳定的AFM生成曲面网格，对AFM具体实现进行改进.一方面，在AFM前沿数据管理中引进kD树以加快临近前沿和节点的查找，提高AFM网格生成速度；另一方面，在周期曲面网格生成中提出点修正算子并融入到AFM中，以避免添加虚边界导致网格质量较差和虚边界计算复杂的问题，从而改善网格质量和提高程序稳定性. 

　　为方便控制网格生成方式和提高程序的稳定性，把前沿分为活动前沿、非活动前沿和拒绝前沿等3类，在算法中根据需求实现三者间的数据自动交互.对新单元的校核分为拓扑校核和几何校核，以保证整个区域网格的成功生成.基于这些改进，列出AFM实现的详细步骤.网格生成实例说明：kD树能极大地提高AFM网格生成效率，特别是对大规模网格生成效率更为明显；加入点修正算子的AFM可极大地改善周期曲面局部网格单元质量. 

　　参考文献： 

　　[1]关振群， 单菊林， 顾元宪. 基于黎曼度量的复杂参数曲面有限元网格生成方法[J]. 计算机学报， 2006， 29（10）： 18231833. 

　　[2]熊英， 胡于进， 赵建军. 基于映射法和Delaunay方法的曲面三角网格划分算法[J]. 计算机辅助设计与图形学学报， 2002， 14（1）： 5660. 

　　[3]孟宪海， 蔡强， 李吉刚， 等. 面向四面体网格生成的曲面Delaunay三角化算法[J]. 工程图学学报， 2006， 27（1）： 7681. 

　　[4]黄晓东， 丁问司， 杜群贵. 基于波前法的参数曲面有限元网格生成算法[J]. 计算机辅助设计与图形学学报， 2010， 22（1）： 5259. 

　　[5]杜群贵， 刘胜， 黄晓东. 闭曲面有限元网格生成的边界预调整方法[J]. 华南理工大学学报： 自然科学版， 2007， 35（2）：2732. 

　　[6]LOHNER R. Automatic unstructured grid generators[J]. Finite Elements in Analysis and Design， 1997， 25（12）： 111134. 

　　[7]LEE C K. Automatic adaptive metric advancing front triangulation over curved surfaces[J]. Eng Computations， 2000， 17（1）： 4874. 

　　[8]梁义， 陈建军， 陈立岗， 等. 几何自适应参数曲面网格生成[J]. 计算机辅助设计与图形学学报， 2010， 22（2）： 327335. 

　　[9]WU B， WANG S. Automatic triangulation over threedimensional parametric surface based on advancing front method[J]. Finite Elements Anal & Des， 2005， 41（910）： 892910. 

　　[10]FRYKESTIG J. Advancing front mesh generation techniques with application to the finite element method[R]. Gothenburg： Chalmers University of Technology， 1994. 

　　[11]LIANG X， EBEIDA M S， ZHANG Y. Guaranteedquality allquadrilateral mesh generation with feature preservation[J]. Comput Methods Appl Mech & Eng， 2010（199）： 20722082. 

　　[12]BENTLEY J. Multidimensional binary search trees used for associative searching[J]. Commun ACM， 1975， 18（9）： 509517. 

　　[13]BERG M D， OTFRIED C， van KREVELD M. 计算几何：算法与应用[M]. 3版. 邓俊辉，译. 北京： 清华大学出版社， 2009. 

　　[14]GUAN Zhenqun， SHAN Hulin， ZHENG Yao， et al. An extended advancing front technique for closed surfaces mesh generation[J]. Int J Numer Methods Eng， 2008， 74（4）： 642667. 

　　[15]郭新强. 边界面法四边形网格生成研究与应用[D]. 长沙： 湖南大学， 2011. 

　　[16]CUILLIRE J C. A direct method for the automatic discretization of 3D parametric curves[J]. Comput Aided Des， 1997， 29（9）： 639647.