ОПТИМИЗАЦИЯ
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++;
}