简化球体的BSP剖分结构的快速碰撞检测  

Detection of simplified sphere BSP-trees structure for broad-phase collision

作　　者：于晓霞[1] 沈志刚[1] 

机构地区：[1]中山职业技术学院计算机工程系,广东中山528404

出　　处：《信息化纵横》2009年第5期69-72,75,共5页

摘　　要：在动态场景中,碰撞检测遇到的最明显的问题就是需要对N个物体对进行两两求交测试,其时间复杂度达到O(N2)。提出了一种简化球体的BSP剖分结构的快速碰撞检测算法。首先用一种调度算法估计BSP树开始失衡的地方,再用一种策略来选择分割面,新结构在表示动态场景中不需要重新构建树,而是在保持树的平衡和合理的高度的同时通过自身的调节来达到更新。The broad-phase step of collision detection in scenes composed of n moving objects is a challenging problem because enumerating collision pairs has an inherent O（N^2） complexity. In this paper we propose a new structure based on BSP tree for representing scenes composed of thousands of moving objects. An scheduling algorithm evaluates locations where the BSP-tree becomes unbalanced, uses several strategies to alter cutting planes, and defer updates based on their re-structuring cost. We show that the tree does not require a complete re-structuring even in highly dynamic scenes, but adjusts itself while maintaining desirable balancing and height properties.

关 键 词：碰撞检测 动态场景 BSP树 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]