【作者】 刘冰；

【导师】 谢伟松；

【作者基本信息】 天津大学 ， 应用数学， 2007， 硕士

【摘要】 近年来,用Delaunay三角剖分的方法来进行曲线、曲面的拟合与逼近已成为计算机辅助几何设计(CAGD)领域研究的热点问题,它在图形设计等方面有着广阔的应用前景。Delaunay三角剖分是CAGD中用于曲线、曲面逼近的一种非常有效的方法,主要有两种方法生成Delaunay三角剖分,一是给定样本点集,做出它的Voronoi图,然后,将其Voronoi单元相邻的样本点连接起来,这样就形成了Delaunay三角剖分;同时,为了实际需要,需要控制样本点对其它样本点的影响范围,因此对其加以限制,然后再根据上述方法,得出的Delaunay三角剖分,称为常规三角剖分。二是首先由已知的样本点集生成三角剖分,然后对该三角剖分进行优化,使得三角剖分中的每个三角形都满足空圆(球)定理,这样得到的新的三角剖分为Delaunay三角剖分,也就能更好地逼近初始曲线、曲面。本文总结和研究了以上两种生成Delaunay三角剖分方法的基本概念和理论、模型的构建方法及经典的计算方法。并且,为了解决三角网格的优化问题,采用对等翻转的方法,优化普通的三角网格,有效的提高了运算速度及曲面的光滑性。另外,本文还将Delaunay三角剖分的方法应用到了曲面的逼近。实例表明,该方法简洁、快速、有效。对于非凸包区域的处理方面,本文采用了对边界点添加保护圆、边界边添加保护边的方法,构成缓冲区域,分别对缓冲区域和原区域内部进行三角剖分,两者就不会相互影响。实践证明该方法能很好的逼近原曲面,更好地保持原曲面在非凸包区域的几何特征。更多还原

【Abstract】 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.更多还原