На что вы сейчас смотрите? Если вы не из параллельной вселенной, где все сидят за векторными мониторами, то перед вами растровое изображение. Поглядите на эту полоску: /. Если придвинуться поближе к монитору, то можно увидеть пиксельные ступеньки, которые пытаются притвориться векторной линией. Для этой цели существует целая куча всевозможных алгоритмов растеризации, но я бы хотел рассказать об алгоритме Брезенхема и алгоритме У, которые находят приближение векторного отрезка в растровых координатах.
С проблемой растеризации мне довелось столкнуться во время работы над процедурным генератором планов зданий. Мне нужно было представить стены помещения в виде ячеек двумерного массива. Похожие задачи могут встретиться в физических расчётах, алгоритмах поиска пути или расчёте освещения, если используется разбиение пространства. Кто бы мог подумать, что знакомство с алгоритмами растеризации однажды может пригодиться?
Принцип работы алгоритма Брезенхема очень простой. Берётся отрезок и его начальная координата 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 есть код на разных языках для алгоритма Брезенхема и алгоритма У. Ссылка на статью У Сяолиня
Автор: BasmanovDaniil
