以整数形式获取线段和 2^n 网格之间的所有交点 [英] Getting all intersection points between a line segment and a 2^n grid, in integers

问题描述

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

I have a line going from (x0, y0) to (x1, y1) through a grid made of square tiles 2^n wide. I not only need to find the tiles the line intersects, but also the corresponding entry and exit points. All the SO questions on this I can find deal with "1x1" tiles without caring where the intersections occur within the tile.

点并不总是精确的整数，在某些情况下，我会使用自然底数，而其他的我会想要四舍五入.但是现在让它在所有情况下自然地落地是没问题的.

The points won't always be precisely on an integer, and in some cases I'll use the natural floor and others I'll want to round up. But letting it naturally floor in all cases for this is fine for now.

我找到了一个例子使用整数进行光线跟踪的非常简单的情况，但它不跟踪交点，也不适用于除了穿过 1x1 图块中心(假设为 0.5、0.5 偏移)的线.

I found an example that eventually gets to a very simple case of raytracing with integers, but it doesn't keep track of the intersection points and also isn't adapted for anything but lines going through the center (assumed 0.5, 0.5 offset) of 1x1 tiles.

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 个相关的交点?似乎在 tile 中任何地方"开始的能力确实破坏了这个算法，而我的解决方案最终使用了除法，并且可能会在每次迭代中进行设置以累积错误.那不好...

How can it be adapted to find the intersected 2^n x 2^n grid tiles while also grabbing the 2 relevant intersection points? It seems the ability to start "anywhere" in a tile really mucks up this algorithm, and my solutions end up using division and probably setting things up to accumulate error over each iteration. And that's no good...

另外我认为对于第一个和最后一个图块，端点可以被假定为另一个"交叉点.

Also I think for the first and last tile, the endpoint can be assumed to be the "other" intersection point.

推荐答案

有有用的文章 "快速体素遍历算法..."，作者 Woo，Amanatides.看看实际的实现(网格遍历部分).我用过这个方法效果很好.

There is useful article "Fast Voxel Traversal Algorithm..." by Woo, Amanatides. Look at the practical implementation (grid traversal section) too. I've used this method with good results.

这篇关于以整数形式获取线段和 2^n 网格之间的所有交点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！