電纜三維模型可視化及數據高效索引研究①

孫小虎,李 揚,許 剛

1(國網經濟技術研究院有限公司,北京 102209)

2(華北電力大學 電氣與電子工程學院,北京 102206)

目前電纜三維設計成果體系已基本建立,數字化設計成果的數據量越來越大,三維可視化作為數字化成果的一部分,其數據量也變得越來越大.尤其在電纜工程的三維可視化中,由于電纜和支架的幾何結構簡單,并不會占據大量的內存空間,而大量結構復雜的電纜井和管溝的三維模型則占據了接近80%的內存空間,因此對電纜井和管溝進行模型簡化,減少存儲的數據量是當前研究工作的重點與難點所在.另外受限于軟硬件技術的發展水平,計算機無法實現短時間內加載大量數據的要求,而且由于電纜鋪設過程中具有線路繁復、模型復雜而且地形不確定性大等特點,使得電纜鋪設場景中三維模型的數據組織更加困難.因此必須尋求一種適用于電纜工程的三維數據簡化和組織調度方法,來實現三維場景的快速顯示和交互.

當前對電纜工程可視化的研究主要集中在三維管線可視化的研究,文獻[1]在原有的平面二維系統基礎上引入了高程信息,實現了由二維到三維的轉變.文獻[2]主要利用近景測量技術與結構實體法對管線進行了三維建模,然而該研究主要對地上管線有效,對于重建大范圍地下管線及管理具有一定的難度.在文獻[3]提出了一種去除三維模型冗余結構的簡化方法,但對于結構復雜的模型會存在過度簡化的情況,無法保留模型的特征信息.同時在文獻[4]中介紹了一種基于SQL Server和OpenGL的管線模型構建方法.在文獻[5]中介紹了基于ArcGIS Engine平臺進行綜合三維管線可視化的方法.文獻[6]為了運用GRASS實現三維可視化,提出了基于PostgreSQL和PostGIS 設計并構建地下管線綜合數據庫,利用AutoCAD進行管線三維建模的方法.在文獻[7]中建立一種計算模型頂點曲率,簡化三角面片模型,由曲率來決定權值比重的方法,并將權值最小的三角形去除.文獻[8]對網格優化算法進行了改進,引入了遞進網格的相關概念.而文獻[9]為了提高大量數據條件下的地形渲染的效率,提出了一種六邊形的四剖分算法,提升了LOD模型簡化的精度,提高了模型渲染的加載速度.

當前研究雖然對三維數據加載速度的提高有一定效果,但數據存儲量仍然較大.針對目前存在的問題,提出一種三維模型外表面提取算法來對電纜工程中的模型進行簡化,減小數據量.因為電纜工程所具有的特殊性,在三維場景中,較低的LOD層級LOD1-2的情況下,電纜線和支架占據內存量較大,電纜井和管溝所占內存較小;而在實際工程中,大量應用的則是包含內外結構的更高等級的LOD,即LOD3-4.在LOD3-4中,電纜井和管溝則占據了大量的內存,電纜線和支架則對整個工程的數據量影響很小,如圖1所示.所以將研究重點置于對電纜井和管溝進行簡化的研究上[8,9].

1 基于外表面提取算法的電纜場景三維模型簡化設計

1.1 三維場景下的電纜工程細節層次模型

針對電纜場景下的電纜和支架模型結構較為簡單的情況,在實際工程中,只需對其進行LOD1-2的兩級定義.電纜的兩級LOD組織如下:LOD1是矢量點、線,即顯示的是電纜管線整體特征;LOD2是電纜管線的粗模,是細節層次較為豐富的模型,包含了電纜的外層結構[10-12].而支架的兩級LOD組織則是:LOD1是不具有厚度信息的矩形模型;LOD2是長方體的支架模型,如圖2所示.

圖1 不同模型在不同LOD層級下所占內存比例

圖2 工程中的電纜LOD 等級對比

相對于工程中結構較復雜的模型,如電纜井、管溝而言,則需要LOD層級更高更豐富的LOD模型來進行描述.LOD4層級的模型通常包含大量且較為詳細的幾何和語義的信息[13].與LOD3模型相比,LOD4模型包含了模型的具體內部結構和特征.LOD3與LOD4之間的差異是巨大的.因為LOD4模型不再是整體的塊模型,而是包含了對所描述物體的內部結構表示.正是因為有了這樣詳細的信息,LOD4模型可以支持各種三維場景下的應用展示,但同時由于CityGML 中的LOD4模型在文件大小方面過于龐大,無法在時效性要求較高的應用場景中有效地呈現和傳輸數據.雖然與LOD4相比,轉化為LOD3模型后數據大小減小了很多,但模型細節簡化不夠精細,仍具有較多冗余部分而且有著較大的數據量[14,15].為此提出了一個新的子LOD,它具有更小的文件大小,更加簡化的幾何結構.由于新提出的LOD 包含內部結構特征,即在LOD4和LOD3之間,所以命名為LOD3.5.LOD3.5模型既具有豐富的數據,足以進行可視化;又能夠支撐廣泛的應用程序,且需要比LOD3模型小得多的存儲空間.LOD3.5和LOD3模型差距大的原因如下:

圖3 3種不同LOD 等級下的模型對比圖

(1)在LOD3模型中,一些模型表面的結構,如電纜井的管線入口和出口具有較為復雜的形狀,而在LOD3.5中,則只用一個表面來代表這些結構.

(2)在LOD3模型中,包含著模型外表面的厚度信息,而在LOD3.5 中則不存在.

因此,LOD3.5模型可以保留三維模型的重要特性,同時具有更小的數據大小.

如圖3列舉了電纜井中的轉角井、四通井以及管溝進行LOD模型簡化后的效果示意圖.

1.2 模型外表面提取算法

在對電纜工程三維模型進行簡化時,提取模型的外部表面是必須進行的步驟.雖然外部特征和內部特征可以在CityGML 中定義,但一些輸入模型可能并不一定能夠將這些特征區分為外部和內部.例如,從IFC或KML 等其他數據格式轉換而來的CityGML模型可能不會定義每個表面是內部還是外部.因此,我們需要為一些輸入的模型找到外表面,同時,這也是LOD4到LOD3 轉換的一個重要步驟.在三維環境中,電纜井和管溝的外表面難以提取,來形成CityGML的LOD3模型.首先,一個模型可能有不同的布局以及不同的高度,這樣不能通過簡單地擠壓來代表模型本身.其次,計算機程序很難確定電纜井和管溝的內部結構,也很難找到它們的外表面,而且在建模過程中還可能會出現大量的曲面結構,增加了實現模型高精度簡化的難度.針對這些存在的問題,對光線跟蹤算法進行改進,提出了一種模型外表面提取算法[16-18].經過數據處理,CityGML模型被分解成多個具有相應語義信息的塊模型,通過檢查這些塊模型的可見性來找到外表面.我們的算法如下:第一步是找到外部,它是建筑的一個包圍球體,如圖4所示.接下來,檢查每個表面對邊界球上的點的可見性.表面的可見性是由光線跟蹤算法確定的,假設觀察光線從球面上的點發射.例如,如圖4所示,點P11在包圍球上的任何一點上都不可見,因此包含該點的任何表面都不能位于建筑模型的外部外殼上.如果從表面隨機生成的3個點在邊界球上都是可見的,那么這些表面就被認為是可見的,因此在建筑的外殼上也是可見的.為了避免一些外部表面在邊界球中不可見的故障判斷,程序還會檢查生成的外部殼體的連續性.如果在表面上存在孔洞,程序將再次檢查孔洞內的表面,看看它們是否是外部的.算法的流程如算法1.

圖4 外表面提取算法示意圖

算法1.模型外表面提取算法1)輸入:電纜工程中的電纜井模型數據集;2)找出建筑物的邊界球S;3)將初始觀測點陣列P[]分別作為邊界球S的上、下、左、右端點.4)進行循環.5)從輸入中選取一個曲面s,并生成s的數學表達式.6)從s 中隨機選取3個點,每一個點p 都進行如下操作.7)檢查p 對P[]中所有點的可見性.8)如果被某些表面遮擋,將每個邊界的中心加到P[]中,重復上一步.9)直到將所有的表面進行檢查或返回得到一個點存在為止.10)如果P[]中的任何點沒有被遮擋,則報告p為可見;否則,報告p為不可見.11)如果這3個點都是可見的,則返回s為可見;否則,返回s為不可見.12)將返回得到的所有可見表面作為外部表面.13)輸出:電纜井模型的LOD3.5.

使用光線跟蹤算法對建筑進行可見性檢驗,對于從邊界球上的給定點s射向目標表面上的點p的每一條光線,可以表示為:

其中,Is=(xs,ys,zs)和Ip=xp,yp,zp表示點s和點p的坐標.對于模型中其他每一個點p,p所在的平面可以表示為:

其中,pk=(xk,yk,zk)k=0,1,2是曲面p上3個非共線點的坐標.光線與平面的交點p′計算公式為:

可以解得(t′,u′,v′)為:

在實際的電纜工程應用中,與LOD4模型相比,LOD3.5模型減少對三維模型厚度的渲染并不會影響實際的電纜模型展示效果和可視分析.

2 基于多細節層次的三維R-樹索引數據調度方法

針對電纜工程三維數據量大,存儲路徑多且復雜等特點以及其特有的查詢需求,特提出了一種基于多細節層次的三維R-樹索引數據調度方法,來對上文簡化后的電纜井和管溝的三維LOD數據進行組織調度[14].該方法的實施分為以下3個步驟.

(1)節點篩選.根據節點篩選算法的原則:先從底層節點向上進行篩選,再從最高層節點向下進行一遍篩選.接著將目標模型的數據插入.由此可以避免節點重疊的情況出現,也就可以避免由此帶來的選擇錯誤問題,進而可以選出最優葉節點.

(2)節點分裂.對于兄弟節點中所出現的各種情況,如上溢現象、重疊等,采用二分為三的算法進行分裂操作,將出現上述現象的節點進行重組,得到3個小節點.在分裂后想要得到形狀與尺寸均最優的節點,就需要對發生重疊和覆蓋的情況時,節點的評價標準進行綜合分析.

(3)多細節層次索引結構的建立.經過前兩步的節點篩選、節點分裂的操作,已經使得生成的R-樹具有了良好的樹形,可以使得重要模型的數據自動地分配到R-樹的高層節點,從而利用R-樹來對數據進行高效的調用.

2.1 節點篩選算法

評判本算法是否最優,取決于將目標模型的數據插入已選節點后,將其上溯至根節點的路徑上,對于在路徑上的各層節點的影響是否最小.對于R-樹結構的特殊性,當原節點范圍內出現新的模型目標時,插入新數據的操作不會對節點和父節點的范圍產生影響.如果目標不再被包含在集合的所有子節點中,那么就在集合中選擇一個子節點,當把目標模型的數據插入其中時,使得該子節點的效果達到最優,再依次向下進行遍歷操作,尋找最優節點,直至葉節點所在,即可停止[19].

通常把覆蓋范圍和重疊范圍作為R-樹樹形質量的評價標準,但考慮到本索引方法對于多細節層次數據的調用功能的特殊性,故對R-樹的各層節點形狀也有要求,形狀更接近于立方體為最佳,即在三維空間中各個坐標軸上的長度要盡可能保證相等,故定義了如式(5)所示的三維柯西值作為評價標準.

只有在X、Y、Z相等時,等式才成立.假設X×Y×Z的值一定,當三者相等時,的值最小,此時節點在三維空間中的形狀就更接近立方體.所以,將X、Y、Z三個賦予相同大小的權重值所得到的R-樹為最優.綜合節點重疊、節點覆蓋和節點形狀這3個評價因子,將評價標準定義為式(6)所示:

定義節點的邊長分別為X、Y、Z,Overlap代表模型數據插入子節點后,該節點與相鄰節點之間重疊部分的體積變化值;Overlay代表著該節點插入模型數據前后的體積變化值;Shape是由式(5)定義的三維柯西值的變化值.具體的算法明細如算法2.

算法入口,R-樹,待插目標T:簡化后的電纜井和管溝三維模型子集.

算法出口,經過選擇的電纜井和管溝模型子集,并命名為葉節點L.

算法2.節點篩選子算法1)假設目前R-樹有N層,其中,根節點和葉節點分別位于第1和N層.從葉節點所在的第N層開始,查找其中完全包含T的集合,若非空,令I=N,并進入下一步驟;若為空,則向上一層進行查找操作,直到第1層,將根節點加入集合.如果進行上溯操作時,在第J層出現了非空的情況,則令I=J,再進入下一步驟;2)若第I層的節點集合非空,則將其中所有節點的子節點作為一個集合C;3)將T 插入C 中的節點,并計算節點所對應的Metric值,選出該值最小的節點,記為M;M′4)新設立的根節點由步驟3)中選中的節點M 來擔當,在M的子節點中選出合適的節點,將待插目標T 插入.選出一個子節點中Metric值最小的,記為,將其作為新的根節點,重復此步驟直至葉節點;M′5)將步驟4)中選出的所有的Metric值進行比較,選出其中最小的節點作為最終結果;6)退出程序.

2.2 節點分裂算法

R-樹的子元組的數目是有限的.當插入操作使得數目超過最大值時,上溢的節點需要分裂為小節點.這個過程是一種有約束的條件下在三維空間中進行分裂的過程.在執行算法時,一直堅持二分為三的原則.當一個節點出現上溢現象時,在其兄弟節點中尋找二者互相重疊最嚴重的節點,把包含在這兩個節點中的子元素分為三個子節點,這樣可以在減少重疊的同時,對節點形狀進行改進優化[20,21].對于沒有重疊部分的兄弟節點,繼續沿用一分為二的方式.最后,對于分裂后的節點,為其定義評價標準,如式(7):

為達到最優的算法效果,將式(7)中的3個因子賦予相同的權重.算法流程如算法3所示.

算法入口,出現上溢現象的葉節點L1.

算法出口,調整后的R-樹.

算法3.節點分裂算法1)在L1的兄弟節點中尋找L2,L2是符合與之重疊體積最大的條件的節點;2)若不存在L2,就把L1 中所包含的全部子元素作為一個集合C1,進入步驟3),準備將其分為兩個子集合;若存在L2,就把L1和L2 中所包含的全部子元素作為集合C1,進入步驟5),準備將其分為3個子集合.3)從C1 中選擇兩個子元素,如果這二者的(Overlay+Shape)值最大,就將其作為兩個子集合C11和C12的備選元素.接著在剩下的元素中選出一個元素,當其分別插入C11和C12時,Metric值能達到最大,則將其放入到C11和C12 中Metric值較小的中.

4)沿用步驟3)中方法,將其余元素插入到合適的子集合中.插入過程進行到一定程度時,子集合中的元素數目恰好滿足某個子集合的下限最小值,就將其全部賦給該集合,并進入步驟12).5)在C1 中尋找兩個子元素,若二者的(Overlay+Shape)值最大,就將其作為子集合C11、C12和C13 中兩個子集合的備選元素.接著在剩余的元素中選出一個,當其插入三者中的某一個時,若Metric值最小,就將該元素歸入該子集合中.6)由于步驟5)的約束,集合元素的數目受限,當其恰好與R樹節點的下限值相等時即可.7)將剩余的元素記做集合{P1,P2,…,Pi,…,Pn},其中,對于Pi的最小包圍體記為(Ximin,Yimin,Zimin,Ximax,Yimax,Zimax),這些參數分別代表著該元素在3個坐標方向上的坐標最值.接著計算剩余元素的重心.定義元素個數為A,R-樹節點最小值定義為B,若A>B,則刪除離質心最遠的元素,接著返回步驟7);若A=B,則從中選出距質心最近的元素作為第3個集合的備選元素,進入步驟8).8)對于未被列入上述步驟的元素,從中直接挑選出一個,插入第3個子集合中.將W1 定義為評價指標的變化值;再將該元素分別插入另外兩個集合中,得到兩個Metric值,記W2為其中的較小值.若(W2-W1)的值最大,則將該元素插入第3個子集合.9)經過步驟8)的篩選,再從剩余的集合中找出合適的元素插入第3 子集中,使得該集合的元素數目與R-樹的下限值相等即可.10)尋找一個剩余元素,將其分別插入3個子集合中,對應的有3個Metric值,選擇值最小的子集合,并將其歸入該集合中.11)由上一步驟,將剩余的所有元素依次分配到子集合中.12)對于特殊情況,分裂操作導致父節點出現上溢現象,則將該父節點記做L1,并進入步驟1);若不上溢,則進入步驟13).13)退出算法流程.

2.3 多細節層次索引結構的建立

對于三維空間中的目標模型而言,需要建立多尺度的LOD模型描述機制,來對其內外部空間特征進行詳細描述.此外,對于不同層級下的LOD模型進行簡化,可以實現對模型有選擇性的篩選保留.之前的算法所建立的R-樹結構,有著良好的樹形,基于此提出多細節層次三維R-樹索引結構,來對三維空間中的模型數據進行快速索引調用.

本方法與傳統方法的不同點在于,可以實現對重要目標模型數據的管理和調用.對于子節點所管理的重要模型數據,父節點可從中選擇與子節點數目相同的重要模型數據,此操作對于整個R-樹的數據量影響有限.

從R-樹的根節點開始,向下進行遍歷操作,若對于其中的某節點,視點距其的最小距離超過了該節點層次所描述的最遠距離,就不需要考慮其所包含的目標;相反,則需要考慮,并對其進行描述.在實際情況中,要結合視距來選擇合適的LOD模型.

3 實驗結果與分析

3.1 實驗環境設置

實驗仿真基于北京市某區電纜設計工程,運用本文方法對電纜三維場景的數據進行實驗,并測試可視化效果.三維電纜井和管溝模型的數量為175個,原始場景中總的數據量為2 GB.算法的性能取決于兩個因素:1)存儲模型數據量的大小;2)查詢相應時間.數據量越小,查詢響應時間越短代表著算法越優.

具體的軟硬件配置如表1所示.

表1 軟硬件配置

3.2 結果分析

共進行3個實驗,對不同種類電纜井模型進行簡化實驗;接著對簡化后的模型進行響應時間與加載幀率的對比測試;最后對整體三維場景下的漫游效果進行測試.

三維模型的結構簡化與多細節層次索引結構調度的整體思想和流程如圖5所示.

圖5 三維場景模型簡化和可視化過程

實驗1.電纜三維場景模型簡化測試

在實驗1中,針對原始三維場景中占據大量內存的LOD4和LOD3層級的電纜井模型進行簡化,得到LOD3.5模型.對比3種不同層級下的模型數據量,選取了三種常見的電纜井模型,分別是三通井、四通井和轉角井.可以看出,簡化后的模型不僅保留了原有模型的結構特征,更大幅減小了數據量,達到了預期實驗目的.結果如圖6所示.

實驗2.對使用文中算法和使用傳統R-樹三維場景對比測試

圖6 不同LOD層級下的3種電纜井模型

1)查詢響應時間的對比測試

首先用外表面提取算法對電纜三維場景中的模型進行簡化,使得整個三維場景的數據量大幅減小,接著對簡化后的數據分別應用本文算法和傳統R-樹索引算法進行索引組織調度.實驗在不同的尺寸比例下進行查詢響應測試,結果如圖7所示,隨著比例的增加,所需的查詢時間也相應地增加.在相同的比例下,本文算法所需的時間要明顯比傳統R-樹方法的短,特別是隨著比例的增加,這種差別越來越明顯,本方法的優勢也更加突出.

圖7 不同查詢區域尺寸比例下的查詢響應時間

2)加載幀率的對比測試

通過Chrome Dev tools 對電纜三維場景加載時間進行記錄,對使用本文算法和只使用傳統R-樹方法的三維電纜場景漫游過程分別記錄加載幀率,結果如圖8所示.先使用外表面提取算法對模型進行簡化,再用多細節層次的三維R-樹索引數據調度方法實現的三維場景的加載幀率總體上要比只使用傳統R-樹方法實現的三維場景的幀率要高,基本保持在40 fps左右.

圖8 電纜三維場景漫游幀率對比測試

實驗3.電纜工程三維場景圖漫游效果測試

圖9(a)為電纜三維場景中某一視點的三維場景全貌圖,圖9(b)、圖9(c)、圖9(d)為該三維場景下的細節圖,在整個漫游縮放的過程中,電纜工程中的模型顯示流暢,能夠實現與用戶的良好交互.

圖9 電纜三維場景效果測試圖

4 結論與展望

針對電纜三維場景下加載速度慢的問題,本文提出了一種基于外表面提取算法的三維模型簡化與多細節層次的三維R-樹索引數據調度方法.通過對占據大量內存的電纜井和管溝模型進行簡化,即保留了電纜三維場景的結構特征,又大幅減小了數據存儲量.然后根據多細節層次的R-樹索引結構組織調度簡化后的模型數據,最終能夠實現提高電纜模型三維場景的加載速度,有效實現了電纜工程中三維模型的流暢展示以及與用戶的良好交互的目標.為電網工程數字化移交中的三維場景的交互可視化提供了支撐方法.下一步將電纜工程三維可視化技術應用到運檢中,進一步補充和完善相關技術,實現對電纜工程的有效保障.