基于多輪廓線的地下工井三維建模

劉啟康

（1、北京建筑大學 測繪與城市空間信息學院，北京100044 2、北京北建大科技有限公司，北京100044）

1 概述

利用物體的輪廓線來重建三維形體的表面是三維建模領域一項重要的研究課題，已廣泛應用于醫學CT 切片成像、三維地質建模、地形表面重建等領域。而依托三維激光掃描儀獲得的地下工井點云進行模型重建也是必然的趨勢，馬洪濱[1]等提出了一種新的多輪廓線重構三維形體算法——切開-縫合法，該法通過引入控制點對作為切口, 將輪廓線對進行坐標轉換和輪廓對應后, 切開并鋪展成兩條平行直線段, 通過尋求輪廓線對頂點的對應關系, 生成了符合Delaunay 法則的三維形體表面三角面片, 并將其應用到基于剖面的三維地質建模中；劉坤良[2]等提出了三維重構中每一個實現步驟具體的解決方案。對輪廓線一對多分叉問題提出了按周長比率解決問題的思路；在末端輪廓線的三角剖分算法中提出了最大張角三角形方法，減少了三角剖分的計算量，達到了在各種形態輪廓線條件下能夠實現正確的拼接；譚正華[3]等提出了一種高質量的基于空間輪廓線的礦體表面三維建模方法，該方法首先根據地層屬性和高程，對輪廓線的空間交點進行一致性校驗，并進行拓撲預處理；其次建立結點-路徑網絡拓撲關系，采用內層路徑優先的搜索算法提取空間網格；最后采用生成過渡輪廓線的方法，對空間網格進行單獨建模并無縫拼接成完整的礦體表面模型；Fuchs[4]提出了在一組橫截面輪廓上構造曲面的一般解決方案，該方法以表面積最小為目標，確定了每對連續輪廓線之間的最佳三角面片組合；Ekoule[5]提出了一種簡單的啟發式三角剖分算法，該算法將原始的任意輪廓分解為基本凸子輪廓，解決了鏈接不同輪廓對的困難以及輪廓分叉的問題。

本文根據地下工井的特點，提出了以網格法分離工井上下面，切片法提取工井邊界線，切割插入法進行邊界點云排序，最后將上、下輪廓線構成三角網模型的方法實現工井的模型重建，不僅解決了規則工井的模型重建，同樣適用于不規則工井的模型重建。

圖1

2 地下工井建模流程

本文采取的地下工井主要建模流程如圖1 所示。

2.1 網格法分離上、下面（圖2）

網格法分離工井上、下面的算法流程如下：

2.1.1 計算x、y 方向的極值；

2.1.2 設置網格的大小d*d，記錄每個網格的編碼code；

2.1.3 計算每個網格內部點云z 方向的極值；

2.1.4 在z 方向設置閾值threshold,分離工井上、下面。

圖2

2.2 切片法提取邊界線（圖3）

切片法提取工井上、下面的邊界線的算法流程如下：

2.2.1 在提取的工井上、下面的基礎上，分別計算上、下面在x、y 方向的極值；

2.2.2 在x 方向上設置切片寬度為d，計算切片內y 方向的極大值和極小值，設置閾值，得到x 方向的邊界點；

2.2.3 同理可得到y 方向的邊界點，合并邊界點；

2.2.4 邊界點濾波、采樣。

圖3

2.3 邊界點排序（圖4-5）

對于獲取的工井邊界點，本文采取切割插入法進行排序，以便提取角點，算法如下：

2.3.1 在x 方向設置閾值，計算x 的極大值和極小值，將邊界點劃分為left_loop、right_loop 兩個區域；

2.3.2 獲取左右區域距離最大的兩個點的索引start(left_loop)、end(right_loop)；

2.3.3 規定起始方向start-end,順時針方向為左環，逆時針方向為右環；

2.3.4 利用knn 搜索鄰近點，依次迭代插入，并將左環與右環相連，形成最終的有序邊界點。

圖4

圖5

2.4 提取角點并構建三角網（圖6-7）

提取邊界線角點的方法是采用從起始點開始遍歷，向前取五個點front，向后取五個點back，分別對front、back 做直線擬合得到方向向量，并進行歸一化處理，計算兩個方向向量的點積，設置閾值，滿足條件則保存為角點。

以相鄰輪廓線點對之間的距離最小為局部最優原則, 通過遍歷所有的輪廓線頂點, 可以搜索出算法最優的控制點對作為“切口”，沿輪廓線統一方向，依次向前取點，將此時對角線最短的兩點作為作為三角形索引點，重復上述操作，直至所有的點都成為三角形的索引點，最后將起點對應的線段“縫合”構建無約束Delaunay 三角網。

具體構建三角網步驟：（1）將邊界點按時針排列；（2）沿著輪廓線方向，迭代選取Pi、Pi+1、Pi+2連續的三個頂點，組成三角面片，下一個三角面片從Pi+2開始選?。唬?）利用PiPi+1、Pi+1Pi+2的叉乘判斷該三角面片是否為逆時針，再判斷其它點Px 是否在三角面片內；（4）若true，則保存此三角面片，記錄索引點，將Pi、Pi+2作為下一次迭代的邊界點；若false，則繼續迭代選取，直至剩余最后一個三角面片；（5）得到新的邊界點后，重復2、3、4 步驟，直至所有的邊界點都組成一個三角面片。

圖7

3 實驗成果（圖8）

圖8