Мипмэппинг
6. Мипмэппинг
Если полигон относительно сильно удален или повернут, так, что соседним пикселам на экране соотвествуют сильно разнесенные точки текстуры, то возникают всякие неприятные артефакты - можно считать, что потому, что при текстурировании мы выбираем лишь какую-то одну точку текстуры, а реально в экранный пиксел будет проецироваться несколько текселов (точек текстуры). Вообще идеальным методом было бы следующее: провести до пересечения с гранью 3D-пирамиду с вершиной в камере и основанием-пикселом, выбрать все точки текстуры, попадающие в наш пиксел, и усреднить значения их цветов. Вот только вычислительные затраты на одну точку в этом случае окажутся просто фантастическими.
Поэтому для удаления артефактов используется значительно более простая вещь, а именно мипмэппинг. Идея, как обычно, проста. Для каждой текстуры заранее создается несколько ее копий уменьшенного размера (1/2, 1/4, и так далее), а далее при текстурировании используется либо сама текстура, либо подходящая уменьшенная копия. Памяти при этом расходуется на 25-33% больше, чем без мипмэппинга, но зато, вроде бы, увеличивается качество изображения.
Как создать уменьшенную в два раза копию текстуры? Здесь мы опишем три метода, два из них очевидны, третий позаимствован у Crystal Space. Методы расположены в порядке уменьшения скорости и увеличения качества уменьшенной текстуры.
Метод 1. Выкинуть все пикселы текстуры с нечетными координатами. Самый простой, самый быстрый, но дает не очень хорошо выглядящие результаты.
Метод 2. Оставить точки с четными координатами, в каждой точке усреднить значения цвета в этой точке и ее трех соседях (справа, снизу и справа-снизу).
Метод 3. Оставить точки с четными координатами, использовав в каждой точке фильтр, заданный вот такой матрицей:
[ 1 2 1 ] 1/16 * [ 2 4 2 ] [ 1 2 1 ]
В виде формул для каждой из компонент цвета точки уменьшенной в два раза копии текстуры эти методы запишутся, соответственно, так:
mip1[x][y] = tex[2*x][2*y]; // метод 1 mip2[x][y] = ( // метод 2 tex[2*x ][2*y ] + tex[2*x+1][2*y ] + tex[2*x ][2*y+1] + tex[2*x+1][2*y+1]) / 4; mip3[x][y] = ( // метод 3 1 * tex[2*x-1][2*y-1] + 2 * tex[2*x ][2*y-1] + 1 * tex[2*x+1][2*y-1] + 2 * tex[2*x-1][2*y ] + 4 * tex[2*x ][2*y ] + 2 * tex[2*x+1][2*y ] + 1 * tex[2*x-1][2*y+1] + 2 * tex[2*x ][2*y+1] + 1 * tex[2*x+1][2*y+1]) / 16;
Последовательно применяя любой из описанных методов, мы можем построить набор уменьшенных текстур. Остается выяснить, какую именно из них надо выбрать при текстурировании. Здесь опять будет описано два достаточно простых метода; а вообще, конечно, их можно придумать значительно больше.
Метод 1: полигональный мипмэппинг. В этом случае мы считаем площадь полигона на экране в пикселах и его же площадь в текстуре в текселах (последнюю обычно можно посчитать заранее), определяем по ним примерное количество пикселов, соотвествующих одному пикселу и выбираем нужный уровень уменьшения текстуры по следующей формуле:
miplevel = floor(log2(screenArea / textureArea) / 2);
здесь
- screenArea - площадь грани на экране (в пикселах)
- textureArea - площадь грани в текстуре (в текселах)
- log2() - функция двоичного логарифма (для Watcom C стандартная)
- miplevel - уровень уменьшения; выбираемая текстура должна быть сжата по обеим осям в (2^miplevel) раз
Поскольку бесконечное количество уменьшенных копий текстуры никто хранить не будет, да и увеличенные текстуры тоже обычно не хранят, а miplevel может получится любым действительным числом, надо, конечно, поставить заглушку:
miplevel = floor(log2(screenArea / textureArea) / 2); if (miplevel < 0) miplevel = 0; if (miplevel > MAXMIPLEVEL) miplevel = MAXMIPLEVEL;
screenArea и textureArea проще всего, по-моему, посчитать по формуле Герона для площади треугольника:
// a, b, c - стороны треугольника; p - периметр a = sqrt((v2.sx-v1.sx)*(v2.sx-v1.sx) + (v2.sy-v1.sy)*(v2.sy-v1.sy)); b = sqrt((v3.sx-v1.sx)*(v3.sx-v1.sx) + (v3.sy-v1.sy)*(v3.sy-v1.sy)); c = sqrt((v3.sx-v2.sx)*(v3.sx-v2.sx) + (v3.sy-v2.sy)*(v3.sy-v2.sy)); p = (a + b + c); screenArea = sqrt(p * (p-a) * (p-b) * (p-c)); a = sqrt((v2.u-v1.u)*(v2.u-v1.u) + (v2.v-v1.v)*(v2.v-v1.v)); b = sqrt((v3.u-v1.u)*(v3.u-v1.u) + (v3.v-v1.v)*(v3.v-v1.v)); c = sqrt((v3.u-v2.u)*(v3.u-v2.u) + (v3.v-v2.v)*(v3.v-v2.v)); p = (a + b + c); textureArea = sqrt(p * (p-a) * (p-b) * (p-c));
Этот метод практически не требует вычислительных затрат, так как все операции проделываются один раз на грань. С другой стороны, здесь использутся один и тот же уровень уменьшения (он же уровень детализации, LOD, level of detail) для всего полигона, а разным пикселам может соответствовать разное количество текселов. Есть и более неприятное следствие - уровни уменьшения для двух соседних полигонов меняются скачком, а это не очень хорошо выглядит.
Метод 2: попиксельный мипмэппинг. В этом случае нужный уровень уменьшения считается для каждого пиксела и выбирается на основе максимального шага в текстуре из соответствующих переходу к соседнему пикселу:
textureStep = max( sqrt(dudx * dudx + dvdx * dvdx), sqrt(dudy * dudy + dvdy * dvdy)); miplevel = floor(log2(textureStep));
Подобную операцию для каждого пиксела проводить, конечно, накладно. Но при аффинном текстурировании dudx, dvdx, dudy и dvdy постоянны для всех пикселов, так что попиксельный мэппинг становится полигонным, только с другой методикой расчета уровня уменьшения. Для перспективно-корректного же текстурирования dudx, dvdx, dudy и dvdy постоянны для всех пикселов одного кусочка (span'а), так что уровень уменьшения считается раз в несколько пикселов.
Впрочем, даже раз в несколько пикселов подобное (два корня и один логарифм) считать будет достаточно медленно. Поэтому займемся небольшой оптимизацией: во-первых, для скорости можно сделать упрощение и считать, что
textureStep = sqrt(dudx * dudx + dvdx * dvdx);
Далее, заметим, что log2(sqrt(x)) = log2(x) / 2, откуда
miplevel = floor(log2(dudx * dudx + dvdx * dvdx) / 2);
Осталась, практически, одна трудоемкая операция - взятие логарифма. Но и ее можно убрать. Дело в том, что числа с плавающей запятой (float'ы) как раз и хранятся в логарифмической форме, и floor(log2(x)) можно посчитать вот так:
float x; int floor_log2_x; x = 123456; floor_log2_x = ((*((int*)&x)) - (127 << 23)) >> 23; // чистый C floor_log2_x = (((int&)x) - (127 << 23)) >> 23; // C++
Соответственно, floor(log2(sqrt(x))) = floor(log2(x) / 2) считаем как
miplevel = ((*((int*)&x)) - (127 << 23)) >> 24; // чистый C miplevel = (((int&)x) - (127 << 23)) >> 24; // C++
Естественно, что этот трюк можно применить и в случае полигонного мипмэпинга для полного устранения всяческих медленых операций типа sqrt(), log2(). Вот, в общем-то, и все.