﻿ 基于AABB树的聚变堆形变部件碰撞检测算法
 计算机系统应用  2018, Vol. 27 Issue (11): 161-167 PDF

1. 中国科学技术大学 物理学院, 合肥 230027;
2. 中国科学院 等离子体物理研究所, 合肥 230031

Collision Detecting Algorithm for Deformable Components in Fusion Reactor Based on AABB Tree
DENG Jun-Sheng1, MAO Shi-Feng1, LIU Xu-Feng2, YE Min-You1,2
1. School of Physical Sciences, University of Science and Technology of China, Hefei 230027, China;
2. Institute of Plasma Physics, Chinese Academy of Sciences, Hefei 230031, China
Foundation item: National Magnetic Confinement Fusion Development Research Project of China (2014GB110002)
Abstract: To perform fast collision detection on the Finite Element Model (FEM) of deformable components in engineering design, an algorithm of collision detection based on the Axis-Aligned Bounding Box (AABB) tree is developed. For the FEMs to be checked, the facial surfaces are triangulated at first. AABBs are then generated for the triangles, and optimized AABB trees are built to divide the space. The AABBs and AABB tree are used to exclude disjoint graphics, and the Devillers & Guigue algorithm are applied to perform fast triangle intersection test. Parallel computing is also applied to accelerate the calculation. This proposed algorithm is applied for testing models, and the result shows that the efficient collision detection algorithm could give reliable result for complex FEMs.
Key words: collision detection     AABB tree     deforamable components     Finite Element Model (FEM)     engineering design     fusion reactor

1 碰撞检测算法

Step 1. 读取有限元计算结果, 提取模型的表面节点, 用三角片重构, 以三角形网格描述几何体的轮廓.

Step 2. 计算三角片对应的AABB包围盒, 将包围盒与三角形对应.

Step 3. 对包围盒集, 构造AABB树, 将所有包围盒存储在二叉树中.

Step 4. 对两棵AABB树中的包围盒进行碰撞检测. 如果包围盒间存在碰撞, 则继续检测包围盒对应的三角片的碰撞问题.

Step 5. 跳过未碰撞的包围盒、三角片, 记录所有碰撞的三角片对, 构成碰撞结果集.

 图 1 碰撞检测算法计算流程

Step 6. 结束计算, 将碰撞区域存储为STL (stereolithography, 立体光刻)格式的三角片模型文件.

1.1 包围盒算法

 ${{\rm{P}}_{\max }} = {x_{\max }}\vec i + {y_{\max }}\vec j + {z_{\max }}\vec k$ (1)
 ${{\rm{P}}_{\min }} = {x_{\min }}\vec i + {y_{\min }}\vec j + {z_{\min }}\vec k$ (2)

 $A \to ({x_{a - \min }},{x_{a - \max }})$ (3)
 ${\rm{B}} \to ({x_{{{b}} - \min }},{x_{b - \max }})$ (4)

 $({x_{a - \min }} > {x_{b - \max }})||({x_{a - \max }} < {x_{b - \min }})$ (5)

1.2 AABB树算法 1.2.1 层次包围盒与AABB树

AABB树是一种以二叉树存储的层次包围盒, 树的每个节点都是一个包围盒, 除叶节点外每个包围盒包含两个子盒; 所有叶节点为几何体的包围盒.

AABB树的层次包围盒结构如图2所示, 对应的二叉树存储结构如图3所示.

1.2.2 AABB树的构建

AABB树的构建流程如图4, 核心步骤如下文.

(1) 新建包围盒作为节点, 包含两个子节点的包围盒.

(2) 新包围盒向树中添加时, 与节点包围盒测试相交.

(3) 如果不相交则新建包围盒包裹当前节点和新包围盒并作为头结点, 当前节点和新包围盒作为子节点.

(4) 如果与其相交, 则首先新建大包围盒替换当前节点, 然后新包围盒与两个子节点合并, 选择合并后体积较小的节点, 进行迭代操作.

 图 2 层次包围盒示意图

 图 3 二叉树结构示意图

 图 4 AABB树构造流程

1.2.3 AABB树的碰撞检测

(1) 如果与节点不相交, 则该节点的所有子节点都不相交.

(2)如果包围盒与一个节点相交, 则继续与节点的两个子节点求交, 进行迭代直到叶节点. 理想情况下, 包围盒每次只与一个子包围盒相交, 相当于二分查找. 对于n个节点的树, 理想情况下的求交次数为logn级别.

1.2.4 AABB树的优化

(1)选择整个模型在xyz轴上最长的轴, 计算模型在该方向的最大值、最小值.

(2)将所有包围盒, 按照其在最长轴上的投影, 在最小值、最大值方向分成两组, 并尽可能保证平衡.

1.3 三角形相交检测

1.3.1 标量判别型的Möller算法

 ${{{N}}_1} \times (x - {V_{10}}){\rm{ = }}0$ (6)

Step 1. 计算 ${{\rm{T}}_2}$ 的三个顶点在 ${S_1}$ 平面方程的值.

Step 2. 如果 ${{\rm{T}}_2}$ 三点在 ${S_1}$ 平面同侧, 则不相交.

Step 3. 如果T2三点在 ${S_1}$ 平面上, 转换为共面三角形的相交计算. 如果一个点在面上, 且其它两点同号, 则计算该点是否在三角形内部; 如果两个点在面上, 计算线段与三角形的关系. 总之, 可以转换为平面内计算.

Step 4. 如果T2的三个顶点在 ${S_1}$ 的两侧, 则计算 ${{\rm{T}}_1}$ 的三个顶点与 ${S_2}$ 平面的关系.

Step 5. 经过排除计算, 只剩下 ${{\rm{T}}_1}$ 、T2在两侧的情况.

 $k = K \times i + O$ (7)

Möller算法的核心, 就是计算出三角形与k的交点的i值. 设T1和T2k的交点参数值分别为ijkl, 则区间(i, j)与(k, l)相交, 等价于三角形相交.

1.3.2 矢量判别型的Devillers算法

 $\left[ {{{a}},b,c,d} \right] = \left( {\begin{array}{*{20}{c}} {{a_x}}&{{a_y}}&{{a_z}}&1 \\ {{b_x}}&{{b_y}}&{{b_z}}&1 \\ {{c_x}}&{{c_y}}&{{c_z}}&1 \\ {{d_x}}&{{d_y}}&{{d_z}}&1 \end{array}} \right)$ (8)

Devillers算法不计算具体的交点坐标, 而是计算行列式的值, 进行相交判断. 如图所示得情况下, 循环置换顶点, 保证 ${{{V}}_{10}}$ ( ${{{V}}_{20}}$ )在面 ${S_2}$ ( ${S_1}$ )的一面, 同时交换V11V12( ${{{V}}_{21}}$ ${{{V}}_{22}}$ ), 保证 ${{{V}}_{10}}$ ( ${{{V}}_{20}}$ )在面的上方.

 $\left[ {{{{V}}_{10}}{{,}}{{{V}}_{11}}{{,}}{{{V}}_{20}}{\rm{,}}{{{V}}_{21}}} \right] \leqslant 0 \cap \left[ {{{{V}}_{10}}{\rm{,}}{{{V}}_{12}}{\rm{,}}{{{V}}_{22}}{\rm{,}}{{{V}}_{20}}} \right] \leqslant 0$ (9)
1.3.3 算法比较

(1)内存使用上, Möller算法使用55个变量, 而Devillers算法只需18个变量.

 图 5 三角形相交示意图

(2)在计算点与面的关系时, 面方程方法与行列式方法计算量相同; 两种算法的区别在处理三角形在两侧的场景下, Möller算法要求解四个坐标的值, 而Devillers算法只判断两个行列式大小, 后者计算量更小.

(3)排除不相交的三角形时, Möller算法进行三次排除, 而Devillers算法进行四次排除; 前两次排除的计算相同, Devillers算法在后面的排除中, 通过行列式的正负号排除, 比Möller算法效率更高.

1.4 并行优化

(1)根据计算机核心数确定线程数, 一般为 ${2^{{n}}}$ .

(2)将二叉树A, 从头结点开始迭代, 按左右节点拆分为2n棵子树.

(3)在每个线程中, 每棵子树与二叉树B进行碰撞检测; 全部计算结束后合并结果.

2 算法应用与分析

2.1 算法效率

(1)采用Möller算法遍历计算三角形相交.

(2)采用Devillers算法遍历计算三角形相交.

(3)在方法2基础上, 为三角形建立包围盒, 先对包围盒测试相交, 再计算三角形相交.

(4)在方法3基础上引入AABB树方法, 计算包围盒相交, 然后求解三角形相交.

(5)对方法4中AABB树的构建进行优化.

(6)在5基础上, 采用并行计算加速; 本文中选择4线程进行计算.

(1) 三角形相交算法

(2) AABB包围盒

(3) AABB树

(4) 优化的AABB树

(5) 并行计算

2.2 算法应用

 图 6 算法的碰撞计算结果

 图 7 CATIA的碰撞计算结果

3 结论

 [1] Wan YX, Li JG, Liu Y, et al. Overview of the present progress and activities on the CFETR. Nuclear Fusion, 2017, 57(10): 102009. DOI:10.1088/1741-4326/aa686a [2] Wan BN, Ding SY, Qian JP, et al. Physics design of CFETR: Determination of the device engineering parameters. IEEE Transactions on Plasma Science, 2014, 42(3): 495-502. DOI:10.1109/TPS.2013.2296939 [3] Song YT, Wu ST, Li JG, et al. Concept design of CFETR Tokamak machine. IEEE Transactions on Plasma Science, 2014, 42(3): 503-509. DOI:10.1109/TPS.2014.2299277 [4] Ye MY, Wang ZW, Mao SF, et al. Integration design platform of the CFETR. Fusion Engineering and Design, 2017, 123: 87-90. DOI:10.1016/j.fusengdes.2017.05.093 [5] Ye MY, Wang SJ, Mao SF, et al. Development of CFETR integration design platform: Modular structure. IEEE Transactions on Plasma Science, 2017, 45(3): 512-518. DOI:10.1109/TPS.2017.2655548 [6] Park SH, Kim JY, Park WW, et al. The effect of plastic deformation on low temperature mechanical and magnetic properties of Austenite 316LN tube for ITER TF conductor. IEEE Transactions on Applied Superconductivity, 2012, 22(3): 7800204. DOI:10.1109/TASC.2011.2176894 [7] 王振文, 徐华. 复杂场景中基于拓扑空间网格的碰撞检测算法. 计算机系统应用, 2017, 26(12): 116-123. [8] Curtis S, Tamstorf R, Manocha D. Fast collision detection for deformable models using representative-triangles. Proceedings of 2008 Symposium on Interactive 3D Graphics and Games. Redwood City, CA, USA. 2008. 61–69. [9] 吴峥, 谢叻, 马浩博. 虚拟手术实时物体碰撞检测和软组织变形研究. 计算机仿真, 2010, 27(2): 255-259. DOI:10.3969/j.issn.1006-9348.2010.02.061 [10] Van Den Bergen G. Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools, 1997, 2(4): 1-13. DOI:10.1080/10867651.1997.10487480 [11] 马登武, 叶文, 李瑛. 基于包围盒的碰撞检测算法综述. 系统仿真学报, 2006, 18(4): 1058-1061, 1064. DOI:10.3969/j.issn.1004-731X.2006.04.063 [12] 赵亮, 张义德, 胡旭晓. 基于网格包络的工业机器人仿真碰撞检测算法. 中国机械工程, 2017, 28(3): 316-321. DOI:10.3969/j.issn.1004-132X.2017.03.011 [13] 王晓荣, 王萌, 李春贵. 基于AABB包围盒的碰撞检测算法的研究. 计算机工程与科学, 2010, 32(4): 59-61. [14] Möller T. A fast triangle-triangle intersection test. Journal of Graphics Tools, 1997, 2(2): 25-30. DOI:10.1080/10867651.1997.10487472 [15] Guigue P, Devillers O. Fast and robust triangle-triangle overlap test using orientation predicates. Journal of Graphics Tools, 2003, 8(1): 25-32. [16] 邹益胜, 丁国富, 何邕, 等. 空间三角形快速相交检测算法. 计算机应用研究, 2008, 25(10): 2907-2909.