Determine if a 3D point is within a triangle

Question

Given a 3D point (x, y & z), and a triangle made of three other 3D points, how can I determine if the point is in triangle?

I've read a lot about doing this in 2D, the most helpful being http://imusthaveit.spaces.live.com/blog/cns!B5212D3C9F7D8093!410.entry, but I'm struggling to move the concept to 3D - could anyone help with either the general concept or code example?

Ultimately what I'm wanting to do is obtain a list of points that can represent the interior of the triangle.

Answer 1

Are you really talking about 3 points of a triangle or 4 points of a pyramid?

A single point is extremely unlikely to ever exactly be on the plane of a flat triangle in a 3d space.

EDIT:

As an idea for the triangle version (as it seems you want). You could perform 3x2D checks. Discard the Z cooridinates from your check point and the three triangle points, then see if the point is in the plane using your existing method. Then do the same disregarding just the X coordinate and then again disregarding just the Y coordinate. I'm sure its not the most efficient method, but it will be simple to code.

Answer 2

The method described here is very good for the 2D case. I think it is possible to modify this to work in 3D. This doesn't directly answer your question, but if you understand this method you should be able to work out how to modify it for 3D (if that is possible).

Answer 3

1. Use the three points of the triangle to calculate the equation of the plane in which they lie
2. Check if your point satisfies that equation.

Answer 4

Given a 3D point P and three vertices of a triangle T1, T2, T3

• Find the plane through the three points T1, T2, T3
• Find the closest point on the plane to P (project P onto the plane)

Now you can transform all the points to the 2D problem of finding a point in the triangle. Also the distance of P to the plane will tell you how close the point is to being exactly on the triangle.

If I understand your elaboration correctly you are planning to examine all the voxels in your 3D grid to find out if they are in a given triangle? This would be very inefficient - I think a 3D version of Bresenham's line algorithm may work for what you want to do. It would be trivial to find the voxel that T1 is in, then progress through the voxels towards T2, repeating for T3 and back to T1.

Answer 5

Given point P and triangle A, B, C, compute:

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

(get the order right!)

Now think about the dot product N1*N2. if P is in the plane of the triangle, and inside the three sides, those normals should be parallel, so this dot product will be 1.0000 (or 0.999...). If P is kept in the plane but moved beyond side BC, those two normals will be opposite: N1*N2==-1. If P isn't in the plane, the dot product will be some intermediate value. Whoops, we still have a loophole - if P goes out past side CA. We need to compute one more:

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

Make these two tests (in an ideal world):

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

(testing N3*N1 is redundant) Of course, the test will have to allow some slop for the imperfections of computer arithmetic. Look for (N1*N2 > 1-epsilon) where epsilon is some small value, depending on accuracy needed and floating point types.

You may need a formula for these unit normals. Given (A,B,C) compute the cross product N =(B-A)x(C-B). Then divide by sqrt(N*N). Definitions of "dot product" and "cross product" are easy to find in textbooks and wikipedia etc. It is possible to increase performance with some algebra to about square roots.

I don't claim this is the fastest algorithm, but should work (until so

Answer 6

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;

    }