Algorithm Optimization And Implementation Of Delaunay Triangulation Of Three Dimensional Scattered Points

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.Delaunay triangulation is one of the key parts in the field of computer-aided design,geometric modeling and computer graphics.For triangulation algorithm,the important things are lower time complexity and higher quality mesh.Delaunay triangulation algorithm attract attentions because of its good characters,The study and optimization of the algorithm in this paper make lots of sense both in theory and application.This paper discusses 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 and Direct3D programming.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.After studying and analysising the typical algorithms of Delaunay triangulation in this paper,we present improved methods to the key problems of the incremental algorithm.From the aspect of reducing the time complexity of the algorithm,and regarding the point location search as the key step of the algorithm,a new method to improve the point location search is presented.The algorithm determines the location direction by the angle between the normal of triangular facets and the vector pointing from the point in triangular facet to the inserted point,it does not need complicated data structure,and only three facets' normals and angles are need to be calculated for each tested tetrahedra,which reduces the calculation in searching process,and optimizes the location route and improves the efficiency of algorithm.The time complexity of improved Delaunay triangulation algorithm is about O(N^1.12),which is closes to linear time.The implementation and results displaying of algorithm is an important work,we integrate Direct3D with MFC single document framework,and establish modules including loading scattered data points module and triangulation module base the framework,we choose VC++.NET 2003 as programme platform to develop 3DMAKER software.Finally,we analyse the experiment results of our algorithm,and compare it with the former algorithms,discusse the time complexity of the algorithm,besides,analysis the inadequacy in our algorithm and propose the problems that need further study, preparing for the forword work in future.