三维Voxel网格视线Bresenham算法

Question

给定一个三维体素网格，其中每个体素都是大小*大小(宽度*高度*长度)的一些整数大小和一条线通过在网格中的一些体素，有一个体面的有效的方法计算视线算法，以检测所有的体素，这条线通过？

算法约束：

1. 由于原始Bresenham的近似性质，没有遗漏任何体素，如这个2D示例所示：

​

​

1. 算法需要合理的效率，因为它将计算每帧一次；只要算法不取一个立方体的面积，并计算这条线是否与每一个立方体相交，它就应该是很好的。

Answer 1

首先，Bresenham不太擅长视线:正如您的绘图所示，结果选择的单元格/体素将不允许源“看到”目标，因为所有这些锯齿状的边缘。

但是，如果您愿意在2d内考虑Bresenham对您的问题有好处，则很容易扩展到3d:给定一条从p0 ={x0、y0、z0}到p1 ={x1、y1、z1}的线，您可以运行2d Bresenham两次，从{x0，y0}到{x1，y1}，从{x0，z0}到{x1，z1}。使用第一次运行时的x值和y值，第二次运行时使用z值。

或者，您也可以完全概括如下：

 // 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 --;
     }
   }
}

Brensenham背后的想法可以推广到任何维度:只需跟踪累积的错误，并在需要时跳转以控制错误。