线光栅化:覆盖所有像素,无论线条渐变？

Question

基本上,我想使用行算法来确定哪些单元格要检查我的raycaster的碰撞.

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;
        }
    }
}

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

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)));
    }
}