10. Растровые алгоритмы

10.1. Понятие связности

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

• переведение идеального объекта (отрезка, окружности и др.) в их растровые образы;

• обработка растровых изображений.

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

    Достаточно важным понятием для растровой сетки является связность – возможность соединения двух пикселов растровой линией, т. е. последовательным набором пикселов. Возникает вопрос, когда пикселы (х₁,y₁) и (x₂,y₂) можно считать соседними.

Вводится два понятия связности:

• 4-связность: пикселы считаются соседними, если либо их x-координаты, либо их y-координаты отличаются на единицу (рис. 10.1.1):

Рис. 10.1.1. Пример 4-связности

• 8-связность: пикселы считаются соседними, если их x-координаты и у-координаты отличаются не более чем на единицу (рис. 10.1.2):

Рис. 10.1.2. Пример 8-связности

Понятие 4-связности является более сильным: любые два 4-связных пиксела являются и 8-связными, но не наоборот. На рис. 10.1.3 изображена 8-связная линия, а на рис. 10.1.4  4-связная линия.

В качестве линии на растровой сетке выступает набор пикселов P₁ P₂,..., Р_n, где любые два пиксела P_i, P_i+1 являются соседними в смысле заданной связности.

    Замечание. Так как понятие линии базируется на понятии связности, то естественным образом возникает понятие 4- и 8-связных линий. Поэтому, когда мы говорим о растровом представлении (например, отрезка), следует ясно понимать, о каком именно представлении идет речь. В общем случае растровое представление объекта не является единственным и возможны различные способы его построения.

Рис. 10.1.3. 8-связная линия       Рис 10.1.4. 4-связная линия

10.2. Растровое представление отрезка. Алгоритм Брезенхейма

Рассмотрим задачу построения растрового изображения отрезка, соединяющего точки А(х_а, у_a) и В(х_b, y_b). Для простоты будем считать, что

.

Тогда отрезок описывается уравнением

где

Однако взятие целой части у может приводить к не всегда корректному изображению.

Улучшить внешний вид получаемого отрезка можно за счет округления значений y до ближайшего целого. Фактически это означает, что из двух возможных кандидатов (пикселов, расположенных друг над другом так, что прямая проходит между ними) всегда выбирается тот пиксел, который лежит ближе к изображаемой прямой (рис. 10.2.1). Для этого достаточно сравнить дробную часть y с 1/2.

Рис. 10.2.1. Отрезок, получаемый, в соответствии с алгоритмом Брезенхейма

Пусть х₀ = х_а, у₀, ..., х_n = х_b, y_n = у_b – последовательность изображаемых пикселов, причем х_i + 1 – x_i = 1. Тогда каждому значению x_i  соответствует число kx_i + b.

Обозначим через с_i дробную часть соответствующего значения функции kx_i + b – c_i = {kx_i + b}.

Тогда, если c_i ≤ ½, положим y_i = [kx_i + b], в противном случае –

y_i = [kx_i + b] + 1.

Рассмотрим, как изменяется величина с_i при переходе от x_i к следующему значению x_i + 1.

Само значение функции при этом изменяется на k.

Если с_i + k ≤ ½, то c_i + 1 = c_i + k, y_i + 1 = y_i.

В противном случае необходимо увеличить у на единицу и тогда приходим следующим соотношениям:

c_i + 1 = c_i + k – 1, y_i + 1 = y_i + 1,

так как

kx_i + b = y_i + c_i,

kx_i + 1 + b = y_i + 1 + c_i + 1,

а y_i + 1 – целочисленная величина.

Заметим, что с₀ = 0, так как точка (x₀ , у₀) лежит на прямой y = kx + b.

Замечание. Выбор точки можно трактовать и так: рассматривается середина отрезка между возможными кандидатами и проверяется, где (выше или ниже этой середины) лежит точка пересечения отрезка прямой, после чего выбирается соответствующий пиксел. Это метод срединной точки (midpoint algorithm).

Сравнивать с нулем удобнее, чем с 1/2, поэтому введем новую вспомогательную величину d_i = 2с - 1, заметив, что, d_i = 2k - 1 (так как с₁ = k).     Несмотря на то, что и входные данные являются целочисленными величинами и все операции ведутся на целочисленной решетке, алгоритм использует операции с вещественными числами. Чтобы избавиться от необходимости их использования, заметим, что все вещественные числа, присутствующие в алгоритме, являются числами вида p/Δx, p Є Z     Поэтому если помножить величины d_i и k на Δx = x_b - x_a в результате этого останутся только целые числа. Тем самым мы приходим к алгоритму Брезенхейма.