segment intersecting a tetrahedron

Question

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

1. 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:

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

Thanks.

Answer 1

Hint:

You can't avoid a complex case discussion. Here I introduce the planar case of a line segment and a triangle.

The sides of the triangle define three straight lines that partition the plane in 7 regions, one bounded and 6 unbounded. On the figure, they are designated by the signs obtained when you plug the coordinates of a point in the three implicit equations of these lines.

If you need to consider endpoints exactly on a side, you need to add 6 half-lines and 3 segments to the discussion.

Then take all possible combinations of the starting and ending regions.

Many of the cases are straightforward. When the two segment endpoint belong to the same region, the segment is wholly inside or outside; when one of the regions is +++ and the other is different, there is exactly one intersection...

In the case of the figure (--+ to ++-), you are sure to have one intersection with the bottom edge; but which is the other intersected side is unsure: to answer this, you need to tell on what side of the line segment the top vertex lies.

With some courage, you can discuss all 16 x 15 / 2 = 120 cases, many of which are identical to a permutation of the elements.

This is just an appetizer compared to the 3D problem.

Answer 2

"How can I determine if the segment lies on one of the edges of the tetrahedron?"

Write a function that computes the area of the triangle determined by three points in space. This can be computed from a determinant, as explained here and many other sites.

Then write a function that determines if two segments ab and cd are collinear. They are if and only if the area of abc is zero, and the area of abd is zero.

Finally, write a function that determines if one point c lies on the segment ab. With all this, the remainder is easy.

Answer 3

To answer the general question, i.e. how to find the (up to two) intersections between a segment and a tetrahedron, I'd prefer to avoid the painful case-by-case analysis (mentioned in your problem reduction and in another answer).

I would use a variant of Sutherland-Hogdman's reentrant clipping (explained in 2D in [1]): the idea is to consider the tetrahedron as the intersection between four oriented half-spaces (limited by the support planes of the four faces of the tetrahedron).

Thus to compute the intersection between a segment and a tetrahedron, you can proceed as follows:

S := your segment
for f := 0 to 3 {
   H := half_space(tet, f)
   S := intersect(S, H)
}

H is just a plane equation (coefficients a,b,c,d of equation ax+by+cz+d=0, [a,b,c] is the normal to the facet, oriented towards the interior of the tetrahedron. d is obtained by injecting a vertex incident to the facet into the equation).

The function intersect() is simple to implement (just test the sign of ax+by+cz+d at both vertices of the segment, if they differ, there is an intersection, that can be computed by injecting a parametric equation of S x=x1+t(x2-x1), y=y1+t(y2-y1), z=z1+t(z2-z1) into (ax+by+cz+d=0) and solving for t, where (x1,y1,z1) and (x2,y2,z2) denote the two extremities of S.

In addition, the function intersect() may compute two booleans, to keep track of which vertex of S is a generated intersection.

[1] https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm