Брезенхем и У на страже диагоналей

в 10:11, , рубрики: game development, Алгоритмы, Программирование

Брезенхем и У на страже диагоналей

На что вы сейчас смотрите? Если вы не из параллельной вселенной, где все сидят за векторными мониторами, то перед вами растровое изображение. Поглядите на эту полоску: /. Если придвинуться поближе к монитору, то можно увидеть пиксельные ступеньки, которые пытаются притвориться векторной линией. Для этой цели существует целая куча всевозможных алгоритмов растеризации, но я бы хотел рассказать об алгоритме Брезенхема и алгоритме У, которые находят приближение векторного отрезка в растровых координатах.

С проблемой растеризации мне довелось столкнуться во время работы над процедурным генератором планов зданий. Мне нужно было представить стены помещения в виде ячеек двумерного массива. Похожие задачи могут встретиться в физических расчётах, алгоритмах поиска пути или расчёте освещения, если используется разбиение пространства. Кто бы мог подумать, что знакомство с алгоритмами растеризации однажды может пригодиться?

Принцип работы алгоритма Брезенхема очень простой. Берётся отрезок и его начальная координата x. К иксу в цикле прибавляем по единичке в сторону конца отрезка. На каждом шаге вычисляется ошибка — расстояние между реальной координатой y в этом месте и ближайшей ячейкой сетки. Если ошибка не превышает половину высоты ячейки, то она заполняется. Вот и весь алгоритм.

Это была суть алгоритма, на деле всё выглядит следующим образом. Сначала вычисляется угловой коэффициент (y1 — у0)/(x1 — x0). Значение ошибки в начальной точке отрезка (0,0) принимается равным нулю и первая ячейка заполняется. На следующем шаге к ошибке прибавляется угловой коэффициент и анализируется её значение, если ошибка меньше 0.5, то заполняется ячейка (x0+1, у0), если больше, то заполняется ячейка (x0+1, у0+1) и из значения ошибки вычитается единица. На картинке ниже жёлтым цветом показана линия до растеризации, зелёным — значение ошибки на каждом шаге. Угловой коэффициент равняется 0.4, на первом шаге ошибка становится равной угловому коэффициенту, что меньше 0.5, а значит ордината остаётся прежней. На следующем шаге ошибка пересекает рубеж, из неё вычитается единица, а новый пиксель поднимается выше. И так до конца отрезка.

Брезенхем и У на страже диагоналей

Ещё один нюанс. Если проекция отрезка на ось x меньше проекции на ось y или начало и конец отрезка переставлены местами, то алгоритм не будет работать. Чтобы этого не случилось, нужно проверять направление вектора и его наклон, а потом по необходимости менять местами координаты отрезка, поворачивать оси, и, в конечном итоге, сводить всё к какому-то одному или хотя бы двум случаям. Главное не забывать во время рисования возвращать оси на место.

Для оптимизации расчётов, применяют трюк с умножением всех дробных переменных на dx = (x1 — x0). Тогда на каждом шаге ошибка будет изменяться на dy = (y1 — y0) вместо углового коэффициента и на dx вместо единицы. Также можно немного поменять логику, «передвинуть» ошибку так, чтобы граница была в нуле, и можно было проверять знак ошибки, это может быть быстрее.

Примерно так может выглядеть код для рисования растровой линии по алгоритму Брезенхема. Псевдокод из Википедии переделанный под C#.

void BresenhamLine(int x0, int y0, int x1, int y1)
{
    var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); // Проверяем рост отрезка по оси икс и по оси игрек
    // Отражаем линию по диагонали, если угол наклона слишком большой
    if (steep)
    {
        Swap(ref x0, ref y0); // Перетасовка координат вынесена в отдельную функцию для красоты
        Swap(ref x1, ref y1);
    }
    // Если линия растёт не слева направо, то меняем начало и конец отрезка местами
    if (x0 > x1)
    {
        Swap(ref x0, ref x1);
        Swap(ref y0, ref y1);
    }
    float dx = x1 - x0;
    float dy = Math.Abs(y1 - y0);
    float error = dx / 2; // Здесь используется оптимизация с умножением на dx, чтобы избавиться от лишних дробей
    int ystep = (y0 < y1) ? 1 : -1; // Выбираем направление роста координаты y
    int y = y0;
    for (int x = x0; x <= x1; x++)
    {
        DrawPoint(steep ? y : x, steep ? x : y); // Не забываем вернуть координаты на место
        error -= dy;
        if (error < 0)
        {
            y += ystep;
            error += dx;
        }
    }
}

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

Пример кода рисования окружности на C#.

void BresenhamCircle(int x0, int y0, int radius)
{
    int x = radius;
    int y = 0;
    int radiusError = 1 - x;
    while (x >= y)
    {
        DrawPoint(x + x0, y + y0);
        DrawPoint(y + x0, x + y0);
        DrawPoint(-x + x0, y + y0);
        DrawPoint(-y + x0, x + y0);
        DrawPoint(-x + x0, -y + y0);
        DrawPoint(-y + x0, -x + y0);
        DrawPoint(x + x0, -y + y0);
        DrawPoint(y + x0, -x + y0);
        y++;
        if (radiusError < 0)
        {
            radiusError += 2 * y + 1;
        }
        else
        {
            x--;
            radiusError += 2 * (y - x + 1);
        }
    }
}

Теперь про алгоритм У Сяолиня для рисования сглаженных линий. Он отличается тем, что на каждом шаге ведётся расчёт для двух ближайших к прямой пикселей, и они закрашиваются с разной интенсивностью, в зависимости от удаленности. Точное пересечение середины пикселя даёт 100% интенсивности, если пиксель находится на расстоянии в 0.9 пикселя, то интенсивность будет 10%. Иными словами, сто процентов интенсивности делится между пикселями, которые ограничивают векторную линию с двух сторон.

Брезенхем и У на страже диагоналей

На картинке выше красным и зелёным цветом показаны ошибки двух пикселей. Остальное по-старому.

Для расчёта ошибки можно использовать переменную с плавающей запятой и брать значение ошибки из дробной части.

Примерный код сглаженной линии У Сяолиня на C#.
private void WuLine(int x0, int y0, int x1, int y1)
{
    var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0);
    if (steep)
    {
        Swap(ref x0, ref y0);
        Swap(ref x1, ref y1);
    }
    if (x0 > x1)
    {
        Swap(ref x0, ref x1);
        Swap(ref y0, ref y1);
    }

    DrawPoint(steep, x0, y0, 1); // Эта функция автоматом меняет координаты местами в зависимости от переменной steep
    DrawPoint(steep, x1, y1, 1); // Последний аргумент — интенсивность в долях единицы
    float dx = x1 - x0;
    float dy = y1 - y0;
    float gradient = dy / dx;
    float y = y0 + gradient;
    for (var x = x0 + 1; x <= x1 - 1; x++)
    {
        DrawPoint(steep, x, (int)y, 1 - (y - (int)y));
        DrawPoint(steep, x, (int)y + 1, y - (int)y);
        y += gradient;
    }
}

Если вам вдруг в будущем придётся работать с сетками, задумайтесь ненадолго, возможно вы изобретаете велосипед и на самом деле вы работаете с пикселями, хотя и не знаете этого. Модификации этих алгоритмов можно использовать в играх для поиска ячеек перед юнитом на карте, расчёта области поражения выстрела или красивой расстановки объектов. Или можно просто рисовать линии, как в программе по ссылкам ниже.

Unity Web Player | Windows | Linux | Mac | Исходники на GitHub
Левая кнопка мыши — Брезенхем, правая кнопка мыши — У, пробел — очистить, Esc — выход.
Для пользователей Linux: Сделайте файл BresenhamWu исполняемым с помощью «chmod +x BresenhamWu» и запускайте.

На Rosetta Code есть код на разных языках для алгоритма Брезенхема и алгоритма У. Ссылка на статью У Сяолиня

Автор: BasmanovDaniil

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js