基于樣點拓撲近鄰的散亂點云曲面拓撲重建

史 陽，孫殿柱，李延瑞，劉 健

（山東理工大學機械工程學院，山東淄博255091）

散亂點云曲面拓撲重建主要用于解決實物表面樣點鄰接關系的復原問題，輸出結果體現為二維可定向流形結構的多邊形網格曲面［1－4]，是逆向工程中實現曲面重建及創新設計的重要基礎．高質量的曲面拓撲重建對提高曲面重建精度具有重要意義．

目前，散亂點云曲面拓撲重建的主流算法可歸納為三類——場函數算法［4－7]、網格增量構造算法［1－3，8－10]和Voronoi過濾算法［11－15]．場函數法通過為散亂點云構建標量場，采用等值面提取算法獲得曲面拓撲網格，該類算法重建的網格為非插值網格，重建精度不高．網格增量構造算法通常從任一樣點開始，在點云中選取匹配點［2]以完成初始網格的構造，然后將當前的網格邊界向其鄰域樣點擴展形成新的網格邊界，重復此過程直至所有樣點成為曲面拓撲網格頂點，該類算法效率較高，但對于r－dense恰當采樣點云［16]中非均勻區域和曲率變化大的多輪廓點云，基于幾何鄰域獲取的匹配點進行拓撲重建常產生非工藝孔洞和多余面片．Voronoi過濾算法基于散亂點云的Voronoi圖進行Delaunay全局剖分，利用局部二維流形與中軸約束條件從Delaunay三角剖分結果中提取曲面拓撲網格，該類算法需要生成整個散亂點云的Voronoi圖，時間復雜度高，且不能有效重建模型邊界．

本文提出一種基于樣點拓撲近鄰的散亂點云曲面拓撲重建算法，以期有效解決r－dense恰當采樣點云中非均勻區域易產生非工藝孔洞的問題．

1 樣點拓撲近鄰查詢

與樣點Voronoi單元相鄰的單元所對應的中心點即為樣點的拓撲近鄰數據，拓撲近鄰反映的是空間近鄰．獲取樣點拓撲近鄰最直觀的方法就是生成整個點云的Voronoi圖，但構造散亂點云的Voronoi圖系統資源消耗高［17]，如果為查詢某個樣點拓撲近鄰而構造整個點云的Voronoi圖，則付出的代價太大．為快速查詢樣點的k近鄰，首先對點云數據構建R＊S－樹索引結構［18]，基于該索引應用動態擴展空心球算法獲取樣點k近鄰，通過偏心擴展和自適應擴展獲取樣點拓撲近鄰參考數據，生成該局部點集的Voronoi圖，獲取樣點的拓撲近鄰［19]．

1．1 偏心擴展

點集P包含樣點C及其k近鄰點，（xi，yi，zi）為P中各點的坐標．則點集P的形心C1的坐標為

分別求解以點C為起點，k近鄰各點為終點的向量與向量CC1夾角，根據夾角判斷k近鄰點是否位于樣點的同側，若都位于同側則需要對點集P進行偏心擴展．圖1為樣點及其k近鄰點集（k＝12）的Voronoi圖［17]，樣點C的Voronoi單元如圖1中粗線框所示．由圖1可見，如果沿向量CC1相反方向偏心擴展點集P使其包含虛線所示面f右側點，有助于縮小樣點的初始Voronoi單元，進而有效減少后續經自適應擴展獲取的拓撲近鄰參考數據的數量，提高樣點的拓撲近鄰查詢效率．

圖1 樣點及其k近鄰生成的Voronoi圖

該算法的具體步驟如下：

Step1：將散亂點云的采樣密度ρ作為偏心擴展的距離閾值，初始化擴展次數i＝0．

Step2：計算向量C1C的長度d．

Step3：若點集P中所有點位于樣點的同側且i·d≤ρ，則執行Step4；否則，程序結束．

Step4：求解C1關于C的對稱點C′1，并作如下代換：C1＝C，C＝C′1，R＝R＋d，i＝i＋1．

Step5：以C為球心，R為半徑作球，將球內的點添加到點集P中，執行Step3．

對圖1中樣點C的近鄰點集P進行偏心擴展，點A、B被添加到點集P中，如圖2所示，生成其Voronoi圖，樣點的初始Voronoi單元如圖中粗線框所示，與圖1相比，偏心擴展后樣點的初始Voronoi單元明顯縮小．

圖2 偏心擴展后點集的Voronoi圖

1．2 自適應擴展

偏心擴展后獲得樣點的Voronoi單元，計算樣點與其Voronoi單元各頂點的距離，確定最大值dmax，然后以樣點為球心，作半徑為2dmax的球，獲取球內及球面上所有點，將其作為樣點拓撲近鄰參考數據，完成自適應擴展，樣點的拓撲近鄰必定全部包含在該點集中．

1．3 樣點拓撲近鄰查詢

生成樣點拓撲近鄰參考數據的Voronoi圖，從存儲Voronoi單元信息的“facet－edge”數據結構中查找當前樣點所對應的Voronoi單元并獲取Voronoi頂點，查詢與樣點至少具有一個相同Voronoi頂點的Voronoi單元，其所對應的數據點即為樣點拓撲近鄰點．基于局部點集——樣點拓撲近鄰參考數據的Voronoi圖獲取樣點拓撲近鄰，避免了對整體點云生成Voronoi圖，有效降低了算法的時間復雜度．

對于非平面點云，為獲取非均勻區域樣點（如圖3中點p所示）的拓撲近鄰，進行偏心擴展和自適應擴展后獲取的拓撲近鄰參考數據中往往包含樣點局部點集所在平面的鄰側面或對面中的點，如圖3（b）中的點A、B，這些點是不應該參與樣點局部曲面拓撲重建的．為此，將樣點的拓撲近鄰分為同層拓撲近鄰TN1和異層拓撲近鄰TN2．

將樣點及其k近鄰點組成點集P，求解點集P的最小二乘平面，計算點集P中各數據點到該最小二乘平面的最大距離H，將到該最小二乘平面距離小于H的樣點拓撲近鄰數據稱作該樣點的同層拓撲近鄰，其它拓撲近鄰則稱為該樣點的異層拓撲近鄰，并將同層拓撲近鄰作為樣點的Delaunay匹配點．

圖3 樣點同層拓撲近鄰示意圖

2 散亂點云曲面拓撲重建

本文基于網格增量構造算法［2－3]并結合上述樣點拓撲近鄰查詢方法實現散亂點云曲面拓撲重建．

網格增量構造算法的實現步驟一般為：

1）讀取散亂點云，對散亂點云建立R＊S－樹空間索引結構，同時初始化各點的狀態函數值．

2）讀取散亂點云中任意一樣點，查詢其k近鄰，將樣點及其k近鄰組成點集P．

3）對點集P構建Voronoi圖，判斷樣點與其k近鄰之間的空間鄰接關系，從中選擇匹配點．

4）將樣點及其匹配點連接生成局部Delaunay三角網格，將樣點的匹配點順次添加到傳播主環中．

5）以傳播主環為初始邊界，基于網格邊界分裂條件和自裁剪條件，通過已構造網格邊界膨脹、分裂及自裁剪等增量操作將局部網格構造增量傳播至整體點云，完成散亂點云的曲面拓撲重建．

本文采用同層拓撲近鄰查詢方法替換上述Step2中的k近鄰查詢，并將獲取的同層拓撲近鄰數據作為樣點的匹配點，同時省去了Step3，然后依據樣點拓撲近鄰參考數據的Voronoi圖，遍歷樣點p所在Voronoi單元各面的邊表，若共用該邊的多面體鏈表中有三個成員，且此三成員的中心點有兩個是樣點的同層拓撲近鄰，則將此三成員的中心點連接成三角網格，該三角網格即為Delaunay三角網格．將生成的三角網格以Voronoi單元的面結構體形式存儲于一面表中，遍歷完成后即生成滿足條件的局部Delaunay三角網格，順次遍歷存儲局部Delaunay三角網格的面表，再遍歷每個面的頂點鏈表．如圖4所示，將第一個面的第一個非樣點p的數據點p1存儲于區域子環LRp中，將第二個非樣點p的數據點p2存儲于區域子環LRp中，再查找共用p2的另一個面，可獲得p3，同理查找，可獲得區域子環LRp，并將其作為初始傳播主環．獲取傳播主環后即可按網格增量構造算法中的Step5完成散亂點云的曲面拓撲重建．

圖4 樣點p的同層拓撲近鄰及初始網格

基于同層拓撲近鄰重建的三角網格曲面是一個內部無隙曲面，不會存在內邊界．因此，當傳播主環無法繼續膨脹時，如果原產品為封閉的產品模型，則獲取的最終傳播主環為空；如果原產品為開曲面模型，則最終傳播主環為產品的重建邊界．

根據樣點拓撲近鄰的性質可知，基于樣點拓撲近鄰進行散亂點云曲面拓撲重建能夠有效解決現有的網格增量構造算法在處理r－dense恰當采樣點云中非均勻區域時容易產生非工藝孔洞的問題，但與此同時，如圖5（a）所示，原產品模型上的工藝孔洞邊界數據也被重建生成了三角網格，因此需對該區域進行孔洞處理．具體方法為：r－dense恰當采樣點云局部區域為近似均勻采樣，采樣密度為ρ，由三角形三邊關系定理可知合理三角網格的最長邊不大于2ρ，因此，可通過人機交互選擇需要進行孔洞處理的區域，將邊長大于δρ（δ≥2）的三角面片視為不合理面片并刪除，以滿足工藝要求．對圖5（a）所示三角網格進行孔洞處理后，重建效果如圖5（b）所示．

圖5 孔洞處理

3 應用實例

采用本文算法對不同類型點云模型進行曲面拓撲重建，為體現本文算法自適應性強的特點，同時為保證重建效率，k值取常用值（k取10～20［20]）中的最小值10．

圖6（a）所示兔子模型的散亂點云（點數為34 833）分布均勻但曲率變化復雜，采用本文算法對其進行曲面拓撲重建，重建效果如圖6（b）所示．由圖6可知，由于本文算法基于同層拓撲近鄰進行局部網格重建，因此，對于曲率變化大的多輪廓點云仍具有良好的重建效果．

圖7（a）所示汽車部件外殼散亂點云（點數為29 226）內部存在多處工藝孔洞，采用本文算法對其進行曲面拓撲重建，重建效果如圖7（b）所示，由圖7可知，基于本文算法提出的孔洞處理方法能夠有效重建散亂點云的內孔特征．

圖6 本文算法曲面拓撲重建效果圖

圖7 本文算法曲面拓撲重建效果圖

圖8（a）所示米老鼠模型散亂點云在耳朵處由于近似為平面，所以沒有進行高密度均勻采樣，部分區域點云稀疏．如圖8（c）所示，采用文獻［3] 算法對其進行曲面拓撲重建，效果如圖8（d）所示，此時采樣不均勻區域產生非工藝孔洞；采用本文算法進行曲面拓撲重建，效果如圖8（e）和圖8（f）所示；采用文獻［11] 基于全局Voronoi圖過濾的Cocone算法進行曲面拓撲重建，邊界點會與其全部的拓撲近鄰點相連生成三角網格，點云內部重建效果與本文算法基本一致，而邊界重建效果不好，圖8（a）方框區域邊界點的重建效果分別如圖8（g）和圖8（h）所示．由圖8可知，由于本文算法能夠查找到樣點的同層拓撲近鄰，所以既能夠有效解決現有網格增量構造算法在處理r－dense恰當采樣點云中非均勻區域時容易產生非工藝孔洞的問題，又能夠有效生成點云邊界特征．

分別采用文獻［3] 算法、文獻［11] 算法及本文算法對米老鼠、汽車部件、兔子等6種散亂點云進行曲面拓撲重建，所用時間如圖9所示．由于本文算法基于局部點集——樣點拓撲近鄰參考數據的Voronoi圖查詢樣點拓撲近鄰，所以與文獻［11] 基于全局Voronoi圖過濾的Cocone算法相比時間復雜度明顯降低．由圖9可知，本文算法的曲面拓撲重建時間比文獻［11] 算法提高了5倍以上，雖然效率稍遜于文獻［3] 算法，但足以滿足工程需求．

圖8 不同算法曲面拓撲重建效果圖

圖9 不同算法的曲面拓撲重建時間比較

4 結論

本文算法與其他相關算法相比，具有以下特點：

1）基于同層拓撲近鄰數據獲取樣點的自由匹配點，并通過選擇重建模型上的工藝孔洞區域進行孔洞處理，實現了任意復雜散亂點云曲面拓撲重建，算法數據適應性強．

2）基于樣點拓撲近鄰生成Delaunay三角網格，有效解決了現有的網格增量構造算法在處理rdense恰當采樣點云中非均勻區域時容易產生非工藝孔洞的問題．

3）通過建立局部點集——樣點拓撲近鄰參考數據的Voronoi圖獲取樣點拓撲近鄰，相對于現有Voronoi過濾算法有效提高了散亂點云曲面拓撲重建效率．

［1] 譚建榮，李立新．基于曲面局平特性的散亂數據拓撲重建算法［J] ．軟件學報，2002，13（11）：2 121－2 126．

［2] 孫肖霞，孫殿柱，李延瑞，等．散亂數據點的快速三角剖分算法［J] ．中國機械工程，2006，17（增刊）：245－248．

［3] 黃運保．測量點集曲面重建若干關鍵技術研究［D] ：武漢：華中科技大學，2004．

［4] Hugues H．Surface reconstruction from unorganized points［D] ．Washington：University of Washington，1994．

［5] Amenta N，Bern M，Kamvysselis M．A new Voronoi－based surface reconstruction algorithm［C] ／／Ivan Iee．Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques．New York：ACM，1998：415－421．

［6] Hornung A，Kobbelt L．Robust reconstruction of watertight 3D models from non－uniformly sampled point clouds without normal information［C] ／／Ivan Lee．Proceedings of the Fourth Eurographics Symposium on Geometry Processing．New York：ACM，2000：213－222．

［7] 熊邦書，魏江．變分辨率的曲面重建算法［J] ．系統仿真學報，2007，19（18）：4 126－4 133．

［8] Huang J，Menq C．Combinatorial manifold mesh reconstruction and optimization from unorganized points with arbitrary topology［J] ．Computer－Aided Design，2002，34（2）：149－165．

［9] Lin H W，Tai C L，Wang G J．A mesh reconstruction algorithm driven by an intrinsic property of a point cloud［J] ．Computer－Aided Design，2004，36（1）：1－9．

［10] 錢歸平，童若鋒，彭文，等．基于散亂點云內部特征的網格重建［J] ．浙江大學學報：工學版，2008，42（5）：731－735．

［11] Amenta N，Choi S，Dey T K，et al．A simple algorithm for homeomorphic surfacere construction［C] ／／Alla sheffer．ACM Symposium on Computational Geometry．Cagliari：Eurographics Association，2000：213－222．

［12] Tsai Y C，Huang C Y，Lin K Y，et al．Development of automatic surface reconstruction technique in reverse engineering［J] ．The International Journal of Advanced Manufacturing Technology，2009，42（1）：152－167．

［13] Amenta N，Choi S，Kolluri R K．The power crust，unions of balls，and the medial axis transform［J] ．Computational Geometry：Theory and Applications，2001，19（2－3）：127－153．

［14] Dey T K，Goswami S．Tight cocone：a water－tight surface recon－structor［J] ．Journal of Computing and Information Science in Engineering，2003，3（4）：302－307．

［15] Mederos B，Amenta N，Velho L，et al．Surface reconstruction from noisy point clouds［C] ／／Desbrun M，Pottmann H．Proceedings of the Third Eurographics Symposium on Geometry Processing．Vienna：Eurographics Association，2005．

［16] 關東東，汪嘉業，關華勇．r－dense采樣密度及其三維網格簡化中的應用［J] ．山東大學學報：理學版，2005，40（6）：1－8．

［17] Hugo L．Computing the 3Dvoronoi diagram robustly：an easy explanation［C] ／／Christopher Gold．Voronoi Diagrams in Science and Engineering，2007．ISVD’07．4th International Symposium on．Wales：IEEE Computer Society，2007：117－129．

［18] 孫殿柱，朱昌志，李延瑞，等．散亂點云局部型面參考數據的快速查詢算法［J] ．農業機械學報，2009，40（5）：218－221．

［19] 孫殿柱，劉健，李延瑞，等．三維散亂點云的Voronoi拓撲近鄰點集查詢算法［J] ．武漢大學學報：信息科學版，2011，36（1）：86－91．

［20] 單東日，柯映林．基于二維Delaunay近鄰的空間散亂數據曲面重建算法［J] ．中國機械工程，2003，14（9）：756－759．