论文摘要
近年来随着数据采集设备和技术的发展,科学计算和工程分析的对象越来越复杂,大规模离散数据点的三角网格剖分引起了广泛的研究,如何提高三角网格的生成速度是当前网格剖分技术的研究热点之一。局部变换法和Watson算法是工程实践中常用的三角剖分算法,两者都属于逐点添加、局部优化的增量Delaunay三角剖分方法。快速定位包含新插入点的网格单元、减小局部优化的范围是增量Delaunay三角剖分方法的关键。建立离散数据的矩形空间索引可以提高查找包含新插入点的网格单元的效率,本文在此基础上重点研究了如下几个问题:(1)不同的加点次序对局部变换法和Watson算法的局部优化影响较大,按位置相邻次序加点的方法易产生外接圆较大的扁平三角形,引起较多三角形的局部优化,三角网格的生成速度下降。而按随机次序加点,网格生成过程中网格单元相对匀称,局部优化的三角形较少,缩短了局部优化消耗的时间。以激光点扫描采集的数据为例,统计分析了局部优化三角形的数量及分布特征,当数据点大于20000时,随机次序加点方法能提高三角网格生成速度1倍以上,且数据量越大,效率越高。(2)建立离散数据的矩形空间索引,按索引轮流加点,点序对局部优化的影响降低,相邻次序加点方法局部优化的三角形总量是随机次序加点方法的1.1~1.3倍,其中随机次序加点与没有空间索引的随机次序相比,局部优化的三角形数量仅增加了约1%。(3)点与三角形位置关系判别和三角形外接圆包含点的测试分别是局部变换法和Watson算法正确生成Delaunay三角网格的重要环节。对于大规模离散数据,点的空间分布比较复杂,由于计算机浮点运算精度有限,当数据点的位置坐标较大时,三角形的面积坐标和外接圆圆心、半径会产生较大的计算误差,导致点与三角形位置关系以及三角形外接圆包含点的错误判别,从而生成几何拓扑关系不正确的三角网格。采用相对位置坐标可以提高面积坐标和外接圆圆心、半径的计算精度,以等高线地图采集的393252点的实例数据进行测试,相对位置坐标的计算精度能够保证生成几何拓扑关系正确的Delaunay三角网格。将上述关于增量Delaunay三角剖分局部优化的研究成果应用于逆向工程、地质建模的实例数据处理,能够快速有效地生成Delaunay三角网格。在此基础上利用三角形外接圆半径与最长边之比评估三角网格的质量,在允许移动或添加数据点的情况下优化三角网格中的畸形单元。