«上一篇
 文章快速检索 高级检索

 哈尔滨工程大学学报  2018, Vol. 39 Issue (10): 1695-1701  DOI: 10.11990/jheu.201701036 0

引用本文

TANG Yuanhao, HOU Jin, WU Tingting, et al. Hybrid collision detection algorithm based on particle conversion and bounding box[J]. Journal of Harbin Engineering University, 2018, 39(10), 1695-1701. DOI: 10.11990/jheu.201701036.

文章历史

Hybrid collision detection algorithm based on particle conversion and bounding box
TANG Yuanhao, HOU Jin, WU Tingting, GONG Sui, ZHANG Juan, ZHONG Litao
School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756, China
Abstract: To improve the efficiency of collision detection, this paper presents a collision detection algorithm based on particle conversion and bounding box. The algorithm first makes use of the binary tree and regional center to construct an oriented bounding box (OBB) for all objects in space, then expresses objects separated by a certain distance as a physical particle. The outermost OBB of the object was considered as a dot in a three-dimensional space, so as to calculate the distance between two objects. This distance was determined using the result of dot calculation and distance of reduction, so that the dot that did not pass the test was not detected again, while the dot that passed the validation was reduced. Finally, the OBB intersection test was carried out on the reduced bounding box. The results showed that the proposed algorithm can effectively improve collision detection efficiency compared with its predecessor algorithm, and can further reduce the time and cost of the increased space, especially for the complicated environment where a large number of objects exist in the space.
Keywords: collision detection    regional center    binary tree    OBB hierarchical bounding box    particle conversion    particle reduction

1 质点转换和包围盒混合法总体描述

2 质点转换和包围盒混合法原理 2.1 OBB层次包围盒的构建

 Download: 图 2 不同包围盒的构造 Fig. 2 The structure of the different bounding boxes

 $\mathit{\boldsymbol{A}} = \left[ {\begin{array}{*{20}{c}} {{\mathop{\rm cov}} \left( {x, x} \right)}&{{\mathop{\rm cov}} \left( {x, y} \right)}&{{\mathop{\rm cov}} \left( {x, z} \right)}\\ {{\mathop{\rm cov}} \left( {x, y} \right)}&{{\mathop{\rm cov}} \left( {y, y} \right)}&{{\mathop{\rm cov}} \left( {y, z} \right)}\\ {{\mathop{\rm cov}} \left( {x, z} \right)}&{{\mathop{\rm cov}} \left( {y, z} \right)}&{{\mathop{\rm cov}} \left( {z, z} \right)} \end{array}} \right]$ (1)

 Download: 图 4 包围盒构建图 Fig. 4 The structure of hierarchical bounding box

2.2 质点转换

 ${x_j} = \frac{{{x_i}}}{s}$ (2)
 ${y_j} = \frac{{{y_i}}}{s}$ (3)
 ${z_j} = \frac{{{z_i}}}{s}$ (4)

2.3 质点还原

 ${L_{xi}} = \frac{{|{x_{{i_1}}} - {x_{i{a_1}}}{\rm{|}}}}{s} + \frac{{{\rm{|}}{x_{{i_2}}} - {x_{i{a_2}}}|}}{s}$ (5)
 ${L_{yi}} = \frac{{|{y_{{i_1}}} - {y_{i{a_1}}}{\rm{|}}}}{s} + \frac{{{\rm{|}}{y_{{i_2}}} - {y_{i{a_2}}}|}}{s}$ (6)
 ${L_{zi}} = \frac{{|{z_{{i_1}}} - {z_{i{a_1}}}{\rm{|}}}}{s} + \frac{{{\rm{|}}{z_{{i_2}}} - {z_{i{a_2}}}|}}{s}$ (7)

 ${L_{xj}} = |{x_{{j_1}}} - {x_{{j_2}}}|$ (8)
 ${L_{yj}} = |{y_{{j_1}}} - {y_{{j_2}}}|$ (9)
 ${L_{zj}} = |{z_{{j_1}}} - {z_{{j_2}}}|$ (10)

1) 选择空间中相同大小包围盒数目相对较多的物体将其包围盒定义为单位包围盒；

2) 根据选择好的单位包围盒，确定质点转换中所需的转换系数；

3) 根据确定好的转换系数，利用质点转换公式把空间中包围盒全部转换为空间中的一个点；

4) 对空间中运行的点进行还原距离的计算；

5) 对空间两点的间0距进行计算；

6) 最后通过对两点间还原距离和间距之间的比较判断该质点是否还原为包围盒。

2.4 OBB层次包围盒相交测试

1) 对物体A的最外层包围盒A1和物体B的最外层包围盒B1进行分离轴定理相交测试，测试结果两包围盒相交。

2) 使A1和物体B的第一层子包围盒B2、B3进行相交测试，测试结果A1和B3相交。

3) 使A1和物体B的第一层子包围盒中的B3的子包围盒B6、B7进行相交测试，测试结果A1和B6相交，因为图中为两层子包围盒的层次包围盒所以经过三次测试确定本次碰撞的物体B的终端节点包围盒B6

4) 根据确定的终端节点包围盒B6对物体A的层次包围盒进行遍历，首先使B6和物体A的第一层子包围盒A2、A3进行相交测试，测试结果B6和A2相交。

5) 使B6和物体A的第一层子包围盒中的A2的子包围盒A4，A5进行相交测试，测试结果B6与A5相交，那么可以确定本次碰撞的物体A的最终节点包围盒A5

6) 通过前面相互遍历的相交测试能够知道两物体的最终节点包围盒B6和A5相交，那么就可以判定两物体发生了碰撞。

3 实验结果与分析

 Download: 图 9 显示包围盒的两物体碰撞图 Fig. 9 Two objects collide with bounding boxes