耿 宏，劉增森

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

0 引言

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

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

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

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

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

1 面向?qū)ο笏缮瞬鏄?shù)基本原理

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

圖1 面向?qū)ο笏缮瞬鏄?shù)基本結(jié)構(gòu)圖

2 面向?qū)ο笏缮瞬鏄?shù)模型構(gòu)建

2.1 場(chǎng)景模型的對(duì)象化

將場(chǎng)景模型從面片中分離并形成可交互的對(duì)象需以下步驟：

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

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

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

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

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

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

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

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

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

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

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

3）對(duì)象AABB樹(shù)的更新

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

表3 組件樹(shù)根節(jié)點(diǎn)的數(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)矩陣分別為。若對(duì)象只進(jìn)行平移運(yùn)動(dòng)，只需求出變換后的最大、最小值點(diǎn)即可確定新位置處對(duì)象的包圍盒，即。當(dāng)對(duì)象發(fā)生旋轉(zhuǎn)運(yùn)動(dòng)時(shí)，不能直接利用旋轉(zhuǎn)矩陣將包圍盒變換到新位置，這里采用一種技巧，首先測(cè)出包圍盒最長(zhǎng)邊的長(zhǎng)度，記為L(zhǎng)en，對(duì)象旋轉(zhuǎn)后以B'center為中心，邊長(zhǎng)為len的立方體作為新包圍盒，B'center經(jīng)旋轉(zhuǎn)運(yùn)動(dòng)后的位置可以用旋轉(zhuǎn)矩陣求得，假設(shè)包圍盒中心點(diǎn)依次繞Z軸、Y軸、X軸旋轉(zhuǎn)，設(shè)ROT為旋轉(zhuǎn)矩陣，則

2.2 場(chǎng)景的空間剖分

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

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

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

當(dāng)對(duì)象移動(dòng)時(shí)，須對(duì)八叉樹(shù)進(jìn)行更新，其基本原理如下：

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

由以上可得下列各式：

則取depth的極大值為

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

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

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

3 實(shí)例

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

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

圖2 文中算法在機(jī)庫(kù)場(chǎng)景的實(shí)現(xiàn)圖

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

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

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

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

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

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

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

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

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

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

表4 兩種算法下幀速、靈敏度對(duì)比表

圖3 AH、EEC場(chǎng)景更新時(shí)間對(duì)比圖

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

4 結(jié)論

針對(duì)飛機(jī)虛擬維修場(chǎng)景的組織管理效率低的問(wèn)題，提出一種面向?qū)ο笏缮瞬鏄?shù)場(chǎng)景管理方法，將面向?qū)ο蟾拍詈退缮瞬鏄?shù)相結(jié)合，以樹(shù)葉節(jié)點(diǎn)來(lái)存儲(chǔ)包含對(duì)象屬性信息的AABB樹(shù)，利用該方法對(duì)維修對(duì)象和工具進(jìn)行快速的定位、簡(jiǎn)化了運(yùn)動(dòng)物體更新操作過(guò)程、降低了場(chǎng)景更新時(shí)間開(kāi)銷，最終提高了飛機(jī)虛擬維修場(chǎng)景的組織管理效率。