结合轴对齐包围盒和空间划分的碰撞检测算法

Collision detection algorithm based on AABB bounding box and space division

目的碰撞检测是虚拟现实,特别是虚拟装配中的关键技术。针对基于包围盒的碰撞检测算法的准确性和检测效率不足的问题,提出一种结合AABB轴对齐包围盒和空间划分的碰撞检测算法。方法本文算法采用分步检测的方法,利用AABB算法来确定两包围盒的相交区域后,结合模型移动方向和运动趋势进行空间划分,利用碰撞检测的时空相关性,对时空相关的部分进行相交测试,通过将包围盒还原成三角面以及点的方式来保证检测的准确性。结果本文算法与AABB层次包围盒二叉树算法、k-Dops包围盒算法以及BPS空间分割树算法进行对比实验分析。在碰撞的几何精度上,本文算法在大部分情况下与AABB算法和k-Dops算法的距离差超过阈值0. 02,证明本文算法在碰撞几何精度上有明显的提高。在碰撞检测时耗上,随着碰撞检测难度的不断增加,本文算法在平移自由度下比AABB算法和BSP算法、在旋转自由度下比AABB算法和k-Dops算法的检测时间均降低了50%以上。在三角面数对算法碰撞检测时耗的影响上,当运动模型的三角面数较多时,本文算法表现出更高的稳定性。结论结合AABB包围盒和空间划分方法的碰撞检测算法,在减少碰撞检测所需时间的同时提高了碰撞检测的准确性,可以满足虚拟装配技术中对碰撞检测算法准确性的要求,同时也能满足使用者实时性的交互习惯。

Objective Collision detection is a key technique applied in virtual reality,especially in virtual assembly.A collision detection algorithm based on an object space uses three-dimensional geometric features of the object for expansion and calculation.This phenomenon is evaluated by two methods,namely,a space division method and a bounding box method. The collision detection algorithm based on the bounding box method has attracted considerable attention and is widely used globally.The testing between the bounding boxes increases the possibility of collision detection errors.This condition can be explained by the use of an algorithm based on the axis-aligned bounding box (AABB)hierarchy binary tree that has many testing nodes but lowers detection efficiency in several cases.The space division method divides the entire virtual space into a sequence of equally sized cells and only detects objects in the same cell.The space division method is suitable for consistently distributed and sparse objects.The cells are divided into small sizes for cases with many objects and irregu-lar distribution.The intersection tests between the collections of cells reduce the collision detection speed and require considerable storage space.To solve the problems of traditional collision detection algorithms,this study proposes a collision detection algorithm based on AABB bounding box and space division.Method The proposed algorithm utilizes a step-bystep detection method.In the pre-detection phase of the algorithm,a bounding box is generated for each object in the scene.This method determines the intersection area of the two bounding boxes based on the AABB algorithm.Subsequently,the method divides the areas of intersections to conduct cross-tests on each planned area.The algorithm combines the direction and movement trend of the model to create a space division.The intersection of space-time related parts is evaluated based on the corresponding correlation of collision detection.In this algorithm,the spatial correlation of the object is used to reduce the detection range,which improves the efficiency of the algorithm.The transfer of bounding box into triangle surfaces and points is used to reduce detection errors.The algorithm refines the interference detection between the triangle plane and points.This process directly restores the collision detection between various models.In addition,the algorithm uses a rapid detection method to determine whether a set of points passes through a triangle or not.The detection method conducted in two steps obviously improves the efficiency of the collision detection algorithm.Result In the experiment,five typical experimental environments are established to compare the AABB hierarchical bounding box binary tree algorithm,k-Dops (discrete orientation polytopes)bounding box algorithm,and BPS (Binary Space Partitioning Tree)spatial segmentation tree algorithm.Two kettle models with a large number of triangular faces are used as the experimental model.The model has planes,surfaces,and rings,which can verify the advantages and disadvantages of the algorithm. The five experimental environments are built to evaluate the geometric collision accuracy,collision detection time loss in the translation degree of freedom and rotation degree of freedom,and the impact of the number of triangle faces on collision detection of the algorithm.In terms of geometric collision accuracy,six locations are randomly selected in performing collision detection.At thesame position,the algorithm is used to perform collision detection by using three traditional algorithms. The space difference between the three algorithms and the proposed algorithm is recorded.The distance between the proposed algorithm and AABB algorithm and the distance between the algorithm and k-Dops algorithm exceed the threshold of 0.02 in most cases.Visible visual gaps are observed when the distance exceeds 0.02.This finding proves that the algorithm remarkably improves the collision geometry accuracy.In terms of collision time consumption and collision detection difficulty,the proposed algorithm reduces the detection time by more than 50% in contrast to the AABB algorithm and BSP algorithm for the translation degree of freedom.Moreover,the proposed algorithm reduces the detection time by more than 50% in contrast to the k-Dops algorithm and AABB algorithm in the rotation degree of freedom.The experimental results show that the proposed algorithm attains superior performance in the calculation of collision detection for complex models. In terms of the influence of triangle number on the algorithm's collision detection time consumption,two groups of experiments are conducted in this study.We use a coordinate positioning method to ensure that each collision detection position is the same and the required time for each collision detection in the current position is obtained.In the first set of experiments,a teapot model with 530 faces is set as the dynamic model,and a model with different number of faces is set as the static model.In the second group of experiments,a teapot model with a face number of 530 is set as the static model,and a model with different number of faces is set as the dynamic model.The experiment result shows that the computational time cost of the proposed algorithm is less than those of the AABB algorithm and the BSP algorithm when collision detection occurs at the same location.The proposed algorithm shows high stability when the triangle number of the motion model is large.The algorithm reduces the detection scope to reduce the cost and improves the detection efficiency of the algorithm and the geometric accuracy of collision detection.Conclusion This study proposes a collision detection algorithm that combines the bounding box and space division methods.The proposed algorithm utilizes the advantages of the bounding box method,such as easy update,speed,compactness,and simple cross-section testing,to rapidly exclude the disjoint objects and determine the areas that may intersect.At the same time,the probability of model collision in the same partition space is increased using the space division method.The space division method reduces the collision detection time and invariably improves the collision detection accuracy.The proposed algorithm is suitable in virtual assembly technology field,which can increase its accuracy and can satisfy the real-time interaction of the users.