首页 文章

查找光线是否在没有行进的情况下相交体素

提问于
浏览
0

我很清楚行进/ DDA算法,但我希望能够在恒定时间内进行每体素射线对检查,而不必通过体素空间“行进” . 我该怎么做?

为了清楚起见,我并没有试图找到光线相交的第一个体素,而是给定光线和体素,确定该体素是否为路径 .

2 回答

  • 1

    光线是 P = O + t D ,其中 POD 是向量, 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²
    
  • 0

    您可以使用任何Ray Box(AABB)交叉算法 .

    Arbitrary one

    如果需要交叉坐标,则选择3D线裁剪算法

相关问题