SURFACE SIMPLIFICATION USING DELAUNAY TRIANGULATION

Abstract

Polygonal surfaces are a common choice for representing the 3-D geometric models in computer graphics, medical imaging, scientific visualization etc. A huge data set has always been a major problem for both visualization and storage purpose. Keeping the shape intact to reduce the size of the data set is known as simplification. The different approaches for the visualization and simplification of the surfaces are overviewed. The triangulation is a popular technique for approximating the surfaces. This dissertation describes all the implementation details for Delaunay triangulation using the triangulation growth approach in two-dimensions as well as in three-dimensions integrated with simplification. The algorithms use the cell structure for preprocessing and range searching to find the Delaunay points quickly. In 3-D shelling mechanism guarantees the completeness and correctness. The vertex decimation method simplifies the surface. The algorithm has been implemented in Turbo C++ on Pentium processor. The time complexity of the algorithm comes out to be approximately linear. The simplified surface at no extra cost in terms of time complexity is an extra advantage of the algorithm for the Delaunay triangulation in 3-D.