如何确定射线在体素体积中可以通过的最大体素数？

Question

假设体素体积（x, y, z 具有相同的大小=>立方体）和穿过该体素体积的光线，如何确定光线可以通过的最大体素数？

Answer 1

如果我们考虑平面和 2d 正方形像素（棋盘），我们可以看到光线最多可以通过 2*N-1 个像素，如果我们计算真正的交叉点（例如，起点 0，-。 5 和方向 Pi/4) 和 3*N-2，如果我们计算触摸（按角）的单元格。

很难想象头部的 3d 情况 :)，但我怀疑平行于主对角线的光线可以与 3 * N - 2 单元格相交，当光线按顺序通过单元格时（0,0, 0)-(1,0,0)-(1,1,0)-(1,1,1) 等

加法。快速愚蠢的光线追踪建模表明 3 * N - 2 值是可能的：

var
  sx, sy, sz: Double;
  x, y, z: Double;
  ox, oy, oz, nx, ny, nz, Cnt: Integer;
begin
  // starting point coordinate
  sx := 0;
  sy := 0.7;
  sz := 0.7;
  // current coordinates
  X := sx;
  Y := sy;
  z := sz;
  // previous cell indexes
  ox := Floor(X);
  oy := Floor(Y);
  oz := Floor(z);
  Cnt := 1;
  Memo1.Lines.Add(Format('%d: (%d, %d, %d)', [Cnt, ox, oy, oz]));
  repeat
    // new cell indexes
    nx := Floor(X);
    ny := Floor(Y);
    nz := Floor(z);
    // if cell changes
    if (nx > ox) or (ny > oy) or (nz > oz) then begin
      Inc(Cnt);
      Memo1.Lines.Add(Format('%d: (%d, %d, %d)', [Cnt, nx, ny, nz]));
    end;
    ox := nx;
    oy := ny;
    oz := nz;
    // do small step in main diagonal direction
    X := X + 0.03;
    Y := X + 0.03;
    z := z + 0.03;
  until (X > 4) or (Y > 4) or (z > 4);

给出具有 4 * 3 - 2 个相交体素的输出：

1: (0, 0, 0)
2: (0, 0, 1)
3: (0, 1, 1)
4: (1, 1, 1)
5: (1, 1, 2)
6: (1, 2, 2)
7: (2, 2, 2)
8: (2, 2, 3)
9: (2, 3, 3)
10: (3, 3, 3)

如何确定射线在体素体积中可以通过的最大体素数？

How to determine the maximal number of voxels a ray may pass in a voxel volume?

math

3d

image-processing

computer-vision