31 декабря 2017

    3D движок: фрагменты
Alone Coder

      1. Отрисовка залитого полигона

   Классические  сканлайны  для  полигона,
залитого текстурой:
   - Second Breath:200..500 t
   - Iris Ultrademo:377 t
   - 3D Lame:>400 t
   - Awaken demo:258 t(линейный экранный
буфер) 

   Наш сканлайн тоже под линейный экранный
буфер (l=Y ), время  переброски  которого
утонет  во времени отрисовки множества по─
лигонов. И оптимизирован он для трёх самых
частых случаев:
   - ширина 1 байт (левая и правая стороны
в одном байте) =167t
   - ширина 1+0+1 байт =223t
   - ширина 1+1+1 байт =234t
   И далее с каждым байтом ширины добавля─
ется11t. Это быстрее, чем LDI.

DRSNO
  inc e ;Y
  exx
  add hl,de ;left
  add ix,bc ;right
  dec hy
  jp z,DRSKEEP;обработка конца текущего
                 ;левого или правого ребра
  ld a,h;XL
  exx
  ld l,a;XL
  ld b,(hl);leftmask
  inc h
  ld a,(hl);endx(L)
  ld d,hx;XR
  ld l,d
  ld d,(hl);beginx(R)
  dec h
  sub d;beginx
  jp z,DRSNSAME;если лев.и прав. стороны
                  ;в одном байте
  jr nc,DRSNO;если отрицательная ширина
  add a,a
  ld (DRSjr),a
  ld a,(de)
  xor c;texture
  cpl
  or (hl)
  cpl
  xor c;texture
  ld (de),a
  dec d
  ld a,c;texture
DRSjr=$+1
  jp DRSLOOP
  ...
DRSLOOP ;лев.и пр.стороны не в одном байте
  dup 31;максимальная ширина = 256 пикс
  ld (de),a;texture
  dec d
  edup
  ld a,(de)
  xor c;texture
  and l
  xor c;texture
  ld (de),a
  ...(на начало, реально 2 копии начала)
DRSNSAME ;лев.и прав.стороны в одном байте
  ld a,(hl);rightmask
  cpl
  or b;leftmask
  ld l,a
  ld a,(de)
  xor c;texture
  and l
  xor c;texture
  ld (de),a
  ...(на начало, реально 2 копии начала)

   Чтобы сделать текстуру не на интерлейс─
ном экране,достаточно продублировать цикл,
а во второй копии цикла  вместо регистраc
использоватьly.

      2. Проверка видимости полигона

   Нам  нужно  узнать  знак одной проекции
векторного  произведения  одного  ребра на
другое:
x21 := vert[poly[i].v2].xscr
     -vert[poly[i].v1].xscr;
x31 := vert[poly[i].v3].xscr
     -vert[poly[i].v1].xscr;
y21 := vert[poly[i].v2].yscr
     -vert[poly[i].v1].yscr;
y31 := vert[poly[i].v3].yscr
     -vert[poly[i].v1].yscr;
poly[i].visible := ((x21*y31-x31*y21) >0);

   Обычно  при  этом  действительно делают
вызовы  знаковых  умножений  (иногда  даже
используется вращение нормали грани),но мы
пойдём другим путём.

;bc=y1x1 
;de=y2x2 
;hl=yЗxЗ 
  ld a,h;y1
  sub b;y3
  ld h,a;-dy2 = -y31
  add a,e;x2
  sub c;x1
;a += (dx1 = x21) 
;e*b => a (dx1*dy2) 
  ld e,a;(A/2-(-b)/2)
  sub h
  sub h;b+(A/2-(-b)/2)
   ld h,a
  ld a,d;y1
  sub b;y2
  ld d,a;-dy1 = -y21
  add a,l;x3
  sub c;x1
;a += (dx2 = x31) 
;a*d => a (dx2*dy1) 
  ld b,a;(A/2-(-d)/2)
  sub d
  sub d;d+(A/2-(-d)/2)
  ld l,a
   ld d,h

  ld h,tsqr/256;таблица квадратов
  ld a,(hl)
  ld l,b
  sub (hl);a=(dx2*dy1)=-63..+63
;вычесть e*b => a (dx1*dy2) 
  ld l,d
  sub (hl)
  ld l,e
  add a,(hl);(dx1*dy2)=-63..+63
;a=-126..+126 (7-й бит содержит видимость) 

   Итого123 такта.

   Реально  в  действующем  коде несколько
костылей  для  точности, использующих нашу
технику "зумов" объекта.
   И  всегда  можно  включить вместо этого
16-битный код(VISIBILITY16=1).

       3. Отрисовка короткой линии

   Обычно  оптимизируют случай длинной ли─
нии, то  есть смотрят, сколько тактов ухо─
дит  на один пиксель. Но на больших сценах
наоборот - много  коротких  линий. Поэтому
надо  смотреть, сколько  тактов  уходит на
обвязку линии - на вход и выход.
   Сколько  занимает  обвязка  в известных
движках:
   - Dies Irae =192..227t
   - Second Breath =222..645t
   - Iris Ultrademo = в среднем458t
   - X-Trade = в среднем533t (30..44t/pix
горизонтальная,40..49t/pixвертикальная) 
   - Cheburashka = в среднем244t(60t/pix)

   Мы  сделаем  экстремально - для  каждой
короткой линии сгенерируем спрайт. А чтобы
два раза не вставать, сгенерируем его пря─
мо в  виде процедуры. Рисуем  опять-таки в
линейный экранный буфер.

;de=xy1 
;hl=xy2 
;x=#80..#ff ;так не зашкалим по H 
;y=#80..#ff 
  ld a,d;x1
  sub h;a=dx=-31..+31
   cp 8
   jp p,line_slow_p
   cp -7
   jp m,line_slow_m
  add a,jumptable_center/256
  ld h,a
  ld a,e;y1
  sub l;a=dy=-31..+31
  add a,a;a=2*dy=-62..+62
   jp pe,line_slow_dx;overflow
  add a,a;a=4*dy=-124..+124
   jp pe,line_slow_dx;overflow
  ld l,a;4*dy
  ld c,d;для восстановления в длинных
  sra d
  jp (hl);там jp drawspr_thisangle
            ;(с выходом в line_slow_dy)

   Код коротких линий выглядит так:

...00
   ;<рисуем> 00 (set n,(hl):inc/dec...)
  ret
...0x
  sra h
  jr nc,...00
   ;<рисуем> 01 (set n,(hl):inc/dec...)
  ret
...10
   ;<рисуем> 10 (set n,(hl):inc/dec...)
  ret
drawspr_thisangle
  ex de,hl
;l=y=#80..#ff (т.к. рисуем только чётные 
              ;строки для моушн блура)
;h=x=#80..#ff (точность 2 пикселя) 
  jr nc,0x
  sra h
  jr nc,10
;hl=scrbuf+...: 
;h=f(x)=#e0..#ff, 
;l=f(y)=#80..#ff (остальные l свободны) 
   ;<рисуем> 11 (set n,(hl):inc/dec...)
  ret

   Некоторые  куски кода можно оптимизиро─
вать черезld a,(hl):or N:ld (hl),a  и inc
(hl).

   Можно  рисовать  и  в нелинейный экран,
если добавить код типа:
;e=х 
;l=y 
   ld d,tX/256
   ld a,(de) ;l(X)
   ld h,tY/256
   add a,(hl);l(Y)
   inc h
   ld h,(hl) ;h(Y)
   ld l,a
   ld a,h
   or 7
   И вместо  инкремента по вертикали испо─
льзовать, например:
   cp h
   call z,dhlchr
   inc h

   Например, для  объекта из80 полигонов,
120 линий  (по10 пикс)  и 40 вершин можно 
добиться таких показателей:
  - вершины (без перспективы):118*40=4720
  - полигоны:165*80 = 13200
  - линии:41*60 + (79+460)*60 = 34800
  - стирание (128*128=2K)= 11264
   Итого63984 тактов, то есть  можно даже
фреймово.

   Код линий (более5 килобайт) генерируе─
тся довольно  сложным генератором, который
ещё  объединяет похожие линии. Ещё4 кило─
байта (15 сегментов) занимают переходы.
   Это  для  максимального размера линии7
пикс. Можно настроить  максимальный размер
до31 пикс.
   Правда, в текущей версии ЗD-движка этот
код вообще  выключен, потому что упор сде─
лан  на  залитые полигоны, а память на 48K
не резиновая. Все линии считаются длинными
и  рисуются через медленный код с клипиро─
ванием.
   Но вдруг кому пригодится...

            4. Вращение вершин
        с перспективной коррекцией

   Пусть  рассчитана матрица вращения (см.
rotmatrix.asm - там  же  приведены формулы
для  случая вращения по двум и трём осям),
и  после этого для каждой её клеточки сге─
нерирована таблица умножения на эту клето─
чку  (в каждой  таблице  всего32 значения
координат в объекте: от0 до 31 ). Назовём
это "таблицами  засечек". Таблицы  засечек
строятся простым сложением:
   dup 15
   ld c,h
   push bc
   add hl,de
   ld b,h
   add hl,de
   edup   ;от de*0 до de*29
   ld c,h
   push bc;от de*30 до de*31
   Пусть  координаты вершин в объекте про─
писаны прямо в коде (с прибавлением смеще─
ния  начала  соответствующей таблицы засе─
чек). В случае  чего, код  можно  патчить.
Вращаем  по  трём  осям. Для двух осей (то
есть без вращения по крену) теряется толь─
ко одно слагаемое в одной из координат.
   Пусть отрицательные координаты вершин в
объекте  прописаны  кодом, чтобы не разду─
вать таблицы засечек в два раза.

   ld de,#100*_z+_x
   ld hl,CUTS+_y;засечки

   ld a,(hl);или xor a:sub (hl)
   ld l,d;_z
   add/sub (hl);(=0 без крена)
   ld l,e;_x
   add/sub (hl)
   ld c,a;x'

   inc h

   ld a,(hl);или xor a:sub (hl)
   ld l,d;_z
   add/sub (hl)
   ld l,_y
   add/sub (hl)
   ld b,a;y'

   inc h

   ld a,(hl);или xor a:sub (hl)
   ld l,d;_z
   add/sub (hl)
   ld l,e;_x
   add/sub (hl)
;a = z' 
;b = y' 
;c = x' 
   call div8xinch
;bc = полученные экранные координаты 
   push bc

   Процедура div8xinch делает перспектив─
ную коррекцию с учётом "зума" объекта:

;a = z 
;b = y 
;c = x 
div8xinch
   inc h;таблица 1/z
;a=-127..+127 
   ...;сдвигаем a,b,c через sra
         ;в соответствии с текущим "зумом"
;a=-63..+63 
   add a,#40;Z объекта (патчится)
   ld e,a
   ld a,c;x
   add a,0;X объекта (патчится)
;a/e => c 
;f=флаги после сложения двух знаковых 
;+-8/+7 => +-1.6 (т.е. можно перспективу в 
 ;удвоенном створе экрана, но реально
 ;зависит от делителя - при e=255 будет
 ;только один створ экрана)
;для правильного деления надо a < 2*e 
 ;(иначе надо формировать переполнение)
   jp po,div8xposjp;pe=переполнение
;S=9-й бит результата инверсный 
   jp m,div8xpos
div8xneg
   DIV8NEG div8xpos,div8x_128
   jp div8y
div8x_128 ;выход по переполнению DIV8NEG
   ld l,e ;Z+z
   ld d,(hl) ;1/(Z+z)
   ld h,trotsqrpos/256
   ld c,128
   jp div8y
div8x_127 ;выход по переполнению DIV8POS
   ld l,e ;Z+z
   ld d,(hl) ;1/(Z+z)
   ld h,trotsqrpos/256
   ld c,127
   jp div8y
div8xposjp
;S=9-й бит результата 
   jp m,div8xneg
div8xpos
   DIV8POS div8xpos,div8x_127
   jp div8y

   На  этот момент посчитан правильныйx в
экране с учётом "сплющивания" объекта,пер─
спективной коррекции и "сплющивания" пере─
полнения деления.Делаем то же самое дляy:

div8y
   ld a,b ;y
   add a,0 ;Y объекта (патчится)
;a/e => b 
;f=флаги после сложения двух знаковых 
;+-8/+7 => +-1.6 (т.е. можно перспективу в 
 ;удвоенном створе экрана, но реально
 ;зависит от делителя - при e=255 будет
 ;только один створ экрана)
;для правильного деления надо a < 2*e 
 ;(иначе надо формировать переполнение)
   jp po,div8yposjp;pe=переполнение
;S=9-й бит результата инверсный 
   jp m,div8ypos
div8yneg
   DIV8NEG div8ypos,div8y_128
   ret
div8y_128
   ld b,128;переполнение DIV8NEG
   ret
div8y_127
   ld b,127;переполнение DIV8POS
   ret
div8yposjp
;S=9-й бит результата 
   jp m,div8yneg
div8ypos
   DIV8POS div8ypos,div8y_127
   ret

   Вот  как  выглядит  деление(X+x)/(Z+z) 
для случая положительных аргументов:

   sub e
   jr c,$+2+1+2;CY:a<e
   cp e
   jr nc,div8_127addr;CY:a<2*e ;выход по
                             ;переполнению
   add a,e

   ld l,e
   ld d,(hl);1/(Z+z)
   inc h
   sub d
   ld l,a;a-e
   add a,d
   add a,d
   ld c,a;a+e
;a-e = -#6b..#70 
   ld a,(hl);-sqrsigned
   inc h
   ld l,c;a+e
;a+e = #11..#b5 
   add a,(hl);sqrpos
   srl a;лишний бит точности

   add a,XADD
   ld c,a

   Для(Y+y)/(Z+z) немного  короче, потому
что1/(Z+z) уже прочитано в регистр d:

   sub e
   jr c,$+2+1+2;CY:a<e
   cp e
   jr nc,div8_127addr;CY:a<2*e ;выход по
                             ;переполнению
   add a,e

   dec h
   sub d;1/(Z+z)
   ld l,a;a-e
   add a,d
   add a,d
   ld d,a;a+e
;a-e = -#6b..#70 
   ld a,(hl);-sqrsigned
   inc h
   ld l,d;a+e
;a+e = #11..#b5 
   add a,(hl);sqrpos
   srl a;лишний бит точности

   add a,YADD
   ld b,a

   Разумеется, в реальном  коде  прописаны
костыли,макросы и патчи.Изучайте по месту.
Но это для совсем бесстрашных :)

           5. Вращение объекта

   Объекты переводятся в систему координат
камеры без учёта угла поворота объекта от─
носительно  вертикальной оси (в отличие от
вращения  вершин  того же объекта). Но это
не единственная причина, почему мы вращаем
объекты  не  по матрице вращения. Просто у
этой матрицы недостаточная точность, а ес─
ли её рассчитывать в16 битах, то мы толь─
ко проиграем в скорости.
   Но тот факт, что все объекты преобразу─
ются  одинаково,  позволяет  патчить  сами
16-битные  умножения, которыми  происходит
поворот!
   Кроме того, нам  нужна  не вся точность
синусов-косинусов, потому что в каждом от─
дельном кадре это отражается только на по─
зиции камеры.
   Кроме того, если мы  вращаем камеру то─
лько  по двум осям (без крена), нам  нужно
только  два перекрёстных умножения, причём
можно считать сразу по два умножения в од─
ном сумматоре!
   Код умножения одновременно на две конс─
танты (ячейки матрицы вращения):

;bc,de=+-10.0=%ssssssxx xxxxxxxx 
;результат в hl = k1*bc + k2*de 
   xor a;по идее 1 раз из 4,но надо CY=0
   ld h,a
   ld l,a
   sbc hl,bc;или патчем #ed:nop
   or a
   sbc hl,de;или патчем #ed:nop
   add hl,hl

   dup 5;6
   add hl,bc;или патчем nop
   add hl,de;или патчем nop
   add hl,hl
   edup
   org $-1
   add hl,hl
   sbc a,a
   add hl,hl
   rla
   add hl,hl
   rla
   ld l,h
   ld h,a

   Для одного перекрёстного вращения нужно
два таких фрагмента.
   Патчи  нужно  делать только один раз на
кадр примерно таким кодом:

   ...
   rl e
   sbc a,a
   and c;"add hl,bc"
   ld (hl),a
   inc hl
   rl d
   sbc a,a
   and b;"add hl,de"
   ld (hl),a
   inc hl
   inc hl
   ...

   В итоге  со  всеми входами-выходами всё
вращение  объекта  занимает 1184 такта, а
для объектов за спиной происходит экстрен─
ный выход всего за358 тактов! Это потому,
что для выхода  нужна только половинка од─
ного  перекрёстного  вращения. Разумеется,
такое  срабатывает только при ограниченном
угле тангажа. Если  это  не ваш случай, то
экстренный выход можно убрать.