确定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是多余的)当然,测试必须允许一些slop来解决计算机算术的不完善问题.寻找(N1*N2> 1-epsilon)其中epsilon是一个小值,取决于所需的精度和浮点类型.

您可能需要这些单位法线的公式.给定(A,B,C)计算叉积N =(BA)x(CB).然后除以sqrt(N*N)."dot product"和"cross product"的定义很容易在教科书和维基百科等中找到.有可能通过一些代数来增加性能到大约平方根.

我不认为这是最快的算法,但应该工作(直到这样

Answer 2

你真的在谈论三角形的3个点或金字塔的4个点吗？

单个点极不可能完全位于3d空间中的平面三角形平面上.

编辑:

作为三角形版本的想法(因为它似乎你想要).您可以执行3x2D检查.从检查点和三个三角形点丢弃Z cooridinates,然后使用现有方法查看该点是否在平面中.然后不管只考虑X坐标,然后再忽略Y坐标.我敢肯定它不是最有效的方法,但编码很简单.

Answer 3

private bool PointInTriangle(Vector3[] TriangleVectors, Vector3 P)
    {
        Vector3 A = TriangleVectors[0], B = TriangleVectors[1], C = TriangleVectors[2];
        if (SameSide(P, A, B, C) && SameSide(P, B, A, C) && SameSide(P, C, A, B))
        {
            Vector3 vc1 = Vector3.Cross(Vector3.Subtract(A, B), Vector3.Subtract(A, C));
            if (Math.Abs(Vector3.Dot(Vector3.Subtract(A, P), vc1)) <= .01f)
                return true;
        }

        return false;
    }

    private bool SameSide(Vector3 p1, Vector3 p2, Vector3 A, Vector3 B)
    {
        Vector3 cp1 = Vector3.Cross(Vector3.Subtract(B, A), Vector3.Subtract(p1, A));
        Vector3 cp2 = Vector3.Cross(Vector3.Subtract(B, A), Vector3.Subtract(p2, A));
        if (Vector3.Dot(cp1, cp2) >= 0) return true;
        return false;

    }