К разделу 'Компьютерная Графика' сайта AlgoList.







ТЕКСТУРИРОВАНИЕ
4.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(). Вот, в общем-то, и все.



 в самое начало


demo.design
3D programming FAQ