Мипмэппинг

Если полигон относительно сильно удален или повернут, так, что соседним пикселам на экране соотвествуют сильно разнесенные точки текстуры, то возникают всякие неприятные артефакты - можно считать, что потому, что при текстурировании мы выбираем лишь какую-то одну точку текстуры, а реально в экранный пиксел будет проецироваться несколько текселов (точек текстуры).Вообще идеальным методом было бы следующее: провести до пересечения с гранью 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(). Вот, в общем-то, и все.