本文主要是介绍计算机图形学入门games103——碰撞检测,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一.怎么发现碰撞,有没有碰撞
碰撞最难的是布料的碰撞
碰撞检测分为两个部分:
第一阶段:去除不可能发生碰撞的元素,输出的就是可能碰撞的备选目标,这阶段叫做碰撞剔除
这常用的套路有两种:第一种是Spatial Hashing,第二种是BVH(Bounding Volume Hirearchy)
Spatial Hashing:
将整个空间划分成很多的小区域,对每一个元素在空间上的分布存入进去,存储后,做相交检测就很容易了,如下图所示,我要想知道t3和哪一些其他的三角形有可能相交,我只需要搜寻t3存在哪些小区域中,这些小区域中有哪些其它的三角形就可以了,这里就有t0和t5
那么如果是运动的话,只要根据运动轨迹,将轨迹上的小区域都存进去就可以了,这样的问题是存储量太大了,而且事先我并不知道要存入多少三角形,而且有大量的可能是空的 这个解决方法就是先存入序列,然后再根据小区域的顺序进行排序,这样可优化内存,对每一个区域存入一个开始和结束的位置,我需要知道几号区域有三角形,直接访问几号区域的开始指针就可以了
这样的话还有一个问题,内存的访问不够连续,无法有效利用到缓存的优势,内存访问的跨度会很大,这样下来有一个新的套路,对整个空间进行细分,优化整个数据访问的连续性
这里有一个基于空间划分的方法进行碰撞的教程例子,英伟达在GPU上对于碰撞的实现
BVH(Bounding Volume Hirearchy):
有别于对于空间进行划分,对于一个有规律的物体,我们可以根据物体的结构进行划分,也就是包围盒的方法,我们可以通过包围盒做一些筛选,快速剔除不会发生碰撞的元素对,基于小的包围盒,我可以从上至下做一个层级的包围盒,,这样在和外部物体以及内部检测方面都会很方便,如下是一个简单的例子
自上而下一个一个的遍历过来,那么对于自相交的处理,比如说对于整体的节点,我们可以通过递归的方式来检测有没有自相交,然后检测子节点有没有相交,然后检查子节点的子节点
包围盒有很多种,其中比较容易也比较常见的就是AABB包围盒,不需要进行数值计算,只需要进行一个大小的比较就可以了,用的最多的就是AABB这种横平竖直的包围盒,但是这种方法很难做和近邻的相交,这个方法使用了能量剔除的方法,特别是对于弹性体使用这个是比较好的
两种方法对比的话,空间划分的方法写起来相对还比较容易,对于GPU也比较友好,但是计算资源的消耗是比较高的,若是包围盒的代码写起来就比较麻烦,对于GPU也不太友好,因为是树的结构,但是这种方法更新起来比较容易
第二阶段:根据处理可能分为连续的检测和离散的检测,这部分输出真正发生碰撞的对象进行检测
离散的检测:
这其实真正检测的是相交,对于边和三角形是否相交,DCD没有运动的概念,并不是真正的检测碰撞,相交和碰撞是有区别的,没有相交不等于没有碰撞,物体如果运动的比较快的话,可能就检测不到相交
连续的检测:
也就是真正的碰撞检测算法,那么对于一个三角形而言,我们需要检测的就是状态之间点—三角形,边—边的检测
做连续的碰撞检测计算量要比离散的要大一些,当然,连续的碰撞检测计算量只是模拟的小头,不用太在意,写起来也比较复杂,在游戏中大家使用的更多是DCD,也就是离散的碰撞检测,除非需要特别高的精度,如果是在手术模拟这种需要满足实时性的碰撞检测的时候,也大多使用DCD离散的碰撞检测
2.内点法
在我们发现碰撞了之后,我们需要怎么处理,内点法的处理思路是。我保证我的点一直在合理区域内,一直去接近最优解(这样比较慢),永远可以成功
实现方法,步长的选择很重要,每走一步都要进行碰撞检测
3.冲击区优化
这个就是直接不断优化不安全的结果到安全的结果,比较快,只需要集中优化一个区域就可以了,但有可能在步长很大的情况下失败
4.离散碰撞
当我发现有可能发生碰撞,我就回到前一帧,封住整个区域,下面是实现连续碰撞的思路
相交处理:
对于有体积的物体来说,如果有相交,把物体推出去就可以了,例如之前球和布料的模拟,或者那个弹性体的模拟
这篇关于计算机图形学入门games103——碰撞检测的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!