Базовые растровые алгоритмы.

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

Алгоритмы растеризации.

Связность – возможность соединения двух пикселей растровой линией, т. е. последовательным набором пикселей.

1. Четырехсвязность: пиксели считаются соседними, если либо их x-координаты, либо их y – координаты отличаются на единицу: .

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

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

Растровое представление отрезка.

Рассмотрим задачу построения растрового изображения отрезка, соединяющего точки и . Для простоты будем считать, что . Тогда отрезок описывается уравнением: или .

Отсюда получаем простейший алгоритм растрового представления отрезка:

void line(int xa, int ya, int xb, int yb, int color){

double k = ((double)(yb – ya)) / (xb – xa);

double b = ya – k * xa;

for (int x = xa; x <= xb; x++)

putpixel(x, (int)(k * x + b), color);

}

Приведенный простейший пошаговый алгоритм построения отрезка имеет ряд недостатков:

1. Выполняют операции над числами с плавающей точкой, а желательно было бы работать с целочисленной арифметикой;

2. На каждом шаге выполняется операция округления, что также снижает быстродействие.

Эти недостатки устранены в следующем алгоритме Брезенхейма.

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

Как и в предыдущем случае, будем считать, что тангенс угла наклона отрезка принимает значение в диапазоне от 0 до 1. Рассмотрим i-й шаг алгоритма (см. рисунок). На этом этапе пиксель уже найден как ближайший к реальному отрезку. Требуется определить, какой из пикселов ( или ) будет установлен следующим.

В алгоритме используется управляющая переменная , которая на каждом шаге пропорциональна разности между S и T. Если S<T, то ближе к отрезку и выбираем ее, иначе выбирается .

Пусть изображаемый отрезок проходит из точки в точку . Исходя из начальных условий, точка ближе к началу координат. Тогда перенесем оба конца отрезка, так чтобы первый конец отрезка совпал с началом координат. Начальной точкой отрезка стала точка (0, 0), конечной точкой стала (dx, dy), где , .

Итеративная формула вычисления управляющего коэффициента по предыдущему значению имеет вид: . {Вычисляется она из подобия треугольников: .

Находим T, как

Помножим левую и правую часть этого выражение на dx. И заменяем , , = }.

С помощью управляющего коэффициента выбирается следующий пиксель или .

Если , тогда выбирается и , .

Если , тогда выбирается и , .

Начальные значения , т.к. .

Преимуществом алгоритма является то, что для работы алгоритма требуются минимальные арифметические возможности: сложение, вычитание и сдвиг влево для умножения на 2.

Если dy>dx, то необходимо будет использовать этот же алгоритм, но пошагово увеличивая y и на каждом шаге вычислять x.