I’m working on optimizing my Python / Pygame voxel raytracing engine. I am stuck trying to find the most performance efficient ray intersection algorithm that does what I need. I’ll simplify the exact aspect I’m stuck on in minimal form.

The world contains one line and an undefined number of boxes. The line is represented by two variables which are its start and end positions, each box is two variables for the start and end corners. All points are tuples, line position is a float but box corners are always integers, world center is 0 0 0 so positions may be positive or negative. For example: line_start = (-8.2, 0.0, 4.6) and line_end = (0.125, 16.75, -0.0625) may be the line, box_min = (-1, -2, -3) and box_max = (7, 8, 9) is a box.

The code loops through all boxes and must determine which are touched by the line. If the line intersects a box, I need to obtain a list of all integer positions inside its area that are touched by the line. As the later are points without an inherent radius, they can be interpreted at size dot_min = (-0.5, -0.5, -0.5) and dot_max = (+0.5, +0.5, +0.5) if needed to detect intersections, the returned positions must be integers since I only need the centers. The final position list from all intersected boxes should be sorted in order of which is closest to the line’s start position.

Here’s a simplified visual example, it’s 2D and I need this in 3D but the concept is the same. Red units are area boxes that weren’t touched, yellow units are a box that was touched by the line, green units are the integer positions inside the box which are themselves intersected by the ray. The ray starts at (4.0, 12.0) and ends at (10.0, 2.0), the intersected box stretches between corners (3, 3) to (10, 8), the result should thus be the array [(6, 8), (7, 8), (7, 7), (7, 6), (8, 6), (8, 5), (9, 5), (8, 4), (9, 4), (9, 3), (10, 3)].