我很清楚行进/ DDA算法,但我希望能够在恒定时间内进行每体素射线对检查,而不必通过体素空间“行进” . 我该怎么做?
为了清楚起见,我并没有试图找到光线相交的第一个体素,而是给定光线和体素,确定该体素是否为路径 .
光线是 P = O + t D ,其中 P , O , D 是向量, t 是正实数 . 如果以下系统有解决方案,则与体素 [x,y,z]x[x+1,y+1,z+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' = (x - Ox) / Dx
x' < t < x" y' < t < y" z' < t < z" 0 < t
如果 Dx < 0 ,则必须颠倒不等式 . 如果 Dx == 0 ,则不等式在 x < Ox < x + 1 中退化,这可以直接决定 .
Dx < 0
Dx == 0
x < Ox < x + 1
对所有三个轴重复相同的讨论,并检查所有支架是否兼容 .
例如,对于 Dx, Dy, Dz > 0 ,您必须拥有
Dx, Dy, Dz > 0
max(0, x', y', z') < min(x", y", z").
有27个符号组合需要考虑,它们在三个级联三向比较中分开 .
作为微优化,您可以通过 Dx Dy Dz 重新调整最后的不等式并简化,以交换(快速)乘法的除法 .
Dx Dy Dz
如果许多光线错过了体素,则可以通过使用边界球来加快处理速度 . 假设体素中心是 C ,体素半径 R 和矢量 D 被归一化,预测试是
C
R
(OC x D)² < R²
您可以使用任何Ray Box(AABB)交叉算法 .
Arbitrary one
如果需要交叉坐标,则选择3D线裁剪算法
2 回答
光线是
P = O + t D
,其中P
,O
,D
是向量,t
是正实数 . 如果以下系统有解决方案,则与体素[x,y,z]x[x+1,y+1,z+1]
存在交集:我们为了简洁而重写(与
x' = (x - Ox) / Dx
...)如果
Dx < 0
,则必须颠倒不等式 . 如果Dx == 0
,则不等式在x < Ox < x + 1
中退化,这可以直接决定 .对所有三个轴重复相同的讨论,并检查所有支架是否兼容 .
例如,对于
Dx, Dy, Dz > 0
,您必须拥有有27个符号组合需要考虑,它们在三个级联三向比较中分开 .
作为微优化,您可以通过
Dx Dy Dz
重新调整最后的不等式并简化,以交换(快速)乘法的除法 .如果许多光线错过了体素,则可以通过使用边界球来加快处理速度 . 假设体素中心是
C
,体素半径R
和矢量D
被归一化,预测试是您可以使用任何Ray Box(AABB)交叉算法 .
Arbitrary one
如果需要交叉坐标,则选择3D线裁剪算法