线光栅化:覆盖所有像素，而不管线梯度如何? [英] Line rasterisation: Cover all pixels, regardless of line gradient?

问题描述

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

Basically, I want to use a line algo to determine which cells to check for collisions for my raycaster.

Bresenham 不适用于此，因为它使用统一厚度方法，表示它会忽略那些至少没有覆盖线的单元格.一点也不好，因为这意味着我的线的某些部分没有被检查与单元格的交集，从而导致错误.

Bresenham isn't great for this as it uses a unified-thickness approach, meaning that it ignores cells that aren't at least half-covering the line. Not great at all, because it means that some segments of my line aren't being checked for intersections with the cells, leading to errors.

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

I can't seem to find any "thick-line" algorithms, can anyone help me find one?

格林:我想要的.
红色:我目前拥有和不想要的.

Green: What I would like.
Red: What I currently have and don't want.

推荐答案

我遇到了与您完全相同的问题，并找到了一个非常简单的解决方案.通常，布雷森纳姆有两个连续的if来确定是否应增加两个维度的坐标:

I had exactly the same problem as you and found an very simple solution. Usually, Bresenham has two consecutive if's to determine whether it should increase the coordinate for the two dimensions:

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:

Now all you have to do is to insert an else before the second 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;
        }
    }
}

现在，该算法不再一次更改两个坐标. 我尚未对此进行彻底的测试，但它似乎工作得很好.

Now the algorithm doesn't change both coordinates at once anymore. I haven't thoroughly tested this but it seems to work pretty well.

这篇关于线光栅化:覆盖所有像素，而不管线梯度如何?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！