MIP-MAP Filtering в процессе выполнения приложения

При разработке игр, программисты отвечающие за графику, всегда пытаются достичь наибольшей реалистичности создаваемых ими объектов. Самый простой способ — применить технологию наложения текстуры на объект (texture mapping). Значительно усиливая реалистичность восприятия создаваемой сцены, этот способ, в то же время, вызывает целый ряд новых проблем. Наиболее заметной проблемой при наложении текстур, является проблема визуальных искажений изображения возникающая из-за цифровой дискретизации всех используемых в компьютере изображений (aliasing artifacts). Эти искажения становятся особенно заметными тогда, когда наблюдаемый полигон с наложенной текстурой находится на некотором расстоянии от точки наблюдения. Если вы начнете быстро передвигаться внутри своего виртуального мира, то данные искажения будут проявляться в виде мерцания и появления паразитных бликов на поверхности текстуры. Или, в случае если вы находитесь в неподвижном состоянии, вы заметите искажения в виде паразитных муаров и узоров на поверхности полигона, который вы только что "обтянули" текстурой. Это хорошо заметно на Рисунке 1, когда по мере увеличения дистанции от точки наблюдения, мы замечаем значительные искажения строгих геометрических фигур на текстуре.

Рисунок 1. Шахматная доска без применения MIP-mapping

Технология MIP-mapping (MIP текстурирование) сглаживает отрицательные визуальные проявления данной проблемы и делает искажения менее заметными. Акроним MIP происходит от латинского "multum in parvo", означающего "множество в малом" или "много вещей на одном пятачке". Для общего образования отметим, что по информации из OpenGL RedBook термин "mipmap" был предложен для использования Ланцем Вильямсом (Lance Williams) в 1983 году, когда на SIGGRAPH'83 он рассказал идею этой новой техники в своем докладе "Pyramidal Parametrics". Правда, Lance Williams использовал несколько инуюрасшифровку термина, а именно: "multim im parvo", так что не удивляйтесь, если встретите и такую транскрипцию. По другой версии исследователи из Нью-йоркского технологического института впервые применили данный термин в 1979 году, для того, что бы описать технологию преобразования и сжатия множества пикселей в одну малую, специальным образом сформированную текстуру или карту, известную как MIP-map.

Для того, что бы увидеть насколько улучшается визуальная чистота изображения, достаточно поглядеть на Рисунок 2, который показывает эффект от применения MIP-mapping c билинейной фильтрацией (bilinear filtering).

Рисунок 2. Шахматная доска с MIP-mapping and bilinear filtering

Для того, что бы понять, что же вызвало проблемы, показанные на
Рис.1, вы должны заглянуть внутрь процесса наложения текстуры на объекты и понять каким образом процесс дискретизации текстур влияет на конечное изображение, выводимое на экран монитора. Посмотрите на Рисунок 3а, на котором синусоида дискретизируется внешним сигналом со значительно большей частотой. Видно, что мы можем получить достаточно точную копию исходной синусоиды, если восстановить значения амплитуды каждого из сэмплов при частоте внешнего сигнала. Однако, если частота внешнего сигнала (частота дискретизации) будет равна удвоенной частоте синусоиды (Рис. 3b), то возможны моменты (при равенстве фаз, например), когда моменты дискретизации будут совпадать с моментами прохождения исходной синусоиды через нуль, в результате чего данный сэмпл будет неинформативен. Применение частоты дискретизации меньше удвоенной частоты исходного сигнала (Рис. 3с) приведет к тому, что сигнал, восстановленный из значений полученных сэмплов, будет синусоидой с частотой меньшей, чем у исходного сигнала. Исходя из изложенного, мы можем предположить, что частота дискретизации должна быть, по крайней мере, в два раза больше частоты дискретизируемого сигнала. Данное соотношение известно под названием предел Найквиста (В России, данное соотношение носит название теоремы Котельникова. Прим. переводчика).

Рисунок 3. Дискретизация синусоиды

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

Знакомство с рядом Фурье

Полное изложение вопросов теории Фурье, может запросто занять несколько отдельных книг, поэтому для тех из вас, читатели, кто не особо утруждался на лекциях по ТЭРЦ (теории электро-радио цепей) в институте, я могу предложить почитать книгу Брейсуэлла, ссылка на которую дана в конце статьи. Что же касается самой статьи, то в ней будет изложено очень сжатое введение в теорию преобразований Фурье, но этого должно быть достаточно для того, что бы понять из чего вытекает значение предела Найквиста (Котельникова).

Рисунок 4а. Графическое представление дискретизации Фурье

Рисунок 4а показывает вид функции h(t)=sinc²x и ее представление рядом Фурье H(f). Для удобства будем считать, что H(f) это ряд Фурье (или частотный ряд), а h(t) временной ряд. (Если вас интересует, почему я выбрал в качестве функции именно sinc²x, просто потому, что она имеет наиболее простое графическое представление в частотном ряду). Для того, что бы перейти от временного ряда к частотному в теории Фурье применяется следующее преобразование:

В этой формуле, представляющей собой преобразование Фурье, f определяет частоты гармоник (обычных синусоидальных сигналов) составляющих исходный сигнал h(t), а говорит нам о том, что степень является комплексным членом, т. е. имеет вещественные и мнимые части. Оператор Й часто используется для обозначения преобразования по Фурье, т.е. выше приведенную формулу мы можем записать как h(t) Й H(f). Рисунок 4b показывает последовательность импульсов и их предстваление рядом Фурье. Импульс, который мы обозначим d(t) это теоретический сигнал бесконечно малой длительности и бесконечно большой амплитуды приведенной к единице. Интересной особенностью последовательности импульсов с периодом T_s, является то, что ряд Фурье этой последовательности будет иметь вид другой последовательности импульсов, но с периодом 1/T_s .

Рисунок 4b

Рисунок 4с

Результат преобразования h(t) последовательности импульсов представленных функцией s(t) показан на Рисунке 4с. Во временном ряду преобразования напоминают перемножение h(t) и s(t), тогда как в частотном ряду (ряду Фурье) результатом является конволюция H(f) и S(f).

Конволюция двух любых функций f(x) и g(x) представляется формулой:

Формула 4

Если попытки подстановки в формулу 4 результатов функций h(t) и s(t) преобразованных по Фурье вызывают у вас головную боль и желание пропустить эту "мыльную" статью (стр.72 Ноябрьского выпуска Game Developer), то все же задержитесь на секунду — все не так сложно, как кажется. Конволюция единичного импульса в момент времени t=t₀ измененного по h(t) это ничто иное, как значение h(t) смещенное на позицию времени t=t₀.

Формула 5

Применим Формулу 5 для нахождения конволюции H(f) и S(f).

Как видим, эта формула показывает нам, что результат конволюции это функция H(f) с образами разнесенными на величину интервала 1/T_s, как раз то, что мы видим на Рис. 4с. Спектр функции sinc²x не является бесконечным, т. е. имеет вполне определенные ограничения частоте до f_max. Мы так же знаем, что частота это величина обратная периоду. Отсюда, единственное требование, которое мы должны удовлетворить, что бы избежать искажений, это не допустить перекрывающихся областей в частотном ряду, т. е. обеспечить соотношение f_s>2f_max, где f_s=1/T_s. Это то, откуда и взялся предел Найквиста (Котельникова). Как можно заметить из Рис. 4d, если частота дискретизации будет ниже 2f_max, то рядом лежащие спектральные области перехлестнутся, и частотные составляющие данных областей будут безвозвратно утеряны в результирующем сигнале. Однако, вместо того, что бы исчезнуть полностью, эти высокочастотные гармоники, появляются на низких частотах в виде паразитных гармоник, отзвуков на исходные гармоники (aliases). Вот, откуда появился термин — aliasing. Для того, что бы избежать этих отзвуков, необходимо либо сузить полосу, занимаемую сигналом, подлежащим дискретизации до величины меньшей 2f_s, либо установить частоту дискретизации в два раза выше максимально возможной частоты дискретизируемого сигнала 2f_max.

Рисунок 4d

Основы MIP-mapping (MIP текстурирования)

Давайте посмотрим, как MIP-mapping позволяет уменьшить искажения вызываемые дискретизацией изображения (aliasing artifacts) на примере изображения. Помните, наложение текстур на объекты в сцене применяется исключительно для придания большей реалистичности создаваемым объектам. Однако, все мелкие детали изображения в текстуре это всегда наиболее высокочастотные компоненты, и они же и являются источником aliasing problems. Так, как реально мы не можем изменить частоту дискретизации (1/DU и 1/DV в визуализирующей части нашего игрового движка), то мы вынуждены будем отфильтровать (filtering) наши текстуры таким образом, чтобы убрать высокочастотные составляющие нашего изображения.

^*Примечание переводчика: при использовании двумерных текстур в трехмерном пространстве, возникает необходимость использования двумерной координатной системы текстуры внутри существующей трехмерной координатной системы X, Y, Z. Для того, что бы разделить между собой эти координаты, разработчики ввели дополнительные обозначения двумерных координат U и V для текстур. Также был введен параметр W для того, чтобы расширить пространство Евклида (X, Y, Z) до неевклидова гомогенного (X, Y, Z, W). При эжтом, если W>0, то (X, Y, Z, W) совпадает с (X/W, Y/W, Z/W). Так что, если вам необходимо произвести манипуляции над текстурой уже размещенной в вашей 3D сцене, то вы должны будете использовать каординаты U, V.

Величины DU и DV, упоминаемые выше по тексту, это минимальные единичные приращения текстуры, которые мы можем использовать для вычислений. Обычно эти величины определяются размерностью пикселя, именно он является минимальной дискретизирующей величиной. Отсюда 1/DU и 1/DV будут величинами, определяющими частоту дискретизации изображения текстуры.

Рисунок 5. Пирамидальность MIP-map

Хотя и считается возможным отфильтровать каждый индивидуальный тексель непосредственно в процессе исполнения программы, но этот способ не применяется ввиду сложности его реализации. Более оптимальным считается вариант использования MIP текстур (MIP-map), которые состоят из серии заранее отфильтрованных и отмасштабированных текстур. Фильтрация текстур может быть произведена непосредственно в период начального запуска программы или произведена самим программистом еще в период разработки программы. Другой способ реализации MIP-mapping, это применение графических акселераторов, например, NVIDIA RIVA 128, которые произведут генерацию необходимых MIP-текстур для вашей сцены в момент, когда исходные текстуры загружаются в видео память. Рис. 5 иллюстрирует пирамидальную структуру MIP карты (текстуры), сформированную в результате MIP-mapping для исходной текстуры размерностью в 64х64 пикселя. Как можно видеть, уровень детализации (LOD) уменьшается по мере увеличения MIP уровня (MIP level). Как только текстура была преобразована в
MIP-map, все, что вам необходимо сделать в период выполнения программы для достижения базового per-polygon MIP-mapping — это выбрать корректный MIP уровень для конкретной текстуры и передать его для визуализации в акселератор или модуль программы отвечающей за визуализацию в случае software rendering.

Генерация MIP текстур

Существует несколько способов генерации MIP текстур. Один из них — просто подготовить их заранее, используя графические пакеты типа Adobe PhotoShop. Другой способ — генерация MIP текстур на "лету", т.е. в процессе выполнения программы. Заранее подготовленные MIP текстуры означают дополнительные 30% дискового пространства для текстур в базовой поставке инсталляции игры, но позволяют применять более гибкие методы управления их созданием и позволяют добавлять различные эффекты и дополнительные детали различным MIP уровням. Независимо от того, какой из способов реализации MIP-mapping вы выбрали, MIP текстуры потребуют дополнительные 30% RAM для своего размещения, что значительно увеличивает минимальные требования к количеству оперативной и/или видеопамяти на компьютере.

Давайте начнем с создания MIP карты для 8-битной текстуры.

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

Рассмотрим процесс генерации MIP текстур на "лету". Первый MIP
уровень представляет собой неизмененную исходную текстуру, скопированную в структуру MIP карты. Смотри Listing 1 (С целью экономии печатного пространства все кодовые листинги доступны для загрузки в виде одного архива: nov98.zip (584 Кб).

Создание остальных MIP уровней текстуры это шаг за шагом повторяющийся процесс. Каждый последующий (более высокий) уровень создается на базе предыдущего уровня, имеющего больший масштаб. Каждый созданный уровень располагается в памяти последовательно с предыдущим. Так же в структуре MIP карты хранится стартовый указатель (pointer) на нужный MIP уровень, так что игровой движок с легкостью может извлечь для использования уровень с соответствующим LOD.

Первым шагом в определении цвета нового пикселя будет вычисление усредненой цветности прямоугольника из четырех близлещащих пикселей на предыдущем MIP уровне. См. Listing 2. Так как, в нашем случае мы работаем с текстурой содержащей палитру цветов, то после того как мы определили значение нового пикселя, нам необходимо найти наиболее соответствующий ему цвет из палитры. Этот процесс показан в Listing 3. Процесс поиска нужного цвета из палитры прост, но может потребовать значительных временных затрат, так как нам необходимо обработать таким образом все пиксели в каждом из MIP уровней. К счастью, данная процедура требуется только один раз, на этапе инициализации MIP текстуры, значит, это не будет критичным. Однако, если вы пожелаете использовать другие эффекты в процессе рендеринга (визуализации), например билинейная и трилинейная фильтрация, то процесс поиска нужного цвета может стать очень медленным.

В этом случае, нам необходимо отказаться от применения текстур содержащих палитру в заголовке, и перейти к использованию 16 или 24-битных текстур. Ввиду того, что большинство применяемых графических карт поддерживают 16 битные текстуры, то мы рассмотрим в данном разделе именно 16 битную текстуру. Технология создания MIP текстуры для 16 битного изображения, очень близка к той, которую мы применяли для 8 бит, см. Listing 4. Так как 16 битные текстуры не содержат палитру, усредненные значения цветности для нового пикселя берутся непосредственно из предыдущего MIP уровня. Одна из проблем, которая возникает в результате неоднократно усреднения цветовых величин для каждого из LOD, это то, что каждая последующая текстура будет темнее предыдущей, находящейся на один MIP уровень ниже. Можно компенсировать это некоторым увеличением значений цветовых составляющих пикселя на каждом из новых MIP уровней. Хотя это компенсация обычно не столь необходима ввиду того, что потеря в интенсивности чаще всего не столь значительна, что бы она бросалась в глаза.

Наложение MIP текстур в процессе выполнения приложения

Рисунок 6 (ниже) показывает некоторые из проблем, с которыми вы можете столкнуться, выбирая корректный LOD (уровень детализации) в процессе выполнения программы. На рисунке, прямоугольная текстура, наложенная на треугольник в плоскости самой текстуры, преобразуется в четырехсторонний многоугольник, находящийся в плоскости экрана. Перспективная проекция текстуры вызывает соответствующие преобразования прямоугольных индивидуальных текселей в многоугольники различных размеров. В нашем случае, когда полигон развернут в плоскости экрана, определение корректного LOD, который необходимо применить на полигон, является первостепенной задачей, т.к. именно от него будет зависеть хорошее конечное качество изображения. Если выбранный уровень детализации (LOD) слишком велик (размерность текстуры велика), искажения дискретизации (aliasing) будут видны в "полной своей красе". Если LOD будет недостаточным, то конечное изображение будет слишком размытым. Например, уровень детализации, выбранный для текстуры использованной на Рис. 7 (ниже) слишком мал, поэтому мы можем наблюдать большие грубые тексели в увеличенном окне вынесенном влево. Существует множество различных методов для выбора корректного LOD, каждый из которых имеет свои плюсы и минусы. Существуют два наиболее известных метода, которые мы рассмотрим ниже. Первый, основан на выборе уровня детализации в зависимости от местоположения текстуры в плоскости экрана (Area based); второй, использует для выбора LOD проекции u и v векторов.

Рисунок 6. Искажение текстуры после проекции в плоскости экрана

Рисунок 7. Наложенная текстура имеет неправильный LOD

Следует обратить внимание еще на один момент, дело в том, что вам, возможно, потребуется различное количество текселей для того, что бы прорисовать разные пиксели на экране. Как результат, вам необходимо будет просчитать LOD для каждого из пикселей. Эти вычисления могут быть очень медленными, и именно поэтому большинство программных методов визуализации (software renderers) и некоторые из устаревших видеоакселераторов, производят вычисления LOD основываясь на технологии per-polygon и/или per-triangle. Однако, несомненным плюсом per-polygon технологии в MIP-mapping, особенно при программной визуализации, является то, что для полигонов расположенных на удалении (более мелких) вы применяете более мелкие версии текстур из MIP карты, что значительно снижает требования к количеству кэш-памяти процессора в период интенсивных операций с текстурами. В то же время, по-пиксельный вариант выбора LOD позволяет вам реализовать целый ряд дополнительных преобразований в процессе MIP-mapping, включая такие как: точечная дискретизация; билинейная фильтрация на одном уровне детализации; трилинейная фильтрация между двумя ближайшими LOD.

Per-polygon MIP-mapping

Выбор корректного LOD в per-polygon MIP-mapping считается наиболее выгодным с точки зрения количества вычислений необходимых для его реализации, так как выборка производится однократно для целого полигона. Здесь, однако, есть два недостатка:

Первый — два соприкасающихся полигона могут быть отвизуализированы с применением разных уровней детализации. Визуально это проявляется в виде потери неразрывности восприятия нанесенной на объект текстуры (такие искажения носят название MIP banding). Рис.8 демонстрирует проявление незначительного MIP banding явившегося результатом per-triangle MIP-mapping.

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

Рисунок 8. Дорога рендеренная с применением per-polygon MIP-mapping

Выбор LOD в зависимости от местоположения текстуры на экране (Area-based LOD selection)

Area based LOD selection реализует по-полигонную технику MIP-mapping. Используя этот метод, вы регулируете LOD путем изменения степени сжатия, которая будет применена к текстуре нужной текстуре. Для того, чтобы определить необходимую степень сжатия, вам нужно определить местоположение полигона в плоскости экрана, а так же определить ту часть текстуры (в проекции текстуры) которая будет покрывать выбранный полигон. Используя пример из Listing 5, вы можете определить соотношение текселей к пикселю и далее выбрать соответствующий уровень детализации для применения. (С целью экономии печатного пространства все кодовые листинги доступны для загрузки в виде одного архива: nov98.zip (584 Кб).

U и V размеры более высокого MIP уровня в MIP текстуре равны половине предыдущего MIP уровня, таким образом площадь каждого из уровней, представляющего соответствующий LOD, будет равна одной четвертой от
площади предыдущего. Соответственно, при выборе необходимого LOD мы будем перемещаться на одну ступень вверх по пирамиде MIP текстуры каждый раз, когда соотношение количества текселей на пиксель (texel-to-pixel ratio) изменится четырехкратно. Например, если texel-to-pixel ratio равно 3:1, то мы выбираем MIP уровень 0; если texel-to-pixel ratio равно 7:1, то выбираем уровень 1 и т.д. Как только произошла смена LOD мы можем передать указатель на соответствующий MIP уровень нашему модулю отвечающему за визуализацию, который в свою очередь и произведет визуализацию текстуры с указанным LOD. Здесь необходимо отметить, что каким бы способом мы не проводили MIP-mapping, одна проблема нас будет преследовать всегда. Эта проблема связана с любым преобразованием использующим проекции полигонов с наложенными текстурами и выражается в проявлении паразитного aliasing в те моменты, когда используемый полигон достаточно тонок. Корни этой проблемы прячутся в анизотопности алгоритмов компрессии текстур (анизотропность заключатся в том, что степени сжатия вдоль координатных осей U и V- всегда различна!)

Per-pixel MIP-mapping

По-пиксельное MIP текстурирование позволяет реализовать более утонченное управление уровнем применяемой детализации, чем по-полигонное, оно так же допускает применение дополнительных преобразований над текстурами, хотя все это за дополнительную "плату". Все по-пиксельные методы требуют хранения полной MIP текстуры в RAM, а дополнение внутренних циклов в процедурах программы отвечающих за наложение текстур, может привести к значительному падению производительности игрового движка. К счастью, большинство из сущестующих в настоящее время 3D акселераторов аппаратно поддерживают MIP-mapping c билинейной фильтрацией (а некоторые чипы без ущерба могут осуществлять и трилинейную), поэтому мы рассмотрим, что же собственно необходимо для того, что бы реализовать по-пиксельное MIP текстурирование. Хотя и здесь, при выборе уровня детализации, мы можем применить Area based метод, мы все же пойдем по более аккуратному и сложному пути и просчитаем LOD для каждого из пикселей, в отличие от однократного просчитывания LOD на весь полигон.

Выбор LOD на основе краевого сжатия (Edge compression-based LOD selection)

В 1983 году, Поль Хекберт, перед тем как обнаружить, что метод основанный на определении сжатия краев пикселя при обратном проецировании на текстуру, является наиболее эффективной техникой вычисления LOD, он вероятно уже исследовал больше методов вычисления LOD, чем сам мог запомнить. Рис. 9 показывает единичный прямоугольный пиксель в плоскости экрана и соответствующий ему многоугольник в плоскости текстуры. Что бы избежать искажений типа aliasing , мы попробуем определить необходимый LOD основываясь на максимальном сжатии которую претерпевают края пикселя в плоскости текстуры. Она соответствует максимальной длине стороны в плоскости текстуры, и определяется Выражением 7.

Рисунок 9. Обратное проецирование пикселя на плоскость текстуры

Выражение 7

Значения u_x, u_y, v_x,v_y определяются четырьмя частными производными. См. Рис.9. Т.к. мы уже знаем, как вычислять значения u и v для любого пикселя на экране, мы можем применить наши знания для вычисления частных производных. Зная текущие градиенты u/z, v/z и 1/z в системе × и y, а так же зная начальные значения u/z, v/z, 1/z в плоскости экрана, мы можем определить значения u и v по формулам 8 и 9. Нотацию, принятую в формулах 8 — 19 вы можете определить из серии статей Криса Хекера (Chris Hecker) по проекционному текстурированию, которые могут быть найдены на его WEB сайте. (См. раздел "Особые благодарности" в конце статьи).

Формула 8

Формула 9

Используя полученные выше результаты, мы можем определить частные производные в соответствии с формулами 10 — 13.

Формула 10

Формула 11

Формула 12

Формула 13

Где, значения a, b, c, d, e, f определяются формулами 14 — 19.

Формула 14

Формула 15

Формула 16

Формула 17

Формула 18

Формула 19

Очень важно заметить, что числители в частных производных u_x и v_x — функции y, а числители в частных производных u_y и v_y — функции x. Значения a, b, c, d, e, f вычисляются для всего полигона однократно, точно так же, как и в случае с обычными градиентами текстур. См. Listing 6. Ну и, наконец, формула для нахождения максимального краевого сжатия дана ниже:

Формула 20

На первый взгляд кажется, что нам необходимо вычислять корень для каждого пикселя. Однако, если внимательнее рассмотреть формулу, то окажется, что значение y_l — нам необходимо вычислять только раз на каждое значение × текущего полигона.
Более того, значение x_l — достаточно вычислить всего раз для одного прохода луча ЭЛТ монитора (scan line). Listing 7 наглядно показывает как мы производим вычисление значения y_l для диапазона × полигона в период нормальной подготовки к нанесению текстуры. Вы также заметите, что x_l — вычисляется только раз на проход. И еще, нам не нужно беспокоиться о вычислении значения знаменателя, так как он уже будет вычислен ранее, в процессе стартовой выборки текстуры. Таким образом, вся дополнительная нагрузка к внутренним циклам процедур программы, будет представлять собой две операции умножения и одну операцию сравнения. Теперь, после того, как мы узнали каким образом вычислить краевое сжатие, давайте попробуем произвести выбор необходимого уровня детализации при текстурировании, используя точечную выборку, билинейную и трилинейную фильтрации.

Метод точечной выборки (Point-sampled per-pixel MIP-mapping)

Точечная выборка — самый простой способ реализации по-пиксельного MIP текстурирования и если вы заглянете в Listing 8 вы заметите, что нет значительной разницы между циклами простого наложения текстур и циклами в которых реализуется точечная выборка (point sampling). Как только мы нашли значение краевого сжатия для текущего пикселя, мы можем определить корректный уровень детализации текстуры для визуализации данного пикселя. Предварительные значения краевого сжатия, полученные нами при использовании формул приведенных выше, могут варьироваться в диапазоне значений от 0 до 1. Поэтому нам надо привести эти значения к размерности используемой текстуры, что бы получить значимую высоту в пирамиде примененной MIP текстуры. Как только мы получили значение этой высоты, мы сможем выбрать корректный LOD перемещаясь на уровень выше каждый раз, когда значение высоты будет превышать определенную степень двойки от 1 (например: высота 1 будет означать применение уровня детализации 0; 2 или 3 соответсвует уровню 1; 4 — уровень 2; 8 — уровень 3; 16 — уровень 4 и т.д.). Далее мы используем таблицу соответствий LOD, для получения значения указателя (pointer) внутри нашей MIP текстуры для извлечения соответсвующего текселя. На Рис. 10 показан тот же самый объект, что и на Рис. 8, только отвизуализированный с применением точечной выборки (point-sampled MIP-mapping). Как можно заметить, при использовании данного метода, по прежнему присутствует проблема MIP banding в тех точках, где происходит смена LOD. Это объясняется тем, что соседние пиксели могут иметь различные уровни детализации, и ощущение неразрывности объекта теряется.

Рисунок 10. Дорога отвизуализированная с применением технологии точечной выборки

По-пиксельное MIP текстурирование с билинейной фильтрацией (Bilinear filtered per-pixel MIP-mapping)

Билинейная фильтрация призвана обеспечить дальнейшее уменьшение искажений типа aliasing на экране, путем усреднения значений четырех соприкасающихся пикселей текстуры, U и V координаты которых наиболее соответствуют реальному пикселю на экране. Рассмотрев Рис.11 и Listing 9, мы можем заметить, что билинейная интерполяция (аппроксимация) реализуется тремя линейными интерполяциями. Вычисление корректного LOD и извлечение необходимого указателя (pointer) для нашей текстуры производится аналогично тому, что мы делали в случае точечной выборки. Однако, мы извлекаем значения для четырех пикселей текстуры и применяем билинейную интерполяцию для каждого цветового компонента, с целью получения усредненного значения цветности нового пикселя. Рис. 12 показывает, то, как выглядит наша дорога после применения билинейной фильтрации. Хотя заметен значительный прогресс в визуальном представлении по сравнению с Рис. 10, мы все же можем заметить присутствие MIP banding.

Рисунок 11. Механизм интерполяций при билинейной фильтрации

Рисунок 12. Билинейная фильтрация

По-пиксельное MIP текстурирование с трилинейной фильтрацией (Trilinear filtered per-pixel MIP-mapping)

Способоность аппаратно поддерживать трилинейную фильтрацию при MIP-mapping, является неотемлемой чертой акслелераторов последнего поколения. Трилинейная фильтрация позволяет исключить проявления MIP banding путем сглаживания переходов между различными уровнями детализации. В Listing 10, вы снова можете заметить, что вычисление корректного LOD производится путем, полностью аналогичным примененному при точечной выборке с той лишь разницей, что мы извлекаем указатели (pointers) для двух LOD: текущего и следущего выше по пирамиде, с меньшей детализацией. Трилинейная фильтрация выполняется путем восьми последовательных линейных интреполяций (апроксимаций). Мы выполняем билинейные интерполяции отдельно для каждого из двух выбранных LOD, а затем производим окончательные интерполяции между самими LOD. Как можно видеть на Рис. 13, трилинейная фильтрация обеспечивает очень плавный переход между уровнями детализации (хотя это выливается в некоторую размытость линий). К сожалению, "плата" за подобное качество — велика. Непосредственная реализация алгоритмов трилинейной фильтрации требует восьмикратного обращения к текстуре на каждый просчитываемый пиксель, что вызвает производство огромного количества вычислений. Несмотря на то, что мы можем снизить количество обращений к текстуре, путем сохранения значений текселя в промежутках между итерациями цикла, производство самих интерполяций по прежнему будет выполнятся в каждом цикле, отсюда следует, что достижение приемлемых frame rates при использовании трилинейной фильтрации в неакселерированном режиме игрового движка — является очень и очень не простой задачей.

Рисунок 13. Трилинейная фильтрация

Заключение

В данной статье мы осветили довольно большой диапазон вопросов,
связанных с MIP текстурированием, и хотя применение трилинейной фильтрации делает конечное изображение гораздо более привлекательным, по сравнению с методами простого наложения текстур, все же идеального результата мы не получаем. Самой значительной проблемой в наших преобразованиях, является проблема анизотропности алгоритмов сжатия текстур (См. упоминание об этом выше в статье). Мы выбираем необходимый/корректный LOD исходя из максимальной степени краевого сжатия пикселя по одной из его сторон, но что будет если существует заметная разница в компрессии по различным координатным осям. В этом случае, выбранный уровень детализации будет недостаточен для стороны текстуры с меньшей компрессией и наша сцена будет казаться размытой. Посмотрите на Рис. 14, это скриншот из CHAOSVR demo, который был получен с использованием акселератора на базе 3dfx Voodoo², мы отчетливо видим, что размытие происходит только в направлении одной из осей координат. Данная проблема будет присутствовать при использовании любого 3D акслелератора, который использует алгоритмы вычисления LOD аналогичные разработанным здесь, а не только на Voodoo² используемом мной. Определенно, что следующим шагом на пути улучшения качества визуализации будет разработка и принятие алгоритмов анизотропной фильтрации. Уверен, что данная технология не заставит себя долго ждать, и появится на акселераторах следующего поколения.

Рисунок 14. Скриншот из CHAOSVR с использованием трилинейной фильтрации на базе Voodoo²

Особые благодарности

Огромное спасибо Крису Хекеру (Chris Hecker), который любезно разрешил мне вставить мои наработки в области MIP-mapping в алгоритмы наложения текстур, разработанные им. Это сэкномило массу времени. Посмотрите материалы на его домашней страничке http://www.d6.com/users/checker для получения дополнительной информации по технике наложения текстур и более ранним статьям из Game Developer.

Хочу выразить признательность Полу Хекберту (Paul Heckbert), за направление в мой адрес материалов публикаций, и наверное единственных , в которых обсуждается MIP текстурирование.

Наконец, я хочу поблагодарить Питера Лофенберга (Peter Laufenberg) за разрешение использовать скриншот из CHAOSVR demo компнании Virtually Unlimited.

Для дальнейшего изучения:

• Bracewell, R. N., The Fourier Transform and its applications, McGraw-Hill Book Co., New York, 1986.
• Williams, L., "Pyramidal Parametrics", Computer Graphics, vol. 17, no. 3, (Proc. SIGGRAPH 1983).
• Heckbert, P., "Texture Mapping Polygons in Perspective", NYIT Tech. Memo No. 13, 1983