Discuss Scratch

Geoge_jonh
Scratcher
5 posts

在2D网格上的一个快速射线步进方案

定义一个名为“加速场”的列表,第n项对应2D网格上从左到右、从上到下数的第n格,值为本格中心到最近实体格中心的切比雪夫距离,并且以格为单位。
射线在2D网格上步进时,将自己的位置映射到加速场中,并读取此项的值。
若值>2,直接沿射线方向走值-1格,否则:若值=0,使用DDA沿反方向步进一格并将当前坐标设为交点,否则用DDA走一格。

逐步分析这方案:
实体格是中心±0.5的单位方格;格内点相对本格中心偏移≤0.5,实体区域相对其实体中心偏移≤0.5,因此点到实体区域的距离至少为`d-0.5-0.5=d-1`。
当`d>2`时,沿射线方向移动`d-1`格的欧氏长度。
这个位移向量的切比雪夫范数,也就是max(|Δx|, |Δy|),最大为`d-1`,轴向时取等号。
因为点到实体的切比雪夫距离≥`d-1`,所以位移向量的切比雪夫范数永远不会超过该点到实体的距离。
最坏情况下仅能刚好触及实体边界,不可能进入实体内部。
若跳跃后恰好落在实体格内,也就是`d = 0`,算法通过DDA沿反方向回退一格并设交点。
这能修正因触及边界或浮点误差进入实体的情况,保证总会输出一个靠近真实入口的交点。
但是也发现了个BUG:
跳跃`d-1`可能恰好到达实体边界。
网格归属和浮点舍入可能导致该点被视为实体内部,进而触发反向 DDA 修正,交点精度会有一个格以内的保守偏移,但绝不会漏掉物体。

求大佬改进!我已经准备好将方案落地到我的光线投射项目中了。

Powered by DjangoBB