[發明專利]基于雙重空間數據組織的海量點云Delaunay三角網構建方法

在審

• 申請號: 201710882593.2
• 申請日: 2017-09-26
• 公開（公告）號: CN107644422A
• 公開（公告）日: 2018-01-30
• 發明（設計）人: 周良辰;劉年濤;林冰仙;閭國年
• 申請（專利權）人: 南京師范大學
• 主分類號: G06T7/11
• 分類號: G06T7/11;G06T7/543
• 代理公司: 南京蘇高專利商標事務所(普通合伙)32204
• 代理人: 唐紅

1.一種基于雙重空間數據組織的海量點云Delaunay三角網構建方法，其特征在于：依次包括以下步驟：

(1)利用四叉樹通過三次完整遍歷實現對點云進行格網組織；

(2)對經過上述組織后的每個矩形格網中的點云進行逐點排序；

(3)利用逐點插入法對點云進行構網，并將構網過程中內存里的三角形分為穩定三角形和不穩定三角形，將內存中的穩定三角形寫入到硬盤，保留不穩定三角形繼續參與后續的構網過程；

(4)流水線調度：對以上三個步驟按照流水線進行調度，設格網分割線程、排序線程和構網線程分別對應步驟(1)、(2)和(3)，最后輸出三角網。

2.根據權利要求1所述的基于雙重空間數據組織的海量點云Delaunay三角網構建方法，其特征在于：所述步驟(1)的具體過程為：

(1.1)第一次遍歷：

設待分割的原始輸入點云為P＝{p_i,i∈[1,n]}，其中P_i.x和P_i.y分別代表點p_i的X和Y坐標，通過第一次遍歷點云P計算出點數n和X、Y坐標的最值：

xmax＝max(P_i.x),i∈[1,n]、xmin＝min(P_i.x),i∈[1,n]

ymax＝max(P_i.y),i∈[1,n]、ymin＝min(P_i.y),i∈[1,n]

則由p₁(xmax,ymax)，p₂(xmax,ymin)，p₃(xmin,ymax)，p₄(xmin,ymin)四個點組成的矩形就是點云P的最小外接矩形MBR；

(1.2)第二次遍歷：

利用四叉樹對點云進行遞歸分割，至每個四叉樹葉節點中包含的點數量n小于10000時停止，然后設此時的四叉樹深度為k，則該四叉樹的根節點對應的空間范圍是點云的最小外接矩形MBR，經過k次遞歸細分，MBR被細分為4^k個子矩形G＝g_i,i∈[1,4^k]；

第二次遍歷點云P，統計每個子矩形g_i中的所包含的點數n_i，即判斷每個點被包含于哪個四叉樹的葉子節點中；

(1.3)第三次遍歷：

先確定每個點的所屬四叉樹葉子節點，與第二次遍歷類似，然后將這個點保存在葉子節點中，并將第二次遍歷時統計的該葉子節點中保存的點數n_i減1，當n_i等于0的時候，說明該葉子節點包含的所有點已經保存到節點中。

3.根據權利要求1所述的基于雙重空間數據組織的海量點云Delaunay三角網構建方法，其特征在于：所述步驟(2)中穩定三角形和不穩定三角形的判斷依據為：如果一個三角形的外接圓既不與頂點所在的矩形邊界相交，也不與頂點所在矩形的父節點的矩形邊界相交，則認為這個三角形是穩定的，否則即為不穩定三角形。

4.根據權利要求1所述的基于雙重空間數據組織的海量點云Delaunay三角網構建方法，其特征在于：所述步驟(4)中流水線調度的具體過程為：

(4.1)對于格網分割線程，每次完成分割的時候，將當前所有矩形格網中的點云寫入待排序緩沖區中，而排序線程在空閑的時候就不停的檢測待排序緩沖區中是否存在數據，若有，則取出進行排序，否則繼續檢測；

(4.2)在排序線程完成當前矩形格網中點云的排序之后，將該矩形格網內的所有點云放入待構網緩沖區中，而構網線程則不停的檢測構網緩沖區中是否存在數據，若有，則取出進行構網，否則繼續檢測；

(4.3)在分塊線程完成所有點云的格網分割之后，對排序線程發送信號，則排序線程在處理完待排序緩沖區中的數據后就停止運行，同時給構網線程發送信號，最后構網線程處理完構網緩沖區中的數據，并且將內存中的所有有效三角形都輸出到硬盤中，整個點云的重建過程就結束。