Scream #02
29 января 2002

Tutorials - coding: реализация эффекта "Mirror rotator" (статья рассчитана на довольно подготовленного демо-кодера).


| coding 
| vivid//brainwave 



   Хотелось бы сначала сделать лирическое отступление. Hекоторые
из  вас,  наверное, читали нулевой выпуск ковровской электронной
газеты    Kosme,    выпускаемой   группой   Placebo (ex-Eternity
Industry). В этой газете содержалась статья main coder'а группы, 
Sairoos'а  о  демосцене. Скажу лишь, что я, как кодер, во многом 
солидарен  с  Сайрусом.  Во многом, но не во всем. А именно, мне
непонятна  была его дикая реакция на нашу дему Tryptomine Dream.
И  если  личную  неприязнь  Сайруса  к  мультиколорам я еще могу
понять (мне,  например,  чанки не очень нравятся), то его слова,
из которых явно или косвенно следовал вывод о том, что почти все
в  Tryptomine  Dream  сделано  при помощи анимации, пусть даже и
заранее  рассчитанной,  не  могли  не  визвать  в моей душе бурю
негодования.  Конечно,  мы  с  ним  при  личной встрече на CC'01
выяснили  все  недоразумения, однако у некоторых читателей Kosme
после этой статьи могло уже сложиться негативное мнение о группе
Brainwave  и  ее  демах.  После CC я пытался связаться с Placebo 
посредством  e-mail'а  с  просьбой  дать опровержение негативных
слов,  высказанных в наш адрес, однако так до сих пор не получил
ответ.  Поэтому  придется делать опровержение самостоятельно. ;)
Пользуясь  предоставленной  мне  возможностью могу смело заявить
на  всю спектрумовскую демосцену: "Во всех демах, выпущенных под
лейблом  Brainwave  отсутствует  анимация  в привычном понимании 
этого     слова!"     Т.е.     никакой    заранее    загруженной 
последовательности  кадров у нас в демах не было нет и, надеюсь,
не будет. Pre-calculated animation (т.е. анимация, кадры которой
рассчитываются во время декрянчинга, а потом просто выводятся) у
нас  в  демах  тоже  не  применялась.  Правда,  было в 4k Marazm
заранее рассчитанное шахматное сердечко, но это было давно, да и
оправдываться   за   маразм  двухгодовалой  давности  я  уже  не
собираюсь, к тому же это единичный случай.
   Теперь   вопрос   терминологии.   Четкого   разделения  между
анимацией  и  реалтаймом  нет.  Еще  на  CC'01 у меня был спор с
Flying^DR  и  Sair00s^PCB  на эту тему. Скажем, можно ли считать 
анимацией  вывод  3д объекта по заранее просчитанным координатам
его вершин? А использование Look Up таблиц (Bump mapping, Sphere
mapping,  Tunnel,...)?   А  использование  синусных  таблиц  при 
рассчете   3d   вместо  честного  рассчета  синусов  по  формуле
Тейлора?   У  каждого на этот счет свое мнение. Так, что-то меня 
увело  не  в  ту  сторону.  Я, вроде, о кодинге собирался писать
статью. Этим и займусь.

   Предполагается,    что    статья   рассчитана   на   довольно
подготовленного  демо-кодера,  имеющего  некоторый базовый набор
знаний.

                        Mirror rotator.

   Впервые  появился  на  Спектруме  в  деме  Refresh  и  GOA4k,
написанных Exploder^Extreme, потом реинкарнировался в нашей деме
Tryptomine Dream в мультиколорной реализации. Кстати, Сайрус его 
принял  за  прекалкулейтинг (видать,  смутил  мультиколор, 25fps
(которые  он  посчитал за 50) и подзагрузка перед ним). Сразу же
изложу алгоритм своей собственной реализации.
   У  меня  есть  текстура размером 128*128 точек. Причем в друх
одинаковы   экземплярах.  В  центре  каждой  текстуры  есть  так
называемый  View  port,  размером  с  экран (в  моем  случае это
64*48). 

                ┌──────────────┬──────────────┐
                │              │              │
                │   ┌──────┐   │   ┌──────┐   │
                │   │      │   │   │      │   │
                │   │      │   │   │      │   │
                │   └──────┘   │   └──────┘   │
                │              │              │
                └──────────────┴──────────────┘

   Для  получения  эффекта  надо всего лишь использовать обычный
Rotate-Zoomer,  используя текстуру из первого буффера для вывода 
во  Viewport  второго буффера. Далее, картина из второго буффера
перекидывается  в  экран.  При  отрисовке  следующего кадра роль
текстуры-источника  выполняет  второй  буффер,  а роль текстуры-
приемника - первый.
   Это общий алгоритм. Теперь детали моей реализации.
   Ротозумер - довольно  жрущий  эффект,  поэтому  использование
классического   60   тактового   иннерлупа  оказывается  слишком
медленным   для   разрешения   64*48.   Поэтому   были   сделаны
упрощения (кстати, в Refresh и GOA было то же самое):
   Использование  тангенса вместо синуса,ограничив угол поворота
от -pi/4 до +pi/4. Это дало возможность перемещаться по текстуре
вдоль оси X с шагом 1, а по оси Y - с шагом tg(alfa). Недостаток
- зуминг  как  таковой  зависит  только  от  угла поворота и его
нельзя  гибко  менять. Достоинство - на расчет цвета одной точки
уходит всего 20 тактов:

   ldi; перекидываем точку и, одновременно, смещаемся по X
   nop; сюда в процессе decrunching'а подставляется команда
      ; nop, inc h или dec h для необходимости смещения
      ; по оси Y в текстуре

   Далее,  непосредственно  то,  для  чего  он  был  реализован:
сам  мультиколор.  Эффект  рассчитывается  параллельно с выводом
мультиколора.   Достоинство:   рационально   используется  время
процессора. Недостаток: написать сложно, хотя и можно.
   Для  того,  чтобы создать мультиколор 4*4, необходимо (в моей
реализации),  чтобы  четные  строки хранились на одном экране, а
нечетные - на  другом.  При  этом надо переключаться с экрана на
экран  через  224*4=896  тактов (здесь  и  далее подразумевается
синхронизация   под   Пентагон-128).  На  рассчет  одной  строки
вышеупомнутым иннерлупом уходит 20*64+?? тактов, т.е. около 1300
тактов.  Получается,  что  рассчитать  одну строку за 896 тактов 
невозможно. Значит у нас два выхода:

1.   Рассчитать   начальную  часть  строки,  переключить  экран, 
рассчитать  остаток  строки,сделать задержку до 896*1792 тактов,
не  забыв  переключить экран. В этом случае мы теряем просто так
около  500  тактов.  Думаю,  Full Screen 25 fps Mirror rotator в
этом случае не сделать.
2.  Я  выбрал  именно этот способ, хотя он более трудоемок. Надо 
переключать  экраны  через  896  тактов,  не  делая  паузы между
рассчетом  строк.  Это  довольно нетривиальная задача, поскольку
сам  характер иннерлупа (необходимость перерассчитывать команды,
стоящие  после  ldi,  для  каждого  фрейма  заново) не позволяет
раздекрянчить  этот код на всю доступную память. К тому же, этой
оставшейся  памяти остается довольно мало (32 килобайта занимает
текстура,  8 килобайт экран и переменные бейсика, плюс код нужен
еще и для других вещей). Выход один: извращаться с динамическими
точками останова. Расскажу об этом лишь вкратце (подробности уже
подзабыл,   т.к.   прошло   больше   года.   Кому   надо,  могут
посмотреть исходник). В общем виде main loop выглядит так:

      org #ed00      ;почему #ed00, узнаете дальше
      ld bc,#7ffd
      ld de,#1018
      ld h,#ed
      exx
      ...
      ld sp,AddTab
loop: расчет адреса текущей строки и пр. 
      rept 64
       ldi:nop
      endr
      рассчет адреса нижележащей строки
      ret
exit: 

   Казалось бы, зачем здесь ret? А вот зачем:
1.  когда нужно, выполняет роль команды djnz, только выполняется 
за 10 тактов вместо 13 ;)
2. когда нужно, снимает адрес маленькой процедурки типа: 

      exx
      ld l,xx
      ld (hl),#c9    ;код команды ret
                     ;ставим точку останова на место кода #еd
                     ;команды ldi
      exx
      ret            ;переходим на начало цикла

Попав  на этот ret мы переходим на процедуру примерно следующего
содержания:


      exx
      out (c),d   ;или out (c),d в зависимости от того,
                  ;какой экран надо включить
      ld (hl),h   ;восстанавливаем код #ed команды ldi
                  ;здесь пригодилось то, что иннерлупразмещен по
                  ;адресу #ed00 ;)
      ld l,xx
      ld (hl),#c9 ;ставим новую точку останова
      exx
      ret         ;выходим из точки останова

   Таблица AdrTab содержит адреса для перехода на эти процедурки
и  адреса  выхода из точек останова. Таблица составлена так, что
swapping  экранов  не  происходит  во  время  верхнего и нижнего
бордюра, экономя драгоценные такты.
   После  того, как картинка отрисована в буффере в виде Munk'ов
(сокращение   от   Multicolor   Chunk,   придуманное   мной  для
обозначения  элементов  изображения,  занимающих  один  байт,  и
являющимися  кодом  цвета), надо вывести его (буффер) на экран в
виде  атрибутов.  Это  очень  простая  и шустая операция. Munk'и
имеют  номера,  скажем,  с  #f8 по #ff. В области адресов #f8f8-
#ffff лежит таблица вида:

   #f8f8:  00 01 02 03 04 05 06 07
   #f9f8:  08 ...               0f
... 
   #fff8:  38 39 3a 3b 3c 3d 3e 3f

   Для  повышенной яркости таблица должна содержать числа от #40
до #7f.
   Конверсия Munk'ов в атрибуты выполняется иннерлупом:


;sp-munky buffer 
;de-screen address (attr) 
   rept 32
    pop hl
    ldi
   endr
26 тактов на пару манков.



   Эффект готов. Надеюсь, что кто-нибудь что-то понял.




         One frame multicolor Mandelbrot fractal zoom.

Его  можно  лицезреть  хотя  бы в нашей деме Stellar Contour для
CC'01.  Многие  приняли  его  за  анимацию, думая, что спектруму 
такая  работа не под силу. Оказалось, что при некоторой смекалке
и сноровке, можно сделать и при помощи кода.

Сначала   вкратце   о   самом   алгоритме   рисования   фрактала
Мандельброта:  Есть  у  нас комплексная плоскость (или плоскость 
комплексных чисел).
Что  за комплексная плоскость (или плоскость комплексных чисел)?
Те,  кто  в  курсе,  могут  пропустить  следующую  пару абзацев.
Да  будет  вам  известно,  что  корень  из  отрицательного числа
все-таки  можно  извлечь,  только  вот полученное число будет не
действительным (Real) (1,  2,  5.6523),  а  мнимым (Image). Т.е.
например:

sqrt(-9) = sqrt (-1*9) = sqrt (-1) * sqrt (9). 

Квадратный   корень   из -1   называется   мнимой   единицей   и
обозначается буквой i (в некоторой литературе буквой j).
Значит, корень из -9 равен:

   sqrt (-1)*sqrt(9) = i*3.

Комплексным  называется  число  Z  =  A  +  i*B,  где  A  и  B -
действительные  числа,  i - мнимая  единица. В данном случае A - 
действительная   часть (обозначается  Re(Z)),  B - мнимая  часть 
(обозначается  Im(Z)).  Комплексная плоскость - это плоскоть, пo
горизонтальной    оси   которой   откладывается   действительная
составляющая  комплексного  числа,  а  по вертикальной - мнимая.
Например,  комплексное  число  вида  Z  = 3 + 5*i на комплексной
плоскости    будет   являться   точкой   с   координатами (3;5).
   Поскольку  комплексные  числа  являются  числами,  то для них
определены арифметические (и не только операции). Нас интересуют
в первую очередь операции сложения и возведения в квадрат:

Сложение:

  C1 = A + i*B  ;первое число
  C2 = X + i*Y  ;второе число
  C3 = C1 + C2 = A+X + i*(B+Y) ; т.е.    действительные    числа
складываются отдельно, мнимые - отдельно.

Возведение в квадрат:

  (A + i*B)^2 = A^2 + 2*A*i*B + i^2*B^2 = (с  учетом  того,  что
i^2=-1) = A^2 - B^2  +  i*2*A*B

Каждое   комплексное   число   характеризуется   своим  МОДУЛЕМ,
действительнынм   числом,   равным   его  расстоянию  до  начала
координат:

R = |Z| = sqrt ((Re(Z))^2 + (Im(Z))^2) 

Так,  с  компл.  плоскотью  разобрались,  осталось разобраться с
алгоритмом  рисования  фрактала  Мандельброта.  Итак, есть у нас
плоскость  комплексных  чисел,  каждая  точка которой окрашена в
определенный  цвет.  Совокоупность этих точек как раз и образует
фрактал   Мандельброта.  Как  определить  цвет  точки,  зная  ее
координаты? Вот так:

C  =  X + i*Y - комплексное число, или, грубо говоря, наша точка 
на плоскости с координатами (X,Y)

Есть  у  нас некое комплексное число Z, изначально равное 0 (или
0 + i*0).
Так   вот,  вычисляем  в  цикле  следующую  рекурентную  формулу

Z(k) = (Z(k-1))^2 + C 

до  тех  пор,  пока  модуль  Z(k) не станет очень большим числом
(порядка   10E100)  либо  пока,  цикл  не  выполнится  некоторое
количество  итераций (порядка  100-10000).  От того, сколько раз
выполнился цикл, будет зависет цвет нашей точке.
   Программно можно реализовать примерно так:

на входе:

X0,Y0 - координаты  точки,  соответствующей верхнему левому углу 
экрана в компл. плоскости.
SCALE - масштаб. (чем меньше, тем больше степень увеличения). 
SCRX,SCRY - размеры окна, в которое будет рисоваться фрактал. 

double yy = Y0;   //координата Y верхнего угла экрана
                  //в компл. плоскости

for (int Y = 0;   //цикл по строкам
     Y<SCRY;
     Y++)
{
   double xx = X0;   //координата Y верхнего угла экрана
                     //в компл. плоскости

   for (int X = 0;   //цикл по столбцам
        X<SCRX;
        X++)
   {
      double ReZ = 0;   //начальные значения
      double ImZ = 0;   //действительных и мнимых
      double ReC = 0;   //частей компл. числа
      double ImC = 0;   //равны нулю

      int color = MAX_COUNT;  //цвет точки.

      double Re2 = ReZ * ReZ; //нужно для оптимизации рассчетов
      double Im2 = ImZ * ImZ;

      do
      {
         //след. 4 строки выполняют рассчет той самой
         //итерационной формулы Z(k) = Z(k-1)^2 + C
         ReC = Re2 -  Im2  +  xx;
         ImC = 2 * ReZ * ImZ  +  yy;
         ReZ = ReC;
         ImZ = ImC;

         //перерассчитываем квадраты действительной и мнимой
         //частей
         double Re2 = ReZ * ReZ;
         double Im2 = ImZ * ImZ;

         //уменьшаем номер цвета
         color--;

         //делаем пока не превысили максимально допустимое
         //количество итераций или пока наша точка не
         //улетела в "бесконечность"
      } while (color>0) && (Re2 + Im2  <  1e100);

      PutPixel (X,Y,color);   //рисуем точку в буффер
   }
}

Все   бы  замечательно,  только  вот  даннаа  программа,  будучи
запущенной  на  Pentium-233,  будет рисовать в окошке 128*64 в 8
цветах  каждый  фрейм  где-то  по  полсекунды. Что уж говорить о
нашем  бедняжке Спекки :(. Однако все не так плохо, как кажется.
Первое, что могло бы прийти в голову, так это поставить париться
писюк минут на 5, чтобы тот рассчитал нам несколько сотен кадров
размером,  скажем  64*32,  а мы потом уж их на спекки как-нибудь
нарисуем. Причем можно применить дельта-паковку (хранится только
разность  соседних  кадров,  остальное  остается без изменения).
Данные  хранятся  следующим  образом:  сначала идет поток битов,
каждый установленный в единицу бит которого сигнализирует о том,
что  соответствующий  ему  байт аттрибутов (мы же в мультиколоре
делаем)  нужно  поменять, а сброшенный в ноль говорит о том, что
надо его оставить без изменения.

         rl e           ;8
         jr nc,pausa0   ;15/20
         ld a,(hl)      ;22
         ld (bc),a      ;29
         inc l,c        ;33
         jr next1       ;45
pausa0:  or (hl)        ;27 
         or (hl)        ;34
         or (hl)        ;41
         nop
next1:   .... 

Итого  41 такт на 1 байт. На строку из 32 байт уходит около 1300
тактов.  Но,  так  как  нам  надо  держать мультиколор, придется
сделать  в конце строки задержку до 1792 тактов (за это время на
пентагоне успевает вывестись на экран 8 строк).

Все  бы  хорошо,  только вот сжать кадр сильнее, чем в 8 раз, не
получится,   а  иные  способы  паковки  для  мультиколора  очень
проблематичны.  Реально  же кадр будет сжиматься где-то раза в 4
или  в  5,  что  при  размере фрейм-буффера 64*32 манка составит
около  250  байт  на  фрейм.  Выходит,  что на каких-то 5 секунд
зуминга  у нас уйдет свыше 60 килобайт ОЗУ. Учитывая, что демо -
это,   прежде   всего,   демонстрация  возможностей  компьютера,
получается,  что  на  спеке  только  галимую  аниму по несколько
секунд   крутить.  Поэтому  я  решительно  отказался  от  такого
леймового способа реализации фрактального зума.

   Поняв,  что  считать фрактал в реалтайме на Спектруме - идея,
конечно, геройская, однако никто на пати ждать не будет 5 минут,
пока  наш  спекки  геройски  отрендерит очередной кадр, пришлось
поступить  хитро и не без помощи пц. Так как саундтрек в Stellar
Contour  идет  с  3 темпом, а под зуминг планировалось отвести 4 
паттерна  по  64  ноты (768  интов),  то было решено реализовать
эффект следующим образом:
   Я   при  помощи  подобной  проги  отрендерил  на  пц  27  фаз
фрактального  зума,  каждая  из  которых являет собой увеличение
одной  и  той  же  области  фрактала  в  2  раза  большее, чем в
предыдущей  фазе.  Каждый  кадр  был  отрендерен размером 128*64
(вывод  планировалось  производить  в  окно 60*32) в 8 цветов, и
занимал,   соответственно   4096   байт.   Алгоритм   такой:  на
прерываниях  висит  процедура,  которая  плавно (за  28  кадров)
увеличивает (прямо на экран, без всяких дополнительных буфферов)
текущую  фазу изображения фрактала от двухкрантого уменьшения до
нормальных   размеров,   в   то   время   как   в  другой  буфер
перекидывается  следующая фаза. Идея хорошая, однако 4k * 27 фаз
- это  108 килобайт! Хуже, чем в случае с анимой. Решение пришло
быстро - хранить   в   памяти   эти   27   промежуточных  фаз  в
запакованном   виде,   и   распаковывать  их  во  время  зуминга
предыдущей  фазы.  Хе-хе,  ловко  придумано.  Вот  только зуминг
съедает  около  60  тысяч  тактов,  оставляя свободными около 11
тысяч. 11 тысяч тактов * 28 интов = около 300 тысяч тактов, т.е.
грубо  говоря я должен успеть распаковать 4 килобайта за 4 инта!
Хруст  и  хрум  не  годились  по  причине недостаточной скорости
распаковки.  Поэтому  пришлось  написать  собственный паковщий и
распаковщик,  которые  сочетали  бы  приличную  степень сжатия и
необходимую мне скорость распаковки. Учитывая, характер пакуемых
данных (байты  от  0  до  63),  было  решено написать упаковщик,
заточенный  под паковку именно таких данных. Алгоритм распаковки
(по нему, кстати, становится ясным алгоритм паковки):

*  коды с #00 по #3f: просто записываем этот байт. 

*  коды  с  #40  по  #bf:  например,  попаллось число #ad, тогда 
записываем #0d+2=15 байт с кодом #36 (inc = #а-4=6, paper = 6)

*  коды  с  #c0  по  #cf: повторяем последний распакованный байт 
(n-#be) раз.

*  коды  с  #d0  по  #fe: перекидываем n - #cd байт следующие из 
входного  потока,  хранящиеся  упакованными  по 6 бит. Позволяет
экономить по 2 бита на одном непакующемся байте

*  код #ff - признак конца блока. 

Паковщик,  написанный мной на некоторых фреймах давал результаты
даже  лучшие,  чем  hrust 1.3 (естественно сравнение проводилось
без  учета  длин  распаковщиков). Кстати, сжимал он каждый фрейм
быстрее, чем за секунду. Вот что значит паковщик, заточенный под
сжатие  конкретного  типа  данных. В моем случае - это 8 цветные
текстуры.     Распаковщик,     естественно,     укладывался    в
ограничительные рамки с небольшим запасом.

В   результате,  выходные  данные  стали  занимать  около  28-29
килобайт  вместо  108.  После  сжатия  Хрустом  уже запакованных
данных удалось выиграть около килобайта.

Посчитаем теперь общий коэффициент сжатия:
За  время  своей  работы  генерится  28*27=756  кадров  размером
30*32=960  байт.  Т.е.  700  с лишним килобайт. Занимает это все 
хозяйство около 30 килобайт. Налицо сжатие где-то в 24 раза.

Назвать  этот эффект анимацией или нет?  Ежу понятно, что хоть в 
названии  и  содержится  слово  Fractal Zoom, расчет фрактала не
идет  вообще. Зато зуминг реалтаймовый. Ну а те промежуточные 27
кадров из 756 - хотите считайте анимацией, хотите - не считайте.

Теперь  пару слов о зуминге. Тут тоже пришлось придумать (именно
придумать,  а  не  с3.1415здить откуда-нибудь) алгоритм шустрого
увеличения  битмапа.  Особенность  первая: он зумит изображение,
хранящееся  в  уплотненном  виде (2 munk'а в одном байте) причем
сразу  в  атрибуты (тоже  уплотненный  формат). Возникает задача
быстрого  перекодирования туда и обратно. Я решил эту проблему с
помощью  таблиц,  которые  позволяют извлекать отдельный munk из
байта  из  источника  и  перемещать  его  либо  в  левую, либо в
правую половину байта приемника.

               TBL2L     TBL2R    TBR2L   TBR2R 
              ┌──┬──┐  ┌──┬──┐  ┌──┬──┐  ┌──┬──┐ 
              │L │R │  │L │R │  │L │R │  │L │R │ 
              └┬─┴──┘  └┬─┴──┘  └──┴┬─┘  └──┴┬─┘ 
               │        │           │        │
               │        └──┐     ┌──┘        │
               │           │     │           │
               V           V     V           V
              ┌──┬──┐  ┌──┬──┐  ┌──┬──┐  ┌──┬──┐ 
              │L │  │  │  │R │  │L │  │  │  │R │ 
              └──┴──┘  └──┴──┘  └──┴──┘  └──┴──┘ 


Для  повышения  скорости, я продублировал одну из этих таблиц, а
сами таблицы разместил в памяти следующим образом

TBL2R  equ xxxx 
TBL2L  equ TBL2R + #100 
TBR2R  equ TBL2L + #100 
TBR2L  equ TBR2R + #100 
TBL2R_ equ TBR2L + #100 

Иннерлуп   для  каждой  фазы  скейлинга  пришлось  раздекрянчить
заранее  на  всю  строку.  Например  иннерлуп для увеличения в 1
раз выглядит примерно так:

      pop de         ;берем 2 байта изображения
      ld l,e
      ld h,TBL2L/256
      ld a,(hl)      ;извлекаем из левой половины байта в левую
      inc h          ;move to TBR2R
      or (hl)        ;объединяем с правой половиной байта
      ld (bc),a
      inc c
      ld l,d
      ld h,TBL2L/256
      ld a,(hl)
      inc h          ;move to TBR2R
      or (hl)
      ld (bc),a
      inc c

Естественно,  в  конце  каждой  строки  необходимо предусмотреть
задержку, чтобы весь иннерлуп выполнялся ровно 1792 такта.

Вот. Раскрыт секрет еще одного эффекта.



                        Multicolor Doom.

   Ну, Doom - это громко сказано. Скорее всего, Wolf.
   Этот эффект - моя гордость. Еще после CC'000 у меня была идея
реализовать   что-нибудь   в   мультиколоре,  на  первый  взгляд
нереализуемое  в  нем. И вот, затратив на это дело больше месяца
кодинга,    я   написал   этот   эффект.   Краткие   технические
характеристики:

Разрешение: 64*32 
Количество цветов: 8 multicolor 
Frames per second: 16.7 (!). Один фрейм рендерится за 3 инта. 
Размер карты: 32*32 
Размер текстуры: 16*32 
Число текстур: 32 
Дополнительные возможности: была возможность пустить еще по 
нижнему бордеру скрол типа RAGE'овского. Однако из-за нехватки
времени пришлось на скролл забить. Тем более, что скролл не
совсем вяжется с doom'ом. Ну да и бог с ним.

Сразу  скажу,  что  этот эффект полностью реалтаймовый. Никакого
прекалкулейтинга  изображения  не проводится. Для доказательства
этого  я  уже в Питере откомпилировал этот эффект добавив к нему
управление   от  клавиатуры  и  добавил  полученный  суррогат  в
качестве  бонуса  к деме ;). Так что все неверующие могут просто
порулиться по карте с помощью кнопок Q,A,O,P,L,Enter.

Применены следующие "извраты":
1. Реалтаймовая трассировка лучей. 
2. Реалтаймовый скейлинг текстур. 
3. Внутри иннерлупа мультиколора применяется процедура умножения 
байта на слово.
4.   Иннерлуп   содержит  кучу  ветвлений.  Время  каждой  ветви 
просчитывалось вручную.
5. Все вычисления, естественно, проводятся параллельно с выводом 
мультиколора.

Итак, общая идея эффекта. 
Сразу  скажу,  у  меня  применен  не совсем корректный алгоритм.
На  самом  деле его делают без трассировки лучей. Во-первых, это
несколько быстрее, а, во-вторых, позволяет избежать погрешностей
вычислений.   Однако,  в  мультиколоре  реализовать  способ  без
трассировки параллельно с выводом мультиколора невозможно.

Итак, суть трассировки: 


У   нас   есть   центр   камеры (обозначен   1
символом "о"), направление камеры (ось z).
Плоскость  экрана: (обозначена  через AB).
Плоскость экрана разбивается на 64 столбца
(каждый столбец шириной в 1 munk). Назовем
их    кластерами (мне   пофиг,   как   они
называются,    я    буду    называть    их
кластерами).   Проводится  луч  из  центра 
камеры    через    каждый    кластер    до
столкновения  со  стенкой (на  рисунке  это луч oD) либо пока не
превысим  максимальную  длину  луча (у  меня  это,  на сколько я
помню,   это   7   блоков   карты).  По  координате  пересечения
определяется  какой  столбец  в  текстуре  надо отрисовать, а по
длине  проекции  луча  на  ось  направления  определяется высота
данного столбца. Осталось только отрисовать его в буффере.

Хе-хе,  все  не так-то просто, как хотелось бы. Если подходить к
этому  делу напрямик, то скорость будет ОЧЕНЬ мала. Во-первых, в
карте я перемещаюсь не попиксельно, а сразу поблочно. Во-вторых,
все  смещения и коэффициенты для каждого угла поворота (0..pi/4)
и каждого кластера рассчитываются заранее (отсюда пауза где-то в
10  секунд  при  декрянчинге).  В  третьих, для нахождения точки
пересечения  применяется  процедура  умножения  байта  на слово,
которую  пришлось  раздекрянчить  256 раз, чтобы она выполнялась
всегда  за 204 такта (вместе с CALL и RET). Кроме того, пришлось
также  раздекрянчить  процедуры  скейлинга текстур и трассировки
лучей.   В  результате,  размер  исходников  составил  около  90
килобайт в формате ZXAsm. Наверное, это неправильно. Но написать
и  отладить  90  килобайт  исходников  однотипных  процедур  мне
показалоь  проще,  чем  написать  и  отладить декрянчер, который
сам  бы  сделал  эту  работу.  Ладно,  главное,  что работает и,
вроде, не глючит.
   Описывать  здесь  все  тонкости  не хочется. Поэтому изучайте
исходник.

                    Free Directional Tunnel.

   Данную  байду  можно  наблюдать  в  деме  Dogma  by  Eternity
Industry. Скажем  так, я был восхищен мужеством Сайруса, который 
реализовал  этот эффект на Спектруме. Однако, я считаю, что этот
эффект  всё  же  не  для  Спекки, поскольку при реализации его в
чанках  будут  видны  погрешности  вычислений,  поэтому в данной
статье  я  ограничусь  только  самим  алгоритмом,  который можно
просто  реализовать на более мощной машине, не особо изголяясь с
ассемблером.

   Данный  эффект  реализуется  по  принципу  трассировки лучей,
проведенных из фокуса камеры до пересечения со стенкой туннеля.
   Итак,  туннель представляет собой обычный бесконечный цилиндр
радиуса  R0.  Для  упрощения  формул  положим,  что камера может
передвигаться   только   по   прямой,  являющейся  осью  данного
цилиндра:

===========P================================================== 
^         / 
│        /                ^X или Y 
│       /                 │ 
│R0    /                  │ 
│    О*                   └────>Z 
 
 
                           U
                         ────────>
============================================================== 

   Текстура   накладывается   на   цилиндр   следующим  образом:
координата  U  в текстуре изменяется так же, как и Z, т.е. вдоль
стенок туннеля. Координата V в текстуре изменяетс равномерно по
окружности туннеля.

   В  данном  случае  камера может перемещаться только по оси Z.
Итак,  необходимо  найти  точку  пересечения  луча  OP(x,y,z) со
стенкой туннеля.

Координата Zi точки пересечения находится из условия:

R1   z            z * R0 
-- = --   => Zi = ------ 
R0   Zi             R1 

   Здесь: R1 = sqrt (x^2+y^2).

   Зная Zi можн определить U:
   U  =  Zi*k  + U0, здесь k - какой-то коэффициент, от которого
зависит  то,  как  растянута  текстура  вдоль  оси  Z.  Можно, в
принципе,  принять  его  равным  1,  U0 - базовая  координата  в
текстуре, меняя которую можно создать иллюзию перемещения камеры
по оси туннеля.

   Координата   V  определяется  из  условия,  что  она  линейно
изменяется   по   окружности   туннеля.  Т.е.  зная  угол  между
вертикалью и вектором (x,y,0) можно вычислить координату V:

     arctan2(x,y)*N
V = ---------------- 
         2*PI

   Функция arctan2(x,y) возвращает значение арктангенса величины
(x/y), если y<>0, и 0 в противном случае. 
   Если текстура имеет размеры Un x Vn, то N = Vn.

   Так,  формулы для нахождения координат в текстуре у нас есть,
осталось  определиться  что с ними делать. Надеюсь, что читатель
знает  формулы  вращения  точки вокруг осей. Если нет, на всякий
случай напомню:

Вокруг оси x:

x' = x 
y' = -sa*y + ca*z 
z' = sa*z + ca*y 

Вокруг оси y:

x' = -sa*x + ca*z 
y' = y 
z' = sa*z + ca*x 

Вокруг оси z:

x' = -sa*x + ca*y 
y' = sa*y + ca*x 
z' = z 

x',y',z' - координаты точни (x,y,z) после вращения. 
sa - синус угла поворота вокруг данной оси 
ca - косинус угла поворота вокруг данной оси 

Камера у нас характеризуется следующими параметрами:
SX - ширина экрана в пикселях 
SY - высота экрана в пикселях 
SC - расстояние  от  фокуса камеры до плоскости экрана. От этого 
параметра зависит угол обзора камеры. Он равен:

angle = arctan((SX/2)/SC)*360/PI - угол обзора камеры по X. 

   Обычно  принимат Scale равным SX/2. В этом случае угол обзора
равен  90  градусам. При угле обзора в 120-130 градусов и больше
становится заметна неестественная перспектива изображения.

   Так,  теперь  знаем  параметры  камеры и формулы 3D вращения.
Теперь нам достаточно повернуть всего лишь 3 точки камеры:

ULC(-sx/2,-sy/2,SC) - верхний левый угол экрана 
URC(sx/2, -sy/2,SC) - верхний правый угол экрана 
DLC(sx/2,  sy/2,SC) - нижний левый угол экрана 

   После поворота получим точки:

ULC'(x0,y0,z0) 
URC'(x1,y1,z1) 
DLC'(x2,y2,z2) 

   Зная их, можем найти 2 вектора:

VX=(URC'-ULC')/SX=((x1-x0)/SX,(y1-y0)/SX,(z1-z0)/SX) 
VY=(DLC'-ULC')/SY=((x2-x0)/SY,(y2-y0)/SY,(z2-z0)/SY) 

VX - вектор,   на  который  смещается  3д  координата  точки  на 
повернутой  плоскости  экрана  при  смещении  на один пиксель по
горизонтали
VY - то же самое, но по вертикали. 

   Зачем  нам  эти  вектора?   А затем, что зная их, мы можем по
найденным  3-м  точкам запросто найти координаты каждого пикселя
повернутой  плоскости  экрана,  а  это  есть  ни  что  иное, как
координата  луча, проведенного из фокуса камера в данный пиксель
экрана.  Вот  для  него-то  и  находим  по  формулам  координаты
пересечения со стенкой туннеля.

   Конечно,   честно   обсчитывать   каждый  пиксель  экрана  по
вышеупомянутым  формулам - очень  кропотливое  занятие  даже для
довольно  мощных  машин,  не говоря уже о Спекки, поэтому обычно
расчитывают по этим формулам координаты в текстуре для каждой 8-
ой (или  16-ой)  точки  каждой  8-ой (или  16-ой) строки, т.е. в
узлах  сетки,  а  потом  линейно их интерполируем внутри каждого
квадратика 8*8 (или 16*16). Таким образом можн достичь заметного
выигрыша в скорости при довольно сносном качестве изображения.

   Похожим  образом,  кстати,  можно  создать  и эффект вращения
камеры  внутри сферы, только формулы для трассировки лучей будут
несколько  иными.  Предлагаю читателю самому их вывести, а также
усовершенствовать алгоритмы трассировки лучей внутри туннеля для
того,  чтобы  камера могла находиться не только на его оси, но в
любой точке внутри туннеля.

   Интересующимся  3d  графикой  могу  порекомендовать  почитать
Demo.Design  3d  programming  FAQ,  который  когда-то можно было 
найти  на  www.enlight.ru.  Там изложен тот базовый минимум, без
знания  и  понимания  которого  нормально работать с 3д графикой
довольно проблематично.



Другие статьи номера:

Editorial - я с планеты Майга.

Editorial - две триады кристая: "...Однако я люблю крик2! Он получился немного наивным, возможно, абсурдным, но для меня он характерен прежде всего теплотой..."

Editorial - индустриальные капли бархатного сока мозговых извилин: "Два дня назад я вернулся с cc1 и с тех пор меня гложет что-то непонятное, необъяснимое, неподдающееся пониманию..."

Editorial - make a clean breast of it: "что касается моей музыки здесь - то я хотел чтобы она дарила людям душевное тепло, то, которое у меня было в детстве и то, которое я сумел сохранить до настоящего дня..."

Editorial - Unbeliever: "С трудом я вспоминаю о каких-либо шоковых программных продуктах последнего времени. Очередная версия Best View, быстро развивающийся BGE, HRiP и AcEditor, это наверное все, что достойно внимания..."

Крик - charts index: "я наконец-то решил посчитать все пришедшие чарты. Да уж, не густо - всего 18 vote-листов, но зато какие люди голосовали!"

Крик - charts результаты: "Безумная работа, скажу я вам! Целый день в моей голове крутятся одни чертовы цифры, целый день я считал, изучал, исправлял, стрелял, убивал..."

Крик - credits.

Zoom - новости: создатели газеты Абзац делают игру, Phantom Family cвалили на pc, новый состав группы 4D, Вячеслав Медноногов потерян для спектрума окончательно, Davos забил на спектрум, Lynx работает над HTML вьювером, у группы Sage "полный негативизм", Kvazar прекращает выпуск газеты "Полесье" и т.д.

Zoom - интервью с Baze/3sc.

Zoom - Wlodek Balck о ситуации со Спектрумом в Москве.

Scene - Internet vs Speccy: победила дружба! "Чем же так привлекателен интернет для создания новых проектов посвященных нашему любимому компьютеру?"

Scene - Insanity Zer0: "Реальных демомейкеров за всю историю спектрума - не больше десятка имен, с натяжкой можно назвать двадцать! Геймемйкеров - еще меньше..."

Scene - leet?! Определения элитного "сценера".

Scene - плацебоги: "placebo: вы плацебоги, мы вас любим".

Scene - каннибализм на сцене: "лагерь спектрума разбит на две тусовки: западную, европейскую сцену и русскую..."

Pro-обзор - press.scene.review: Kosme 0, Psyhoz 5, Body 2f, Plutonium 19, Черная Ворона 6, Subliminal Extacy 3, IzhNews 0C, ZX-time 2, Lamergy 1, MSF 22, Стекло.

Pro-обзор - cc01.gfx заложник пикселей: "Я ждал этого компо, честно признаюсь, без каких-либо особых переживаний..."

Pro-обзор - CC1 music или 'дело было вечером...' - Gas 13 vs Nik-O.

Pro-обзор - Nuotrauka music compo review: "Написание обзоров графики с прошедших party уже стало хорошей традицией, но почему-то не получило большого развития в музыке..."

Pro-обзор - Nuotrauka GFX compo review: "наслушавшись мнений художников-техников, очевидно небезынтересно будет узнать мнение тех, кто видит работы под несколько другим углом зрения"

Pro-обзор - Nuotrauka'tm compo stuff review: "Обзоры - штука довольно сложная, потому что говорить не лицеприятные вещи людям, с которыми ты в хороших дружеских отношениях, сложно всегда"...

Pro-обзор - Millennium'1901 Demoparty ... Обзор графики от Ice'Di.

Pro-обзор - phat1 gfx compo review.

Pro-обзор - phat0 gfx compo review: "Графика в этот раз? Не очень. Помнится, в прошлый раз было лучше"

Pro-обзор - insanity#9 review: "Этот номер хотя и не был изначально ожидаем мною как скандальный, но после выхода таковым стал. Лично я остался если не избитым до смерти, то по крайней мере покалеченным"

Demoparty - chaos construstions'oo1 report: "в Петербурге царила просто непередаваемая атмосфера духа сцены, дружбы, сплочённости, и так хорошо мне, наверное, никогда ещё не было"

Demoparty - Chaos Constructions 001: Party было... было rulez! "возвратившись домой с CC'001, я не могу поверить в то, что все происходило наяву"

Demoparty - Megus: Отчет о demoparty Chaos Constructions'2001.

Demoparty - nuotrauka'tm details: "Так получилось, что я стал одним из органайзеров этой парти, а потому и отмазываться от части придется мне"

Interview - интервью с poisoned CyberJack/Triebkraft (часть 1).

Interview - интервью с poisoned CyberJack/Triebkraft (часть 2).

Interview - интервью c Blade, Steelzer, Ice'di / Ttriumph.

Interview - гоны за сцену: "почему Chasm/CPU урод, и кто вообще решил, что он - урод?"

Tutorials - coding: реализация эффекта "Mirror rotator" (статья рассчитана на довольно подготовленного демо-кодера).

Tutorials - ascii scene: "Ascii сцена... Как же я тебя безумно люблю! Наверное, ты как никакая другая сцена смогла зародиться так рано"

Tutorials - под прессом прессы: "Когда тебя учат писать, рассказывая о литературных тонкостях и приемах, это отлично, это здорово! Когда у тебя кроме этих познаний нет ничего, нет базовых понятий, это куда хуже"

Сладкие - index.

Сладкие - одиночество.

Сладкие - son.

Сладкие - треугольный кабинет.

Сладкие - три испачканных розы.

Сладкие - сам.

Сладкие - вася.

Сладкие - осуждение.

Сладкие - добро.

Сладкие - приход.

Сладкие - алюминиевая ложка.

Сладкие - ботинок.

Сладкие - внезапность.

Сладкие - ДРАМА13.

Сладкие - холодильник заснеженных идеалов.

Сладкие - моя оля.

Иной - index.

Иной - dnewnik-ol.

Иной - e-dnewnik-oz.

Иной - скеси-ссака.

Иной - скеси-ссака (2).

Иной - скеси-ссака (3).

Иной - скеси-ссака (4) или кристов любит роню.

Иной - его губы.

Иной - Пойми сигу.

Иной - Чем пахнет сига?.

Иной - Дым-шептун.

Биться - безумные оправдания: "Думаю, ты еще не знаешь, что в insanity#9 бОльшая часть материалов - выдержки из личной переписки автора с различными сценерами"

Биться - Трахальщик Frunze: "Увидели мы значит в сетях рекламу от "товарища Frunze", касающуюся видео с CC'999. Итак, подкопив некоторый капитал в размере 100 р. заказали видео_кассету"

Мозги - skene anexx.

Мозги - dick is out of my pants!.

Мозги - сладкие члены.

Sobaka.ру - postbox: "собственно, вот и оно, то, ради чего отчасти и делался [крик - ваши отзывы, эмоции и даже Зло. Писем пришло много..."

Миска - "Самое прекрасное в том, что сюда ты можешь писать даже не зная ничего о сцене!"

Миска - Тривиальное чтиво: "Декларации демократического общества сами по себе как обещания ничeго не стоят. У нас привыкли верить красивым словам, но в поступки верить почему то не принято"

Миска - ОС будущего для SPECCY.

Миска - "Ты - слизняк. Да, да, это так, не нужно отрицательно мотать головой и отмазываться тупыми фразами. Ты дохляк! Ты маструбируешь на голых девок из zx-stag'а"

Миска - About girls.

Лоzhение - index: "Возможно, ты не оценишь то, как я сократил слово "приложение", но..."

Лоzhение - about ACEdit0.59.

Лоzheние - Группа CRUSHERS представляет свою мини игру: Flintstones: Fred in the magic wood.

Лоzheние - [В]арга lit packs 13, 14, 15, 16 and 17: "Я безумно тебе завидую - ведь у тебя все еще впереди, ведь тебе еще только предстоит окунуться в сказочно прекрасный мир, созданный талантливыми писателями из команды [В]арга".


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Реклама - реклама и объявления.
Demo Party - информация по демопарти CC999.999.
Про людей - одна история из жизни спектрумиста.

В этот день...   4 июня