3.6 Copyright 1994 Sean Barrett

3.6.1 Базис

Примем систему координат , построенную по правилу правой руки : X - вправо , Z - вверх , Y - вглубь экрана .
Текстура - массив пикселов , который применяется для прорисовки полигонов .
run - строка пикселов , обрабатываемая в одном цикле .
arbitrarily-angled polygon - произвольный многоугольник .
Для описания текстуры как 2-мерного массива используется специальная система координат , называемая "u-v" системой .
Обозначение вектора : P = < Px, Py, Pz >.
x,y,z - 3-мерные координаты
i,j - экранные координаты
u,v - текстурные координаты
a,b,c - специальные координаты : u = a/c, v = b/c
Примем 3 вектора для текстурных координат :
P - координатный ноль,
M и N - вектора для u&v осей .
Переход от 3D к 2D :
(x,y,z) -> (i,j)
i = x / y
j = z / y
Координату (0,0) мы определим в начало экрана . В этом случае преобразование мировой координаты к экранному виду :

i = Hscale * x / y + Hcenter
j = -Vscale * z / y + Vcenter

где нужно буде умножить Px, Mx, Nx на Hscale, а Hcenter =0 . Начнем с вычисления 9 векторов , применяемых для маппинга полигонов :

Oa = Nx*Pz - Nz*Px
Ha = Nz*Py - Ny*Pz
Va = Ny*Px - Nx*Py

Ob = Mx*Pz - Mz*Px
Hb = Mz*Py - My*Pz
Vb = My*Px - Mx*Py

Oc = Mz*Nx - Mx*Nz
Hc = My*Nz - Mz*Ny
Vc = Mx*Ny - My*Nx

Для того , чтобы найти соответствие между экранной координатой(i,j) и текстурной(u,v) :

a = Oa + i*Ha + j*Va
b = Ob + i*Hb + j*Vb
c = Oc + i*Hc + j*Hc

u = a/c
v = b/c

3.6.2 Основы

Итак , мы имеем полигон , который надобно заполнить текстурой . Каковы тут основные проблемы ? Сразу можно выделить большие временные затраты на вычисление и проблемы с нечеткой прорисовкой граней . Начинать всегда нужно с ПРОСТОГО , ясного , пусть и медленного алгоритма , но правильного .
Для начала рассмотрим маппинг простого квадратного полигона . Текстуру возьмем размером 256*256 . В качестве основного формата при вычислениях мы будем использовать floating point . Привяжем текстуру к квадратному полигону : левый нижний угол полигона совпадет с текстурной координатой (0,0) , остальные углы полигона соответственно с текстурными координатами (<256, 0>, <256, 256>, <0, 256>). Полигон имеет 4 вершины V[0], V[1], V[2], V[3] . Вектор P совпадает с V[0]. Вектор M начинается в V[0] и заканчивается в V[1], т.е M = V[1] - V[0] . Вектор N начинается в начале координат и заканичается в коордиате <0, 256>, т.е. N = V[3] - v[0]. Вычисляем 9 векторов (вектора O, H, V) , как описано выше . Далее , для каждого пиксела в полигоне , экранные координаты которого , вычисляем переменные a, b, c, (см. выше), а уже с их помощью вычисляем , которые всегда находятся в диапазоне от 0...1 . Поэтому их еще прийдется домножать на 256 .
Алгоритм (режим 320*200) :

[ loop #1 ]
for every j which is a row in the polygon
screen = 0xA0000000 + 320*j
for i = start_x to end_x for this row
a = Oa + (Ha * i) + (Va * j)
b = Ob + (Hb * i) + (Vb * j)
c = Oc + (Hc * i) + (Vc * j)
u = 256 * a / c
v = 256 * b / c
screen[i] = texture_map[v][u]
endfor
endfor


3.6.3 DOOM

Немного о прорисовке стен , полов , потолков (технология а-ля DOOM - Ultima Underworld - Legends of Valour).
Рассмотрим цикл :
a = Oa + Va*j
b = Ob + Vb*j
c = Oc + Vc*j

a += start_x * Ha
b += start_x * Hb
c += start_x * Hc

for i = start_x to end_x
u = 256 * a / c
v = 256 * b / c
screen[i] = texture_map[v][u]
a += Ha
b += Hb
c += Hc
endfor

Прежде всего , в цикле нужно попробовать избавиться от делений . Это можно сделать в том случае , если на протяжении всего цикла переменная c есть величина постоянная , а это будет в том случае , если все пикселы в рассматриваемой строке находятся на одной глубине . Для потолков и полов это всегда справедливо , так что :

__setup from loop #2__
u = 256 * a / c
v = 256 * b / c
du = 256 * Ha / c
dv = 256 * Hb / c
for i = start_x to end_x
screen[i] = texture_map[v][u]
u += du
v += dv
endfor
Что касается стен , здесь не Hc , а другой вектор - Vc - равен нулю . Это означает , что нам от горизонтальной прорисовки нужно перейти к вертикальной . При такой прорисовке константы a , c , u остаются неизменны , меняется только ОДНА переменная - v , отсюда и скорость .

3.6.4 Асм-оптимизация

Растянем наш полигон по длине в 4 раза и заполним его той же самой текстурой :

Polygon A-B-C-D

A
o--------o-E------------_______o B
|111112222 |
|111112222 |
|111112222 |
|333334444 |
|333334444 |
|333334444 ________-------C-o
o--------o-

Texture map

u=0 u=1
11112222
11112222
33334444
33334444

При этом , для 1-й четверти значения u будут лежать в пределах 0 <= u <= 1. Для 2-й четверти значения 1 <= u <= 2 , здесь можно отбросить целую часть , взяв только дробную . Аналогично для остальных частей . Т.е. здесь применяется механизм взятия u по маске .

[ loop #4 ]
mask = 127, 63, 31, 15, whatever.
for (i=0; i < len; ++i) {
temp = table[(v >> 16) & mask][(u >> 16) & mask];
u += du;
v += dv;
}

Рассмотрим ассемблерную оптимизацию для горизонтальной прорисовки .
Дробная часть имеет 16-битный формат .
mov al,mask
mov ah,mask
mov mask2,ax ; setup mask to do both at the same time
loop5 and bx,mask2 ; mask both coordinates
mov al,[bx] ; fetch from the texture map
stosb
add dx,ha_low ; update fraction part of u
adc bl,ha_hi ; update index part of u
add si,hb_low ; these are constant for the loop
adc bh,hb_hi ; they should be on the stack
loop loop5 ; so that ds is free for the texture map
В следующем куске рассмотрен механизм 32-битного сложения вместо 16-битного . Проблема в том , что при маппинге используется дополнительная индексация текстуры . Для сложения чмсел , имеющих формат более 16 бит , используем команду ADC . Уловка в том , что 32-разрядный регистр ESI содержит в верхней половинке hb_low , а в нижней - ha_hi , так что одной командой ADC мы убиваем 2-х зайцев :
loop6 and bx,mask2
mov al,fs:[bx]
stosb
add dx,bp ; update fractional part of u
adc ebx,esi ; update u (BL) and frac. part of v (EBX)
adc bh,ch ; update index part of v
dec cl
jnz loop6
Следующий кусок кода - быстрый no-wraparound texture mapper для 32-разрядного fixed-point . ADC используется дважды . Флаг CF очищается на каждой итерации . В регистре EBX содержится u , в регистре EDX - v . Алгоритм выводит за одну итерацию ДВА пиксела :
loop7
mov al,[bx] ; get first sample
adc edx,esi ; update v-high and u-low
adc ebx,ebp ; update u-high and v-low
mov bh,dl ; move v-high into tmap lookup register
mov ah,[bx] ; get second sample
adc edx,esi
adc ebx,ebp
mov bh,dl
mov es:[di],ax ; output both pixels
inc di ; add 2 to di without disturbing carry
inc di
dec cx
jnz loop7


3.6.5 Проблемы

Однажды вы можете обнаружить , что переменные U & V находятся за пределами 0..1 . Это может выглядеть либо как черный пиксел , либо как мусор , либо еще как-то . Причины могут быть различны . Пиксел может оказаться вне пределов полигона . При неправильном определении векторов P, M, N текстура может оказаться больше полигона . Нужно в таких случаях использовать wraparound textures . Можно сделать защиту :
if (u < 0) u = 0; else if (u > 1) u = 1;
if (v < 0) v = 0; else if (v > 1) v = 1;
Многие движки используют для удаления скрытых поверхностей алгоритм художника . Отличительной особенностью качественного текстурного маппинга является то , что каждый пиксел должен быть отрисован на экране лишь один раз . Что касается z-буффера , то в данном случае он неприемлим . Нужно заранее отказываться от полигонов с произвольным числом углов-вершин и по возможности все сводить к стенкам - потолкам .


3.6.6 Освещение

В DOOM использован flat-run shading. Испоьзуется световая таблица , представляющая 2-мерный массив . На цвет пиксела накладывается интенсивность , вычисляемая по таблице . Алгоритм :
...compute light...
for (i=start_x; i <= end_x; ++i) {
color = texture[v >> 16][u >> 16];
output = light_table[light][color];
screen[i] = output;
u += du;
v += dv;
}
При Gouraud shade алгоритм таков : нужно сначала вычислить световую интенсивность в начале и в конце световой строки :
z = light1 << 16;
dz = ((light2 - light1) << 16) / (end_x - start_x);
for (i=start_x; i <= end_x; ++i) {
color = texture[v >> 16][u >> 16];
output = light_table[z >> 16][color];
screen[i] = color;
u += du;
v += dv;
z += dz;
}
Рассмотрим ассемблерную версию . Особенность процессоров линии 80x86 в том , что они имеют всего один регистр , который можно использовать для индексации - BX . вследствие этого маппинг и освещение будут разнесены по разным циклам . Указатель на текстуру - в DS , световую таблицу - в GS .
flat-shading inner loop :

mov ch,fs:light
adc ax,ax
loop8 shr ax,1 ; restore carry
mov cl,[bx] ; get first sample, setting up cx for color lookup
adc edx,esi ; update v-high and u-low
adc ebx,ebp ; update u-high and v-low
mov bh,dl ; move v-high into tmap lookup register
mov ah,[bx] ; get second sample, save it in ah
adc edx,esi
adc ebx,ebp
mov dh,bl ; save value of bl
mov bx,cx ; use bx to address color map
mov al,gs:[bx] ; lookup color for pixel 1
mov bl,ah ; switch to pixel 2
mov ah,gs:[bx] ; lookup color for pixel 2
mov es:[di],ax ; output both pixels
mov bl,dh ; restore bl from dh
mov bh,dl
adc ax,ax ; save carry so we can do CMP
add di,2
cmp di,fs:last_di ; rather than having to decrement cx
jne loop8
Для Gouraud shading : в цикле трижды используется adc :
loop9 shr ax,1 ; restore carry
mov al,fs:[bx] ; get first sample
mov ah,cl ; save away current z-high into AH
; this makes AX a value we want to lookup
adc edx,esi ; update v-high and u-low
adc ebx,ebp ; update u-high and z-low
adc ecx,z_v_inc ; update z-high and v-low
mov bh,dl ; move v-high into tmap lookup register
mov ch,fs:[bx] ; get second sample, save it in ch
mov dh,bl ; save value of bl
mov bx,ax
mov al,gs:[bx] ; lookup first color value
mov bl,ch
mov bh,cl
mov ah,gs:[bx] ; lookup second color value
mov es:[di],ax ; output both pixels
mov bl,dh ; restore bl from dh
adc edx,esi
adc ebx,ebp
adc ecx,z_v_inc
mov bh,dl
adc ax,ax ; save carry
add di,2
cmp di,last_di ; rather than having to decrement cx
jne loop9

Смотрите также: