I''m working on some collision detection code and I''ve got the intersection point with the plane formed by the triangle the problem I have now is if the point is inside the triangle. I''m trying to figure this out but the triangle will not neccisarrly be a right triangle and will not neccisarly be entrily on one axis. If anyone has any ideas on how to do this please let me know.

I have an idea, about 10. If you are working on collision detection and are asking this question it seems you don''t want the knowledge that comes with doing it by yourself. So whatever you are going to do will not be better than the best is right now, so why even do it, just use someone elses library.

CONCEDE!

You could check the containment by using dot product

Think about it if you have a point right in the middle of a triangle which means the angle around the point is 360 degree.

A . B = |A| |B| cos q

now you want q to be the subject

so q = cos-1 ( A.B/|A||B|)
note that it''s the inverse of cosine

There you are, you have got your formula!!!!


------------
\ / <--360 right????
\ * /
\ /
\ /
\ /
\/

Then All you have to do is draw lines between the intersection point
and all the vertices of the triangle, and calculate the angle of each pair of vectors around the intersection point by the formula I have given to you. The sum will have to be greater than 360 or 2pi, otherwise it''s not in the middle.

Hope it helps
By the way, if you wanna be good you have got to ASK if you don''t know!

You could check the containment by using dot product

Think about it if you have a point right in the middle of a triangle which means the angle around the point is 360 degree.

A . B = |A| |B| cos q

now you want q to be the subject

so q = cos-1 ( A.B/|A||B|)
note that it''s the inverse of cosine

There you are, you have got your formula!!!!


------------
\ / <--360 right????
\ * /
\ /
\ /
\ /
\/

Then All you have to do is draw lines between the intersection point
and all the vertices of the triangle, and calculate the angle of each pair of vectors around the intersection point by the formula I have given to you. The sum will have to be greater than 360 or 2pi, otherwise it''s not in the middle.

Hope it helps
By the way, if you wanna be good you have got to ASK if you don''t know! you''ve done the right thing

quote:

---

Original post by smarterthanyou

I have an idea, about 10. If you are working on collision detection and are asking this question it seems you don''t want the knowledge that comes with doing it by yourself. So whatever you are going to do will not be better than the best is right now, so why even do it, just use someone elses library.

CONCEDE!

---

Were you born as a complete @$$ or do you have to work at it? The whole point of this forum is so that when someone is haveing problems figuring something out they can ask for ideas! Note that I did NOT ask for someone to GIVE me the code I asked anyone if they had any ideas on how it could be done! Not like a lot of others around here who want someone to write there program for them! I''m actually willing to, and want to, do it. I have a couple ideas too but there not very good! Sometimes you start looking at a problem and don''t notice the best answer right away then you can get stuck with one not so good solution trying to impose itself into every idea that you come up with (caused from spending 12 hrs a day looking at 5000+ lines of code). What more or less happened to me! T-Rex said something that I was thinking but one of my other ideas was muddleing my mind and I didn''t realize the simple buety of that solution. also someone else''s library might not do what I need. do you even have any idea how I have to implement the collision detection for the data set that I have? All I had left in it was this one problem. So stop being a complete horse''s rump and be constructive for a change! I''d just like to get through half a day without haveing some prick like you try to act like a total twit. Why does the whole planet seam to be populated with a-holes???? Is it just my bad luck that I have to deal with them all?

Now that I''ve got that out of my system (mostly).

Thanks T-Rex, I was thinking something along those lines but your explanation lifted the cloud! I''m going to try to implement that, I''m still open to any other ideas that might work better. If I have time I''ll report back my success (or failure).

I''ve done something like this in 2D using an area method..

First I got the area of the triangle, using Green''s theorem, which is something like:

area = y1 * (x2 - x1) - x1 * (y2 - y1) +
y2 * (x3 - x2) - x2 * (y3 - y2) +
y3 * (x1 - x3) - x3 * (y1 - y3)

Secondly, construct three more triangles from the point of interest to each of the vertices of the triangle, calculate the area of each (using the same method as above), and sum the areas. If the sum of the areas is equal to the area of the original triangle, the point is inside.

Obviously thats only for the 2D case, I have yet to try doing anything similar in 3D, it may involve first verifying whether the point is somewhere on the plane that the triangle lies on, and possibly projecting the point onto the plane (unless you know the 3D equivalent of the formula I gave above)..

Might be worth investigating, but as I said I''m not sure of exactly how the 3D case would work, so T-Rex''s suggestion would probably be the one to ride with.

Following up on dmerrick's post, here's a 3D area solution that I've seen a few times. I'll post another that uses half-planes.

The idea is that if a point (2d or 3d) -- call it P -- lies within a triangle ABC, then the sum of the areas of the 3 triangles PAB + PBC + PCA must equal the area of ABC.

How do you find the area of a triangle ABC? Use the vector cross product. The area of a triangle ABC is:

1/2 * |(B-A) x (C-A)|

where |V| denotes the vector norm (length) of V, and V x W denotes the cross product between V and W.

The upside of this method is that it is simple. The downside is it requires 4 square roots. The method using half planes -- which I will post shortly -- requires only multiplications and addition/subtraction.

Below is some Java code (translates to C/C++ easily enough):

// calculates the length (norm) of a vector A
static public double MatNorm(double[] A)

{
int n = A.length;
double x = 0.0;

for (int i = 0; i < n; i++)
x += A * A;<br> <br> x = Math.sqrt(x); <br> <br> return(x);<br> } <br><br>// computes the cross product of 2 vectors<br>// right hand rule A->B<br>static public double[] MatCross(double[] A, double[] B)<br> <br> {<br> int n = A.length;<br> if (n!= 3 || n != B.length)<br> throw(new MatrixConformException(<br> "MatCross: nonconforming matrices"));<br> <br> double[] X = new double[n];<br><br> X[0] = A[1] * B[2] - A[2] * B[1];<br> X[1] = A[2] * B[0] - A[0] * B[2];<br> X[2] = A[0] * B[1] - A[1] * B[0];<br> <br> return(X);<br> }<br><br>// calculates the area of the triangle formed by A, B, and C<br>// MatSub just subtracts two vectors<br>public static double TriArea(double[] A, double[] B, double[] C)<br> {<br> double x = 0.5 * MatNorm(<br> MatCross(<br> MatSub(B, A), <br> MatSub(C, A))<br> );<br> return(x);<br> } <br> <br><br> </i> <br><br><SPAN CLASS=editedby>[edited by - drj on October 2, 2003 11:19:52 AM]</SPAN>

There are alot of ways to test if point is in triangle. And you can get about 10 of them in 5 minutes using google... Here''s a start : http://www.blackpawn.com/texts/pointinpoly/default.html

You should never let your fears become the boundaries of your dreams.

As promised, a generic 3D half-space method for determining whether a point lies within a triangle.

The idea is that each edge of a triangle separates space into 2 halves: one half includes the "inside" of the triangle, and the other does not. If the point lies on the plane of the triangle, and it lies in the "inside" half-spaces described above, then it lies inside the triangle. (I leave it as an exercise to test for degenerate triangles; i.e., those where the 3 vertices are collinear.)

Refer to my previous post for cross-product code.

Some analytical geometry refresher:

i) A vector N perpendicular to the plane of the triangle ABC can be found using the cross product: N = (B-A) x (C-B)

ii) A plane -- in particular, the plane determined by a triangle -- is fully determined by such an orthogonal (perpendicular) vector along with one point in the plane (e.g., one of the vertices).

iii) A plane divides space into two halves. Let d = N.A, where . represents the vector dot product (Nx*Ax + Ny*Ay + Nz*Az). If P lies in the plane of the triangle, then N.P = d. If P is "above" the plane (in the direction of N), then N.P > d; similarly, if x is "below" the plane, N.P < d.

Example: the X-Z plane is described by the orthogonal vector N=(0,1,0) and point A=(0,0,0). Here, d = N.A = 0. The point (5, 0, -10) is in the plane, since N.(5,0,-10)=0. The point (0,5,0) is above the plane, since N.(0,5,0)=5 > 0. The point (0,-2,0) is below the plane, since N.(0,-2,0)=-2 < 0.

----------------------------------

Ok, enough primer. Here goes the algorithm to determine whether a point P lies inside the triangle ABC:

1) For triangle ABC, compute an orthogonal vector N and a constant d as in (i) above.
2) Test whether P lies in the plane of the triangle as in (iii). That is, test that N.P = d. If not, stop: P does not lie inside the triangle (in fact, it doesn''t even lie in the plane of the triangle).
3) For each edge IJ in {AB, BC, CA} (edge direction is important here!):
3a) Compute an orthogonal vector Q that is perpendicular to the plane containing N and the edge IJ, that is, perpendicular to the triangle: Q = N x (J-I). This vector will point "inward" toward the triangle.
3b) Compute a constant c to determine a plane that is perpendicular to the triangle and contains edge IJ: c = Q.I
3c) Test whether P lies on the "inside" or "outside" half of the plane. If Q.P < c, then stop: P lies "outside" the triangle.
4) Stop: P lies inside the triangle.

Note that a lot of the geometry can be pre-computed and stored along with your triangles. In particular, many programs already compute normals for their triangles, so N is often free.

Also, note that the computations are quite simple: at most something like 6 multiplies and 3 subtracts for each cross product, 3 multiplies and 3 adds for each dot product, for a worst case of 48 multiplies, 45 add/subtracts, and 4 compares (someone should check my counting).

The area algorithm in my previous post requires 4 cross products (one for each area, although total triangle area could be precomputed and stored), 4 dot products, and 4 square roots, for a total of 36 multiplies, 24 add/subtracts, one compare -- and 4 square roots. Square roots are slow: on a Pentium 4, anywhere from 10-20 times slower than a multiply and 20-40 times slower than an add/subtract. Roughly, the area algorithm is slower than the half-space algorithm by about 2 square roots, although optimizations such as precomputing values and using single-precision sqrts will narrow that difference.

Which brings me to the following point: graphics card manufacturers would do their users (and hence themselves) a great service by adding some collision detection maths to their cards. They already have built-in floating point vector and matrix pipelines. The benefit of offloading these calculations from the CPU would be substantial! Maybe this is an enhancement for OpenGL? (Pardon my ignorance if it''s already there -- and please let me know if it is!)

I suggest adding functions such as:
+ point inside a triangle / quad
+ intersection of a line / line segment with a triangle / quad / quadric

Darkwing''s right: there are gazillions of ways to skin this cat, and they''ve all been around a long time! The link he gives is the half-space approach. My hope is these postings will help other NeHe users by extending the discussion and consolidating the information.

The fact that there are so many postings out there says that graphics card designers should focus on adding some of the basic algorithms to their hardware.