3d - 确定 3D 点是否在三角形内

Question

给定一个 3D 点(x、y 和 z)和一个由其他三个 3D 点组成的三角形，我如何确定该点是否在三角形中？

我已经阅读了很多有关在 2D 中执行此操作的信息，最有帮助的是 http://imusthaveit.spaces.live.com/blog/cns!B5212D3C9F7D8093!410.entry ，但我正在努力将概念转移到 3D - 任何人都可以帮助提供一般概念或代码示例吗？

最终我想要做的是获得一个可以代表三角形内部的点列表。

Answer 1

给定点 P 和三角形 A、B、C，计算:

1. the unit normal of triange (A, B, P)  - call it N1
2. the unit normal of triangle (B, C, P) - call it N2

(正确排序!)

现在考虑点积 N1*N2。如果 P 在三角形的平面内，并且在三个边内，则这些法线应该平行，所以这个点积将为 1.0000(或 0.999...)。如果 P 保持在平面内但移动到边 BC 之外，则这两条法线将相反:N1*N2==-1。如果 P 不在平面上，则点积将是某个中间值。哎呀，我们还有一个漏洞——如果 P 越过 CA 侧。我们需要再计算一个:

3.  the unit normal (C,A,P) called N3

进行这两个测试(在理想情况下):

N1*N2 == 1.0 ?
N2*N3 == 1.0 ?  

(测试N3*N1是多余的)当然，由于计算机算法的不完善，测试必须允许有一些偏差。寻找 (N1*N2 > 1-epsilon)，其中 epsilon 是某个小值，具体取决于所需的精度和浮点类型。

您可能需要这些单位法线的公式。给定 (A,B,C) 计算叉积 N =(B-A)x(C-B)。然后除以 sqrt(N*N)。 “点积”和“叉积”的定义很容易在教科书和维基百科等中找到。可以通过一些代数将性能提高到大约平方根。

我不认为这是最快的算法，但应该可行(直到如此