命运召唤尔茄的精...吧 关注:4,453贴子:98,191
  • 10回复贴,共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属地:陕西来自Android客户端5楼2024-11-30 10:45
        回复
          ?????这都是啥???完全看不懂啊


          IP属地:江苏来自Android客户端6楼2024-12-01 00:58
          收起回复
            这样好理解不


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


              IP属地:江苏来自Android客户端8楼2024-12-07 09:31
              回复
                有实力 什么时候全反编译出来了是不是可以直接做改版续作了


                IP属地:湖南9楼2024-12-10 18:41
                收起回复