LabVIEW基于平面映射的散乱点云Delaunay三角剖分算法

散乱点云进行三角网格重建方法很多，基于种子三角形的扩张增进方法、Delauanay 三角剖分重建、隐式重建等，重建三角网格质量最高的是Delauany三角剖分方法，国内也有些学者研究这个方向，接下来介绍下该方法的具体LabVIEW实现。

Delauany Triangulation在两维平面内算法非常成熟（LabVIEW函数选中数学–>几何）中存在该函数。在三维显示选板中Scene Mesh也有这个属性，返回三角网格，但不要误解，只能返回2D的三角网格。

三维散乱点云如何进行Delauany三角剖分？既然在2D平面内如此的成熟，何不将三维点云映射到一个平面上，然后用2D的Delauany三角剖分方法进行重建，完成后反映射回三维散乱点云。注意解决问题的思路。基于该思路需要掌握几个算法。

1. 基于种子点周围一坨点的整体法向

2. 基于种子点和平面法向建立的平面，平面外点的投影坐标计算

3. 计算的平面法向与Z轴的夹角，并计算旋转矩阵，将投影后的坐标旋转到Z平面，这样才能够利用XY坐标，将3维问题转为2维问题解决。

拿一片散乱点云来举例说明，入下图所示：

1. 基于种子点周围一坨点的整体法向

估算一片点云的整体法向，通常采用协方差矩阵来计算，其原理如下：协方差矩阵总是指向数据方差最大的方向。

更准确的说，第一特征向量是数据方差做大的方向，第二特征向量是与第一特征向量垂直方向上数据方差最大的方向，第三特征向量是与第一和第二特征向量垂直的方向上方差最大的方向。

1. 平面外点在平面内的投影

1. 向量夹角计算

设两个向量分别为a=（x1，y1）,b=(x2,y2)，其夹角为α，因为ab=|a||b|cosα，所以cosα=ab/|a||b|=（x1y1+x2,y2）/(根号（x1^2+y1^2）根号（x2^2+y1^2）)。

1. 向量绕任意轴旋转固定角度产生旋转矩阵

具体LabVIEW实现如下：

以上将算法原理详细介绍了，实验结果如下：

原始点云基于种子点和整体法向投影到平面内的效果图

与坐标轴有夹角，没法直接用XY坐标进行2D Delauany三角剖分，需要将平面旋转到平行于Z平面。根据该平面的法向与Z轴的夹角，根据上述方法计算法向绕任意轴旋转角度计算旋转矩阵的方法，获取旋转矩阵，然后对该平面进行旋转计算。效果如下：

旋转计算后，即可使用XY坐标用2DDelauany Triangulation函数进行计算，其2D效果如下：

重建后反映射回原始散乱点云得到的重建效果如下，重建质量非常高。

当然在这里只是核心的几个算法作了详细解释，在实际应用中比如一个完整的三维点云，需要分块进行剖分，分块依据就是根据点云法向的夹角大小，把法向小于一定角度阈值的点划为一坨，利用上述方法进行剖分，一个完整的点云模型可能有很多坨点云，最后进行坨与坨之间的融合，删除重复三角面片等，由于2DDelauany Triangulation算法是对凸包进行计算，在实际应用中会有些异常三角形出现，由于点云的密度基本是一致的，可以用三角形的边长限制原则，对得到的三角形进行过滤，去除掉不合理的三角网格。