jma*_*erx 54 algorithm 3d collision-detection data-structures
我总是想知道这一点.在像GTA这样的游戏中,有数以万计的物体,一旦你在健康包上,游戏怎么知道呢？
每个对象都不可能有一个事件监听器？迭代也不好？我只是想知道它是如何实际完成的.
cha*_*tar 60
对此没有一个答案,但是大型世界通常通过沿着四叉树或kd树的线使用某些东西来进行空间划分,这使得搜索时间能够在线性时间内找到最近的邻居(分数幂,或者最坏的O(N ^( 2/3))用于3D游戏).这些方法通常被称为BSP,用于二进制空间分区.
关于碰撞检测,每个物体通常还具有与其相关联的边界体积网格(形成凸包的多边形集合).这些高度简化的网格(有时只是一个立方体)不是绘制的,而是用于检测碰撞.最基本的方法是创建一个平面,该平面垂直于连接每个对象的中点的线与在线的中点处与线相交的平面.如果对象的边界体积在此平面的两侧都有点,则它是一个碰撞(您只需要测试两个边界体积中的一个相对于该平面).另一种方法是增强的GJK距离算法.如果您想要深入了解教程,请查看NeHe Productions的OpenGL课程#30.
毫无疑问,边界卷也可用于其他优化,例如所谓的遮挡查询.这是确定哪些对象在其他对象(遮挡物)后面的过程,因此不需要处理/渲染.边界体积也可以用于平截头体剔除,这是确定哪些物体在透视观察体积之外(太近,太远或超出视场角度)的过程,因此不需要渲染.
正如Kylotan所指出的那样,使用边界体积可以在检测到遮挡时产生误报,并且根本不能用于某些类型的物体(例如环形线圈)(例如,通过环形孔观察).像这样的对象被正确遮挡是门户网站剔除的另一个线程.