ОПТИМИЗАЦИЯ
6.4. Тайловые текстуры
В пункте 6.1.2. кратко описана схема работы кэш-памяти для процессоров Intel
Pentium. Из этой схемы, в частности, видно, что при непоследовательном
чтении из памяти будут периодически случаться кэш-промахи, что не очень
хорошо влияет на скорость. Хрестоматийный пример - это поворачивающаяся
картинка; при угле поворота, равном 0, чтение из памяти последовательно и
ситуация с кэшированием идеальна; если мы читаем байт и получаем кэш-промах,
то следующий за ним 31 байт будет прочитан уже из L1 cache, по полтакта на
чтение. А при достаточно больших углах поворота, например, 90 градусов,
каждый следующий байт находится на достаточном расстоянии от предыдущего,
и получаем кэш-промах практически на каждом пикселе, что *очень* медленно.
Но эта же ситуация постоянно случается и при текстурировании, грани ведь у
нас ориентированы произвольным образом, камера - тоже. Тайловые текстуры как
раз и призваны бороться с кэш-промахами.
Идея такова. Обычно текстура хранится в памяти построчно, именно из-за этого
при движении вдоль строки все нормально, а при движении поперек строк будут
постоянные кэш-промахи (кэшируется ведь небольшой горизонтальный кусочек).
Разобьем ее на маленькие кусочки - тайлы, и будем хранить такими кусочками.
Вот пример для текстуры размера 256x256 и тайла размера 8x8:
Текстура в пикселах:
0, 1, 2, 3, ..., 255
256, 257, 258, 259, ..., 511
512, 512, 513, 514, ..., 767
...
Текстура в тайлах:
0, 1, 2, 3, ..., 31 (первые восемь строк пикселов)
32, 33, 34, 35, ..., 63 (вторые восемь строк пикселов)
64, 65, 67, 68, ..., 95
...
Тайл 0 в пикселах: Тайл 1 в пикселах:
0, 1, ..., 7 8, 9, ..., 15
256, 257, ..., 263 264, 265, ..., 271
512, 513, ..., 519 520, 521, ..., 527
... ...
1792, 1793, ..., 1799 1800, 1801, ..., 1807
В этом случае все близкие к текущему текселы почти наверняка находятся в
текущем тайле, и количество кэш-промахов хоть как-то, да уменьшается. То
есть, тайлы как бы позволяют двигаться в текстуре и по горизонтали, и по
вертикали. Зато изменяется код расчета смещения нужного пиксела в текстуре.
Посмотрим, что получится для случая на иллюстрации. Пусть координаты в
текстуре (то есть, их целые части) равны u, v; тогда номер нужного тайла
равен (v / 8) * 32 + (u / 8), а координаты в тайле равны (u % 8), (v % 8)
соответственно. Тут помогает то, что 8 - степень двойки, получается, что
номер и координаты в тайле можно посчитать и проще, а по ним находим и
смещение в текстуре:
tile_number = ((v >> 3) << 5) + (u >> 3);
tile_u = u & 0x07;
tile_v = v & 0x07;
texture_offset = (tile_number << 6) + (tile_v << 3) + tile_u;
Напишем эти формулы и для общего случая, то есть для текстуры размером
(2^TEXBITS)x(2^TEXBITS) и тайла размером (2^TILEBITS)x(2^TILEBITS):
TILEMASK = ((1 << TILEBITS) - 1);
tile_number = ((v >> TILEBITS) << (TEXBITS - TILEBITS)) +
(u >> TILEBITS);
tile_u = u & TILEMASK;
tile_v = v & TILEMASK;
texture_offset = (tile_number << (2*TILEBITS)) +
(tile_v << TILEBITS) + tile_u;
Делать такое преобразование для каждого пиксела текстуры - занятие довольно
небыстрое. Поэтому начинаем заниматься оптимизацией. Выделяем части смещения,
зависящие от целых частей u, v соответственно:
tile_u_part = ((u >> TILEBITS) << (2*TILEBITS)) +
(u & TILEMASK);
tile_v_part = ((v >> TILEBITS) << (TEXBITS + TILEBITS) +
((v & TILEMASK) << TILEBITS);
texture_offset = tile_u_part + tile_v_part;
Отсюда видно, что биты целой части u, v разделяются на две группы (нижние
TILEBITS и все остальные) и эти две группы как-то раскидываются, сдвигаются.
Посмотрим, как именно это происходит для конкретного случая, где u, v - 8:16
fixedpoint, TILEBITS = 3, TEXBITS = 8:
u 00000000 UUUUUuuu ffffffff ffffffff
v 00000000 VVVVVvvv ffffffff ffffffff
tile_u_part 00000UUU UU000uuu ffffffff ffffffff
tile_v_part VVVVV000 00vvv000 ffffffff ffffffff
Идея быстрого тайлового текстурирования заключается как раз в интерполяции
непосредственно tile_u_part и tile_v_part, а не u, v; мы заранее переставляем
биты u, v, du, dv нужным образом и интерполируем уже готовые к использованию
с тайловыми текстурами величины tile_u_part, tile_v_part. Но для того, чтобы
сложение давало правильный результат, "дырки" между кусками целой части и
дробной частью u, v в tile_u_part, tile_v_part надо перед каждым сложением
заполнять единицами; иначе, скажем, целая единица, получившаяся при сложении
v и dv уйдет в нижний бит целой части tile_v_part и вместо перехода на пиксел
вниз вызовет переход на пиксел вправо. Поэтому все должно выглядеть так:
u 00000000 UUUUUuuu ffffffff ffffffff
v 00000000 VVVVVvvv ffffffff ffffffff
tile_u_part 00000UUU UU111uuu ffffffff ffffffff
tile_v_part VVVVV111 11vvv111 ffffffff ffffffff
Теперь переносы при сложении будут обрабатываться правильно, при переносе все
эти единички обнуляются, а переносимый бит добавляется туда, куда надо. Зато
теперь не будет работать сложение, не вызывающее переноса - в этом случае
единички останутся на месте и испортят все смещение. Получается, что перед
сложением нужно выставлять нужные биты в единичку, а после сложения их же и
очищать. Соответствующий цикл будет выглядеть так:
// ...
u = make_tile_u(u);
v = make_tile_v(v);
du = make_tile_u(du);
dv = make_tile_v(dv);
for (current_sx = x_start; current_sx <= x_end; current_sx++) {
putpixel(current_sx, current_sy, texture[unfix(u) + unfix(v)];
u |= TILE_U_MASK;
v |= TILE_V_MASK;
u += du;
v += dv;
u &= (~TILE_U_MASK);
v &= (~TILE_U_MASK);
}
// ...
Здесь make_tile_u(), make_tile_v() осуществляет перевод u, v в "тайловую"
форму; unfix() просто сдвигает u, v на собственную дробную часть, оставляя
лишь целую, TILE_U_MASK, TILE_V_MASK заполняют нужные биты числа единичками.
В нашем примере видно, что
TILE_U_MASK = 0x380000; // 00000000 00111000 00000000 00000000
TILE_V_MASK = 0x7C3000; // 00000111 11000111 00000000 00000000
По сравнению с обычным текстурированием добавилось более четырех инструкций.
Много. Смотрим дальше. С той же самой целью - заставить биты "перепрыгивать
дырки" при сложении - можно не заполнять дырки единичками в u, v для каждой
точки, а сделать это один раз для du, dv. Кроме того, unfix() можно делать
один раз, а не два, заменив (unfix(u) + unfix(v)) на unfix(u + v). Но здесь
надо проследить за тем, чтобы дробные части u, v при сложении не вызвали бы
переноса и не испортили смещение на единичку. Достигается это использованием
fixedpoint 8:15 и вставкой одного запасного бита между целой и дробной частью
u, v. Т.о., битовые раскладки для нашего примера теперь выглядят вот так:
tile_u_part 00000UUU UU000uuu 0fffffff ffffffff
tile_v_part VVVVV000 00vvv000 0fffffff ffffffff
tile_du 00000UUU UU111uuu 1fffffff ffffffff
tile_dv VVVVV111 11vvv111 1fffffff ffffffff
TILE_U_MASK 00000000 00111000 10000000 00000000
TILE_V_MASK 00000111 11000111 10000000 00000000
А окончательная версия цикла выглядит вот так:
// ...
u = make_tile_u(u);
v = make_tile_v(v);
du = make_tile_u(du) | TILE_U_MASK;
dv = make_tile_v(dv) | TILE_V_MASK;
for (current_sx = x_start; current_sx <= x_end; current_sx++) {
putpixel(current_sx, current_sy, texture[unfix(u + v)];
u += du;
v += dv;
u &= (~TILE_U_MASK);
v &= (~TILE_V_MASK);
}
// ...
В переводе на ассемблер, заимствованном из все того же fatmap2.txt, все это
выглядит вот так:
mov eax,tile_u_part
mov ebx,tile_v_part
mov ecx,length
mov esi,texture
mov edi,outputbuffer
lea edi,[edi+ecx-1]
xor ecx,-1
lea ebp,[eax+ebx]
inc ecx
inner:
add eax,tile_du
add ebx,tile_dv
shr ebp,16
and eax,11111111110001110111111111111111b ; (~TILE_U_MASK)
and ebx,11111000001110000111111111111111b ; (~TILE_V_MASK)
inc ecx
mov dl,[esi+ebp]
lea ebp,[eax+ebx]
mov [edi+ecx],dl
jnz inner
Осталось упомянуть про то, что тайлы можно расположить не по горизонтали,
а по вертикали:
Текстура в тайлах:
0, 32, 64, ...
1, 33, 65, ...
2, 34, 66, ...
...
Тогда преобразование для целых частей u, v выглядит следующим образом:
tile_number = ((u >> TILEBITS) << (TEXBITS - TILEBITS)) +
(v >> TILEBITS);
tile_u = u & TILEMASK;
tile_v = v & TILEMASK;
texture_offset = (tile_number << (2*TILEBITS)) +
(tile_v << TILEBITS) + tile_u;
Выделяя u, v, получаем:
tile_u_part = ((u >> TILEBITS) << (TEXBITS + TILEBITS) +
(u & TILEMASK);
tile_v_part = ((v >> TILEBITS) << TILEBITS) +
((v & TILEMASK) << TILEBITS);
то есть
tile_u_part = ((u >> TILEBITS) << (TEXBITS + TILEBITS) +
(u & TILEMASK);
tile_v_part = v << TILEBITS;
Все это делается для единственной цели - скорости. В таком виде перевод u, v
в "тайловые координаты" делается немного проще и быстрее; внутрениий цикл же
остается таким же (ну, константы (~TILE_U_MASK) и (~TILE_V_MASK), конечно,
поменять придется, но это непринципиально). Здесь битовая раскладка выглядит
следующим образом:
tile_u_part UUUUU000 00000uuu 0fffffff ffffffff
tile_v_part 00000VVV VVVVV000 0fffffff ffffffff
tile_du UUUUU111 11111uuu 1fffffff ffffffff
tile_dv 00000VVV VVVVV111 1fffffff ffffffff
TILE_U_MASK 00000111 11111000 10000000 00000000
TILE_V_MASK 00000000 00000111 10000000 00000000
Полные формулы (функции) для перевода из 16:16 fixedpoint в "тайловый" 8:15
fixedpoint приведем именно для этого случая; выглядят они вот так:
int make_tile_u(int u) {
return
((u << 8) & 0xF8000000) +
(u & 0x70000) +
((u >> 1) & 0x7FFF);
}
int make_tile_v(int u) {
return
((v << 3) & 0x7F80000) +
((v >> 1) & 0x7FFF);
}
Для полной комплектности осталось только привести кусочек кода для перевода
обычной текстуры в тайловую форму (для случая текстуры 256x256, тайла 8x8,
"вертикального" расположения тайлов).
void tile_texture(char *dst, char *src) {
int u, v;
for (v = 0; v < 256; v++)
for (u = 0; u < 256; u++)
dst[((u << 8) & 0xF800) + (u & 0x7) +
((v << 3) & 0x7F8)] = *src++;
}
главная
Смотрите также
