Determine if point is inside triangle in 3D

Question

I am looking for acknowledgement on my perception of a method regarding determining whether a point is located inside a triangle or not in 3D.

Given a ray in the form R(t) = e + td and a set of three points T = {V0, V1, V2} that forms a triangle in three dimensions, I know how to find the parametic equation for the plane that the three points form and how to determine if the ray intersects this plane or not. Lastly, if it intersects, I want to know if the intersection point actually is within the bounds of the triangles edges.

Please see my picture below.

What I am thinking is that I can calculate the dot product between each edge vector and the vector that goes from the first edge in the edge vector towards the point and check if they are all positive. Like this:

If that is the case, the point should be inside the triangle. Right? Isn't this kind of the same method used for determining backfaces in computer graphics?

Answer 1

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.

Answer 2

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!

Answer 3

You want to solve

E + t.D = a.V0 + b.V1 + c.V2

where

t, a, b, c >= 0, a + b + c = 1

Using c = 1 - a - b, you get a 3x3 linear system (decompose for x, y, z)

a.(V0 - V2) + b.(V1 - V2) - t.D = E - V2

that you can solve for t, a, b, then c and check positiveness.