Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (4): 149-153.DOI: 10.3778/j.issn.1002-8331.2011.04.041

• 图形、图像、模式识别 • Previous Articles     Next Articles

Fast collision detection based on improved honeycomb-shape spatial decomposition

LIU Xiuling,LIU Jing,WANG Hongrui,GUO Lei   

  1. Department of Electronic and Informational Engineering,Hebei University,Baoding,Hebei 071002,China
  • Received:2010-06-02 Revised:2010-08-06 Online:2011-02-01 Published:2011-02-01
  • Contact: LIU Xiuling


刘秀玲,刘 京,王洪瑞,郭 磊   

  1. 河北大学 电子信息工程学院,河北 保定 071002
  • 通讯作者: 刘秀玲

Abstract: Real-time and accurate collision detection research has become a hot research problem in the field of virtual reality.In this paper,an improved honeycomb-shape spatial decomposition collision detection algorithm based on image space is proposed.The non-collision polyhedron is first removed and the collision polyhedron is partially and spatially decomposed.Then back-projection is used to build local sub-collision bounding box and to complete the honeycomb-shape space decomposition.So the collision detection is converted to measure the distance from the cross-section in the sub-cellular space polyhedron of next frame to the threshold line of the other party.This algorithm gets rid of the constraints of graphics hardware,and makes the detection algorithm based on image space fit for arbitrary polyhedra.It improves the speed and accuracy of collision detection.

Key words: collision detection, honeycomb-shape spatial decomposition, back-projection, threshold line

摘要: 目前高速、精确的碰撞检测研究已经成为了虚拟现实领域研究的热点。在图像空间的碰撞检测研究基础上,设计了基于蜂窝状空间分解的碰撞检测算法。首先完成非碰撞多面体的快速剔除,对碰撞多面体局部进行空间分解,进而,反向投影构建碰撞模型局部子包围盒,完成沿相反方向进行子包围盒蜂窝状空间分解,将碰撞检测转化为判断在下一帧中多面体蜂窝子空间内局部子多面体截面到对方阈值线的距离值与对方所设定阈值大小的关系问题,完成任意多面体间的精细碰撞检测。摆脱了图形硬件信息存储的限制,也使基于图像空间的碰撞检测适用于任意多面体,提高了碰撞检测的速度和精度。

关键词: 碰撞检测, 蜂窝状空间分解, 反向投影, 阈值线

CLC Number: