Анти-алиасинг изображения

КУРСОВАЯ РАБОТА Тема: «Анти-алиасинг изображения»

• Введение
• 1. Искажение сигнала и борьба с этим эффектом
• 2. Краевой и полный анти-алиасинг
• 3. Алгоритмы краевого анти-алиасинга
• 4. Методы полного анти-алиасинга
• 5. Суперсэмплинг
• 6. Мультисэмплинг
• 7. Общие подходы на практике
• Заключение
• Список используемой литературы

Как следует из приставки «анти», эта технология призвана бороться с алиасингом. Что же это такое? Не так давно, слова «алиасинг» и «анти-алиасинг» были совершенно неизвестны широкой общественности. А между тем, проблема алиасинга стояла очень давно. Чтобы понять, что такое алиасинг, необходимо понять самый общий принцип вывода изображения на экран монитора.

Экран состоит из сотен тысяч очень мелких квадратов (обычно, называемых точками или пикселями) — примерно как бумага в клетку, только гораздо мельче. Каждый квадрат (точка, пиксель, клетка) может быть закрашена только одним цветом. Так, например, когда говорят, что установлено разрешение 1024×768 True Color, это значит, что по горизонтали на экране помещаются 1024 точки, а по вертикали — 768 точек, т. е. всего на экране 1024*768=768 432 точек, каждая из которых может быть закрашена любым из доступных.

Обратите внимание, что рисунок, состоящий из таких больших точек, выглядит странно. Собственно, это и есть алиасинг — на краях букв видны «ступеньки». Самое очевидное решение проблемы — уменьшить точки. К сожалению, экран монитора имеет очень существенный недостаток: он не позволяет сделать точки настолько малыми, чтобы взгляд не мог их различить. Для сравнения: хороший принтер может печатать изображения с разрешением 2048×2048 точек на дюйм и больше, в то время, как лучшие мониторы ограничены разрешением около 100×100 точек на дюйм.

На первый взгляд, задача кажется невыполнимой: из цельных кирпичей круглое колесо не сделать никак! Но оказалось, что решение все-таки есть. При помощи плавных переходов цветов на изображении, можно очень существенно сгладить «ступеньки», т. е. как бы компенсировать недостаток пространственного разрешения цветовым. Это стало всем очевидно еще с появлением видеоадаптера VGA, поддерживающим 2 новых разрешения — 640×480 16 цветов и 320×200 256 цветов. Самое интересное в том, что многие игры работали в разрешении 320×200 и имели на порядок более качественную графику, чем игры, использующие режим 640×480! Все дело в том, что большее количество цветов (256 против 16) позволило сделать плавные переходы между цветами и не только компенсировать потери в разрешении, но и получить существенно более качественную графику и даже показывать настоящие фотографии, вместо простенькой «мультяшной» графики в режиме 640×480. Основано это на особенности зрения человека, которое стремится сгладить плавные переходы между близкими цветами, усиливая эффект.

1. Искажение сигнала и борьба с этим эффектом

Как доказано в теореме Найквиста-Котельникова, при недостаточной частоте дискретизации восстановленный сигнал будет искажен. Это наглядно можно наблюдать в частотной области (см. рис.1), т.к. при этом копии частотного спектра исходного сигнала будут суммироваться в пересекающихся областях, что даст мнимое увеличение веса компонент с этими частотами в спектре, некую подмену высокочастотных компонент низкочастотными, эффект, известный как алиасинг (англ. aliasing). Особенно наглядно этот эффект можно наблюдать на резких контрастных изменениях яркости (см. рис.2). Этот эффект легко объясним, если рассмотреть прямоугольный сигнал и его Фурье-образ (sinc), который имеет спектр бесконечной ширины (см. рис. 3, прямоугольный фильтр).

Для борьбы с подобными явлениями применяют префильтрацию — свертку с некой функцией фильтра, что эквивалентно умножению на Фурье-образ функции-фильтра в частотной области, перед тем как производится дискретизация. Цель префильтрации — заранее отсечь высокочастотные компоненты, которые могут привести к алиасингу. В идеале, для этого следовало бы применять функцию sinc, действие которой как раз и состоит в отсечении высоких частот, но она имеет бесконечный носитель, что затрудняет ее применение в пространственной области. На практике используются различные аппроксимации с ограниченным носителем (см. таблицу 1 и рис. 4 и 5). Гауссовский фильтр обычно применяется с (так он лучше всего приближает sinc в частотной области), R берется порядка 2−3. У кубического фильтра присутствует параметр, с помощью которого можно регулировать степень размытия (увеличение) или, наоборот, более четкой передачи краев несмотря на некоторый алиасинг (уменьшение), стандартным компромиссным значением является. Для Lanzcos, который представляет собой обрезанный и сглаженный sinc, радиус R обычно равен 2 (так называемый Lanzcos2), реже — до 4. Большие значения не используются ввиду того, что носитель, а значит, и область интегрирования при свертке, будет слишком большой.

Рис. 1. Эффект алиасинга при недостаточной частоте дискретизации.

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

(1)

где — функция фильтра с центром в 0, supp (F) — ее носитель (область, где она не равна 0), — непрерывное аналоговое изображение.

Рис. 2. Видимый эффект алиасинга на изображении: слева — исходное изображение без анти-алиасинга, справа — с анти-алиасингом.

Рис. 3. Функция-фильтр Sinc.

Таблица 1. Одномерные функции-фильтры для анти-алиасинга

Двумерные аналоги одномерного фильтрастроятся двумя путями:

как функция от радиуса:

;

как произведение:

.

Первый вариант — более корректный, но второй обладает свойством сепарабельности, т. е. в выражении (1) можно двумерное интегрирование разбить на два одномерных:

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

алиасинг мультисэмплинг изображение сигнал Рис. 4. Фильтры для анти-алиасинга.

Рис. 5. Фильтры для анти-алиасинга (продолжение).

Двумерные аналоги фильтров, представленных в таблице 1 и на рис. 4 и 5, приведены в таблицах 2, 3 (для простоты частота дискретизации равна 1, произвольный случай получается масштабированием по осям). Прямоугольный фильтр соответствует либо цилиндру (первый тип), либо параллелепипеду с квадратным основанием (англ. Box filter) (второй тип); треугольный соответствует либо конусу, либо пирамиде соответственно. По смыслу прямоугольные и треугольные аналоги соответствуют так называемым не взвешенной и взвешенной площадным выборкам. Если рассмотреть Фурье-образы их одномерных аналогов, можно заметить, что взвешенная площадная выборка лучше отфильтровывает высокие частоты, поэтому рекомендуется применять именно ее.

Таблица 2. Радиально-симметричные фильтры для анти-алиасинга

Таблица 3. Одномерные функции-фильтры для анти-алиасинга

2. Краевой и полный анти-алиасинг

Краевой анти-алиасинг — механизм борьбы с лестничным эффектом. Краевой анти-алиасинг сглаживает края полигонов и диагональные линии.

Для реализации краевого антиалиасинга чаще всего используют технику усреднения по площади (area averaging). Цвет пиксела определяется на основании того, насколько каждый полигон перекрывает данный пиксел. Например, как показано на рисунке ниже, пиксел перекрывают два полигона: A и B. Метод усреднения по площади определяет видимые области, занимаемые полигонами, которые «прикасаются» к пикселу, и вычисляет результирующий цвет на основании видимых площадей перекрытия (то есть принадлежащих и пикселу, и полигону). Пусть полигон A занимает 40% площади пиксела, а полигон B — 60%. Результирующий цвет в этом случае определяется цветами A и B c весовыми коэффициентами 40% и 60% соответственно (то есть проводится операция альфа-смещения). Для линий и точек метод тот же самый, в данном случае считается, что линии и точки имеют ненулевую площадь.

К сожалению, альфа-смешение в краевом анти-алиасинге приводит к появлению артефакта под названием bleeding (дословно «кровоточение»). Bleeding — окрашивание внутренних ребер в цвет фона, это связано с тем, что между гранями образуется тонкий просвет. Поэтому программа сама должна знать, какие ребра и линии нужно сглаживать. Из-за этого краевой анти-алиасинг сложно программировать.

Полный антиалиасинг, в отличие от краевого, направлен на полную нейтрализацию алиасинга. Единственным представителем полного антиалиасинга является субпиксельный антиалиасинг. Субпиксельный антиалиасинг применяется в 3D-ускорителях PVNG, Intel740, nVidia Riva128 и TNT, а также во всех профессиональных OpenGL-ускорителях.

Субпиксельный антиалиасинг в Intel740 и nVidia Riva TNT базируется на технике суперсэмплинга. Суперсэмплинг означает, что вся сцена рендерится в каком-то большом виртуальном разрешении, а затем сжимается до фактического разрешения. В общем случае виртуальное и фактическое разрешения могут быть некратными. Техника суперсэмплинга возможна из-за того, что эти ускорители используют tile-based архитектуру. Ускорителю традиционной архитектуры потребовался бы большой объем памяти (для виртуального разрешения 1600×1200 — более 8 MB). Дело в том, что ускоритель tile-based архитектуры не работает с целым фреймбуфером, а с отдельными фрагментами (tiles). И все данные о субпикселах он хранит только для фрагмента, который рендерится в данный момент.

В 3D-ускорителях серии Glint от 3DLabs используется другой метод, основанный на хранении маски. Рассмотрим случай, когда 1 пиксел разбивается на 16 (4×4) субпикселов (эта техника называется мультисэмплингом), а полигоны рендерятся front-to-back (картинка снизу).

Когда рендерится полигон не переднем плане, субпикселы 2,3,4,7,8,12 окрашиваются в цвет переднего полигона. Причем запоминается, какие субпикселы попали в передний полигон, то есть маска. Эта маска проверяется когда рендерится задний полигон. Субпикселы 1,5,6,9 окрашиваются в цвет заднего полигона. Субпикселы 2,3, принадлежащие обоим полигонам, не изменяют цвет и таким образом остаются с цветом переднего полигона. В результате — никакого bleedingа.

Обратная сторона такого антиалиасинга — это необходимость хранения маски для каждого пиксела и требование сортировки полигонов front-to-back. Второе требование можно обойти, сохраняя z-координату для каждого субпиксела. Однако хранить z-координаты для всех субпикселей на экране невозможно, так как это требует гигантского объема видеопамяти.

Поддержку субпиксельного антиалиасинга с z-буферизацией реализует техника аккумулятора. Суть его сводится к тому, что обработка ведется последовательно для каждого пиксела и при этом используется одна и та же память.

Недостаток: из-за требования последовательной обработки невозможность аппаратного распараллеливания и как следствие уменьшение производительности в число раз, равное числу субпикселов в пикселе. Например субпиксельный антиалиасинг 4×4 снижает производительность в 16 раз, или другими словами увеличивает Fillrate в 16 раз.

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

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

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

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

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

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

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

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

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

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

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

e = 2b — a;

ДeS = 2b;

ДeD = 2b — 2a;

denom = 1/ (2*sqrt (a*a+b*b));

fixPart = 2a*denom; // фикс. часть r₁ и r₃

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

x= 0; y = 0;

while (x < a)

{

av2 = (e+a) *denom;

plot (x, y-1, ITable [round (fixPart+av2)]);

plot (x, y, ITable [round (abs (av2))]);

plot (x, y+1, ITable [round (fixPart-av2)]);

if (e > 0)

{

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

x++; y++;

e += ДeD;

}

else

{

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

x++;

e += ДeS;

}

}

Листинг 1. Алгоритм Гупты-Спрулла для отрезка

Алгоритм Ву

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

Пусть мы хотим растеризовать некоторую кривую. Без ограничения общности будем считать, что она локально наклонена горизонтально, т. е. ее можно представить как функцию y = f (x) и f' (x) < 1. При классической растеризации без анти-алиасинга для каждого столбца пикселей с абсциссой i просто закрашивается ближайший к f (i) пиксель с ординатой, т. е. минимизируется ошибка. В то же время Ву замечает, что при такой растеризации возможны неприятные визуальные эффекты (см. рис.8), и предлагает минимизировать динамическую ошибку, возникающую при растеризации и показывающую насколько искажается наклон кривой. Если часть кривой соответствует абсциссам в отрезке, то предлагается минимизировать норму матрицы, что в общем случае является вычислительно сложной задачей комбинаторной оптимизации.

Если же рассматривать возможность закрашивать пиксели с несколькими уровнями интенсивности, то можно в каждом столбце распределять исходную интенсивность в точке (i, f (i)) по двум соседним пикселям так, чтобы центр тяжести (если интенсивность рассматривать как массу) приходился на точку (i, f (i)); таким образом с учетом усреднения получаем E = 0. Пусть исходная интенсивность кривой равна I0, тогда, так что

Рис. 8. Погрешность при аппроксимации кривой.

Из этой системы легко получается решение:

(2). (3)

Если рассмотреть данный подход с точки зрения фильтрации, то сигнал здесь представлен объединением квадратов

и используется фильтр-параллелепипед радиуса ½ (см. рис.9).

Рассмотрим применение данного подхода к растеризации отрезка с целочисленными координатами концов. Пусть строится отрезок. Тогда прямая определяется формулой, где. Для максимального быстродействия будем проводить все вычисления приближенно, используя лишь целочисленную арифметику. Пусть D отвечает за дробную часть y.

где n — число разрядов в машинном представлении целых чисел. На каждом шаге будем прибавлять к D аппроксимацию k (обозначим ее d):

.

Рис. 9. Аппроксимация кривой по Ву.

Ошибка аппроксимации e=k-d2^-n не превосходит по модулю 2^-n. D естественным образом будет содержать дробную часть f (i), умноженную на 2ⁿ, т.к. машинная арифметика автоматически осуществляет сложение по модулю 2ⁿ.

Единственное, что нужно в тех случая, х когда происходит переполнение, увеличивать текущее значение y (которое отвечает за целую часть kx) на 1 (т.е. диагональный сдвиг).

Пусть значения интенсивности пикселя определяются m-разрядным числом, тогда максимальное значение I₀ = 2^m-1. m, как правило, много меньше n (обычно, m = 8, n = 32). В соответствии с уравнениями 2 для столбца с абсциссой x,

.

Учитывая, что I₊ должна быть целочисленной, пренебрежем последними двумя членами: I₊ = D2^n-m.

Фактически это целое, полученное из m старших двоичных разрядов D.

Отсюда довольно легко получить и (здесь означает двоичное дополнение). Это следует из того, что битовое представление 2^m — 1 — D2^m-n является двоичным дополнением D2^m-n.

Также используя оптимизацию, заключающуюся в одновременной закраске с двух концов (см. раздел 3.2), получаем следующий алгоритм.

// Координаты концов отрезка — (0,0) и (a, b)

// plot (x, y, I) закрашивает пиксель (x, y) с интенсивностью I

// I0 — максимальная интенсивность (2^m-1)

x0 = 0; x1 = a; y0 = 0; y1 = b;

plot (x0,y0, I0);

plot (x1,y1, I0);

D = 0;

d = floor ((b/a) *2^n + 0.5);

while (x0 < x1)

{

D = D + d;

if (произошло переполнение D)

{

y0++; y1—;

}

I1 = D / 2^ (n-m); // битовый сдвиг вправо на n-m

I2 = двоичное_доп (I1);

plot (x0,y0, I1);

plot (x1,y1, I1);

plot (x0,y0+1, I2);

plot (x1,y1−1, I2);

}

Листинг 2. Алгоритм Ву для отрезка

Хотя алгоритм Ву теоретически не очень качественный, т.к. использует грубую аппроксимацию кривой и грубый фильтр-параллелепипед, но на практике он успешно справляется с задачей анти-алиасинга, обладая при этом большей простотой реализации (в частности, аппаратно) и скоростью, чем алгоритм Гупты-Спрулла.

4. Методы полного анти-алиасинга

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

Мультисэмплинг — идея, по сути, очень проста: зачем просто так вычислять N субпикселей для каждого пикселя? Ведь, уже рассчитанные субпиксели, во многих случаях, можно использовать несколько раз, для формирования не одного, а нескольких результирующих пикселей. С другой стороны, в некоторых участках изображения, сглаживание не требуется вовсе, так зачем рассчитывать их по нескольким субпикселям? Достаточно и одного. И, наоборот, в других участках нужно очень хорошее качество сглаживания и там можно рассчитать очень много субпикселей.

Стоит отметить, что если каждый пиксель из области с текстурами, рассчитывается на основании нескольких «честных» субпикселей (т.е., не взятых у другого пикселя), то это весьма положительно сказывается на качестве. Чтобы объяснить почему, необходимо сделать небольшое отступление и рассказать о текстурах.

Текстура — это рисунок, имеющий определенное разрешение, допустим 256×256 точек. Если он накладывается на большой (или близкий) объект, занимающий область примерно 256×256, то все в порядке. А вот что делать, если объект занимает область, намного меньшую, чем разрешение текстуры, например 128×128? В этом случае, на один реальный пиксель приходится 4 текселя (так называется один пиксель текстуры) и физического разрешения не хватает для вывода текстуры. В обычном режиме, ускоритель снижает качество (разрешение) текстуры. Эта техника называется LOD (Level Of Detail) Biasing. К сожалению, она далеко не идеальна: текстуры упрощаются гораздо больше, чем необходимо потому, что метод применяется для всех текстур сразу, на определенном расстоянии от экрана, без учета размера объектов, на который они наложены и без учёта их разрешения. К счастью, уровень LOD Biasing можно изменять, т. е. текстуры с увеличением расстояния от наблюдателя будут упрощаться сильнее или слабее. Если LOD Biasing уменьшить, то текстуры будут упрощаться слабее, т. е. их четкость на удалении будет намного выше. Но, если слишком занизить Biasing, то на удаленных объектах появляется артефакт, называемый «дрожание текстур», «шум текстур», «песок» и пр. Выглядит это так: пиксели как будто разбросаны и явно находятся не на своем месте, причем, во время движения сцены, пиксели хаотично прыгают на новые места, в результате чего, на удаленных текстурах заметен шум, немного напоминающий то, что мы видим на экране телевизора после того, как канал прекратил свое вещание. Этот артефакт вызван тем, что текстура имеет большее разрешение, чем область экрана, отведенная для ее изображения.

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

5. Суперсэмплинг

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

Вот как это выглядит на практике, когда виртуальное разрешение в два раза выше итогового (видимого на экране монитора) по горизонтали и вертикали:

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

Несмотря на то, что метод давно реализован, по причине огромного падения скорости (в рассмотренном нами случае — примерно в четыре раза!), практически никакого распространения он не получал, до сравнительно недавнего времени — начала 2000 года. Именно тогда появились достаточно мощные ускорители, такие как NVIDIA GeForce2 GTS и ATI Radeon256.

В новых драйверах Detonator, серии 5. хх, NVIDIA раньше конкурентов реализовала возможность принудительного включения анти-алиасинга, в любых трехмерных играх, на всех видеокартах семейства GeForce. Это значит, что теперь от игры больше не требовалось, чтобы она сама включала анти-алиасинг: теперь это, при желании пользователя, делал драйвер.

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

Вскоре, после выхода GeForce2 GTS, ATI выпустила достойный ответ. Это был ускоритель Radeon256, составивший серьезную конкуренцию GeForce2. Естественно, не была обойдена вниманием ставшая тогда очень модной функция анти-алиасинга. ATI никак не усовершенствовала стандартную реализацию и, точно так же, ввела принудительное включение полноэкранного сглаживания в любых играх, поэтому нет смысла рассматривать ее отдельно (все, выше сказанное о суперсэмплинге, верно и для Radeon256).

6. Мультисэмплинг

Другой вид сглаживания, на основе мультисэмплинга, предложила NVIDIA в своем очередном поколении продуктов GeForce3, а затем немного доработала его, к выходу GeForce4.

ATI также не осталась в стороне. В ответ на семейство GF3, она выпустила очень серьезный продукт, помимо всего прочего, поддерживающий фирменный метод анти-алиасинга, альтернативный подходу NVIDIA.

В начале 2001 года NVIDIA выпустила на рынок новый ускоритель, приятно удивляющий количеством новых и усовершенствованных функций. Одной из них был новый метод полноэкранного сглаживания, называемый High-Resolution AntiAliasing (или просто HRAA). Вряд ли можно утверждать, что его качество превосходит качество традиционного суперсэмплинга, но скорость была очень и очень серьезно увеличена, что было направлено на решение главной проблемы анти-алиасинга, которая не снята до сих пор: падение скорости от включения этой функции часто так велико, что вместо нее можно увеличить разрешение, поставить максимальные настройки графики и иметь при этом большую скорость. Именно поэтому, некоторые люди, скептически относятся к анти-алиасингу, вообще не видя смысла в его применении в играх. Разберемся в принципах работы нового метода сглаживания.

Основная идея метода NVIDIA, позволившая столь существенно поднять скорость этой функции состоит в том, что сглаживание делается только на краях треугольников (полигонов) и не делается внутри них или за их пределами. Логика здесь проста: алиасинга не бывает внутри треугольников — с пикселизацией текстур справляются билинейная или анизотропная фильтрации. Алиасинга не бывает и за пределами всех треугольников, потому, что где нет треугольников, там нет и объектов, на которых можно наблюдать «лестничный эффект». То есть, ускоритель был освобожден от значительной части работы, связанной со сглаживанием всего изображения полностью, и делал сглаживание только там, где есть алиасинг.

Выгода от такого решения очевидна: серьезный прирост в скорости. Каковы же недостатки? Если вы помните, выше, в начале раздела, я рассказывал о том положительном влиянии, которое оказывает полноэкранное сглаживание на текстуры, значительно улучшая их качество. Так вот: HRAA не оказывает на текстуры никакого влияния вообще, ни положительного, ни отрицательного. Эта функция на 100% соответствует своему названию, специализируется исключительно на борьбе с эффектом алиасинга и ничего больше не делает (в отличие от суперсэмплинга, качественно сглаживающего все изображение без исключений).

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

7. Общие подходы на практике

Отсутствие анти-алиасинга.

Каждому пикселю соответствует один сэмпл (или субпиксель). Этот режим вряд ли требует комментариев. На рисунке показаны 4 пикселя. Номерами обозначены субпиксели (в дальнейшем, если номера одинаковы, то это один и тот же сэмпл, записанный несколько раз, если нет — то это разные сэмплы).

Анти-алиасинг 2x (1×2).

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

Здесь и далее, на рисунке, зеленой линией, обозначена граница между двумя полигонами. Сэмплы, на основе которых рассчитывается цвет пикселя, изображены маленькими кружками. Один и тот же сэмпл отображается одним цветом.

Анти-алиасинг 4x (2×2).

Каждому пикселю соответствует блок из четырех субпикселей. Аналогично режиму 1×2, если в пиксель попадает граница между полигонами (или край полигона), то рассчитывается два честных субпикселя (по одному на каждый полигон). Но, поскольку на пиксель приходится четыре сэмпла, то усредняются уже не два, а четыре значения. Так, первый полигон, граница которого проходит через рассматриваемый пиксель, может занимать один, два или три субпикселя, принадлежащего этому пикселю. Например, если один полигон занимает только один субпиксель, а второй — оставшиеся три, то для получения цвета результирующего пикселя, два цвета субпикселей будут смешиваться в аналогичной пропорции — один к трем.

Однако режим 2×2 не ограничен двумя честными сэмплами на пиксель. Так, например, если в один пиксель попадут четыре полигона (что, конечно, весьма маловероятно), то будут честно рассчитаны 4 субпикселя (по одному на каждый) и честно смешаны для получения результирующего цвета также, как делает суперсэмплинг в режиме 2×2.

Анти-алиасинг 4x (2×2) по девяти сэмплам.

Этот режим — аналог Quincunx, но только рассчитывающий четыре своих субпикселя (точно также, как при работе обычного режима 2×2) и «заимствующий» пять чужих, как это показано на рисунке. Достоинства и недостатки этого метода аналогичны Quincunx, но, поскольку доля честных сэмплов стала больше, размазанность изображения практически незаметна, а качество сглаживания повышается.

К сожалению, как и в случае с Quincunx, скорость работы этого метода заметно ниже аналогичного, «честного» метода — в данном случае 2×2.

Анти-алиасинг 4XS.

После выхода последнего, на сегодняшний день, ускорителя, анти-алиасинг NVIDIA приобрел, наконец, модное название: Accuview. Хотя, сам по себе, он практически не изменился. В драйверах был добавлен новый режим анти алиасинга — 4XS, который в закладках драйвера можно включить только при наличии карты на GeForce4, а через скрытые настройки — на любой карте семейства GeForce3. Если вы не являетесь счастливым обладателем карты на GeForce4, а всего лишь скромный обладатель GeForce3, то для включения этого режима придется либо залазить в реестр, либо просто не забывать, своевременно скачивать последние версии RivaTuner.

Суть нового режима анти-алиасинга в совместном использовании мультисэмплинга и суперсэмплинга для увеличения качества изображения. Проще всего это представить так: по горизонтали изображение сглаживается методом мультисэмплинга 1×2. Точно также, пиксель по горизонтали состоит из двух сэмплов, имеющих одинаковый цвет, если не находятся на краю полигона и два разных цвета, если на краю. Но, по вертикали, пиксель состоит не из одного такого блока из двух сэмплов, как режим мультисэмплинга 1×2, а из двух. Результирующий цвет пикселя определяется так: сначала находятся результирующие цвета верхнего и нижнего блока из двух сэмплов, затем они смешиваются. В итоге, пиксель рассчитывается на основе четырех сэмплов, точно также как и в режиме 4х. Но, в отличие от последнего, 4XS рассчитывает больше честных сэмплов и меньше использует один и тот же рассчитанный сэмпл (не более двух раз, в то время как 4x — до четырех раз).

Для примера, если пиксель находится в центре полигона или за пределами всех полигонов, то для верхнего и нижнего блока рассчитывается по одному честному сэмплу, то есть пиксель формируется на основании двух субпикселей (а в режиме 4х — на основании одного). В случае, если через пиксель проходит стык двух полигонов, то рассчитывается от двух, до четырех честных субпикселов, в зависимости от того, проходит край полигона ровно между двумя блоками, пересекает оба блока или пересекает только один блок, не затрагивая другой (режим 4х генерирует не более двух сэмплов на стыке двух полигонов или на краях одного).

Очевидно, что метод 4XS обеспечивает более качественное и полное сглаживание, чем режим 4x. Кроме краев полигонов он честно сглаживает по двум сэмплам все текстуры. А самое приятное заключается в том, что этот режим работает с той же скоростью, что и обычный 4x.

3dfx Voodoo 5.

До сих пор мы рассматривали методы сглаживания, в которых сэмплы располагаются упорядоченно, в виде прямой упорядоченной решетки, подобных клеточной бумаге. Недостаток подобной техники в том, что при сравнительно небольшом количестве сэмплов (от четырех до девяти на пиксель), которые используются в современных ускорителях для формирования пикселя, очень плохо сглаживаются линии (границы полигонов), близкие к вертикальным или близкие к горизонтальным, т. е. угол наклона которых относительно прямых составляет всего 10−15 градусов. Это связано с тем, что такой «почти вертикальный» или «почти горизонтальный» край треугольника в половине случаев проходит между двумя пикселями и потому, сглаживание никак его не затрагивает:

Решить эту проблему можно двумя способами:

Все больше увеличивать количество сэмплов, на основании которых формируется пиксель. Этот способ снижает вероятность того, что край полигона пройдет между двумя пикселями. Это катастрофически скажется на производительности и, к тому же, не решит проблему на 100%.

Изменить расположение сэмплов, то есть исказить обычную прямую решетку.

В идеале, второй способ подразумевает случайное расположение сэмплов внутри пикселя (на максимальном удалении друг от друга). Но такой вариант трудно реализуем: сама по себе

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

Фирма 3dfx предложила метод сглаживания, просто поворачивающий эту решетку на 20−30 градусов.

В результате линии, близкие к прямым, сглаживаются очень даже неплохо. К сожалению, проблему этот метод не снимает, так как линии, имеющие наклон около 30−45 градусов, точно также могут проскочить между двумя пикселями, не попав ни в один из них, следовательно, они будут сглаживаться очень плохо. Однако, по многим оценкам, на таких линиях алиасинг гораздо менее заметен, чем на линиях, близких к прямым. Поэтому, такая повернутая решетка, в большинстве случаев все-таки предпочтительнее, чем прямая.

Рассмотрим метод 3dfx. Он называется Rotated Grid Super Sampling (в дальнейшем RGSS). Основывается на технологии 3dfx T-Buffer, позволяющей рассчитать сразу четыре разных кадра, а потом их смешивать для получения широкого набора эффектов. Нас сейчас интересует только один из этих эффектов — полноэкранное сглаживание.

Ускоритель Voodoo5 — первый и единственный, поддерживающий технологию T-Buffer, а значит и RGSS. Карта снабжена двумя чипами VSA-100, каждый из которых может рассчитать и хранить один или два кадра. В результате, мы имеем два режима анти-алиасинга: 4x и 2x.

Анти-алиасинг 4х.

В отличие от обычного суперсэмплинга, RGSS рассчитывает не одно изображение в повышенном разрешении, а четыре одинаковых изображения в установленном на экране разрешении. На самом деле, эти четыре рассчитываемых изображения не совсем одинаковы. Поскольку результирующий пиксель по-прежнему состоит из четырех субпикселов, нужно определить их положение внутри пикселя. Как мы уже говорили, метод 3dfx предполагает, что все сэмплы внутри пикселя повернуты на 20−30 градусов:

Финальный пиксель формируется путем смешивания цветов соответствующих

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

Очевидно, что в данном случае честно сглаживаются по четырем сэмплам все пиксели экрана, а не только эффект алиасинга, как при использовании Accuview от NVIDIA. Из этого факта следуют естественные выводы: скорость падает не меньше, чем при использовании обычного суперсэмплинга (Ordered Grid Super Sampling — суперсэмплинг с прямой решеткой), но и удаленные текстуры тоже серьезно улучшаются, также как и при использовании OGSS.

Анти-алиасинг 2х.

Другой, более быстрый, но и менее качественный режим сглаживания. Это расчет только двух разных кадров и формирование финального пикселя по двум сэмплам. Очевидно, что в отличие от других рассмотренных методов, использующих для расчета пикселя два субпикселя, метод 3dfx сглаживает изображение не только по горизонтали, но и по вертикали. Хотя, совершенно не сглаживаются линии с наклоном около 60 градусов, этот режим, тем не менее, является одним из самых удачных, среди конкурентов в весовой категории 2х.

ATI Radeon 8500 (Smooth Vision)

В своем сверхновом ускорителе, способном на равных бороться с ускорителями NVIDIA GeForce3, ATI предложила новое решение полноэкранного сглаживания с фирменным названием Smooth Vision.

Это второй, после 3dfx метод, основанный на неупорядоченном расположении сэмплов внутри пикселя (так называемая искаженная решетка или jittered sample pattern). Но, в отличие от метода 3dfx, сэмплы не просто повернуты внутри пикселя. Каждый пиксель допускает восемь различных, заранее заданных расположения внутренних сэмпла:

Метод 3dfx сдвигает каждый пиксель одинаково в одном и том же направлении. В отличие от него, Smooth Vision сдвигает пиксели группами, причем каждая группа может быть сдвинута в любую сторону. В итоге, расположение сэмплов должно приближаться к идеалу, то есть полностью случайной решетке. А значит, метод должен одинаково хорошо справляться с линиями, проходящими под любыми углами.

SV оперирует с блоками из 16-ти сэмплов, на основе которых может рассчитываться различное количество результирующих пикселей (для режима 2х — 8 пикселей, для режима 4х — 4 пикселя). Каждый пиксель внутри этого блока имеет собственное, отличное от остальных пикселей, расположение внутренних субпикселов, наугад выбранное из восьми допустимых позиций.

Вот пример расположения сэмплов внутри пикселя, в режиме SV 4x:

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

Полноэкранное сглаживание SV имеет два основных режима работы: Quality и Performance. Они отличаются только тем, что первый честно рассчитывает заданное количество сэмплов (от 2х до 6х), а второй использует сэмплы соседних пикселей. Естественно, использование не своих субпикселей приводит к повышению скорости и некоторой смазанности изображения, о чем мы достаточно подробно говорили выше.

Искаженная решетка сэмплов позволяет делать некоторые интересные вещи, например, нечетное количество субпикселей на пиксель. Кроме того, как и у Voodoo 5, режим 2х дает действительно полное сглаживание, а не только по одной из координат, как у NVIDIA, даже более полное, чем у Voodoo5, поскольку сэмплы располагаются внутри пикселей намного более произвольно (случайно). Однако это не значит, что качество сглаживания будет на достаточном уровне.

Следует также отметить одну неприятную особенность драйверов Radeon 8500: на сегодняшний день, поддержка Smooth Vision реализована только в Direct3D, а в OpenGL используется самый обыкновенный суперсэмплинг, работающий гораздо медленнее и дающий худшее качество сглаживания. Будем надеяться, что эта досадная недоработка будет исправлена в самое ближайшее время.

Заключение

Как видим, на рынке представлено не так уж много различных методов полноэкранного сглаживания и их достоинства и недостатки вполне очевидны. Стандартный метод суперсэмплинга, очевидно, устарел и уже не может рассматриваться как действительно серьезная реализация анти-алиасинга, поскольку его применение приводит к очень существенному падению скорости, при этом давая совсем не рекордное качество сглаживания.

Среди остальных методов можно выделить два направления развития: увеличение качества обычного суперсэмплинга и повышение скорости.

3dfx и ATI пошли по первому направлению, увеличив качество суперсэмплинга, поворачивая или располагая случайно сэмплы внутри пикселя, при этом немного оптимизировав скорость. Причем, ATI пошла гораздо дальше 3dfx, введя почти случайное расположение субпикселов и значительно лучше оптимизировав скорость. Кроме того, 3dfx больше не существует и ее продукт, Voodoo5, едва ли можно назвать для кого-то серьезным конкурентом, хотя бы по причине фактического отсутствия такового на рынке.

Метод, предлагаемый ATI, вероятно, является самым качественным из того, что реализовано до сих пор. К сожалению, производительность Radeon 8500 не позволяет использовать его с максимальными настройками в достойном разрешении. На сегодняшний день, для современных ускорителей намного важнее такой показатель сглаживания, как качество/падение скорости. Чем выше будет этот показатель, тем выше в итоге будет и качество, с которым можно будет играть с достойной скоростью. ATI увеличила этот показатель, увеличив качество. Но математика подсказывает и другой способ: уменьшить падение скорости.

Именно по этому пути и пошла NVIDIA, сглаживание которой по качеству не лучше суперсэмплинга, но зато гораздо быстрее по скорости, давая, в итоге, самый быстрый анти-алиасинг среди всех конкурентов.

Трудно однозначно назвать победителя. Режим Accuview 4XS дает хорошее качество при небольшом падении скорости. Зато режим SV Quality 4x дает несколько более высокое качество сглаживания, хотя и заплатить за него придется дороже.

Список используемой литературы

1. http://www.nvworld.ru/docs/fsaa2.html

2. http://ru. wikipedia.org/wiki/Сглаживание#. D0. A1. D0. BC. _. D1.82. D0. B0. D0. BA. D0. B6. D0. B5

3. http://www.intuit.ru/department/graphics/rastrgraph/7/

4.

Введение

в цифровую обработку сигналов, А. Лукин, МГУ, 2002 г.