查找射线是否在没有行进的情况下与体素相交
Find If a Ray Intersects a Voxel Without Marching
我很了解行进/DDA 算法，但我希望能够在恒定时间内对每个体素射线对进行检查，而不必 "march" 通过体素space。我该怎么做？
需要说明的是，我并不是要找到射线相交的第一个体素，而是，给定一条射线和一个体素，确定该体素的单元是否位于其中光线的路径。
您可以使用任何光线盒 (AABB) 交集算法。
如果需要交点坐标，则选择3D线裁剪算法
射线是 P = O + t D，其中 P、O、D 是向量，t 是正实数。如果下面的系统有解决方案，则与体素[x,y,z]x[x+1,y+1,z+1]有交集：
x < Ox + t Dx < x + 1
y < Oy + t Dy < y + 1
z < Oz + t Dz < z + 1
0 < t
我们为简洁起见重写了（使用 x' = (x - Ox) / Dx ...）
x' < t < x"
y' < t < y"
z' < t < z"
0 < t
如果Dx < 0，不等式必须反转。若Dx == 0，不等式在x < Ox < x + 1处退化，可直接判定
对所有三个轴重复相同的讨论并检查所有括号是否兼容。
例如，对于 Dx, Dy, Dz > 0，您必须
max(0, x', y', z') < min(x", y", z").
要考虑的符号组合有 27 种，它们在三个级联的三向比较中分开。
作为微优化，您可以通过 Dx Dy Dz 重新缩放最后一个不等式并简化，以将除法换成（更快的）乘法。
如果很多光线错过了体素，您可以通过使用包围球稍微加快这个过程。假设体素中心为C，体素半径R，向量D归一化，预测试为
(OC x D)² < R²
我很了解行进/DDA 算法，但我希望能够在恒定时间内对每个体素射线对进行检查，而不必 "march" 通过体素space。我该怎么做？
需要说明的是，我并不是要找到射线相交的第一个体素，而是，给定一条射线和一个体素，确定该体素的单元是否位于其中光线的路径。
您可以使用任何光线盒 (AABB) 交集算法。
如果需要交点坐标，则选择3D线裁剪算法
射线是 P = O + t D，其中 P、O、D 是向量，t 是正实数。如果下面的系统有解决方案，则与体素[x,y,z]x[x+1,y+1,z+1]有交集：
x < Ox + t Dx < x + 1
y < Oy + t Dy < y + 1
z < Oz + t Dz < z + 1
0 < t
我们为简洁起见重写了（使用 x' = (x - Ox) / Dx ...）
x' < t < x"
y' < t < y"
z' < t < z"
0 < t
如果Dx < 0，不等式必须反转。若Dx == 0，不等式在x < Ox < x + 1处退化，可直接判定
对所有三个轴重复相同的讨论并检查所有括号是否兼容。
例如，对于 Dx, Dy, Dz > 0，您必须
max(0, x', y', z') < min(x", y", z").
要考虑的符号组合有 27 种，它们在三个级联的三向比较中分开。
作为微优化，您可以通过 Dx Dy Dz 重新缩放最后一个不等式并简化，以将除法换成（更快的）乘法。
如果很多光线错过了体素，您可以通过使用包围球稍微加快这个过程。假设体素中心为C，体素半径R，向量D归一化，预测试为
(OC x D)² < R²