如何为球形物体和三角形地形提供高效的碰撞检测和响应？

Question

我一直在尝试在物体和地形之间进行有效的碰撞检测。对象由移动球体表示，地形由静态三角形组成。
到目前为止，我成功地实现了一个碰撞算法，但它有一些主要问题：
1. 非常耗资源
2.碰撞只对三角形的一侧有效
3. 多次同时碰撞会产生不良结果。
下面是我的算法。它基于 realtimecollisiondetection.net 的一篇文章，并且使用了 GLM 数学库。我简化了循环、变量名、不必要的代码和 class 成员：

//Class definitions:  
class Sphere
{
     public:
     float x;
     float y;
     float z;
     float radius;
     float sqradius;
     float xmov;
     float ymov;
     float zmov;
};
class TriangularWall
{
     public:
     float x[3];
     float y[3];
     float z[3];
     glm::vec3 Normal;
};

using namespace glm; 
Sphere Obj;
TriangularWall Wall;
//Assume that the 2 objects above are constructed. I didn't include their constructors because they looked ugly. 
float rr=Obj.sqradius;  
vec3 A=vec3(Wall.x[0], Wall.y[0], Wall.z[0])-vec3(Obj.x, Obj.y, Obj.z);  
vec3 B=vec3(Wall.x[1], Wall.y[1], Wall.z[1])-vec3(Obj.x, Obj.y, Obj.z);
vec3 C=vec3(Wall.x[2], Wall.y[2], Wall.z[2])-vec3(Obj.x, Obj.y, Obj.z);  
vec3 V=cross(B-A, C-A);  
float d=dot(A, V);  
float e=dot(V, V);  
float di=d;  
float ei=e;
vec3 Ai;
vec3 Bi;
vec3 Ci;
vec3 Vi;
if(!(di*di>rr*ei))
{
      float aa=dot(A, A);
      float ab=dot(A, B);
      float ac=dot(A, C);
      float bb=dot(B, B);
      float bc=dot(B, C);
      float cc=dot(C, C);
      if(!(aa>rr && ab>aa && ac>aa))
      if(!(bb>rr && ab>bb && bc>bb))
      if(!(cc>rr && ac>cc && bc>cc))
      {
            vec3 AB=B-A;
            vec3 BC=C-B;
            vec3 CA=A-C;
            float d1=ab-aa;
            float d2=bc-bb;
            float d3=ac-cc;
            float e1=dot(AB, AB);
            float e2=dot(BC, BC);
            float e3=dot(CA, CA);
            vec3 Q1=A*e1-d1*AB;
            vec3 Q2=B*e2-d2*BC;
            vec3 Q3=C*e3-d3*CA;
            vec3 QC=C*e1-Q1;
            vec3 QA=A*e2-Q2;
            vec3 QB=B*e3-Q3;
            if(!(dot(Q1, Q1)>rr*e1*e1 && dot(Q1, QC)>0)
            if(!(dot(Q2, Q2)>rr*e2*e2 && dot(Q2, QA)>0)
            if(!(dot(Q3, Q3)>rr*e3*e3 && dot(Q3, QB)>0)
            {
                  vec3 ObjectMov=vec3(Obj.xmov, Obj.ymov, Obj.zmov);
                  if(dot(ObjectMov, Wall.Normal)<0)
                  ObjectMov-=dot(ObjectMov, Wall.Normal);
                  Obj.xmov=ObjectMov [0];
                  Obj.ymov=ObjectMov [1];
                  Obj.zmov=ObjectMov [2];
            }
      }
}

对于第三期，我重新做了上面的算法（如果仍然发生碰撞，只需将物体停在相应的轴上）。但是，这会显着加载程序，并且不会产生很好的效果。
我也知道我可以对上面的算法进行一些性能调整，但我没有看到任何可以显着提高性能的东西。
我知道我也可以使用八叉树，但是它们对我来说似乎很复杂，而且我也担心它们在某些情况下会造成很多延迟。
因此，有什么方法可以改进我使用的算法以解决其主要问题吗？或者我应该尝试使用另一个？

Answer 1

假设你所说的"resource consuming"太高了运行-时间，那么三角形的数量肯定是很大的。所以首先要做的是减少要测试的三角形的数量。

你提到了八叉树。更一般地说，边界体积的层次结构是可行的方法。 (https://en.wikipedia.org/wiki/Bounding_volume_hierarchy.)百万个三角形的加速将是巨大的。在您的特定情况下，我可能会选择边界球的二叉树。

注意，在实现这个之前，你已经通过预先计算每个三角形的边界球来获得加速（球的中心是外接圆的中心，即中介平面与平面的交点三角形）。然后通过比较中心之间的距离与半径之和来检测非相交三角形。

关于球体与三角形的精确交集测试，恐怕天下没有免费的午餐。使用 "inflating/deflating" 方法，球体的中心可以位于三角形上方的直棱柱内、边缘周围的三个截短圆柱体之一或顶点周围的三个球体之一。

无论采用何种方法，您都必须处理案例分析的复杂性。

如何为球形物体和三角形地形提供高效的碰撞检测和响应？

How to provide efficient collision detection and response for spherical objects and triangular terrain?

c++

collision-detection

computational-geometry

glm-math