無序點雲的快速三角化
本小節描述了怎樣使用貪婪投影三角化算法對有向點雲進行三角化，具體方法是先将有向點雲投影到某一局部二維坐标平面内，再在坐标平面内進行平面内的三角化，再根據平面内三位點的拓撲連接配接關系獲得一個三角網格曲面模型。
貪婪投影三角化算法原理是處理一系列可以使網格“生長擴大”的點（邊緣點），延伸這些點直到所有符合幾何正确性和拓撲正确性的點都被連上。該算法的優點是可以處理來自一個或者多個掃描器掃描得到并且有多個連接配接處的散亂點雲。但該算法也有一定的局限性，它更适用于采樣點雲來自于表面連續光滑的曲面并且點雲密度變化比較均勻的情況。
該算法的三角化過程是局部進行的，首先沿着一點的法線将該點投影到局部二維坐标平面内并連接配接其他懸空點，然後在進行下一點。是以這裡我們設定如下參數：
1）函數SetMaximumNearestNeighbors(unsigned)和SetMu(double)，這兩個函數的作用是控制搜尋鄰域大小。前者定義了可搜尋的鄰域個數，後者規定了被樣本點搜尋其鄰近點的最遠距離，（是為了适應點雲密度的變化），特征值一般是50-100和2.5-3（或者1.5每栅格）。
2）函數SetSearchRadius(double)，該函數設定了三角化後得到的每個三角形的最大可能邊長。
3）函數SetMinimumAngle(double)和SetMaximumAngle(double)，這兩個函數是三角化後每個三角形的最大角和最小角。兩者至少要符合一個。典型值分别是10和120度（弧度）。
4）函數SetMaximumSurfaceAgle(double)和SetNormalConsistency(bool)，這兩個函數是為了處理邊緣或者角很尖銳以及一個表面的兩邊非常靠近的情況。為了處理這些特殊情況，函數SetMaximumSurfaceAgle(double)規定如果某點法線方向的偏離超過指定角度（注：大多數表面法線估計方法可以估計出連續變化的表面法線方向，即使在尖銳的邊緣條件下），該點就不連接配接到樣本點上。該角度是通過計算法向線段（忽略法線方向）之間的角度。函數SetNormalConsistency(bool)保證法線朝向，如果法線方向一緻性辨別沒有設定，就不能保證估計出的法線都可以始終朝向一緻。第一個函數特征值為45度（弧度）、第二個函數預設值為false。
本小節我們一起學習用貪婪投影三角化算法對有向點雲進行三角化的例子。
代碼
首先，在PCL（Point Cloud Learning）中國協助發行的書[1]提供CD光牒的第15章例3檔案夾中，打開名為greedy_projection.cpp的代碼檔案，同檔案夾下可以找到相關的測試點雲檔案table_scene_lms400_downsampled.pcd。
解釋說明
下面對打開的檔案關鍵語句進行解析。
#include //PCL中所有點類型定義的頭檔案
#include //打開關閉pcd檔案的類定義的頭檔案
#include //kdtree搜尋對象的類定義的頭檔案
#include //法向量特征估計相關類定義的頭檔案
#include //貪婪投影三角化算法類定義的頭檔案
以上代碼是與本程式相關的類和函數的頭檔案聲明。
//将一個xyz點類型的pcd檔案打開并存儲到對象PointCloud中
pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>);//定義點雲對象指針
sensor_msgs::PointCloud2 cloud_blob;
pcl::io::loadPCDFile ("table_scene_lms400_downsampled.pcd", cloud_blob);//加載bun0.pcd檔案
pcl::fromROSMsg (cloud_blob, *cloud); //*資料最終存儲在cloud中
由于例子中用到的pcd檔案隻有XYZ坐标，是以我們把它加載到對象PointCloud< PointXYZ>中，上面代碼打開pcd檔案，并将點雲存儲到cloud指針對象中。
pcl::NormalEstimation<pcl::PointXYZ, pcl::Normal> n;//法線估計對象
pcl::PointCloud<pcl::Normal>::Ptr normals (new pcl::PointCloud<pcl::Normal>);//存儲估計的法線
pcl::search::KdTree<pcl::PointXYZ>::Ptr tree (new pcl::search::KdTree<pcl::PointXYZ>);//定義kd樹指針
tree->setInputCloud (cloud); //用cloud建構tree對象
n.setInputCloud (cloud); //為法線估計對象設定輸入點雲
n.setSearchMethod (tree); //設定搜尋方法
n.setKSearch (20); //設定k搜尋的k值為20
n.compute (*normals); //估計法線存儲結果到normals中
由于本例中使用的三角化算法輸入必須為有向點雲，是以需要使用PCL中的法線估計方法預先估計出資料中每個點的法線，上面的代碼就完成該預處理。
pcl::PointCloud<pcl::PointNormal>::Ptr cloud_with_normals (newpcl::PointCloud<pcl::PointNormal>);
pcl::concatenateFields (*cloud, *normals, *cloud_with_normals);//連接配接字段，cloud_with_normals存儲有向點雲
由于XYZ坐标字段和法線字段需要在相同PointCloud對象中，是以建立一個新的PointNormal類型的點雲來存儲坐标字段和法線連接配接後的點雲。
pcl::search::KdTree<pcl::PointNormal>::Ptr tree2 (newpcl::search::KdTree<pcl::PointNormal>);
//定義搜尋樹對象
tree2->setInputCloud (cloud_with_normals); //利用點雲建構搜尋樹
pcl::GreedyProjectionTriangulation<pcl::PointNormal> gp3;//定義三角化對象
pcl::PolygonMesh triangles; //存儲最終三角化的網格模型
以上代碼是對三角化對象相關變量進行定義。
gp3.setSearchRadius (0.025);//設定連接配接點之間的最大距離（即為三角形最大邊長）為0.025
//設定各參數特征值，詳見本小節前部分對參數設定的描述
gp3.setMu (2.5);//設定被樣本點搜尋其鄰近點的最遠距離為2.5，為了适應點雲密度的變化
gp3.setMaximumNearestNeighbors (100); //設定樣本點可搜尋的鄰域個數為100
gp3.setMaximumSurfaceAngle(M_PI/4); //設定某點法線方向偏離樣本點法線方向的最大角度為45度
gp3.setMinimumAngle(M_PI/18); //設定三角化後得到三角形内角最小角度為10度
gp3.setMaximumAngle(2*M_PI/3); //設定三角化後得到三角形内角最大角度為120度
gp3.setNormalConsistency(false); //設定該參數保證法線朝向一緻
gp3.setInputCloud (cloud_with_normals);//設定輸入點雲為有向點雲cloud_with_normals
gp3.setSearchMethod (tree2); //設定搜尋方式為tree2
gp3.reconstruct (triangles); //重建提取三角化
以上代碼設定參數特征值和實際三角化的過程。
//附加頂點資訊
std::vector<int> parts = gp3.getPartIDs();
std::vector<int> states = gp3.getPointStates();
對每個點來說，ID字段中中含有連接配接元件和該點本身的“狀态”(例如 gp3.FREE, gp3.BOUNDARY或gp3.COMPLETED)可以被檢索到。
編譯并運作該程式
利用CD光牒提供的CMakeLists.txt檔案，在cmake中建立工程檔案，并生成相應的可執行檔案。生成執行檔案後，就可以運作了，在cmd中鍵入指令：
...>greedy_projection.exe
運作之後在三維可視化視窗可看到三角化重建後的曲面模型，如圖2所示，對比重建前的點雲與重建後的曲面模型，由于點雲中有離群點是以重建結果在空間也有三角化的碎片，其他的部分重建效果一般，與點雲本身密度和平滑程度有關，讀者可以自行試驗不同的處理後的點雲，觀察重建效果。
儲存并觀察結果
存儲成VTK檔案，可以作為網格模型做後續處理。
#include
...
saveVTKFile ("mesh.vtk", triangles);
圖1 貪婪三角化之前點雲
圖2 貪婪三角化之後曲面模型
敬請關注PCL（Point Cloud Learning）中國更多的點雲庫PCL（Point Cloud Library）相關官方教程。