碰撞检测算法

Tags:

碰撞检测算法,暴力解决是一个\( O(n^{2}) \)的过程:对于场景中的每一个obj都和所有其他的obj做相交测试。2个for循环解决问题,所以时间复杂度是\( O(n^{2}) \),这是最坏情况了。于是可以说,现在流传的各种碰撞检测算法的存在意义都是为了降低这个复杂度\( O(n^{2}) \)。

实际可用的碰撞检测算法,一般要分2个阶段:

  1. broad phase 快速找出潜在的碰撞物体对列表,不在这个列表里的是绝对没可能碰撞的。broad phase确定了一批需要进一步检查的物体对。

  2. narrow phase 准确找出发生碰撞的物体对列表。因为上一个阶段的部分物体对实际上是没有碰撞的,需要在这个阶段剔除。

broad phase用的数据结构不一定和narrow phase用的数据结构是同一个结构。

broad phase

分2个阶段的好处是,在第一个阶段,可以用不那么精确但快速的算法,找出潜在的碰撞物体。总好过直接就是应用narrow phase的精确但缓慢的算法去处理n个物体。更深刻的原因是,如果单个物体具有复杂的几何结构,那么narrow phase的计算开销非常大。

broad phase阶段的算法和需要的数据结构数据信息和narrow phase是不一样的。

broad phase阶段要求提供物体的包围盒信息,例如AABB盒。这就是broad phase为什么快但不精确的原因:物体的几何信息被近似地压缩了。

broad phase还要求把场景所有物体的包围盒信息放进一个数据结构(一般是一个树结构)中,例如插入到一个四叉树、八叉树、AABB树等。通过这个数据结构来实现快速相交判定。例如在Box2d中,是设计了一个proxy机制,每个场景物体对应唯一一个proxyAABB盒,这些proxyAABB盒就记录在一颗称之为Dynamic AABB Tree里,然后就可以做broad phase了。

broad phase其中有一个简单算法叫sweep and prune(SAP),本质上是利用了排序算法。第一步是初始化排序列表,列表中的元素是包围盒,可以用任意排序算法完成,例如快排;之后的排序就不是用快排了,而是用冒泡排序,为什么用冒泡排序更好呢?是因为一个默认的前提:物体的运动有时间相关性(temporal coherence),即当前帧和下一帧的位置是相近的,所以在冒泡排序过程中,发生的位置交换预期都很靠近。如果这个前提不成立,例如物体会经常发生远距离瞬移,那就不能用这种算法了。

narrow phase

相交判定算法

根据我的调研,在2维情况下,可以用SAT算法做任意凸多边形的碰撞检测,十分简单;但在3维情况下,只能GJK算法,因为SAT相对毕竟暴力、慢,以及GJK算法还有更多的SAT不具备的高级特性。另外,Box2D用的是GJK算法,所以证明了GJK算法是可以应用到2维情况的。除了SAT和GJK,还有一个sweep line算法可以求出多边形的相交点,此算法内部需要用到排序算法。

Separating Axis Theorem, SAT, 分离轴算法

GJK算法

用于做碰撞检测的场景管理树

这里讨论的场景管理树,只针对碰撞检测。

基于空间划分的八叉树

一般说到场景管理,都会想到四叉树(八叉树的简化)、八叉树,这种基于空间划分的结构,然而,基于空间划分的树,会遇到一个十分蛋疼的问题:物体可能会overlap边界。这种情况,有几种可行的处理方案:

  1. Loose OCTree,松散八叉树。

大概就是说,空间划分后的各个cell bound,各对应一个loose bound(relaxing the bounds slightly!),loose bound应是cell bound的两倍大小,这个loose bound可以保证完全包含cell bound里的所有物体的包围盒。这是个重要的性质,比如说如果有一个物体的包围盒刚好和cell bound一样大,但是物体包围盒中心点刚好在cell bound里,那么此时可以保证loose bound仍然能完全包含物体包围盒。

有了这个性质后,根据任意物体的包围盒中心点,决定把它放进哪个cell的列表里。即不会出现一个物体同时存在于2个cell的情况。然后查询相交时,就好办了,只需要根据query point确定要检查的cell,不过缺点是,如果query point处于多个loose bound的重叠区域,就需要这些loose bound的cell都做一次相交判定。

  1. 允许内部节点存物体的OCTree。overlap了边界的物体,通通丢到父节点去。

  2. 允许一个物体同时存进多个叶子节点的OCTree。这种方案主要是怕出bug,因为2个叶子节点都存了这个物体。需要严格管理好节点的增删,防止出现不一致性。

另外,还有一个问题是:当大量物体集中于一个cell。此时八叉树基本就废了,退化成了\( O(n^{2}) \)级别的算法了。

因此我觉得,八叉树适合处理的场景是,物体分布均匀、静态物体较多、动态物体较少的情况。

btDbvt - Dynamic AABB Tree

这个btDbvt数据结构是从Box2D、Bullet源码中发现的,并且Box2D在注释里写到Box2D的Dynamic AABB Tree是参考了Bullet的,那么可以知道Bullet的Dynamic AABB Tree才是根源。

更让人激动的是,Bullet的官网有介绍这个数据结构的资料

btDbvt是一个基于物体集合划分的二叉树,注意和八叉树的区别,八叉树是基于空间划分的。btDbvt另一个性质是,它考虑到了时间相干性,这也是这个数据结构更适合物体引擎的原因,因为物理世界里,物体不会发生瞬移。

时间相干性是用了一个fatBound的机制体现的,大概意思是,每个物体的proxyBound都会比实际的Bound大那么一点,当物体移动时,如果移动后的没有超过fatBound范围,那么不会发生节点的移动。从而降低树的更新频率。

先贴出算法伪代码:

场景管理树的比较

(未经授权禁止转载)
Written on May 10, 2017

博主将十分感谢对本文章的任意金额的打赏^_^