Растеризация линии: охватить все пиксели независимо от градиента линии?

Question

По сути, я хочу использовать линейный алгоритм, чтобы определить, какие ячейки проверять наличие столкновений для моего raycaster.

Брезенхам не подходит для этого, так как использует унифицированную толщинуподход, означающий, что он игнорирует ячейки, которые по крайней мере наполовину не покрывают линию.Совсем не здорово, потому что это означает, что некоторые сегменты моей линии не проверяются на предмет пересечений с ячейками, что приводит к ошибкам.

Кажется, я не могу найти никаких «толстых» алгоритмов,Может ли кто-нибудь помочь мне найти его?

Зеленый: то, что я хотел бы.
Красный: то, что у меня есть и не хочу.

Answer 1

У меня была точно такая же проблема, как и у вас, и я нашел очень простое решение. Обычно у Брезенхэма есть два последовательных символа, чтобы определить, следует ли увеличить координату для двух измерений:

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

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

Вы можете найти все пересечения, которые ваш луч имеет с горизонтальными линиями сетки, а затем отметить все ячейки в строке, которые либо имеют точку пересечения на одной стороне, либо находятся между двумя ячейками с пересечениями в строке.

Найти пересечения можно, начав с начала координат, продвинув точку до первого пересечения (и отметив ячейки в процессе), выяснив вектор, который переводит вас от пересечения к следующему (обе эти операции Основные аналогичные треугольники (или триг), а затем продвигаться столбец за столбцом, пока вы не зашли достаточно далеко. Перемещение столбец за столбцом включает одно добавление вектора на столбец и небольшой цикл для заполнения ячеек между пересечениями. Замените «mark» на «process», если вы обрабатываете ячейки на лету - этот алгоритм гарантированно пометит каждую ячейку только один раз.

То же самое можно сделать с вертикальными линиями, но сетки обычно хранятся в горизонтальных срезах, поэтому я выбрал это. Если вы используете триг, вам нужно обрабатывать прямые горизонтальные линии в специальном случае.

Кстати, насколько я знаю, именно так были сделаны старые "3D" игры на основе сетки raycaster (такие как Wolfenstein 3D). Я впервые прочитал об этом алгоритме из этой книги , эоны назад.

Answer 6

Как насчет Брезенхэма с дополнительным ограничением на недопустимость диагональных перемещений: создайте точки с помощью традиционного алгоритма, а затем в качестве шага последующей обработки вставьте дополнительные шаги, необходимые для выполнения только ортогональных перемещений.