4.1 Z-сортировка

function quicksort(left, right)
if left<right
q = partition(left,right)
quicksort(left,q)
quicksort(q+1,right)
endif
endf
function partition(left, right)
- crd = таблица вершин
- face = таблица полигонов
x = crd[face[left,0],2] + crd[face[left,1],2] + crd[face[left,2],2]
a = left-1
b = right+1
loop forever:
decrement b by one as long as (crd[face[b,0],2] +
crd[face[b,1],2] + crd[face[b,2],2]) is less than x
increment a by one as long as (crd[face[a,0],2] +
crd[face[a,1],2] + crd[face[a,2],2]) is greater than x
if a<b
xchg(face[a],face[b])
else
break looping and return b
endif
endloop
endf

Вообще , Z-sort - не самый быстрый способ .

4.2 Z-буффер

float zbuffer[64000];

Псевдокод :

z = z1
for x=x1 -> x2
if (z < zbuffer[y*320+x])
zbuffer[y*320+x] = z
plot(x,y,color)
endif
z = z + kz ; интерполяция z
endfor

Рекомендуется интерполировать 1/z вместо of z :

opz = opz1
for x=x1 -> x2
if ( (opz+cur_frame) < zbuffer[y*320+x] )
zbuffer[y*320+x] = opz
plot(x,y,color)
endif
opz = opz + k_opz ; interpolate z
endfor

4.3 BSP-Tree

4.3.1 Основная идея Рассмотрим 6 линий :
(X = положение камеры) Создадим дерево :
Бинарное дерево :

1). Все проверяем относительно линии 1 . Проверим , с какой стороны от нее находятся все остальные линии . Линия 1 разбивает линию 2 на половинки : 2a и 2b . Если камера находится СЛЕВА от линии 1 , проверим сначала , есть ли линии с ПРАВОЙ стороны от линии 1 - есть , это линия 2а , рисуем ее , затем рисуем саму линию 1 .
2). Продолжим относительно линии 2 . Мы находимся СПРАВА от линии 2 . Что находится СЛЕВА от линии 2 ? 3a , 5c , 4 , 5b и сама 2 b .
3). Продолжим относительно линии 3 . Мы находимся СЛЕВА от нее , что находится СПРАВА от нее ? Только 6a , рисуем , далее сама 3b .
4). Продолжим относительно линии 5 . Мы находимся СПРАВА от нее , что находится СЛЕВА от нее ? Осталось прорисовать 6b и 5a .
Итак , порядок вывода таков : 2a,1,3a,5c,4,5b,2b,6a,3b,6b,5a.

4.3.2 Формулы

Уравнение для плоскости :

Nx * (X-ax) + Ny * (Y-ay) + Nz * (Z-az) = 0,
где N - нормальный вектор плоскости , X, Y, Z - произвольные к-ты , и (ax,ay,az) - точка на этой плоскости . Нормальный вектор вычисляем с помощью 2-х вершин полигона . Для того , чтобы проверить , принадлежит ли точка с произвольными координатами (ax1,ay1,az1)плоскости , нужно подставить их в уравнение , и в случае равенства нулю принадлежит . В противном случае она лежит либо слева , либо справа от плоскости , в зависимости от знака .

Если вершины полигона разбросаны по разные стороны от плоскости , значит , полигон пересекается с данной плоскостью . В таком случае найдем линию пересечения :

X = X1 + (X2-X1)t
Y = Y1 + (Y2-Y1)t
Z = Z1 + (Z2-Z1)t
Эта линия проходит через точки (X1,Y1,Z1) и (X2,Y2,Z2) Подставив эти X, Y, Z в уравнение плоскости , мы получим :
Nx*(X1+(X2-X1)t-ax) +
Ny*(Y1+(Y2-Y1)t-ay) +
Nz*(Z1+(Z2-Z1)t-az) = 0
Найдем t:
Nx*(X2-X1)t + Ny*(Y2-Y1)t + Nz*(Z2-Z1)t =
Nx*(X1-ax) + Ny*(Y1-ay) + Nz*(Z1-az)
< = >
t * ( Nx*(X2-X1) + Ny*(Y2-Y1) + Nz*(Z2-Z1) ) =
Nx*(X1-ax) + Ny*(Y1-ay) + Nz*(Z1-az)
< = >
Nx*(X1-ax) + Ny*(Y1-ay) + Nz*(Z1-az)
t = --------------------------------------
Nx*(X2-X1) + Ny*(Y2-Y1) + Nz*(Z2-Z1)
Все это просчитывается 1 раз при инициализации .

4.3.3 Хинты1) Вычислять уравнение плоскости - дело неблагодарное , лучше один раз в начале программы вычислить нормаль для нее .

2) Другой путь к ускорению - уменьшить число полигонов .

4.4 S-buffer

S-buffer - вариант z-буффера , где происходит сортировка scanlines , а не пикселов . При выводе горизонтальных линий необходимо сравнивать лишь конечные координаты .

В таблице происходит их сравнение , сортировка , после чего делаем вывод :

typedef struct
{
short xb,xe,zb,ze; // x_begin, x_end, ...
byte ub,ue,vb,ve;
long kz,ku,kv; // kz = (ze-zb)*65536/(xe-xb) etc
unsigned char used; // if 0 -> not used
} sbuf_t;
sbuftype sbuf[200][100]; // 200 lines in mode 320x200,
// max. 100 segments / line

Сегменты могут взаимно располагаться 6-ю возможными способами (старое значение = v, новое = u):

(1)
vvvvvvvv
uuuuuuuu
(2)
vvvvvvvv
uuuuuuuu
(3)
vvvvvvvv
uuuuuuuuuuu
(4)
vvvvvvvv
uuuuuuuuuuu
(5)
vvvv
uuuuuuuuuuu
(6)
vvvvvvvvvvv
uuuu
- tmap = 256x256-sized bitmap
function flip_sbuf
integer i,j,k
integer du,dv
for i=0 -> 199
j = 0
while sbuf[i][j].used<>0 and j<100
du = 0
dv = 0
for k=sbuf[i][j].xb -> sbuf[i][j].xe
putpixel(k,i,tmap[sbuf[i][j].ub+du/65536+
(sbuf[i][j].vb+dv/65536)*256])
du = du + sbuf[i][j].ku
dv = dv + sbuf[i][j].kv
endfor
j = j + 1
endwhile
endfor
endf
function clear_sbuf()
integer i,j
for i=0 -> 199
j = 0
while sbuf[i][j].used<>0 and j<200
sbuf[i][j].used=0
j = j + 1
endwhile
endfor
endf

Смотрите также:
www.new-maneg.ru