** финиш **
Все вышесказанное нужно подвергнуть беспощадной оптимизации , которая
отнимет львиную долю времени по созданию 3d-движка .
3.1.1 Fixed pointИспользовать float-формат при 3д-вычислениях -
не хорошая идея ... Пора познакомиться с fixed point-форматом ,
представляющим число в 32-битном формате , отводящем по 16 бит на дробную
и целую часть .
Технология такова : число умножаем на 2^16 , выполняем нужные действия
и делим на 2^16 . В результате повышается точность преобразований .
3.2 Гуро-треугольник
Идея схожа с прорисовкой обычного треугольника
, только добавляется цветовой компонент для каждой вершины треугольника , но
прорисовка становится более приятная . В обычном треугольнике
интерполируется только одна переменная x , в гуро - целых три : обычная
координата x , цветовая координата по x , цветовая координата по y .
Итак , псевдо-код :
- - c[0] - это цвет для (x[0],y[0])
-
- for (a=y[0] -> y[1])
- gouraud_horizline( x[0] + (a-y[0])*d[0], x[0] + (a-y[0])*d[2],
c[0] + (a-y[0])*dc[0], c[0] + (a-y[0])*dc[2], a )
- endfor
Гуро - горизонтальная линия с fixed point :
- - dc = 32-битное целое
- < сравним: x1 > x2? если да, xchg x1 и x2, c1 и c2 >
- dc = ((c2-c1)*65536)/(x2-x1)
- for (a=x1 -> x2)
- putpixel(a,y,c1+((a-x1)*dc)/65536)
- endfor
Оптимизация :
- c1=c1*65536 ;
- for (a=x1 -> x2)
- putpixel(a,y,c1/65536) ; Note!
- c1=c1+dc
- endfor
Здесь критичным по скорости может оказаться деление на 65536 , которое
можно попробовать заменить делением на 256.
3.3 Текстурированный треугольник
Используя идею все той же линейной интерполяции , нарисуем
текстурированный треугольник . По сравнению с гуро , мы добавим еще 2
переменных . Мы будем интерполировать переменные x, u, v , зависимые от y, а
также еще две переменных u и v , зависимых от x. Рассмотрим рисунок :
Левый треугольник
- это тот , который мы рисуем на экране . Справа - битмап-треугольник .
Кодирование выполняется по аналогии с гуро .
- Текстурные координаты (u,v) постоянны и вычисляются только один раз .
- Рассмотрим интерполяцию u1 к u2 за (x2-x1) шагов. Нам понадобится
дельта- к-т :
h_ku = (h_u2 - h_u1) / (h_x2 - h_x1),
Известно ,
что :
- h_u2 = u2 = u1 + (y2 - y1) * ku2,
- h_u1 = u1 + (y2 - y1) * ku1,
- h_x2 = x2 = x1 + (y2 - y1) * kx2,
- h_x1 = x1 + (y2 - y1) * kx1,
когда y=y2 (когда y -
это y для второй вершины).
Подставляя , получаем :
- [u1 + (y2 - y1) * ku2] - [u1 + (y2 - y1) * ku1]
- h_ku=-----------------------------------------------
- [x1 + (y2 - y1) * kx2] - [x1 + (y2 - y1) * kx1]
<=>
- (y2 - y1) * (u1 - u1 + ku2 - ku1)
- h_ku=---------------------------------
- (y2 - y1) * (x1 - x1 + kx2 - kx1)
<=>
- ku2 - ku1
- h_ku=---------
- outerUdelta2-outerUdelta1
- innerUdelta = ---------------------------.
- outerXdelta2-outerXdelta1
3.3.1 Перспективная коррекция Если мы встанем в точку мирового
пространства с координатой (1,1,3000) и начнем двигаться в напралении к
точке (1,1,1) , Как это будет выглядеть на экране ?
Формула преобразования 3D->2D такова :
У нас x и y не меняются :
Но что делать с тектурированным треугольником ?
Попробуем вот так :
Запишем для пиксела такую операцию :
- u_bitmap = u_2D / z_2D,
- v_bitmap = v_2D / z_2D,
or
- u_bitmap = (u/z) / (1/z),
- v_bitmap = (v/z) / (1/z),
or
- u_bitmap = u,
- v_bitmap = v!
На пиксел 2 деления , что медленно
. Оптимизация :
1) Идея в том , чтобы вычислять только для каждого 8 или 16 пиксела ,
а промежутки запонять линейно .
2) Можно избавиться от одного умножения :
- z = 1/z_2D ; z = 1/(1/z) = z
- u_bitmap = u_2D*z
- v_bitmap = v_2D*z.
3.3.2 Bilinear filteringПри линейной бифильтрации цвет
линейно интерполируется между промежуточными узлами .
[Chem] Псевдо-код :
- typedef struct { float r, g, b; } pixel;
- float xf = frac x ; fractional part
- float yf = frac y
- int xd = trunc x ; integer part
- int yd = trunc y
- float w1 = (1.0 - xf) * (1.0 - yf) ; weight
- float w2 = (xf) * (1.0 - yf)
- float w3 = (1.0 - xf) * (yf)
- float w4 = (xf) * (yf)
- pixel p1 = GetBitmapPixel(xd, yd) ; pixel rgb
- pixel p2 = GetBitmapPixel(xd + 1, yd)
- pixel p3 = GetBitmapPixel(xd,yd + 1)
- pixel p4 = GetBitmapPixel(xd + 1,yd + 1)
- float red = p1.r*w1 + p2.r*w2 + p3.r*w3 + p4.r*w4
- float green = p1.g*w1 + p2.g*w2 + p3.g*w3 + p4.g*w4
- float blue = p1.b*w1 + p2.b*w2 + p3.b*w3 + p4.b*w4
(w1234 are the weights of the four texels the pixel hits)
3.4 Texturing + Shading
Исползуется одновременная двойная
интерполяция , которая накладывается друг на друга :
- - 16-битный fixed point
- - tab = заранее просчитанная таблица
- - параметры пиксела: x,y,red,green,blue.
- for (a=y1 -> y2)
- texel = tmap[ u/65536 + v/65536*256 ]
- putpixel( x/65536,a,
- tab[texel,c/65536].r,
- tab[texel,c/65536].g,
- tab[texel,c/65536].b )
- x += kx
- u += ku
- v += kv
- c += kc
- endfor
Инициализация таблицы :
- for (a=0 -> 255)
- for (b=0 -> 255)
- tab[a,b].r = pal[a].r * phong[b].r / 256
- tab[a,b].g = pal[a].g * phong[b].g / 256
- tab[a,b].b = pal[a].b * phong[b].b / 256
- endfor
- endfor
3.5 Выпуклые многоугольники
Нарисуем 5-угольник :
1) Идея прорисовки в следующем : отсортируем вершины выпуклого
многоугольника в порядке убывания координат y .
2) Через каждую вершину проведем горизонтальную линию до
пересечения со стороной многоугольника , и получим точки пересечения .
3. Соединим эти точки пересечения с прилегающими вершинами , в
результате многоугольник будет разбит на элементарные треугольники .
- start1 = stop1
- stop1 = stop1 предыдущая вершина
- start = start1 = stop1
- stop2 was higher:
- start2 = stop2
- stop2 = stop2 следующая vertex
- start = start2
Смотрите также: