3D Voxel Grid Line of Sight Bresenham Algorithm

Question

Given a 3D voxel grid where each voxel is SIZE * SIZE * SIZE (width * height * length) for some integer SIZE and a line passing through some of the voxels in the grid, is there a decently efficient way of computing a line of sight algorithm to detect all voxels that the line passes through?

Algorithm Constraints:

No voxels are left out due to the approximate nature of the original Bresenham as seen in this 2D example:

2D Bresemham

Algorithm needs to be reasonably efficient as it will be calculated once per frame; as long as the algorithm does not take an area of cubes and calculates if the line intersects each individual cube, it should be fine.

@MBo I fail to see how a raytracing algorithm that is interested in finding object intersections can be used as a generalization of the Bresenham algorithm to 3d — tucuxi, May 24 '18 at 19:04
@tucuxi Bresenham algo does not provide registration of ALL touched voxels, so .. it is just not suitable here without crucial changes. — MBo, May 25 '18 at 03:37
@MBo I agree, but OP explicitly asked for Bresenham in 3d. See 1st paragraph in my answer. — tucuxi, May 25 '18 at 07:03
@tucuxi I'd suppose he used Bresenham as example of *(the only)* known algorithm — MBo, May 25 '18 at 07:27
Duplicate of https://stackoverflow.com/questions/25016603/forwarding-drawing-line-in-3d-grid (as already pointed out) and https://stackoverflow.com/questions/16505905/walk-a-line-between-two-points-in-a-3d-voxel-space-visiting-all-cells. The answer on the first of these looks best. — AakashM, May 25 '18 at 07:57

score 2 · Accepted Answer · answered May 24 '18 at 19:30

First, Bresenham is not that good at line-of-sight: as your drawing shows, the resulting selection of cells/voxels will not allow the source to "see" the target due to all those jagged edges.

However, if you are willing to consider Bresenham good for your problem in 2d, it is easy to extend to 3d: given a line from p0 = {x0, y0, z0} to p1 = {x1, y1, z1}, you can run 2d Bresenham twice from {x0, y0} to {x1, y1} and from {x0, z0} to {x1, z1}. Use the x and y values from the 1st run, and the z values from the 2nd run.

Alternatively, you can just do the full generalization:

 // adapted from https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
 // expects x to be the fastest-changing dimension; replace
 //   with fastest-changing dimension otherwise, and fix plot() accordingly
 function line(float x0, float y0, float x1, float y1, float z1, float y1) {
   float dx = x1 - x0;
   float dy = y1 - y0;
   float dz = z1 - z0;
   float deltaErrorY := abs(dy / dx);
   float deltaErrorZ := abs(dz / dx);
   float errorY = 0;
   float errorZ = 0;
   int y = y0;
   int z = z0;
   for (int x = x0; x<x1; x++) { 
     plot(x,y,z);
     errorY += deltaErrorY;
     while (errorY >= 0.5) {
         y += sign(dy);
         errorY --;
     }
     errorZ += deltaErrorZ;
     while (errorZ >= 0.5) {
         z += sign(dz);
         errorZ --;
     }
   }
}

The idea behind Brensenham can be generalized to any dimension: simply keep track of accumulated errors, and jump when needed to keep them under control

3D Voxel Grid Line of Sight Bresenham Algorithm

1 Answers1