Archived

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

Point in triangle?

This topic is 5014 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
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
The math is very simple. First do you understand what a hyperplane is? A hyperplane is a dimension agnostic partitioning plane. 1d hyperplane = point, 2d hyperplane = line, 3d hyperplane = plane, 4d hyperplane = volume, etc.. It is important that a plane has a direction or a normal. This determines what is in "front" of the plane or behind it.

Now using 2d since its easiest to visualize and apply to 3d, if you draw a mathematical (neverending) line somewhere, then every other point in this 2d world will take on one of three qualities. It will be in the front of the plane in which case its distance to the line will be negative. It can be behind the plane in which case its distance to the plane would be positive, or it can be on the plane in which case its distance would be zero.

Now imagine three intersecting hyperplanes ( lines ) in 2d. They would create a triangle at their intersection. Now let''s also assume that the normal of each of these planes points towards the inside of the triangle. This means given any point on this 2d world we can determine whether or not it lies within the given triangle by determining its distance relative to each plane. If for any of these 3 hyperplanes, its distance is positive that would mean that the plane lies on the negative halfspace of this plane and would not be inside of the triangle.

Make sure you understand this basic concept perfectly. After you understand this all that is left is how you conceptualize planes. I prefer point/normal format. You have a point and then a normal to that point. A normal is simply the perpendicular direction. This point/normal combination defines a unique hyperplane. Going back to our 2d example, if we have the point 0,0 ( the origin ) and a normal of (1,0) we have essentially defined the y axis hyperplane. Again make sure you understand this perfectly.

Now there''s nothing but a formula. To check for distance use:

d = normal[direction] * ( planePoint[direction] - pointWeAreTesting[direction] )

If the normal is normalized or reduced to a unit vector then this will give absolute distance. If it is not normalized then it will give relative distance. This is all you need to now write the code for point/tri detection. Let me know if anything is not clear.

Share this post


Link to post
Share on other sites
One clarification in my last post. d is the SUM of the distances. So it would be:

d = normal[x] * ( planePoint[x] - pointWeAreTesting[x] ) +
normal[y] * ( planePoint[y] - pointWeAreTesting[y] )

For the 2d example.


Share this post


Link to post
Share on other sites
was the original post talking about being ONE THE SAME PLANE AS, AND INSIDE OF the triangle ... or was it talking about being INSIDE OF A TRIANGULAR PRISM defined by the triangle.

Cause it just doesn''t make a lot of sense to talk about 3D points being inside of 2D triangles - not when dealing with real world systems with roundoff error and such (unless you add the concept of a tollerance setting)

Share this post


Link to post
Share on other sites
quote:
was the original post talking about being ONE THE SAME PLANE AS, AND INSIDE OF the triangle ... or was it talking about being INSIDE OF A TRIANGULAR PRISM defined by the triangle.

It makese sense to understand a simple triangle before moving to figure out how to detect a 3d prism or whatever.. is used in 3d collision.


So would that mean to detect a point in a triangle its something like this:


[edited by - DevLiquidKnight on March 24, 2004 7:30:46 PM]

Share this post


Link to post
Share on other sites
pretty much. I prefer with the edge normals facing outwards, but either way it works the same

and by the way, no need for normalising edge plane normals, if it''s just a point test.

Share this post


Link to post
Share on other sites
and also, don;t forget fast rejects. if a point is back facing one of the planes, no need to test the others planes, you know it''s gonna be outside.

Share this post


Link to post
Share on other sites
Ok, the concept of determaining if the point lies in the triangle is rather easy to understand now the confusing part I am finding is the actual check itself.

[edited by - DevLiquidKnight on March 24, 2004 7:56:41 PM]

Share this post


Link to post
Share on other sites
Stop being lazy. Read what I wrote and write the code from it yourself. You''re not going to learn anything by just pasting together other people''s code. I intentionally included every piece of information you need to write the code.

Share this post


Link to post
Share on other sites
Ok i figured it out my own I got a polygon->sphere->polygon collision system working for my .x file mesh now, works very well now.

Im going to add some sort of tree algorithm to speed it up and then, figure out what to do next with my engine, thanks for help everyone. Maybe I try using a vertex/pixel shader next, or something else 0.o running out of things to add maybe physics ? sense this has no physics right now

[edited by - DevLiquidKnight on March 24, 2004 9:30:41 PM]

Share this post


Link to post
Share on other sites
This is rediculous. You are doing bounding volume approximations for single tri collisions? Why can you not be bothered to actually understand what you are doing and take 5 minutes to learn the "proper" method?

Share this post


Link to post
Share on other sites
I do understand what im doing, correct me if im at all wrong.

I take the polygon's vertices and the users location in 3d space, use a radius to determain a paramaeter to restrain the user from.

I then take the Normal of the polygon, then determain if the sphere is in front, behind, or intersects the plane.

If it intersects we have to find the offset of the intersection which is the normal * distance.

Where distance is defined as:

float d = (float)PlaneDistance(normal, user_pos);
distance = (normal.x * user_pos.x + normal.y * user_pos.y + user_pos.z * user_pos.z + d);

Then check if the intersection point is inside the polygon. If it is we obviously have colldied. If its not we have not collided.

[edited by - DevLiquidKnight on March 24, 2004 9:48:09 PM]

Share this post


Link to post
Share on other sites