Алгоритмы краевого анти-алиасинга

Рис.6. Фильтрация для прямой.

Алгоритм Гупты-Спрулла

Данный алгоритм для растеризации отрезков с целочисленными координатами концов был предложен Гуптой и Спруллом в статье. В нем предполагается использование радиально-симметричного фильтра (такого как конический). Пусть его радиус равен R. Для того чтобы выяснить, каким цветом следует закрасить пиксель, необходимо посчитать значение свертки фильтра с функцией прямой (I = 1 в вытянутом прямоугольнике толщиной t и 0 вне него), см. рис.6. Обозначим результат этой операции FR,t (r), где r - расстояние от центра закрашиваемого пикселя до центральной оси прямой. Заметим, что FR,t (r) = 0 для r > R + t/2.

Рис.7. Алгоритм Гупты-Спрулла.

Идея алгоритма состоит в одновременной закраски нескольких пикселей разной интенсивности в столбце (см. рис.7.). Речь идет о случае наклона прямой меньше чем на . Случай вертикального наклона аналогично просто сводится к первому случаю.

Количество пикселей, которые могут быть закрашены в одном столбце зависит от t и R, а также от наклона прямой. Канонически будем полагать радиус фильтра R = 1 и толщину отрезка t = 1. Тогда максимально может быть закрашено 4 пикселя при наклоне, близком к . Если рассматривать конический фильтр, то в случае 4 пикселей возможный вклад самого верхнего или нижнего будет достаточно мал, поэтому для упрощения алгоритма будем закрашивать только ближайшие 3 к пересечению прямой с вертикалью пикселя.

Пусть строится отрезок .

Обозначим нижний текущий пиксель P2, нижний - P1, а верхний - P3 (см. рис.7). Пусть v - расстояние от центральной точки между рассматриваемыми пикселями до выбранного пикселя P2. Оно может быть как положительным (если выбран шаг s), так и отрицательным (если выбран шаг d). Тогда соответствующие расстояния до оси прямой равны , где равен углу наклона прямой (см. рис.7.), т.е. .

Несложно заметить, что , или . Тогда . Для ускорения вычислений построим дискретную аппроксимацию FR,t (r), разбив интервал [0, R+t/2] на равные части и аппроксимируя значение F в каждом интервале значением в центре этого интервала. Получим таблицу значений интенсивности ITable.

Пусть функция round находит номер интервала по действительному значению в [0, R+t/2]. Тогда получаем следующий алгоритм: // plot (x,y, I) закрашивает пиксель (x,y) с интенсивностью I

= 2b - a;

ΔeS = 2b;

ΔeD = 2b - 2a;= 1/ (2*sqrt (a*a+b*b));= 2a*denom; // фикс. часть r_1 и r_3

// (x,y) - Координаты текущей точки

x= 0; y = 0;

while (x < a)

{= (e+a) *denom;(x, y-1, ITable [round (fixPart+av2)]);(x, y, ITable [round (abs (av2))]);(x, y+1, ITable [round (fixPart-av2)]); (e > 0)

{

// d: диагональное смещение

x++; y++;

e += ΔeD;

}

else

{

// s: горизонтальное смещение

x++;

e += ΔeS;

}

}

Перейти на страницу: 1 2 3

Другие публикации

Unix-подобные системы
UNIX — группа переносимых, многозадачных и многопользовательских операционных систем. Первая система UNIX была разработана в 1969 г. в подразделении Bell Labs ком ...

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

Меню

Copyright @2020, TECHsectors.ru.