命运召唤尔茄的精...吧 关注:4,453贴子:98,181
  • 3回复贴,共1

多边形的连续碰撞检测真是麻烦

取消只看楼主收藏回复

个人demo里的平面几何算法纯属个人创作、优化,应该有比我更快的。
如果只是质点,质点的移动轨迹(扫掠形)就是线,连续碰撞检测就是线段与线段相交,点碰撞在交点;在地形上移动为单接触点移动。
下图,线段相交算法 cpu tick(通过rdtsc指令读取)平均为52/次

而下图,到地形索引块碰撞上几乎乘以20,当然普通速度不会这么巨大

以平常跑步速度为例如下图,【不跨索引块】,地形部分只有一条多段线,如下图,tsc为300多

以平常跑步速度为例如下图,【跨索引块】,地形部分只有一条多段线,如下图,tsc会比上面多25%左右

-----------------------------------------------------------------------------------------------------------------------------------------------
而线段的移动轨迹(扫掠形)是平行四边形,连续碰撞检测就是段线扫掠段线(多段线简化),线段碰撞扫掠距离最短点,直接看下图,文字表达太烦;在地形上移动为1~2接触点移动。
凸多边形的话,只取移动方向上的边,其移动轨迹(扫掠形)是多段线的移动构成的一并的平行四边形,连续碰撞检测就是多段线扫掠多段线,多段线碰撞扫掠距离最短点,直接看下图,文字表达太烦;在地形上移动为1~2接触点移动。

线段扫掠碰撞算法 cpu tick(通过rdtsc指令读取)平均为122/次,原理上讲符合线段相交的3倍左右

而目前卡在讨人厌额与地形索引块融合的阶段,质点根据索引块边界任一时刻只会属于一个索引块,凸多边形则会占据多个,想要性能好真麻烦。估计最优要到3000~4000 tick


IP属地:江苏1楼2024-11-30 02:25回复
    请忽略GJK耗时这么多,因为之前的写法是重合较多时最快,还可以写成重合一点点时最快


    IP属地:江苏2楼2024-11-30 02:31
    收起回复
      此电脑cpu单核频率3.4Ghz,意味着1纳秒(ns) == 3.4cpu tick,1微秒(us) == 3.4k cpu tick,1豪秒(us) == 3.4m cpu tick,1秒(us) == 3.4g cpu tick


      IP属地:江苏4楼2024-11-30 02:45
      回复
        这样好理解不


        IP属地:江苏7楼2024-12-03 18:25
        回复