找出光线是否与Voxel相交而不行进

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²

Answer 2

您可以使用任何射线盒(AABB)交叉算法。

任意一

如果需要交点坐标，则选择三维直线裁剪算法。