[Перевод] Трассировка лучей в реальном времени в 1 КБ кода
PENTRACE
Всё началось в 1994 году, когда я прочитал в Dr. Dobbs Journal несколько интересных статей о FPU (математическом сопроцессоре) нового процессора Pentium. Я пришёл к пониманию того, что численная производительность Pentium очень чувствительна к использованию и порядку команд FPU, и что дополнительными командами FXCH можно значительно увеличить скорость выполнения.
В то время при необходимости трассировки сцены лучами для получения результата требовались часы или даже дни. Я решил написать трассировщик лучей, похожий на POV-Ray или BOB, только на языке ассемблера, чтобы код при этом был сильно оптимизирован под FPU процессора Pentium. Это был «Pentrace», мой дипломный проект в колледже.
CHROME
Существовала очень известная и популярная анимация под названием Chrome, созданная трассировкой лучей. В основном она распространялась среди пользователей Amiga. Я решил, что будет круто показать ту же анимацию зрителям демопати Assembly, но всего в 4 КБ!
Интро Chrome на 4 КБ заняло в 1995 году четвёртое из 44 мест.
CHROME 2
Chrome я заканчивал уже на пати, прямо перед дедлайном, а на следующий год я первым бросил гибкий диск в коробку участников соревнования. Это интро стало первым продуктом с элементами трассировки лучей в реальном времени, только в очень низком разрешении, всего 144×102 пикселя.
Однако я шёл туда за победой! К сожалению, интро не демонстрировали в категории compo, потому что организаторы потеряли мою дискету и его показали только позже, между двумя блоками compo.
В конечном итоге, в 1996 году интро Chrome2 в категории 4kb заняло пятое место, но на следующей неделе мой продукт был первым по скачиваниям с Hornet Archive.
CODER-L
До 2001 года я управлял очень успешным венгерским списком рассылки для кодеров. В этом списке CODER-L было много обсуждений теоретических возможностей трассировки лучей в реальном времени.
Позже на основе этих обсуждений появились такие творения, как Slumpism by Pathos (при выполнении трассировки исходящих из камеры лучей он проводил перед каждой растровой строкой тест пересечения плоскости камеры и объекта) или Heaven Seven by Exceed (использовал для лучей камеры адаптивное субсэмплирование).
Однако тем временем, в конце 90-х, я потерял интерес к демосцене и мотивацию…
COLORFUL
Вернулся я в 2016 году, поучаствовав в qbparty. Меня поразило то, что в демосцене по-прежнему оставалось место для кодинга на ассемблере для DOS, поэтому я начал публиковать 256-байтные интро.
Однако с прежних времён аппаратная среда сильно изменилась, и после тестирования на многих современных компьютерах я понял, что единственным вариантом для трассировщика лучей остаётся видеорежим 640×480 c 32 битным цветом (с банкируемой памятью).
Моим первым 256-байтным интро в режиме HiRes стало Colorful (заняло второе место на Function 2016).
256B SEMINAR
В 2017 году я представил на Function свой движок трассировки лучей с покеболами. В нём использовалось адаптивное субсэмплирование, однако только в горизонтальном направлении из-за ужасного переключения банков в видеопамяти. И да, он был довольно быстрым.
SEASHELL
В этом демо я впервые использовал для лучей камеры ортогональную проекцию. Она выглядела достаточно красивой, была быстрой и занимала малый объём кода.
256-байтное интро Seashell заняло первое место на Riverwash 2017.
TCTRONIC
Мы нарушили правила compo на Function 2017. В нашем интро была музыка PWM PC-Speaker, воспроизводящая хорошо известный байтбит.
256-байтное интро TCTRONIC заняло второе место на демопати Function.
Plasmifier Cover 256b
Первое 256-байтное интро, имеющее музыку с программным синтезатором вместо просто байтбита.
Plasmifier Cover заняло второе место на Chaos Constructions 2018.
Благодарю Provod и Frag за то, что показали мне малозатратную огибающую IMUL xx, xx,-1 на стриме ikubun. И спасибо Gargaj за то, что обратил моё внимание на мастеринг в своей речи на Assembly.
Balls Harmony
HellMood открыл интересную тему о комбинировании записи, которое может ускорить запись в видеопамять. Особенно от этого выигрывали интро в True color.
При комбинировании записи я мог трассировать каждый пиксель экрана в своём интро (однако в эмуляторе это так не работало).
256-байтное интро Balls Harmony заняло второе место на Function 2019.
SSE 4.1
С Kuemmel мы начали код-гольфинг демо разработчика Frigo для Function (Space Fungus). Мы попытались ускорить его с помощью команд SSE. И запись в видеопамять при помощи MOVAPS [ES: DI], XMM7 оказалась даже быстрее, чем комбинирование записи.
Кроме того, Kuemmel из темы на Tiny Intro Toolbox узнал, насколько легко ограничивать значения цветов при помощи команд SSE.
SSE настолько крутое, там можно нормализовать векторы без SQRT и DIV!
Технические подробности
HiRes TrueColor
Наименьшее разрешение TrueColor на любом современном PC — это 640×480 с 32 битами на пиксель. Можно легко задать его при помощи VESA BIOS.
MOV BX,112H MOV AX,4F02H INT 10H
Однако номер видеорежима в разных VGA-картах может различаться. Чаще всего используется номер 112H. Он работает на nVidia, Intel, DosBox и т.п., но не на ATI. В VGA-картах ATI/AMD он устанавливает режим 640×480x24 бит. Поэтому в этом случае нужен номер 121H.
К сожалению, в VESA-драйверах виртуальных машин используются ещё более странные номера: VirtualBox — 142H, VMware — 13FH.
Видеопамять
Под DOS самым быстрым способом записи в видеопамять является команда MOVAPS, если её поддерживает процессор. Она может записывать по 16 байт (4 пикселя) за раз.
MOVAPS [ES:DI],XMM7
Чтобы использовать её, нужно собрать 4 пикселя в регистры. Нижние 4 байта XMM2 — это новые пиксельные данные для одного пикселя. Повернув XMM7 влево на 4 байта, мы можем вставить новый пиксель.
SHUFPS XMM7,XMM7,10010011B MOVSS XMM7,XMM2
При вычислении цветовых компонентов пикселя мы получаем значения float. Их нужно преобразовать в integer и ограничить интервалом от 0 и 255. Для этого очень пригождаются команды SSE:
CVTPS2DQ XMM2,XMM2 PACKSSDW XMM2,XMM2 PACKUSWB XMM2,XMM2
Видеопамять VESA high-color упорядочена в банки, поэтому после 4096 операций записи мы должны переключиться на следующий банк.
ADD DI,16 JNZ .4 PUSHA SUB BX,BX MOV AX,4F05H INT 10H POPA INC DX ; DL: number of memory bank .4:
Адаптивное субсэмплирование
По сути, мы трассируем каждый четвёртый луч из камеры. Во время трассировки я вычисляю байт метки, то есть уникальное значение, зависящее от того, с чем мы пересеклись.
Если байт метки такой же, как и 4 пикселями ранее, то можно выполнить интерполяцию между цветами. Если нет, то нужно оттрасировать больше лучей камеры между двумя пикселями.
INSERTPS XMM7,XMM2,00110000B ; XMM7: insert new color on the top .2: SHUFPS XMM7,XMM7,10010011B ; XMM7: rotate left PAVGB XMM2,XMM7 ; XMM2: averaging the colors MOVSS XMM7,XMM2 ; XMM7: put interpolated color on the bottom CMP [BP+SI],BL ; is it the same stampbyte? LOOPNZ .3 ; if no, then trace the next pixel TEST CL,3 ; was the fourth pixel? JNZ .2 ; if no, then interpolate the next pixel .3: TEST CL,3 ; was the fourth pixel? JNZ .4 ; if no, then skip putpixel CALL putpixel SHUFPS XMM7,XMM7,11111111B ; XMM7: fill by the last color MOV BL,[BP+SI] ; store the stampbyte ADD CX,8 ; go to right by 8 pixels .4: CMP CX,RESX/2+4 ; was it the last pixel in the raw? JNE nextpixel ; if no, then go to the next pixel
То есть нам нужно трассировать больше, чем каждый четвёртый луч из камеры, но в среднем, как мне кажется, значение меньше, чем каждый третий пиксель.
Ортогональная проекция
Испускание лучей камеры выполняется ортогонально к плоскости X-Y (другими словами, параллельно оси Z). Вектор направления всегда равен [0,0,1], а позиция глаза (камеры) является координатами X, Y экрана плюс любое отрицательное значение Z. Если конкретнее, то после корректировки соотношения сторон P равен [+94…-94,-160…+160,-8260].
MOV AX,RESY/2 nextline: MOV CX,-RESX/2+4 nextpixel: PUSHA ; -20:DI SI BP SP BX DX CX AX 1 0 PMOVSXWD XMM6,[BX-8] ; XMM6: P = x,y,1,0 CVTDQ2PS XMM6,XMM6 MOVAPS XMM5,XMM6 MULPS XMM6,[SI] ; *Aspect [SI]=[0.5028877,0.39081812,-8260.683] SHUFPS XMM5,XMM5,11101111B ; XMM5: D = 0,0,1,0
Векторы
Выполнение вычислений с тремя (или четырьмя) векторными координатами одновременно при помощи команд SSE само по себе является ускорением работы. Вот как я хранил следующие векторы в разных регистрах SSE:
;XMM0: temporary #1 ;XMM1: temporary #2 ;XMM2: color coordinates ;XMM3: reflection vector ;XMM4: normal vector ;XMM5: direction vector ;XMM6: point ;XMM7: collector for colors of 4 pixels
Нормализация?
Сегодня наиболее затратными командами являются деление и квадратный корень. При нормализации используются обе эти команды, поэтому я попытался избежать нормализации векторов. Именно поэтому мы испускаем лучи с ортогональной проекцией. Лучи камеры являются единичными векторами.
Отражённые лучи также являются единичными векторами из-за свойства отражения; нам не нужно их нормализовать. Единственными векторами, для которых нормализации нельзя избежать, являются лучи теней. К счастью, существует специализированная команда для вычисления величин, обратных квадратным корням.
MOVAPS XMM0,XMM5 ; XMM5: D = VNORM(D) DPPS XMM0,XMM0,01111111B RSQRTPS XMM0,XMM0 ; instead of SQRTPS XMM0,XMM0 MULPS XMM5,XMM0 ; instead of DIVPS XMM5,XMM0
Примечание: RSQRTPS даёт серьёзный прирост производительности. Однако она ОЧЕНЬ приблизительная: она создаёт результаты с относительной погрешностью менее 1.5×2^-12. Учитывая то, что машинный эпсилон чисел float с одиночной точностью равен 2^-24, можно сказать, что эта аппроксимация имеет примерно половинную точность. Её нельзя использовать для лучей камеры, но она неплоха для лучей теней.
Когда я попытался нормализовать лучи камеры при помощи RSQRTPS, это привело к множественным артефактам в контуре сферы.
Затенение
Единственный источник света — это слишком скучно, поэтому у нас их два. Один источник имеет координаты (255,255,255), а второй противоположен ему и находится в (-255,-255,-255).
Для затенения я использовал модель Фонга. Компонент рассеянного освещения очень прост: dot (normal, shadow)
MOVAPS XMM1,XMM4 ; XMM1: N.S DPPS XMM1,XMM5,01110001B MOVAPS [DI],XMM1 CMP [DI+3],CH JLE @F ; Ambient FADD DWORD [DI] ; Ambient+Diffuse @@:
Компонент зеркального освещения более интересен: dot (reflected, shadow)^2^2^2
DPPS XMM5,XMM3,01110001B ; XMM5: R.S MOVAPS [DI],XMM5 FLD1 FADD DWORD [DI] ; Specular Ambient+Diffuse @@: FMUL ST0,ST0 ; Specular=Specular^2 INC CX JPO @B ; loop x3
Рекурсия
Три уровня рекурсии очень заметны в отражениях, но дополнительные уровни будут пустой тратой ресурсов. Для проверки уровня текущей рекурсии я использовал регистр указателя стека.
CMP SP,-22-2*maxlevel ; Max recursion level = 3 LOOPE Tquit ; JE Tquit + DEC CX MOVAPS XMM5,XMM3 ; D = R FMUL DWORD [SI] ; level/2 0 FILD DWORD [SI] ; big number for min CALL Trace0 Tquit: RETN
На каждом уровне рекурсии я вдвое уменьшал яркость отражённого цвета.
Сцены
Источником вдохновения для первой сцены стала часть интро Chrome2, выполняемая в реальном времени. Но на этот раз сцена вычисляется в полный экран и с красивыми пересечениями.
В парке аттракционов Walt Disney Studios в основном холле наверху магазина вращается три сферы. Мне это очень понравилось.
Из соображений скорости во второй сцене есть только одна шина, состоящая из сфер, остальные — это отражения.
Я уже пытался воссоздать это гипнотическое движение в своём 256-байтном интро, но результат мне не понравился.
Эта трассируемая лучами сцена намного лучше с сохраняющимися цветами и отражениями.
Написание Sizesong
Характеристики платформы
Традиционные платформы с ограниченной музыкой (например, монофонические рингтоны, Amiga mod, General MIDI и т.п.) имеют «высеченные в камне» ограничения: полифонию или набор тонов, но обычно не имеют значительных ограничений на размер данных. В нашем случае, на платформе динамика PC-DOS, справедливо обратное. Мы можем сгенерировать любую волну, нет ограничений на проигрыватель, однако вычисление каждого тона и функции секвенсора отнимает место у визуальных эффектов.
Мысли о кавере
Во-первых, создание кавера хорошо известной песни для ограниченной платформы — это интересная и сложная задача. Если кавер точный, то при прослушивании в нашей голове звучит и оригинал, что усиливает ощущения. С другой стороны, мы не можем изменять партитуру, чтобы выиграть несколько байтов. Мы можем просто вырезать части целиком (например, пропускать строки), убирать инструменты (например, не использовать бас) или упрощать их (например, применять упрощённые ударные). В крайних случаях, наподобие 549Notes, мы не можем пропускать и изменять ничего.
Структура композиции
Песня «I Remember» Deadmau5 и DJ Kaskade — идеальный кандидат на создание sizecode-музыки.
Её аккордовая последовательность достаточно характерна, чтобы представлять целую композицию, поэтому я могу отказаться от вокала. Кроме того, она имеет длину всего в 8 паттернов и содержит повторения:
1 2 R R 3 4 R R
Так как каждый аккорд состоит из 4 тонов, нам нужно хранить 5×4 = 20 нот.
Есть только одна сложность: смена аккорда происходит на четверть раньше ожидаемого, но только в каждом 2 из 4 случаев:
[1 1 1 1] [1 1 1 2] [2 2 2 2] [2 2 2 R] [R R R R] [R R R R] [R R R R] [R R R R] [3 3 3 3] [3 3 3 4] [4 4 4 4] [4 4 4 R] [R R R R] [R R R R] [R R R R] [R R R R]
К счастью, партия ударных довольно простая и повторяющаяся:
[BD HT BD+SN HT] [BD HT BD+SN HT] [BD HT BD+SN HT] etc.
Согласно правилам жанра house, композиция начинается только с ударных, но только на половину повтора. Затем идут четыре полных повтора, с проигрыванием в каждом повторе более долгих нот. На четвёртом повторе с самыми длинными нотами дорожка ударных замолкает. Затем композиция продолжается почти с начала, но пропускает интро только с ударными.
[drums only]
loop point:
[drums + chords - short]
[drums + chords - long]
[drums + chords - longer]
[no drums, only chords - longest]
continue at loop pointАльтернативная версия
Мы попытались связаться с авторами, но нам это не удалось, поэтому у нас нет разрешения на публикацию кавера. Возможно, у нас есть на это право, но правила пати строже, поэтому нам пришлось изменить музыку.
Я хотел внести как можно меньше изменений, поэтому изменил только аккорды, оставив всё остальное неизменным, даже структуру аккордов:
1 2 R R 3 4 R R
Моя основная задача заключалась в создании композиции, как можно больше отличающейся от оригинала, и мне кажется, я справился. Моя версия ярче, счастливее и светлее, и она звучит как рефрен, а не отдельная песня.
Оригинал мне нравится больше; он очень уникален и имеет необычно хорошо сделанную последовательность аккордов, особенно для современной композиции; он напоминает мне о 80-х, золотой эпохе поп-музыки.
Но я не разочарован своей версией; на самом деле, я начинал писать небольшую счастливую композицию, в которой эта тема будет рефреном.
Программный синтезатор PC-Speaker
Сэмпл
Чтобы PC speaker работал наподобие устройства PWM, мы переключили канал 2 PIT в нулевой режим работы («прерывание по счётчику терминала»).
MOV AL,90H OUT 43H,AL
Благодаря этому мы можем выводить 6-битный сэмпл. Значение 0 — это тишина, значение 63 — максимальная громкость.
IRQ: PUSHA MOV AL,2 ; Sample [0...127] SHR AL,1 ; scaled to 6-bit JZ .1 ; zero means pause (no sound) OUT 42H,AL ; out the 6bit sample .1: ... POPA IRET
Темп и ноты
Мы присвоили счётчику таймера значение 68 (позже мы назвали его Divider), потому что хотели получить темп 129 bpm.
MOV AL,68 OUT 40H,AL MOV AL,0 OUT 40H,AL
Тогда частота проигрывателя будет 17,5 кГц.
Hz=105000000/88/Divider,
bpm(low)=Hz*60sec/2/2/2/2/2/2/2/2/2/2/2/2/2/2,
bpm(high)=Hz*60sec/2/2/2/2/2/2/2/2/2/2/2/2/2.
Для проигрывания музыкальных нот нужно умножать несущую волну на постоянные значения. Мы можем вычислять эти значения в зависимости от частот, например, нота A4 (ля четвёртой октавы) вычисляется так: A_4=(32×256*44000/Hz+50)/100.
У меня есть файл inlcude для нот: notes.inc
Ударные
Мы хорошо повеселились с ударными программного синтезатора pc-speaker в выпущенном ранее продукте.
И этот очень простой паттерн ударных (bd — ht — sn/bd — ht) использовался и в другом интро, но с другим темпом: qblove.
Басы ударных реализованы простым делением: постоянное значение делится на время (или счётчик таймера).
KICKDRUM: MOV AX,16128 ; constant value CWD ; extend the value to 2 words MOV CX,8191 ; get some lower bits of AND CX,SI ; the timer counter (SI) INC CX ; avoiding division by zero DIV CX ; get one bit only AND AL,64 ; 0 or 64 will be the volume (the sample)
Сравнивая SN (слева) с BD (справа), можно заметить, что малый барабан намного дольше и более случайный, чем басовый.
Хай-хэту тоже требуется случайный шум, поэтому HT и SN начинаются с одного фрагмента кода.
XCHG AX,DI ; DI: pointer to video memory, which is quite random here :) MUL SI ; SI: the timer counter XCHG AX,DX ; AX: random number depending on time AND AX,32 ; get only one random bit
Аккорды
Один аккорд состоит из четырёх просуммированных нот.
MOV BP,NOTES CHORDS: SALC ; AL: zero MOV AH,[BP+DI] ; AX: pitch F#, ... MUL SI ; SI: the timer counter AND DX,1FH ; DX: get a saw wave sample ADD BH,DL ; BH: sample (sum of the notes) INC DI ; next note TEST DI,3 ; loop 4x JNZ CHORDS
Идея создания кавера популярной песни в среде с ограничениями — это очень увлекательно. Именно поэтому длительность нот отличается от степени двойки.
Аккорды имеют длину 7, 8 и 17. Мне пришлось преобразовать длительности в 8, 8 и 16. Поэтому я сместил начало и в последнюю долю поместил тишину.
TEST SI,1111000000000000B JZ SKIP ; no chords at the last beat ... ; chords here DRUMS: SUB SI,1000000000000B ; shifting back the drums by one beat
Но после того, как музыка провалилась на Revision, мы её изменили. Я считаю, что ern0 нашёл гораздо более интересные аккорды. Мне нравится настроение новой композиции.
Паттерн
Хранимые данные музыкальных нот почти всегда можно ужать. «Сырые» данные имеют размер 32 байта:
NOTES: DB A_3,B_3,D_4,Fs4 DB B_3,D_4,E_4,Gs4 DB Cs4,E_4,Fs4,A_4 DB Cs4,E_4,Fs4,A_4 DB B_3,D_4,Fs4,B_4 DB B_3,Cs4,E_4,Gs4 DB Cs4,E_4,Fs4,A_4 DB Cs4,E_4,Fs4,A_4
Вот простой декодер:
MOV DI,SI SHRD DI,BX,2+16-5 AND DI,7*4
Видите, мы можем сэкономить 12 байт данных…
NOTES: DB A_3,B_3,D_4,Fs4 DB B_3,D_4,E_4,Gs4 DB B_3,D_4,Fs4,B_4 DB B_3,Cs4,E_4,Gs4 DB Cs4,E_4,Fs4,A_4
А на декодере мы потеряли всего 7 байт.
MOV DI,4*4 SHR BL,1 JC .1 MOV DI,AX SHLD DI,SI,3 AND DI,3*4 .1:
Огибающие
У нас есть две огибающие. Простая ADSR: без атаки, только затухание.
Подготавливаем регистры CL и CH перед циклом аккордов:
MOV AX,BX ; BL: pattern MOV CX,3 SHR AL,1 JC .1 MOV CH,128 .1: DEC AX ; skipping the drums-only intro SHR AL,1 AND CL,AL
Одна огибающая для тона…
IMUL AX,SI,-16 OR AL,111B ROR AX,CL MUL BX ; DH: sample
и одна для громкости…
IMUL AX,SI,-1 OR AH,CH ; CH: 128 or 0 MUL DX ; DH: sample
Мастеринг
После сложения каждого инструмента, барабана и аккорда я проверяю максимальную громкость. Я всегда храню отладочную информацию в памяти и вывожу её при помощи внешней утилиты.
if maxvol=1 CMP [FS:8000H],BH JAE .1 MOV [FS:8000H],BH .1: end if
На этот раз максимальное значение сэмпла равно 181. Поэтому я ограничу его всего 7 битами.
MOV AL,180 ; vol 181 -> vol 127 MUL BH ; mastering XCHG BX,AX DONE: MOV [BP+IRQ.SAMPLE-1],BH
Но на части подавления я убираю это снижение размерности и аккорды становятся ещё громче.
Вот сгенерированная песня целиком:
Готовое интро можно скачать отсюда: https://www.pouet.net/prod.php? which=87078
