三维散乱点云三角网格化技术的研究与应用

西安交通大学研究论文摘录

1.选题背景

随着计算机图形学的发展，许多领域都出现了对“实体数字化”技术的强烈需求，越来越多的企业、研究机构甚至个人迫切地需要得到实体的高精度数字化模型，而利用传统的几何造型技术进行设计不仅费时且不能得到物体真实的几何信息。正是在这样的应用背景下，三维光学测量技术实现了飞速的发展。三维扫描能获得物体表面点的三维坐标信息，它属于一种立体测量技术。与传统测量技术相比，它能够完成对复杂物体的测量，特点是非接触、精度高、速度快，能大幅节约时间和成本，并且其测量数据通用性比较强。这些优势使三维扫描技术得到了广泛的应用，并且在某些特殊场合，三维扫描技术还具有独特的、不可替代的作用。比如测量比较柔软的物体，用传统的接触测量方法，很可能在测量时使物体变形，从而使测量结果不准确，而三维扫描技术以光为测量媒质，不会引起物体表面的形变和损伤。

三维扫描技术在众多领域内的广泛应用。其中最为重要的并且最为代表性的应用领域为逆向工程和逆向检测。三维光学扫描仪采用非接触的测量方法，直接得到真实物体表面的采样点，即点云数据，利用点云数据即可以重构出任意曲面。如何快速的讲点云数据转变化为实体模型是逆向工程中需要解决的重要问题。

本课题得到国家863项目“大型复杂曲面产品的反求和三维快速检测系统研究”和江苏省科技支撑计划（工业部分）的支持。研究成果将应用于天津汽车模具有限公司泡沫实型的检测、模具的表面检测和制件的检测。

2、理论意义和应用价值

三角网格自动剖分技术的研究起源于20世纪70年代，主要为了满足航空、数学、地质等领域解决实际问题的需要[8]。20世纪80年代三角网格剖分在众多领域引起了广泛的关注，世界各国的学者和研究机构从不同的需求出发，对三角网格剖分进行深入的研究。目前，点集的网格剖分的主要研究集中在曲面网格剖分，边界的一致性问题是点集三角网格剖分亟待解决的问题。

点云网格重建的目的在于寻找某种数学描述形式，构造一个带有顶点和相互连接拓扑关系的三角形网格模型，如图1示，并以此为依据对网格本身进行分析、优化改和绘制。复杂物体扫描获取的点云数目己经超过几百万个，甚至上亿，给曲面重建技术带来新战和困难:

l)由于这些技术产生大量的体数据，需要有效地被存储和处理;

2)不精确的照相机定位，图像扭曲和配准误差使得点云产生大量噪音和离群点加大了曲面重建的难度，同时导致细节特征丢失。

3)扫描光照的不完善、材料表面的低反射率和遮挡导致物体表面的数据丢失，从而在点云中产生空洞，导致原始表面特征恢复难度加大。

针对这些问题，许多研究者提出了多种解决方案，但是对超大规模而且带有大量噪音的点云，推测物体表面几何结构形式，并非易事。

图1-1 散乱点云的拓扑重建

从近几年来的点云网格重建方法中可以看出，快速鲁棒地对点云进行曲面重建仍然是广大研究者不断努力的目标，除了基于点的造型、CAD中的NURBS曲面外，散乱点云曲面重建几乎都集中网格重建。散乱数据的曲面重建一直以来只是函数逼近论的一个重要研究内容，但是随着激光测距扫描等三维数据采样技术和硬件设备的日益完善。以往难以满足取样密度的散乱数据点集的障碍现在不再是曲面重建的瓶颈。散乱数据的曲面重建作为一种能代表将来发展趋势的新造型技术得到了广泛的研究，特别自从九十年代以来，Hoppe等人对基于散乱数据点集的任意拓扑重建算法进行了开创性的研究，散乱数据点的曲面重建越来越成为图形学界的研究热点之一。该技术具有广泛的应用前景，它的发展将会在科学研究和工程上很多的应用领域，其中包括三维扫描、边缘数据的曲面重建、艺术品及考古文物复制、游戏影视制作等发挥极大的作用。对散乱数据点集的曲面重建研究将会有力地促进造型和可视化等技术的高速发展。因此对散乱数据的曲面重建研究具有重要的理论和现实意义。

3、国内外研究现状及发展趋势

在上个世纪八十年代中期，散乱点云网格重建问题首次由Bofssonnat提出，Bofssormat对网格重建问题作出了开创性的工作，其它许多方法都是在这基础上的改进和提高。随后大约十年，Hoppe提出构造点到物体表面的(有向)离场，该距离场的零等值面即为重建曲面网格。Hoope的文章引起了研究者的大兴趣，散乱点云网格重建成为图形学中一个活跃的研究方向,主要包括有以下

几个研究方向：

（1）基于隐式曲面拟合的方法

隐式曲面拟合方法是使用隐函数曲面拟合数据点，然后在零等值面上提取三角形网格的一类方法。这些隐函数通常为径向基函数或多项式函数，而提取三角形网格的方法，主要以Matching Cube[1]和 Bloomenthal[2]多边形化这两种方法为代表。曲面拟合方法可用一个函数解析表达式完全表达被测表面的曲面方程，广泛应用于计算机视觉、模式识别等邻域，但整体逼近的方式致使逼近精度往往不高(否则导致解大规模的线性方程，如径向基函数拟合法，因此常常需要进行局部细微特征的拟合。

现阶段国际上绘制参数曲面和隐式曲面的方法主要分为四种：多边形化法、扫描线法、光线追踪法和点式绘制算法。

规则的隐式曲面一般用多边形化法来绘制，可以满足任意精度的要求。但是存在的问题是曲面上一些曲率较大的部分要用许多多边形才能精确表达出来，绘制效率很低；还有对于一些隐式曲面，比如自相交（Self-intersecting）隐式曲面是很难用多边形化法绘制出来。扫描线法可以绘制参数曲面和任意的隐式曲面，但因为包含有很复杂的求交算法部分，所以实现过程比较复杂，所需时间长.

（2）基于区域增长的方法

（3）区域增长的方法基本原理是:从一种子三角形开始，基于某种准则，不断选择新点并加入当前的区域边界，生成新三角形，更新边界，直到遍历所有点，将所得数据集的初始剖分优化后，获取逼近被测面的三角网格。算法的关键是按照怎样的规则在点云中选择新的点。

Boissolmat[3]在文献中率先介绍了这种算法，并以三角形张角最大为选点准则。choi的三角形递增基于以下假设:存在某个三维点c，由该点可看到被测面上所有散乱点，并可定义以C为锥顶的凸锥，使之包含所有散乱点。初始三角剖分后，以最小内角最大和光顺性准则优化网格。算法具有可直接处理凸封闭曲面和开曲面的优点，尽管如此，因受凸锥顶角的角度限制，所建曲面可能存在不稳定区域。

Gopi[4]等人基于低维Delaunay三角剖分技术，快速实现每个数据点的拓扑重建，自动矫正局部数据点的非法连接关系，算法效率高，能处理大规模数据点云。Crossno[45]基于螺旋边准则，即从初始三角网格的边界开始，对边界的每个点按最小内接圆准则得到新的三角形，更新边界，直至覆盖整个数据点云，该方法在数据分布均匀时效率很高。

Bemardini[5]的滚球法，又称BPA算法(Ball一Pivoting Algothm)是基于-shape理论，利用半径为r的球在数据点云中的滚动建立网格。滚球若该球接触到3个点，且不含其它点，则该点形成一个三角形。该法继承了-shape的各种优良性能，并具有概念简单、直观、参数设置少、执行时间为线性，要求低、鲁棒性好、能处理简单的out一of-core模型等优点，可惜难以确定滚边半径而致使算法效率低。

（3）基于德劳内（Delaunay）准则的方法

由于Deluanya三角剖分提出至今己有近70年的历史，其间出现了多种多样的计算方法。其中较有影响的算法有:

1.Bowye算法[6]：该算法由英国Bath大学数学分校的Bowye于1981年提出。Bowyer算法首先构造所给点集的Voornoi图，然后根据Voornoi邻域准则连接相邻点即得所给点集的Delnanay三角剖分。所给点集Voornoi图的构造是从一个由n+1个剖分点构成的Deluanya单纯体的Voornoi图开始的。然后逐步加入剖分点，每加入一个就对已有的Voornoi图进行修改，构造新点集的Voornoi图。该算法在n维空间中的效率为 ，是一个效率较低的算法。

2.wesotn算法[7]。该算法是澳大利亚悉尼大学地科系Wasotn于1981年提出的，它是应用计算机构造晶体模型的研究成果。Wasotn算法采用空外接圆准则，直接从三角剖分入手。其主要思想是:从一个单纯形出发，每次加入一个样点后，找出所有外接球包含此点的单纯体，并予以删除基于Curst图的散乱数据点集的曲面网格重建的算法研究得到一个包含此点的空洞。将新点与空洞各顶点相连就构成了加入新点后的Deluanay三角剖分。当所有剖分点全部加完时，所给点集的Deluanay三角剖分即告完成。W叔sotn算法的特点是:思路明确，易于编程实现。其主要不足是计算复杂度较大。Wasotn本人虽然没有分析其算法的时效，但Joe的研究指出，其复杂度将高于Bowyer算法。

3.Lwason算法[8]。1977年，美国加利福尼亚工学院Lawson提出了基于边交换的二维Deluanya三角剖分算法。Lawosn算法是以二维空间中四点的三种构型及构型间的两种变换为基础的。如图2所示，这三种构型分别是:)a构成一个三角形，第四点在一条边上。b)构成一个凸四边形，又可分为两种三角剖分。C)构成一个三角形，第四点在其内部。两种变换，指的就是b)中两种构型之间的相互转换。Lawosn算法从一个非优化的三角剖分出发，对其中每一条边的两个相邻三角形进行空外接圆检查，若不满足，则交换这条对角线。由于交换后一定满足空外接圆准则，所以Lawson算法最终可以构造Delaunay三角剖分。

图1-2 Lwason算法示意图

4.Joe算法[8]。加拿大阿尔伯特大学Joe于1991年给出了基于面交换的二维Deluanya三角剖分算法。Joe的算法不仅是对Lawosn算法的推广，它同时将加点法结合进来，构造了具有。(Nlgo，N)复杂度的换边换面算法。Joe的算法是以三维空间中五点的五种构型及构型间的四种变换为基础的。如图3所示，这五种构型分别是:a)构成一个凸六面体，又可分为两种三角剖分。b)构成一个四面体，第五点在其内部。c)构成一个四面体，第五点在其一条边上。d)构成一个四面体，第五点在其一个面上。e)构成一个五面体，其中有四个点共面，又可分为两种三角剖分。四种变换，指的就是a)中两种构型之间的相互转换以及e)中两种构型之间的相互转换。

图1-3 Joe 算法示意图

5.闵卫东算法[10]。清华大学计算机科学与技术系CAD中心闵卫东和唐泽圣对二维域内点集的Dduanay三角剖分问题进行了比较深入和系统基于Curst图的散乱数据点集的曲面网格重建的算法研究的研究，提出了DTAD的生成算法。该算法首先生成给定域的三角剖分，然后采用生成核插入算法逐个插入域内的剖分点。

6.徐永安算法[11]。浙江大学工程图学所徐永安在其博士论文中对约束边、约束面在Delnanay三角剖分中的存在条件进行了理论研究，并以此为基础提出了一种将Wasotn算法与Lawosn算法相结合的算法。其主要研究特色在于提出并证明了约束边、约束面的存在条件，这一条件也就是低维单纯形的存在条件。徐永安算法在解决约束Deluanya三角剖分问题上取得了理论进展，为加点法构造约束Delnanay三角剖分提供了理论依据。但与其它已有的散乱点集Deluanya三角剖分的算法一样，徐永安算法也是从剖分的整体构造这一角度来考虑的，因而无法推广到曲面点集的拓扑重建中去。