09 декабря 2019 года    
Понедельник | 05:02    
Главная
 Новости
Базы данных
Безопасность PC
Всё о компьютерах
Графика и дизайн
Интернет-технологии
Мобильные устройства
Операционные системы
Программирование
Программы
Связь
Сети
 Документация
Статьи
Самоучители
 Общение
Форум







Разделы / Программирование / Другие

demo.design 3D programming FAQ.

Секция 4 из 6 - Предыдущая - Следующая
Все секции - 1 - 2 - 3 - 4 - 5 - 6

а лучше - сдвиг, и одно сложение. Пример: пусть у нас есть 8 цветов и 32
градации освещенности. Палитру заполняем так: 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 при сложении не вызвали бы
переноса и не испортили смещение на единичку. Достигается это использованием

Секция 4 из 6 - Предыдущая - Следующая

 demo.design 3D programming FAQ.
Лента новостей


2006 (c) Copyright Hardline.ru