Hi, I want to know how could i do to determine if a point is on a triangle (a face) in a 3d world. I know the coordinates of the 3 points of the triangle and the coordinate of the point i want to test.

you can generate a plane (aX+bY+cZ+d=0) equation for the triangle... then plug in the values for your point and find out if it''s on the plane...

you can then flatten the 4 coordinates (using the triangles normal) and solve it as a 2D ''puzzle'' using barycentric coordinate tests...

it''s similar to a method that I used for a landscape ray tracer. there may be better ways, but I know this one works

Jack;

DirectX 4 VB: All you need for multimedia programming in Visual Basic
Formula 1 Championship Manager, My Game Project.

You should flatten the triangle and do one of the point-in-polyon tests. There are many; one of the most common is to trace a ray from infinity to your point, and intersect it with the edges of the triangle. If it crosses one edge before reaching the point, it is in the triangle. Otherwise, it''s not.

I know that Graham has a ''standard link'' for this question, but I don''t have it.

Cédric

I do indeed have a standard link for 2D point-in-polygon strategies:

http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

jollyjeffers and cedricl gave the other part of the puzzle, i.e., finding out first if the point lies in the same plane as the polygon.


Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

finding out if a point is on a triangle surface semms indeed very tricky.
As said before, the first thing to do is to check if they are in the same plane.
But how to do it?...

In the following text, i consider A, B and C as the triangle points, P as the outside point and the notation XY means the vector from point X to point Y.

The idea do make an equation like ax + by + cz = d and then check if the point fits the equation seems nice.
But how to define the plane knowing the 3 points?
The easiest way is to make: AB x AC = normal (where x is a croos product (of cousre!))
This will give you the normal, the vector corresponding to the seeked values (a b c). to know d, just replace x, y and z by A''s coordinates. Then check if point P also fits the equation.

If the point is in the plane, the next thing to do is to find out if it lies in the triangle.
The proposal was to "flatten" the surface (and the point) with 3D coordinates into a surface with 2D coordinates and then check if it lies inside.
The question if the point lies inside or not (in 2D) is no problem since standart libraries do it for you, no need for advanced math nor algorithms, just inform you about the libs.
On the other side, how to "flatten" the triangle?
This means, you make an orthogonal projection on a plane.
Wich plane? the x-y plane? This is solved by simply removing the z component of the coordinates.
However, this solution isn''t so nice since it can lead to errors if the plane is "vertical", i mean orthogonal to the x-y plane.
Hmm, should we then make an orthogonal projection from the point on the triangle plane?
Then, we stay in 3D, an the problem of knowing if the point lies inside stays the same!


Therefore, i propose you another solution. Quicker, simplier, without need of outside lib.
The key is: "to solve, don''t adapt your triangle to your space but adapt your space to your triangle!"
Consider a new space, a new coordinate system where:
A is the origin
AB is the first axis
AC is the second
and the normal, the third.
In this space, the new coordinates are:
A (0 0 0)
B (1 0 0)
C (0 1 0)
and P?
Ok, this needs a little more brain...
We now the original-space position of P and desire the transformed-space position of P. All we have to do is to perform on P the same transformations, which are (considering O as the origin of the original-space):
first, substracting OA. Where coordinates of A are (a1 a2 a3).
the temporary P'' will be:
x'' = x - a1
y'' = y - a2
z'' = z - a3
then another transformation... hmm, not so simple, involves matrix manipulations...
well, the final transformation matrix will be:
ab1ab2 ab3
ac1 ac2 ac3
n1 n2 n3
divided by D
(where ab1 = a1 - b1...)
and D is equal to...
D = ab1.ac2.n3 + ab2.ac3.n1 + ab3.ac1.n2 - ab1.ac3.n2 - ab2.ac1.n3 - ab3.ac2.n1
This means, the new position of P is:
x'''' = (ab1.x'' + ab2.y'' + ab3.z'') / D
y'''' = (ac1.x'' + ac2.y'' + ac3.z'') / D
z'''' = (n1.x'' + n2.y'' + n3.z'') / D
The result seems very complicated but all calculations are now finished.
Now you have the new position P'' of the point and easy conclusions:
if z'''' = 0 then it''s in the same plane.
if x'''' > 0 & y'''' > 0 & x'''' + y'''' < 1 then it''s inside the triangle!
that''s it!

Hmm... yeah... this seems very complicated, i agree...

You can follow the first procedure if you prefer, but don''t forget that you''ll have to manage cases where triangles are orthogonal to the projection plane. This involve 2 checks on the triangle to choose a valid projection plane from the 3 main ones (x-y, y-z or x-z)
before proceeding with the "inside check".


I hope this will help you.
If any question, drop me a line.