1

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

在此处输入图像描述

这些点并不总是精确地在一个整数上，在某些情况下我会使用自然地板，而另一些我会想要四舍五入。但是现在让它在所有情况下都自然下降是可以的。

我找到了一个示例，该示例最终得到了一个非常简单的整数光线跟踪案例，但它不跟踪交点，也不适用于穿过中心的线（假设为 0.5、0.5 偏移） 1x1 瓷砖。

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^nx 2^n 网格图块，同时还抓住 2 个相关的交点？似乎在一个 tile 中“任何地方”开始的能力真的搞砸了这个算法，我的解决方案最终使用除法，并且可能设置为在每次迭代中累积错误。而且这样不好...

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

4

3 回答 3

2

有一篇有用的文章“ Fast Voxel Traversal Algorithm... ”，作者 Woo, Amanatides。也看看实际的实现（网格遍历部分）。我已经使用了这种方法，效果很好。

于 2012-12-14T18:36:43.083 回答
2

您可以通过将整个坐标系除以 2^n来将 2^n X 2^n 平铺大小减小到 1 X 1 。

准确地说，在我们的例子中，这意味着您将线的起点和终点的坐标除以 2^n。从现在开始，您可以将问题视为 1X1 大小的瓦片问题。在问题结束时，我们将 2^n 乘回到我们的解决方案中，从而得到 2^n X 2^n 解决方案的答案。

现在是在每个图块中查找入口和出口点的部分。假设该行从 (2.4, 4.6 ) 开始并在 (7.9, 6.3) 结束

  • 由于线的起点和终点的 x 坐标是 2.4 和 7.9，因此，它们之间的所有整数值都将与我们的线相交，即 x 坐标为 3、4、5、6、7 的图块将相交。我们可以使用输入线的方程计算这些 x 坐标对应的 y 坐标。
  • 类似地，线的起点和终点的 y 坐标之间的所有整数都将导致线和图块之间的另一组交点。
  • 根据它们的 x 坐标对所有这些点进行排序。现在成对挑选它们，第一个将是入口点，第二个将是出口。
  • 将这些点乘以 2^n 以获得原始问题的解决方案。

算法复杂度： O(nlog n )其中 n 是线的开始坐标和结束坐标之间的整数范围。通过小的修改，这可以进一步减少到 O(n)。

于 2012-12-15T12:58:17.730 回答
1

在 x0..x1 范围内插入 x 的每个整数值，并求解每个 y。这将为您提供瓷砖两侧的交叉点的位置。

在 y0..y1 范围内插入 y 的每个整数值，并求解 x。这将为您提供瓷砖顶部/底部的交叉点的位置。

编辑

当处理不同的图块大小并从图块内部开始时，代码会变得有点难看，但想法是一样的。这是 C# 中的一个解决方案（在LINQPad中按原样运行）：

List<Tuple<double,double>> intersections = new List<Tuple<double,double>>();

int tile_width = 4;

int x0 = 3;
int x1 = 15;
int y0 = 1;
int y1 = 17;

int round_up_x0_to_nearest_tile = tile_width*((x0 + tile_width -1)/tile_width);
int round_down_x1_to_nearest_tile = tile_width*x1/tile_width;

int round_up_y0_to_nearest_tile = tile_width*((y0 + tile_width -1)/tile_width);
int round_down_y1_to_nearest_tile = tile_width*y1/tile_width;

double slope = (y1-y0)*1.0/(x1-x0);
double inverse_slope = 1/slope;

for (int x = round_up_x0_to_nearest_tile; x <= round_down_x1_to_nearest_tile; x += tile_width)
{
    intersections.Add(new Tuple<double,double>(x, slope*(x-x0)+y0));
}

for (int y = round_up_y0_to_nearest_tile; y <= round_down_y1_to_nearest_tile; y += tile_width)
{
    intersections.Add(new Tuple<double,double>(inverse_slope*(y-y0)+x0, y));
}

intersections.Sort();

Console.WriteLine(intersections);

这种方法的缺点是，当直线与一个瓦片正好在一个角上相交时（即交叉点的 x 和 y 坐标都是整数），那么相同的交叉点将从 2 个中的每一个添加到列表中循环。在这种情况下，您可能希望从列表中删除重复的交点。

于 2012-12-14T18:27:47.727 回答