基于分类遍历的碰撞检测优化算法

doi:10.11772/j.issn.1001-9081.2015.01.0194

计算机应用 ›› 2015, Vol. 35 ›› Issue (1): 194-197.DOI: 10.11772/j.issn.1001-9081.2015.01.0194

基于分类遍历的碰撞检测优化算法

孙劲光¹, 吴素红²

1. 辽宁工程技术大学电子与信息工程学院, 辽宁葫芦岛125105;
2. 辽宁工程技术大学研究生院, 辽宁葫芦岛125105

收稿日期:2014-08-15 修回日期:2014-09-12 出版日期:2015-01-01 发布日期:2015-01-26
通讯作者: 吴素红
作者简介:孙劲光(1962-),女,辽宁阜新人,教授,博士,主要研究方向:数据挖掘、图形和图像处理、人脸识别;吴素红(1989-),女,辽宁沈阳人,硕士研究生,主要研究方向:计算机图形学.
基金资助:
国家科技支撑计划项目(2013BAH120f00).

Collision detection optimization algorithm based on classified traversal

SUN Jinguang¹, WU Suhong²

1. School of Electronic and Information Engineering, Liaoning Technical University, Huludao Liaoning 125105, China;
2. Graduate School, Liaoning Technical University, Huludao Liaoning 125105, China

Received:2014-08-15 Revised:2014-09-12 Online:2015-01-01 Published:2015-01-26

摘要/Abstract

摘要：

针对现有层次树遍历方法的低效率问题,提出了一种基于分类遍历的碰撞检测算法.首先根据两个物体树中节点的平衡因子差值来将所有的物体对进行分类:结构相似的,采用同步下降遍历方法;结构不相似的,采用交换下降遍历方法,这减少了相交测试的次数.然后加入时空相关性和优先级策略优化遍历过程.最后通过实验结果表明,相比基于统一遍历的碰撞检测算法,该算法缩短了相交测试的时间,物体数目越多,快速性优势越显著,大约可以缩减所需时间的1/5.

关键词: 碰撞检测, 层次包围盒, 分类遍历, 深度优先, 物体结构, 时空相关性

Abstract:

To solve the problem that present traversal methods of hierarchical tree which lead to low efficiency, a new collision detection algorithm based on classified traversal was proposed. Firstly, these objects were classified according to the difference between the balance factors of two tree' nodes. The simultaneous depth-first traversal method was applied to the objects which have similar structure, and the commutative depth-first traversal method was applied to the other objects, which reduced the number of intersect tests. Then, the process of traversal was optimized by using the temporal spatial coherence and priority strategy. Finally, the experimental results show that, compared with the collision detection algorithm based on unified traversal, the proposed algorithm shortens the time of the intersection test. The bigger the number of objects, the more significant the advantage of quickness, it can reduce about 1/5 of the required time.

Key words: collision detection, hierarchical bounding box, classified traversal, depth-first, object structure, temporal spatial coherence

中图分类号:

孙劲光, 吴素红. 基于分类遍历的碰撞检测优化算法[J]. 计算机应用, 2015, 35(1): 194-197.

SUN Jinguang, WU Suhong. Collision detection optimization algorithm based on classified traversal[J]. Journal of Computer Applications, 2015, 35(1): 194-197.

参考文献

[1] CHANG J, WANG W, KIM M. Efficient collision detection using a dual OBB-sphere bounding volume hierarchy [J]. Computer-Aided Design, 2010, 42(1): 50-57.
[2] JIMÉNEZ P, THOMAS F, TORRAS C. 3D collision detection: a survey [J]. Computers & Graphics, 2001, 25(2): 269-285.
[3] ZHANG L. The research and realization of collision detection in virtual reality [J]. Journal of Communication and Computer, 2011, 8: 693-696.
[4] STVVEL S A, MAGNENAT-THALMANN N, THALMANN D, et al. Hierarchical structures for collision checking between virtual characters [J]. Journal of Visualization and Computer Animation, 2014, 25(3/4): 333-342.
[5] SEILER C, PENNEC X, REYES M. Geometry-aware multiscale image registration via OBBTree-based polyaffine log-demons [C]// MICCAI'11: Proceedings of the 14th International Conference on Medical Image Computing and Computer-Assisted Intervention. Berlin: Springer, 2011: 631-638.
[6] KLOSOWSKI J T, HELD M, MITCHELL J S B, et al. Efficient collision detection using bounding volume hierarchies of k-DOPs [J]. IEEE Transactions on Visualization and Computer Graphics, 1998, 4(1): 21-36.
[7] XAVIER P G. A generic algorithm for constructing hierarchical representations of geometric objects [C]// Proceedings of the 1996 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 1996: 3644-3651.
[8] GREß A, GUTHE M, KLEIN R. GPU-based collision detection for deformable parameterized surfaces [J]. Computer Graphics Forum, 2006, 25: 497-506.
[9] ZHAO Y, GUO Q, WANG Y, et al. Interactive augmented reality method based on collision detection [J]. Journal of Wuhan University of Technology, 2010, 32(20): 160-163.(赵元杰,郭禾,王祎,等.增强现实技术中基于碰撞检测的交互性方法[J].武汉理工大学学报,2010,32(20):160-163.)
[10] DU P. Research on some key technologies for continuous collision detection between deformable models [D]. Hangzhou: Zhejiang University, 2013.(杜鹏.柔性物体连续碰撞检测若干关键技术研究[D].杭州:浙江大学,2013.)
[11] LU R, LIU H. A self-collision detection algorithm based on BVH of complete binary tree [J]. Computer Applications and Software, 2012, 29(12): 282-294.(陆睿,刘卉.基于完全二叉树BVH的自碰撞检测算法[J].计算机应用与软件,2012,29(12):282-294.)
[12] ZHU H. The teaching and research of balanced binary tree in data structure [J]. Journal of Chifeng College: Natural Science Edition, 2012, 28(3): 19-21.(朱洪浩.数据结构中平衡二叉树的教学探讨与研究[J].赤峰学院学报:自然科学版,2012,28(3):19-21.)
[13] LI H, ZHOU D, WU Y. Collision detection algorithm based on mixed bounding box [J]. Journal of Computer Applications, 2010, 30(12): 3304-3307.(李红波,周东谕,吴渝.基于混合包围盒的碰撞检测算法[J].计算机应用,2010,30(12):3304-3307.)
[14] JIANG J, FANG Z, XU J, et al. Improved collision detection on dual Sphere-OBB bounding volume hierarchy and its application [J]. Computer Engineering and Applications, 2011, 47(17): 172-174.(蒋健勋,方志刚,徐洁,等.基于Sphere-OBB的改进碰撞检测算法及其应用[J].计算机工程与应用,2011,47(17):172-174.)
[15] TANG M, LIN J, TONG R. Graphics hardware accelerated continuous collision detection between deformable objects [J]. Chinese Journal of Computers, 2010, 33(10): 2023-2027.(唐敏,林江,童若锋.图形硬件加速的柔性物体连续碰撞检测[J].计算机学报,2010,33(10):2023-2027.)

基于分类遍历的碰撞检测优化算法

Collision detection optimization algorithm based on classified traversal

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	曹堉, 王成, 王鑫, 高悦尔. 基于时空节点选择和深度学习的城市道路短时交通流预测[J]. 计算机应用, 2020, 40(5): 1488-1493.
[2]	王江坤, 何坤金, 曹红飞, 王金强, 张燕. 基于光滑粒子流体动力学方法的交互式水流加热仿真[J]. 计算机应用, 2020, 40(5): 1409-1414.
[3]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[4]	马梦莹, 曾雅丽, 魏甜甜, 陈志德. 基于邻居节点预状态的无线传感器网络故障诊断算法[J]. 计算机应用, 2018, 38(8): 2348-2352.
[5]	张忠林, 刘述昌, 江粉桃. 深层次分类中候选类别搜索算法[J]. 计算机应用, 2017, 37(3): 635-639.
[6]	李梓杨, 于炯, 卞琛, 王跃飞, 鲁亮. 基于负载感知的数据流动态负载均衡策略[J]. 计算机应用, 2017, 37(10): 2760-2766.
[7]	李丹妮, 刘奇, 田琪, 赵雷昱, 何凌, 黄韫栀, 张劲. 面向上颌骨骨折复位手术的虚拟系统设计[J]. 计算机应用, 2015, 35(6): 1730-1733.
[8]	陈美子王晓东李少博章联军. 高清立体视频的传输失真估计模型[J]. 计算机应用, 2014, 34(12): 3409-3413.
[9]	史玲玲王伟东闫志远. 虚拟手术中基于可变方向凸包的碰撞检测算法[J]. 计算机应用, 2013, 33(09): 2614-2616.
[10]	白宇郭显娥. 深度优先稳定原地归并排序的高效算法[J]. 计算机应用, 2013, 33(04): 1039-1042.
[11]	于海军马纯永张涛陈戈. 基于图像空间的快速碰撞检测算法[J]. 计算机应用, 2013, 33(02): 530-533.
[12]	唐朝伟李超群燕凯严鸣. 基于LISOMAP的相关向量机入侵检测模型[J]. 计算机应用, 2012, 32(09): 2606-2608.
[13]	向宇侯进徐芳吴铃. 分类应变限制下的服装仿真[J]. 计算机应用, 2012, 32(06): 1589-1593.
[14]	谢倩茹耿国华. 虚拟手术中的快速碰撞检测算法[J]. 计算机应用, 2012, 32(03): 719-721.
[15]	陈乃金. 基于深度优先贪婪搜索的可重构硬件任务划分算法[J]. 计算机应用, 2012, 32(01): 158-162.