《点云数据三角化.doc》由会员分享，可在线阅读，更多相关《点云数据三角化.doc（20页珍藏版）》请在金锄头文库上搜索。
1、第1章 、1.1 空间曲面上散乱数据三角剖分的概念目前有多种方法可以获得物理模型的形状信息。在制造工业中最常使用的是坐标测量机(Coordinate Measuring Machine,CMM)。坐标测量机能精确测量物体表面上点的位置，但其测量速度较慢，当测量点数较多时，效率很低，一般用在对精度要求较高的场合，如检查零件的形状精度、位置精度等。当需要大量获取零件表面的数据点时，一般使用激光扫描仪(Laser Scanner)。激光扫描仪能在相对较短的时间内得到大量零件表面的数据点。另外一种在医学上常用的测量设备是计算机断层扫描仪(Computerized Tomography,CT)。CT得到
2、的是物体的轮廓线，数据点呈层状分布，每一层代表物体的一个剖面。这些测量设备得到的数据点形式各不相同，虽然在局部上某些数据点具有有组织的状态，如激光扫描仪和CT所得的数据点呈现层状的特点，但在全局上基本均表现出散乱的特点。所谓散乱数据的三角剖分就是给定一组散乱数据点，将各数据点之间以三角形相互连接，形成一张三角网格。其实质是以三角网格反映数据点与其邻近点间的拓扑连接关系。而正确的拓扑连接关系将有效揭示散乱数据集所蕴涵的原始物体表面的形状和拓扑结构。1.2 空间曲面上散乱数据三角剖分的研究意义及应用范围空间曲面上散乱数据的三角剖分是构造散乱数据插值曲面的必不可少的前置处理步骤，也是最重要最关键的一
3、步，基于散乱数据点三角剖分构造散乱数据插值曲面的过程如图1所示:图1.1构造散乱数据插值曲面的步骤空间曲面上散乱数据的三角剖分是在对测量数据点必要的处理之后进行的，它是构造散乱数据插值曲面的前置处理步骤。平面域内的散乱数据的三角剖分研究己经经历了相当长的时间，相关理论与算法己经相当成熟，特别是Delaunay三角剖分及其优化准则等研究成果使得平面内的散乱数据点的三角剖分已经不再困难。但在把平面内的算法推广到空间曲面上时，由于空间曲面散乱数据点之间拓扑关系的复杂性，对其直接剖分的理论和算法尚不完善。在处理空间曲面上数据点时，一般的算法都是基于平面凸域的或者是已知各种约束条件的情况，对于与多值曲面
4、对应的空间曲面上散乱数据点的三角剖分算法研究的较少，且在算法效率和剖分效果上还远远不能让人满意。散乱数据曲面重构的难点在于如何在数据点集中快速自动得到邻近点间正确的拓扑连接关系。目前的测量设备能够在短时间内得到数万乃至几十万数据点，所能体现的曲面形状信息越来越精细和复杂，因此对曲面构造的效率和效果提出了较高的要求。研究散乱数据特别是大规模散乱数据的三角剖分，对于迅速构建数据点之间的拓扑连接关系，进而构造插值曲面具有十分重要的意义。散乱数据的三角剖分不但是构造散乱数据插值曲面的重要基础，对三维数据场的可视化、快速原型制造等新技术的研究也有巨大的推动作用。因此广泛应用于测量造型、计算机视觉、医学、
5、气像、勘探、环保等领域中。本文所要研究三维散乱数据的直接剖分方法旨在探索解决与复杂曲面对应的散乱数据点的三角化方法，快速准确地生成优化的三角网格，为构造散乱数据插值曲面做好准备。因此本文关于空间曲面上散乱数据三角剖分方法的研究对散乱数据插值曲面的构造以及逆向工程曲面重构方法的研究有着重要的现实意义，对三维数据场的可视化、基于CT图像的体数据的三维模型重建等应用研究也有一定的借鉴与参考价值。第2章 22.1 引言空间曲面上散乱数据的三角剖分是科学计算与分析中的一种重要方法，在计算几何散乱数据插值曲面构造和三维数据场可视化中得到了广泛应用。对空间曲面上散乱数据的三角剖分方法的研究不论是在二维平面区
6、域还是在三维空间区域上都己经有了很多成果，尤其是对二维平面散乱数据三角剖分的研究，其理论和算法已经比较成熟，相对来说对空间曲面乱数据的三角剖分，特别是曲面形状比较复杂、散乱数据点的数目很大时，目前的算法在适应性、执行效率等方面还有待进一步提高。2.2 问题描述及分类问题2.1:给定一组散乱数据点Vi(i=1,2,?，n)，如何将各数据点之间以三角形相互连接，形成一张三角网格，并使网格质量较优。该问题的解是散乱点集Vi的一个三角剖分T，其实质是以三角网格M反映各个数据点与其邻近点之间的拓扑连接关系，从而揭示数据点之间的内在本质联系。三角剖分所涉及的问题在实际应用中根据数据点位置的不同有三种情况:
7、二维，三维实体和空间曲面。根据这种情况，空间曲面上散乱数据的三角剖分可分为对空间曲面上散乱数据投影域的剖分和在空间中直接剖分两种类型。空间曲面上散乱数据的投影域包括平面域和球面域。直接三角剖分方法研究如何直接将空间曲面上散乱数据点在空间中连接成一个优化的三角网格。2.3 三角剖分2.3.1 定义定义2.1：给定中k个不相同的点， 点集P=+（R，0，+=1）（3.1）是由，生成的凸集。定义2.2：给定一个点集的任意子集L，L的凸壳是包含L的最小的子集。定义2.3：给定平面内的顶点的集合Vi(i=1,2,n),用不相交的直线段连接vi和vj，1i,jn,i j.使得n个点的凸壳内每一个区域是一个
8、三角形。图2.2平面点集的一种三角剖分一般来说，对顶点集合Vi的三角剖分不是唯一的，有多种剖分结果都能满足上述定义。当然，其中只有部分结果的三角剖分网格的形态较优，能够满足际应用的需求。在许多应用中，最好是三角形尽可能是“等边”的，或边总长度最小，当三角剖分边的总长度减至最小时，则称为最小权三角剖分。2.3.2 三角剖分基本理论2.3.2.1 Voronoi图与Delaunay三角剖分平面三角剖分的实质是以三角形反映数据点与其邻近点之间的拓扑连接关系。若能首先找出平面上一点的所有邻近点，则问题2.1在平面上的情况就好办多了，为此需要解决下面的问题:问题2:给定平面中n个点的集合S=对于平面中比
9、其它点更接近于P的点(x,y)轨迹是什么?图2.3定义2.4:给定平面中n个点的集合s,V(pi)在平面S中比其它点更接近于的Pi点的轨迹是n-1个半平面的交，它是一个不多于n-1条边的凸多边形域，称V(pi)为关联于P的Voronoi多边形或关联于P的Voronoi域。图2.4表示关联于pi的一个Voronoi多边形，它是一个五边形，n=6。图2.4对于S中的每一个点都可以作一个Voronoi多边形，这样的n个Voronoi多边形组成的图成为Voronoi图，记为Vor(S)，如图2.5所示。该图中的顶点分别称为Voronoi顶点和Voronoi边。Vor(S)的边是某点对的垂直平分线上的一
10、条线段或者半直线，从而为该点对所在的两个多边形域所共有。Vor(S)中有的多边形域是无界的。图2.5在叙述Voronoi图的性质时作假设:原来集合S中没有四个点是共圆的。若此假设不成立，则需要在证明中加入一些无关紧要的，但却是冗长的陈述。在叙述Voronoi图的性质时作假设“原来集合S中没有四个点是共圆的。若此假设不成立，则需要在证明中加入一些无关紧要的，但却是冗长的陈述。图2.6图2.6定理2.1:对于S的Voronoi图每一个顶点v，圆C(v)不包含S的其它点。由于定理2.1：Vor(S)又称为最近点意义下的Voronoi图。定理2.2：在S中，Pi的每一个最近点确定Voronoi多边形v
11、(pi)的一条边。图2.7i图2.7的每一个最近邻近点确定v(pi)定义2.5:Voronoi图的直线对偶是由S的每个点对之间加入一个直线段以获得嵌入平面的图，产生的图是原来n个点上的一个图。如图2.5中的虚线所示。对偶的重要性主要归于下面的Delaunay定理。定理2.3:Voronoi图的直线对偶是S的一个三角剖分。图2.5中的虚线即是S的一个三角剖分。Voronoi图的这些性质可以用来快速构造Voronoi图，且可应用它解决最邻近点问题和三角剖分问题。定义2.6:在一个三角剖分中，若每一个三角形的外接圆为空(即在外接圆中不含有其它点)，则该三角剖分称为Delaunay三角剖分。对于给定的
12、一组平面数据点集S，可以多种不同的三角剖分，其中Delaunay三角剖分是最优的，二维Delaunay三角剖分由满足最小内角最大准则的三角形组成。下一节将介绍详细三角剖分准则。2.3.2.2 三角剖分优化准则在三角剖分过程中，往往用一种比较简单的方法构造散乱数据点的初始三角网格，然后对其进行优化，以获得较优化的三角形网格。优化的方法和效果取决于所采用的优化准则。平面三角剖分常采用的优化准则有Thiessen区域准则、最小内角最大准则、圆准则。Sibson证明了这三个准则的等价性，并指出符合这三个准则的三角剖分只有一个，即Delaunay三角化。今Thiessen区域准则(Thiessen re
13、gioncriterion)Thiessen区域指Voronoi分割后形成的多边形区域。如果两个区域具有非零长度的公共线段，则称这两个区域的生成点为Thiessen强邻接点(strongThiessen neighbours);如果它们的公共部分仅是一个点，则称为Thiessen弱邻接点(weak Thiessen neighbours)。一个严格凸的四边形至多有一对相对顶点是Thiessen强邻接点。Thiessen区域准则指对一个严格凸的四边形三角化时，将Thiessen强邻接点相连，若两对顶点都是Thiessen弱邻接点，则任选一对相连，这样构造的三角化是最优的，见图2.8:图2.8 T
14、hiessen区域准则最小内角最大准则在平面内，对一个严格凸的四边形进行三角化时，有两种选择，最小内角最大准则就是要保证对角线两侧两个三角形中的最小内角最大。如图2.9所示:图2.9最小内角最大准则圆准则严格凸的四边形中的三个点确定一个圆，如果第四个顶点落在圆内，则将第四个顶点与其相对的顶点相连，否则将另两个相对顶点相连，如图210所示:图2.10圆准则平面三角剖分优化准则理论为平面内散乱点集的快速三角剖分提供了判断标准，也为三维空间散乱点集的三角剖分优化标准提供了借鉴依据。2.3.3 经典三角化算法三角化算法虽然很多，但大多算法生成的是Delaunay三角网格，即以空外接圆(球)准则为优化准
15、则。根据实现方法的不同，Delaunay三角化方法。主要有三类:换边法(Swapping edges):首先构造非优化的初始三角化，然后对2个共边三角形形成的凸四边形迭代换边优化。以Lawson为代表的对角线交换算法属于换边法，换边法适用于二维Delaunay三角化，对于三维Delaunay三角化，则需要对共面四面体进行换面优化。加点法(Adding points):从一个三角形开始，每次加一个点，保证每一步得到的当前三角化是局部优化的。以英国Bath大学数学分校Bowyer,Green,Sibson为代表的计算Dirichlet图的方法属于加点法，是较早成名的算法之一;以澳大利亚悉尼大学地学系Watson为代表的空外接球法亦属于加点法。加点法算法简明，是目前应用最多的算法。分割占有法(Devide and conquer):将数据域递归细分为子块，每块实现局部优化三角化，然后合并。对应于上述三类算法各有一些著名的算法。2.3.3.1 Bowyer算法该算法基于Dirichlet图的构造，适用于n维空间中的离散点集的网格剖分，是英国Bath大学数学分校的A.Bowyer在总结该校Robin Sibson教授、PeterJ.Green博士七十年代所做工作的基础上，于1981年提出的。算法思路Bowyer算法是针对Voronoi图的实现，首先开始于一个由n+1个数据点形成
