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

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

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

Принцип работы алгоритма Брезенхема очень простой. Берётся отрезок и его начальная координата 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 вместо единицы. Также можно немного поменять логику, «передвинуть» ошибку так, чтобы граница была в нуле, и можно было проверять знак ошибки, это может быть быстрее.

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

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

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%. Иными словами, сто процентов интенсивности делится между пикселями, которые ограничивают векторную линию с двух сторон.

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

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

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 есть код на разных языках для алгоритма Брезенхема и алгоритма У. Ссылка на статью У Сяолиня