[發明專利]針對海量地形大數據點云的總分式三角網多線程并行生成方法

有效

• 申請號: 201410624511.0
• 申請日: 2014-11-07
• 公開（公告）號: CN104318035A
• 公開（公告）日: 2015-01-28
• 發明（設計）人: 韓元利;鄧振林;陳燕平;劉云東;王海松
• 申請（專利權）人: 中鐵第四勘察設計院集團有限公司
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06T17/20
• 代理公司: 武漢開元知識產權代理有限公司 42104
• 代理人: 黃行軍;李滿

技術領域

本發明涉及工程仿真技術領域，具體地指一種針對海量地形大數據點云的總分式三角網多線程并行生成方法。

背景技術

學術上認可的Delaunay三角網構模的主流方法包括逐點插入法、生長法及分治-綜合法。其中分治-綜合法要以前兩者為基礎方法展開，而在兩種基礎方法中最成熟通用的三角網構模方法為逐點插入法，但該方法只適用于小規模點數據建模。

介紹插入法構建三角網技術的中外專業文獻非常多，其中《快速構建三角網數字地形模型方法的研究》(2001.12,蒲浩，中國鐵道科學)不僅簡要地介紹了此方法，并給出了插入點影響域的定義與確立方法，這一概念及方法在本發明中予以引用。

三角網構模算法最大的問題是計算的時間復雜性，由于每個三角網的形成都涉及所有待處理的點，且難于通過簡單的分塊或排序予以徹底解決。點越多，問題越突出，因此對海量空間點的建模一直是一個復雜的難題，此前最理想的解決方法就是采用分治-綜合建模方法，涌現了許多學術成果如《快速構建Delaunay三角網算法研究》(2001.10，宋占鋒，鐵道學報)，其基本思想仍然是空間分割+網格內插入法構建子三角網+網格綜合。但是主要的困難是網格綜合的復雜度既影響構模的穩定性，同時也增加了額外的網格綜合時間銷耗。

發明內容

本發明的目的就是要提供一種針對海量地形大數據點云的總分式三角網多線程并行生成方法，本方法充分引用當前先進的多線程編程技術到傳統算法實現中，與分治-綜合方法相反，是一種新型的總分式空間建模方法，它由整體空間的采樣建模再到局部網格的臨近細節建模，實現了先整體、后局部的分化建模，從而避免了網格之間復雜的綜合過程，并運用多線程技術高效地實現了網格的并行獨立分布化完善建模。

為實現此目的，本發明所設計的針對海量地形大數據點云的總分式三角網多線程并行生成方法，其特征在于，它包括如下步驟：

步驟1：對海量點云數據進行給定規模的自適應網格劃分，使得每一網格內的點數限定在預設的數量LN內(LN表示網格的限制點數,如LN＝1000)，即網格之間無縫無疊地覆蓋整個點云數據空間；

步驟2：對每一個網格內的點按點距離網格中央的距離，由遠及近地進行排序，這樣網格內點隊列的最后一個點就一定是距離網格中央最近的點，稱為中央點；將中央點移動至網格點隊列的最前面；

步驟3：按網格里包含點的數量從小到大對所有網格進行排序，同時標注各個網格中待構模點數RN為點列隊中點的數量；

步驟4：從網格隊列中第一個待構模點數RN>0的網格開始，依次從每一個網格的點隊列中取出第i個點，其中0≤i<LN，用查找插入法構建初級的均衡的三角網，當網格中的一個點參加構模后，該網格的待構模點數RN減1；如此對所有網格重復操作K次，完成各個網格前K個點的插入法構模(1≤K<LN，通常可取K＝4,5,6較適宜)；

步驟5：在每一個網格中完成第K個點的查找插入法構模時，同時在插入法新增加的三角形中找到一個以該網格中央點為頂點的三角形，作為該網格進行拓撲檢索的起始三角形予以記錄；

步驟6：對網格隊列中余下第i個點的插入(K<i≤LN)構模，根據標記的起始三角形，利用既有三角網的拓撲關系采用重心趨近方向搜索方法定位點所對應的三角形，按插入法構模，單個點插入后同樣在新生成的三角形中找到一個以網格中央點為頂點的三角形作為新的起始三角形，這樣能夠保證后續點的插入構模效率不會因為三角網的增加而變低；依次對每一個網格完成第i點的插入構模后再次循環完成i＝i+1個點的構模，直至所有網格的所有點均參與構模，主線程算法完成。

步驟7：在步驟6網格的第i點插入過程完成后，對該網格進行影響域閉合檢測判斷，判斷方法為：

檢索以網格中央點為頂點的所有三角形，如果三角形鄰接三角形的所有頂點均位于本網格內，可認為后續插值點，即i＝i+1個點的影響域在網格區域內閉合，且不存在與其它網格三角形的共享并發沖突，因而可以采用一個獨立的線程對余下所有插值點進行獨立插入法構網,進入步驟8啟動一個新線程對網格余下點進行獨立構模；

步驟8：將以中央點為頂點的所有三角形及其鄰接三角形，作為網格的私有初始三角形，連同后續插值點交由獨立的插入法構網程序完成建模操作，獨立線程的數據來源均由網格私有，外圍拓撲三角形以共享訪問方式共享給所有獨立線程，獨立線程起動后，待構模點數RN＝0，不再同時參加步驟6的檢索插值過程；