The Analysis,Research And Modification Of Three-Dimensional Terrain Algorithm

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.