acw83 174 Report post Posted February 21, 2002 Hi, I have a point and a triangle, how do i test the point to see if it lies within the triangle? Thanks. P.S. I tried searching, but the forum search doesn''t work. 0 Share this post Link to post Share on other sites

Symphonic 313 Report post Posted February 21, 2002 What exactly are you asking?A triangle in 2D space as a bounding area with a point in it?A triangle in 3D space describing a bounding area on a plane?A triangle in 3D space projected to a 2D space (viewport) as a bounding area? George D. FiliotisAre you in support of the ban of Dihydrogen Monoxide? You should be! 0 Share this post Link to post Share on other sites

acw83 174 Report post Posted February 21, 2002 I am doing a triangle/triangle collision routine in 3D. I am at the point where I have the points where the triangle crosses the plane of the other triangle. I need to check these points to see if they lie within the other triangle, and thus confirm the collision. Thanks for the help. 0 Share this post Link to post Share on other sites

Guest Anonymous Poster Report post Posted February 22, 2002 i thought about this before, and it seems to me you can test whether a 2d point is in a 2d triangle, by1) drawing lines from all trianglevertices to the point2) check if these lines cross the triangle-sides, if they don''t -> the point is inside, else outsideOfcourse in your algo you need to find someway of projecting the plane in question to 2d. That''s the hard part I guess...hope this helps,Pieter (earx) 0 Share this post Link to post Share on other sites

Axter 122 Report post Posted February 22, 2002 Here is my algorithm for testing for a 3D point to see if it’s inside the polygon. Note that this assumes the point is coplanar with the polygon. This works with convex as well as concave polygons.It works by picking the two dominant axis and ignoring the other one. Thus it projects it to 2D. Note you need the normal to the polygon, which you might have lying around…To the ANSI/ISO/C++ conformation police… Yes, it probably isn’t, but I don’t care. //Returns true if the point is inside the polygon. //Assumes the point is coplanar with the polygonbool PointInPoly(point3* pVerts, int nNumVerts, point3& pt3Norm, point3& pt3CoPlanar){ int nOffsetA; int nOffsetB; point2 pt2Point; bool bInside = false; //Do one of three orientations if(fabs(pt3Norm.x) > 0.5773f) //Use y and z { nOffsetA = 1; nOffsetB = 2; pt2Point = point2(pt3CoPlanar.y, pt3CoPlanar.z); } else if(fabs(pt3Norm.y) > 0.5773f) //Use x and z { nOffsetA = 0; nOffsetB = 2; pt2Point = point2(pt3CoPlanar.x, pt3CoPlanar.z); } else //Use x and y { nOffsetA = 0; nOffsetB = 1; pt2Point = point2(pt3CoPlanar.x, pt3CoPlanar.y); } // Extend a straight line away from the point, // and count the lines that cut through that extended line for(int i = 0, j = nNumVerts - 1; i < nNumVerts; j = i++) { // Skip lines that begin and end either above or below the point bool bAZeroY; bool bBZeroY; point2 pt2VertA(((float*)&pVerts[i])[nOffsetA], ((float*)&pVerts[i])[nOffsetB]); point2 pt2VertB(((float*)&pVerts[j])[nOffsetA], ((float*)&pVerts[j])[nOffsetB]); // Move the vertices so that it''s relative to the origin, not the test point pt2VertA -= pt2Point; pt2VertB -= pt2Point; // Test if the line is either completely above or below the point if((pt2VertA.y > EPSILON && pt2VertB.y > EPSILON) || (pt2VertA.y < -EPSILON && pt2VertB.y < -EPSILON)) continue; // Test if the line is completely to the left of the origin if(pt2VertA.x < -EPSILON && pt2VertB.x < -EPSILON) continue; bAZeroY = fabs(pt2VertA.y) < EPSILON; bBZeroY = fabs(pt2VertB.y) < EPSILON; if(bAZeroY) { if(pt2VertA.x > -EPSILON) bInside ^= 1; // Going through the origin of the line else if(bBZeroY && pt2VertB.x > -EPSILON) bInside ^= 1; continue; } else if(bBZeroY) continue; // Calculate the point going through y == 0.0f float fRel = pt2VertA.y / (pt2VertA.y - pt2VertB.y); float fHitX = pt2VertA.x + (pt2VertB.x - pt2VertA.x) * fRel; if(fHitX > -EPSILON) bInside ^= 1; } return bInside;} SS 0 Share this post Link to post Share on other sites

acw83 174 Report post Posted February 22, 2002 Thanks 0 Share this post Link to post Share on other sites