【作者】 岳磊；

【导师】 魏东；

【作者基本信息】 沈阳工业大学 ， 计算机软件与理论， 2009， 硕士

【摘要】 三角剖分是计算机辅助几何设计、几何造型及计算机图形学中的重要研究内容之一,在曲面重构、三维有限元方法的预处理、医学可视化及地理信息系统等领域有着广泛的应用。对于三角剖分算法来说,最重要的就是其复杂度低和高质量网格的形成。Delaunay三角剖分算法由于其良好的优化特性受到青睐,本文对其算法进行研究及改进有着重要的理论意义和重大的应用价值。本文研究的是空间三维散乱点的三角剖分方法,由三维散乱点的导入、三角剖分过程到最后的结果显示输出,涉及到了计算几何、计算机图形学等相关知识。平面的三角剖分方法已经较为成熟,而三维三角剖分方法仍需进一步完善和改进,这正是本文对其进行研究的目的。根据三维散乱点集构造曲面剖分在CAD、反求工程等方面有着十分广泛的应用,本文介绍了几种常用的剖分方法,主要阐述和分析了直接三维三角剖分方法中的一种增量算法——Choi算法以及几种常用的剖分优化准则。在研究和分析了典型的三角剖分算法的思想后,针对Choi算法提出改进意见。针对原算法当中点预处理过程中可见点不一定存在以及原算法当中存在的数据冗余等问题进行改进,采用一种新的点预处理方法来替代原算法的点预处理方法并针对原算法的数据结构进行部分改进。采用一种优化准则对剖分结果进行优化,从而得到最终的剖分结果。最后通过对改进前算法和改进后算法的运行实验结果进行分析,改进后的算法比改进前算法的数据结构更加简练,运行时间更短,达到了算法改进的目的。更多还原

【Abstract】 Delaunay triangulation is one of the key parts in the field of computer-aided design, geometric modeling and computer graphics, triangulation has been widly applied in areas of surface reconstruction, three-dimensional pretreatment of finite element method, medical visualization and geographic information system(GIS), etc. For triangulation algorithrm, the important things are lower time complexity and higher quality mesh. Delaunay triangulation algorithrm attract attentions because of its good characters, The study and optimization of the algorithrm in this paper make lots of sence both in theory and application.This paper studies the Delaunay triangulation method of three-dimensional scattered points, including loading scattered points, triangulation and the results display, which relates to knowledges about computational geometry, computer graphics, etc. Delaunay triangulation algorithm in two dimension has been studied very well, but in three dimension, it still needs to be improved, that is also our study purpose.Surface triangulations based-on 3D arbitrary point-sets are widely applied in CAD and reverseengineering, etc. This paper introduces several proverbial triangulation algorithm, mainly expatiate and analyses one incremental algorithm of direct triangulation algorithm called Choi algorithm and some proverbial optimal criteria. After studying and analysising the typical algorithms of Delaunay triangulation in this paper, we put forward improving ideas about Choi algorithm. About Choi algorithm, there has some problems, such as visible point can not been found in point pretreatment and data redundancy exists in Choi algorithm, etc. We improve Choi algorithm, adopt a new point pretreatment method to replace the former point pretreatment method and improve parts of the data structures of algorithm. After using one optimal criteria to optimize the result of the triangulation, we can gained final result.Finally the experiment proves that the data structures of improved algorithm is more concise and the runtime is more short, gain one’s ends of improving algorithm.更多还原