Часть III / Лекция 13. Аппроксимация непрерывного пространства в дискретной реализации

Отрисовка линий

Итак, мы вплотную подошли к задачам алгоритмизации компьютерной графики. Начнем с основных алгоритмов рисования прямой линии.

Монитор компьютера состоит из конечного числа точек, а линия по физической природе является непрерывной, состоящей из бесконечного числа точек. Поэтому возникают проблемы представления непрерывного объекта в дискретном пространстве. Очевидно, что прямые отрезки на экране должны выглядеть прямыми, начинаться и заканчиваться в заданных точках; яркость вдоль отрезка должна быть постоянной и не зависеть от наклона, и наконец, рисовать нужно быстро. Понятно, что не все требования могут быть реализованы с абсолютной точностью: например, сама природа растрового дисплея исключает генерацию абсолютно прямых линий (кроме строго горизонтальных и вертикальных отрезков), возникает проблема оптимального выбора наиболее подходящего пиксела — от этого напрямую зависит результат:

Алгоритм Брезенхема

Этот алгоритм выбирает оптимальные растровые координаты для представления отрезка.

Из рис. 13.2 мы видим как выбирается эта координата. Сначала измеряют ошибку (обозначим ее е) отхода пиксела от линии. Затем проверяют знак ошибки: если e > 0, то выбирают верхний пиксел, иначе нижний.

Вывод: ошибка — это интервал, отсекаемый по оси y рассматриваемым отрезком в любом растровом элементе (относительно -1/2).

Первое улучшение алгоритма Брезенхема

Недостаток предыдущего алгоритма заключается в том, что в нем используется деление, которое является очень медленной операцией. Исключим эту операцию и перейдем к работе с целыми числами. Чтобы избавиться от умножения, надо преобразовать декартовы координаты в экранные. Чтобы оперировать целыми числами е заменяют на e' = 2Dx * e = 2Dx * (Dy/Dx - 1/2) = 2Dy - 2Dx. Программа, написанная по такому улучшенному алгоритму, работает гораздо быстрее. Также этот алгоритм дает самую незазубренную линию.

Второе улучшение алгоритма Брезенхема

Попробуем теперь уменьшить зазубренность линий за счет применения полутонов: при наличии нескольких интенсивностей (оттенков) одного цвета внешний вид прямой может быть улучшен размыванием ее краев. Самый простой способ состоит в том, чтобы устанавливать интенсивность пиксела на прямой пропорционально площади части пиксела, находящейся внутри. В результате простой модификации алгоритма Брезенхема можно получить аппроксимацию площади части пиксела, находящейся внутри линии.

Поправка к старому алгоритму: e' = e + w = e + (1 - m), m = Dy * I/Dx, где I — интенсивность или максимальное число градаций при переходе от черного к белому. Ошибка e' учитывает площадь, отсекаемую от пиксела.

Новый алгоритм:

Алгоритм Флойда-Стейнберга

Алгоритм заключается в распределении ошибки по соседним пикселам (размазывание) всегда вниз и вправо. Введем понятие порога интенсивности: если интенсивность изображения превышает некую пороговую величину, то пиксел считается белым, иначе — черным. Эту величину обычно устанавливают приблизительно равной половине максимальной интенсивности: T = I_max/2, где T — пороговый параметр или середина диапазона градации, I_max — максимальное число градаций при переходе от черного к белому.

Если I < T, то Р_x (пиксел по х) = черный, ошибка = I — черный,
иначе Р_x (пиксел по х) = белый, ошибка = I — белый.
Пиксел справа: Р_x(x + 1, y) = Р_x(x + 1, y) + 3/8 ошибки.
Пиксел снизу: Р_x(x, y + 1) = Р_x(x, y - 1) + 3/8 ошибки.
Пиксел ниже справа: Р_x(x + 1,y - 1) = Р_x(x + 1,y - 1) + 1/4 ошибки.

В результате в изображении появляются дополнительные точки и исчезают резкие тени.