I am not sure if this is the right forum to post in but what the hell. Problem: Check to see if a triangle is passing through: A) Another triangle. B) A Cube. C) A Sphere. I do not need to know where it hits or anything, just if it does. Solution: A) Get a point (x,y,z) and check which ''side'' it is on. Then get another point and see if it is on the other ''side'' of the triangle. Problem: How do I find out if a line segment passes through a triangle. This is essentially what I described above except just using two points. Solution: Now this is where you come in. Any help is appreciated.

quote:

---

Problem:
How do I find out if a line segment passes through a triangle. This is essentially what I described above except just using two points.

---

This might give you some hints:
check whether the triangle crosses the 2d-plane that the triangle spans. If it doesn't, then they do not cross,duhhh.
IF it does cross, the 3d-problem has been transformed to a 2d-problem. Coz, now you only need to know if the point (the intersection of the line segment and the infinite 2d plane) is contained within the 2d triangle. And I know there are 2d-algorithms for this!

regards

PS. Hmmm, I forgot, you'll need some extra checking to see if the line is lying in the plane, coz then you'll NOT get a point, you'll get MANY (a line)!!!!!
/Mankind gave birth to God.

Edited by - silvren on September 27, 2001 11:41:50 AM

This is the right forum.

Here''s the brute force solution to finding if a line segment passes through a triangle: find out if the two points are on opposite sides and if the *are* see if the intersection of the segment with the triangle lies within the interior. Steps:

Define: Your line segment goes from point A to B
Define: Triangle is defined by points T1, T2, and T3
Define: Triangle normal is N, and its unit length:

N = normalize(CrossProduct(T2-T1, T3-T1))

(This N ensures that the ordering T1, T2, T3 is counterclockwise from the side the normal is pointing to)

1) Line segment passes through the *plane* that contains the triangle if the following is true:

given float ADP = DotProduct(A-T1, N)
and float BDP = DotProduct(B-T1, N)

sign(ADP) = -sign(BDP) must be true for line segment to pass through plane of triangle

where sign is 1.0 for positive numbers, -1.0 for negative numbers

2) If segment passes through plane, find the point of intersection with the plane, PI:

PI = A - ((A - B) * fabs(ADP)/fabs(BDP))

PI lies in the plane of the triangle

3) PI is inside triangle if the following 3 conditions are met:

DotProduct(PI - T1, CrossProduct(N, T2 - T1)) > 0.0
and DotProduct(PI - T2, CrossProduct(N, T3 - T2)) > 0.0
and DotProduct(PI - T3, CrossProduct(N, T1 - T3)) > 0.0

NOTE: This is *NOT* a fast way to do the check, but it should *work*. As I said above, it is brute force. Part 1 (maybe) and Part 3 (especially) should be quite a bit less expensive if you transform everything into a coordinate system defined in the plane of the triangle and then do an edge-crossing check to see if the point is in the interior. See this page for more on checking to see if points are in the interior of a 2D polygon: http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

If your test volume is *convex* then you can easily determine if a point is inside or out. Simply define all the triangles of the object so that the normals point towards the outside. Given test point TP, if DotProduct(TP - TC, N) is positive for *all* triangles, where TC is the center of the current triangle and N is the normal of the current triangle, the point is *outside*. If the dot product is negative, the point is inside. This only works for convex objects.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Greg''s post reminds me.... The page I gave on point-in-polygon tests does have a link to fast ray/polygon intersections, from the Graphics Gems series of books. Here''s a link to the sample source code:

http://www.acm.org/pubs/tog/GraphicsGems/gems/RayPolygon.c

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Both of you have been helpful. I will try out what you have suggested. Thank you.