algorithm - 查找射线是否在没有行进的情况下与体素相交

Question

我很清楚行进/DDA 算法，但我希望能够在恒定时间内对每个体素射线对进行检查，而不必在体素空间中“行进”。我该怎么做？

需要说明的是，我并不是要寻找射线相交的第一个体素，而是在给定射线和体素的情况下，确定该体素的单元是否位于射线的路径内。

Answer 1

一条射线是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²