從零開始一起學習SLAM | 點雲到網格的進化
點擊公眾號「計算機視覺life」關注，置頂星標更快接收消息！
本文編程練習框架及數據獲取方法見文末獲取方式菜單欄點擊「知識星球」查看「從零開始學習SLAM」一起學習交流
小白：師兄，師兄，你在《從零開始一起學習SLAM | 給點雲加個濾網》、《從零開始一起學習SLAM | 點雲平滑法線估計》中都提到了點雲網格化，這個聽起來高大上，不過到底是什麼意思呢？
師兄：別急，是這樣的：你看我們之前處理的都是一個個點，不管是濾波還是平滑，我們都是對一個個離散的空間點進行的處理，雖然你遠看能看出物體的輪廓，但是拉近了看是一個個分散的空間點，是吧？
小白：是啊，這樣不算是3D模型吧
師兄：嗯，這樣的結果解析度比較低，也沒辦法進行三維列印，點雲網格化就是用點雲生成網格，最後得到的是一個連續（相對於前面的離散點）的表面。如果再加上紋理貼圖，就能得到和真實物體一樣的三維模型了
什麼是網格？
小白：師兄，你說了很多次網格，其實我還不知道網格到底是啥？
師兄：哦，忘記說這個最基本的概念了。網格主要用於計算機圖形學中，有三角、四角網格等很多種。下面左圖就是四角網格，右圖是三角網格
不過，計算機圖形學中的網格處理絕大部分都是基於三角網格的，三角網格在圖形學和三維建模中使用的非常廣泛，用來模擬複雜物體的表面，如建築、車輛、動物等，你看下圖中的兔子、球等模型都是基於三角網格的
小白：仔細看了下還真是，為啥一般用三角網格啊？是因為三角形的穩定性嗎？（滑稽）
師兄：還真是一個原因。三角形表示網格也叫三角剖分。它有如下幾個優點：
1、正如你所說的，穩定性強。
2、三角網格比較簡單（主要原因），實際上三角網格是最簡單的網格類型之一，可以非常方便並且快速生成，在非結構化網格中最常見。而且相對於一般多邊形網格，許多操作對三角網格更容易。
3、有助於恢復模型的表面細節。
小白：原來如此。三角網格在空間中如何表示呢？
師兄：實際應用中出現的三角網格，每個三角形都和其他三角形共享邊。所以三角網格需要存儲三類信息：
- 頂點。每個三角形都有三個頂點，各頂點都有可能和其他三角形共享。
- 邊。連接兩個頂點的邊，每個三角形有三條邊。
- 面。每個三角形對應一個面，我們可以用頂點或邊列表表示面。
網格生成演算法有什麼要求？
小白：那這個點雲網格化一般怎麼做呢？
師兄：點雲網格化一般輸入就是點雲啦，輸出就是三維網格啦，不過輸入的點雲一般面臨幾個問題，我們前面也提到過：
1、點雲雜訊。 每個點雲都會帶有雜訊，雜訊有可能和物體表面光學性質、物體深度、感測器性能等都有關係。
2、點雲匹配誤差。三維重建中需要將不同幀得到的點雲估計其在世界坐標系下的位姿，會引入一定的位置誤差。
3、點雲分佈。分佈的不均勻性體現在兩個方面。一個是每個點雲在不同的方向上分佈是不均勻的另一個是不同的點雲匹配後，不同位置的點雲密度是不一樣的。
4、缺失數據。 掃描中如果碰到不易成像的部位（比如不可見、反光等等），那麼這部分的數據是缺失的，點雲是不完整的。
小白：點雲有這麼多問題，網格化演算法肯定要求比較高了？
師兄：是的，想要生成漂亮的網格，除了網格密度和精度外，我們還希望網格生成演算法有如下的能力：
1、對點雲雜訊有一定的冗餘度。
2、能夠重建出曲率變化比較大的曲面。
3、能夠處理大數據量，演算法時間和空間複雜度不會太高。
4、重建出的網格中包含儘可能少的異常三角片，比如三角片交錯在一起、表面法向量不連續或不一致、同一個位置附近出現多層三角片等。
小白：感覺要求挺高的，那我們一般用什麼演算法呢？
師兄：目前點雲進行網格生成一般分為兩大類方法：
1、 插值法。顧名思義，也就是重建的曲面都是通過原始的數據點得到的
2、逼近法。用分片線性曲面或其他曲面來逼近原始數據點，得到的重建曲面是原始點集的一個逼近。
點雲貪心三角化原理
師兄：我們主要介紹一種比較簡單的貪心三角化法（對應的類名：pcl::GreedyProjectionTriangulation），也就是使用貪心投影三角化演算法對有向點雲進行三角化。
小白：為啥介紹這個，有啥特點？
師兄：該演算法的優點是可以用來處理來自一個或者多個設備掃描到得到、並且有多個連接處的散亂點雲。但是也是有很大的侷限性，它更適用於採樣點雲來自表面連續光滑的曲面，並且點雲的密度變化比較均勻的情況
小白：這樣啊，難怪之前師兄要講點雲濾波和平滑呢，原來都是鋪墊啊
師兄：哈哈，是的。
小白：那這個貪心三角化法到底是什麼原理呢？
師兄：貪心投影三角化的大致流程是這樣的：
（1）先將點雲通過法線投影到某一二維坐標平面內
（2）然後對投影得到的點雲做平面內的三角化，從而得到各點的拓撲連接關係。平面三角化的過程中用到了基於Delaunay三角剖分 的空間區域增長演算法
（3）最後根據平面內投影點的拓撲連接關係確定各原始三維點間的拓撲連接，所得三角網格即為重建得到的曲面模型
Delaunay 三角剖分簡介
小白：師兄，這個Delaunay是啥？
師兄：先說說點集的三角剖分（Triangulation）吧，對數值分析以及圖形學來說，三角剖分都是極為重要的一項預處理技術。而Delaunay 三角剖分是一種常用的三角剖分的方法，這個方法比較常見，關於點集的很多種幾何圖都和Delaunay三角剖分相關，如Voronoi圖，當然這些很複雜了。我們這裡只是簡單介紹一下Delaunay 三角剖分，不然估計你要頭大了。
小白：師兄，你一連說了幾個我從來沒聽過的術語，我已經頭大了。。
師兄：哈哈，那打住，只簡單提一下Delaunay 三角剖分。你看下面這個圖，左側就是不滿足Delaunay 三角剖分，右側是Delaunay 三角剖分的結果。
小白：看起來右邊的圖好像很規則啊
師兄：的確，Delaunay 三角剖分的有兩個優點：
1.最大化最小角，「最接近於規則化的「的三角網。
2.唯一性（任意四點不能共圓）。
我們來看一下它的定義，有點拗口：點集??的Delaunay三角剖分滿足滿足任 意??內任意一個點都不在?? 內任意一 個三角面片的外接圓內。
小白：師兄，這個定義每個字我都認識，但是連起來不知道啥意思啊！（捂臉）
師兄：沒關係，確實很拗口，就是定義了一種三角化時三角形必須滿足上述條件，我們就叫它為Delaunay條件吧。你看下面的圖就是滿足了Delaunay條件，所有三角形的頂點是不是都不在其他三角形的外接圓內？
小白：我看看，（幾分鐘過去了。。）師兄，確實是這樣，不過這個也太費眼了吧，每次都還要畫外接圓出來。。
師兄：實際上當然不能這樣判定了，有更簡便的方法。你看下面最左圖，觀察具有公共邊緣BD的兩個三角形ABD和BCD，如果角度α和γ之和小於或等於180°，則三角形滿足Delaunay條件。按照這個標準下圖左、中都不滿足Delaunay條件，只有右圖滿足。
小白：這樣是簡單多了，起碼不用畫外接圓了
師兄：嗯，Delaunay 三角剖分就說這麼多（再多估計不知道了）。我們繼續前面。剛才說到的貪心投影三角化方法第2步就是利用Delaunay 三角剖分，它通過選取一個樣本三角片作為初始曲面，不斷擴張延伸曲面的邊界，直到所有符合幾何正確性和拓撲正確性的點都被連上，最後形成一張完整的三角網格曲面。
小白：聽起來有點複雜啊
師兄：沒關係，前面說的瞭解一下就行。現階段我們主要是「掉包俠」，因為PCL都幫我們封裝好了，以後研究深入了再回頭去看吧。
小白：好，那師兄快教我寫代碼吧！
貪心投影三角化實踐
師兄：貪心投影三角化方法屬於速度比較快的，而且比較簡單，主要代碼都在這裡啦，還給你加了注釋，你有了前面的基礎，結合PCL官網函數，應該能看懂的~
// 將點雲位姿、顏色、法線信息連接到一起
pcl::PointCloud<pcl::PointNormal>::Ptr cloud_with_normals(new pcl::PointCloud<pcl::PointNormal>);
pcl::concatenateFields(*cloud_smoothed, *normals, *cloud_with_normals);
//定義搜索樹對象
pcl::search::KdTree<pcl::PointNormal>::Ptr tree2(new pcl::search::KdTree<pcl::PointNormal>);
tree2->setInputCloud(cloud_with_normals);
// 三角化
pcl::GreedyProjectionTriangulation<pcl::PointNormal> gp3; // 定義三角化對象
pcl::PolygonMesh triangles; //存儲最終三角化的網路模型
// 設置三角化參數
gp3.setSearchRadius(0.1); //設置搜索時的半徑，也就是KNN的球半徑
gp3.setMu (2.5); //設置樣本點搜索其近鄰點的最遠距離為2.5倍（典型值2.5-3），這樣使得演算法自適應點雲密度的變化
gp3.setMaximumNearestNeighbors (100); //設置樣本點最多可搜索的鄰域個數，典型值是50-100
gp3.setMinimumAngle(M_PI/18); // 設置三角化後得到的三角形內角的最小的角度為10°
gp3.setMaximumAngle(2*M_PI/3); // 設置三角化後得到的三角形內角的最大角度為120°
gp3.setMaximumSurfaceAngle(M_PI/4); // 設置某點法線方向偏離樣本點法線的最大角度45°，如果超過，連接時不考慮該點
gp3.setNormalConsistency(false); //設置該參數為true保證法線朝向一致，設置為false的話不會進行法線一致性檢查
gp3.setInputCloud (cloud_with_normals); //設置輸入點雲為有向點雲
gp3.setSearchMethod (tree2); //設置搜索方式
gp3.reconstruct (triangles); //重建提取三角化
可以左右拖動哦
小白：雖然代碼注釋了，但還有疑問，setMaximumSurfaceAgle和setNormalConsistency到底是幹嘛的？
師兄：setMaximumSurfaceAgle和setNormalConsistency 其實是用於處理有尖銳邊緣或稜角的情況，以及表面的兩面非常接近的情況。比如setMaximumSurfaceAgle，表示如果某點的法線偏離了參考點超過了指定的角度（典型為45°），那麼它們就不會與當前點連接。
setNormalConsistency 的話，注釋裏也說了，是保證法線朝向一致。因為大多數表面法線估計方法得到的法線，即使是在銳利的邊緣之間也是平滑的過渡。因為不是所有的法線估計方法都能保證法線的方向一致。通常情況下，設置為false對大多數數據集有效。
小白：嗯嗯，我好好理解一下。
師兄：好了，今天就這樣吧，留個編程練習給你吧
註：本文參考了PCL官網。
編程練習
給定輸入點雲，結合之前的內容對點雲進行濾波、平滑，並計演算法線，最後用貪心投影三角化方法進行網格化，顯示出網格化結果。
如果代碼正確，網格化結果大概如下所示。嘗試調整一下參數，看看有什麼變化。可以試試泊松重建方法，看看有什麼不同。
提示：公眾號後臺回復「網格」可以獲得代碼框架和待處理點雲。
歡迎留言討論，更多學習視頻、文檔資料、參考答案等關注計算機視覺life公眾號，，菜單欄點擊「知識星球」查看「從零開始學習SLAM」星球介紹，快來和其他小夥伴一起學習交流~
推薦閱讀
從零開始一起學習SLAM | 為什麼要學SLAM？
從零開始一起學習SLAM | 學習SLAM到底需要學什麼？從零開始一起學習SLAM | SLAM有什麼用？從零開始一起學習SLAM | C++新特性要不要學？從零開始一起學習SLAM | 為什麼要用齊次坐標？從零開始一起學習SLAM | 三維空間剛體的旋轉
從零開始一起學習SLAM | 為啥需要李羣與李代數？從零開始一起學習SLAM | 相機成像模型從零開始一起學習SLAM | 不推公式，如何真正理解對極約束?從零開始一起學習SLAM | 神奇的單應矩陣從零開始一起學習SLAM | 你好，點雲從零開始一起學習SLAM | 給點雲加個濾網從零開始一起學習SLAM | 點雲平滑法線估計零基礎小白，如何入門計算機視覺？SLAM領域牛人、牛實驗室、牛研究成果梳理我用MATLAB擼了一個2D LiDAR SLAM可視化理解四元數，願你不再掉頭髮最近一年語義SLAM有哪些代表性工作？視覺SLAM技術綜述推薦閱讀：
