耿 宏，劉增森

（中國民航大學(xué)電子信息與自動化學(xué)院，天津 300300）

0 引言

飛機虛擬維修以培訓(xùn)受訓(xùn)者的維修操作技能為目的，其場景由特定的維修環(huán)境、維修工具和維修對象組成，而場景管理的好壞對最終的培訓(xùn)效果有著直接影響。目前最常用的場景管理方式有場景圖、八叉樹、四叉樹和二叉樹等。其中場景圖主要是對二維動態(tài)場景的管理，而八叉樹、四叉樹和二叉樹主要針對靜態(tài)場景進行管理[1]。由于八叉樹算法充分利用了物體在三維空間上的相關(guān)性，并且具備構(gòu)造簡單、使用方便等特點，進而被廣泛應(yīng)用于虛擬現(xiàn)實系統(tǒng)的場景管理中。然而基于傳統(tǒng)八叉樹對飛機虛擬維修場景進行管理會有以下不足：

1）若一個對象橫跨在某個節(jié)點的任一劃分平面上，那么它就會被存儲在那個節(jié)點中，當(dāng)對象很小而用于存儲它的節(jié)點很大時，大大降低空間劃分的效率。

2）在維修過程中，當(dāng)移動對象時，為表現(xiàn)出它的運動，必須更新八叉樹中相應(yīng)部分，這會增加系統(tǒng)的計算開銷[2-4]。

3）傳統(tǒng)八叉樹中不存在對象的概念，場景中所有三角面片視為整體，在維修過程中無法快速定位到維修對象和維修工具，導(dǎo)致無法滿足與場景對象進行動態(tài)交互的要求。

針對以上問題，通過虛擬維修場景與現(xiàn)實世界進行比較，采用松散八叉樹和面向?qū)ο蟾拍钕嘟Y(jié)合，構(gòu)成一種面向?qū)ο蟮乃缮瞬鏄洹＠脴涞摹八缮ⅰ碧匦?，將對象盡量放在樹的更深層次，以提高場景劃分效率；利用對象的尺寸、中心點確定其應(yīng)處的節(jié)點，避免對樹的重建，以降低因其移動造成的場景更新時間開銷；利用對象的結(jié)構(gòu)樹，構(gòu)建用于存儲其幾何、物理等信息的AABB樹，將對象從場景整體三角面片中劃分出來，以滿足與場景對象進行動態(tài)交互要求。

1 面向?qū)ο笏缮瞬鏄浠驹?/h2>

面向?qū)ο笏缮瞬鏄浠窘Y(jié)構(gòu)由模型對象化和場景空間剖分兩部分組成，如圖1所示。前者依據(jù)對象結(jié)構(gòu)樹來構(gòu)建零件、組件、產(chǎn)品各層次模型的AABB樹，根據(jù)系統(tǒng)交互需求，在對象AABB樹根節(jié)點包圍盒中加入相關(guān)屬性索引，其索引內(nèi)容包括對象的幾何、物理、運動類型等信息，對象的三角面片存儲在AABB樹特定層次的特定包圍盒中，圖1中RP、RA、RC分別表示產(chǎn)品、組件、零件的根節(jié)點，反向虛箭頭表示產(chǎn)品AABB樹是采用自下而上的方式構(gòu)建，L、R為零件樹的左右子節(jié)點，Le為包含面片的葉節(jié)點；后者采用松散八叉樹對AABB樹根節(jié)點八叉剖分，以樹葉節(jié)點存儲對象AABB樹，構(gòu)成一棵面向?qū)ο蟮乃缮瞬鏄?，其中R代表整個虛擬場景的根節(jié)點，N為組結(jié)點，R到N之間的虛線段代表省略了其上層的非葉節(jié)點，Ge為包含模型對象的葉節(jié)點。

圖1 面向?qū)ο笏缮瞬鏄浠窘Y(jié)構(gòu)圖

2 面向?qū)ο笏缮瞬鏄淠Ｐ蜆?gòu)建

2.1 場景模型的對象化

將場景模型從面片中分離并形成可交互的對象需以下步驟：

1）根據(jù)結(jié)構(gòu)樹構(gòu)建零件AABB樹，并在相關(guān)節(jié)點植入對象信息。除節(jié)點索引等信息外，在根、葉節(jié)點包圍盒添加了對象屬性信息索引，屬性信息以XML單獨存儲，中間節(jié)點包圍盒數(shù)據(jù)結(jié)構(gòu)除不包含屬性信息索引外與根節(jié)點相同[5-6]。圖2為零件AABB樹根、葉節(jié)點的數(shù)據(jù)結(jié)構(gòu)，其中屬性信息索引、左右子節(jié)點索引均以4 Byte的int型數(shù)據(jù)表示，6個坐標(biāo)值以4 Byte的float型數(shù)據(jù)表示，F(xiàn)lchild，F(xiàn)rchild用于判別根節(jié)點的左右子節(jié)點是否為葉節(jié)點，以1字節(jié)char型數(shù)據(jù)表示，若是葉節(jié)點取值為true，否則取false。

表1 AABB樹根、葉節(jié)點包圍盒數(shù)據(jù)結(jié)構(gòu)表

要構(gòu)建一棵包含零件屬性信息的AABB樹，需對零件根節(jié)點AABB分割直至葉節(jié)點包圍盒只含有一個三角面，文中采用分裂平面法對AABB分割，構(gòu)建過程為：①構(gòu)建零件的根節(jié)點包圍盒，記為V；②使用最長軸法確定根節(jié)點V的分裂軸，即選擇方向軸使包圍盒沿軸線方向最長，設(shè)軸的方向向量為，軸線由兩個面的交線表示，即，均為已知系數(shù)；③采用中值法確定分裂點以定位分裂平面，設(shè)TCi為節(jié)點中三角面片的中心坐標(biāo)，則

設(shè)分裂軸上n個投影點的中值坐標(biāo)為TC_CENTER，則中值坐標(biāo)可由下式求得，

④利用分裂平面將當(dāng)前節(jié)點中的三角面片劃分到左右兩個子節(jié)點中，取分裂平面上任意點的坐標(biāo)e，令分別為左右子節(jié)點包含的三角面數(shù)，依據(jù)表1判定三角面片應(yīng)處的子節(jié)點。

表2 面片應(yīng)處節(jié)點判定表

⑤將左右子節(jié)點作為根節(jié)點，返回步驟②直到每個葉節(jié)點包圍盒僅含有一個三角面片。

2）根據(jù)零件AABB樹構(gòu)建組件AABB樹

若一個組件由n個零件組成，分別以M1～Mn表示，B（M1）～B（Mn）為 M1～Mn的 AABB 樹根節(jié)點，為構(gòu)建 AABB 樹，CBVT（M1～Mn）利用零件樹的根節(jié)點建立父節(jié)點CB（M1～Mn）將它們聯(lián)系起來，它可表示為B（M1）～B（Mn）的并集[7-8]。

另外，根據(jù)AABB的定義可得

表3為組件樹根節(jié)點的數(shù)據(jù)結(jié)構(gòu)，根據(jù)結(jié)構(gòu)樹，一個產(chǎn)品由N個組件構(gòu)成，則產(chǎn)品AABB樹可由N個組件的AABB樹整合而成，其構(gòu)成原理與組件AABB樹相同。

3）對象AABB樹的更新

設(shè)Bcenter為包圍盒中心初始坐標(biāo)，最大、最小值頂點為Bmax、Bmin，運動后的最大、最小值頂點為B'max，B'min，B'center為運動后的包圍盒中心，B'center沿 X，Y，Z軸的平移向量為

表3 組件樹根節(jié)點的數(shù)據(jù)結(jié)構(gòu)

Bcenter繞 X，Y，Z軸的旋轉(zhuǎn)角度分別為 α，β，θ，旋轉(zhuǎn)矩陣分別設(shè)為Rot（x，α），Rot（y，α），Rot（z，α），繞X軸旋轉(zhuǎn)得，，同理可得繞Y，Z軸的旋轉(zhuǎn)矩陣分別為。若對象只進行平移運動，只需求出變換后的最大、最小值點即可確定新位置處對象的包圍盒，即。當(dāng)對象發(fā)生旋轉(zhuǎn)運動時，不能直接利用旋轉(zhuǎn)矩陣將包圍盒變換到新位置，這里采用一種技巧，首先測出包圍盒最長邊的長度，記為Len，對象旋轉(zhuǎn)后以B'center為中心，邊長為len的立方體作為新包圍盒，B'center經(jīng)旋轉(zhuǎn)運動后的位置可以用旋轉(zhuǎn)矩陣求得，假設(shè)包圍盒中心點依次繞Z軸、Y軸、X軸旋轉(zhuǎn)，設(shè)ROT為旋轉(zhuǎn)矩陣，則

2.2 場景的空間剖分

定義空間為包含多個對象模型的立方體，采用松散八叉樹對其在X，Y，Z 3個方向上剖分，這里涉及到約束條件的建立、對象AABB樹根節(jié)點的剖分、樹的更新。

約束條件為樹的最大分裂深度Dmax，和節(jié)點可包含的最大面片數(shù)Fmax，兩參數(shù)確定方法如下：設(shè)傳統(tǒng)八叉樹某一節(jié)點的包圍盒邊長為u，松散系數(shù)為k，松散后的包圍盒邊長為L，則 L=ku，k∈（1，+∞），設(shè)場景根節(jié)點包圍盒邊長為U，在深度d下的松散節(jié)點包圍盒邊長為L=k×U/2d，設(shè)對象AABB樹根節(jié)點包圍盒的最大邊長為l，對于含有n個對象模型的場景，設(shè)lmin為所有對象樹根節(jié)點包圍盒l(wèi)的最小值，為保證場景中最小八叉樹節(jié)點的包圍盒可包含最小的對象AABB樹根包圍盒，令L≥lmin，得：

基于AABB樹根節(jié)點包圍盒對場景剖分時，若當(dāng)前節(jié)點深度小于Dmax且包含的三角面片數(shù)大于Fmax，則對該節(jié)點繼續(xù)劃分，直到滿足約束條件要求。在剖分過程中，該樹結(jié)構(gòu)可將對象盡量存儲在更深層次的節(jié)點中，以此提高劃分效率，基本原理是：若對象橫跨劃分平面，常規(guī)的處理方法是把該對象存儲在當(dāng)前兩節(jié)點的上一層節(jié)點，這里將節(jié)點邊長擴大k倍，以便對象可被深層單個節(jié)點容納，這種處理方法將對象存儲在樹更深層次的節(jié)點中[9]。

當(dāng)對象移動時，須對八叉樹進行更新，其基本原理如下：

在松散八叉樹中，對于一個特定的物體，它應(yīng)插入的深度和節(jié)點可根據(jù)其尺寸大小和中心位置求得[10]。對于給定深度depth的松散節(jié)點，它在該深度任意位置可容納小于等于八叉樹節(jié)點包圍盒邊長1/2，大于1/4的對象AABB樹根節(jié)點包圍盒，尺寸比此更小的包圍盒應(yīng)存在更深層次的節(jié)點中。

由以上可得下列各式：

則取depth的極大值為

設(shè)對象AABB樹根節(jié)點包圍盒中心點坐標(biāo)為Ocenter，由depth已知，此時只需選擇距離中心坐標(biāo)最近的節(jié)點作為存儲物體的節(jié)點，所有節(jié)點的中心坐標(biāo)集合可表示為：

則節(jié)點node的索引公式可表示為：

其中find為自定義函數(shù)，作用是搜索距Ocenter最小點，并輸出與其對應(yīng)節(jié)點信息。

3 實例

為驗證本文算法的有效性，將文中算法、傳統(tǒng)算法分別應(yīng)用到飛機虛擬維修機庫AH（Aircraft hangar）、電子設(shè)備艙 EEC（Electronic equipment cabin）場景，對所測性能數(shù)據(jù)進行統(tǒng)計和對比。圖2為機庫場景的實現(xiàn)圖，運用其Ⅰ～Ⅳ階段實現(xiàn)算法如下：

Ⅰ該階段是將零件模型對象化。首先，獲取對象的最大、最小值頂點坐標(biāo)，建立其AABB樹根節(jié)點包圍盒，以梯子橫板為例，其最大、最小值坐標(biāo)分別為：

圖2 文中算法在機庫場景的實現(xiàn)圖

其次，遍歷構(gòu)成該對象的所有三角面片，獲取面片總數(shù) n 和頂點坐標(biāo)（pi，qi，ri）ni=1，由式（1）到式（3）求得分裂點 TC_center=（452.129，532.915，29.75），測得n=2 158；最后，根據(jù)表2判定面片應(yīng)處的子節(jié)點位置，首次分裂最長軸方向向量 a取（0，0，1），重復(fù)以上步驟對子節(jié)點分裂，直到每個節(jié)點只包含一個面片，依據(jù)表1完成對零件AABB樹根節(jié)點和葉節(jié)點相關(guān)索引信息的添加。

Ⅱ此階段的任務(wù)是在Ⅰ的基礎(chǔ)上，將組件或產(chǎn)品模型對象化處理。圖2中橫板和支撐桿作為構(gòu)成梯子16零件中的兩個，虛線表示省略了其他零件，測得AABB樹16個根節(jié)點的包圍盒的最大、最小值頂點為：

根據(jù)式（4）可得

由此可構(gòu)建梯子AABB樹，依據(jù)表3完成根節(jié)點相關(guān)索引信息的添加。

Ⅲ該階段是在Ⅰ、Ⅱ階段的基礎(chǔ)上，利用松散八叉樹對場景進行八叉剖分，本文取k=2、=3，同時測得 U≈350，lmin≈8，NUMmin=1 371，則據(jù)式（8）、式（9）可得Dmax=6，F(xiàn)max=4 113，以兩參數(shù)為約束條件，完成對場景的剖分。

Ⅳ該階段主要處理場景中運動對象的更新問題，這里的更新包括兩方面，一是對象AABB樹的更新，二是松散八叉樹的更新。由圖2，梯子由位置A移動至位置B，其轉(zhuǎn)換過程為先繞Z軸旋轉(zhuǎn)8°，即α=0°，β=0°，θ=8°，測得梯子初始包圍盒中心 Bcenter=（898.795，586.029，32.135），再按平移矩陣（-36.182，127.23，0.0）T進行平移到達B 位置，

結(jié)合式（5）～ 式（7）得

利用len=36.327作出對象運動后的AABB樹。對象運動后還需對八叉樹更新，已知梯子的l≈36，則根據(jù)式（10）可得 depth=3，結(jié)合式（11）得梯子應(yīng)放節(jié)點的索引公式

其 i=1，…，n，（xi，yi，zi）遍歷節(jié)點自動獲取。

表4和圖3記錄了傳統(tǒng)算法與本文算法在飛機虛擬場景管理方面的性能參數(shù)，這里將平均繪制幀速、場景更新平均耗時和平均交互靈敏度（受訓(xùn)者點擊交互對象到對象響應(yīng)時間間隔）作為兩者對比主要的性能參數(shù)。場景更新平均耗時選用飛機電子設(shè)備艙進行測試，通過改變設(shè)備艙內(nèi)移動物體的數(shù)量，記錄在兩種算法下場景更新時間變化。

表4 兩種算法下幀速、靈敏度對比表

圖3 AH、EEC場景更新時間對比圖

由表4，與傳統(tǒng)算法相比，本文算法在機庫和飛機電子設(shè)備艙內(nèi)的平均繪制幀速分別提高了34.8%、19.8%，平均交互靈度分別降低了62.3%、46.8%的時間開銷，由圖3，在本文算法下，隨著場景中移動對象的增多，場景更新操時間并沒有顯著增加。

4 結(jié)論

針對飛機虛擬維修場景的組織管理效率低的問題，提出一種面向?qū)ο笏缮瞬鏄鋱鼍肮芾矸椒?，將面向?qū)ο蟾拍詈退缮瞬鏄湎嘟Y(jié)合，以樹葉節(jié)點來存儲包含對象屬性信息的AABB樹，利用該方法對維修對象和工具進行快速的定位、簡化了運動物體更新操作過程、降低了場景更新時間開銷，最終提高了飛機虛擬維修場景的組織管理效率。