Detecting 3D Collisions

Question

I am currently working on a lwjgl project where I need to detect collisions between 3D triangles. I'm using OpenGL, and I'm seeking guidance on the most efficient and accurate way to achieve this.

To give you some context, I have a set of triangles defined by their vertices in 3D space, and I need to check for collisions between them.

I'm wondering if there are simpe and optimized algorithms that I can leverage to make this collision detection process. Additionally, if anyone has experience or knowledge regarding this specific problem, I'd greatly appreciate any insights or resources you can provide.

I have done some research on this topic for example this algorithm: https://cis.temple.edu/~lakaemper/courses/cis350_2004/etc/moeller_triangle.pdf, but still looking for a simpler, more practical and efficient solution. Any recommendations or code samples would be very helpful.

I already found the solution and described it below

Answer 1

Here's line - plane intersection test in 3D space

We have points: A(Ax, Ay, Az), B(Bx, By, Bz), C(Cx, Cy, Cz), P(Px, Py, Pz), Q(Qx, Qy, Qz).

That's an equation of a plane defined by 3 points A, B, C on it. ¯⁠\⁠_⁠(⁠ツ⁠)⁠_⁠/⁠¯

|x-A.x      y-A.y       z-A.z  |
|B.x-A.x    B.y-A.y     B.z-A.z| = 0 
|C.x-A.x    C.y-A.y     C.z-A.z|

And that paramedic equation of a line(i hope thats the right name (: )

t = (x-P.x)/(Q.x-P.x) = (y-P.y)/(Q.y-P.y) = (z-P.z)/(Q.z-P.z)

Combine these together to get intersection point:

|t(Q.y-P.x)+P.x-A.x   t(Q.y-P.y)+P.y-A.y    t(Q.z-P.z)+P.z-A.z  |
|B.x-A.x              B.y-A.y               B.z-A.z             | = 0
|C.x-A.x              C.y-A.y               C.z-A.z             |

    a = -(Px-Ax)*(By-Ay)*(Cz-Az) -
         (Py-Ay)*(Bz-Az)*(Cx-Ax) -
         (Pz-Az)*(Bx-Ax)*(Cy-Ay) +
         (Pz-Az)*(By-Ay)*(Cx-Ax) +
         (Px-Ax)*(Bz-Az)*(Cy-Ay) +
         (Py-Ay)*(Bx-Ax)*(Cz-Az);

    b = (Qx-Px)*(By-Ay)*(Cz-Az) +
        (Qy-Py)*(Bz-Az)*(Cx-Ax) +
        (Qz-Pz)*(Bx-Ax)*(Cy-Ay) -
        (Qz-Pz)*(By-Ay)*(Cx-Ax) -
        (Qx-Px)*(Bz-Az)*(Cy-Ay) -
        (Qy-Py)*(Bx-Ax)*(Cz-Az);

    a = b = 0 => ABC and PQ are in the same plane => infinite amount of intersection points
    b = 0 => A plane and a line do not intersect => no intersection

Now, find the point of intersection:

    t = a/b
    
    x = t(Q.x-P.x)+P.x
    y = t(Q.y-P.y)+P.y
    z = t(Q.z-P.z)+P.z

So if that point belongs to triangle ABC and line segment AB there is an intersection.

So you can repeat that process with every edge og the 2nd triangle to find the intersection between triangles.