一种基于三维散乱稠密点云的三角网格重构方法

摘要

本发明公开了一种面向三维散乱稠密点云，基于三维Delaunay四面体剖分和网格生长法的三角网格重构方法及其理论基础。该理论是基于著名的三角网格重构算法Crust算法理论的进一步推导出的粗略分离特性。本发明基于三维散乱稠密点云的三角网格重构方法，要求在两个距离近或曲率大的对顶曲面部分采样稠密。原理为：先对所有点云进行三维Delaunay四面体剖分，再根据粗略分离特性通过判断三角形的交叉值抽取出属于物体表面的部分三角形面片，再从中选择初始前沿三角形，最后从初始前沿三角形不断扩展形成整个曲面的三角网格。本发明着重改善以往三角网格剖分算法速度慢的问题，从而提高算法速度，并且生成的三角网格质量良好，适应性广。

说明书

技术领域

本发明涉及对来自三维扫描设备的三维散乱点云进行曲面重构，主要是面向三维散乱点云的三角网格重建技术和方法。 

背景技术

随着信息化社会的到来，无论是在科学研究上，还是在工程应用中，三维几何模型已经成为一种重要的数据表示形式。从曲面的三维采样点恢复出曲面的三维几何模型称之为曲面重建。通过对三维散乱点云的网格重建是曲面重建的一种重要方式。网格重建技术应用广泛，包括有限元分析、计算机图形学、科学计算可视化、生物医学、地理信息系统、逆向工程、博物馆考古的传播、特效、虚拟世界等。 

目前的三维测量设备能够在短时间内得到数万乃至几十万数据点，一方面，可以反映更精细复杂的曲面特征，但另一方面，对曲面构造的效率和效果提出了更高的要求。 

只要采样点足够，三角网格理论上可以直接逼近任何复杂的曲面，也可以在三角网格基础上进行曲面重构。 

发明内容

本发明的目的在于：提出了一种新的面向三维散乱点云的三角网格重构方法及其理论，该方法基于提出的粗略分离特性理论，结合三维Delaunay四面体剖分和三角网格生长法进行三角网格剖分，着重改善以往三角网格重构方法速度慢的问题，从而提高算法速度，并且生成的三角网格质量良好，适应性广。 

为了达到上述目的，本发明基于三维散乱稠密点云的三角网格重构方法，步骤是：先对所有点云进行三维Delaunay四面体剖分，再根据粗略分离特性通过判断三角形交叉值抽取出属于物体表面的部分三角形面片来初始化网格曲面，然后选择初始前沿三角形，最后从前沿三角形扩展形成整个三角网格曲面。 

具体步骤如下： 

第一步：导入三维散乱点云数据； 

第二步：对导入点云数据进行三维Delaunay四面体剖分，所有形成的三角 形都为Delaunay三角形，计算每个三角形的交叉值； 

第三步：根据粗略分离特性通过判断交叉值抽取部分三角形初始化三角网格曲面； 

第四步：选择初始前沿三角形，从初始前沿三角形不断扩展网格曲面，完善没有抽取出来的物体表面三角形，直到输出整个重构三维网格曲面。 

其中，第三步的过程为：选取交叉值<-0.2的三角形，选出物体表面的三角形；建立一个空栈，每条前沿边依次加进这个空栈，形成前沿边栈。 

第四步包括如下步骤： 

步骤4.1：对每条前沿边，定义一个以搜索点为球心的搜索球，搜索球内的候选点与前沿边组成的Delaunay三角形都为候选三角形；如果在搜索范围内没有找到候选点，则该前沿边被认为是边界边； 

其中，所述搜索球的定义为：选择与前沿三角形在同一平面上并且与前沿边构成正三角形的点为搜索球球心，前沿边长度为半径的搜索球； 

步骤4.2：从候选三角形里选取和前沿三角形夹角最大的唯一三角形，使之成为新的前沿三角形。检查新的前沿三角形的各条边原来是否是前沿边，如果原来是前沿边，则跳出前沿边栈变为非前沿边；如果原来不是前沿边，则变为前沿边，且将新的前沿边入栈。 

步骤四不断重复，直到前沿边栈为空停止。 

本发明面向三维散乱稠密点云，是基于三维Delaunay四面体剖分和网格生长法的三角网格重构方法及其理论基础。该理论是基于著名的三角网格重构算法Crust算法的理论进一步推导出的粗略分离特性。该方法要求在两个距离近或曲率大的对顶曲面部分采样稠密。该方法的原理如下：先对所有点云进行三维Delaunay四面体剖分，再根据粗略分离特性通过判断三角形的交叉值抽取出属于物体表面的部分三角形面片，再从中选择初始前沿三角形，最后从初始前沿三角形不断扩展形成整个曲面的三角网格。三角网格重构方法无论是在科学研究上，还是在工程应用中都有重要意义。本发明着重改善以往三角网格重构方法速度慢的问题，并且生成的三角网格质量良好，适应性广。 

附图说明

图1是二维空间和三维空间中的中轴。 

图1（a）是二维空间中的中轴示例。 

图1（b）是三维空间中的中轴示例。 

图2是局部特征值LFS(p)的定义。 

图3是交叉角的定义。 

图3（a）是二维空间中的交叉角示意图。 

图3（b）是三维空间中的交叉角示意图。 

图4是根据公共边的两个关联Voronoi点的位置，该公共边关联的两个外接圆相交情况的三种分类。 

图5是定理1的证明图示。 

图6是本发明理论部分第（ii）部分一些讨论的图示。 

图7是前沿系列和搜索系列的定义图示。 

图8是本发明算法中各步骤中间结果图。 

图8（a）是本发明算法实例手模型的点云数据模型。 

图8（b）是本发明算法对导入点云数据进行Delaunay四面体剖分的结果图。 

图8（c）是本发明算法形成的初始网格曲面。 

图8（d）是本发明算法实例的三角剖分结果，即形成的最终三角网格曲面。 

具体实施方式

本发明是基于三维散乱稠密点云的三角网格重构方法，技术方案是：先对所有点云进行三维Delaunay四面体剖分，再根据粗略分离特性通过判断三角形交叉值抽取出属于物体表面的部分三角形面片来初始化网格曲面，然后选择初始前沿三角形，最后从前沿三角形扩展形成整个三角网格曲面。具体步骤为：第一步：导入三维散乱点云数据；第二步：对导入点云数据进行三维Delaunay四面体剖分，所有形成的三角形都为Delaunay三角形，计算每个三角形的交叉值；第三步：根据粗略分离特性通过判断交叉值抽取部分三角形初始化三角网格曲面；第四步：选择初始前沿三角形，从初始前沿三角形不断扩展网格曲面，完善没有抽取出来的物体表面三角形，直到输出整个重构三维网格曲面。 

本发明提出了一种面向三维散乱稠密点云的三角网格重构方法及其理论，其特征在于以下方面： 

（1）基于Crust算法理论的粗略分离特性，包括交叉角的粗略分离特性和交叉值的粗略分离特性。在二维曲线重构问题中，当采样稠密尤其是在两段距离近或曲率大的对顶曲线部分时，曲线上两个临近采样点形成的Delaunay边的交叉角趋向于钝角或直角，其它边的交叉角趋向于锐角或直角，这种性质被称为交叉角的粗略分离特性。其对应的交叉值也有粗略分离特性，称为交叉值的 粗略分离特性。当采样密度逐步降低时，这种分离特性逐步变得不明显。粗略分离特性在三维曲面重建中和在二维曲线重建问题中大致相同，唯一的不同是由于少部分Voronoi点位于曲面附近而不是中轴上，曲面上三角形的交叉角可能是锐角。 

（2）本发明提出的一种面向三维散乱稠密点云的三角网格重构方法是基于粗略分离特性理论，包括以下五个步骤：第一步：导入三维散乱点云数据；第二步：对导入点云数据进行三维Delaunay四面体剖分，所有形成的三角形都为Delaunay三角形，计算每个三角形的交叉值；第三步：根据粗略分离特性通过判断交叉值抽取部分三角形初始化三角网格曲面；第四步：选择初始前沿三角形，从初始前沿三角形不断扩展网格曲面，完善没有抽取出来的物体表面三角形，直到输出整个重构三维网格曲面。 

本发明的实施例是在以本发明技术方案为前提下进行实施的，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述实施例。实例选取一只手模型的三维点云数据，有5029个数据采样点。 

步骤1：输入与曲面相关的三维散乱点云数据，原始通过三维扫描仪得到的点云数据是以文件的形式存储，每个点都是三维坐标X,Y,Z的形式，其输入显示如附图8（a）所示。 

步骤2：对输入点云进行Delaunay四面体剖分，最外层的多面体形成点云凸壳，每个三角形都是Delaunay三角形，那么物体表面的三角形就包含在这些Delaunay三角形中。如果物体是完全凸的，那么点云凸壳就是重构曲面。一般情况下扫描出来的物体，因为有误差，不会形成凸集。每个Delaunay四面体包含四个属性：点、边、三角形和四面体。然后计算每个Delaunay三角形的交叉值。附图8（b）为该手模型点云的Delaunay四面体剖分结果，最外层的多面体为点云凸壳。 

步骤3：通过判断交叉因子抽取部分三角形初始化三角网格曲面。从步骤2形成的Delaunay结构中，抽取部分三角形作为种子三角形来初始化三角网格曲面是本算法的关键，抽取规则很简单，即抽取那些交叉因子满足一定条件的Delaunay三角形。根据算法理论和实践经验，选取交叉值<-0.2的三角形（因为-0.2可以满足一般条件下的采样密度，当采样点密度稀疏时，可调整交叉值变小）。通过这一步可以选出大量的物体表面的三角形。如图8（c）为通过这一步 选出的物体表面的部分三角形。 

这些三角形被称为已接受三角形，只关联一个已接受三角形的边称为前沿边。建立一个空栈，每条前沿边依次加进这个空栈，形成前沿边栈。关联前沿边的已接受三角形称为前沿三角形，前沿边的点称为前沿点，不属于已接受三角形的点称为自由点，前沿点和自由点的并集称为候选点集。这一系列定义见附图7所示。 

步骤4：根据前沿边扩展剩余的物体表面的三角形。这一步骤是对前沿边栈的一个循环过程，循环过程在前沿边栈为空时结束。这一步分为以下两小步。 

步骤4.1：候选三角形的选取。对每条前沿边，定义一个以搜索点为球心的搜索球，搜索球内的候选点与前沿边组成的Delaunay三角形都为候选三角形。如果在搜索范围内没有找到候选点，则该前沿边被认为是边界边。搜索球大小的确定很关键,它影响扩展三角形的速度和质量。大的搜索半径可以找到附近较多的候选三角形，但容易导致找到的候选三角形多而扩展速度变慢。小的搜索半径，有利于扩展速度，但容易导致候选三角形不充足。搜索球的半径和局部采样的密度有关。本发明算法中选择与前沿三角形在同一平面上并且与前沿边构成正三角形的点为搜索球球心，前沿边长度为半径的搜索球。这样通过前沿边的长度可以估计局部采样密度从而把搜索球控制在一个适当的范围内。这一步形成的三角片是有重叠的。 

步骤4.2：这一步的目的是从候选三角形里选取和前沿三角形夹角最大的唯一三角形，使之成为新的前沿三角形。检查新的前沿三角形的各条边原来是否是前沿边，如果原来是前沿边，则跳出前沿边栈变为非前沿边；如果原来不是前沿边，则变为前沿边，且将新的前沿边入栈。 

步骤4不断重复，直到前沿边栈为空停止。图8（d）为手模型点云的数据的最终重构三角网格曲面。 

本发明的算法理论如下： 

本发明算法理论是基于曲面重构算法中Crust算法理论中的中轴，局部特征值LFS(P)和r-采样等概念，概念介绍如下。三维曲面重构问题在二维空间中变成了二维曲线重构问题。 

定义1（流形，Manifold）：是局部具有欧氏空间性质的空间。而实际上欧氏空间就是流形最简单的实例。 

定义2（中轴）：设Rⁿ为n维实数空间，W为Rⁿ中的流形，定义P为Rⁿ中的 点集，P中有两个或两个以上的点距离W最近且相等，点集P就是W的中轴。 

换句话说，中轴可以定义为至少有一个到物体表面距离最近的点的集合。附图1(a)(b)分别给出了R²和R³空间中中轴的示意图。图1(a)中虚线展示了光滑曲线的中轴，可以看出，根据曲面的形状，中轴有可能是不连续的，可能部分在W内部，部分在W外部（可能延伸到无穷远），需要注意的是曲面W允许有多个连通域。图1(b)展示了一个三维手模型的中轴，在三维空间中，中轴是二维曲面。 

定义3（局部特征值）：设Rⁿ为n维实数空间，W为Rⁿ中的流形，p为曲面W上任一点，LFS(p)表示p到W中轴的最短欧几里得距离。如附图2所示。 

定义4(r-采样/r-sample)：设Rⁿ为n维实数空间，W为Rⁿ中的流形，若S是W上的一个采样点集合，p为曲面W上任一点，如果它到离他最近的采样点的欧式距离不大于r·LFS(p)，则采样S满足为r-采样条件，称S为W的一个r-采样。 

在r-采样中，因为当r≥1时对点云的重构会出现歧义，所以本发明中的算法都是在r<1的大前提下。 

对输入二维（三维）点集进行Delaunay三角（四面体）剖分后形成的最外层多边形（多面体）形成了点集的凸壳。位于点集凸壳上的边（三角形）只关联一个Delaunay三角形（四面体），除此之外剩余的边（三角形）都是两个相邻Delaunay三角形（四面体）的公共边(三角形)，每个Delaunay三角形（四面体）都关联一个Voronoi点，即该三角形外接圆（四面体外接球）的圆（球）心，则公共边（三角形）关联两个Voronoi点。 

定义5(交叉角)：以点集的非凸壳上的公共边(三角形)的一个顶点为角的顶点，该点与该公共边（三角形）两个关联Voronoi点的连线为角的两条边，定义该角为该公共边（三角形）的交叉角，用表示。的范围是[0,π)，三维空间和二维空间中的交叉角分别见附图3（a）、（b）所示。 

定义6（交叉值）：公共边（三角形）的交叉角的余弦值称为该公共边（三角形）的交叉值。它的范围是(-1,1]。 

我们知道公共边是它所关联的两个外接圆的公共弦。设V1和V2是公共边关联的两个Voronoi点。 

根据公共边关联的两个Voronoi点是否同时包含在该公共边关联的其中一个外接圆中，和是否同时位于该公共边的同一侧可以分为三类，分别见附图4（a）、（b）、（c），分别对应（a）类、（b）类、（c）类。 

对于（a）、（b）两类，V₁和V₂同时位于公共边的同一侧，或者同时位于公共边关联的其中一个外接圆中，他们的交叉角很明显一定是锐角。对于（c）类，交叉角可能是锐角，直角或者钝角。 

讨论：接下来我们分类讨论平面域内的交叉角： 

(i)当公共边是两个邻近点连线的边时 

当公共边是两个邻近点连线的边时，它关联的两个外接圆不可能出现（a）和（b）类的交叉情况，所以我们只考虑公共边关联的两个Voronoi点位于该公共边两侧的情况。 

定理1：在二维空间中，r<1时，两个邻近点连线的公共边的交叉角必定是钝角。 

证明：见附图5，S₁S₂是邻近采样点的连线，P是原曲线上的点，根据r采样和局部特征值的定义可知，PS₁≤r*LFS(P)，PV₁≥LFS(P)，PV₂≥LFS(P)，那么r<1时,以P为圆心，LFS(P)为半径画圆，S₁包含在该圆中，所以角大于90度。(ii)当公共边不是两个邻近点连线的边时 

当公共边不是两个邻近点连线的边时，公共边关联的两个外接圆的交叉情况可能出现（a）（b）（c）三类中的任何一类。前两类中的交叉角都是锐角，所以我们只考虑最后一类。 

在二维曲线重构问题中，采样点通常倾向于找位于其最近对面曲线段的采样点来形成Delaunay三角形。设S₁、S₂是两个分别位于两条最近相对曲线段上的采样点，S₃、S₄是S₂的两个邻近点。接下来，我们分类讨论最后一类的交叉角（不考虑对称情况）。 

假设曲线时局部平滑的和采样是稠密的，则两个邻近采样点间的距离远远小于两条最近相对曲线间的距离，且三个邻近点形成的角为钝角，此时，交叉角趋向于锐角，见附图6（a）。 

当采样稀疏时，如果采样点距离其对面的线段较近，交叉角可能出现钝角，见附图6（b）。此外，不管S₃、S₄是否是S₂的两个邻近点，在两段对顶的非常弯曲的曲线段之间的公共边的交叉角可能是钝角，见附图6（c）。 

(iii)当两个采样点连线的边不是公共边，而是位于凸壳上的边时 

因为凸壳上的边（三角形）没有交叉角，我们规定他们的交叉角为直角，交叉值为0。 

总之，在二维曲线重构问题中，当采样稠密尤其是在两段距离近或曲率大 的对顶的曲线部分时，曲线上两个临近采样点形成的Delaunay边的交叉角趋向于钝角或直角，其它边的交叉角趋向于锐角或直角，这种性质被称为交叉角的粗略分离特性。其对应的交叉值也有粗略分离特性，称为交叉值的粗略分离特性。当采样密度逐步降低时，这种分离特性逐步变得不明显。 

粗略分离特性在三维曲面重建中和在二维曲线重建问题中大致相同，唯一的不同是由于少部分Voronoi点位于曲面附近而不是中轴上，曲面上三角形的交叉角可能是锐角。 

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明披露的技术范围内，根据本发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护范围之内。