Jump to content
  • Advertisement

Archived

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

DevLiquidKnight

Point in triangle?

This topic is 5321 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

Is there some way to determain if a point lies within a triangle, main reason I ask is because If I can figure that out figuring out how to do 3d collsion detection will be much more simple then if I dont know how to detect if a point lies in a triangle.. and im not talking about like. just right triangles all triangles if possible. Say I have the 3 vertexes for the triangle now how to do I determain if a point at (x,y,z) lies inside the triangle? Anyone know what I mean or how to help me here?

Share this post


Link to post
Share on other sites
Advertisement
I think i know what you mean. One way of determining whether a point is inside a triangle is to project that point onto the triangles plane.
Then you find the angle between p1 and p2 from your point,
then find the angle between p2 and p3 from your point....
THEN you find the angle between p3 and p1........

if sum of those angles if approx 180, you are inside the triangle

Share this post


Link to post
Share on other sites
I believe Muncher''s method has quite a bit of slow trig involved. Another way is to treat each edge of the triangle as a plane with all normals pointing in ( or out, just be consistent ). And then if a point lies in the positive ( or negative depending on your normals ) halfspace of each plane, then the point lies within the triangle. This is pretty easy and quick to do..

Share this post


Link to post
Share on other sites
Right Haro, this is the speediest and most solid method. The algo based on angles is nice, but a bit outdated and has painful cases of inaccuracy. From this concept, seeing it as a flat 3D convex, one can optimize and find the best code next.

[edited by - Charles B on March 24, 2004 6:07:49 AM]

Share this post


Link to post
Share on other sites
I know we're not worried about optimization but wouldnt it be faster to use haro's method but to always have the normals pointing out, and to check if ANY of them are positive? That way you can end as soon as it finds one. This also works for all convex polygons right? The worst case scenario for computing time woudl be he point inside the poly casue it would have to check all sides.

I know this is pointless to even talk about but I just need to get into the mindset of trying to optimize every bit of code I do.

[edited by - Healeyx76 on March 24, 2004 12:01:09 PM]

Share this post


Link to post
Share on other sites
It would work the same either way. If the normals are pointed inward, then as soon as one value comes up negative, you can exit. If they're pointed outwards, then as soon as one value comes up positive, you can exit. But you can exit early only if the point is not in the triangle. If the point is in the triangle, you're going to have to check all three planes regardless. No fundamental changes to performance occur.

[edited by - Agony on March 24, 2004 12:07:56 PM]

Share this post


Link to post
Share on other sites
Well discussing the exact optimized algo is pointless unless the context of the data structures one can feed or not is set.

For instance a quick AABox or Sphere rejection can be very useful. If the outward edge planes are already computed it may help but not that much given the memory drawback. BTW you do not need to normalize the planes unless even if your algo adds mertic tolerance. You can neaerly always remove rsqrts in col det algos.

Else if the data is simply about three points, another equivalent way of seing things is a 3D -> triangle coordiantes transfo. Name the coords a,b,c, all these must be in [0,1[ and c=1-a-b. This detailed can lead to some quick code too. Anyway when you develop equations you can see that the convex scheme gives equivalent equations.

If N is any perp to ABC

(a,b,c,n)*[A,B,C,N] -> P = x,y,z,1

Just inverse this matrix and multiply by P. Then develop the equations and you'll find the cross products of the convex approach in the Det and the comatrix of the sub 3x3 matrix.

Since deviding by Det is not required, this ends up in a quite fast code. As you can see convex approach <=> transfo inversion approach.



[edited by - Charles B on March 24, 2004 2:10:48 PM]

[edited by - Charles B on March 24, 2004 2:14:35 PM]

Share this post


Link to post
Share on other sites
So say we have a triangle whose vertices are located at:
( 1, 0, -1 ) = Point A
( -1, 0, -1 ) = Point B
( 0, 1, 1 ) = Point C

And we have a the user's camera located at the point (x,y,z) location how do we determain if this point has hit (or collided) into this this individual triangle?

[edited by - DevLiquidKnight on March 24, 2004 5:54:15 PM]

Share this post


Link to post
Share on other sites
You may want to google for basic 3d graphics tutorials. You are going to be over your head if you do not understand planes and half space calculation. I could offer the code but this would probably hurt more than help. Learn the math, it is not difficult!

Share this post


Link to post
Share on other sites
Im pretty good at figuring things out when I am presented with an example of how to do what im looking for I know there is math involved in it and its probably behond my current level, but I have learned a lot of math behond my current level, through examples of how specific concepts work.

Plus, I don't like my current 3d collsion system of boxes at every vertex that keep the user from runing into the terrain; because the world isn't exactly box shaped.

[edited by - DevLiquidKnight on March 24, 2004 6:10:52 PM]

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!