光线投射算法

1. 前沿

光线投射算法(Ray Casting)是指在一个空间体素模型中，已知起点和终点，求光线从起点到终点经过的所有体素

此算法与直线绘制算法的不同之处在于：一个是寻找点，一个是寻找体素。因此当直线穿过对角点时，直线绘制算法直接加入这个点就行了；光线投射算法需要把对角线周围的体素加入进去

2. 快速体素遍历算法

2.1 思路

已知起点$P_0$和终点$P_n$，可以分别计算两点距离在x轴方向和y轴方向的投影$\Delta x,\Delta y$。可以把每个栅格的边长设为1(栅格索引以1为单位进行移动)，则移动一个格子时的比例（或者称为时间）为$t_{\Delta x}=1/\Delta x$或$t_{\Delta y}=1/\Delta y$。分别累积计算水平方向穿过网格边和竖直方向穿过网格边的$t$值，记为$t_{x}$和$t_{y}$

• 如果t_{x} < t_{y}$，那么光线先穿过垂直边界，那么向x方向移动一步

• 如果t_{x} \geq t_{y}$, 那么光线先穿过水平边界，那么向y方向移动一步

2.2 代码参考

首先定义栅格对象

class GridPoint {
public:
    explicit GridPoint() = default;
    GridPoint(const int x_, const int y_) : x{x_}, y{y_} {}
    bool operator==(const GridPoint& other) const {
        return x == other.x && y == other.y;
    }
    int x = 0;
    int y = 0;
};

参考代码

std::vector<GridPoint> runRayCast(GridPoint start, GridPoint end) {
    std::vector<GridPoint> path;

    // 1. 起点直接加入路径
    GridPoint current = start;
    path.push_back(current);

    // 如果起点终点相同，直接返回
    if (start == end) {
        return path;
    }

    // 2. 计算差值
    int dx = end.x - start.x;
    int dy = end.y - start.y;

    // 3. 确定步进方向 (1 或 -1)
    // 如果是 0 (垂直/水平线)，方向无所谓，后续逻辑会处理
    const int step_x = (dx >= 0) ? 1 : -1;
    const int step_y = (dy >= 0) ? 1 : -1;

    // 4. 计算 t_delta (移动一个格子需要的时间/比例)
    // 这里的 t 是归一化的，范围 [0, 1]。如果 dx 是 0，delta 设为无穷大
    const double t_delta_x = (dx == 0) ? std::numeric_limits<double>::infinity()
                                       : std::abs(1.0 / dx);
    const double t_delta_y = (dy == 0) ? std::numeric_limits<double>::infinity()
                                       : std::abs(1.0 / dy);

    // 5. 计算 t_max (到达第一个边界的时间)
    // 我们假设射线从格子的“中心”出发。
    // 所以到达第一个 X 边界的距离是 0.5 个格子宽度。
    double t_max_x =
        (dx == 0) ? std::numeric_limits<double>::infinity() : t_delta_x * 0.5;
    double t_max_y =
        (dy == 0) ? std::numeric_limits<double>::infinity() : t_delta_y * 0.5;

    // 6. 核心循环
    // 只要没到达终点，就一直循环
    while (!(current == end)) {
        // 比较：下一个 X 边界近，还是 Y 边界近？
        if (t_max_x < t_max_y) {
            // 撞到了 X 轴边界 -> 向 X 方向移动一步
            t_max_x += t_delta_x;
            current.x += step_x;
        } else {
            // 撞到了 Y 轴边界 -> 向 Y 方向移动一步
            t_max_y += t_delta_y;
            current.y += step_y;
        }

        // 将新进入的格子加入路径
        path.push_back(current);
    }

    return path;
}

---

参考文章

原文链接： A Fast Voxel Traversal AlgorithmforRay Tracing

源码链接：https://github.com/francisengelmann/fast_voxel_traversal