CN109636913A - 基于Delaunay剖分的三角网格增量拓扑拼接方法 - Google Patents

Abstract

本发明的目的在于提供一种基于Delaunay剖分的三角网格增量拓扑拼接方法。该方法通过边缘清理删除待拼接网格边界上的畸形面片；基于边缘清理后的网格以及被删除面片的顶点集合，构造待拼接网格之间的缝合区域，并为该区域数据点集添加边界保护点；采用Delaunay曲面插值重建算法对缝合区域数据点集进行局部重建，并通过波前扩展策略使此局部重建过程在缝合区域内传播，获取插值于网格拼接处数据点的缝合曲面。该算法可实现三角网格的拓扑正确拼接，具有较高的拼接效率，所生成的缝合曲面能够较为准确地反映原始模型在网格拼接处的局部细节特征。

Description

基于Delaunay剖分的三角网格增量拓扑拼接方法

技术领域

本发明提供一种基于Delaunay剖分的三角网格增量拓扑拼接方法，可实现曲面网格之间的拓扑正确拼接，属于产品逆向工程领域。

背景技术

基于实物表面采样数据的曲面重建技术被广泛应用于CAD/CAM、机器视觉、虚拟现实等诸多领域。三维扫描技术的发展使得点云采样数据的规模日趋庞大，例如激光扫描仪所获得的点云数据可达千万级甚至亿级。针对如此大规模的点云数据直接进行曲面重建，算法的时间复杂度和空间复杂度通常较高，难以在提高拼接效率的同时保证拼接结果的正确性。若对点云数据进行分块重建，然后将所得各块重建网格拼接成整体网格，则可显著降低算法的时空复杂度，提升大规模点云数据的重建效率。在该过程中如何正确拼接各块重建网格，以恢复整体曲面的拓扑邻接关系，是制约大规模点云数据重建效率及重建结果拓扑正确性的关键问题。

为实现网格拼接，Turk等在《Zippered polygon meshes from range images》(Conference on Computer Graphics&Interactive Techniques.1994:311-318.)中基于裁剪的思想提出一种Zipper算法，即利用一块网格的边界裁剪另一块网格的边界三角形，基于剩余网格的边界样点及被删减三角面片的顶点生成待拼接网格之间的缝合曲面；Jin等在《Mesh fusion using functional blending on topologically incompatiblesections》(Visual Computer,2006,22(4):266-275.)中首先采用径向基函数拟合待拼接模型的边界，然后基于Hermite曲面插值的方法获得待拼接区域的连续曲面，实现网格的无缝光滑衔接；Lin等在《Mesh composition on models with arbitrary boundarytopology》(IEEE Transactions on Visualization&Computer Graphics,2008,14(3):653.)中基于移动立方体的方法将缝合区域的隐式拟合曲面转化为离散网格，得到拼接完成的整体曲面；Qin等在《Efficient Smoothness-Preserving Fusion Modelling Methodfor Mesh Models》(International Journal of Simulation Modelling,2017,16(3):527-540.)中将待拼接网格的边界轮廓投影到二维平面，对轮廓的顶点集合进行三角剖分并基于隐函数插值的方法对经过细分的轮廓顶点剖分结果进行平滑，从而得到光滑的缝合曲面。上述方法生成的缝合曲面能够将待拼接网格无缝光滑衔接，但均忽略了网格拼接处样点间的拓扑邻接关系，所生成的缝合曲面通常难以准确反映网格拼接处的局部细节特征。

Dey等在《Localized Cocone surface reconstruction》(Computers&Graphics,2011,35(3):483-491.)中基于Delaunay剖分的方法提出了Localized Cocone算法。该算法可实现曲面分块重建网格之间的正确拼接，且所生成的缝合曲面可较为准确地反映网格拼接处样点间的拓扑邻接关系。但Localized Cocone算法在实现网格拼接过程中需要对网格顶点集合进行多次Delaunay剖分,算法的时间复杂度和空间复杂度过高，降低了网格拼接的效率。

发明内容

本发明的目的在于提供一种基于Delaunay剖分的三角网格增量拓扑拼接方法，可兼顾网格拼接的效率以及拼接结果的拓扑正确性。其技术方案为：

一种基于Delaunay剖分的三角网格增量拓扑拼接方法，其特征在于步骤依次为：(1)构造列表L＝{D(S_i)|i＝1,2,...,n}，列表中任一元素D(S_i)为待拼接的三角网格，S_i为网格顶点集合，令S为S₁∪S₂∪...∪S_n；(2)对每一块待拼接的三角网格D(S_i)进行边缘清理，即：对D(S_i)中最外层具有完整拓扑圆盘结构面片顶点的入射面片进行删除，并将所删除面片的顶点存入集合O_i，直至D(S_i)中剩余面片顶点位于S中的Voronoi近邻点均包含于S_i中；(3)将D(S_i)中被删除面片的顶点集合O_i合并，得到缝合区域数据点集O；(4)为保证O边界区域的点具有完整的Voronoi近邻点，将D(S_i)中最外层具有完整拓扑圆盘结构面片顶点的Voronoi近邻点作为O的边界保护点添加到O中；(5)从O中选取一点p₀，并获取距离p₀最近的k个点组成点集λ(p₀)，对点集{p₀}∪λ(p₀)进行Delaunay曲面插值重建，并将重建结果作为曲面初始区域，通过波前扩展算法构建插值于O的缝合曲面Q；(6)Q∪D(S₁)∪D(S₂)∪...∪D(S_n)为网格拼接结果。

为实现发明目的，所述的基于Delaunay剖分的三角网格增量拓扑拼接方法，其特征在于：步骤(2)中，对每一块三角网格D(S_i)进行边缘清理的步骤具体是：(1)获取D(S_i)的边界边，将边界边入射面片中非边界边上的点存入集合P_i中；(2)令j为1，k为P_i中的顶点数量；(3)从P(λ_i)中提取点p_j，计算p_j位于D(S_i)中入射三角形的最大外接圆半径r_j；(4)以p_j为球心，为半径作球，将S中包含于该球内的点存入空集中；(5)若不完全包含于D(S_i)所对应的网格顶点集合S_i，则将P_i中各点的入射面片从D(S_i)中删除，并将P_i清空，然后执行(1)；(6)令j增1，若j≤k，则执行(3)，否则清理过程结束。

为实现发明目的，所述的基于Delaunay剖分的三角网格增量拓扑拼接方法，其特征在于：步骤(4)中，从D(S_i)中获取O的边界保护点的步骤具体是：(1)查询D(S_i)的边界边，将边界边入射面片中非边界边上的点存入集合M_i；(2)对于M_i中的每个顶点p_l，计算p_l位于D(S_i)中入射三角形的最大外接圆半径r_l，然后以pl为球心，为半径作球，将该球内不属于点集O中的点标记为保护点添加到O中。

为实现发明目的，所述的基于Delaunay剖分的三角网格增量拓扑拼接方法，其特征在于：在步骤(5)中，对{p₀}∪λ(p₀)的Delaunay曲面插值重建结果采用权利要求2中所述方法进行边缘清理，将所得结果作为曲面初始区域，通过波前扩展算法构建插值于O的缝合曲面Q。

为实现发明目的，所述的基于Delaunay剖分的三角网格增量拓扑拼接方法，其特征在于：在通过波前扩展算法构建插值于O的缝合曲面Q的过程中，对于已构建曲面区域中的任一边界点p_r，以p_r与O中距离其最近的k个点组成的点集λ(p_r)构成目标剖分区域，对λ(p_r)进行Delaunay曲面插值重建，并对重建结果采用权利要求2中所述方法进行边缘清理，然后删除边缘清理结果中与构建完成区域重叠的面片，并对已构建曲面作增量扩展。

本发明与现有技术相比，具有以下优点：

(1)通过边缘清理删除待拼接网格边界区域上畸形面片；基于保护点的添加，采用Delaunay曲面插值重建算法对缝合区域数据点集进行局部重建，并通过波前扩展算法将此局部重建过程在缝合区域内传播，获得插值于网格拼接处数据点集的缝合曲面，可实现相邻网格之间的拓扑正确拼接。

(2)缝合曲面是基于局部重建以及波前环的扩张、分裂等方式在网格拼接处的点集中逐步扩展而成；整个过程仅依赖少量点集的Delaunay网格剖分结果，具有较高的网格拼接效率。

(3)该方法适用于海量点云分块重建网格的拼接，可保证最终重建结果拓扑正确性并显著提升海量点云数据的重建效率。

附图说明

图1是待拼接网格边界区域上任意点p的Voronoi近邻点分布范围；

图2～图3是相邻网格边缘清理前和边缘清理后的效果图；

图4是相邻网格之间缝合区域的边界点及扩展边界点；

图5是缝合曲面的波前扩展过程示意图；

图6是实施例一中Happy Buddha模型的分块重建网格；

图7～图9实施例一中Happy Buddha模型分块重建网格拼接结果图；

图10实施例二中Venus模型的分块重建网格；

图11实施例二中Venus模型分块重建网格拼接结果图。

具体实施方式

下面结合附图及实施例对本发明作进一步说明。

设分割点云S所得到的各块子集为{S₁,S₂,...,S_n}，对每块子集进行曲面重建，得到各块待拼接的三角网格{D(S₁),D(S₂),...,D(S_n)}。在任意待拼接网格D(S_i)独立生成过程中，由于D(S_i)边界区域样点的部分Voronoi近邻点存在于与D(S_i)相邻的网格中(如图1所示)，导致D(S_i)的边界区域面片通常难以准确反映网格拼接处样点间的拓扑邻接关系。因此为实现各块网格之间的拓扑正确拼接，需对每块待拼接网格进行边缘清理，即对其边界区域上的点进行Voronoi近邻点完整性检测，将Voronoi近邻点不均位于该块网格中的顶点的入射面片删除。

为进行准确的边缘清理，首先需要获取待拼接网格边界区域样点完整的Voronoi近邻点。对于待拼接网格D(S_i)中具有完整拓扑圆盘结构的任意样点p而言，其完整的拓扑近邻点必定包含于中，其中B(p；r)是指以p为中心、r为半径的圆球，而r为D(S_i)中点p入射三角形的最大外接圆半径。因此，可对D(S_i)中具有完整拓扑圆盘结构的样点p，以p为球心，为半径作球，将该球内所包含的点近似看作点p的完整Voronoi近邻点。但由于待拼接网格的边界点不具备完整的拓扑圆盘结构，因此在边缘清理过程中，各块待拼接网格边界区域样点Voronoi近邻点的完整性检测需要从该块网格中具有完整拓扑圆盘结构的最外层样点开始进行。对整体点云S的子集S_i独立重建所生成的待拼接网格D(S_i)进行边缘清理的步骤如下：(1)获取D(S_i)的边界边，将边界边入射面片中非边界边上的点存入集合P_i中；(2)令j为1，k为P_i中的顶点数量；(3)从P(λ_i)中提取点p_j，计算p_j入射三角形的最大外接圆半径r_j；(4)以p_j为球心，为半径作球，将S中包含于该球内的点存入空集中；(5)若不完全包含于S_i，则将P_i中各点的入射面片从D(S_i)中删除，将所删除面片的顶点存入集合O_i，并将P_i清空，然后执行(1)；(6)令j增1，若j≤k，则执行(3)，否则清理过程结束。相邻待拼接网格边缘清理前和边缘清理后的效果分别如图2和图3所示。

在各块网格边缘清理完成后，相邻网格之间的缝合区域由各块网格中被删除面片的顶点集合构成。因此，可通过合并被删除面片的顶点集合来构造待拼接网格之间的缝合区域。只要能够实现缝合区域内数据点集的正确重建，便可在相邻网格之间生成缝合曲面，完成网格拼接的过程。

缝合区域内数据点集的正确重建同样需要保证其边界区域的点具有完整的Voronoi近邻点。如图4所示，缝合区域的边界点亦是经过边缘清理后待拼接网格的边界点，因此可将每块待拼接网格边界点的完整Voronoi近邻点添加到缝合区域内，从而保证该区域边界点Voronoi近邻点的完整性。但由于待拼接网格的边界点不具备完整的拓扑圆盘结构，因而无法基于其入射三角形的最大外接圆半径查询到其完整的Voronoi近邻点集。此时，可将缝合区域的边界点向待拼接网格内部扩展，将待拼接网格内具有完整拓扑圆盘结构的最外层样点作为缝合区域的扩展边界点，并将扩展边界点完整Voronoi近邻点的查询结果添加到缝合区域中，从而保证缝合区域边界点Voronoi近邻点的完整性。此处，将新添加至缝合区域中的点作为保护点。设缝合区域数据点为O，则缝合区域的构造及其边界保护点的添加步骤如下：(1)将每一块待拼接网格D(S_i)在边缘清理过程中被删除面片的顶点集合O_i合并，得到缝合区域数据点集O；(2)获取D(S_i)中最外层具有完整拓扑圆盘结构面片顶点的Voronoi近邻点，并将其标记为保护点添加到O中；在上述步骤(2)中，从任一块网格D(S_i)中获取O的边界保护点的步骤具体是：①查询D(S_i)的边界边，将边界边入射面片中非边界边上的点存入集合M_i；②对于M_i中的每个顶点p_l，计算p_l位于D(S_i)中入射三角形的最大外接圆半径r_l，然后以p_l为球心，为半径作球，将该球内不属于点集O中的点标记为保护点添加到O中。

由于缝合区域数据点集属于非封闭的长条型点云，直接对其进行插值曲面重建往往会产生大量的跨区域面片，影响最终重建结果的正确性。为解决这一问题，可采用Delaunay曲面插值重建算法中重建结果具有理论保证的Cocone算法重建缝合区域数据点集的局部样本，并通过上述的边缘清理方法删除局部重建结果中Voronoi近邻点不完整的顶点入射面片；然后基于波前扩展算法将上述局部重建过程向整个缝合区域延伸，从而获得插值于网格拼接处数据点集的缝合曲面，完成网格的拼接过程。

以缝合区域内的特定样点p及距离p最近的k个点组成的点集λ(p)作为局部重建样本，并将生成的缝合曲面设为Q。为提升局部样本的获取效率，采用R*树作为数据索引。对各块待拼接的三角网格{D(S₁),D(S₂),...,D(S_n)}进行增量拓扑拼接的步骤如下：(1)构造列表L＝{D(S_i)|i＝1,2,...,n}，列表中任一元素D(S_i)为待拼接的三角网格，S_i为网格顶点集合，令S为S₁∪S₂∪...∪S_n；(2)对L中每一块待拼接的三角网格D(S_i)进行边缘清理，然后基于边缘清理后的网格以及被删除面片的顶点集合构造缝合区域数据点集O，并为O添加边界保护点；(3)采用R*树建构点集O的空间索引，同时选取O中Z坐标最小的点作为初始点p₀，以p₀及距离p₀最近的k个点组成的点集λ(p₀)作为初始局部重建样本；(4)采用Cocone算法对λ(p₀)进行曲面重建，得到初始局部重建网格D(λ(p₀))，并对D(λ(p₀))进行边缘清理；(5)将D(λ(p₀))加入到Q中，并将D(λ(p₀))中的点标记为饱和点；(6)获取Q的边界边，并从边界边中获取首个不含有边界点标记的点p_r，若p_r不存在，执行步骤(9)；(7)将p_r及距离p_r最近的k个点组成的点集λ(p_r)作为局部样本，若此时λ(p_r)中的点均为饱和点，则将p_r标记为边界点，执行步骤(6)，否则对λ(p_r)进行曲面重建，获得局部重建网格D(λ(p_r))；(8)对D(λ(p_r))进行边缘清理，并删除D(λ(p_r))内与Q中重叠的面片，将剩余网格添加到Q中，并将新加入Q中的网格顶点标记为饱和点，然后执行(6)；(9)将保护点的入射面片从Q中删除，Q∪D(S₁)∪D(S₂)...∪D(S_n)为网格拼接结果。

如图5所示，经波前扩展生成的缝合曲面网格能够无缝的衔接待拼接网格的边界，使得相邻的待拼接网格融合成一块整体网格。

本文所用主要参数为缝合曲面生成过程中的局部样本获取数量k，可根据缝合区域内数据点集的分布密度来选取，对于样点分布较为均匀的缝合区域数据点集，建议k取值为50，而对于样点非均匀分布的缝合区域数据点集，可适当增大局部样本数量，建议k取值为80。

实施例一：对图6所示Happy Buddha点云模型分块重建网格，应用本文所述方法进行拼接。图6所示模型网格拼接处的样点分布较为均匀，但局部存在曲率变化较大区域。从图7～图9可以看出，本文算法能够正确拼接边界区域样点分布较为均匀的网格模型；同时在曲率变化较大的模型特征区域，本文算法生成的缝合曲面能够较为准确的反映原始模型在该处的局部细节特征。

实施例二：对图10所示Venus点云模型分块重建网格，应用本文所述方法进行拼接。图10所示模型在网格拼接处存在样点分布不均匀的特征区域。如图11所示，本文算法可正确拼接边界区域样点分布不均匀的网格模型。

以上所述，仅是本发明的较佳实施例而已，并非是对本发明作其他形式的限制，任何熟悉本专业的技术人员可能利用上述揭示的技术内容加以变更或改型为等同变化的等效实施例。但是凡是未脱离本发明技术方案内容，依据本发明的技术实质对以上实施例所做的任何简单修改、等同变化与改型，仍属于本发明技术方案的保护范围。

Claims (5)

1.一种基于Delaunay剖分的三角网格增量拓扑拼接方法，其特征在于，步骤依次为：(1)构造列表L＝{D(S_i)|i＝1,2,...,n}，列表中任一元素D(S_i)为待拼接的三角网格，S_i为网格顶点集合，令S为S₁∪S₂∪...∪S_n；(2)对每一块待拼接的三角网格D(S_i)进行边缘清理，即：对D(S_i)中最外层具有完整拓扑圆盘结构面片顶点的入射面片进行删除，并将所删除面片的顶点存入集合O_i，直至D(S_i)中剩余面片顶点位于S中的Voronoi近邻点均包含于S_i中；(3)将D(S_i)中被删除面片的顶点集合O_i合并，得到缝合区域数据点集O；(4)为保证O边界区域的点具有完整的Voronoi近邻点，将D(S_i)中最外层具有完整拓扑圆盘结构面片顶点的Voronoi近邻点作为O的边界保护点添加到O中；(5)从O中选取一点p₀，并获取距离p₀最近的k个点组成点集λ(p₀)，对点集{p₀}∪λ(p₀)进行Delaunay曲面插值重建，并将重建结果作为曲面初始区域，通过波前扩展算法构建插值于O的缝合曲面Q；(6)Q∪D(S₁)∪D(S₂)∪...∪D(S_n)为网格拼接结果。

2.如权利要求1所述的基于Delaunay剖分的三角网格增量拓扑拼接方法，其特征在于：步骤(2)中，对每一块三角网格D(S_i)进行边缘清理的步骤具体是：(1)获取D(S_i)的边界边，将边界边入射面片中非边界边上的点存入集合P_i中；(2)令j为1，k为P_i中的顶点数量；(3)从P(λ_i)中提取点p_j，计算p_j位于D(S_i)中入射三角形的最大外接圆半径r_j；(4)以p_j为球心，为半径作球，将S中包含于该球内的点存入空集中；(5)若不完全包含于D(S_i)所对应的网格顶点集合S_i，则将P_i中各点的入射面片从D(S_i)中删除，并将P_i清空，然后执行(1)；(6)令j增1，若j≤k，则执行(3)，否则清理过程结束。

3.如权利要求1所述的基于Delaunay剖分的三角网格增量拓扑拼接方法，其特征在于：步骤(4)中，从D(S_i)中获取O的边界保护点的步骤具体是：(1)查询D(S_i)的边界边，将边界边入射面片中非边界边上的点存入集合M_i；(2)对于M_i中的每个顶点p_l，计算p_l位于D(S_i)中入射三角形的最大外接圆半径r_l，然后以p_l为球心，为半径作球，将该球内不属于点集O中的点标记为保护点添加到O中。

4.如权利要求1所述的基于Delaunay剖分的三角网格增量拓扑拼接方法，其特征在于：在步骤(5)中对{p₀}∪λ(p₀)的Delaunay曲面插值重建结果采用权利要求2中所述方法进行边缘清理，将所得结果作为曲面初始区域，通过波前扩展算法构建插值于O的缝合曲面Q。

5.如权利要求4所述的基于Delaunay剖分的三角网格增量拓扑拼接方法，其特征在于：在通过波前扩展算法构建插值于O的缝合曲面Q的过程中，对于已构建曲面区域中的任一边界点p_r，以p_r与O中距离其最近的k个点组成的点集λ(p_r)构成目标剖分区域，对λ(p_r)进行Delaunay曲面插值重建，并对重建结果采用权利要求2中所述方法进行边缘清理，然后删除边缘清理结果中与构建完成区域重叠的面片，并对已构建曲面作增量扩展。