一种结合平面投影和区域生长的曲面重建算法

冯 丹，苏铁明，华顺刚

(大连理工大学 机械工程学院，辽宁 大连 116024)

0 引言

逆向工程已被广泛应用于机械制造、文物保护、医疗与虚拟现实等多领域[1，2]。而三维点云曲面重建作为逆向工程的一部分，已经成为当今科研领域的研究热点。近些年，国内外学者提出了许多点云曲面重建的算法，主要包括四面体法、隐函数法、平面投影法、区域生长法。隐函数法是通过表面拟合的方法构造一个描述模型表面的隐函数，常用的有泊松算法[3]和径向基函数算法[4]，重建的曲面在细节特征处可能不够精确，如Edelsbrunner等[5]提出的四面体法是建立包围点集的立方体盒子，用空外接球法依次插入其他点，得到包含所有点集的凸多面体，该方法涉及到大量的计算，且需要后续算法对四面体进行提取。区域生长算法[6]是从种子三角形开始，按照某种原则不断地选择第三点和生长边组成新的三角形等，该方法重建精度良好，但重建结果依赖于第三点的筛选结果。平面投影法是将三维点云投影到二维平面内进行Delaunay三角剖分[7]，该方法重建速度快但会出现面片重叠以及形状失真的情况。

本文将平面投影法和区域生长法进行结合。首先需要估算每个点的法向量，之后根据平面投影法对每个点及k邻域进行投影和生成三角形操作，计算每个点的法向量与k邻域所有点法向量的夹角，若夹角都小于某阈值，将该点平面投影法生成的三角形存于确定三角形集合T1,否则存于待定三角形集合T2。对T1中的可生长边，在T2中找到满足要求的三角形，使其逐步生长成三角网。同时，为保证具有尖锐特征的曲面重建效果良好，使用面夹角准则对生长过程中的三角形进行判断调整。上述操作完成后，对仍剩余的点采用区域生长法进行生长重建。

1 法向量估算

本文采用最小二乘法计算法向量，遍历点云中的每个点，假设点p的k邻域可拟合成一平面，设平面方程为ax+by+cz+d=0，其中(a,b,c)为拟合平面的法向量。三维点的坐标为(xi,yi,zi)，可得到矩阵如下：

(1)

(2)

其中：N为点云的数目。

若点的σj大于C,则标记为1，若小于C标记为0。对标记为1的点，判断其k邻域点，若有超过k/2个点标记为1，则将此点与其邻域点均标记为2，在后续步骤，用来判断边是否需要生长。

2 点云重建

2.1 平面投影与生长步骤

利用上述方法估算出点云法向量后，根据平面投影法对每个点及k邻域点进行生成Delaunay三角形操作，保留每个与当前点相连的三角形。接下来需要对三角形分别进行存储，并进行生长操作。具体算法步骤如下：

(1)对任一点，计算其法向量与k邻域法向量的夹角，若夹角均小于35°，将这个点根据平面投影法生成的三角形存于确定三角形集合T1，否则，其生成的三角形存于待定三角形集合T2。其中，若点在计算法向量时被标记为1或2，其平面投影法得到的三角形也存于T2。

(2)在第(1)步中，为防止出现三角面片重叠现象，需要对加入T1的三角形按以下原则进行筛选：①三角形中不包含内点(包含此点的边均不为可生长边)；②三角形不包含不可生长边；③最小内角大于10°；④二面夹角大于50°。

(3)在T1中找到生长边，根据其在T2中满足要求的相邻三角形，对其向外生长生成三角形。在生长过程中，先寻找面夹角最大的三角形，若存在与最大面夹角相近的三角形，则选择边长更短的三角形。其中，若生长边两顶点均为在法向量估算时被标记为2，则此边不进行生长。

2.2 面夹角最大准则

因为三维点与二维点的不同，在使用平面投影法时，二维平面的三角形还原到三维空间存在不符合棱边结构的三角形，所以在上述第(3)步生长过程需要采用面夹角准则对三角形进行优化，让其可以与周围三角形组成棱边结构。当前边生长完成后，若调换以当前生长边为公共边的三角形合成的四边形的对角线后，生成的三角形与四边形边共边的三角形二面夹角更大，则选择调换对角线，形成新的三角形。

面夹角判断如图1所示，几个三角形形成棱边结构，当前生长边为AD，生长边所在的四边形为ABCD。若调换对角线AD，连接BC，相比于△ABD，△ABC与△ABE的面夹角更大。同样的，相比于△ADC，△ABC与△AFC面夹角也更大，且更符合棱边结构。则选择调换对角线AD，形成新的三角形△ABC和△BCD来代替原来的三角形。

图1 面夹角判断实例

2.3 剩余点的重建

上述操作结束后，仍剩余的点多数为奇异点情况，可分为相邻曲面以及薄壁特征，如图2所示。相邻曲面处会因为曲面距离过近出现面片重叠现象，而薄壁特征处曲率突然变化，细节处重建效果较差，薄壁特征周围往往伴随相邻曲面。

本文对剩余点采用区域生长法进行生长，每条生长边的候选点由边的两个顶点的k邻域点组成，可通过以下原则对点进行筛选：①最小内角最大；②二面夹角最大；③最大边长限制。同时因为相邻曲面距离太小，在对每个点选取k邻域时，会选到其他曲面的点，所以在区域生长筛选过程中，可以先将大多数属于其他曲面的点筛掉。

将生长边与候选点组成的三角形分为向内生长三角形与向外生长三角形，可以通过计算生长边所在三角形的法向量n与生长边与候选点组成的三角形之间的角度来判断。若角度小于90°，生成的三角形为向外生长；否则，为向内生长。

如图3所示，BC为生长边，D为候选点，需要计算△ABC的法向量n1与△BCD之间的角度，可以通过计算n1与△BCD的高(即向量ED)之间的夹角来获得。而对于如图2(a)所示的相邻曲面，其三角形生长情况如图4所示，△ABC为向内生长三角形，△ABD为向外生长三角形。把大部分可以形成向外生长三角形的候选点筛掉，可以防止选到其他曲面的点，生成错误的拓扑结构。

图2 奇异点情况

图3 向外、向内生长判别示例 图4 相邻曲面三角形生长情况

3 实验及结果分析

采用平面投影法和本文算法的cat重建如图5所示。由图5可以看出：与图5(a)相比，图5(b)中cat点云尾巴处重建效果良好,没有三角面片重叠。

图5 采用平面投影法和本文算法的cat重建

采用平面投影法和本文算法的part重建如图6所示。从图6可以看出：part点云在使用平面投影方法重建时有边缘凹陷现象，而使用本文算法重建的各个棱边结构明显，无错误连接。

图6 采用平面投影法和本文算法的part重建

采用本文算法重建的其他点云模型如图7所示。由图7可以看出，采用本文算法所重建的各点云模型效果良好。

图7 点云模型重建示例

4 结束语

(1)本算法结合了平面投影法与区域生长的优点，重建速度相比区域生长要快，而重建精度要比平面投影法高。

(2)在区域生长过程时使用面夹角准则，对于棱边、棱角等尖锐特征处，重建结果良好。