DOOM. Как в битвах с демонами закалялся новый жанр

BSP – это, по сути, способ выяснить, как различные сектора связаны друг с другом, и таким образом избежать ненужного рендеринга. Этот алгоритм перемещает трудоемкие вычисления для расчета того, какие объекты видны из той или иной точки, на итоговую часть процесса создания уровня. Этот процесс завершается созданием BSP-таблицы, которая содержит данные для графического движка, чтобы установить, какие объекты и в каком порядке рендерить – таким образом, этим не приходится заниматься в режиме реального времени в процессе игры. BSP разбивает уровень на части, которые называются подсекторами – их составляют многоугольники, содержащиеся внутри секторов. У каждого подсектора имеется список связанных с ним секторов. Механизм рендеринга движется вниз по дереву, пока не найдет нужный подсектор, а затем проверяет связанные с ним сектора вместо того, чтобы при каждой перерисовке экрана всякий раз вычислять связанность секторов, так сказать, «обычным способом». По сути, BSP работает как предметный указатель в книге, позволяя быстро и легко находить связи, зависимости и иерархии. Таким образом, как и любой другой алгоритм индексирования, BSP весьма значительно сокращает время рендеринга и, следовательно, увеличивает частоту смены кадров. Считается, что Кармак узнал о BSP из работы Брюса Нейлора, который опубликовал ряд статей о BSP в начале 1980-х годов. Там он ссылался на концептуальную идею BSP, или «предварительную версию», которую Роберт Шумакер предложил за десять с лишним лет до того. Кармак, однако, говорит, что впервые он наткнулся на описание этого принципа в книге Computer Graphics: Principles and Practice («Компьютерная графика: принципы и практика») и уже какое-то время ломал над ним голову. О его опыте внедрения BSP полезно рассказать, потому что он в красках показывает, как компьютерные науки существовали в эпоху до интернета:

«Это не очень важно, но интересно: когда я начал работать над BSP, Брюс Нейлор приехал к нам и подарил мне копии своих статей. Так интересно разговаривать с людьми о прошлом. Конечно, теперь у вас есть интернет. Сейчас вы можете найти все что угодно. Но в те годы найти перепечатки старых научных статей было большой удачей. Раньше я пользовался услугами справочных служб: вы платили им где-то двадцать пять долларов, а они высылали вам ксерокопии старых исследовательских работ. Это был совершенно другой мир. Большую часть своих знаний о программировании я извлек где-то из трех справочников, потому что других книг у меня не было. Приходилось доходить до всего самому. Поэтому оказалось, что в свое время я переизобрел много классических вещей, таких как код Хаффмана[48] или LZW[49]. Я так гордился своими открытиями, а потом узнавал, что все эти вещи уже давно придуманы, причем придуманы гораздо лучше».

Кармак первым применил технологию BSP для игр, и с тех пор она прижилась в основе огромного количества игровых движков. Наряду со многими другими достижениями DOOM, использование Кармаком двоичного разбиения пространства стало исключительно важным наследием для игр в целом. Каковы были результаты? Как выразился Ромеро: «Именно тогда все заработало супербыстро и BSP переродилось для компьютерных игр». В отличие от остальных, Кармак говорит о своих прорывных достижениях намного скромнее: