Research On The Optimization Of The Data Structure For The Triangular Mesh Representation Of Surfaces

The computational geometry is an important borderline discipline related to computational mathematics, differential geometry, algebraic geometry, approximation theory. The theoretical results have important applications in a variety of scientific and engineering fields such as CAD\CAM\CAE, image processing, computer graphics, and scientific visualization.This paper first presents the definition of the computational geometry and some classic subjects such as Voronoi diagram and Delaunay triangulation. Following the parts of Delaunay triangulation optimal criterions and algorithms, it shows and compares the triangle mesh surface reconstruction methods, including zero-set method, α -shape method and Crust algorithm.The geometric information and the adjacency information are important basis for mesh post processing, related with data structure closely, so the paper gives the summary of Winged-Edge, Half—Edge, Quad-Edge and Corner Table data structures.At last, an adjacency list storage data structure for 3-D mesh is represented in this paper with advantage of quick construction. The connectivity of mesh can be easily found, moreover the structure has a efficient space storage. Finally, the analysis of time complexity is presented and a contrast.