劉啟康

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

1 概述

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

本文根據(jù)地下工井的特點(diǎn)，提出了以網(wǎng)格法分離工井上下面，切片法提取工井邊界線，切割插入法進(jìn)行邊界點(diǎn)云排序，最后將上、下輪廓線構(gòu)成三角網(wǎng)模型的方法實(shí)現(xiàn)工井的模型重建，不僅解決了規(guī)則工井的模型重建，同樣適用于不規(guī)則工井的模型重建。

圖1

2 地下工井建模流程

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

2.1 網(wǎng)格法分離上、下面（圖2）

網(wǎng)格法分離工井上、下面的算法流程如下：

2.1.1 計(jì)算x、y 方向的極值；

2.1.2 設(shè)置網(wǎng)格的大小d*d，記錄每個(gè)網(wǎng)格的編碼code；

2.1.3 計(jì)算每個(gè)網(wǎng)格內(nèi)部點(diǎn)云z 方向的極值；

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

圖2

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

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

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

2.2.2 在x 方向上設(shè)置切片寬度為d，計(jì)算切片內(nèi)y 方向的極大值和極小值，設(shè)置閾值，得到x 方向的邊界點(diǎn)；

2.2.3 同理可得到y(tǒng) 方向的邊界點(diǎn)，合并邊界點(diǎn)；

2.2.4 邊界點(diǎn)濾波、采樣。

圖3

2.3 邊界點(diǎn)排序（圖4-5）

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

2.3.1 在x 方向設(shè)置閾值，計(jì)算x 的極大值和極小值，將邊界點(diǎn)劃分為left_loop、right_loop 兩個(gè)區(qū)域；

2.3.2 獲取左右區(qū)域距離最大的兩個(gè)點(diǎn)的索引start(left_loop)、end(right_loop)；

2.3.3 規(guī)定起始方向start-end,順時(shí)針方向?yàn)樽蟓h(huán)，逆時(shí)針方向?yàn)橛噎h(huán)；

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

圖4

圖5

2.4 提取角點(diǎn)并構(gòu)建三角網(wǎng)（圖6-7）

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

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

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

圖7

3 實(shí)驗(yàn)成果（圖8）

圖8