   Matrix Math to solve Point in Triangle Problem
  I tried to implement a 3D "Point in Poly" function yesterday. It used the approach that the sum of the vertices is always 360 if it is inside. To me, that function seemed like a potential overhead, because of it's heavy use of trig functions. And given that I only use triangles anyways, there HAD to be something simpler (usually, vector math works without trig functions).I came up with a quite nice idea in today's math class, but I'm not sure if it's all correct.Given the vectors OA,OB,OC that point to the edges of the triangle and the vector OS that points to the point we want to check and it is already known that they are on the same plane, then this must be correct:AS = u*AB + v*ACandOS = OA + (u*AB + v*AC)where u and v are scalars. So, AB and AC actually form a 2d coord system.For any triangle ABC, S is inside if the following is true:0.0 <= u + v <= 1.0.Now we just have to find out what u and v are: We can use Matrix math and Determinats for that.u = Du / DD is the determinant of the 2D Matrix of AB and AC (since a triangle is always on one plane, we don't need 3D here) and Du is the Determinant of the 2D Matrix of AS and AC. It's the same as:u = ( ACy*ASx - ACx*ASy ) / ( ACy*ABx - ACx*ABy )We could use the same way to determine v, but that would be a waste of timejust stick it into the first equation and you get:v = (ASy - u*ABy) / ACyfirst thing to check no, is whether the point is on the Triangle's plane, like this:ASz == u*ABz + v*ACz if yes, we just check (u>=0) && (v>=0) && ( u+v <= 1.0 )and we're done, the point is within the triangle.That's 13 adds, 7 mults and 2 divs. So, how fast is this? Could anyone test it in a game/engine with lots of collisions?Edited by - _Jax_ on March 7, 2002 7:43:07 AM  
  Here''s some code I just wrote. It SHOULD work, but it''s untested ( I have no test data yet ).boolIntersectTrianglePoint( CTriangle3D& triangle, CVector3D& point ){// Transform to 2d "triangle space"CVector3Dp = point - triangle[0];CVector3Dx = triangle[1] - triangle[0];CVector3Dy = triangle[2] - triangle[0];doubleu =(( p[X] * y[Y] ) - ( p[Y] * y[X] )) / (( x[X] * y[Y] ) - ( x[Y] * y[X] ));doublev = (p[Y] - u*x[Y]) / y[Y];if ( p[Z] == u*x[Z] + v*y[Z] ){// Point is on Planeif ( ( 0.0 <= u ) && ( 0.0 <= v ) && ( (u+v) <= 1.0 ) ){// Point is within the area of the Trianglereturn true;}else{return false;}}else{// Point is not on planereturn false}} ;  _Jax_ do you realize that you are almost doing a barycentric point in triangle test? Try using Google to read up on Barycentric coordinates.I don''t know if your method is correct though, I''m not too hot on matrix math.  ;  no, I had no idea.. that''s why I asked ;  Hehe cool. Well barycentric coordinates can be described as coordinates on the surface of a triangle. Let a point P on a triangle with points A,B,C (in counterclockwise order) have barycentric coordinates a,b,c, then:0 <= a,b,c <= 1a+b+c = 1P = aA + bB + cCThe point P is not within the triangle if:a,b,c < 0or a,b,c > 1The barycentric coordinates a,b,c can be computed using the signed area of a triangle, which is positive if counterclockwise, negative if clockwise.a = signed_area(P,B,C) / signed_area(A,B,C)b = signed_area(P,C,A) / signed_area(A,B,C)c = signed_area(P,A,B) / signed_area(A,B,C)The barycentric point in triangle test is not the fastest, but it is used a lot in raytracing because it makes interpolating quantities between the vertices very easy. For example, the color at P = (a * the color at A) + (b * the color at B) + (c * the color at C).PS not sure if the pseudo code I gave is 100% correct. But I think you get the picture.Edited by - Scarab0 on March 7, 2002 10:23:52 AM  ;  I was thinking about this yesterday. What IS the fastest way to find if a point is in a triangle? How about creating 3 planes from the walls of the tri and then checking if the point is on the same side of each plane? It seems like it would be faster...if I''m correct, the method I use is the same as _Jax_s method...which means there are three normalizations and 3 acos calls...slow! The plane way would HAVE to be faster...no?BTW, I found this somewhere a long time ago, and I think this may be what you were trying to describe:   #define EPSILON 0.000001inline bool TriangleCollision(vectorfvOrigin, vectorfvDir,   vectorfvVert0, vectorfvVert1, vectorfvVert2,   float*t,float*u,float*v){   vector3fEdge1, Edge2, tvec, pvec, qvec;   floatdet, inv_det;   // find vectors for two Edges sharing Vert0   VectorSubtract3f(Edge1, Vert1, Vert0);   VectorSubtract3f(Edge2, Vert2, Vert0);   // begin calculating determinant - also used to calculate U parameter   VectorCross3f(pvec, Dir, Edge2);   //if determinant is near zero, ray lies in plane of triangle   det = VectorDot3f(Edge1, pvec);if (det > -EPSILON && det < EPSILON){return false;}   inv_det = 1.0f / det;   //calculate distance from Vert0 to ray Originin   VectorSubtract3f(tvec, Origin, Vert0);   //calculate U parameter and test bounds   *u = VectorDot3f(tvec, pvec) * inv_det;   if (*u < 0.0f || *u > 1.0f){return false;}   //prepare to test V parameter   VectorCross3f(qvec, tvec, Edge1);   //calculate V parameter and test bounds   *v = VectorDot3f(Dir, qvec) * inv_det;   if (*v < 0.0f || *u + *v > 1.0f){return false;}   //calculate t, ray intersects triangle   *t = VectorDot3f(Edge2, qvec) * inv_det;   return true;}  ;  I''m not sure what THE fastest way is, but I would suggest you read Point in polygon strategies (http://www.acm.org/pubs/tog/editors/erich/ptinpoly/). It explains some more methods that have not been mentioned yet, such as sending out a line from the test point and counting how many edges it crosses. This method does require flattening the triangle. That can be done very fast if the normal of the triangle is pre-calculated. Simply find out the largest of x,y,z in the normal and discard that axis.   int x_axis = 0;int y_axis = 1;if (normal.x > normal.z){    x_axis = 1;    y_axis = 2;}if (normal.y > normal.x){    x_axis = 0;    y_axis = 2;}// 2d points of triangle are now:point1[x_axis], point1[y_axis]point2[x_axis], point2[y_axis]point3[x_axis], point3[y_axis]  ;  Ok I just found an old Flipcode thread that should get you an awesomely fast point in triangle routine:http://www.flipcode.com/cgi-bin/msg.cgi?showThread=00003017&forum=3dtheory&id=-1Read it, learn it, live it. ;  Scarab, thx! By using Jukkas second to last algorithm I gained 137 fps :o!!!Basicly his is just a simplified version of what I posted. His version doesn''t calculate the uv.  ;  Here''s a demo. This mesh has 9000+ triangles and is drawn with the glDrawElements function.A line is clipped by the surface and is reflected in the direction of the triangles normal. When the line is at the top of the mesh it renders faster simply because it finds a collision sooner. As the line moves down there are a lot more tris to test so it''s slower.Demo using Jakkas PointInPoly function...except I determine the edges for every frame...:http://www.spider3d.com/dl/detect.zip  