一種面向飛機虛擬維修的面向對象松散八叉樹*

耿 宏，劉增森

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

0 引言

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

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

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

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

針對以上問題，通過虛擬維修場景與現(xiàn)實世界進行比較，采用松散八叉樹和面向對象概念相結合，構成一種面向對象的松散八叉樹。利用樹的“松散”特性，將對象盡量放在樹的更深層次，以提高場景劃分效率；利用對象的尺寸、中心點確定其應處的節(jié)點，避免對樹的重建，以降低因其移動造成的場景更新時間開銷；利用對象的結構樹，構建用于存儲其幾何、物理等信息的AABB樹，將對象從場景整體三角面片中劃分出來，以滿足與場景對象進行動態(tài)交互要求。

1 面向對象松散八叉樹基本原理

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

圖1 面向對象松散八叉樹基本結構圖

2 面向對象松散八叉樹模型構建

2.1 場景模型的對象化

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

1）根據(jù)結構樹構建零件AABB樹，并在相關節(jié)點植入對象信息。除節(jié)點索引等信息外，在根、葉節(jié)點包圍盒添加了對象屬性信息索引，屬性信息以XML單獨存儲，中間節(jié)點包圍盒數(shù)據(jù)結構除不包含屬性信息索引外與根節(jié)點相同[5-6]。圖2為零件AABB樹根、葉節(jié)點的數(shù)據(jù)結構，其中屬性信息索引、左右子節(jié)點索引均以4 Byte的int型數(shù)據(jù)表示，6個坐標值以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ù)結構表

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

設分裂軸上n個投影點的中值坐標為TC_CENTER，則中值坐標可由下式求得，

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

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

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

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

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

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

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

3）對象AABB樹的更新

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

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

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

2.2 場景的空間剖分

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

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

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

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

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

由以上可得下列各式：

則取depth的極大值為

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

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

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

3 實例

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

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

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

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

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

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

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

Ⅲ該階段是在Ⅰ、Ⅱ階段的基礎上，利用松散八叉樹對場景進行八叉剖分，本文取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，其轉換過程為先繞Z軸旋轉8°，即α=0°，β=0°，θ=8°，測得梯子初始包圍盒中心 Bcenter=（898.795，586.029，32.135），再按平移矩陣（-36.182，127.23，0.0）T進行平移到達B 位置，

結合式（5）～ 式（7）得

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

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

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

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

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

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

4 結論

針對飛機虛擬維修場景的組織管理效率低的問題，提出一種面向對象松散八叉樹場景管理方法，將面向對象概念和松散八叉樹相結合，以樹葉節(jié)點來存儲包含對象屬性信息的AABB樹，利用該方法對維修對象和工具進行快速的定位、簡化了運動物體更新操作過程、降低了場景更新時間開銷，最終提高了飛機虛擬維修場景的組織管理效率。