Surface Approximation Based On Delaunay Triangulation

Recently, the method of Delaunay triangulation in CAGD used to approximate the original curve or surface has been a hot subject, which has a vast future in graph design.Delaunay triangulation is very effective in the approximation of curve or surface in CAGD. There are two ways to achieve this purpose. First, given a sampling points set, plot its Voronoi graph. Then, connet the points whose Voronoi cell is adjent, and what we get is the Delaunay triangulation. In practice, we need to constrain the influence field some times, so we give each point which will be constrained a power to achieve the goal. And then, by the way introduced above, a Delaunay triangulation is got, which is called regular triangulation. Second, form a triangulation from the original sampling points, then optimize the obtained triangulation to make it satisfy the Empty Circle Property, which is the Delaunay triangulation and approximates the original curve or surface better.This issue summarizes and studies the basic conceptions and theories ,modeling methods and classic computing methods of Delaunay triangulation. And, in order to optimize the triangulation, the method using bisteller flip which makes the triangulation the Delaunay triangulation is proposed here, which accelerates the computing and enhances the smooth property. And it is also extended into curve approximation. Numerical experiments are also given to show that the algorithm is simple, fast and efficient.Especially for the non-convex hull region, new points and protecting edges are added to the original surface to construct buffer zone. Then triangulate the buffer zone and the inner part of the original surface separately, which will not affects each other. The practice proves that this method creats better approximation to the original surface and lose less geometric characteristics.