基于AABB樹的聚變堆形變部件碰撞檢測算法①

鄧峻生,毛世峰,劉旭峰,葉民友,

1(中國科學技術大學 物理學院,合肥 230027)

2(中國科學院 等離子體物理研究所,合肥 230031)

中國聚變工程實驗堆(CFETR)是正在設計中的超導聚變實驗堆,旨在彌補聚變實驗堆ITER和示范反應堆DEMO之間的空白[1–3].為了支持CFETR設計工作高效協同的展開,CFETR集成設計平臺[4,5]目前正在開發中.

在工程設計中,由于外部環境等因素影響,部件會產生應力、導致形變,影響零部件的裝配設計與空間布局[6].因此對形變部件的碰撞檢測,是工程設計中的必不可少的檢測環節.工程設計中通常利用有限元方法分析計算部件的應力、形變,計算結果以有限元網格的形式存儲.目前對于剛體模型的碰撞檢測算法研究比較充分,針對復雜場景的快速檢測算法也正在不斷發展[7].對有限元結果的碰撞檢測,由于模型的復雜度較高,需要采取多種措施降低計算復雜度.

對形變的有限元模型的碰撞檢測問題,Sean Curtis等提出了基于特征三角形的快速檢測方法[8],吳崢等提出了三角片與包圍盒混合的快速碰撞檢測算法[9].這些算法主要針對三角片網格與四面體網格,不適合工程設計中復雜多樣的有限元網格,且在三角形相交、包圍盒處理、并行化等方面存在不足,計算的效率存在提升空間.

本文提出了一種基于三角形碰撞檢測與軸對齊包圍盒(Axis-Aligned Bounding Box,AABB)的、針對有限元模型的通用快速碰撞檢測算法: 將有限元的幾何表面三角化后,選擇合適的三角形相交算法,利用AABB包圍盒緊密性好、相交測試簡單的優勢并采用優化后的AABB樹算法,結合并行化的設計,實現對有限元模型的快速碰撞檢測.利用本算法可以處理多種有限元網格,對工程設計中復雜的形變有限元模型實現高效快速的碰撞檢測.本文將該算法應用于聚變堆的工程設計中,能夠有效提高碰撞檢測的效率,并給出清晰直觀的檢測結果.

1 碰撞檢測算法

有限元模型由大規模的網格和網格節點組成,網格類型包括四面體、六面體等幾何體.在有限元模型的碰撞檢測中,通過提取幾何表面、將表面的幾何面用三角形重構,可以將有限元模型的碰撞問題,轉換為表面三角片的碰撞檢測問題; 同時利用包圍盒算法簡化碰撞計算、引入AABB樹算法提高碰撞檢測效率[10],最終實現部件有限元模型的快速碰撞檢測.算法的處理步驟如圖1所示.

核心步驟如下所述:

Step 1.讀取有限元計算結果,提取模型的表面節點,用三角片重構,以三角形網格描述幾何體的輪廓.

Step 2.計算三角片對應的AABB包圍盒,將包圍盒與三角形對應.

Step 3.對包圍盒集,構造AABB樹,將所有包圍盒存儲在二叉樹中.

Step 4.對兩棵AABB樹中的包圍盒進行碰撞檢測.如果包圍盒間存在碰撞,則繼續檢測包圍盒對應的三角片的碰撞問題.

Step 5.跳過未碰撞的包圍盒、三角片,記錄所有碰撞的三角片對,構成碰撞結果集.

圖1 碰撞檢測算法計算流程

Step 6.結束計算,將碰撞區域存儲為STL (stereolithography,立體光刻)格式的三角片模型文件.

1.1 包圍盒算法

包圍盒算法在數字化模型的碰撞檢測計算中有著廣泛的應用[11,12],其核心思路為: 將復雜幾何體用一個簡單幾何體包圍,如立方體、球體,然后計算簡單幾何體的碰撞,排除不碰撞對象,最后計算被簡單幾何體包含的幾何體間關系.

針對本文靜態檢測的場景,選擇構造AABB包圍盒進行計算.在讀取三角片網格后,首先對所有三角片構造AABB包圍盒,即用一個與x、y、z三軸平行的立方體包圍幾何面.如果一對立方體不碰撞,則立方體內的幾何面元不會碰撞.

對一個三角形面元,其包圍盒可以兩個點表示: 如式(1)(2)所示,兩個點的坐標由所有頂點在x、y、z方向上的最大值最小值決定.

檢測兩個軸對齊包圍盒是否碰撞,需要將包圍盒分別投影到x、y、z軸上,判斷其投影是否相交.對于兩個包圍盒A、B,將其投影到x軸上,對應關系為:

式(3)(4)表示包圍盒在x軸上的投影區間,兩區間不相交的條件為式(5):

當包圍盒在x、y、z軸向的投影都相交,則判定包圍盒相交.本方法只需進行6次大小判斷、3次或操作,即可完成包圍盒碰撞檢測.

相比直接進行空間三角形的檢測,AABB包圍盒排除相交的計算量更小,因此計算速度更快.

1.2 AABB樹算法

1.2.1 層次包圍盒與AABB樹

當兩個三角形相距較遠時,采用AABB包圍盒可以快速排除且降低了求交的計算量,但是采用AABB包圍盒算法,依然需要對A的m個包圍盒與B的n個包圍盒求交,沒有降低求交計算的次數.

為了降低求交計算的時間復雜度,引入AABB樹的結構.AABB樹基于層次包圍盒原理,即用大的包圍盒包裹小的層次包圍盒,并用大包圍盒進行求交計算;層次包圍盒基于如下原理:

AABB樹是一種以二叉樹存儲的層次包圍盒,樹的每個節點都是一個包圍盒,除葉節點外每個包圍盒包含兩個子盒; 所有葉節點為幾何體的包圍盒.

AABB樹的層次包圍盒結構如圖2所示,對應的二叉樹存儲結構如圖3所示.

1.2.2 AABB樹的構建

AABB樹的構建流程如圖4,核心步驟如下文.

(1) 新建包圍盒作為節點,包含兩個子節點的包圍盒.

(2) 新包圍盒向樹中添加時,與節點包圍盒測試相交.

(3) 如果不相交則新建包圍盒包裹當前節點和新包圍盒并作為頭結點,當前節點和新包圍盒作為子節點.

(4) 如果與其相交,則首先新建大包圍盒替換當前節點,然后新包圍盒與兩個子節點合并,選擇合并后體積較小的節點,進行迭代操作.

通過這種方法,可以建立層次包圍盒結構,并存儲在二叉樹中.

圖2 層次包圍盒示意圖

圖3 二叉樹結構示意圖

圖4 AABB樹構造流程

1.2.3 AABB樹的碰撞檢測

一個包圍盒,與一棵AABB樹的碰撞檢測過程,從根節點對應的包圍盒開始計算:

(1) 如果與節點不相交,則該節點的所有子節點都不相交.

(2)如果包圍盒與一個節點相交,則繼續與節點的兩個子節點求交,進行迭代直到葉節點.理想情況下,包圍盒每次只與一個子包圍盒相交,相當于二分查找.對于n個節點的樹,理想情況下的求交次數為logn級別.

因此采用AABB樹后,算法復雜度可以降低為O(mlogn).

對兩棵AABB樹的計算有所區別: 從兩棵樹的根節點開始遍歷,如果當前兩個節點相交,則計算二者的子節點包圍盒的相交關系; 通過遞歸,直到葉節點包圍盒為止.

1.2.4 AABB樹的優化

王曉榮等從AABB樹的平衡角度,提出了AABB樹構建過程中的建議[13].當AABB樹的左右節點近似于空間二分時,碰撞檢測的效率最高; 為了實現這個效果,引入分割操作:

(1)選擇整個模型在x、y、z軸上最長的軸,計算模型在該方向的最大值、最小值.

(2)將所有包圍盒,按照其在最長軸上的投影,在最小值、最大值方向分成兩組,并盡可能保證平衡.

通過這種方法,直到二分后每一組的三角片數量到達一定程度; 如此建立的二叉樹比不分組情況下更加平衡,計算效率更高.

1.3 三角形相交檢測

對于三角形的快速相交檢測算法研究很多,典型的如標量判別型的M?ller算法[14],矢量判別型的Devillers & Guigue算法[15](以下簡稱Devillers算法).本節將對兩種算法進行比較,選擇本計算場景下性能更優的算法.

1.3.1 標量判別型的M?ller算法

標量判別型算法是通過準確計算來獲知兩三角形相交關系的一類算法.算法的基本思路如下所述:

其中,x為任意一點的坐標.

空間中一點坐標帶入方程,值為0則在面上,大于0則在面上方,小于0則在面下方.據此進行如下計算.

Step 3.如果T2三點在平面上,轉換為共面三角形的相交計算.如果一個點在面上,且其它兩點同號,則計算該點是否在三角形內部; 如果兩個點在面上,計算線段與三角形的關系.總之,可以轉換為平面內計算.

Step 4.如果T2的三個頂點在的兩側,則計算的三個頂點與平面的關系.

如圖4所示,設平面的交線為k,則兩個三角形一定都與k相交.直線k的方程可以表示為:

其中K為直線的方向向量,i為標量化的點坐標.

M?ller算法的核心,就是計算出三角形與k的交點的i值.設T1和T2與k的交點參數值分別為i、j和k、l,則區間(i,j)與(k,l)相交,等價于三角形相交.

1.3.2 矢量判別型的Devillers算法

矢量判別型算法是通過一系列計算值的符號來判定兩個三角形的位置關系,繼而判別其相交情況的一類算法.算法的核心思想如下所述:

行列式的值表示點d與a、b、c組成平面的位置關系,等于0在面上,大于0在面上方,小于0在面的下方.通過該公式,對三角形間的位置關系進行判定.

與M?ller算法的過程類似,對于三角形在平面一側的情況可以進行排除、對于共面或者點、線段等情況可以進行計算; 通過T1、T2的最終校驗,最終需要計算剩下T1、T2分別在平面兩側的情況.

Devillers算法不計算具體的交點坐標,而是計算行列式的值,進行相交判斷.如圖所示得情況下,循環置換頂點,保證在面的一面,同時交換保證在面的上方.

如圖5所示,考慮三角形與交線k的相交區域,為保證二者存在重疊,即區間(i,j)與(k,l)相交,只需k≤j且i≤l,用判別式表示即:

1.3.3 算法比較

矢量型的Devillers算法,與標量型的M?ller算法相比,存在性能優勢:

(1)內存使用上,M?ller算法使用55個變量,而Devillers算法只需18個變量.

圖5 三角形相交示意圖

(2)在計算點與面的關系時,面方程方法與行列式方法計算量相同; 兩種算法的區別在處理三角形在兩側的場景下,M?ller算法要求解四個坐標的值,而Devillers算法只判斷兩個行列式大小,后者計算量更小.

(3)排除不相交的三角形時,M?ller算法進行三次排除,而Devillers算法進行四次排除; 前兩次排除的計算相同,Devillers算法在后面的排除中,通過行列式的正負號排除,比M?ller算法效率更高.

鄒益勝等對兩種算法進行了性能測試[16],用隨機生成的三角形進行計算,結果表明Devillers算法的計算效率比M?ller算法高約15%.因此本文選擇Devillers算法,對三角形進行相交檢測.

1.4 并行優化

實際應用場景中,復雜模型的三角片網格一般為十萬、百萬量級,為了充分利用計算資源,加快計算速度,本算法采用多線程的方式,提高碰撞檢測的計算效率.

在文件讀取、包圍盒構建、AABB樹構建過程中,處理兩個模型,可以利用2個線程并行完成.

在碰撞檢測的過程中,可以將待檢測的模型拆分,利用多線程方法加快計算速度.設有兩棵AABB樹A與B,并行的基本思路如下所述:

(2)將二叉樹A,從頭結點開始迭代,按左右節點拆分為2n棵子樹.

(3)在每個線程中,每棵子樹與二叉樹B進行碰撞檢測; 全部計算結束后合并結果.

并行沒有降低計算量,而是充分利用多核優勢,縮短碰撞檢測需要的時間.

2 算法應用與分析

本文選擇CFETR中兩個相鄰部件作為測試用例,對算法性能進行測試.待分析模型為有限元模型,經三角化處理后重構為三角片網格模型.

算法由C++代碼實現,程序的運行平臺為Windows 10系統,硬件參數為: CPU參數4核3.30 GHz,內存8 GB.

2.1 算法效率

待處理模型的基本參數,包括三角形面元、碰撞三角形、碰撞區域占比等參數如表1所示.

表1 模型面元數量與碰撞區域數據

為比較算法的性能與優化效果,在碰撞檢測過程中,使用多種不同策略進行計算:

(1)采用M?ller算法遍歷計算三角形相交.

(2)采用Devillers算法遍歷計算三角形相交.

(3)在方法2基礎上,為三角形建立包圍盒,先對包圍盒測試相交,再計算三角形相交.

(4)在方法3基礎上引入AABB樹方法,計算包圍盒相交,然后求解三角形相交.

(5)對方法4中AABB樹的構建進行優化.

(6)在5基礎上,采用并行計算加速; 本文中選擇4線程進行計算.

采用不同策略時,算法的性能如表2所示.

表2 不同策略下的算法性能比較

對多種優化策略的比較如下:

(1) 三角形相交算法

設A與B模型分別包含m、n個三角形,在計算碰撞時,如果采用直接遍歷方法,對A中的每一個三角形,與B中每一個三角形進行相交測試,相交測試的次數為m×n,時間復雜度為O(mn).策略1與策略2相比,計算復雜度相同.實驗中1與2的對比表明,矢量判別型的Devillers算法比標量判別型的M?ller算法效率高20%左右.

(2) AABB包圍盒

在有限元計算的場景中,每個三角片面積很小,三角形間不相交是大概率事件.采用AABB包圍盒算法時,依然需要將A中m個包圍盒與B中n個求交,計算次數為時間復雜度為O(mn); 但是AABB包圍盒可以將減少每次排除相交的計算量: AABB包圍盒只需要最多9次計算可以排除相交,而Devillers算法在排除相交時,最少需要進行43次計算.實驗結果表明,采用AABB包圍盒,相比直接進行三角形相交測試,可以減少30%左右的計算時間.

(3) AABB樹

采用層次包圍盒算法時,考慮理想情況下,包圍盒與一棵n個葉子的二叉樹求交時,每次在兩個子節點中只與一個相交,則只需要次查詢,因此層次包圍盒算法的時間復雜度為O(mlog2n).在實際的二叉樹建立過程中,由于包圍盒的位置隨機分布,導致建立的二叉樹平衡性較差,復雜度高于到log2n級別.3與4的對比顯示,采用AABB樹可以降低計算耗時的量級.

(4) 優化的AABB樹

方法4與5的對比說明,采取空間劃分的方式對包圍盒進行二分,通過提高二叉樹的平衡性,可以優化AABB樹的結構,從而降低求交的次數.實驗表明,采取優化的AABB樹,相比不優化情況下碰撞檢測的時間降低60%以上.

(5) 并行計算

方法6采用并行方法進行計算,利用多個線程,進行二叉樹構建、AABB樹的碰撞檢測.本次實驗中,并行方法可以將計算耗時降低30%左右.

2.2 算法應用

將該快速碰撞檢測算法應用于CFETR的部件檢測中,所得計算結果如圖6所示.

在實際工程設計中通常使用建模軟件CATIA進行數字化建模、碰撞檢測,因此本文選擇CATIA的碰撞計算結果進行對比.CATIA的計算結果如圖7所示.

碰撞計算結果的對比顯示,快速檢測算法給出的碰撞區域與CATIA計算結果基本一致.CATIA計算碰撞時計算區域的交線,而算法簡化為計算碰撞的三角面對,大幅提高效率的同時,能夠給出可靠的結果.

在實際設計計算中,有限元模型的網格數量往往在百萬、千萬量級,此時算法的處理效率更加重要.

本文通過將模型B進行網格重,衡量算法處理大規模網格時的性能.

模型的網格面數量和計算耗時對比如表3所示.

圖6 算法的碰撞計算結果

圖7 CATIA的碰撞計算結果

表3 大規模網格計算的性能比較

實驗結果表明,本文提出的快速檢測算法在處理復雜有限元網格時,相比CATIA的計算,效率上存在明顯優勢.將本文提出的算法應用在聚變堆工程設計中,可以大幅縮短計算時間,提高了工程設計的效率.

3 結論

針對工程設計中存在的有限元模型碰撞問題,本文設計并實現了一種基于三角形相交檢測、AABB包圍盒的快速碰撞檢測算法,通過采用三角形的Devillers算法、優化的AABB樹和并行化設計,實現高效的碰撞檢測.將算法應用于聚變堆形變部件檢測,測試結果表明,本算法在計算效率、處理大規模網格方面都取得了良好的效果.

在進一步的工作中,該算法將被集成至CFETR集成設計平臺,為支持聚變堆設計提供快速的形變部件碰撞檢測功能.