Секция 4 из 6 - Предыдущая - Следующая
Все секции
- 1
- 2
- 3
- 4
- 5
- 6
градации освещенности. Палитру заполняем так: 32 градации первого цвета,
второго, ..., восьмого. Тогда (для этого примера)
outputColor = (color << 5) + intensity.
5.6.2. 24/32-битные режимы
~~~~~~~~~~~~~~~~~~~~~~~~~~
Здесь все делается теми же самыми таблицами. Только таблица переводит не
цвет в цвет, а компоненту цвета в компоненту цвета. То есть, создаем
таблицы redTable[numShades], greenTable[numShades], blueTable[numShades],
а потом для каждой компоненты каждого пиксела и нужной градации освещенности
по этой таблице определяем выходное значение компоненты:
r = redTable[intensity],
g = greenTable[intensity],
b = blueTable[intensity].
Каждая компонента в этих режимах - это отдельный байт, поэтому никаких
проблем не возникает.
5.6.3. 15/16-битные режимы
~~~~~~~~~~~~~~~~~~~~~~~~~~
Метод 1: тупой, но действенный. Использовать большую таблицу и занести в нее
все возможные комбинации цвета и градации освещения. Таблица получится совсем
не маленькая, размером 65536*32 = 2 мегабайта. Я написал здесь 32, потому как
в этих режимах на компоненту отводится по 5 бит (за исключением 6-битной
зеленой компоненты в 16-битном режим), и делать больше градаций освещенности,
чем 32, бессмысленно.
Метод 2: делать все так же, как в 24/32-битных режимах. Проблемы возникнут
из-за того, что придется с муками выдирать нужные несколько бит компоненты
из пиксела. Таблицы для компонент лучше заранее сделать со всеми нужными
сдвигами, т.е. значения элементов таблиц должны быть такого вида:
000bbbbb - синий, 8 бит
00000gggggg00000 - зеленый, 16 бит
rrrrr000 - красный, 8 бит
Тогда конечный цвет считается примерно так:
outputColor =
(redTable[(color >> 10) & 0x2F] << 8) +
greenTable[(color >> 5) & 0x1F] +
blueTable[color & 0x1F].
На ассемблере это делается, видимо, побыстрее - и покрасивее. Примерно так:
; ...
mov bx,color
shr bx,10
and bx,02Fh
mov ah,redTable[bx]
mov bx,color
and bx,01Fh
mov al,blueTable[bx]
mov bx,color
shr bx,5 ; можно заменить на
and bx,01Fh ; shr bx,4
shl bx,1 ; and bx,02Eh
or ax,greenTable[bx]
mov outputColor,ax
; ...
Метод 3: рисовать все в 24/32-бита, освещение соответсвенно с текстурой
совмещать по пункту 5.6.2, а потом непосредственно при выводе на экран делать
преобразование из 24/32-бит в 15/16. Или использовать PTC и предоставить
делать нужное преобразование именно ему. PTC - это такая графическая система
для C++, взять ее можно на http://www.gaffer.org/ptc.
6. Оптимизация
==============
6.1. Приемы оптимизации для процессоров Intel Pentium
-----------------------------------------------------
Все, что здесь написано, является выборкой наиболее важных на мой взгляд
фактов из документации от Agner Fog. Если вы серьезно интересуетесь
оптимизацией для Intel Pentium (plain, MMX, PPro, P2), найдите и прочтите
эту документацию (я нашел на http://www.agner.org/assem, относительно
старая версия есть на ftp://ftp.cdrom.com/pub/sac/text/pentopt.zip).
6.1.1. Спаривание целочисленных команд
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
По-моему, основной прием ускорения. Дело в том, что у процессоров Pentium
есть два конвейера обработки команд, U-pipe и V-pipe. В результате некоторые
пары команд могут исполняться одновременно, а это практически удваивает
скорость.
Эти команды могут быть исполнены и в U-pipe, и в V-pipe, и при этом могут
быть спарены (с какой-либо другой командой):
mov reg/mem,reg/mem/imm
push reg/imm
pop reg
lea, nop, inc, dec, add, sub, cmp, and, or, xor
некоторые формы test
Эти команды могут быть исполнены только в U-pipe, но при этом все-таки могут
быть спарены:
adc, sbb
shr, sar, shl, sal на заданное число
ror, rol, rcr, rcl на единичку
Эти команды могут быть исполнены в любом конвейере, но могут быть спарены
только в V-pipe:
near call (близкий вызов)
short/near jump (короткий/близкий переход)
short/near conditional jump (короткий/близкий переход по условию)
Все остальные целочисленные команды могут быть исполнены только в U-pipe
и не могут быть спарены вообще.
Две последовательно идущих команды будут спарены в случае выполнения всех
нижеследующих условий. Если хотя бы одно из условий не выполняется, то
исполняется только первая команда, вторая (и, возможно, следующая за ней)
команда будет исполнена лишь в следующем такте. Вот условия спаривания:
1. Первая команда может быть исполнена и спарена в U-pipe, вторая,
соответственно, в V-pipe.
2. Если первая команда записывает что-то в регистр, то вторая команда не
может производить чтение/запись из регистра. Причем, в этом условии
части регистров считаются за весь регистр (то есть, запись в al/ah
расценивается как запись в eax, а запись в cf - как запись в flags).
Пример:
mov eax,1234h / mov ebx,eax - НЕ будут спарены
mov eax,1234h / mov ebx,1234h - будут спарены
inc eax / mov ecx,eax - НЕ будут спарены
mov ecx,eax / inc ecx - будут спарены
mov al,bl / mov ah,0 - НЕ будут спарены
3. Две команды, записывающие что-то в регистр флагов, могут быть
спарены, несмотря на условие 2:
shr ebx,4 / inc ebx - спарится
4. Команда, записывающая что-то в регистр флагов, может быть спарена
с условным переходом, несмотря на условие 2:
cmp eax,2 / ja @@label_bigger - спарится
5. Следующие пары команд могут спариться несмотря на то, что обе команды
изменяют esp:
push + push, push + call, pop + pop
6. Существуют ограничения на исполнение команд с префиксом. Префиксы
возникают в таких случаях:
- команда, адресующаяся не к сегменту по умолчанию, имеет префикс
сегмента (примеры: mov eax,es:[ebx]; mov eax,ds:[ebp])
- команда, работающая с 16-битными операндами в 32-битном режиме
или с 32-битными операндами в 16-битном режиме, имеет префикс
разрядности операнда (примеры: mov ax,1234 в защищенном режиме;
mov ax,word ptr [variable] в защищенном режиме; xor eax,eax в
реальном режиме)
- команды, использующая 32-битную адресацию в 16-битном режиме,
имеет префикс разрядности адреса (пример: mov ax,[ebx] в реальном
режиме)
- rep, lock - префиксы (пример: rep stosd)
- многие команды, которых не было на 8086, имеют двухбайтовый код
команды, где первый байт равен 0Fh. На процессоре Pentium без MMX
этот байт считается префиксом. Наиболее часто встречающиеся команды
с префиксом 0Fh: movzx, movsx, push/pop fs/gs, lfs/lgs/lss, setXX,
bt/btc/btr/bts/bsf/bsr/shld/shrd, imul с двумя операндами и без
операнда-числа (immediate).
На процессоре Pentium без MMX команда с префиксом может исполняться
только в U-pipe, исключение - близкие переходы по условию (conditional
near jumps). На процессоре Pentium с MMX команды с префиксами 0Fh и
размера операнда или адреса может исполняться в любом конвейере; но
команды с префиксами сегмента, rep или lock (повторения или блокировки
шины) могут исполняться только в U-pipe.
7. Команда, в которой одновременно участвует смещение (displacement) и
заданное число (immediate) не может быть спарена на процессоре Pentium
без MMX и может быть выполнена и спарена только в U-pipe на процессоре
Pentium с MMX. Вот примеры:
mov byte ptr ds:[1000],0 ; НЕ спаривается ни с чем
mov byte ptr [ebx+8],1 ; НЕ спаривается ни с чем
mov byte ptr [ebx],1 ; спаривается в U-pipe
mov byte ptr [ebx+8],al ; спаривается в U-pipe
Спаривающаяся команда, которая читает из памяти, считает и записывает
результат в регистр или в регистр флагов занимает 2 такта. Спаривающаяся
команда, которая читает из памяти, считает и записывает результат обратно
в память занимает 3 такта. Примеры таких команд:
add eax,[ebx] ; 2 такта
add [ebx],eax ; 3 такта
Существует также так называемое неполное спаривание (imperfect pairing),
когда обе команды выполняются в разных конвейерах, но НЕ одновременно
(возможно, частично перекрываясь по времени исполнения), а следующие за
ними команды не могут начать исполнение, пока обе команды не закончатся.
Такое случается в следующих случаях:
1. Вторая команда вызывает AGI (address generation interlock,
блокировка генерирования адреса). Это происходит, если адрес,
используемый во второй команде зависит от регистров, измененных
в первой команде. Примеры:
add ebx,4 / mov eax,[ebx] ; AGI
mov eax,[ebx+4] / add ebx,4 ; нормально спаривается
add esp,4 / pop esi ; AGI (pop использует esp)
inc esi / lea eax,[ebx+4*esi] ; AGI
2. Две команды одновременно обращаются к одному и тому же двойному
слову памяти. Примеры (подразумевается, что esi делится на 4):
mov al,[esi] / mov bl,[esi+1] ; неполное спаривание
mov al,[esi+3] / mov bl,[esi+4] ; нормальное спариваение
3. Две команды одновременно обращаются к адресам, в которых одинковы
биты 2-4 (это вызывает конфликт кэш-банков). Для dword-адресов это
значит, что разница между двумя адресами делится на 32. Пример:
mov eax,[esi] / mov ebx,[esi+32000] ; неполное спаривание
mov eax,[esi] / mov ebx,[esi+32004] ; нормальное спаривание
4. Первая команда производит чтение, подсчет и запись одновременно;
вторая - чтение и изменение; в этом случае число тактов, требующееся
для выполнения пары команд, можно рассчитать по следующей таблице:
первая команда
+------------------------------------------+
| mov или | чтение/ | чтение/подсчет/ |
вторая команда | регистровая | подсчет | запись |
+-----------------------+-------------+----------+-----------------+
| mov или регистровая | 1 | 2 | 3 |
| чтение/подсчет | 2 | 2 | 4 |
| чтение/подсчет/запись | 3 | 3 | 5 |
+-----------------------+-------------+----------+-----------------+
Примеры:
add [mem1],eax / add ebx,[mem2] ; 4 такта
add ebx,[mem2] / add [mem1],eax ; 3 такта
add [mem1],eax / add [mem2],ebx ; 5 тактов
add [mem1],eax / sub ebx,ecx ; 3 такта
6.1.2. Кэш-память
~~~~~~~~~~~~~~~~~
У процессора Pentium непосредственно на кристалле есть 8k кэш-памяти (это
т.н. кэш-память первого уровня, L1 cache) для кода и 8k - для данных. Данные
из L1 cache считываются/записываются за один такт; кэш-промах же может
стоить довольно много тактов. Таким образом, для наиболее эффективного
использования кэша необходимо знать, как он работает.
Итак, L1 cache состоит из 256 кэш-линий (cachelines), по 32 байта в каждой.
При чтении данных, которых нет в кэше, процессор считывает из памяти целую
кэш-линию. Кэш-линии всегда выравнены на физический адрес, делящийся на 32;
так что если прочитать байт по адресу, делящемуся на 32, то можно читать и
писать в следующий за ним 31 байт без всяких задержек. Свои данные имеет
смысл располагать с учетом этого факта - например, выравнивать массивы из
структур длиной 32 байта на 32; перед записью в видеопамять читать оттуда
один байт (один раз на 32 записываемых байта); используемые вместе данные
располагать вместе; и так далее.
Но кэш-линия не может быть связана с любым физическим адресом. У каждой
кэш-линии есть некое 7-битное "заданное значение" (set-value), которое
должно совпадать с битами адреса 5-11. Для каждого из 128 возможных значений
set-value есть две кэш-линии. Отсюда следует то, что в кэше не может
одновременно содержаться более двух блоков данных с одинаковыми битами
адреса 5-11. Чем это чревато, покажем на примере.
; пусть в esi - адрес, делящийся на 32
loop_label:
mov eax,[esi]
mov ebx,[esi+13*4096+4]
mov ecx,[esi+20*4096+28]
dec edx
jnz loop_label
У используемых трех адресов будет одинаковое значение в битах 5-11. Поэтому
к моменту самого первого чтения в ecx в кэше точно не окажется свободной
кэш-линии, процессор выберет для нее наименее использованную (least recently
used) линию, ту самую, которая была использована при чтении eax. При
чтении ebx, соответственно, будет заново перекрыта линия, использованная
при чтении ecx... В результате цикл будет состоять из сплошных кэш-промахов
и съест порядка 60 тактов. Если же поменять 28 на 32, изменив, таким образом,
на единичку биты 5-11 для адреса [esi+20*4096+28], то для чтения в eax и ebx
будут как раз использованы две имеющихся линии, для чтения в ecx - третья,
не совпадающая ни с одной из этих двух. В результате - скорость порядка
трех тактов на один проход и ускорение примерно в 20 (!!!) раз.
Еще одна интересная вещь, которую стоит учесть - Pentium НЕ загружает
кэш-линию при промахе записи; только при промахе чтения. При промахе записи
данные пойдут в L2 cache или память (в зависимости от настроек L2 cache).
А это довольно медленно. Поэтому, если мы последовательно пишем в один и
тот же 32-байтовый блок, но не читаем оттуда, то имеет смысл сначала сделать
холостое чтение из этого блока, чтобы загрузить его в L1 cache; тогда все
последовательные операции записи будут есть только по одному такту.
6.1.3. Разные трюки
~~~~~~~~~~~~~~~~~~~
Трюков есть много, перечислим здесь только наиболее часто используемые:
- работа с fixed point вместо floating point иногда (если код не
слишком сильно насыщен математикой) быстрее; практически всегда
быстрее для клонов;
- все данные желательно выравнивать по адресам, кратным размеру данных
(то есть, переменные-байты можно не выравнивать, слова - выравнивать
на 2, двойные слова - на 4); обращение к невыравненной переменной
влечет за собой задержку минимум на три такта;
- деление на заранее известное число можно заменить умножением на
обратное ему число;
- деление на степень двойки для целых чисел заменяется на сдвиг влево;
- деление чисел с плавающей точкой (fdiv) на Intel Pentium (на клонах,
к несчастью, это не так) может исполняться параллельно с целочисленными
командами.
6.2. Примеры внутренних циклов текстурирования
----------------------------------------------
Если немного поработать профайлером, можно выяснить следующую интересную
вещь: большая часть времени на отрисовку сцены тратится именно в процедуре
текстурирования, а в ней, в свою очередь, большая часть времени проходит во
внутреннем цикле (inner loop). Естественно, что его и надо оптимизировать
в первую очередь.
Возьмем этот самый inner loop от обычного аффинного текстурирования (такой
же, на самом деле, используется и в перспективно-корректном) и перепишем на
ассемблере (в критических участках кода на компилятор надеяться не стоит).
Будем использовать 24:8 fixedpoint для u, v, а также 8-битную текстуру
шириной 256 байт.
mov eax,u ; 24:8 fixedpoint
mov ebx,v ; 24:8 fixedpoint
mov ecx,length
xor edx,edx
mov esi,texture
mov edi,outputbuffer
inner:
mov dl,ah ; вытащили целую часть u
mov dh,bh ; вытащили целую часть v
; теперь edx = dx = (100h * v + u) - как раз смещение
; тексела [v][u] относительно начала текстуры
mov dl,[esi+edx] ; dl = texture[v][u]
mov [edi],dl ; *outputBuffer = dl
add eax,du ; u += du
add ebx,dv ; v += dv
inc edi ; outputBuffer++
loop inner
; ...
Красиво, аккуратно, на ассемблере. Только вот согласно правилам спаривания,
половина команд в этом цикле не спарится, и цикл займет порядка 6-7 тактов.
А на самом деле, чуточку переставив местами команды, можно его загнать
где-то в 4.5 такта:
; ...
inner:
mov dl,ah
add eax,du
mov dh,bh
add ebx,dv
mov dl,[esi+edx]
inc edi
dec ecx
mov [edi-1],dl
jnz inner
; ...
В таком виде любая пара команд отлично спаривается, получаем те самые 4.5
такта. Здесь, правда, есть обращения к внешним переменным du и dv, что
может снизить скорость. Решение - самомодифицирующийся код:
; ...
mov eax,du
mov ebx,dv
mov inner_du,eax
mov inner_dv,ebx
; ...
inner:
; ...
add eax,12345678h
org $-4
inner_du dd ?
add edx,12345678h
org $-4
inner_dv dd ?
; ...
Однозначного ответа насчет использования самомодификации нет, а совет, что
можно по этому поводу дать, стандартен - попробуйте, если будет быстрее,
то используйте.
Дальше - больше. 4.5 такта на пиксел - это тоже не предел. В fatmap.txt
(ftp://ftp.hornet.org/pub/demos/code/3d/trifill/texmap/fatmap.txt)
приводится вот такой красивый inner loop на четыре такта.
; текстура должна быть выравнена на 64k
; линии рисуются справа налево
; верхние 16 бит ebx = сегмент текстуры
; bh = целая часть v
; dh = дробная часть v
; dl = дробная часть dv
; ah = целая часть v
; ecx = u
; ebp = du
inner:
add ecx,ebp ; u += du
mov al,[ebx] ; al = texture[v][u]
mov bl,ch ; bl = новая целая часть u
add dh,dl ; считаем новую дробную часть v
adc bh,ah ; считаем новую целую часть v
mov [edi+esi],al ; рисуем пиксел
dec esi ;
jnz inner ;
Надо, правда, отметить, что он уже требует каких-то ухищрений - а именно,
выравнивания текстуры на 64k и отрисовки строк справа налево. Кроме того,
требует более подробного рассмотрения фрагмент с add и adc, об этом более
подробно рассказано чуть ниже.
И, наконец, цитата из fatmap2.txt - 4-тактовый inner loop, использующий
16:16 fixedpoint. Недостатки - текстура должна быть выравнена на 64k;
есть две команды adc, которые могут запросто испортить спаривание. Кстати,
рекомендую скачать этот самый fatmap2.txt; например, по этому адресу:
ftp://ftp.hornet.org/pub/demos/code/3d/trifill/texmap/fatmap2.zip.
; текстура должна быть выравнена на 64k
;
; верхние 16 бит | ah/bh/ch/dh | al/bl/cl/dl
; -----------------+----------------+----------------
; eax = дробная часть u | - | -
; ebx = сегмент текстуры | целая часть v | целая часть u
; edx = дробная часть v | целая часть dv | целая часть du
; esi = дробная часть du | 0 | 0
; ebp = дробная часть dv | 0 | 0
; ecx = длина линии
; edi = буфер
lea edi,[edi+ecx] ; edi += ecx
neg ecx ; ecx = -ecx
inner:
mov al,[ebx] ; al = texture[v][u]
add edx,ebp ; обновляем дробную часть v
adc bh,dh ; обновляем целую часть v (учитывая перенос от дробной)
add eax,esi ; обновляем дробную часть u
adc bl,dl ; обновляем целую часть u (учитывая перенос от дробной)
mov [edi+ecx],al ; outputBuffer[ecx] = al
inc ecx
jnz inner
Этот цикл, с виду, ничем не лучше цикла для 24:8 fixedpoint. Но на самом
деле, он может пригодиться в том случае, если циклу с 24:8 fixedpoint не
хватит точности. Упомянутая нехватка точности проявляется в эффекте "пилы"
внутри относительно больших треугольников, который вовсе не устраняется
добавлением subpixel/subtexel accuracy.
Два последних цикла используют конструкции вида add/adc. Здесь мнения
авторов этих самых циклов явно расходятся с мнениями автора pentopt.txt.
Согласно последнему (и п.6.1.1., соответственно, тоже), add и adc НЕ
спарятся (так как add изменяет регистр флагов, adc - читает из него).
Проведенный эксперимент показал, что они действительно не спариваются, но
он был поставлен на k5; так что на данный момент я достоверной информацией
по этому поводу не располагаю. Впрочем, в любом случае лучше еще чуть-чуть
попереставлять команды - для полной надежности. И для полной надежности,
самостоятельно замеряйте скорость выполнения каждой новой версии цикла и
смотрите, что получилось. Да, совет тривиальный. Но после того, как на моем
k5 цикл из четырех инструкций исполнился, согласно замерам, за такт...
6.3. Использование инструкций MMX
---------------------------------
Если вкратце (а по-другому и не выйдет) с помощью MMX можно довольно неплохо
разогнать некоторые медленные операции - например, сделать RGB-освещение. Или
текстурирование с билинейной фильтрацией. Здесь я только продемонстрирую эти
два примера; всяческие дальнейшие применения - на откуп читателю.
Пример внутреннего цикла с освещением через инструкции MMX:
mov eax,u ; 24:8 fixedpoint
mov ebx,v ; 24:8 fixedpoint
mov ecx,length
xor edx,edx
mov esi,texture
mov edi,outputbuffer
movq mm1,light ; RGB-освещенность, qword (4 штуки 0:9 fixedpoint)
movq mm2,delta_light ; изменение освещенности
inner:
mov dl,ah ; dl = (u >> 8)
add eax,du ; u += du
mov dh,bh ; dh = (v >> 8)
add ebx,dv ; v += dv
movd mm0,[esi+4*edx] ; грузим пиксел
punpcklbw mm0,mm0 ; распаковываем пиксел
psrlw mm0,1 ; для того, чтобы были беззнаковые числа
pmulhw mm0,mm1 ; умножаем RGB на RGB-освещенность
add edi,4
dec ecx
packuswb mm0,mm0 ; пакуем пиксел обратно
paddw mm1,mm2 ; light += delta_light
movd [edi-4],mm0
jnz inner
Этот цикл дает после некоторой дальнейшей оптимизации 7 тактов на
пиксел - зато с текстурированием и полноценным RGB-освещением. Собственно
освещение занимает лишь 2 такта. Не очень плохо.
Пример внутреннего цикла с билинейной фильтрацией через инструкции MMX:
mov eax,u ; 24:8 fixedpoint
mov ebx,v ; 24:8 fixedpoint
mov ebp,length
xor ecx,ecx
xor edx,edx
mov esi,texture
mov edi,outputbuffer
inner:
mov dl,ah ; dl = (u >> 8)
add eax,du ; u += du
mov dh,bh ; dh = (v >> 8)
add ebx,dv ; v += dv
mov cl,al ; ecx = (u & 0xFF) = fu - дробная часть u
movd mm0,[esi+4*edx] ; грузим пикселы
movd mm1,[esi+4*edx+4]
movd mm2,[esi+4*edx+4*256]
movd mm3,[esi+4*edx+4*257]
punpcklbw mm0,mm0 ; распаковываем пикселы
punpcklbw mm1,mm1
punpcklbw mm2,mm2
punpcklbw mm3,mm3
psrlw mm0,1 ; для того, чтобы были беззнаковые числа
psrlw mm1,1 ; и pmulhw (знаковое умножение) работало
psrlw mm2,1 ; нормально
psrlw mm3,1
psubw mm1,mm0 ; mm1 = tex[v+1][u] - tex[v][u]
psubw mm3,mm2 ; mm3 = tex[v+1][u+1] - tex[v][u+1]
pmulhw mm1,tab[8*ecx] ; mm1 *= fu
pmulhw mm3,tab[8*ecx] ; mm3 *= fu
add esi,4
add edi,4
psllw mm1,7 ; корректируем результат умножения
psllw mm3,7 ;
paddsw mm0,mm1 ; mm0 = tex[v][u] + mm1
paddsw mm2,mm3 ; mm2 = tex[v][u+1] + mm3
mov cl,bl ; ecx = (v & 0xFF) = fv - дробная часть v
psubw mm2,mm0 ; mm2 -= mm0
pmulhw mm2,tab[8*ecx] ; mm2 *= fv
psrlw mm0,7 ; корректируем результат умножения
paddsw mm0,mm2 ; mm0 += mm2 - отфильтрованное значение
packuswb mm0,mm0 ; пакуем пиксел
movd [edi-4],mm0 ; записываем его
dec ebp
jnz inner
Отдельного упоминания и разъяснение требует табличка tab. Это просто табличка
дробных частей в готовом для MMX-умножения виде:
tab label qword
dw 0,0,0,0
dw 1,1,1,1
dw 2,2,2,2
; ...
dw 255,255,255,255
То есть в данном примере tab[8*ecx] = [cl, cl, cl, cl] - как раз готовая для
использования в MMX-инструкциях дробная часть.
Здесь получается уже довольно приличное количество тактов на пиксел, порядка
двадцати. Но несмотря на это, вышеприведенный цикл уронил fps на моей любимой
тестовой сцене всего лишь в 1.5 раза по сравнению с обычным текстурированием.
Тоже не очень плохо. В общем, успехов в использовании. Только не забывайте
включать поддержку не-MMX режима для тех, у кого MMX нет, и, соответственно,
детектор наличия MMX-инструкций.
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
Секция 4 из 6 - Предыдущая - Следующая
© faqs.org.ru
