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.

Antimatter

Can you give a bit more detail about why you want the list of point - after all it's a theoretically infinite list – Czardas

I've got a faceted representation of a 3D solid, what I'm trying to do is represent each facet within a 3D grid structure (a basic voxel representation). To do this, I need to be able to represent the facets (triangles) as a set of data points (for my given representation that is...) – Antimatter

Could you elaborate? You either want to see if a point is on a triangular plane or if the point is contained within a pyramid. Correct? – Marcellmarcella

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.

Listed

3 points of a triangle, not 4 points of a pyramid. That's what confusing me – Antimatter

Edited with an idea, but won't be efficient. – Listed

The 2D projects idea won't work. In Blender I could easily make a triangle and a point (a tiny sphere) where the point appears in the traingle in all three x, y, z projections but in a general view, is clearly not in the plane of the triangle. – Rochellrochella

I meant "projections" not "projects", duh. – Rochellrochella

Answer 2

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

Rochellrochella

This blows up if the point is exactly on the edge of the triangle, doesn't it? – Melgar

For future readers: This does blow up on the edges and corner points. Just check the lengths of the three cross products before normalizing. If any length is a zero (within an epsilon), the point is exactly on the boundary of the triangle. You can then decide if that should be considered inside or not. Otherwise i found this solution to be quite elegant. – Lionhearted

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;

    }

Folder

Great code, but I think the vectors need to be normalized before computing dot product and comparing it to 0.01f. – Harkey

Answer 4

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).

Lyceum

Thanks! You may not have answered his question, but this is exactly the answer I was looking for! – Earth

Great reference! Helps me a lot. – Injunction

Answer 5

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.

Abet

Answer 6

If you know the normal to the plane, which is the cross product of two of its edges, you can get rid of the axis suggested by the largest sub-co-ordinate of that normal and look at the triangle in the optimal orthographic plane. To do the test of the point inside the edges (or not), I found this very helpful.

http://jsfiddle.net/PerroAZUL/zdaY8/1/

The program is mostly about making things nice and easy but the algorithm you are looking for is contained in this method:

function ptInTriangle(p, p0, p1, p2) {
  var A = 1/2 * (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
  var sign = A < 0 ? -1 : 1;
  var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y) * sign;
  var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y) * sign;
  return s > 0 && t > 0 && (s + t) < 2 * A * sign;

}

Integration

Answer 7

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.

Tejeda

Good point. That would be point 3. However I'd suggest that the first stage that I described would eliminate a lot of cases. – Tejeda

Question is not whether it is in the same plane. Question is whether the point is inside the triangle. – Matelda

Every point on the plane the triangle is on satisfies that equation, even the points outside the triangle. – Integration

Answer 8

Just my observations for improvement on this (old) post. If you (pre-) compute the U&V vectors for the triangle (U being the vector from A to B and V being the vector from A to C in a standard triangle A-B-C, both U and V are not necessarily unit length) then the vector P (from A to the Point) can be used in the following way: compute dot product of P with U and P with V. If both dot products are less (or equal for point on edge) to one but larger (or equal) to zero and their sum is less than (or equal) to one , then the point is inside, otherwise it is outside. This approach is more efficient than to first compare the normals (cross products) and then also their dot products. This approach does not require that the points are in fact already in the order that form a right handed triangle and as such more stable. What it does require is that the point lies in the plane (or close to it) in order to be approximately accurate.

Jacquie