lythm 203 Report post Posted May 24, 2004 Hello: How can I determin if a point is within a triangle. 0 Share this post Link to post Share on other sites

Karg 133 Report post Posted May 24, 2004 (only if in 3D) You need to find if the point is on the plane spaned by the triangle. Distance of the point to the plane == 0(both 2D and 3D)Then see if it is on the "correct" side of each of the edges of the triangle. Distance of the point from each line has the same sign.The sign you are looking for (+ or -) depends on which way you use the endpoints to create the lines. karg [edited by - Karg on May 24, 2004 12:26:13 AM] 0 Share this post Link to post Share on other sites

Yann L 1802 Report post Posted May 24, 2004 Code: //----------------------------------------------------------------------------// CHECKS IF 2D POINT P IS IN TRIANGLE ABC. RETURNS 1 IF IN, 0 IF OUT// Given a triangle ABC and a point P, determines if P is inside// of ABC (regardless of vertex ordering - CCW or CW). 2D version only, but// this handles the 3D case if appropriately projected to the XY, YZ, or XZ// planes (by dropping corresponding component; i.e. drop Z in XY projection).//----------------------------------------------------------------------------int Pt2dInTri(Vect2d A, Vect2d B, Vect2d C, Vect2d P){ // FIRST CHECK THE SIGN OF THE Z-COMPONENT OF THE NORMAL BY CALCULATING // THE CROSS-PRODUCT (ABxBC). THIS WILL DETERMINE THE ORDERING OF THE // VERTICES. IF NEGATIVE, VERTICES ARE CLOCKWISE ORDER; OTHERWISE CCW. // THEN EVALUATE SIGN OF Z-COMPONENTS FOR ABxAP, BCxBP, and CAxCP TO // DETERMINE IF P IS IN "INSIDE" HALF-SPACE FOR EACH EDGE IN TURN ("INSIDE" // IS DETERMINED BY SIGN OF Z OF NORMAL (VERTEX ORDERING). // NOTE: FULL CROSS-PRODS ARE NOT REQUIRED; ONLY THE Z-COMPONENTS Vect2d dAB=B-A, dBC=C-B; // "REPEATS" if ((dAB.x*dBC.y-dAB.y*dBC.x) < 0) // CW { if (dAB.x*(P.y-A.y) >= dAB.y*(P.x-A.x)) return(0); // ABxAP if (dBC.x*(P.y-B.y) >= dBC.y*(P.x-B.x)) return(0); // BCxBP if ((A.x-C.x)*(P.y-C.y) >= (A.y-C.y)*(P.x-C.x)) return(0); // CAxCP } else // CCW { if (dAB.x*(P.y-A.y) < dAB.y*(P.x-A.x)) return(0); // ABxAP if (dBC.x*(P.y-B.y) < dBC.y*(P.x-B.x)) return(0); // BCxBP if ((A.x-C.x)*(P.y-C.y) < (A.y-C.y)*(P.x-C.x)) return(0); // CAxCP } return(1); // "INSIDE" EACH EDGE''S IN-HALF-SPACE (PT P IS INSIDE TRIANGLE) };//----------------------------------------------------------------------------// CHECKS IF 3D POINT P IS IN 3D TRIANGLE ABC. RETURNS 1 IF IN, 0 IF OUT.// USES 2D VERSION AFTER PROJECTED SINCE THE 3D TRIANGLE IS PROJECTED ON ONE OF // THE PLANES FORMED BY THE PRINCIPAL AXES (XY, YZ, and XZ). N=Normal//---------------------------------------------------------------------------- int Pt3dInTri(Vect3d A, Vect3d B, Vect3d C, Vect3d P, Vect3d N){ // DETERMINE LARGEST COMPONENT OF NORMAL (magnitude, since we want the largest projection) N.x=ABS(N.x); N.y=ABS(N.y); N.z=ABS(N.z); // PROJECT ONTO PLANE WHERE LARGEST COMPONENT IS SET TO ZERO if (N.x>=N.y && N.x>N.z) // X IS LARGEST SO PROJECT ONTO YZ-PLANE return( Pt2dInTri(Vect2d(A.y,A.z),Vect2d(B.y,B.z),Vect2d(C.y,C.z),Vect2d(P.y,P.z)) ); else if (N.y>N.x && N.y>N.z) // Y IS LARGEST SO PROJECT ONTO XZ-PLANE return( Pt2dInTri(Vect2d(A.x,A.z),Vect2d(B.x,B.z),Vect2d(C.x,C.z),Vect2d(P.x,P.z)) ); else // Z IS LARGEST SO PROJECT ONTO XY-PLANE return( Pt2dInTri(Vect2d(A.x,A.y),Vect2d(B.x,B.y),Vect2d(C.x,C.y),Vect2d(P.x,P.y)) );};Found that somewhere on the net a long time ago, I don''t remember where. I fixed two little bugs in the original code, the modified one above works very well. 0 Share this post Link to post Share on other sites

jaba 122 Report post Posted May 25, 2004 Very interesting code!!!In Pt3dInTri is not necessary to calculate the distance from point to the plane? 0 Share this post Link to post Share on other sites

lythm 203 Report post Posted May 25, 2004 Karg: Thanks.Yann L: Thanks for your code. I never thought it could be solved in that clean neat way. 0 Share this post Link to post Share on other sites

sckoobs 157 Report post Posted May 25, 2004 Check this out: http://www.acm.org/pubs/tog/editors/erich/ptinpoly/I use the 2d Even-Odd method for my collision detection algorithm in my asteroids clone, very straightforward and efficient - no cross products and it doesn''t matter in what order you feed the vertices in. 0 Share this post Link to post Share on other sites

Yann L 1802 Report post Posted May 25, 2004 quote:Original post by jaba In Pt3dInTri is not necessary to calculate the distance from point to the plane? The distance is assumed to be 0, ie. the point is assumed to lie on the triangle''s surface (or very near to it, within some epsilon). If it doesn''t, you need to project it along the face normal, onto the surface. 0 Share this post Link to post Share on other sites

Venerable Vampire 151 Report post Posted May 25, 2004 Just out of curiosity, ever heard of barycentric space? If you take the forulas down far enough it doesn''t involve planes and can be quick even without precomputation.Look it up, its fun --------------------------------------------------------Life would be so much easier if we could just get the source code. 0 Share this post Link to post Share on other sites

jaba 122 Report post Posted May 25, 2004 quote:Original post by Yann L quote:Original post by jaba In Pt3dInTri is not necessary to calculate the distance from point to the plane? The distance is assumed to be 0, ie. the point is assumed to lie on the triangle's surface (or very near to it, within some epsilon). If it doesn't, you need to project it along the face normal, onto the surface. Sorry, I don't understandhttp://opengladiator.fateback.com/tri.jpgThe blue point(projected) is within the blue triangle(projected) but it isn't within the red triangle. First you must check if the point is on the plane of the triangle and then check if it iswithin the projected triangle. Sorry I am very stupid, can you explain me please? [edited by - jaba on May 25, 2004 4:27:54 PM] 0 Share this post Link to post Share on other sites

Karg 133 Report post Posted May 25, 2004 The posted code assumes that the point is on the same plane as the triangle. If that isn''t a safe assumption for you case, then you have to test if the absolute distance of the point from the plane is within some small value (almost 0).Find a plane equation from 3 points (ax+by+cz+d form):Given: Point3D p0, Point3D p1, Point3D p2, a = p0.y *(p1.z - p2.z) + p1.y *(p2.z - p0.z) + p2.y *(p0.z - p1.z); b = p0.z *(p1.x - p2.x) + p1.z *(p2.x - p0.x) + p2.z *(p0.x - p1.x); c = p0.x *(p1.y - p2.y) + p1.x *(p2.y - p0.y) + p2.x *(p0.y - p1.y); d = -(p0.x *(p1.y *p2.z - p2.y *p1.z) + p1.x *(p2.y *p0.z - p0.y *p2.z) + p2.x *(p0.y *p1.z - p1.y *p0.z));Then plug in the test point''s coordinates for x, y, and z. If the absolute value of the result is within some small value, then it is on the plane. Then continue with the other test.karg 0 Share this post Link to post Share on other sites

jaba 122 Report post Posted May 25, 2004 Ok!!, thanks 0 Share this post Link to post Share on other sites

motote 122 Report post Posted May 26, 2004 Here is a method I develop some years ago... is more efficient since it''s only make 4 mults.Hi hope it still works This test if point (p) is inside triangle (abc). bool pointInside(point2D a, point2D b, point2D c, point2D p){ float sign1, sign2; if ((a.x <= p.x) && (p.x <= c.x)) { sign2 = (p.x - a.x) * (c.y - a.y) - (p.y - a.y) * (c.x - a.x); if ((p.x < b.x) || (b.x == c.x)) sign1 = (p.x - a.x) * (b.y - a.y) - (p.y - a.y) * (b.x - a.x); else sign1 = (p.y - c.y) * (b.x - c.x) - (p.x - c.x) * (b.y - c.y); if (((sign1 >= 0) && (sign2 <= 0)) || ((sign1 <= 0) && (sign2 >= 0))) return true; } return false;} 0 Share this post Link to post Share on other sites