CODEWITHSUNDEEP
c#algorithmunity-game-enginevoxelbresenham
elveskevtar
elveskevtar

Reputation: 38

3D Voxel Grid Line of Sight Bresenham Algorithm

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:

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

2D Bresemham

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

Upvotes: 1

Views: 2702

Answers (1)

tucuxi
tucuxi

Reputation: 17955

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

Upvotes: 2

Related Questions