线光栅化：覆盖所有像素，无论线梯度如何？

Question

基本上，我想使用直线算法来确定哪些单元格要检查我的光线投射器的碰撞。

Bresenham 不太适合这种情况，因为它使用统一厚度的方法，这意味着它忽略至少未覆盖该线一半的单元格。一点都不好，因为这意味着我的线的某些段没有被检查与单元格的相交，从而导致错误。

我似乎找不到任何“粗线”算法，有人可以帮我找到一个吗？

绿色：我想要什么。
红色：我目前拥有的和不想要的。

Answer 1

我遇到了和你完全相同的问题，并找到了一个非常简单的解决方案。通常，Bresenham 有两个连续的 if 来确定是否应该增加两个维度的坐标：

public void drawLine(int x0, int y0, int x1, int y1, char ch) {
    int dx =  Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
    int dy = -Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
    int err = dx + dy, e2; // error value e_xy

    for (;;) {
        put(x0, y0, ch);

        if (x0 == x1 && y0 == y1) break;

        e2 = 2 * err;

        // horizontal step?
        if (e2 > dy) {
            err += dy;
            x0 += sx;
        }

        // vertical step?
        if (e2 < dx) {
            err += dx;
            y0 += sy;
        }
    }
}

现在您所要做的就是在第二个 if 之前插入一个 else：

public void drawLineNoDiagonalSteps(int x0, int y0, int x1, int y1, char ch) {
    int dx =  Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
    int dy = -Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
    int err = dx + dy, e2;

    for (;;) {
        put(x0, y0, ch);

        if (x0 == x1 && y0 == y1) break;

        e2 = 2 * err;

        // EITHER horizontal OR vertical step (but not both!)
        if (e2 > dy) { 
            err += dy;
            x0 += sx;
        } else if (e2 < dx) { // <--- this "else" makes the difference
            err += dx;
            y0 += sy;
        }
    }
}

现在该算法不再同时更改两个坐标。
我还没有彻底测试过这个，但它似乎工作得很好。

Answer 2

这个线程很旧，但我认为值得将其放在互联网上：

// This prints the pixels from (x, y), increasing by dx and dy.
// Based on the DDA algorithm (uses floating point calculations).
void pixelsAfter(int x, int y, int dx, int dy)
{
    // Do not count pixels |dx|==|dy| diagonals twice:
    int steps = Math.abs(dx) == Math.abs(dy)
            ? Math.abs(dx) : Math.abs(dx) + Math.abs(dy);
    double xPos = x;
    double yPos = y;
    double incX = (dx + 0.0d) / steps;
    double incY = (dy + 0.0d) / steps;
    System.out.println(String.format("The pixels after (%d,%d) are:", x, y));
    for(int k = 0; k < steps; k++)
    {
        xPos += incX;
        yPos += incY;
        System.out.println(String.format("A pixel (%d) after is (%d, %d)",
            k + 1, (int)Math.floor(xPos), (int)Math.floor(yPos)));
    }
}

Answer 3

不失一般性，假设 x2 >= x1，则

int x = floor(x1);
int y = floor(y1);
double slope = (x2 - x1) / (y2 - y1);
if (y2 >= y1) {
  while (y < y2) {
    int r = floor(slope * (y - y1) + x1);
    do {
      usepixel(x, y);
      ++x;
    } while (x < r);
    usepixel(x, y);
    ++y;
  }
}
else {
  while (y > y2) {
    int r = floor(slope * (y - y1) + x1);
    do {
      usepixel(x, y);
      ++x;
    } while (x < r);
    usepixel(x, y);
    --y;
  }
}

发言权可能可以写成强制转换为整数。

Answer 4

GPU Gems 中有一篇有趣的文章，也许可以帮助您：第 22 章. 快速预过滤行

Answer 5

Bresenham 有一个附加约束，不允许对角移动：使用传统算法生成点，然后作为后处理步骤插入仅进行正交移动所需的额外步骤。

Answer 6

您可以找到光线与水平网格线的所有交点，然后标记一行上的所有单元格，这些单元格要么在一侧有交点，要么位于该行上有交点的两个单元格之间。

找到交点可以通过以下方式完成：从原点开始，将点推进到第一个交点（并标记过程中的单元格），找出从一个交点到下一个交点的向量（这两个操作都是基本的相似三角形） （或 trig）），然后逐列前进，直到走得足够远。逐列前进涉及每列一次向量加法，以及一个小循环来填充具有交叉点的单元格之间的单元格。如果您正在动态处理单元格，请将“标记”替换为“处理” - 该算法保证仅标记每个单元格一次。

垂直线也可以做同样的事情，但网格通常存储在水平切片中，所以我选择了它。如果您使用三角函数，则需要使用特殊情况来处理水平直线。

顺便说一句，据我所知，这就是旧的基于网格的光线投射器“3D”游戏（如德军总部 3D）的制作方式。我第一次读到这个算法是在很久以前的这本书中。