Point on 2D Triangle in 3D space (Not Ray Intersection)

[Q_Me]

I have read dozens of Ray intersection of a 2D triangle in a 3D space, but not an actual point. And I know that it is mathimatically posible to determine if a specific point is on a triangle in a 3D space without having to rotate the triangle in any manner.

The problem is that I haven't found the equation to do so since people prefer to do the rotate-to-2D-plane-then-test method.

All I have to work with that I got from NeHe.GameDev is the quote of:

http://nehe.gamedev.net/data/article...asp?article=10

Using the notation used in the article, let me introduce the slightly different method, that is used in analytical geometry. It is pretty simple and deals only with some multiplications: Say, the triangle is given by the three points:
A ( xA, yA, zA)
B ( xB, yB, zB)
C ( xC, yC, zC)

and we want to determine if the point
M ( x, y, z)

is inside that triangle.

It is necessary (and more than enough) for the three vectors "MA", "MB" and "MC" to be co-planar. That is - one of them is a certain linear combination of others.

From analytical geometry we know, that 3 vectors are co-planar if:
|x-xA y-yA z-zA|
|x-xB y-yB z-zB| = 0
|x-xC y-yC z-zC|

(that is: det((MA)...,(MB)...,(MC)...)=0)

But to calculate a 3x3 determinant very few calculations are needed! Something like 12 multiplications and 6 sumations. After that we have to calculate the deviation of the result from 0 (like in the article we calculate the deviation of the total angle from 360 deg) to find out if the point is inside the triangle plane!

That's all about it! So instead of calculating the unnecessary information about triangles, sides, lengths, angle sizes, etc for 4 triangles, we only calculate a 3x3 determinant!

This can also be used to determine if the point is "inside" the triangle and so on...

They give the matricies but not the actual formula. So what is that formula?

[tekbuster]

I resolve this topic in this way....
find the normal vector of the triangle generated by two point on the border and the one that you are checking. make the same for all the point and check if they are all in the same direction if this happen it's inside, if not it's outside...
the fo9llowing is matlab code...sorry... but the concept is correct...

function [ result]=get_if_a_point_is_outside_a_triangle(P, a, b, c,n)
% the result is:
% 0 if the point is inside
% 1 if the point is outside
% 2 if the point is on the border

k1=get_normal_vector_to_the_triangle(a,b,P);
k2=get_normal_vector_to_the_triangle(b,c,P);
k3=get_normal_vector_to_the_triangle(c,a,P);
result=1;
if(dot(k1,k2) > 0 & dot(k1,k3) > 0 & dot(k2,k3) > 0)
result=0;
elseif (dot(k1,k2) == 0 | dot(k1,k3) == 0 | dot(k2,k3) == 0)
result=2;
end

[jemidiah]

The original post will actually only check if a point is in the same plane as the triangle. The missing piece is quite easy to include, though--the arrows must sweep out a 360 degree arc (they do not if the point is outside the plane).

I believe the approach tecbuster supplies suffers from the same problem. The dot products will each be exactly zero any time the triangles are coplanar, which will happen whenever the extra point is coplanar with the triangle's plane.

The way to do it I think is to form vectors MA MB and MC as described in the original post, apply the determinant check (see the 3-by-3 matrices section), and then check the additional constraint arccos(MA dot MB) + arccos(MB dot MC) + arccos(MA dot MC) = 2pi radians. This extra constraint ensures the vectors sweep out a full circle, and are therefore interior points. Computationally, you would have to accept 2pi +/- a tiny amount to account for roundoff errors. Very small values of the error margin will only allow a few points very close to being in the triangle through incorrectly, which is likely fine for your purposes.

Edit: the above assumes MA, MB, and MC are normalized before the arccos test is applied; that is, they are divided by their magnitudes, so that they end up with a magnitude of 1.