Determine if point is inside triangle in 3D

In graphics, people usually use barycentric coordinates. In your case, P can be described as P = aV0 + bV1 + cV2, where a + b + c = 1 . P is inside if and only if 0 <= a, b, c <= 1.

If the triangles formed by v1, P, v2 has the area S1, the triangle formed by P, v0, v2 has the area of S2, and P, V0, V1 has the area of S3. Then a = S1/S, b = S2/S and c = S3/S, where S is the area of triangle V0, V1, V2.

To find the area of S = 1/2||(V0-V1)creosspdoruct(V0-V2)||.

You can check out the tutorial that I put on my website.

I'm a little bit late to the party (sorry), but here's my take on this:

I used to do ray-tracing in the 80's. At the time I came up with a solution that is rather similar to what you are discussing.

The idea is that is a point is always on the right side of an observer walking the edges of the triangle clockwise, then the point is inside the triangle.

For this we need a test to see if the point is on the right side of each edges. A cross product would be nice, but as it was pointed out, a cros product will give you a cos value. What you want is a sin, so you can reject points that have a negative test. This is why people tend to use a cross product instead. But a cross product require a lot more computation that a dot product (in the 80's that was really important!)

But we can transform the cos in a sin by a simple 90 deg rotation! So, instead of computing the dot product with the edge, we compute it with a line rotated 90 deg from the edge in the plane of the polygon.

At first that seem like a lot of trouble, but not if we work in one of the main planes. XY, YZ or XZ. So instead of working in 3D in the triangle's plane, lets work in 2D in one of the main planes. If a point is inside a polygon in 3D, it will also be inside it's projection on the 2D plane. Of course, if the polygon is parallel to one of the main planes we may have a problem if we project on the wrong plane.

So, to select this plane, just look at the triangle's normal and select the plane that is closer to the triangle's plane. If the X component is the biggest, we use the YZ plane etc... Also, the sign of that component will tell us if the projected polygon will be clockwise or counterclockwise.

In one of these 2D planes, a 90 deg rotation of an edge is just swapping the values with a sign change on one of these.

For example, in the XY plane, the edge between V0 and V1 is:

V0V1x = v1x - v0x

V0V1y = V1y - v0y

the vector between V0 and P is:

V0Px = Px - V0x

V0Py = Py - V0y

A -90 deg. rotation of the edge give is given us x' = y and y' = -x ;

So the scalar product we compute for the first edge will be

Scalar = (Px - V0x) * (V1y - V0y) + (Py - V0y) * (V0x - V1x)

If that value is < 0, then the point is not inside.

You do this with the 2 other edges and you have your "inside" test.

In my solution as a pre-processing I compute a value giving me the maximum normal direction and sign for each triangle. After that I use that value to know in what plane I want to compute my intersection. (A negative normal component make me switch the "clockwise" direction of the triangle).

The test to know if the point is inside the polygon take:

• 1 "direction" test with the maximum normal value (a switch with 6 cases, XY, XZ or YZ, positive or negative)

• 3 "edge" tests with 4 subtraction and 2 multiplications each and 1 test.

You only do the "edge" test 3 times if the point is inside the polygon. If not it may be rejected after the first or second edge...

So, knowing if a point is inside a triangle will take from 8 to 22 operations.

Most of the solutions I see nowadays seem to use more operations than that!