检测 3D 碰撞

Question

我目前正在开发一个 lwjgl 项目，我需要检测 3D 三角形之间的碰撞。我正在使用 OpenGL，并且正在寻求有关实现此目标的最有效和最准确方法的指导。

为了给您一些背景信息，我有一组由 3D 空间中的顶点定义的三角形，我需要检查它们之间的碰撞。

我想知道是否有简单且优化的算法可以用来进行此碰撞检测过程。此外，如果有人对这个特定问题有经验或知识，我将非常感谢您可以提供的任何见解或资源。

我对此主题做了一些研究，例如这个算法：https://cis.temple.edu/~lakaemper/courses/cis350_2004/etc/moeller_triangle.pdf，但仍在寻找一种更简单，更实用和高效的方法解决方案。任何建议或代码示例都会非常有帮助。

我已经找到了解决方案并在下面描述了

Answer 1

这是 3D 空间中的线-平面相交测试

我们有以下几点： A(Ax, Ay, Az), B（Bx，By，Bz）， C(Cx, Cy, Cz), P(Px, Py, Pz), Q(Qx, Qy, Qz).

这是由 3 个点 A、B、C 定义的平面方程。 ́\u2060_u2060(u2060ツu2060)u2060_u2060/u2060́

|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|

还有一条线的护理方程（我希望这是正确的名字（：）

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

将它们组合在一起以获得交点：

|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

现在，找到交点：

    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

因此，如果该点属于三角形 ABC 和直线线段 AB，则存在交点。

因此，您可以对第二个三角形的每条边重复该过程，以找到三角形之间的交点。