一、概述

贪婪投影算法（Greedy Projection Algorithm）是M. Gopi等人[1]于2003年提出的点云表面重建算法。该算法从一个数据点R开始，找到与R相邻的一组数据点，连接R与，就可得到数据点R的所有邻接三角形（顶点中包含R的三角形）。然后以广度优先搜索的形式，遍历中的数据点，找到这些数据点的邻接三角形，直到遍历完所有数据点。该算法的重点在于如何连接数据点R和以生成高质量三角形（避免小角度），并保证三角形不会交叠。算法通过投影的方式，将三维数据点投影至二维，在二维平面内连接数据点，以获取不交叠三角形；通过贪婪的方式，当有多个数据点可连成三角形时，尽可能生成角度大的三角形。

二、算法流程

1 获取数据点R的相邻点集

论文通过以下2个步骤确定相邻点集。首先以R为中心，长为的正方体初步筛选相邻数据点。其中为用户定义的常量，表示相邻区域的范围；m为R与最近点的距离。然后计算数据点到R的距离，准确筛选出半径以内的数据点。

而在PCL中，是通过设置常量(mu_)，搜索半径(search_radius_)，最大搜索数目(nnn_)来确定相邻数据点。首先搜索最近的nnn_个数据点，然后选出距离小于和search_radius_的数据点作为。

2 投影R和至二维平面

对于一个光滑表面，当数据点R所在的局部区域无限小时，该区域接近于曲面在数据点R处的切平面，因此在这局部区域三维数据点连线问题可以简化至二维平面。我们可以沿着数据点R的法向量进行投影，R的投影R_为投影平面的坐标原点，的投影结果定义为。

3 按角度排序

投影点与坐标原点R_可连成向量，根据这些向量到X轴的角度排序。按照该排序依次连接中的数据点就可以形成不交叠的三角形。但是中可能有部分点已经生成过三角形，增加的三角形可能与原有三角形交叠，所以要删除部分数据点以避免与原三角形交叠。另外，当有多个数据点可以连接时，如何形成最优三角形也需要探讨。

4 根据可见度删除数据点(Pruning by Visibility)

论文通过以下3个步骤删除中会产生交叠三角形的数据点（如图1中R与数据点V的连线会与已有三角形相交，应删除数据点V）。

边界边：仅与单个三角形连接的边。

（1）删除数据点R的边界边之间的数据点。定义数据点R的边界边之间区域为R的不可见区域，如图1黑色点，当R与这些黑色点相连时会与现有三角形交叠，所以应删除这些黑色点。

（2）若数据点的不可见区域中包括R，这些数据点也应删除。如图1红色的V点，R点在V点边界边之间。

（3）删除会被已有网格阻挡的数据点（主要探讨没有连线的自由点），如图1白色点W。该过程要求遍历所有边，以判断这些边是否与线段R-W相交。论文推导了一个定理来简化这一判断过程：只需判断中数据点的边界边是否与线段R-W相交即可，而不用遍历所有边。

5 根据角度删除数据点（Pruning by Angle Criterion）

根据可见度删除数据点后，依次连接相邻点就可形成不交叠的三角形，如图3（a）依次连接，，，，，。但是这样很容易形成这样的小角度三角形。最好的方式是直接连接和形成大角度三角形，但这样点和就在三角形内部了，这是不允许的。为此论文提出了如下方法来寻找所有可与线段RP连成三角形的数据点。其中，按到R的距离从小到大排列相邻点，；按角度排列相邻点。

使用图2伪代码后，，，可与线段RP连成三角形，根据贪婪算法要求，连接P和形成最大角度。随后寻找可与线段连成三角形的数据点，仅有符合要求，故连接和。

6 三角化

依次连接剩下的数据点就可连成三角形。若相邻数据点的角度过大（如大于120°），则不连成三角形，算法认为这是模型的孔洞。

三、参考文献

[1] M. Gopi, S. Krishnan. A Fast and Efficient Projection Based Approach for Surface Reconstruction. Brazilian Symposium on Computer Graphics & Image Processing. 2003, 179-186