由点云构建网格面的方法

摘要

本发明涉及一种由点云构建网格面的方法，包括以下步骤：首先将输入的点云转化成隐式场；再产生初始的腔胞复形并进行修改，使得所述腔胞复形在拓扑上正确；最后由所述腔胞复形生成拓扑一致的网格表面。该方法克服了现有技术从点云到网格面的构建中不能保证拓扑这一缺点，并能够根据表面的曲率自动调整网格的疏密，保证得到拓扑正确，几何特征得到良好保留的网格表面。

权利要求

1.一种由点云构建网格面的方法，其特征在于，包括以下步骤：将输入的点云转化成隐式场；

利用所述隐式场产生有符号的八叉树，根据所述八叉树产生初始的腔胞复形并进行修改，使得所述腔胞复形在拓扑上正确；

由修改后的腔胞复形生成拓扑一致的网格表面，具体包括：对八叉树的立方体叶子结点进行细分，直到满足以下条件之一：a.所述立方体及其边界的符号全为正或者全为负；b.所述立方体的边界能够按照符号分为两个连通分支且该立方体的每个面也符合该条件；

对每个符号为负，两个端点为正的边，细分一次；

采用DC方法完成网格表面的生成。

2.如权利要求1所述由点云构建网格面的方法，其特征在于，所述将输入的点云转化成隐式场采用MPU方法完成。

3.如权利要求1所述由点云构建网格面的方法，其特征在于，对腔胞复形进行修改具体包括：对所述初始的腔胞复形进行细化求骨架，移除骨架上的拓扑错误，得到拓扑正确的腔胞复形骨架；

由所述拓扑正确的腔胞复形骨架进行几何敏感与拓扑保持的腔胞复形重建。

4.如权利要求1所述由点云构建网格面的方法，其特征在于，所述有符号的八叉树的层数为7～8层。

5.如权利要求3所述由点云构建网格面的方法，其特征在于，所述对初始的腔胞复形进行细化求骨架并移除骨架上的拓扑错误时，如果遇到有表现为骨架上小圈的拓扑错误，则将小圈断开，然后进一步细化骨架，最终得到没有拓扑错误的骨架。

6.如权利要求3所述由点云构建网格面的方法，其特征在于，所述由拓扑正确的腔胞复形骨架进行几何敏感与拓扑保持的腔胞复形重建时，对几何体表面进行考察，在变化剧烈的地方加大腔胞复形的描述精度，并在原拓扑错误的地方加大描述精度。

说明书

由点云构建网格面的方法

技术领域

[0001] 本发明属于数字几何模型处理领域，特别涉及一种几何与拓扑敏感的由点云构建网格面的方法。

背景技术

[0002] 在数字几何模型处理领域，一个三维模型常有三种描述方式，一种是点云方式，即对模型的表面进行采样，直接用采样点来表达模型，这种方法比较简单，处理数据相对容易，是很多扫描模型数据的原始格式，但是，这种方法也有其固有的缺点，点云无法描述物体的拓扑，而且如果要以较高的精度描述表面，需要非常多的点；第二种是网格方式，即用有着连接关系的面片来表示模型表面，这种描述方式可以准确描述物体的拓扑，在3D建模和动画领域有着非常广泛的应用；第三种是样条曲面方式，由于这种方式与本发明的关系不大，故不多加阐述。

[0003] 在实际3D建模应用中，经常需要将点云描述方式转化为网格的描述方式。目前常用的方法有以下几种：体方法，通过点云拟合一个三维空间的隐式场，该隐式场的零点处即为隐式表面，然后直接通过非常成熟的Marching Cubes方法或其变种进行轮廓面的提取，从而完成网格的构造；非体方法，即直接从点云出发，生成网格。但是，这些方法都有一些重大的缺点：首先，这些方法所产生的网格很可能包含有拓扑错误，这些拓扑错误常常以小环或者表面空洞的形式存在；其次，这些方法大都不能很好地对所生成的曲面作出自适应的调整，即，在表面变化比较大的地方加大描述精度，而在表面变化较为缓和的地方减少描述精度，从而要么对物体表面的描述不够精确，要么所产生的面片数过多，给后续的渲染和处理造成负担。一些成熟的商业几何造型软件，如Geomagic、free form等软件，其所提供的点云建造网格功能都或多或少存在这些问题，特别地，目前尚未发现已知的商业软件能在点云重构网格的过程中保证拓扑的正确性。

[0004] 为了能够够描述物体的拓扑，腔胞复形是常用的一种描述方法。这种方法用点、线、面、体来描述物体，如果包含一条线，则必包含该线的两个端点，同理，如果包含一个面或体，则必包含其边界。用腔胞复形描述物体有一个好处，就是可以清楚地表示物体的拓扑，算出物体的亏格等拓扑不变量，同时，还可以对物体进行保拓扑的骨架抽取(骨架本身也是腔胞复形)，以及基于骨架的保拓的生长。在三维空间中，腔胞复形的常用表示方式是带符号的八叉树(ESO)，这是计算机图形学中常用的一种数据结构。近年来，腔胞复形技术在数字几何处理领域的应用越来越广泛。

[0005] 发明内容

[0006] 本发明的目的是提供一种由点云构建网格面的方法，以克服现有从点云生成网格面的技术中无法进行拓扑控制以及自适应调整面片规模等缺陷。

[0007] 为了达到上述目的，本发明的技术方案提出一种由点云构建网格面的方法，包括以下步骤：

[0008] 将输入的点云转化成隐式场；

[0009] 利用所述隐式场产生有符号的八叉树，根据所述八叉树产生初始的腔胞复形并进行修改，使得所述腔胞复形在拓扑上正确；

[0010] 由所述腔胞复形生成拓扑一致的网格表面，具体包括：

[0011] 对八叉树的立方体叶子结点进行细分，直到满足以下条件之一：a.所述立方体及其边界的符号全为正或者全为负；b.所述立方体的边 界能够按照符号分为两个连通分支且该立方体的每个面也符合该条件；

[0012] 对每个符号为负，两个端点为正的边，细分一次；

[0013] 采用DC方法完成网格表面的生成。

[0014] 上述由点云构建网格面的方法中，所述将输入的点云转化成隐式场采用MPU方法完成。

[0015] 上述由点云构建网格面的方法中，对腔胞复形进行修改具体包括： [0016] 对所述初始的腔胞复形进行细化求骨架，移除骨架上的拓扑错误，得到拓扑正确的腔胞复形骨架；

[0017] 由所述拓扑正确的腔胞复形骨架进行几何敏感与拓扑保持的腔胞复形重建。 [0018] 上述由点云构建网格面的方法中，所述有符号的八叉树的层数为7～8层。 [0019] 上述由点云构建网格面的方法中，所述对初始的腔胞复形进行细化求骨架并移除骨架上的拓扑错误时，如果遇到有表现为骨架上小圈的拓扑错误，则将小圈断开，然后进一步细化骨架，最终得到没有拓扑错误的骨架。

[0020] 上述由点云构建网格面的方法中，所述由拓扑正确的腔胞复形骨架进行几何敏感与拓扑保持的腔胞复形重建时，对几何体表面进行考察，在变化剧烈的地方加大腔胞复形的描述精度，并在原拓扑错误的地方加大描述精度。

[0021] 本发明的技术方案在由点云构建网格面的过程中，克服了传统技术不能保证网格拓扑的不足，且能针对表面变化的程度自动调整描述精度，最后生成的网格既能保证拓扑，又能保证几何细节。

[0022] 附图说明

[0023] 图1为本发明由点云构建网格面的方法实施例流程图；

[0024] 图2为本发明实施例模型的八叉树示例；

[0025] 图3为本发明实施例腔胞复形的一个例子；

[0026] 图4为本发明实施例的细化示例；

[0027] 图5为本发明实施例中细分和骨架生长示例；

[0028] 图6为本发明实施例的网格面生成示例(二维情况)；

[0029] 图7为本发明实施例的网格面生成示例。

具体实施方式

[0030] 以下实施例用于说明本发明，但不用来限制本发明的范围。

[0031] 图1为本发明由点云构建网格面的方法实施例流程图，其输入数据为带有法向信息的点云，输出为有几何与拓扑保证的网格。如图所示，本实施例包括以下步骤：S101、将输入的点云转化成隐式场；S102、产生初始的腔胞复形描述；S103、对初始的腔胞复形进行细化求骨架，移除骨架上的拓扑错误，得到拓扑正确的腔胞复形骨架；S104、由拓扑正确的腔胞复形骨架进行几何敏感与拓扑保持的腔胞复形重建；S105、由腔胞复形生成拓扑一致的网格表面。

[0032] 下面进一步对上述步骤S101～S105进行详细说明。

[0033] S101、将输入的点云转化成隐式场。

[0034] 该步骤直接采用目前常用的MPU(Multi-level Partition of UnityImplicits，多层次的单位隐式曲面分解)方法。输出的隐式场是一个函数，定义在三维空间上，取值在实数轴上，其零点处定义一个隐式曲面，大于零处定义物体内部，小于零处定义物体外部。 [0035] S102、产生初始的腔胞复形描述。

[0036] 本步骤的腔胞复形是用带符号八叉树(ESO)描述的，在ESO中每一个元素都被分配了一个符号来记录其是否属于体内(正表示体内，负表示体外)。这里，元素包括了点(point，0维元素)、边(edge，1维元素)、面(face，2维元素)和腔(cell，3维元素)，如图2所 示，其中，(a)部分为原始Eight模型；(b)部分为八叉树的模型内部体结构；(c)部分为完整的空间八叉树。需要注意的是，每个元素的符号和隐式场中的符号是两个不同的概念。这一步主要的目的是给物体一个初始的拓扑描述，所以八叉树的层数一般不会很深。给定一个隐式场，通过以下步骤得到一个初始的腔胞复形：

[0037] i.指定八叉树的最深层数，一般为7或8，初始情况下八叉树只有一层； [0038] ii.随便在表面某处指定一个立方格，立方格的大小和最深层数有关，最深层数越深，立方格越小；然后对八叉树进行细分，使得该立方格成为八叉树的一个叶子节点；再建立一个空队列q，将立方格放入队列中。

[0039] iii.若队列q空，则转步骤v，否则从队列q中取出一个立方格C(八叉树的一个叶子节点)。

[0040] iv.对C的每个面作如下操作，如果该面的4个顶点在隐式场中的符号相同或者C与该面相对的立方体已经是八叉树的一个叶子结点，则转iii，否则进一步细分八叉树，使得C与该面相对的立方体是八叉树的一个叶子结点，将对应的叶子结点加入队列q，转步骤iii。

[0041] v.生成腔胞复形，若八叉树中某点在隐式场中的符号为正，则其符号为正，否则为负，若八叉树某条边的端点的符号都为正，则该边为正，否则为负。若某个面所有边界边都为正，则该面为正，否则为负。若某个腔(也称体，即叶子立方格)的所有边界面都为正，则该腔为正，否则为负。

[0042] 通过上述步骤i～v，一个带符号八叉树(ESO)就生成了，它就是初始的腔胞复形。 [0043] S103、对初始的腔胞复形进行细化求骨架，移除骨架上的拓扑错误，得到拓扑正确的腔胞复形骨架。

[0044] 首先要对初始的腔胞复形进行细化，以求得它的骨架，如图3所 示，其中，(a)部分为原物体，(b)部分为其骨架，可以看到原物体上的一个环对应骨架图上的一个圈。细化的过程是通过移除“简单对”来实现的(如图4所示)，即如果一个低维元素仅仅被一个高维元素所含有，则这两个元素可以同时去除，而不影响整个物体的拓扑。这是数字几何处理领域新提出的一个方法。这样处理后可以得到一个骨架。骨架上的一个圈对应原物体上的一个环，将骨架上的圈断开对应着去除原物体上的一个环，如果这个环是一个拓扑错误，等于去除了一个拓扑错误。

[0045] 下面说明怎样识别一个环究竟是否是拓扑错误。一个环有两个属性，它的大小和厚度，大小指的是要对该环进行填充至少所需要填充的面积，厚度指的是要将该环切开切面的最小面积。在本步骤中，如果一个环的大小或厚度小于某固定的阈值，它就属于一个拓扑错误，这在实际应用中也是很合理的。如何测量一个环的大小和厚度，是腔胞复形处理中的一个现有技术，这里不再赘述。为了去除拓扑错误，只需要在骨架上把环断开(把其中一条边去掉)即可，然后可以继续进行细化。不断进行细化和去除拓扑错误，直到没有发现拓扑错误为止。

[0046] S104、由拓扑正确的腔胞复形骨架进行几何敏感与拓扑保持的腔胞复形重建。 [0047] 本步骤包括两个子步骤，即首先对八叉树进行进一步细分，然后从步骤S103所得到的骨架出发，进行保拓扑的生长。由于原先的八叉树仅为描述拓扑，所以其层数不深，为了使得其能描述几何细节，还要对其进行细分。为了能充分考虑几何和拓扑特性，需要确定一些“特征”区域。在这些区域进行细分，区域所含的“特征”越多，所细分的精度就越高。本算法所定义的特征包含两类，一类是拓扑特征，一类是几何特征。拓扑特征指的是在步骤S103中所定位的含有拓扑错误的地方，几何特征指的是表面处变化较大，或者说曲率较大的地 方，曲率越大，表面其几何特征就越明显。为了确定几何特征，采用积分球的办法，这是数字几何处理领域常用的一个方法。即，为了确定表面某点的弯曲程度，以其为中心做一个球，球与物体内部的公共体积与球体积之比就是该处的几何特征，显然该值与0.5相差越小，该处就越平坦，反之则越弯曲。

[0048] 本方法在拓扑错误和几何弯曲较大的地方对八叉树进行进一步的细分，几何弯曲越大，细分的精度就越高，参见图5。第二个步骤是对骨架进行生长，这里的生长是步骤S103中细化的逆操作，即每次增加两个“简单对”元素。为了保证骨架只在物体内部生长，要求每次增长的0维元素(即点)在隐式场中的符号必须是正的。

[0049] S105、由腔胞复形生成拓扑一致的网格表面

[0050] 本步骤采用改进的DC方法。其示例如图6、7所示，其中，(a)部分对应原始的腔胞复形，(b)部分则对应经过特殊细分后的腔胞复形及网格面。实现本步骤的具体方法如下：由S104得到的腔胞复形可能并不适合直接生成网格表面，需要进行特殊细分。所谓的特殊细分，是指以下步骤：

[0051] i.对八叉树的叶子结点(立方体)进行细分，直到满足以下条件之一： [0052] 1)该立方体及其边界的符号全为正或者全为负，

[0053] 2)该立方体的边界可以按照符号分为两个连通分支，且该立方体的每个面也符合这个条件。

[0054] ii.对每个符号为负，两个端点却是正的边，细分一次。

[0055] 上述的特殊细分后，即可采用已有的DC(Dual contouring，对偶轮廓面构造法)方法进行网格面的生成，即：为每个有符号变化的叶子立方体，产生一个顶点，位置用原始的DC方法计算，然后为每条有符号变化的边，产生一个面连接与该边相邻的各个叶子立方体所对应的顶点。可以在数学上证明，这样产生的网格面和腔胞复形能保持 拓扑的一致。 [0056] 对生成网格面的结果进行分析，可以发现本发明可以生成同时有几何与拓扑保证的网格面。相对于现有的方法，如Geomagic等成熟的商业软件，本方法不仅弥补了其不能保证拓扑的缺点，而且可以主动检测表面的几何细节，在弯曲程度大的地方自动加大描述精度，最终得到几何与拓扑都能得到保证的网格面。

[0057] 以上为本发明的最佳实施方式，依据本发明公开的内容，本领域的普通技术人员能够显而易见地想到一些雷同、替代方案，均应落入本发明保护的范围。