How can I check that the triangle intersects a given cube?

Question

If we have a triangle whose vertices are given by three points, how can I check that the triangle intersects a given cube?

For example

Answer 1

I don't have time to write up a full solution, but here is an outline of an algorithmic approach.

Use the three points of the triangle to set up a 2D coordinate system for a plane spanned by the triangle. Take each edge of the triangle and write it as a linear inequality in terms of this coordinate system. Solutions to this system of inequalities are the same as points of the triangle.

Use the cross product of two edges of the triangle to extend this to a coordinate system of 3D space.

For each face of the cube (or in general a polyhedron), write a linear inequality in terms of the 3D coordinate system. Substitute $0$ in for the third coordinate, giving a linear inequality representing the intersection between the face and the plane spanned by the triangle.

This complete system of inequalities represents the intersection of the triangle and the cube (or polyhedron).

Now, you just want to know if this system is non-empty. The main observation is that the intersection will be a polygon. Start with the triangle from the first three inequalities. For each inequality derived from the cube, find the set of edges this new line intersects and use it to update the polygon. If the polygon becomes empty, there is no intersection. If the polygon remains nonempty at the very end, then we know the triangle and cube intersect.

It is likely that this algorithm can be reduced from this general procedure to a specialized procedure where you check a few cases. For instance, calculate the intersection of the spanning plane and the cube, get a polygon of only a few kinds, and then see if this polygon overlaps the triangle. However, polygon clipping in general has complications. There might be a simple formula for calculating the intersection of a triangle and a convex triangle/square/pentagon/hexagon.

Polygon/plane clipping might be the keyword you are looking for. I also found https://stackoverflow.com/questions/21668797/triangle-cube-voxel-intersection

Answer 2

I would first check if all three vertices of the triangle are inside the cube. If that is not the case, then check for intersections of each edge of the triangle with each face of the cube and also check for intersections of each edge of the cube with the triangle.