Тайловые текстуры В пункте кратко описана схема работы кэш-памяти для процессоров 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++; } <<<  Назад  1  2  3  4  5   8  Комментарии к статье  8 8  Обсудить в чате