改进的混合包围盒碰撞检测算法研究

doi:10.16182/j.issn1004731x.joss.201811023

系统仿真学报 ›› 2018, Vol. 30 ›› Issue (11): 4236-4243.doi: 10.16182/j.issn1004731x.joss.201811023

改进的混合包围盒碰撞检测算法研究

王超¹, 张志利¹, 龙勇², 王韶迪¹

1.火箭军工程大学导弹工程学院,陕西西安 710038;
2.航天科工系统仿真科技有限公司,北京 100095

收稿日期:2018-05-27 修回日期:2018-06-25 发布日期:2019-01-04

Improved Hybrid Bounding Box Collision Detection Algorithm

Wang Chao¹, Zhang Zhili¹, Long Yong², Wang Shaodi¹

1.Missile Engineering Academy, Rocket Force Engineering University , Xi'an 710038, China;
2.China Aerospace Science and Engineering System Simulation Technology Company Ltd, Beijing 100095, China

Received:2018-05-27 Revised:2018-06-25 Published:2019-01-04

摘要/Abstract

摘要： 针对方向包围盒(OBB)构造耗时长,场景碰撞检测算法效率不高的问题,提出了一种快速自适应的混合包围盒碰撞检测算法,优化了包围盒的层次结构和存储方式,通过八叉树空间分割和包围球的粗检测排除大量不可能相交的物体,再对可能相交的对象作OBB包围盒的精确相交测试。实验结果表明,改进的算法较经典的OBB算法相比,降低了包围盒构造的复杂度,且场景中物体数越多,碰撞检测的精确度越高。

关键词: 碰撞检测, 空间分割, 混合包围盒, 包围球, 方向包围盒

Abstract: For the construction of the oriented bounding box (OBB) takes a long time and the efficiency of the scene collision detection algorithm is not high, a fast-adaptive hybrid bounding box collision detection algorithm is proposed, which optimizes the bounding box of hierarchy and the way of storage. A large number of objects that cannot be intersected are excluded by means of the eight-tree space division and the rough detection of the sphere, and the exact intersecting test of the OBB can be made. The experimental result shows that compared with the OBB algorithm, the complexity of the bounding box construction is reduced, and the more the number of objects in the scene, the higher the accuracy of collision detection.

Key words: collision detection, space division, hybrid bounding box, spheres, oriented bounding box (OBB)

中图分类号:

TP391.9

王超, 张志利, 龙勇, 王韶迪. 改进的混合包围盒碰撞检测算法研究[J]. 系统仿真学报, 2018, 30(11): 4236-4243.

Wang Chao, Zhang Zhili, Long Yong, Wang Shaodi. Improved Hybrid Bounding Box Collision Detection Algorithm[J]. Journal of System Simulation, 2018, 30(11): 4236-4243.

参考文献

[1] Pi Xuexian, Yang Xudong, Li Sikun.High-perform ance navigation and rendering of very-largescale landscape and seascape[C]//Computer A ided Design and Computer Graphics,2005 Ninth International Conference, 2005.
[2] SONG Tao, SHU Tao, MEI Zhao, et al.A Collision Detection Algorithm Based on Spatial Partitioning and Hybrid Bounding B[J]. Firepower and Command Control (S1002-0640), 2016, 41(11): 94-97.
[3] JIANG Guangyan.Research and Application of Collision Detection Algorithm Based on Bounding Box [D]. Chengdu: University of Electronic Science and Technology of China, 2012.
[4] M Teschner, S Kimmerle, B Heidelberger, et al.Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs[J]. IEEE Transactions on Visualization & Computer Graphics (S1077-2626), 2002, 4(1): 21-36.
[5] LAI K-C, KANG S-C.Collision detection strategies for virtual construction simulation[J]. Automation in Construction(S0926-5805), 2009, 18(6): 724-736.
[6] GAN Jianhong, PENG Qiang, DAI Pei-dong, et al.Improved Collision Detection Algorithm Based on Oriented Bounding Box[J]. Journal of System Simulation(S1004-731X), 2010, 23(10): 2169-2173.
[7] DIMITORY D, KNAUER C, KRIEGEL K, et al.Bounds on the quality of the PCA bounding boxes[C]. Computational Geometry: Theory and Applications. Amsterdam: Elsevier, 2009, 42(8): 772-789.
[8] WANG Wei, MA Jun, LIU Wei.Research and Application of Collision Detection Based on Oriented Bounding Box[J]. Computer Simulation (S1006-9348), 2009, 26(9): 180-183.
[9] YU Haijun, MA Chunyong, ZHANG Tao, et al.Fast collision detection algorithm based on image space[J]. Journal of Computer Applications (S1001-9081), 2013, 33(2): 530-533.
[10] CHEN Chen, ZHANG Weiming, CHU Ning.Optimized collision detection algorithm based on bounding volume hierarchy and triangular facets[J]. Manufacturing Technology and Machine Tools (S1005-2402), 2013.
[11] Wang Wei, Zhou Cheng, Yang Yun, et al.Virtual Maintenance-oriented collision detection algorithm[J]. Computer Applications and Software (S1000-386X), 2016, 33(4): 235-238.
[12] GUO Lingyun, ZHENG Yanbin, LIU Jingjing.Fast collision detection algorithm based on spatio--temporal correlation[J]. Computer Applications and Software (S1000-386X), 2013, 30(5): 174-176.
[13] JIANG Xiaolu, LIU Yuan.New collision detection algorithm based on hybrid hierarchical bounding box[J]. Computer Engineering and Applications (S1002-8331), 2012, 48(6): 143-145.
[14] SHI Xusheng, QIAO Lihong, ZHU Zuowei.Algorithm of Collision Detection Based on Improved Orieted Bounding Box[J]. Journal of Hunan University(Natural Sciences)(S1674-2974), 2014, 41(5): 26-31.

改进的混合包围盒碰撞检测算法研究

Improved Hybrid Bounding Box Collision Detection Algorithm

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics

本文评价

[1]	舒亮, 张洁, 杨艳芳, 杨秒, 吴自然. 考虑节拍约束的断路器孪生车间模型动力学控制[J]. 系统仿真学报, 2021, 33(6): 1277-1287.
[2]	孙小晴, 程昊, 张潞瑶, 季伟东, 王旭. 一种基于空间分割搜索策略的自然计算方法[J]. 系统仿真学报, 2021, 33(11): 2589-2605.
[3]	贾春洋, 邹湘军, 李锦慧, 曾泽钦, 王杰. 虚拟环境下的复杂变速箱交互式装配仿真平台[J]. 系统仿真学报, 2020, 32(9): 1736-1743.
[4]	薛俊杰, 施国强, 周军华, 曲慧杨, 陶栾, 蒲睿英. 复杂产品三维模型轻量化服务构建技术[J]. 系统仿真学报, 2020, 32(4): 553-561.
[5]	解翠, 耿俊美, 李健, 董军宇. 压缩性骨折内固定手术仿真[J]. 系统仿真学报, 2019, 31(7): 1351-1357.
[6]	李星, 傅妍芳, 王亮, 陆承涛. 基于射线检测的动态碰撞优化算法[J]. 系统仿真学报, 2019, 31(11): 2393-2401.
[7]	石敏, 王俊铮, 毛天露, 刘亚宁. 基于物理的可交互性虚拟服装动画模拟[J]. 系统仿真学报, 2018, 30(7): 2583-2592.
[8]	景乾峰, 神和龙, 尹勇, 刘秀文. 航海模拟器中的岸线实时碰撞检测[J]. 系统仿真学报, 2018, 30(7): 2682-2688.
[9]	李照, 靳雁霞, 秦志鹏, 任超. 基于优化Snake模型的变形物体碰撞检测算法研究[J]. 系统仿真学报, 2018, 30(1): 62-68.
[10]	刘复昌, 王双建, 潘志庚, 王金荣. 并行化碰撞检测算法综述[J]. 系统仿真学报, 2017, 29(11): 2601-2608.
[11]	薛传宇, 董洪伟, 张明敏, 潘志庚. 一种基于人体胖瘦模型的穿衣实时仿真方法[J]. 系统仿真学报, 2017, 29(11): 2847-2855.
[12]	汪军, 刘冬. 一种胆囊切除虚拟手术仿真训练平台研究[J]. 系统仿真学报, 2016, 28(8): 1853-1862.
[13]	刘璐, 刘箴, 何高奇, 陈田, 刘婷婷, 刘翠娟. 一种基于DirectCompute加速的实时流体仿真框架[J]. 系统仿真学报, 2016, 28(10): 2467-2475.
[14]	刘良平, 刘箴, 方昊, 刘翠娟, 刘婷婷. 基于GPU的三维场景表面流体碰撞检测方法研究[J]. 系统仿真学报, 2015, 27(10): 2439-2445.