如何知道线段是否与 3d 空间中的三角形相交? [英] How to know IF a line segment intersects a triangle in 3d space?

问题描述

我有一个由 3d 空间中的 3 个点定义的三角形.我还有一个由 3d 空间中的 2 个点定义的线段.我想知道它们是否相交.我真的不需要知道交点.

I have a triangle defined by 3 points in 3d space. I also have a line segment defined by 2 points in 3d space. I want to know if they intersect. I don't really need to know the point of intersection.

我不会任何微积分，但我知道一些三角函数.我对矩阵有一些了解，但我很了解向量(特别是 3d 向量).请保持简单.

I don't know any calculus but I know some trig. I know some about matrices but I understand vectors well (3d vectors specifically). Please keep it simple.

你能帮我解决示例问题吗:

Can you walk me through the example problem:

三角形:

a: -4, 3, 0

a: -4, 3, 0

b: 4, 3, 0

c: -3, -5, 4

c: -3, -5, 4

线段:

d: 1, -2, 0

d: 1, -2, 0

e: -2, 6, 2

e: -2, 6, 2

我将在 C++ 物理引擎中使用它.

I am going to use this in a c++ physics engine.

一个答案涉及从 4 个顶点计算四面体体积.请提供公式或在代码中显示.

One answer involved tetrahedron volume calculation from 4 vertices. Please provide formula or show it in code.

更新:

正如 meowgoesthedog 指出的那样，我可以尝试使用 Moller-Trumbore 交叉算法.请参阅下面我的回答以获取替代解决方案.

As meowgoesthedog pointed out, I could try to use the Moller-Trumbore intersection algorithm. See my answer below for an alternate solution.

推荐答案

这是解决问题的一种方法.计算四面体的体积 Td =(a,b,c,d) 和 Te = (a,b,c,e).如果 Td 或 Te 的体积任一为零，则段 de 位于包含三角形 (a,b,c) 的平面上.如果 Td 和 Te 的体积符号相同，然后 de 严格地位于一侧，并且没有交叉点.如果 Td 和 Te 有相反的符号，然后 de 穿过包含 (a,b,c) 的平面.

Here is one way to solve your problem. Compute the volume of the tetrahedron Td = (a,b,c,d) and Te = (a,b,c,e). If either volume of Td or Te is zero, then one endpoint of the segment de lies on the plane containing triangle (a,b,c). If the volumes of Td and Te have the same sign, then de lies strictly to one side, and there is no intersection. If Td and Te have opposite signs, then de crosses the plane containing (a,b,c).

有几种策略.一种是计算 de 交叉的点 p那架飞机.然后投影到2D，解决2D的三角点问题.

From there there are several strategies. One is to compute the point p where de crosses that plane. Then project down to 2D, and solve the point-in-triangle problem in 2D.

另一种方法是计算四面体 (a,b,d,e)、(b,c,d,e) 和 (c,a,d,e) 的体积.那么只有当三个都具有相同的符号时，de 才与三角形 (a,b,c) 相交.

Another route is to compute the volumes of the tetrahedra (a,b,d,e), (b,c,d,e), and (c,a,d,e). Then only if all three have the same sign, does de intersect the triangle (a,b,c).

如何从角坐标计算四面体的体积到处都是web，以及C 中的计算几何.

How to compute the volume of a tetrahedron from its corner coordinates is all over the web, and also in Computational Geometry in C.

这篇关于如何知道线段是否与 3d 空间中的三角形相交?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！