3D 体素网格视线 Bresenham 算法

Question

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

算法约束：

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

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

Answer 1

首先，Bresenham 不太擅长瞄准线：正如您的绘图所示，cells/voxels 的结果选择将不允许源 "see" 目标，因为所有这些锯齿状的边缘。

但是，如果您愿意考虑 Bresenham 对 2d 中的问题有好处，则很容易扩展到 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 背后的想法可以推广到任何维度：简单地跟踪累积的错误，并在需要时跳转以控制它们

3D 体素网格视线 Bresenham 算法

3D Voxel Grid Line of Sight Bresenham Algorithm

c#

algorithm

unity3d

voxel

bresenham