siegel@hc.DSPO.GOV (Josh Siegel) (03/28/88)
When given a line, and three points that make up a triangle, how do I tell if the line intersects the triangle and where it intersects.... thanks much --Josh Siegel -- Josh Siegel (siegel@hc.dspo.gov) I like using a C-47A "puff dragon" to go hunting with.
allan@calgary.UUCP (Jeff Allan) (03/30/88)
In article <14212@hc.DSPO.GOV>, siegel@hc.DSPO.GOV (Josh Siegel) writes: > > When given a line, and three points that make up a triangle, > how do I tell if the line intersects the triangle and where it > intersects.... The solution is to intersect the line with each line of the triangle then check to see if the intersection points lie between the end-points of the triangle. There are, however, a number of optional ways of doing things depending on your situation. If it is actually a line segment that you are comparing with the triangle, then you can compare the rectangular extents of both figures. If the extents do not overlap then the figures don't either. But if they do overlap the figures still may not. You can check this by comparing the two line segment end-points against each side of the triangle. If both end-points lie outside of any one edge of the triangle then the figures do not overlap. If this is not the case then you will still have to do the intersections. If, on the other hand, you are actually dealing with an infinite line then you can quickly check whether there is an intersection by checking to see if all three points of the triangle lie on one side of the line. If so then there is no intersection. Here are some algorithms which may come in handy. /************************************************************************/ /* INTERSECT2 */ /* Finds the intersection of 2 lines in 2D. */ /* The homogeneous representation of each line segment is found. */ /* Ax + By + C = 0 */ /* The intersection is found when the determinant of the matrix: */ /* A1 A2 x */ /* B1 B2 y */ /* C1 C2 w */ /* is zero. The determinant is calculated by co-factor expansion. */ /* The resulting homogeneous point (x,y,w) is the intersection point. */ /* This is not the most efficient algorithm but it is numerically stable*/ /************************************************************************/ int intersect2 (p1, p2, q1, q2, result) POINTSTRUCT *p1, *p2, *q1, *q2, *result; { POINTSTRUCT homo; double a1,b1,c1,a2,b2,c2, w, t; a1 = p1->y - p2->y; b1 = p2->x - p1->x; c1 = p1->x * p2->y - p2->x * p1->y; a2 = q1->y - q2->y; b2 = q2->x - q1->x; c2 = q1->x * q2->y - q2->x * q1->y; w = a1*b2 - a2*b1; if (-0.00001 < w && w < 0.00001) return 0; /* Parallel lines */ homo.x = b1*c2 - b2*c1; homo.y = c1*a2 - c2*a1; result->x = homo.x / w; result->y = homo.y / w; return 1; } /************************************************************************/ Point on one side of a line /************************************************************************/ The point (x1,y1) lies on one side of the line from (x2,y2) to (x3,y3) if the sign of: (x2-y3)*(x3-y2) + (x1-y3)*(x3-y1) + (x1-y2)*(x2-y1) is positive and on the other if it is negative (I can never remember which). This can be though of as the z component of the cross product of two vectors or as the determinant to the 3X3 matrix: |x1 y1 1| |x2 y2 1| |x3 y3 1| I hope this helps. -- Jeff Allan, University of Calgary ..!{ubc-vision,ihnp4}!alberta!calgary!allan
siegel@hc.DSPO.GOV (Josh Siegel) (03/31/88)
In article <1501@vaxb.calgary.UUCP> allan@calgary.UUCP (Jeff Allan) writes: >In article <14212@hc.DSPO.GOV>, siegel@hc.DSPO.GOV (Josh Siegel) writes: >> >> When given a line, and three points that make up a triangle, >> how do I tell if the line intersects the triangle and where it >> intersects.... > >The solution is to intersect the line with each line of the triangle >then check to see if the intersection points lie between the end-points >of the triangle. There are, however, a number of optional ways of doing >things depending on your situation. > Sorry if I waisted peoples time by not being specific... oh well.. I was talking 3D points and a three sided polygon (Ray tracing)... Somebody get the flame thrower... -- Josh Siegel (siegel@hc.dspo.gov) I like using a C-47A "puff dragon" to go hunting with.
david@linc.cis.upenn.edu (David Feldman) (04/01/88)
I don't know if the algorithm I am about to present is the fastest, but it should work. Every triangle defines a plane. The equation of that plane can be derived from a normal vector to that plane. A normal vector can be achieved by taking the cross product of two sides of the traingle (reprented by vectors). Now, pick any point on that plane, such as a vertex of the trianlge (x0,y0,z0). A vector from this point to any other point (x,y,z) on the plane will be perpendicular to the normal vector (A,B,C). Using a dot product, A(x-x0) + B(y-y0) + C(z-z0) = 0 Ax + By + Cz = d where d = Ax0 + By0 + cz0 Now, a vector (D,E,F) may be parameterized into a line by the equation set x = x1 + tD y = y1 + tE z = z1 + tF where t is the parameter and (x1,y1,z1) is a point on the line. Substituting these into the first eqn we find that A(x1 + tD) + B(y1 + tE) + C(z1 + tF) = d t = d - (Ax1 + By1 + Cz1) --------------------- AD + BE + CF From t and the line equations we can find the point of intersection. Now that you have the intersection point, is it in the triangle? To find out you can use cross products. Construct vectors from each vertex to the intersection point. Given one of these vectors (label it V1) constructed to a vertex v1, construct a second vector from vertex v1 to vertex v2 such that v2 is the next vertex after v1 in a right-hand-rule procession around the normal to the plane. Label this second vector V2. Now, V2 cross V1 will either be parallel or anti-parallel to the normal. If the intersection point is in the triangle, it will be parallel. You can check this by comparing the signs of the coordinates of the vectors. If the cross product is parallel for all vertices v1, then the point is in the trangle. Incidentally, this works for any convex polygon. Some notes and disclaimers: 1) I am sure that this is in a book somewhere but I derived it here while composing this posting. It may not be totally accurate and make no claims as such. 2) You needn't perform full cross products. Anti-parallelism will show a sign change in all coordinates. Therefore, just calculate and check one coordinate (which must have a non-zero value in the plane's normal vector). 3) If a cross product yields a zero answer, ignore it. You can't check a sign change against a zero. A zero means the intersection point lies along one of the vector edges of the triangle. If this point is outside the triangle, it will be detected on one of the other two comparisons. Hope this helps. Dave Feldman david@linc.cis.upenn.edu david@dsl.cis.upenn.edu david@eniac.cis.upenn.edu david@xmos.cis.upenn.edu etc............