2 Должна использоваться только целочисленная арифметика.
3 Минимальный расход памяти.
4 Желательно, чтобы алгоритм был инкрементным (цикл не должен делать повторные вычисления, а должен корректировать ранее полученные).
5 Примитивы должны быть восьми- или четырёхсвязными (сколько соседних пикселов, с которыми связан текущий).
Методы растеризации отрезка:
1 DDA (Digital Difference Analytics). Интересен с теоретической точки зрения. Каждая точка отрезка определяется как
x(t) = x0 + Δx * t
y(t) = y0 + Δy * t
t ϵ [0,1]
где
Δx = (x1 – x0) / L
Δy = (y1 – y0) / L
L = max( |x1 – x0| , |y1 – y0| )
2 Алгоритм Брезенхема. Рассмотрим случай построения отрезка из точки (0,0) в заданную точку в первом октанте (остальные случаи получаются с использованием поворота, симметрии и т.п.)
Делаем x шагов, на каждом шаге перемещаемся либо вправо, либо по диагонали вправо-вверх и считаем ошибку е — расстояние между реальной точкой на отрезке и координатами пикселя.
○ Если е < ½ , то идём вправо и увеличиваем ошибку е = е + dy/dx
○ Если e ≥ ½, то идём по диагонали и уменьшаем ошибку: е = е - 1
Недостатки:
○ алиасинг (при большом растре видна ступенчатость)
○ использование вещественной арифметики
Чтобы исправить второй недостаток, можно внести следующие изменения:
○ изначально из е вычесть ½
○ сравнивать ошибку не с ½, а с нулём
○ умножить приращения e на 2dx:
■ при шаге вправо: е = е + 2dy,
■ при шаге по диагонали: e = e - 2dx.
При отрисовке текущего пикселя необходимо знать ошибку е для следующего шага, чтобы принять решение, куда идти.
Сам алгоритм (вариант с целочисленной арифметикой):
x = x1;
y = y1;
Dx = x2-x1;
Dy = y2-y1;
e = 2*Dy-Dx; // e = -Dx; ?
for (i = 1; i < Dx; i++)
{
Plot(x, y); //отрисовка точки
if (e >= 0)
{
y++;
e-=2*Dx;
}
x++;
e+=2*Dy;
}
3 Алгоритм Ву (модификация алгоритма Брезенхема)
На каждом шаге рисуем не одну точку, а две, причём яркости распределяем между ними в зависимости от величины ошибки e:
а) шаг по горизонтали б) шаг по диагонали
Рассмотрим случай рисования дуги, которая находится в третьем и четвёртом октантах (остальные части окружности рисуются аналогично).
Инициализируем x=-R, y=0. Можем двигаться либо вверх, либо по диагонали вправо-вверх.
Пиксель может находиться либо внутри окружности, либо вне её. Расстояние от пикселя до окружности:
f(x,y) = x2 + y2 - R2
Если f(x,y) > 0, то пиксель находится вне окружности, делаем шаг по диагонали
Иначе — внутри, делаем шаг вверх.
Шаг — это x++ и y++, при этом пересчитываем f(x,y).
При рисовании эллипса необходимо умножать x или y на некоторый коэффициент. До точки касания эллипса с касательной 45° шаг делается по диагонали, либо по горизонтали, а после — по горизонтали либо по вертикали.
Отрисовка дуг
Задаются: центр, радиус R, α и β. Для каждого октанта прорисовывается часть дуги, которая попадает в этот октант. Как проверить, попадает ли пиксель в октант? Можно найти точки Z, и если пиксель попадает в промежуток между ними, то он попадает в октант.