3D line segment box intersection

Question

Looking for code to detect an intersection between a 3D segment (not a line/ray) and a 3D box (not necessarily a cube, but always axis-aligned). The boxes are voxels so they have regular spacing.

Already have the code to find a segment/plane intersection. Ideally, I'd like to find an efficient solution to adapt this for a rectangle, repeat for each face of the 3d box, and then iterate for tens of thousands of segments and boxes.

seg_start = array([x1,y1,z1])
seg_end = array([x2,y2,z2])
plane_point = array([x3,y3,z3])
plane_normal = array([x4,y4,z4])
u = seg_end - seg_start
w = seg_start - plane_point
D = dot(plane_normal,u)
N = -dot(plane_normal,w)
sI = N / D
if sI >= 0 and sI <= 1:
    return 1

Answer 1

First off, you probably meant and rather than or in your if-condition, otherwise it'll just always return true. Second, if you're just testing whether there is an intersection or not, you can do it faster (without the float-division):

• You can determine which "side" of each plane any given point is on using vector math:
  side = dot(my_point - plane_point, plane_normal)
  Now if side is positive, my_point is "in front of" the plane (i.e. it's on the side the normal is pointing towards); if negative, it's "behind" the plane. If side is zero, your point lies on the plane.

• You can check whether your segment intersects an (infinite) plane by just testing to see if the start point and end point are on different sides:

  start_side = dot(seg_start - plane_point, plane_normal)
  end_side = dot(seg_end - plane_point, plane_normal)
  return start_side * end_side
  #if < 0, both points lie on different sides, hence intersection
  #if = 0, at least one point lies on the plane
  #if > 0, both points lie on the same side, i.e. no intersection
  

• You can use the "side" check to do the axis-aligned-cuboid intersection too (actually, this will work for any parallelpiped):

  • Treat your box as a set of six planes
  • Make sure the plane normals are all pointing either "outwards" or "inwards" from the box. I'll assume you're using "outwards"
  • For any point to lie inside your box, it has to be "behind" all six planes. If it isn't, it lies outside the box.
  • For any segment to intersect the box, one point has to lie outside it and one inside.
  • That's all!

edit: The last point is actually incorrect; as you say, voxels can be intersected even if both endpoints lie outside. So it's not the whole solution - actually, you can't really do this without calculating the intersection point. You can, however, still use the "side test" as an early-reject mechanism, so as to cut down on the number of full calculations you need to do: if both points are on the same side of any one of the six planes, there can be no intersection.

As far as your specific case goes, it seems like you're trying to find all intersecting voxels for some given line segment? In that case, you'd probably be better served using something like Bresenham's to explicitly calculate the path, instead of testing for intersections against all of the voxels...