如何知道线段在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

b:4、3、0

c:-3，-5、4

c: -3, -5, 4

线段:

d:1，-2、0

e:-2，6，2

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

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

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

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的体积为零，则Td的一个端点 段de位于包含三角形(a，b，c)的平面上.如果Td和Te的体积具有相同的符号， 那么de严格地位于一侧，并且没有交集.如果Td和Te相反 符号，然后越过包含(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)的体积.然后，只有三个符号都相同时，才与三角形(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).

如何根据四角的角坐标计算四面体的体积 网络，以及 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屋！