浏览全部资源
扫码关注微信
收稿：2018-02-07，
修回：2018-7-11，
纸质出版：2018-12-16
移动端阅览
目的
2
碰撞检测是虚拟现实，特别是虚拟装配中的关键技术。针对基于包围盒的碰撞检测算法的准确性和检测效率不足的问题，提出一种结合AABB轴对齐包围盒和空间划分的碰撞检测算法。
方法
2
本文算法采用分步检测的方法，利用AABB算法来确定两包围盒的相交区域后，结合模型移动方向和运动趋势进行空间划分，利用碰撞检测的时空相关性，对时空相关的部分进行相交测试，通过将包围盒还原成三角面以及点的方式来保证检测的准确性。
结果
2
本文算法与AABB层次包围盒二叉树算法、
$$k$$
-Dops包围盒算法以及BPS空间分割树算法进行对比实验分析。在碰撞的几何精度上，本文算法在大部分情况下与AABB算法和
$$k$$
-Dops算法的距离差超过阈值0.02，证明本文算法在碰撞几何精度上有明显的提高。在碰撞检测时耗上，随着碰撞检测难度的不断增加，本文算法在平移自由度下比AABB算法和BSP算法、在旋转自由度下比AABB算法和
$$k$$
-Dops算法的检测时间均降低了50%以上。在三角面数对算法碰撞检测时耗的影响上，当运动模型的三角面数较多时，本文算法表现出更高的稳定性。
结论
2
结合AABB包围盒和空间划分方法的碰撞检测算法，在减少碰撞检测所需时间的同时提高了碰撞检测的准确性，可以满足虚拟装配技术中对碰撞检测算法准确性的要求，同时也能满足使用者实时性的交互习惯。
Objective
2
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 irregular 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
2
The proposed algorithm utilizes a step-by-step 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
2
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 the same 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
2
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.
Cecil J, Jones J. VREM:an advanced virtual environment for micro assembly[J]. International Journal of Advanced Manufacturing Technology, 2014, 72(1-4):47-56.[DOI:10.1007/s00170-014-5618-9]
Smith A, Kitamura Y, Takemura H, et al. A simple and efficient method for accurate collision detection among deformable polyhedral objects in arbitrary motion[C ] //Virtual Reality Annual International Symposium. Research Triangle Park, NC: IEEE, 1995: 136-145.[ DOI: 10.1109/VRAIS.1995.512489 http://dx.doi.org/10.1109/VRAIS.1995.512489 ]
Palmer I J, Grimsdale R L. Collision detection for animation using sphere-trees[J]. Computer Graphics Forum, 1995, 14(2):105-116.[DOI:10.1111/1467-8659.1420105]
Gottschalk S, Lin M C, Manocha D. OBBTree: a hierarchical structure for rapid interference detection[C ] //Proceedings of the 23rd annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1996: 171-180.[ DOI: 10.1145/237170.237244 http://dx.doi.org/10.1145/237170.237244 ]
Kay T L, Kajiya J T. Ray tracing complex scenes[J]. ACM Siggraph Computer Graphics, 1986, 20(4):269-278.[DOI:10.1145/15886.15916]
Xing Y S, Liu X P, Xu S P. Efficient collision detection based on AABB trees and sort algorithm[C ] //Proceedings of IEEE ICCA 2010. Xiamen: IEEE, 2010: 328-332.[ DOI: 10.1109/ICCA.2010.5524093 http://dx.doi.org/10.1109/ICCA.2010.5524093 ]
Chang J W, Kim M S. Efficient triangle-triangle intersection test for OBB-based collision detection[J]. Computers&Graphics, 2009, 33(3):235-240.[DOI:10.1016/j.cag.2009.03.009]
Pan Z K, Li J B. Collision detection algorithm based on compressed AABB tree[J]. Computer Science, 2005, 32(2):213-215.
潘振宽, 李建波.基于压缩的AABB树的碰撞检测算法[J].计算机科学, 2005, 32(2):213-215. [DOI:10.3969/j.issn.1002-137X.2005.02.059]
Fang B, Wang Z L, Guo X W. Four-dimensional space and time hierarchical collision detection method based on AABB bounding box[J]. Computer Measurement&Control, 2014, 22(2):397-399, 420.
方彬, 王竹林, 郭希维.基于AABB的四维时空层次包围盒碰撞检测方法[J].计算机测量与控制, 2014, 22(2):397-399, 420.[DOI:10.3969/j.issn.1671-4598.2014.02.027.]
Jin Y X, Qin Z P, Li Z. Deformation collision detection algorithm fusing R-Sphere bounding volume[J]. Computer Engineering and Design, 2017, 38(1):92-96.
靳雁霞, 秦志鹏, 李照.融合R-Sphere包围球的变形体碰撞检测算法[J].计算机工程与设计, 2017, 38(1):92-96.[DOI:10.16208/j.issn1000-7024.2017.01.018]
Hu Y M. A hybrid collision detection algorithm based on bounding volume hierarchy[J]. Computer Engineering and Science, 2012, 34(6):127-130.
胡咏梅.基于层次包围盒的混合碰撞检测算法[J].计算机工程与科学, 2012, 34(6):127-130. [DOI:10.3969/j.issn.1007-130X.2012.06.025]
Li L, Zhang Y J. A survey on algorithms of non-negative matrix factorization[J]. Acta Electronica Sinica, 2008, 36(4):737-743.
李乐, 章毓晋.非负矩阵分解算法综述[J].电子学报, 2008, 36(4):737-743. [DOI:10.3321/j.issn:0372-2112.2008.04.023]
Zhang P, Du G L. A fast continuous collision detection algorithm based on K_DOPs[C ] //Proceedings of 2011 International Conference on Electronics, Communications and Control. Ningbo: IEEE, 2011: 617-621.[ DOI: 10.1109/ICECC.2011.6066778 http://dx.doi.org/10.1109/ICECC.2011.6066778 ]
Sun J G, Wu S H. Collision detection algorithm based on ellipsoid bounding box and spatial decomposition[J]. Computer Engineering and Applications, 2016, 52(4):217-222.
孙劲光, 吴素红.基于空间分割与椭球包围盒的碰撞检测算法[J].计算机工程与应用, 2016, 52(4):217-222. [DOI:10.3778/j.issn.1002-8331.1405-0105]
Wang W, Zhou C, Yang Y, et al. Virtual maintenance-oriented collision detection algorithm[J]. Computer Applications and Software, 2016, 33(4):235-238.
王崴, 周诚, 杨云, 等.面向虚拟维修的碰撞检测算法[J].计算机应用与软件, 2016, 33(4):235-238. [DOI:10.3969/j.issn.1000-386x.2016.04.055]
Song T, Shu T, Mei C, et al. A collision detection algorithm based on spatial partitioning and hybrid bounding box[J]. Fire Control&Command Control, 2016, 41(11):94-97.
宋涛, 舒涛, 梅朝, 等.基于空间分解与混合包围盒的碰撞检测算法[J].火力与指挥控制, 2016, 41(11):94-97. [DOI:10.3969/j.issn.1002-0640.2016.11.022]
相关作者
相关机构
京公网安备11010802024621
