Archived

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

Niklas2k2

point within triangle

Recommended Posts

Hello. I want to check if point P is within the triangle T0, T1, T2. The points all have three dimensions. I also know that P is in the same plane as the triangle, but the triangle can be rotated in any way. The only way I can upp with of doing this is to make three planes of T0->T1 T0->T2 and T1->T2. Then check if P is on the same side of all these three planes. This seems a bit inefficient though so i wonder if any body has a better way . /Niklas

Share this post


Link to post
Share on other sites
As an early test, check whether the point is in the triangle''s bounding box.
Also, check whether the point is on the triangle''s plane.

If both are true, then add the angles T0,P,T1 + T1,P,T2 + T2,P,T0.
If that adds up to (approx) 360 degrees (2PI radians), then the point is in the triangle. If not, it''s outside.

Share this post


Link to post
Share on other sites
quote:
Original post by Niklas2k2
Thanks for the link. It was realy good and covered a lot of different techniques... sorry I started this thread =)


Not a problem. The FAQ does occasionally have good links, so its a good idea to check there first, though.



Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
quote:

The only way I can upp with of doing this is to make three planes of T0->T1 T0->T2 and T1->T2. Then check if P is on the same side of all these three planes.

This seems a bit inefficient though so i wonder if any body has a better way .



That''s not efficient at all if you are colliding against static geometry. In fact, it''s the single most efficient method in existance. If you are doing it against static geometry use that method. It is more efficient than kitty soap''s method (whatever the name of the second guy who posted is) because even if you are doing a triangle test against static geometry you still must either compute vector lengths which requires calls to sqrt, and sqrt is the evil of all 3d graphics programming because it sucks gasoline out of processor cycles faster than a v12 ferarri in a formula one race.

Share this post


Link to post
Share on other sites
The best way to make it fast is to precalculate as much as possible. for you can precalculate the normals of the planes perpendicular to the triangle's edges (they don't even need to be normalized, since you only need the sign of the dot product, not the actual distance or so (altough you will need it if you are going to do barycentric coordinates, so if you are precalculating it you can just normalize them).
if you have the normals precalculated all you have to do is 2 vector subtractions and 3 dot products per test

My Site


[edited by - Quasar3D on October 8, 2003 7:53:51 PM]

Share this post


Link to post
Share on other sites
I''m not for too much pre-calculation, at it is very memory-hungry. Especially if you start caching the edge-plane normals. It''s another 36 bytes per triangle. And since, as you say, they don''t need to be normalised, I''m sure you can spare a plane calculation per test, in average (since most of the times, the point won''t be in the triangle anyway). But caching the triangle plane, or at least the plane normal, is useful, for early and fast rejects.

Share this post


Link to post
Share on other sites