I've been trying to make efficient collision detection between objects and terrain. The objects are represented by mobile spheres and the terrain is made of static triangles.
So far, I managed to implement a collision algorithm, but it has some major issues:
1. It's very resource-consuming.
2. Collision only works on one side of the triangles.
3. Multiple, simultaneous collisions give bad results.
Below I've put the algorithm that I have. It's based on an article from realtimecollisiondetection.net, and it's using the GLM math library. I've simplified loops, variable names, unnecessary code and class members:
//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];
}
}
}
For the third issue, I re-made the above algorithm (simply stopping the object on the corresponding axis if a collision still takes place). However, this loads up the program significantly, and doesn't produce that nice effects.
I'm also aware that I could include a few performance tweaks to the algorithm above, but I don't see anything that could improve performance by a significant margin.
I know that I could also use octrees, however they seemed pretty complicated to me and I'm also worried that they could, in some situations, create a lot of latency.
Therefore, is there any way to improve the algorithm I used in order to fix its main issues? Or should I just try to use another one?
Assuming that what you call "resource consuming" is too high running-time, the number of triangles must be significant. So the first thing to do is to reduce the number of triangles to be tested against.
You mentioned oct-trees. More generally, a hierarchy of bounding volumes is the way to go. (https://en.wikipedia.org/wiki/Bounding_volume_hierarchy.) Speedups will be tremendous for million triangles. In your particular case, I would probably opt for a binary tree of bounding spheres.
Note that before implementing this, you will already obtain a speedup by precomputing the bounding sphere of every triangle (the center of the sphere is the center of the circumscribed circle, i.e. the intersection of the mediator planes and the plane of the triangle). Then non-intersecting triangles are detected by comparing the distance between the centers to the sum of radii.
Regarding the exact intersection test between the sphere and a triangle, I am afraid that there is no free lunch. Using the "inflating/deflating" method, the center of the sphere can be inside either the right prism over the triangle, one of three truncated cylindres around the edges or one of three spheres around the vertices.
Whatever approach you take, you will have to deal with that complexity of the case analysis.