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

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

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

Понятие 4-связности является более сильным, чем 8-связность:
любые два 4-связных пиксела являются и 8-связными, но не наоборот
Соседи пикселей:

Простейший алгоритм растрового представления отрезка
// File Line1.cpp
void Line ( int x1, int y1, int x2, int y2, int color )
{
double k = ((double)(y2-yl))/(x2-xl):
double b = y1 - k*x1;
for ( int x = x1; x <= x2; x++ ) putpixel ( x, round ( k*x + b ), color );
}

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

В 1965 году Брезенхейм предложил простой целочисленный алгоритм для растрового построения отрезка, первоначально предназначенный для использования в графопостроителях.
Алгоритм выбирает оптимальные растровые координаты для представления отрезка.
В процессе работы одна из координат – либо x, либо y изменяется на единицу.
Изменение другой координаты (либо на нуль, либо на единицу) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние назовем ошибкой.

Отрезок проходит через точку растра (0,0) и последовательно пересекает три пиксела.
Также иллюстрируется вычисление ошибки при представлении отрезка дискретными пикселами.

Алгоритмы построения отрезка имеют ряд недостатков:
1. выполняют операции над числами с плавающей точкой, а желательно было бы работать с целочисленной арифметикой;
2. на каждом шаге выполняется операция округления, что также снижает быстродействие.

Пиксель Pi-1 уже найден как ближайший к реальному отрезку.
Требуется определить, какой из пикселов (Ti или Si) будет установлен следующим.
В алгоритме используется управляющая переменная di, которая на каждом шаге пропорциональна разности между S и T.
Если S < T, то Si ближе к отрезку, иначе выбирается Ti.

Пусть отрезок проходит из точки (x1, y1) в точку (x2, y2).
Исходя из начальных условий, точка (x1, y1) ближе к началу координат.
Перенесем оба конца отрезка с помощью преобразования T(–x1, –y1), так чтобы первый конец отрезка совпал с началом координат.
Начальной точкой отрезка стала точка (0, 0), конечной точкой – (dx, dy), где dx = x2 – x1, dy = y2 – y1

di = 2 xi-1 dy –2 yi-1 dx + 2 dy – dx.
di+1 = 2 xi dy –2 yi dx + 2 dy – dx.
di+1 – di = 2 dy (xi – xi-1) – 2 dx (yi – yi-1).
Известно, что xi – xi-1 = 1, тогда
di+1– di = 2 dy – 2 dx (yi – yi-1).
или
di+1 = di + 2 dy – 2 dx (yi – yi-1) - итеративная формула вычисления управляющего коэффициента di+1 по предыдущему значению di.

Если di ≥ 0, тогда выбирается Ti и
yi = yi–1 + 1, di+1 = di +2 (dy – dx).
Если di < 0, тогда выбирается Si и
yi = yi–1 и di+1 = di +2 dy.
Начальные значения d1 с учетом того, что
(x0, y0) = (0, 0), d1 = 2 dy – dx.
Преимущество: для работы алгоритма требуются минимальные арифметические возможности: сложение, вычитание и сдвиг влево для умножения на 2.

void MyLine(int x1, int y1, int x2, int y2, int c)
{
int dx, dy, inc1, inc2, d, x, y, Xend;
dx = abs(x2 - x1);
dy = abs(y2 - y1);
d = dy << 1 - dx;
inc1 = dy << 1;
inc2 = (dy - dx) << 1;
if (x1>x2)
{
x = x2;
y = y2;
Xend = x1;
}
else
{
x = x1;
y = y1;
Xend = x2;
};
putpixel(x, y, c);
while (x < Xend)
{
x++;
if (d < 0) d = d + inc1;
else
{
y++;
d = d + inc2;
};
putpixel(x, y, c);
};
}
Если dy > dx, то необходимо будет использовать этот же алгоритм, но пошагово увеличивая y и на каждом шаге вычислять x.

Методы устранения ступенчатости
Основная причина появления лестничного эффекта заключается в том, что отрезки, ребра многоугольника, цветовые границы и пр. имеют непрерывную природу, тогда как растровые устройства дискретны.
Лестничный эффект проявляется:
1) при визуализации мелких деталей;
2) при прорисовке ребер и границ;
3) при анимации мелких деталей.

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

Метод, основанный на использовании полутонов
Интенсивность пикселя на ребре устанавливается пропорционально площади части пикселя, находящегося внутри многоугольника.

Растровое представление окружности

Окружность в I октанте сгенерирована.
II октант получается зеркальным отражением относительно прямой y=x.
Получаем I квадрант.
Отражаем полученную часть окружности относительно прямой x=0.
Получаем часть окружности во II квадранте.
Верхнюю часть окружности отражаем относительно прямой y=0.
Получаем окружность.

Двумерные матрицы соответствующих преобразований

Отсечение отрезка. Алгоритм Сазерленда'Кохена
Цель алгоритма: определение тех точек отрезка, которые лежат внутри отсекающего окна.

Отрезок называется видимым (лежащим внутри окна), если обе его концевые точки лежат внутри окна, например, отрезок ab.
Если оба конца отрезка лежат справа, слева, выше или ниже окна, то этот отрезок называется невидимым (целиком лежит вне окна), например отрезок ij.
Все остальные отрезки называются частично видимыми и к ним нужно применять алгоритмы отсечения.

для 1 бита – если точка левее окна
для 2 бита – если точка правее окна
для 3 бита – если точка ниже окна
для 4 бита – если точка выше окна