获取线段和 2^n 网格之间的所有交点（以整数表示）

我有一条从 (x0, y0) 到 (x1, y1) 的线，穿过由 2^n 宽的方形瓷砖组成的网格。我不仅需要找到线相交的图块，还需要找到相应的入口点和出口点。我可以找到所有关于此的问题都涉及“1x1”图块，而不关心图块内交叉点的位置。

这些点并不总是精确地为整数，在某些情况下，我会使用自然下限，而在其他情况下，我会进行四舍五入。但就目前而言，在所有情况下让它自然下降就可以了。

我找到了一个例子 http://playtechs.blogspot.com/2007/03/raytracing-on-grid.html最终得到一个非常简单的整数光线追踪情况，但它不跟踪交点，也不适用于除了穿过 1x1 图块中心（假设 0.5、0.5 偏移）的线之外的任何内容。

void raytrace(int x0, int y0, int x1, int y1)
{
    int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    int x = x0;
    int y = y0;
    int n = 1 + dx + dy;
    int x_inc = (x1 > x0) ? 1 : -1;
    int y_inc = (y1 > y0) ? 1 : -1;
    int error = dx - dy;
    dx *= 2;
    dy *= 2;

    for (; n > 0; --n)
    {
        visit(x, y);

        if (error > 0)
        {
            x += x_inc;
            error -= dy;
        }
        else
        {
            y += y_inc;
            error += dx;
        }
    }
}

如何调整它来找到相交的 2^n x 2^n 网格图块，同时抓取 2 个相关的交叉点？似乎在图块中“任何地方”开始的能力确实搞乱了这个算法，我的解决方案最终使用除法，并且可能设置为在每次迭代中累积错误。而且这样也不好...

另外，我认为对于第一个和最后一个图块，可以假设端点是“其他”交点。

有一篇有用的文章“快速体素遍历算法... http://www.cse.yorku.ca/~amana/research/grid.pdf” 作者：Woo，Amanatides。 看看实际的实现（网格遍历部分 http://www.flipcode.com/archives/Raytracing_Topics_Techniques-Part_4_Spatial_Subdivisions.shtml） 也。 我用过这个方法，效果很好。