.
/Niklas
point within triangle
Author
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
.
/Niklas
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.
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.
The second method you might try is searching google or this forums becouse this has been anwserd alot of times before.
You should never let your fears become the boundaries of your dreams.
You should never let your fears become the boundaries of your dreams.
Check the forum FAQ (link below). There''s a link near the end to a website that discusses several point-in-polygon strategies.
Forum FAQ
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
Forum FAQ
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
Author
Thanks for the link. It was realy good and covered a lot of different techniques... sorry I started this thread =)
/Niklas
/Niklas
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.
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.
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]
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]
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
