c# - 3D 体素网格视线 Bresenham 算法

Question

给定一个 3D 体素网格，其中每个体素都是 SIZE * SIZE * SIZE(宽度 * 高度 * 长度)，对于某个整数 SIZE 和一条线穿过网格中的一些体素，是否有一种相当有效的方法来计算视线算法检测线穿过的所有体素？

算法约束:

1. 如本二维示例所示，由于原始 Bresenham 的近似性质，没有遗漏任何体素:

1. 算法需要相当高效，因为它将每帧计算一次；只要该算法不采用立方体的面积并计算直线是否与每个单独的立方体相交，就应该没问题。

Answer 1

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

但是，如果您愿意考虑 Bresenham 对 2d 中的问题有好处，则很容易扩展到 3d:给定一条从 p0 = {x0, y0, z0} 到 p1 = {x1, y1, z1} 的直线，您可以从 {x0, y0} 到 {x1, y1} 和从 {x0, z0} 到 {x1, z1} 运行 2d Bresenham 两次。使用第一次运行的 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 背后的想法可以推广到任何维度:简单地跟踪累积的错误，并在需要时跳转以控制它们