随着逆向工程和三维建模技术的不断发展，三角网格模型被广泛应用于快速成型、虚拟现实以及工业设计中，并且贯穿于模型的整个生命周期。在三维激光扫描系统中^{[1, 2, 3]}，由于待测模型自身缺陷或采样点数据不足等因素的影响，测量结果中存在数据丢失现象，这使得重建网格模型^{[4, 5]}中可能存在空洞缺陷。这些空洞不仅影响重建模型的视觉效果，而且影响模型快速重建、有限元分析等后续处理的有效性。空洞识别是指通过某种途径将网格模型中的空洞缺陷识别出来，以便进行空洞修复。因此，空洞识别技术是否完善直接关系到网格模型空洞修复的整体效果，在网格模型的建立过程中起到举足轻重的作用。

目前，主要的空洞识别与修复技术包括基于点云模型的修复技术^{[6, 7]}和基于网格模型的修复技术^{[8, 9, 10, 11, 12, 13]}。在基于点云模型的修复技术中，Min等人^{[6, 7]}采用层次空间剖分技术进行空洞识别，利用张量理论提取发生剧烈变化的点云区域并消除噪声的影响。但是，该方法在提取空洞周围点云数据的拓扑信息时存在较高的计算复杂度。相对而言，基于网格模型的修复技术更容易实现，其中，王乾等人^{[8, 9]}对点云模型中的空洞进行分类，并分别给出了对应的识别与修复算法。该类方法虽然能够进行有针对性的空洞修复，但是，分类过程带来了额外的运算量且所分类别很难涵盖所有情况下的空洞。Wang等人^{[10, 11]}分别提出了将曲面空洞周围的灰度信息以及拐点等特征信息作为辅助的空洞修复方法，该类方法受空洞的个体差异影响较为明显。高旋辉等人^{[12, 13]}提出了基于邻接三角形中边界边性质的空洞识别方法，该类方法具有较强的通用性，但是在进行特殊空洞的识别过程中鲁棒性较低且容易破坏网格模型的原始数据结构。

针对上述问题，本文在系统分析普通空洞与特殊空洞结构特性的基础上，提出了一种无需对各种情况进行分别判断即可有效识别出曲面空洞的具有强鲁棒性的空洞识别与修复方法。通过为边界边重新分配长度的方法对网格中的空洞进行数学建模，将图论中的Floyd最短路径选择算法^[14]与空洞识别过程有效结合，采用经典的波前法处理空洞边集生成修复后的三维曲面。

设有节点集V={v₁,v₂,…,v_n}，当存在关系R将V中的某些节点相互连接生成边集E={e₁,e₂,…,e_m}时，称节点集V和边集E组成图G，记为G=(V,E)，关系R称为图G的路由矩阵。Floyd算法是一种用于计算图G中多源节点之间最短路径的算法，该算法使用大小均为n×n的距离矩阵和路由矩阵，距离矩阵记为W=[w_ij]_n×n，其中w_ij表示图G中v_i和v_j两点之间的路径长度。路由矩阵记为R=[r_ij]_n×n，其中r_ij表示v_i至v_j经过的转接点(中间节点)。Floyd算法的基本思想是首先写出初始的W矩阵和R矩阵，然后，按顺序依次将节点集中的各个节点作为中间节点，计算节点集中任意两个其它节点的径长，如果计算结果小于W矩阵中记录的径长，则更新W矩阵和R矩阵，如果计算结果大于或等于W矩阵中记录的径长则不变，以此不断更新W矩阵和R矩阵，直至W中的数值收敛，从最后得到的W和R中便可以找到任何节点间最短路径的径长和路由。

本文将三角网格中只参与构成一个三角形和未参与构成三角形的边定义为边界边，将三角网格中至少连接有一条边界边的顶点定义为边界点，多条边界边首尾相连构成了三维曲面的空洞。基于Floyd算法的空洞识别与修复过程如图 1所示。

图  1  基于Floyd算法的空洞识别流程图

Figure 1.  Flow chart of Floyd-based hole-recognition algorithm

由于边界点和边界边是空洞存在的必要非充分条件，因此，本文的空洞识别算法将边界点和边界边作为分析数据。如图 2(a)所示，点A₀₁为对三角网格进行遍历搜索过程中发现的一个未经处理的边界点，在树搜索算法中，首先，将点A₀₁作为树搜索的第0级节点并初始化距离矩阵W、路由矩阵R以及搜索点集P，图 3中的左侧为初始化数据，搜索点集P记录了搜索点在构成整个三维曲面的散点集中的编号(P的第一行数据)以及搜索点在树搜索过程中的搜索级别(P的第二行数据)；然后，采用迭代的方法获取与当前最高搜索级别中的所有节点直接相连的全部边界点作为下一搜索级节点。当下一搜索级中的节点数量为零或者当前搜索的空洞尺寸超过了空洞的最大修复尺寸或者下一搜索级节点中出现了与搜索点集P中重复的节点时，迭代结束。图 2中各边界点下角标的第一个数字表示该点的搜索级别，第二个数字表示该点在本搜索级别中的编号，点A₁₁和点A₁₂为与点A₀₁直接相连的边界点，该两个点即为第1搜索级中的节点。

图  2  空洞识别示意图

Figure 2.  Sketch map of hole-recognition

对于树搜索算法搜索到的边界点，如果该点不与搜索点集P中的点重复，则将W中该点到其它非直接相连点的距离设置为∞(无穷远)，该点到前一搜索级中直接相连节点的距离设置为该点的搜索级别；将该点与搜索点集P中每个点的路由关系存储到路由矩阵R中；将该点在三维曲面散点集中的编号以及搜索级别存储到搜索点集P中。图 2(a)中第1级搜索结束后对W、R和P的更新结果如图 3右侧数据所示。路由矩阵R中的非零数字表示其所在列的对应节点在P中的编号，例如，R(1,2)表示点A₁₁是P中保存的第2个点。

图  3  距离矩阵W、路由矩阵R以及搜索点集P更新过程

Figure 3.  Renewal process of distance matrix W,routing matrix R and search points set P

采用对边界边重新分配长度的方法构建了以处理点(图 2中的点A₀₁和点B₀₁)为中心的边界点拓扑结构，重新分配的边界边长度表征了边界点与处理点间的相关性强度，即，到处理点所经由的边界边数量越少的边界点与处理点的相关性越强，到处理点的距离也越近。

本文定义构成空洞的边界点中搜索级别最低的点为空洞端点。图 2(a)和图 2(b)的空洞端点分别为点A₀₁和点B₀₁，从图 2中可以看出，重复点与空洞端点之间有两条长度相等的最短路径，且这两条最短路径包含的边界边即为构成空洞的边集。因此，只需找到重复点对应的空洞端点，即可实现曲面空洞的有效识别。

(1)空洞端点到重复点有两条最短路径，重复点到空洞端点也有两条最短路径；

(2)在所有满足条件(a)的边界点中，空洞端点到重复点的距离最短；

(3)如果同时满足条件(a)和条件(b)的边界点不止一个，则任取其中之一即可。

在图 2(a)中，由W_FA和R_FA可以确定空洞端点为点A₀₁。最后，利用路由矩阵，将构成重复点到空洞端点的两条最短路径的边界边提取出来生成空洞边集。

如果空洞边集中边界边的数量为3，表明搜索到的并不是空洞而是一个孤立的三角形，对于这种情况，本文继续进行树搜索算法获取边界点；反之，则修复搜索到的空洞并重新搜索边界点。

本文定义空洞尺寸为构成空洞的边界边数量，由于三维激光扫描系统获取的点云密度相对均匀，因此，构成空洞的边界边数量越多，空洞的空间面积越大。本文通过设定空洞的最大修复尺寸来提高所提算法的灵活性并避免将三维曲面的轮廓判断为空洞，操作人员根据扫描对象的精度要求设定最大修复尺寸。

本文采用波前法^[15]对空洞进行修复，该方法将搜索到的空洞边集作为迭代计算的初始数据，在迭代过程中，首先，依次计算当前空洞边集中每两条相邻边界边的夹角并记录构成最小夹角的边界边；然后，连接构成最小夹角的两条边界边的非公共端点生成新的三角形以缩小空洞的尺寸；接下来，在空洞边集中，用新生成的边界边替换与其一起构成三角形的两条边界边，如果更新后的空洞边集中包含的边界边数量大于3，则重复上述过程继续进行迭代，反之，则将空洞边集中包含的这三条边界边构成三角形并结束迭代；最后，对构成空洞的所有边界点采用二面角最大化的三角网格优化准则^{[16, 17]}使修复后的空洞更加平滑。图 4为空洞修复示意图，图中点C、D、E、F和G构成了一个由五条边界边组成的空洞，在第一次迭代中，搜索到∠EFG为空洞的最小内角，连接点E和点G生成△EFG并用边EG替换空洞边集中的EF和FG，由于此时空洞边集中包含4条边界边，因此继续进行迭代；第二次迭代中，由于连接点C和点E后空洞边集中只剩下3条边界边，因此，迭代结束并生成△CDE和△CEG。

图  4  波前法空洞修复示意图

Figure 4.  Sketch map of hole-repairing with wave-front method

为了证明所提方法与其它方法相比具有更高的鲁棒性以及对复杂空洞具有更准确的识别能力，实验中对特殊形状的空洞进行了处理分析，图 5(a)为一个与孤立边相连的空洞，图 5(b)为文献^[12]的处理结果，由于文献^[12]将只属于一个三角形的边识别为空洞的边界边，而图 5(b)中虚线圈出的两条边不属于任何三角形，因此，文献^[12]无法对空洞进行有效识别，图 5(c)为文献^[13]的处理结果，文献^[13]首先将孤立边删除，然后对空洞进行修复，该方法虽然能够成功检测到空洞，但是删除了原始数据的一条边，破坏了数据的完整性。图 5(d)为本文所提方法的处理结果，从图中可以看出，本文所提方法不仅能够有效识别到空洞，而且不需要删除孤立边，保证了原始数据的完整性。

图  5  连接有孤立边的空洞处理结果

Figure 5.  Processing results of the hole with an isolated boundary

图 6(a)为两个相邻空洞的情况，由于文献^[13]通过对边界边进行依次搜索的方法来判断空洞的存在。该方法在识别相邻空洞时存在图 6(b)和图 6(c)两种情况的不唯一性，其中，图 6(b)能够成功的将两个空洞识别出来，而图 6(c)却将围成两个相邻空洞的边界边识别为一个大的空洞，图 6(c)中识别到的空洞的修复结果如图 6(d)所示，从图 6(d)中可以看出，两个相邻空洞的公共边(虚线内的边界边)并没有参与空洞修复而是成为了一条孤立边悬浮于曲面之外，显然，图 6(c)的空洞识别结果是不正确的，文献^[13]无法对两个相邻空洞的情况进行有效识别和修复。由于文献^[12]将只属于一个三角形的边识别为空洞的边界边，因此，文献^[12]也只识别到了一个大的空洞(修复结果如图 6(e)所示)。在本文所提方法中，由于采用树搜索算法对所有空洞进行并行搜索，可以有效识别出相邻的两个空洞，本文所提方法的空洞修复结果如图 6(f)所示。

图  6  两个相邻空洞处理结果

Figure 6.  Processing results of two adjacent holes

图 7(a)为由三维激光扫描仪生成的包含多个空洞的三维曲面，图 7(b)、图 7(c)和图 7(d)分别为文献^[12]、文献^[13]以及本文所提方法的修复结果。从图中可以看出，本文所提方法的修复效果明显优于文献^[12]和文献^[13]。构成图 7中4个曲面的边数量、三角形数量以及3种方法修复的空洞数量如表 1所示，与文献^[12]和文献^[13]相比，本文所提方法的空洞修复数量分别提高了54.1%和21.3%，同时，从表 1中可以看出，文献^[13]的修复曲面与本文所提方相比只少了4个三角形，但是构成曲面的边却减少了40条，进一步证明了文献^[13]由于删除曲面中的孤立边导致原始数据的完整性遭到破坏的问题。

图  7  空洞修复效果对比

Figure 7.  Comparison of the hole-repairing results

图 7(d)中空洞的最大修复尺寸为60，曲面的最大修复尺寸不仅能够有效界定三维曲面的外轮廓与空洞，而且，在实际应用中，操作人员可以通过改变最大修复尺寸来获取不同尺寸空洞在曲面中的统计分布，同时，并非所有空洞都是需要进行修复的，对于一些大尺寸的空洞，修复算法会带来较大误差，操作人员可以通过设定最大修复尺寸来屏蔽掉这些较大尺寸的空洞，而通过再次扫描的方式用真实数据来填充剩余空洞。

本文提出了一种三维曲面空洞的识别与修复方法，该方法将树搜索算法中的搜索级别作为边界边的长度，利用Floyd最短路径算法对存在的空洞进行识别，采用波前法修复发现的空洞。本文所提方法不仅能够识别出由只属于一个三角形的边界边围成的普通空洞，而且能够在保证原始数据完整性的前提下对连接有孤立边的空洞进行识别。对于两个空洞相邻的情况，传统方法会将其识别为一个大的空洞，而本文所提方法能够对其进行准确判断，与传统方法相比，空洞修复数量提高了21.3%以上。