2

I am trying to write C++ code to find the intersection points of a segment intersecting a tetrahedron. I reduced the problem like this:

For each face of the tetrahedron (a triangle), find the intersection point of the line segment. Then, I have three cases: a) The segment doesn't intersect any face - thus either the segment is entirely in the tetrahedron or completely outside. b) The segment only intersects one face. Then I just need to determine the side of the segment that is in the tetrahedron and I get the two points that are in the tetrahedron. c) The segment intersects two faces. I am having trouble implementing this algorithm. Here are the issues:

If the segment and triangle are in the same plane, how do I find the intersection points? How can I determine if the segment lies on one of the edges of the tetrahedron? Thanks.

Shekar Mantha
  • 73

1 Answers1

2

So your segment has endpoints $\mathbf p_1, \mathbf p_2$ and one of the planes is $\mathbf n \cdot \mathbf r = d$, where $\mathbf n$ points into the tetrahedron, then examine $\mathbf n \cdot \mathbf r - d$ for $\mathbf r = \mathbf p_1$ and $\mathbf r = \mathbf p_2$.

  • If they are both negative for any of the 4 planes, then your segment does not intersect the tetrahedron.
  • If for some plane, one is negative and the other point is $0$, and if the $0$ point is negative for some other plane, then your segment also does not intersect the tetrahedron.
  • If all 4 planes have both points giving positive results, your segment lies entirely inside the tetrahedron, but does not intersect the faces.

Otherwise, your segment intersects the tetrahedron in at least one point. Go through your planes and if for any of them you have a negative point:

  • If the other point is $0$, then the $0$ endpoint is the sole point of intersection with the tetrahedron.
  • Otherwise, replace the negative point with $t\mathbf p_1 + (1-t)\mathbf p_2$, where $t = \frac{d - \mathbf n \cdot \mathbf p_2}{\mathbf n \cdot \mathbf p_1 - \mathbf n \cdot \mathbf p_2}$. This is the intersection of the segment with that plane. Check this new point against the all other planes.

When you are done, both points will have positive or 0 values for each plane, and at least one of them will have 0 values for some plane.

  • If a point gives a $0$ value for some plane, then it lies within the triangular face in that plane.
  • If it is $0$ for 2 planes, it lies within their common edge.
  • If it is $0$ for 3 planes, it is their common vertex.
  • If it is $0$ for all 4 planes, then your "tetrahedron" is degenerate.
  • If it is positive for all planes, then it lies within the interior of the tetrahedron, and only the other endpoint is a point of intersection.

The segment is in a plane if both endpoints lie within that plane. The segment is along an edge, if both endpoints lie within the edge.

Paul Sinclair
  • 43,643
  • One thing you need to be careful about here is that the above works in exact mathematics. But sometimes comp error will play dirty tricks. That formula for the point of intersection will likely not result in exactly 0 when you do the $\mathbf n \cdot \mathbf r - d$ calculation on it. – Paul Sinclair Sep 02 '15 at 02:32
  • Thank you for the answer. This is really beautifully written and comprehensive. I will code it today. – Shekar Mantha Sep 02 '15 at 17:55