[Перевод] Пишем трассировщик лучей для ZX Spectrum
Я люблю трассировщики лучей и даже посвятил им половину своей книги. Менее известна моя любовь к ZX Spectrum — домашнему компьютеру 1982 года, с которым я вырос и с которого начался мой интерес к графике и программированию. По современным стандартам эта машина столь смехотворно слаба (и даже по стандартам 1980-х), поэтому возникает неизбежный вопрос: в какой степени удастся портировать трассировщик лучей из книги Computer Graphics from Scratch на ZX Spectrum?
В ZX Spectrum установлен процессор Z80 на 3,5 МГц (в тысячу раз медленнее, чем современные компьютеры), который не может умножать числа (!!!), и 48 КБ ОЗУ (в миллион раз меньше); он имеет графический режим 256×176 (примерно в двести раз меньше современного разрешения), способный отображать 15 цветов (в миллион раз меньше, к тому же с довольно необычными особенностями). Интересная машина для графического приложения, активно задействующего CPU!
Я планирую реализовать его на Sinclair BASIC — встроенном языке программирования Spectrum. Это не просто BASIC, а древний, очень ограниченный диалект BASIC. Например, единственные структуры управления в нём — это FOR и IF (а у IF нет ELSE и даже ENDIF); все переменные глобальны; не существует вызовов функций, только GO TO и GO SUB; и так далее. Кроме того, он интерпретируемый, то есть сверхмедленный. Но, по крайней мере, он реализует программное умножение! Если мне нужна будет производительность, то я всегда могу переписать трассировщик на ассемблере.
Я настроил минимально необходимую среду: код на BASIC я пишу в VS Code, компилирую его с помощью BAS2TAP и запускаю в эмуляторе FUSE. Благодаря этому скорость итераций оказалась достаточно высокой.
Стоит отметить, что я не писал на BASIC примерно тридцать лет, поэтому был удивлён, насколько быстро всё вспомнил. Когда я занимался этим, мне было с четырёх до десяти лет, поэтому, вероятно, это осталось в мозгу как всё, что мы изучаем в этом возрасте, например, языки и акценты. Давайте будем писать код, как будто на дворе 1984 год!
Первая итерация: простой трассировщик лучей
Моя первая итерация была достаточно простой: я портировал начальный код трассировки лучей CGFS на BASIC, почти ничего не изменив, чтобы он выводил изображение размером 32×22 блока. Как ни странно, всё сработало:
Число в левом верхнем углу (879.76) — это время в секундах, которое понадобилось для рендеринга этого изображения. Да, почти 15 минут. А вот та же сцена, отрендеренная трассировщиком лучей CGFS примерно за секунду, с использованием той же сцены и набора свойств:
Учитывая ограничения, версия для Spectrum выглядит вполне неплохо! Давайте взглянем на код:
1 BRIGHT 1: CLS
5 LET ROX = 0
6 LET ROY = 0
7 LET ROZ = 0
8 LET TMIN = 0
9 LET TMAX = 10000
10 FOR X = 0 TO 31
20 FOR Y = 0 TO 21
30 LET RDX = (X - 16) / 32
31 LET RDY = (11 - Y) / 32
32 LET RDZ = 1
40 GO SUB 1000
50 PAPER COL
51 PRINT AT Y, X; " "
100 NEXT Y
105 GO SUB 3000: PRINT AT 0, 0; TIME
110 NEXT X
120 STOP
1000 REM ===== TraceRay =====
1001 REM Params: (ROX, ROY, ROZ): ray origin; (RDX, RDY, RDZ): ray direction; (TMIN, TMAX): wanted ranges of t
1002 REM Returns: COL: pixel color
1010 LET COL = -1: LET MINT = 0
1100 RESTORE 9000
1101 READ NS
1102 FOR S = 1 TO NS
1110 READ SCX, SCY, SCZ, SRAD, SCOL
1200 LET COX = ROX - SCX
1201 LET COY = ROY - SCY
1202 LET COZ = ROZ - SCZ
1210 LET EQA = RDX*RDX + RDY*RDY + RDZ*RDZ
1211 LET EQB = 2*(RDX*COX + RDY*COY + RDZ*COZ)
1212 LET EQC = (COX*COX + COY*COY + COZ*COZ) - SRAD*SRAD
1220 LET DISC = EQB*EQB - 4*EQA*EQC
1230 IF DISC < 0 THEN GO TO 1500
1240 LET T1 = (-EQB + SQR(DISC)) / 2*EQA
1241 LET T2 = (-EQB - SQR(DISC)) / 2*EQA
1250 IF T1 >= TMIN AND T1 <= TMAX AND (T1 < MINT OR COL = -1) THEN LET COL = SCOL: LET MINT = T1
1300 IF T2 >= TMIN AND T2 <= TMAX AND (T2 < MINT OR COL = -1) THEN LET COL = SCOL: LET MINT = T2
1500 NEXT S
1999 IF COL = -1 THEN LET COL = 0
2000 RETURN
3000 REM ===== Get timestamp in seconds =====
3001 LET TIME = (65536*PEEK 23674 + 256*PEEK 23673 + PEEK 23672) / 50
3002 RETURN
8998 REM ===== Sphere data =====
8999 REM Sphere count, followed by (SCX, SCY, SCZ, SRAD, COLOR)
9000 DATA 4
9001 DATA 0, -1, 4, 1, 2
9002 DATA 2, 0, 4, 1, 1
9003 DATA -2, 0, 4, 1, 4
9004 DATA 0, -5001, 0, 5000, 6Если вы знакомы с трассировщиками лучей и с трассировщиком CGFS в частности, то структура кода будет вам привычна, несмотря на то, что написана на древнем диалекте BASIC. Но я всё равно пройдусь по коду, чтобы указать на странные особенности Spectrum.
Во-первых, номера строк. Каждая строка должна была иметь номер, чтобы можно было использовать GO TO или GO SUB. В строки можно было вводить несколько операторов, разделённых двоеточием, что особенно полезно для оператора IF ... THEN, ведь в END IF в этом диалекте не существует!
Можно заметить, что номера строк указаны вразброс. Редактор Spectrum BASIC ориентировался на строки, поэтому хотя номера строк и можно было менять, это был очень долгий процесс. Поэтому мы нумеровали строки числами, кратными 10, чтобы оставалось «место» между ними на случай необходимости добавить строки.
Мы начинаем с этого:
1 BRIGHT 1: CLSВ Spectrum использовался очень странный графический режим. Подробнее я расскажу о нём в следующем разделе, а пока просто скажем, что BRIGHT 1 выбирает яркую версию цветовой палитры, а CLS очищает экран. То есть мы готовы что-нибудь рисовать.
Затем идёт основной цикл трассировщика:
5 LET ROX = 0
6 LET ROY = 0
7 LET ROZ = 0
8 LET TMIN = 0
9 LET TMAX = 10000
10 FOR X = 0 TO 31
20 FOR Y = 0 TO 21
30 LET RDX = (X - 16) / 32
31 LET RDY = (11 - Y) / 32
32 LET RDZ = 1
40 GO SUB 1000
50 PAPER COL
51 PRINT AT Y, X; " "
100 NEXT Y
105 GO SUB 3000: PRINT AT 0, 0; TIME
110 NEXT X
120 STOPВ строках с 5 по 9 задаются параметры, остающиеся константами для всего основного цикла. В BASIC есть массивы, но с ними довольно неудобно работать, поэтому не стоило использовать их для описания точек и векторов. Из-за этого точка начала луча RO представлена тремя переменными ROX, ROY и ROZ.
В строках с 10 по 110 приведён основной цикл, итеративно обходящий холст (32×22 квадрата). После каждого прохода внутреннего цикла, рендеринга столбца квадратов, строка 105 выполняет эквивалент вызова функции: GO SUB 3000 переносит поток управления к подпроцедуре (subroutine) в строке 3000:
3000 REM ===== Get timestamp in seconds =====
3001 LET TIME = (65536*PEEK 23674 + 256*PEEK 23673 + PEEK 23672) / 50
3002 RETURNСтрока 3000 начинается с REM (сокращение от remark, «примечание»). Сегодня мы называем их «комментариями», но ZX Spectrum — британская машина, порождение разума безумного гения сэра Клайва Синклера. То есть эта строка — просто комментарий.
Магическое заклинание в строке 3001 считывает текущую метку времени в секундах. Как? PEEK получает адрес памяти и возвращает его содержимое. Эта строка лишь считывает хранящееся в памяти 24-битное число, описывающее внутренний счётчик FRAME; инкремент этого счётчика выполняется каждые 20 мс, поэтому мы делим его на 50, чтобы преобразовать в секунды, а затем сохраняем в переменную TIME.
Каждая переменная в программе глобальна, поэтому RETURN в строке 3002 просто возвращает поток управления вызывавшей стороне, и подразумевается, что «возвращаемое значение» функции — это глобальная переменная TIME. Этот механизм GO SUB / RETURN очень похож на CALL / RET в ассемблере.
Строка 120 завершает выполнение программы.
Теперь давайте взглянем на внутренний цикл. Строки с 30 по 32 преобразуют координаты холста в координаты точки обзора (CanvasToViewport в CGFS). Направление луча задано (RDX, RDY, RDZ).
Строка 40 выполняет ещё один «вызов функции»; на этот раз это эквивалент TraceRay. Когда она совершает возврат, переменная COL будет содержать цвет того, с чем столкнулся луч.
Строки 50 и 51 отрисовывают блок. Это выполняется заданием цвета PAPER (фона) и отрисовкой пространства (подробнее об этом позже).
Давайте рассмотрим TraceRay, начинающуюся в строке 1000. Она начинается с блока комментариев, в котором задокументированы необходимые входные и выходные данные:
1000 REM ===== TraceRay =====
1001 REM Params: (ROX, ROY, ROZ): ray origin; (RDX, RDY, RDZ): ray direction; (TMIN, TMAX): wanted ranges of t
1002 REM Returns: COL: pixel colorТак как аргументов функций или возвращаемых значений не существует, всё задаётся глобально, косвенно и по договорённости. В данном случае входные данные — это (ROX, ROY, ROZ), (RDX, RDY, RDZ), TMIN и TMAX, а возвращаемое значение находится в переменной COL. Она описывает индекс в фиксированной цветовой палитре ZX Spectrum.
В строке 1010 инициализируются значения, которые нам нужны для отслеживания ближайшего найденного на данный момент пересечения и цвета сферы в месте пересечения:
1010 LET COL = -1: LET MINT = 0Затем мы начинаем цикл «для каждой сферы»:
1100 RESTORE 9000
1101 READ NS
1102 FOR S = 1 TO NS
1110 READ SCX, SCY, SCZ, SRAD, SCOLСтрока 1100 сбрасывает «указатель данных» на строку 9000, которая содержит данные сцены:
8998 REM ===== Sphere data =====
8999 REM Sphere count, followed by (SCX, SCY, SCZ, SRAD, COLOR)
9000 DATA 4
9001 DATA 0, -1, 4, 1, 2
9002 DATA 2, 0, 4, 1, 1
9003 DATA -2, 0, 4, 1, 4
9004 DATA 0, -5001, 0, 5000, 6Оператор READ в строке 1101 считывает первое значение (число 4 в строке 9000) в переменную NS. Затем строка 1102 начинает цикл «для каждой сферы», и первое, что мы делаем в строке 1110 — это считываем в переменные 5 значений, задающих сферу. После первой серии операторов READ указатель данных находится на первом значении строки 9002, готовом к считыванию в следующей итерации цикла.
Строки с 1200 по 1300 решают простое уравнение пересечения луча со сферой, а строки 1250 и 1300 отслеживают самое ближнее пересечение:
1200 LET COX = ROX - SCX
1201 LET COY = ROY - SCY
1202 LET COZ = ROZ - SCZ
1210 LET EQA = RDXRDX + RDYRDY + RDZRDZ
1211 LET EQB = 2(RDXCOX + RDYCOY + RDZCOZ)
1212 LET EQC = (COXCOX + COYCOY + COZCOZ) - SRAD*SRAD
1220 LET DISC = EQBEQB - 4EQA*EQC
1230 IF DISC < 0 THEN GO TO 1500
1240 LET T1 = (-EQB + SQR(DISC)) / 2EQA
1241 LET T2 = (-EQB - SQR(DISC)) / 2EQA
1250 IF T1 >= TMIN AND T1 <= TMAX AND (T1 < MINT OR COL = -1) THEN LET COL = SCOL: LET MINT = T1
1300 IF T2 >= TMIN AND T2 <= TMAX AND (T2 < MINT OR COL = -1) THEN LET COL = SCOL: LET MINT = T2Мы завершаем цикл, проверяя отсутствие пересечений; если их не было, то мы задаём значение цвета 0 (чёрный) и выполняем возврат:
1999 IF COL = -1 THEN LET COL = 0
2000 RETURNВот и всё. Мы получили сверхмедленный результат с ультранизким разрешением:
Мне кажется потрясающим, что для этого нужно всего пятьдесят строк относительно простого кода на маломощной машине начала 80-х!
Но это лишь начало. Зачем останавливаться на 32×22, когда можно использовать все 256×176 пикселей экрана?
Вторая итерация: разрешение повыше и обработка конфликта атрибутов
Можно подумать, что для повышения разрешения этого трассировщика достаточно изменить значение внешнего цикла с 32×22 на 256×176 и отрисовывать отдельные пиксели при помощи PLOT вместо блочных квадратов при помощи PRINT. Это было бы в 64 раз медленнее (16 часов вместо 15 минут), но сработало бы… если не учесть странности графического режима ZX Spectrum!
Первая версия ZX Spectrum имела суммарно 16 КБ ОЗУ, так что абсолютно критичной была эффективность использования памяти (мне купили гораздо более шикарную модель с 48 КБ). Для экономии памяти видео-ОЗУ было разделено на два блока: блок битовых карт, использующих по одному биту на пиксель, и блок атрибутов, использующий по одному байту на блок пикселей 8×8. Блок атрибутов мог присваивать этому блоку два цвета, называвшихся INK (передний план) и PAPER (фон).
То есть можно использовать PLOT для установки или сброса соответствующего пикселю бита, который затем займёт один из двух цветов, назначаемых этому блоку. Это значит, что каждый блок пикселей 8×8 может отображать один или два цвета, но не три или больше.
Всё это замечательно работало для текстовых приложений, так как символы тоже имеют размер 8×8, но для любой графики, и особенно для игр, это было очень большим ограничением. Это ограничение придаёт играм для Spectrum их очень характерную эстетику, потому что художникам приходилось обходить его, обычно проектируя экраны и спрайты так, чтобы они были выравнены по сетке пикселей 8×8, или переходя в полный монохром, или принимая тот факт, что конфликт атрибутов — неотъемлемый факт.
Вернёмся к нашему трассировщику лучей. Повысить разрешение легко. Устранить конфликт атрибутов уже сложнее.
Идеального решения нет: что бы я ни делал, каждый блок 8×8 будет отображаться максимум двумя цветами. Поэтому я реализовал алгоритм аппроксимации. Я собираю цвета, представленные в блоке 8×8, нахожу два наиболее часто встречающихся и отрисовываю каждый пиксель одним из двух цветов.
Чтобы отразить повышение разрешение и обработку блоков 8×8, нужно немного изменить внешний цикл:
10 FOR X = 0 TO 255 STEP 8
20 FOR Y = 0 TO 175 STEP 8
...
500 NEXT Y
505 GO SUB 3000: PRINT AT 0, 0; TIME
510 NEXT X
520 STOPЗатем мы трассируем 64 луча, собирая цвета в массив:
30 DIM C(64)
31 LET CI = 1
32 DIM A(8)
120 REM --- For each 8x8 block, collect the pixel colors and their counts ---
125 FOR U = X TO X+7
126 FOR V = Y TO Y+7
130 LET RDX = (U - 128) / 256
131 LET RDY = (V - 88) / 256
132 LET RDZ = 1
140 GO SUB 1000
141 LET C(CI) = COL
142 LET CI = CI + 1
143 LET A(COL+1) = A(COL+1) + 1
160 NEXT V
161 NEXT UСтрока 30 при помощи DIM преобразует переменную C в массив из 64 элементов. Индексы массивов начинаются с 1, поэтому строка 31 инициализирует CI (индекс C) со значением 1. Строка 32 создаёт ещё один массив A, в котором будет храниться количество цветов.
Строки с 140 по 143 вызывают TraceRay и сохраняют её результаты: цвет пикселя в C, а обновлённое количество цветов — в A. Цвета имеют номера от 0 до 7, а индексы — от 1 до 8, так что нужно использовать в качестве индекса COL+1.
Дальше нам нужно найти самый частый и второй по частоте цвета:
199 REM --- Find the most and second most frequent colors in this 8x8 block ---
201 LET MFC = 0
202 FOR C = 1 TO 8
203 IF A(C) > MFC THEN LET MFC = A(C): LET MFI = C
204 NEXT C
205 LET FCOL = MFI - 1
207 LET II = MFI: LET MFC = 0: LET MFI = 0
208 FOR C = 1 TO 8
209 IF C <> II AND A(C) > MFC THEN LET MFC = A(C): LET MFI = C
210 NEXT C
211 LET SCOL = MFI - 1Настало время рисовать пиксели. Если все пиксели имеют одинаковый цвет, просто рисуем блок:
259 REM --- If there's only one color, paint the whole block --
260 IF SCOL <> -1 THEN GO TO 300
270 POKE 22528 + X/8 + 32*(21-Y/8), 64 + FCOL * 8
280 GO TO 500Нужно объяснить, что такое POKE. POKE помещает байт в адрес памяти. Первый параметр — это адрес текущего блока 8×8 в блоке атрибутов. Второй параметр, байт, задающий значения INK и PAPER — это сочетание цвета INK со сдвигом влево на 3 бита плюс бит для включения атрибута BRIGHT.
Если не все пиксели имеют одинаковый цвет, нам нужно раскрашивать их по отдельности. Цвету PAPER блока присваивается самый частый цвет (чтобы нужно было раскрашивать меньше пикселей); мы обходим массив, и любой пиксель, не являющийся самым частым цветом, отрисовывается цветом INK, которому присвоен второй по частоте цвет:
300 REM --- Otherwise set the PAPER to the most frequent color, and draw everything else in the second most frequent color --
301 LET CI = 1
310 FOR U = X TO X+7
311 FOR V = Y TO Y+7
320 IF C(CI) <> FCOL THEN PLOT INK SCOL; PAPER FCOL; U, V
321 LET CI = CI + 1
350 NEXT V
351 NEXT UРаботает довольно неплохо!
Но конфликты атрибутов всё равно возникают. Посмотрим на увеличенную часть:
Наложив сетку, отображающую границы блоков, проще разобраться в проблеме. Два блока, которые выглядят «неправильно», должны состоять из трёх цветов: чёрного, жёлтого и или зелёного, или красного. Но Spectrum на это не способен, поэтому алгоритм сделал именно так.
Можете взглянуть на полный исходный код этой итерации.
Также стоит отметить, что код невероятно медленный — он выполняется больше 17 часов! Даже если выставить в эмуляторе скорость 20000%, рендеринг занимает приличное время. Можно ли улучшить ситуацию?
Третья итерация: повышение производительности
Я решил использовать проход оптимизации. Вот, что я сделал:
Для каждого из блоков 8×8 трассируем лучи в четырёх углах, и если цвет во всех углах одинаков, то закрашиваем блок целиком. В большинстве случаев это требует четырёх лучей на блок вместо 64, то есть ускоряет рендеринг в 16 раз. Разумеется, если существуют мелкие объекты, целиком попадающие в блок, то трассировщик их упустит;, но для этой тестовой сцены такая аппроксимация выглядит вполне справедливой.
Любой ценой избегаем умножений и делений. Z80 не может выполнять умножение аппаратно (не говоря уже о делении), поэтому BASIC реализует его программно, а это очень медленно.
Пропишем некоторые константы на основании допущений. В частности, точка начала луча всегда (0, 0, 0),
t_min— всегда 0, аt_max— всегда+inf, поэтому здесь мы сэкономим немного времени вычислений.По возможности вычисляем значения заранее. Зачем хранить радиус сферы в виде данных и возводить его в квадрат, если можно изначально хранить её квадрат?
По возможности перемещаем вычисленные значения во внешние циклы. Например, значения, связанные с X, постоянны для каждого Y, а потому могут вычисляться меньше раз.
Встроим подпроцедуру «самого частого цвета» и специализируем первый случай, чтобы она не игнорировала никакие цвета.
Изменим номера строк так, чтобы
GO SUBне переходила на строку сREM; можете не верить, но обработка строки с комментарием занимает время!Используем более короткие имена переменных. Этот BASIC интерпретируемый, так что каждый раз, когда мы ссылаемся на переменную, интерпретатор ищет её по имени…
Ещё я попробовал несколько оптимизаций, которые не сработали, например, предварительное считывание
DATAв массив или помещение отдельных выражений в переменные. У меня есть смутное ощущение, что важен порядок объявления переменных, нужно почитать об этом подробнее.Были ещё оптимизации, которые незначительно помогли, но снизили читаемость, так что я решил их не реализовывать.
В конечном итоге результат оказался вполне неплохим. Изображение осталось идентичным по пикселям, но время выполнения снизилось до двух часов с небольшим:
Можете взглянуть на полный исходный код этой итерации.
Четвёртая итерация: источник света (только один)
Поначалу я хотел остановиться на этом; учитывая ограничения среды, мне казалось, что почти больше ничего сделать не получится.
Очевидным следующим шагом стала бы реализация освещения. Уравнения и алгоритмы освещения относительно просты, но основная проблема заключается в ограниченном наборе цветов ZX Spectrum. Повторюсь, что у него фиксированный набор из 7 цветов в обычной и яркой версии, плюс чёрный:
Даже если бы у меня была значение яркости света в каждом пикселе, я бы не мог просто умножить его на цвет сферы, чтобы получить затенённый цвет, как это элементарно делается в RGB. Что же делать?
Конечно, идти на компромиссы. Я могу имитировать оттенки цветов, перемежая в нужной степени цвет и чёрный фон. Можно это делать для каждого блока 8×8, присвоив INK значение цвета, а PAPER — чёрный цвет. Компромисс в том, что будет присутствовать конфликт атрибутов.
Как решить, раскрашивать ли пиксель, или оставить его чёрным? Первым делом я придумал использовать яркость света, вещественное число от 0.0 до 1.0, как вероятность того, что пиксель будет раскрашен цветом (в противном случае останется чёрным). Это сработало, но выглядело некрасиво. Есть решение получше под названием ordered dithering (упорядоченный дизеринг). Его идея заключается в том, чтобы хранить матрицу пороговых значений, по одному на пиксель, помогающую определить, нужно ли раскрашивать пиксель. Пороговые значения выстроены в таком порядке, что создают повторяющееся и приятные глазу паттерны пикселей для любого уровня яркости. Существует матрица дизеринга 8×8, идеально соответствующая блокам цвета 8×8, которые я обрабатываю, так что реализовать её было на удивление просто.
Из соображений простоты я решил использовать только один источник света. Даже при упорядоченном дизеринге мне будет недостаточно оттенков для адекватного представления нюансов нескольких источников, освещающих один объект. По той же причине я использовал только рассеянное освещение, без отражений.
Наша цель — отрендерить нечто подобное:
Насколько близко мы сможем подобраться к этому на скромном ZX Spectrum?
Я внёс в код следующие изменения:
Использовать трюк с четырьмя лучами на блок 8×8 больше было нельзя, потому что яркость света на каждом пикселе может быть разной. Можно было вычислять по одной яркости на блок, но мне не хотелось терять разрешение освещения. Так что по сравнению с предыдущей итерацией производительность сильно пострадала. Исключением будет случай, когда все четыре угла блока 8×8 чёрные, в этом случае его можно спокойно игнорировать.
Код расчёта освещения довольно прост: в подпроцедуре TraceRay мне нужно было отслеживать индекс ближайшей сферы (поэтому мне также пришлось в начале программы записать данные сфер в массив S). Если после цикла сфер луч сталкивается с какой-то из них, я вычисляю пересечение между лучом и сферой, нормаль в этой точке сферы и освещение в этой точке:
1601 LET NX = DX*MT - S(CS, 1): LET NY = DY*MT - S(CS, 2): LET NZ = DZ*MT - S(CS, 3)
1610 LET PL = AI
1615 LET NL = (NX*LX + NY*LY + NZ*LZ)
1620 IF NL > 0 THEN LET PL = PL + DI * NL / SQR(NX*NX + NY*NY + NZ*NZ)В этом фрагменте CS — это индекс ближайшей сферы (Closest Sphere); PL — новая выходная переменная, обозначающая освещение пикселя (Pixel Lighting); (LX, LY, LZ), DI и AI задаются в другом месте, они описывают направление света, его яркость и яркость внешнего освещения. Из соображений производительности LX, LY, LZ задают нормализованный вектор, благодаря чему я смог избавиться от SQR и от деления в строке 1620.
Больше мне не нужно искать второй по частоте цвет в каждом блоке 8×8, потому что теперь в каждом блоке отображается только самый частый цвет и чёрный.
Я добавил код для добавления в массив матрицу упорядоченного дизеринга Байера:
3 GO SUB 7000
...
6999 REM ===== Initialize 8x8 Bayer matrix =====
7000 DIM H(64)
7001 RESTORE 7100
7002 FOR I = 1 TO 64
7003 READ H(I): LET H(I) = H(I) / 64
7004 NEXT I
7005 RETURN
7100 DATA 0, 32, 8, 40, 2, 34, 10, 42
7101 DATA 48, 16, 56, 24, 50, 18, 58, 26
7102 DATA 12, 44, 4, 36, 14, 46, 6, 38
7103 DATA 60, 28, 52, 20, 62, 30, 54, 22
7104 DATA 3, 35, 11, 43, 1, 33, 9, 41
7105 DATA 51, 19, 59, 27, 49, 17, 57, 25
7106 DATA 15, 47, 7, 39, 13, 45, 5, 37
7107 DATA 63, 31, 55, 23, 61, 29, 53, 21Кроме того, перед раскрашиванием пикселя я сравниваю его яркость освещения с соответствующим пороговым значением в матрице Байера:
320 IF C(CI) > 0 AND H(CI) <= L(CI) THEN PLOT U, VЯ запустил эту итерацию и, если честно, добрую минуту не мог поверить своим глазам:
Во-первых, это сработало!
Выполнение довольно медленное по сравнению с предыдущей итерацией, в основном из-а отсутствия трюка с четырьмя лучами на блок плюс из-за дополнительных вычислений освещённости. Но всё не так уж плохо.
Конфликт атрибутов по-прежнему присутствует, и теперь он гораздо очевиднее. Можно ли улучшить ситуацию? Вероятно. Похоже, конфликты жёлтого/красного можно исправить, делая блоки красными и жёлтыми, избавляясь от деталей затенённости (потому что в них не будет чёрного). Ситуацию с зелёным/жёлтым и синим/жёлтым, похоже, можно сильно улучшить, использовав чёрный/жёлтый, синий/жёлтый и снова чёрный/жёлтый. Возможно, я ещё вернусь к этому.
Можете посмотреть на полный исходный код этой итерации.
Пятая итерация: тени
К этому моменту я уже достаточно хорошо освоился со средой и привык кодить, как будто на дворе 1984 год, поэтому решил проверить, насколько далеко смогу зайти. Следующий этап — тени.
Для этого уже почти всё готово. Теория довольно проста: перед вычислением освещения для точки нам нужно выяснить, есть ли объект между точкой и источником освещения, блокирующий его (то есть отбрасывающий тень). Мне просто нужно было реализовать специализированную версию TraceRay, выполняющую трассировку от пересечения первичного луча и сферы в направлении направленного источника света, и выполняющую возврат сразу после нахождения пересечения:
2090 REM ----- Specialized TraceRay for shadow checks -----
2091 REM Params: (IX, IY, IZ): ray start; (LX, LY, LZ): ray direction (directional light vector)
2092 REM Returns: H = 1 if the ray intersects any sphere, H = 0 otherwise
2093 REM Optimizations: (TMIN, TMAX) hardcoded to (epsilon, +inf)
2100 LET A = 2*(LX*LX + LY*LY + LZ*LZ)
2110 FOR S = 1 TO NS
2111 LET CX = IX - S(S,1): LET CY = IY - S(S,2): LET CZ = IZ - S(S,3)
2120 LET B = -2*(CX*LX + CY*LY + CZ*LZ)
2130 LET C = (CX*CX + CY*CY + CZ*CZ) - S(S, 4)
2140 LET D = B*B - 2*A*C
2150 IF D < 0 THEN GO TO 2210
2160 LET D = SQR(D)
2170 LET T = (B + D) / A
2180 IF T > 0.01 THEN LET H = 1: RETURN
2190 LET T = (B - D) / A
2200 IF T > 0.01 THEN LET H = 1: RETURN
2210 NEXT S
2220 LET H = 0: RETURNЭтот код вызывается до вычисления освещённости:
1600 LET IX = DX*MT: LET IY = DY*MT: LET IZ = DZ*MT
1601 LET NX = IX - S(CS, 1): LET NY = IY - S(CS, 2): LET NZ = IZ - S(CS, 3)
1610 LET PL = AI
1612 GO SUB 2100: IF H = 1 THEN RETURN
1615 LET NL = (NX*LX + NY*LY + NZ*LZ)
1620 IF NL > 0 THEN LET PL = PL + DI * NL / SQR(NX*NX + NY*NY + NZ*NZ)И вот, что получилось…
Сравним это с результатом трассировщика лучей CGFS:
Довольно медленно из-за дополнительных вычислений (мы снова вернулись к 17 часам), но определённо того стоит!
Можно посмотреть полный исходный код этой итерации.
Что дальше?
Очевидно, что дальше можно реализовать отражения. Но смешивать цвета будет практически невозможно, поэтому объекты будут или полностью отражающими, или совсем не отражающими, и это просто будет выглядеть странно. Интересной проблемой станет рекурсия: Spectrum поддерживает её, но поскольку локальные переменные отсутствуют, каждый рекурсивный вызов будет перезаписывать глобальные переменные, поэтому придётся реализовать собственный стек. Вполне выполнимо, но, похоже, не будет стоить всех усилий.
Ещё одна ось для совершенствования — это производительность. Можно было бы переписать весь код на ассемблере и посмотреть, насколько быстро он сможет работать. Я смогу управлять нужной степенью точности, так что, возможно, подойдут и вычисления с фиксированной запятой (или менее точная версия SQR). Вероятно, когда-нибудь я возьмусь за это!
Кроме того, меня по-прежнему напрягает конфликт атрибутов на краях объектов. У меня есть пара идей по улучшению ситуации, однако из-за ограничений Spectrum их невозможно будет устранить на 100%.
Ностальгические рассуждения
Это был интересный проект на выходные. Совершенно бесполезный, но интересный!
Было приятно снова писать на Sinclair BASIC спустя тридцать лет. Хотя язык остался прежним, изменился я: начал думать в более высокоуровневых концепциях и затем переносить их в BASIC. Не знаю, потому ли это, что современные языки дали мне лучший вокабуляр для мышления, который я могу перенести в BASIC, или потому, что мне уже не десять лет. Может быть и то, и другое вместе.
В частности, в этой программе разумно применяется GO TO, который, как все знают, Считается Вредным™. В те времена это практически всё, что у нас было: никаких вызовов функций, только подпроцедуры с помощью GO SUB; никаких WHILE или REPEAT; у IF не было END IF; FOR не имел BREAK или CONTINUE (эти ключевые слова существовали, но делали не то, что вы могли бы подумать). Так что неизбежно приходилось пользоваться GO TO. Да, это может привести к спагетти-коду, но необязательно; мой собственный код из статьи, хотя и прост, структурирован чисто.
Кроме того, я скучаю по непосредственности и простоте среды. Никаких фреймворков, зависимостей, практически никаких абстракций (даже умножение реализовано программно!). ZX Spectrum можно было полностью осознавать. Весь набор команд Z80, особенности ПЗУ и АЛУ — всё это достаточно легко умещалось в голове. Можно было рассуждать о производительности вплоть до уровня тактов процессора — никаких кэшей, конвейеров или чего-то ещё, усложняющего жизнь. Я скучаю по всему этому. Нынешние дети никогда не смогут ощутить, каково работать в такой среде, и это меня печалит.
9999 STOP