Jump to content
  • Advertisement


This topic is now archived and is closed to further replies.


does a point belong to this triangle ?

This topic is 5934 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post

Link to post
Share on other sites
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


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

Share this post

Link to post
Share on other sites
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.


Share this post

Link to post
Share on other sites
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.

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!