Point in triangle?

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

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..

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]

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]

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]

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]

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]

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!

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]

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.

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.

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)

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]

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.

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.

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]

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.

Not trying to be lazy just trying to understand

What exactly do you not understand? Everything you need is posted in this thread.