论文部分内容阅读
三角剖分在曲面重构、三维有限元方法的预处理、医学可视化及地理信息系统（GIS）等领域有广泛的应用。Delaunay三角剖分是计算机辅助几何设计、几何造型及计算机图形学中的重要研究内容之一。对于设计一个三角剖分算法来说,最重要的就是其复杂度低和高质量网格的形成。Delaunay三角剖分算法由于其良好的优化特性受到青睐,本文对其算法进行研究及优化改进有着重要的理论意义和重大的应用价值。本文讨论的空间三维散乱点Delaunay三角剖分的方法,由散乱点的导入、三角剖分到最后的结果显示输出,涉及到了计算几何、计算机图形学及Direct3D编程等相关知识。平面的Delaunay三角剖分已经较为成熟,而三维Delaunay三角剖分仍需进一步完善和改进,这正是本文对其进行研究的目的。本文在详细研究和分析了典型的Delaunay三角剖分算法的思想后,针对增量算法中的关键问题提出改进的方法,从降低算法的时间复杂度的角度出发,以点定位搜索这一关键问题为切入点,提出新的改进搜索的方法,该算法利用四面体三角面的法矢与该面的点到插入点之间形成的向量的夹角来确定定位方向,不需额外的搜索数据结构,且对于每个搜索四面体只需三个面的法矢和夹角的计算,减少了搜索过程中的计算量,且定位的路径较优,有效提高了算法的效率,使整个Delaunay三角剖分算法的时间复杂度约为0(N1.12),接近线性时间。算法的实现和结果的输出显示是一个重要的环节,本文集成了Direct3D与MFC单文档框架,并基于该框架建立三维散乱数据点导入模块和三角剖分模块,在基于VC++.NET 2003开发平台开发了3DMAKER软件。最后对算法运行实验结果进行了分析,同时将其与现有的相关算法进行了比较并讨论了算法的时间复杂度,此外分析了算法中的不足之处并提出有待进一步研究的问题,为后续的展望工作打下基础。