基于三维散乱点云的三角网格重构关键技术

文/曹金俐

基于三维散乱点云的三角网格重构关键技术

文/曹金俐

本文分析了多约束下三维网格的重构方法，同时提出三维散乱点云三角网格构造，以期给相关研究提供参考。

三维散乱点云 三角网格 重构技术

1 前言

伴随计算机的技术飞速发展，CAD/CAM的技术逐渐变成相关设计人员的研究工具，尤其三维造型的技术广泛应用于制造业中自动化的加工制造、产品设计与模具设计方面。通常传统CAD/CAM的工作流程为：按照工程设计师图纸或是构思，通过CAD/CAM的软件来设计产品三维的模型，再实施必要模型的修改，然后生成相应模型数控的代码，进而完成最终的产品加工。

2 多约束下三维网格的重构方法

2.1 三角网格的三维重构算法探究现状

各种形式网格重构可以适应不同类型点云的数据，而本文研究的对象散乱点云数据。散乱点云网格重构研究包含2个方向：其一，投影方式；其二，在三维的空间中实施构造。因为在二维空间中点云的三角化算法相对成熟与稳定，其应用时间较长，所以经常会在二维域内投影三维数据，并在新平面上实施投影点三角化以后，将三角化以后所获得三角网格可以反投至3D空间中。因为相较于2D平面而言，空间中领域点和数据点间关系可以如实的反映，以便在3D的空间中反射出平面的三角网格，并且不会出现畸变的三角形，也不会发生重叠的情况。

2.2 Delaunay的三角剖分计算方法

关于Delaunay的三角剖分计算方法主要是在Voronoi基础上所获得，主要方法为对点集中，探索各个方向K的领域，寻找相应的临近点，同时通过Voronoi的原理图来实现三角化。假如三维空间之中存在某个点集X等于{X1，X2•••XN}，对点集D之中相邻的X1与X2进行连接，然后求解各连线中垂线，然后得出多边形的网格图。

2.3 区域的扩张法

常见经点云数据在三维空间之中三角化的方法为区域的扩张法，这种方法途径就是经初始的边或是三角形开始，根据设定检测的过滤规则，选择匹配点以构成三角片，继而实现网格模型构建。而区域扩张方法过程如下：其一，对某个已知散乱的点云集R，构建种子的三角形 i0，把其置于三角形的集合Ui等于{i0}中，在集合队列中，仅有一个初始三角形的元素 i0；其二，对于集合的队列Ui等于{i0，i1，…，in}之中已经构建含边界边每个三角片/ik，然后在集合的队列Ui等于{i0，i1，…in}寻找和次边界边边相互对应最优的活跃点O，然后生成新三角片in，同时加入到Ui等于{i0，i1，…in}的队列之中；其三，对R中点状态与Ui之中相邻关系进行更新，再不断地迭代，一直到结束三角化的过程。

3 三维散乱点云三角网格构造

同城区域增长的方法就是把三个邻近的点构建种子三角形当作网格的重建基础，根据最优匹配点选取原则进行不断地的扩展，构成新三角形，一直到结束网格重构。

3.1 构建初始的三角形

选择点云的链表之中首个点作初始的顶点，应用栅格方法来寻找与初始点相距较近的点当做第2个顶点。连接两个点构成三角形第一条边，在第二顶点与第一顶点邻域中选择与第一条边两个端点相距比较近的点当做第三个顶点。

3.2 活跃边检测

在进行检测边扩张性的时候，第一步需要对边队列之中e有没有内边进行判断，对e是不是内边进行检测时，采取的一种简单方式就是检测边e两个端点，把ej内邻接列表，若ei（ej）内邻接点的链表之中存在ej（ei），证明e是内边，从活跃边的队列中除去，若e不为内边，需要相应属性与条件use小于2相符合，然后匹配生成新三角形。

3.3 最优的匹配点选择

在重建三角网格的模型时，最佳的匹配点能够合理的选择，会导致网格模型生成质量受到直接影响。因此，为提升运算的效率与避免全局的搜索，需要按照以下原则进行选择。

3.3.1 二面角的准则

为保证所生成网格的光滑性，当前边和备选点构成三角形，需要和三角形平面构成二面角，并且需要处在合适的阈值内，将与上述条件相符点添到最佳的候选点列表之中。

3.3.2 K-邻近的搜索准则

在选择最佳的匹配点时，需要确保改点和前边生成新三角形可以将形体拓扑信息充分反映出来。为缩小最佳的匹配点搜索的范围，余搜索边e最佳的匹配点能够搜索边e邻近的区域，应用栅格方法来查出两个端点，确保点可领域可以有较好的连续性。

3.3.3 已用点的优先准则

在进行网格扩张生成时，若生成新边过多，容易导致扩张效率受到影响。因此，在对e最佳的匹配点进行确定时，需要优先考虑网格模型之中已用点。在对某个点是否是已用点进行判断时，可以应用点与附近点空间几何的相对位置进行排查，搜索该店邻接点的列表，若列表是空，表示为外点，不然表示改点是已用点。如果边e邻近的区域中已用点中缺乏满足最佳的匹配点选择要求，需要从未使用点钟选取与条件相符的点实施网格扩张，具体从图1中可以看出。

图1：已用点优先的使用图

4 结语

总之，伴随计算机飞速发展，各种逆向工程的技术渐渐变成人们的研究重点，现阶段，虽然精确、快速获取物体表面点云模型比较容易。然而，在物体表面的信息数据之中，冗余点含量比较大，因此，需要借助三维散乱的点云三角网格的重构技术，以便建立数据点拓扑关系，进而明确各个点的作用。

[1]段黎明,王浩宇,刘莹.基于工业CT图像重构的网格模型的全局优化方法[J].强激光与粒子束,2015,27(12):173-177.

[2]邸维巍,张旭东,胡良梅.基于可信度的TOF相机三维点云球覆盖网格重建[J].合肥工业大学学报（自然科学版）,2014,23(12):1451-1455.

[3]秦绪佳,陈楼衡,谭小俊.结构光视觉三维点云逐层三角网格化算法[J].计算机科学,2016,43(z2):383-387,410.

作者单位武汉地震科学仪器研究院有限公司 湖北省武汉市 437100