Растеризация

Растеризация отрезков отрезки должны начинаться и заканчиваться в заданных точках и выглядеть прямыми яркость вдоль отрезка должна быть постоянной и не зависеть от его длины и наклона отрисовка должна быть максимально быстрой

Типы отрезков Горизонтали Вертикали Диагонали Линии произвольного наклона

Алгоритм ЦДА дифференциальное уравнение прямой dy/dx = m решение уравнения численным методом m = (y2 – y1) / (x2 – x1) = Δy / Δx алгоритм x1 < x < x2, y = round (y + m)

Достоинства и недостатки Простота Возможность работы с нецелыми координатами Низкая скорость

Угол наклона и симметричность

Алгоритм Брезенхэма Bresenham algorithm Анализ угла наклона прямой. Приращение по ведущей оси на каждом шаге равно 1. Приращение по другой оси (0 или 1) выбирается в зависимости от расстояния между действительным положением отрезка и ближайшими координатами сетки.

Анализ ошибки ½ dy/dx 1 (е 0) 0 dy/dx < ½ (е < 0) е = – ½ е = е + dy/dx

Усовершенствования алгоритма Брезенхэма переход к целым числам универсальность (независимость от октанта и угла наклона) учет требований по устранению ступенчатости (яркость пиксела изменяется в зависимости от расстояния до прямой)

Алгоритм вывода толстых линий использование фигуры или линии в качестве элемента вывода вывод полигона с заполнением последовательная отрисовка нескольких тонких линий

Растеризация окружности Симметрия окружности Прямое вычисление координат (неэффективно)

Алгоритм Брезенхэма начальная точка x = 0; y = R выбирается тот пиксел, для которого минимален квадрат расстояния до контура окружности: Δ1 = (х+1) 2 + у 2 – R 2 Δ2 = (х+1) 2 + (у-1) 2 – R 2 Δ3 = х 2 + (у-1) 2 – R 2

Заливка многоугольников алгоритмы закрашивания от внутренней точки к границам контура (с затравочной точкой); алгоритмы, использующие математическое описание контура