Пишем трассировщик лучей для ZX Spectrum

Я люблю трассировщики лучей и даже посвятил им половину своей книги. Менее известна моя любовь к ZX Spectrum — домашнему компьютеру 1982 года, с которым я вырос и с которого начался мой интерес к графике и программированию. По современным стандартам эта машина столь смехотворно слаба (и даже по стандартам 1980-х), поэтому возникает неизбежный вопрос: в какой степени удастся портировать трассировщик лучей из книги Computer Graphics from Scratch на ZX Spectrum?

В ZX Spectrum установлен процессор Z80 на 3,5 МГц (в тысячу раз медленнее, чем современные компьютеры), который не может умножать числа (!!!), и 48 КБ ОЗУ (в миллион раз меньше); он имеет графический режим 256x176 (примерно в двести раз меньше современного разрешения), способный отображать 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, почти ничего не изменив, чтобы он выводил изображение размером 32x22 блока. Как ни странно, всё сработало:

Число в левом верхнем углу (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 приведён основной цикл, итеративно обходящий холст (32x22 квадрата). После каждого прохода внутреннего цикла, рендеринга столбца квадратов, строка 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-х!

Но это лишь начало. Зачем останавливаться на 32x22, когда можно использовать все 256x176 пикселей экрана?

Вторая итерация: разрешение повыше и обработка конфликта атрибутов

Можно подумать, что для повышения разрешения этого трассировщика достаточно изменить значение внешнего цикла с 32x22 на 256x176 и отрисовывать отдельные пиксели при помощи PLOT вместо блочных квадратов при помощи PRINT. Это было бы в 64 раз медленнее (16 часов вместо 15 минут), но сработало бы... если не учесть странности графического режима ZX Spectrum!

Первая версия ZX Spectrum имела суммарно 16 КБ ОЗУ, так что абсолютно критичной была эффективность использования памяти (мне купили гораздо более шикарную модель с 48 КБ). Для экономии памяти видео-ОЗУ было разделено на два блока: блок битовых карт, использующих по одному биту на пиксель, и блок атрибутов, использующий по одному байту на блок пикселей 8x8. Блок атрибутов мог присваивать этому блоку два цвета, называвшихся INK (передний план) и PAPER (фон).

То есть можно использовать PLOT для установки или сброса соответствующего пикселю бита, который затем займёт один из двух цветов, назначаемых этому блоку. Это значит, что каждый блок пикселей 8x8 может отображать один или два цвета, но не три или больше.

Всё это замечательно работало для текстовых приложений, так как символы тоже имеют размер 8x8, но для любой графики, и особенно для игр, это было очень большим ограничением. Это ограничение придаёт играм для Spectrum их очень характерную эстетику, потому что художникам приходилось обходить его, обычно проектируя экраны и спрайты так, чтобы они были выравнены по сетке пикселей 8x8, или переходя в полный монохром, или принимая тот факт, что конфликт атрибутов — неотъемлемый факт.

Вернёмся к нашему трассировщику лучей. Повысить разрешение легко. Устранить конфликт атрибутов уже сложнее.

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

Чтобы отразить повышение разрешение и обработку блоков 8x8, нужно немного изменить внешний цикл:

 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 помещает байт в адрес памяти. Первый параметр — это адрес текущего блока 8x8 в блоке атрибутов. Второй параметр, байт, задающий значения 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%, рендеринг занимает приличное время. Можно ли улучшить ситуацию?

Третья итерация: повышение производительности

Я решил использовать проход оптимизации. Вот, что я сделал:

• Для каждого из блоков 8x8 трассируем лучи в четырёх углах, и если цвет во всех углах одинаков, то закрашиваем блок целиком. В большинстве случаев это требует четырёх лучей на блок вместо 64, то есть ускоряет рендеринг в 16 раз. Разумеется, если существуют мелкие объекты, целиком попадающие в блок, то трассировщик их упустит; но для этой тестовой сцены такая аппроксимация выглядит вполне справедливой.

• Любой ценой избегаем умножений и делений. Z80 не может выполнять умножение аппаратно (не говоря уже о делении), поэтому BASIC реализует его программно, а это очень медленно.

• Пропишем некоторые константы на основании допущений. В частности, точка начала луча всегда (0, 0, 0), t_min — всегда 0, а t_max — всегда +inf, поэтому здесь мы сэкономим немного времени вычислений.

• По возможности вычисляем значения заранее. Зачем хранить радиус сферы в виде данных и возводить его в квадрат, если можно изначально хранить её квадрат?

• По возможности перемещаем вычисленные значения во внешние циклы. Например, значения, связанные с X, постоянны для каждого Y, а потому могут вычисляться меньше раз.

• Встроим подпроцедуру «самого частого цвета» и специализируем первый случай, чтобы она не игнорировала никакие цвета.

• Изменим номера строк так, чтобы GO SUB не переходила на строку с REM; можете не верить, но обработка строки с комментарием занимает время!

• Используем более короткие имена переменных. Этот BASIC интерпретируемый, так что каждый раз, когда мы ссылаемся на переменную, интерпретатор ищет её по имени…

• Ещё я попробовал несколько оптимизаций, которые не сработали, например, предварительное считывание DATA в массив или помещение отдельных выражений в переменные. У меня есть смутное ощущение, что важен порядок объявления переменных, нужно почитать об этом подробнее.

• Были ещё оптимизации, которые незначительно помогли, но снизили читаемость, так что я решил их не реализовывать.

В конечном итоге результат оказался вполне неплохим. Изображение осталось идентичным по пикселям, но время выполнения снизилось до двух часов с небольшим:

Можете взглянуть на полный исходный код этой итерации.

Четвёртая итерация: источник света (только один)

Поначалу я хотел остановиться на этом; учитывая ограничения среды, мне казалось, что почти больше ничего сделать не получится.

Очевидным следующим шагом стала бы реализация освещения. Уравнения и алгоритмы освещения относительно просты, но основная проблема заключается в ограниченном наборе цветов ZX Spectrum. Повторюсь, что у него фиксированный набор из 7 цветов в обычной и яркой версии, плюс чёрный:

Даже если бы у меня была значение яркости света в каждом пикселе, я бы не мог просто умножить его на цвет сферы, чтобы получить затенённый цвет, как это элементарно делается в RGB. Что же делать?

Конечно, идти на компромиссы. Я могу имитировать оттенки цветов, перемежая в нужной степени цвет и чёрный фон. Можно это делать для каждого блока 8x8, присвоив INK значение цвета, а PAPER — чёрный цвет. Компромисс в том, что будет присутствовать конфликт атрибутов.

Как решить, раскрашивать ли пиксель, или оставить его чёрным? Первым делом я придумал использовать яркость света, вещественное число от 0.0 до 1.0, как вероятность того, что пиксель будет раскрашен цветом (в противном случае останется чёрным). Это сработало, но выглядело некрасиво. Есть решение получше под названием ordered dithering (упорядоченный дизеринг). Его идея заключается в том, чтобы хранить матрицу пороговых значений, по одному на пиксель, помогающую определить, нужно ли раскрашивать пиксель. Пороговые значения выстроены в таком порядке, что создают повторяющееся и приятные глазу паттерны пикселей для любого уровня яркости. Существует матрица дизеринга 8x8, идеально соответствующая блокам цвета 8x8, которые я обрабатываю, так что реализовать её было на удивление просто.

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

Наша цель — отрендерить нечто подобное:

Насколько близко мы сможем подобраться к этому на скромном ZX Spectrum?

Я внёс в код следующие изменения:

Использовать трюк с четырьмя лучами на блок 8x8 больше было нельзя, потому что яркость света на каждом пикселе может быть разной. Можно было вычислять по одной яркости на блок, но мне не хотелось терять разрешение освещения. Так что по сравнению с предыдущей итерацией производительность сильно пострадала. Исключением будет случай, когда все четыре угла блока 8x8 чёрные, в этом случае его можно спокойно игнорировать.

Код расчёта освещения довольно прост: в подпроцедуре 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.

Больше мне не нужно искать второй по частоте цвет в каждом блоке 8x8, потому что теперь в каждом блоке отображается только самый частый цвет и чёрный.

Я добавил код для добавления в массив матрицу упорядоченного дизеринга Байера:

   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