射线投射算法中的精度问题

Question

我正在编写一个光线投射引擎。

一条光线的起点由站在二维网格内的玩家的位置确定。

当向某个方向投射光线时，我必须确定光线与其相交的网格。

(这个概念的详细描述在这里：http://www.permadi.com/tutorial/raycast/rayc7.html)

有一个小的不准确性会导致一些麻烦。我认为这个问题是由于网格步长的错误计算导致的。

然而我缺乏数学理解来解决这个问题。

问题描述：

当光线朝左行驶时，与网格相交的步长大小略微不同于向右行驶时的步长大小。

(为什么我关心这个问题？：当垂直和水平相交点彼此靠近时，特别是在角落处时，一些水平网格交点距离玩家比竖直网格交点更远。由于我使用不同的纹理来表示竖直交点，因此水平墙壁的外观被破坏了，因为即使它是水平的墙壁，竖直的纹理也会出现在墙壁的小部分上。)

这个问题是由算法缺陷引起的吗？这是我如何计算第一个水平网格交点和网格步长的方法：

找到第一个网格交点：

if (current_angle > 180) {
    first_grid_horizontal_y = ((int)p.pos_y / Field::width) * Field::width + Field::width;
} else {
    first_grid_horizontal_y = ((int)p.pos_y / Field::width) * Field::width - 1;
}
first_grid_horizontal_x = p.pos_x + (p.pos_y - first_grid_horizontal_y) / tan( 180 - current_angle);

计算步长：

if (current_angle > 180) {
    grid_stepsize_horizontal_y = Field::width;
    grid_stepsize_horizontal_x = Field::width / tan(current_angle - 180);
} else {
    grid_stepsize_horizontal_y = -Field::width;
    grid_stepsize_horizontal_x = Field::width / tan(180 - current_angle);
}

从代码中可以看出，我一直使用“180-当前角度”来确定x值的方向，这会导致不准确吗？我是否需要更多地区分角度？

- Marius Anderie

Answer 1

三角函数使用弧度制而非角度制。因此，

tan(180 - current_angle)

应该长成这样。

tan(Math.Pi - current_angle)

请注意，它等同于

。

- tan(current_angle)

如果您的 current_angle 以度为单位：

current_angle_radians = current_angle_degrees * Math.Pi / 180

- MBo

---

是的，我自己编写了一个tan函数，可以将弧度转换为角度。我只是为了更好的可读性而发布了tan()。 - Marius Anderie

Answer 2

我认为你的不准确性是由于向上时减去了1。

这背后的想法可能是您想获取块的最后一个像素的索引，但这是不必要的：您在做浮点数运算，下一个水平交点的 y 值应该代表网格单元之间的线。如果向下走，则表示单元格的最上面的坐标；如果向上走，则表示最下面的坐标。

（另外：(int) y / w 将向零舍入，因此仅适用于非负数。您可以考虑使用 floor(x / w)。）

- M Oehm