電纜三維模型可視化及數(shù)據(jù)高效索引研究①

孫小虎,李 揚(yáng),許 剛

1(國(guó)網(wǎng)經(jīng)濟(jì)技術(shù)研究院有限公司,北京 102209)

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

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

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

當(dāng)前研究雖然對(duì)三維數(shù)據(jù)加載速度的提高有一定效果,但數(shù)據(jù)存儲(chǔ)量仍然較大.針對(duì)目前存在的問(wèn)題,提出一種三維模型外表面提取算法來(lái)對(duì)電纜工程中的模型進(jìn)行簡(jiǎn)化,減小數(shù)據(jù)量.因?yàn)殡娎|工程所具有的特殊性,在三維場(chǎng)景中,較低的LOD層級(jí)LOD1-2的情況下,電纜線和支架占據(jù)內(nèi)存量較大,電纜井和管溝所占內(nèi)存較小;而在實(shí)際工程中,大量應(yīng)用的則是包含內(nèi)外結(jié)構(gòu)的更高等級(jí)的LOD,即LOD3-4.在LOD3-4中,電纜井和管溝則占據(jù)了大量的內(nèi)存,電纜線和支架則對(duì)整個(gè)工程的數(shù)據(jù)量影響很小,如圖1所示.所以將研究重點(diǎn)置于對(duì)電纜井和管溝進(jìn)行簡(jiǎn)化的研究上[8,9].

1 基于外表面提取算法的電纜場(chǎng)景三維模型簡(jiǎn)化設(shè)計(jì)

1.1 三維場(chǎng)景下的電纜工程細(xì)節(jié)層次模型

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

圖1 不同模型在不同LOD層級(jí)下所占內(nèi)存比例

圖2 工程中的電纜LOD 等級(jí)對(duì)比

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

圖3 3種不同LOD 等級(jí)下的模型對(duì)比圖

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

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

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

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

1.2 模型外表面提取算法

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

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

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

使用光線跟蹤算法對(duì)建筑進(jìn)行可見(jiàn)性檢驗(yàn),對(duì)于從邊界球上的給定點(diǎn)s射向目標(biāo)表面上的點(diǎn)p的每一條光線,可以表示為:

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

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

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

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

2 基于多細(xì)節(jié)層次的三維R-樹(shù)索引數(shù)據(jù)調(diào)度方法

針對(duì)電纜工程三維數(shù)據(jù)量大,存儲(chǔ)路徑多且復(fù)雜等特點(diǎn)以及其特有的查詢需求,特提出了一種基于多細(xì)節(jié)層次的三維R-樹(shù)索引數(shù)據(jù)調(diào)度方法,來(lái)對(duì)上文簡(jiǎn)化后的電纜井和管溝的三維LOD數(shù)據(jù)進(jìn)行組織調(diào)度[14].該方法的實(shí)施分為以下3個(gè)步驟.

(1)節(jié)點(diǎn)篩選.根據(jù)節(jié)點(diǎn)篩選算法的原則:先從底層節(jié)點(diǎn)向上進(jìn)行篩選,再?gòu)淖罡邔庸?jié)點(diǎn)向下進(jìn)行一遍篩選.接著將目標(biāo)模型的數(shù)據(jù)插入.由此可以避免節(jié)點(diǎn)重疊的情況出現(xiàn),也就可以避免由此帶來(lái)的選擇錯(cuò)誤問(wèn)題,進(jìn)而可以選出最優(yōu)葉節(jié)點(diǎn).

(2)節(jié)點(diǎn)分裂.對(duì)于兄弟節(jié)點(diǎn)中所出現(xiàn)的各種情況,如上溢現(xiàn)象、重疊等,采用二分為三的算法進(jìn)行分裂操作,將出現(xiàn)上述現(xiàn)象的節(jié)點(diǎn)進(jìn)行重組,得到3個(gè)小節(jié)點(diǎn).在分裂后想要得到形狀與尺寸均最優(yōu)的節(jié)點(diǎn),就需要對(duì)發(fā)生重疊和覆蓋的情況時(shí),節(jié)點(diǎn)的評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行綜合分析.

(3)多細(xì)節(jié)層次索引結(jié)構(gòu)的建立.經(jīng)過(guò)前兩步的節(jié)點(diǎn)篩選、節(jié)點(diǎn)分裂的操作,已經(jīng)使得生成的R-樹(shù)具有了良好的樹(shù)形,可以使得重要模型的數(shù)據(jù)自動(dòng)地分配到R-樹(shù)的高層節(jié)點(diǎn),從而利用R-樹(shù)來(lái)對(duì)數(shù)據(jù)進(jìn)行高效的調(diào)用.

2.1 節(jié)點(diǎn)篩選算法

評(píng)判本算法是否最優(yōu),取決于將目標(biāo)模型的數(shù)據(jù)插入已選節(jié)點(diǎn)后,將其上溯至根節(jié)點(diǎn)的路徑上,對(duì)于在路徑上的各層節(jié)點(diǎn)的影響是否最小.對(duì)于R-樹(shù)結(jié)構(gòu)的特殊性,當(dāng)原節(jié)點(diǎn)范圍內(nèi)出現(xiàn)新的模型目標(biāo)時(shí),插入新數(shù)據(jù)的操作不會(huì)對(duì)節(jié)點(diǎn)和父節(jié)點(diǎn)的范圍產(chǎn)生影響.如果目標(biāo)不再被包含在集合的所有子節(jié)點(diǎn)中,那么就在集合中選擇一個(gè)子節(jié)點(diǎn),當(dāng)把目標(biāo)模型的數(shù)據(jù)插入其中時(shí),使得該子節(jié)點(diǎn)的效果達(dá)到最優(yōu),再依次向下進(jìn)行遍歷操作,尋找最優(yōu)節(jié)點(diǎn),直至葉節(jié)點(diǎn)所在,即可停止[19].

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

只有在X、Y、Z相等時(shí),等式才成立.假設(shè)X×Y×Z的值一定,當(dāng)三者相等時(shí),的值最小,此時(shí)節(jié)點(diǎn)在三維空間中的形狀就更接近立方體.所以,將X、Y、Z三個(gè)賦予相同大小的權(quán)重值所得到的R-樹(shù)為最優(yōu).綜合節(jié)點(diǎn)重疊、節(jié)點(diǎn)覆蓋和節(jié)點(diǎn)形狀這3個(gè)評(píng)價(jià)因子,將評(píng)價(jià)標(biāo)準(zhǔn)定義為式(6)所示:

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

算法入口,R-樹(shù),待插目標(biāo)T:簡(jiǎn)化后的電纜井和管溝三維模型子集.

算法出口,經(jīng)過(guò)選擇的電纜井和管溝模型子集,并命名為葉節(jié)點(diǎn)L.

算法2.節(jié)點(diǎn)篩選子算法1)假設(shè)目前R-樹(shù)有N層,其中,根節(jié)點(diǎn)和葉節(jié)點(diǎn)分別位于第1和N層.從葉節(jié)點(diǎn)所在的第N層開(kāi)始,查找其中完全包含T的集合,若非空,令I(lǐng)=N,并進(jìn)入下一步驟;若為空,則向上一層進(jìn)行查找操作,直到第1層,將根節(jié)點(diǎn)加入集合.如果進(jìn)行上溯操作時(shí),在第J層出現(xiàn)了非空的情況,則令I(lǐng)=J,再進(jìn)入下一步驟;2)若第I層的節(jié)點(diǎn)集合非空,則將其中所有節(jié)點(diǎn)的子節(jié)點(diǎn)作為一個(gè)集合C;3)將T 插入C 中的節(jié)點(diǎn),并計(jì)算節(jié)點(diǎn)所對(duì)應(yīng)的Metric值,選出該值最小的節(jié)點(diǎn),記為M;M′4)新設(shè)立的根節(jié)點(diǎn)由步驟3)中選中的節(jié)點(diǎn)M 來(lái)?yè)?dān)當(dāng),在M的子節(jié)點(diǎn)中選出合適的節(jié)點(diǎn),將待插目標(biāo)T 插入.選出一個(gè)子節(jié)點(diǎn)中Metric值最小的,記為,將其作為新的根節(jié)點(diǎn),重復(fù)此步驟直至葉節(jié)點(diǎn);M′5)將步驟4)中選出的所有的Metric值進(jìn)行比較,選出其中最小的節(jié)點(diǎn)作為最終結(jié)果;6)退出程序.

2.2 節(jié)點(diǎn)分裂算法

R-樹(shù)的子元組的數(shù)目是有限的.當(dāng)插入操作使得數(shù)目超過(guò)最大值時(shí),上溢的節(jié)點(diǎn)需要分裂為小節(jié)點(diǎn).這個(gè)過(guò)程是一種有約束的條件下在三維空間中進(jìn)行分裂的過(guò)程.在執(zhí)行算法時(shí),一直堅(jiān)持二分為三的原則.當(dāng)一個(gè)節(jié)點(diǎn)出現(xiàn)上溢現(xiàn)象時(shí),在其兄弟節(jié)點(diǎn)中尋找二者互相重疊最嚴(yán)重的節(jié)點(diǎn),把包含在這兩個(gè)節(jié)點(diǎn)中的子元素分為三個(gè)子節(jié)點(diǎn),這樣可以在減少重疊的同時(shí),對(duì)節(jié)點(diǎn)形狀進(jìn)行改進(jìn)優(yōu)化[20,21].對(duì)于沒(méi)有重疊部分的兄弟節(jié)點(diǎn),繼續(xù)沿用一分為二的方式.最后,對(duì)于分裂后的節(jié)點(diǎn),為其定義評(píng)價(jià)標(biāo)準(zhǔn),如式(7):

為達(dá)到最優(yōu)的算法效果,將式(7)中的3個(gè)因子賦予相同的權(quán)重.算法流程如算法3所示.

算法入口,出現(xiàn)上溢現(xiàn)象的葉節(jié)點(diǎn)L1.

算法出口,調(diào)整后的R-樹(shù).

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

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

2.3 多細(xì)節(jié)層次索引結(jié)構(gòu)的建立

對(duì)于三維空間中的目標(biāo)模型而言,需要建立多尺度的LOD模型描述機(jī)制,來(lái)對(duì)其內(nèi)外部空間特征進(jìn)行詳細(xì)描述.此外,對(duì)于不同層級(jí)下的LOD模型進(jìn)行簡(jiǎn)化,可以實(shí)現(xiàn)對(duì)模型有選擇性的篩選保留.之前的算法所建立的R-樹(shù)結(jié)構(gòu),有著良好的樹(shù)形,基于此提出多細(xì)節(jié)層次三維R-樹(shù)索引結(jié)構(gòu),來(lái)對(duì)三維空間中的模型數(shù)據(jù)進(jìn)行快速索引調(diào)用.

本方法與傳統(tǒng)方法的不同點(diǎn)在于,可以實(shí)現(xiàn)對(duì)重要目標(biāo)模型數(shù)據(jù)的管理和調(diào)用.對(duì)于子節(jié)點(diǎn)所管理的重要模型數(shù)據(jù),父節(jié)點(diǎn)可從中選擇與子節(jié)點(diǎn)數(shù)目相同的重要模型數(shù)據(jù),此操作對(duì)于整個(gè)R-樹(shù)的數(shù)據(jù)量影響有限.

從R-樹(shù)的根節(jié)點(diǎn)開(kāi)始,向下進(jìn)行遍歷操作,若對(duì)于其中的某節(jié)點(diǎn),視點(diǎn)距其的最小距離超過(guò)了該節(jié)點(diǎn)層次所描述的最遠(yuǎn)距離,就不需要考慮其所包含的目標(biāo);相反,則需要考慮,并對(duì)其進(jìn)行描述.在實(shí)際情況中,要結(jié)合視距來(lái)選擇合適的LOD模型.

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境設(shè)置

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

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

表1 軟硬件配置

3.2 結(jié)果分析

共進(jìn)行3個(gè)實(shí)驗(yàn),對(duì)不同種類電纜井模型進(jìn)行簡(jiǎn)化實(shí)驗(yàn);接著對(duì)簡(jiǎn)化后的模型進(jìn)行響應(yīng)時(shí)間與加載幀率的對(duì)比測(cè)試;最后對(duì)整體三維場(chǎng)景下的漫游效果進(jìn)行測(cè)試.

三維模型的結(jié)構(gòu)簡(jiǎn)化與多細(xì)節(jié)層次索引結(jié)構(gòu)調(diào)度的整體思想和流程如圖5所示.

圖5 三維場(chǎng)景模型簡(jiǎn)化和可視化過(guò)程

實(shí)驗(yàn)1.電纜三維場(chǎng)景模型簡(jiǎn)化測(cè)試

在實(shí)驗(yàn)1中,針對(duì)原始三維場(chǎng)景中占據(jù)大量?jī)?nèi)存的LOD4和LOD3層級(jí)的電纜井模型進(jìn)行簡(jiǎn)化,得到LOD3.5模型.對(duì)比3種不同層級(jí)下的模型數(shù)據(jù)量,選取了三種常見(jiàn)的電纜井模型,分別是三通井、四通井和轉(zhuǎn)角井.可以看出,簡(jiǎn)化后的模型不僅保留了原有模型的結(jié)構(gòu)特征,更大幅減小了數(shù)據(jù)量,達(dá)到了預(yù)期實(shí)驗(yàn)?zāi)康?結(jié)果如圖6所示.

實(shí)驗(yàn)2.對(duì)使用文中算法和使用傳統(tǒng)R-樹(shù)三維場(chǎng)景對(duì)比測(cè)試

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

1)查詢響應(yīng)時(shí)間的對(duì)比測(cè)試

首先用外表面提取算法對(duì)電纜三維場(chǎng)景中的模型進(jìn)行簡(jiǎn)化,使得整個(gè)三維場(chǎng)景的數(shù)據(jù)量大幅減小,接著對(duì)簡(jiǎn)化后的數(shù)據(jù)分別應(yīng)用本文算法和傳統(tǒng)R-樹(shù)索引算法進(jìn)行索引組織調(diào)度.實(shí)驗(yàn)在不同的尺寸比例下進(jìn)行查詢響應(yīng)測(cè)試,結(jié)果如圖7所示,隨著比例的增加,所需的查詢時(shí)間也相應(yīng)地增加.在相同的比例下,本文算法所需的時(shí)間要明顯比傳統(tǒng)R-樹(shù)方法的短,特別是隨著比例的增加,這種差別越來(lái)越明顯,本方法的優(yōu)勢(shì)也更加突出.

圖7 不同查詢區(qū)域尺寸比例下的查詢響應(yīng)時(shí)間

2)加載幀率的對(duì)比測(cè)試

通過(guò)Chrome Dev tools 對(duì)電纜三維場(chǎng)景加載時(shí)間進(jìn)行記錄,對(duì)使用本文算法和只使用傳統(tǒng)R-樹(shù)方法的三維電纜場(chǎng)景漫游過(guò)程分別記錄加載幀率,結(jié)果如圖8所示.先使用外表面提取算法對(duì)模型進(jìn)行簡(jiǎn)化,再用多細(xì)節(jié)層次的三維R-樹(shù)索引數(shù)據(jù)調(diào)度方法實(shí)現(xiàn)的三維場(chǎng)景的加載幀率總體上要比只使用傳統(tǒng)R-樹(shù)方法實(shí)現(xiàn)的三維場(chǎng)景的幀率要高,基本保持在40 fps左右.

圖8 電纜三維場(chǎng)景漫游幀率對(duì)比測(cè)試

實(shí)驗(yàn)3.電纜工程三維場(chǎng)景圖漫游效果測(cè)試

圖9(a)為電纜三維場(chǎng)景中某一視點(diǎn)的三維場(chǎng)景全貌圖,圖9(b)、圖9(c)、圖9(d)為該三維場(chǎng)景下的細(xì)節(jié)圖,在整個(gè)漫游縮放的過(guò)程中,電纜工程中的模型顯示流暢,能夠?qū)崿F(xiàn)與用戶的良好交互.

圖9 電纜三維場(chǎng)景效果測(cè)試圖

4 結(jié)論與展望

針對(duì)電纜三維場(chǎng)景下加載速度慢的問(wèn)題,本文提出了一種基于外表面提取算法的三維模型簡(jiǎn)化與多細(xì)節(jié)層次的三維R-樹(shù)索引數(shù)據(jù)調(diào)度方法.通過(guò)對(duì)占據(jù)大量?jī)?nèi)存的電纜井和管溝模型進(jìn)行簡(jiǎn)化,即保留了電纜三維場(chǎng)景的結(jié)構(gòu)特征,又大幅減小了數(shù)據(jù)存儲(chǔ)量.然后根據(jù)多細(xì)節(jié)層次的R-樹(shù)索引結(jié)構(gòu)組織調(diào)度簡(jiǎn)化后的模型數(shù)據(jù),最終能夠?qū)崿F(xiàn)提高電纜模型三維場(chǎng)景的加載速度,有效實(shí)現(xiàn)了電纜工程中三維模型的流暢展示以及與用戶的良好交互的目標(biāo).為電網(wǎng)工程數(shù)字化移交中的三維場(chǎng)景的交互可視化提供了支撐方法.下一步將電纜工程三維可視化技術(shù)應(yīng)用到運(yùn)檢中,進(jìn)一步補(bǔ)充和完善相關(guān)技術(shù),實(shí)現(xiàn)對(duì)電纜工程的有效保障.