Real-Time Rendering (9) :碰撞检测

发表于2017-09-14
评论0 400浏览

想免费获取内部独家PPT资料库?观看行业大牛直播?点击加入腾讯游戏学院游戏程序行业精英群

711501594

提要

       碰撞检测(CD)在很多图形应用中都有着极其重要的角色,CAD/CAM,游戏动画,基于物理的建模,基本上所有的虚拟现实模拟都会用到,

      我们常说的CD其实指的是Collision handling,可以分为三个部分:Collision detection,Collision determination,Collision response。Collision detection阶段得到的是一个bool值,表示是否检测到碰撞,Collsion determination 是找到碰撞的部位,Collision response则决定碰撞的物体做出的反应。

       一个健壮的CD系统需要拥有下面的一些特性: 

1.能够处理大量多边形的交互,无论近距离还是远距离都能处理;

2.可以处理任意的多边形汤(polygon soups),它不一定保证是凸的,也不一定包含链接信息;

3.模型能够做刚体的运动,比如平移,旋转,或者其他更复杂的运动;

4.提供有效的包围体(Boundig volume),为几何体创建合适的BV能够提高算法的效率,当然BV的创建也要够快;

      一个大的游戏场景中可能有成百上千的运动物体,一个CD系统要能够处理这样的场景,如果场景中有n个运动的物体和m个静止的物体,那么每一帧要进行检测计算的次数就是:


首先是检测所有静止的物体和运行哦那个的物体是否有碰撞,然后是检测运动的物体之间的碰撞。这是最暴力的算法,m和n的大小直接关系到计算量。

实际应用中,不可能使用这样的计算,应为无法支付这样的性能代价,特别是在大的场景中。

注意下面要讨论的内容都指的刚体运动。


光线碰撞检测 Collision Detection  with Rays

        在一个赛车游戏中,一辆车奔驰在路上,在碰撞检测方面要做的就是车轮和路面的检测,非别检测每个轮子和地面mesh的碰撞,但有更简单有效的方法。

        将运动的物体近似成一组光线,对于上面的情形,我们可以在每个车轮上放一个光线,光线的原点就在轮子的最下端,当车辆只与地面进行接触的时候,这种近似非常有效。


         在车的运动过程中,不断检测光线到地面的距离distance,如果为0,则刚好在地面上,如果大于0,则车轮离开了地面,如果小于0,则车轮已经陷入地面了。通过计算distance,CD 系统还可以做出对应的碰撞处理,离开地面就落下来,陷入地面就升上去,如果场景更加复杂的话就要考虑更多的情况,比如要考虑车与墙面的碰撞,车于车之间的碰撞,就要在车体上放更多的光线了。

        加速算法方面,最常用的就是层级表示(hierarchical representation)。整个环境场景可以用axis-aligned BSP树来表示,然后接下来就是光线求交的问题了。

       在实际应用中,ray的原点通常不是在界面上,而是在物体里面,这样当轮子陷入地面的时候,就能够保证求得的distance为正值。


用DSP 树处理动态碰撞检测 Dynamic CD using BSP Trees

        线段和标准的BSP树能够很有效的检测到碰撞,一个线段可以表示一个点为从p0到p1,可能这个线段会和物体有很多交点,但第一个点就是就是这个线段与物体的碰撞点。注意在这种情况下BSP树是依附于物体表面(surface aligned)的,而不是平行轴(axis-aligned)的。如下图所示。每一个切面都和墙面或者地面平行。


       这种方式的检测很容易从质点扩展到球。只要将每个表面从法向向外扩展r。这样的话碰撞检测起来将是非常地快,而且对于不同半径的球体,BSP树都不用改变。假设场景中有个面的方程是 n·x d=0,那么对这个面进行调整之后为n·x d /-r=0. r还是-r取决于要检测的面 。

         游戏中的一个角色用一个球体来近似并不是那么合适,通常会用一个包围角色的凸包(convex hull)或者圆柱来代替。


层级碰撞检测 General Hierarchical Collision Detection

       这里要说的碰撞检测主要是关于两个模型的。每一个模型都用层级的Bounding volumes来代表,对应不同的BVs,上层的代码都是一样的。

       层级建树

       一种名为k-ary 树的数据结构在这里会用到,在树中每一个节点都有k个孩子,很多算法用的都是最简单的情况,也就是二叉树,即k=2,在树中的每个非叶子节点都代表着一个BV,包含着以它为根的所有子节点。对于任意点的的bunding volume记为ABV,A的所有子节点的集合记为Ac 。

      主要有三种建树的方法:自底向下(bottom-up),增量插入(incremental tree-insertion),自顶向下(top-down)。为了建立有效、进凑的结构,通常BV是越小越好,对于CD,肯定也是如此。

       自底向上的方法首先找到紧挨在一起的一组多边形,然后用BV将其包裹起来,然后不断地用新的BV去包裹老的BV,直到最后只有一个BV将整个物体都包住,这个BV也就是BVH树的根。

        增量插入地方法初始的时候是一棵空树,然后不断找出BV插入到树中,这种方法的难点是在插入的时候并不是简单地插入叶子节点,可能需要添加一个父节点,也就是一个父BV。

       自顶向下的方法是最常用的,初始的时候是一个单节点的树,这个节点是包含整个物体的BV,接下来要做的就是divide-and-conquer了。 将根分裂成k个部分,每个部分都生成一个BV将其包围起来,然后不断循环,到最后一个层级的BVH就建立了。

       CD算法的一个很大的挑战就是找到合适的BVs,还有就是一个高效平衡的树结构。记住平衡树是的最优的,因为每个叶子节点的深度都是一样的,这意味着查找叶子节点的时间基本相同,而碰撞检测的时间也就不会因为位置不同而出现很大的波动。但也有其他的情况,比如在某种情形下,某些部位经常会出现碰撞,则最好将其放在离树根比较近的叶子上,而有些部位基本不会发生碰撞,那么最好将其放在离根远的叶子上。

       碰撞检测算法

        最简单的情况是只判断两个物体是否相撞,则算法的停止条件就是范县有两个三角形有重叠。在下面的算法中,A和B是模型层级树的根节点,TA表示A的叶子节点,基本的思路就是当重叠出现的时候,打开BV,递归调用函数进行检测。

        

          算法中分了很多中情况,第一种是两个节点都是叶子节点的情况,第二种是两个节点都不是叶子的情况,最后是当两个节点有一个是叶子的情况。


       时间复杂度

             上面算法的复杂度主要由模型的BV和物体的运动。总的时间计算公式如下:


nv:BV/BV重叠测试数;cv:单个BV/BV重叠所耗费时间;

np:图形单元重叠测试数;cp:两个图形单元重叠所耗费时间;

nu:由于模型运动需要update的BV数量;cu:update一个bv所耗费的时间。


通过创建一个好的层级树可以减少一些时间复杂度,但有时候都是一些trade-off,比如如果使用比较简单的BV,检测的时间会减少,但BV就不是最优的了。


多物体碰撞检测系统 A Multiple Objects CD System

        在大的场景中的碰撞检测如果还是用上面的方法并不是很现实,特别是在时间复杂度要求高的情况下,比如游戏。下面要介绍的是一种两层的碰撞检测系统,目标是处理复杂的大型场景。第一级检测的是检测场景中可能发生碰撞的物体,得到的结果传到第二级,在第二级检测中实现具体物体的碰撞检测。


广义相碰撞检测 Broad Phase Collision Detection

        第一级检测的目标是尽量传递少的需要检测的物体到第二层,这是一个High-level的检测。

        算法的开始首先将每一个物体用一个BV包围住,然后用算法找到所有重叠的 BV/BV 。一个简单的方法是每个物体都用一个AABB来包围。为了防止BV的重新构造,AABB一定要足够大,能够包容住物体的刚体运动。划分好AABB之后,检测就可以很快的进行。

        除了Box,球体也可以使用,而且是合理的,因为球体可以包含物体任意方向的旋转。


扫描和修剪  Sweep and Prune

        这里假设每个物体都有一个AABB包围,在扫描修建算法中,使用了时间相干性(temporal coherence)。在这里,时间相干性质指的是物体在帧与帧之间的相对位置变化是相对小的,在这种情况下,上一帧所得到的碰撞检测结果可以用于下一帧的计算,这个特性也可以称为帧-帧相干性(Frame-to-frame coherence)。

         如果两个AABB是重叠的,那么这两个AABB在各个轴上的投影也是重叠的,将物体投影到坐标轴上,可以将一个三维的问题降低到三个轴上的一维问题,这就是 Sweep and Prune的核心思想。

1.将物体的AABB分离到三个坐标轴上。得到若干个区间。
2.根据区间的终点坐标由小到大排序。
3.逐个遍历排序结果,当遇到一个区间的起始点的时候,就将这个区间放到一个列表中;当遇到一个区间的终点时,就将这个区间从列表中清除。当在列表中存在区间,而又遇到一个新区间的起始点时,则遇到的区间与列表中的所有区间重叠。

4.如果一对物体在三个坐标轴上的区间都重叠,那么他们的AABB相叠。

注意,排序的算法最快可以到O(nlogn),找到覆盖的区间的复杂为O(k),则整个算法的复杂度为O(nlogn k)。由于时间的相干性,插入或者冒泡排序可以达到很高的效率,应为相对的重叠区域变化不会很大。

         最终的时间可以控制在线性的时间,但当出现clumping的时候,排序的时间复杂度可能退化到O(n^2),这时候我们可以绕过某个轴的检测,有时候这样做是可行的。

原文链接

著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引

游戏学院公众号二维码
腾讯游戏学院
微信公众号

提供更专业的游戏知识学习平台