• Advertisement

Archived

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

point in triangle

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

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.

Share this post


Link to post
Share on other sites
Advertisement
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!

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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[i];

x = Math.sqrt(x);

return(x);
}

// computes the cross product of 2 vectors
// right hand rule A->B
static public double[] MatCross(double[] A, double[] B)

{
int n = A.length;
if (n!= 3 || n != B.length)
throw(new MatrixConformException(
"MatCross: nonconforming matrices"));

double[] X = new double[n];

X[0] = A[1] * B[2] - A[2] * B[1];
X[1] = A[2] * B[0] - A[0] * B[2];
X[2] = A[0] * B[1] - A[1] * B[0];

return(X);
}

// calculates the area of the triangle formed by A, B, and C
// MatSub just subtracts two vectors
public static double TriArea(double[] A, double[] B, double[] C)
{
double x = 0.5 * MatNorm(
MatCross(
MatSub(B, A),
MatSub(C, A))
);
return(x);
}




[edited by - drj on October 2, 2003 11:19:52 AM]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
DrJ's approach is the best approach for colliding against static geometry because all of the pertinent data can be pre computed and you can rely on using dotproducts only. Basically what he is doing is he generates vectors that point to the insides of the triangle. You find where a point intersects the plane formed by the triangle, and if that point is in front of all of the planes represented by the vectors that point inward then the ray hit that particular triangle.


EDIT: and unless I misunderstood you drj, there is absolutely no point in putting something like collision detection into video card implementation...that defeats the purpose of OpenGL as a low level graphics rendering API.


EDIT1: Oh, and brush collision code is better than all of this :-) (i use it in my engine)


[edited by - Shadow12345 on October 2, 2003 10:29:23 PM]


[edited by - Shadow12345 on October 2, 2003 10:31:46 PM]

[edited by - Shadow12345 on October 2, 2003 10:33:44 PM]

Share this post


Link to post
Share on other sites
Brush collision uses BSP trees and bounding planes, which still requires a fair amount of testing, particularly for a complex physical system, such as modeling a dynamic (not static!) piece of cloth. Cloth can be a difficult material to model well, for several reasons. One, as one of the NeHe articles describes (article #40?), there are the physics systems to take into account, which are often far from trivial. Second, even when one applies the proper physics equations for the forces, strange things occur due to round-off error, time discretization, and so on. Third, the modeling of a piece of fabric/cloth in 3D can create a very complicated collision detection issue: one does not want the cloth "passing through" itself.

To prevent an object from "passing through" itself, one needs to test for collision of each piece of the object with all other pieces of the object... before and after they've moved. This can be very time consuming, and I've yet to find a better solution than collision-testing each tesselated facet. Such a collision for a piece of cloth, for example, means testing whether the applied Euler equations (i.e., velocity + acceleration at each vertex) cause a vertex to pass through another face of the cloth (presumably, a face held fixed as of the last rendering frame). This test has to be applied for each vertex along its entire path of motion.

To summarize, I believe that hardware manufactureres would do a great service by including at least some rudimentary collision detection "helper" functions in their hardware. For complex virtual reality simulation, modelspace collision detection is vital, and eats up a lot of CPU time that is better spent on the model physics, AI, and so forth.



[edited by - drj on October 3, 2003 11:03:28 AM]

Share this post


Link to post
Share on other sites

  • Advertisement