Ветеран программирования трёхмерной графики Майкл Абраш на примере разработки первого Quake рассказывает о необходимости творческого мышления в программировании.

Много лет назад я работал в теперь уже не существующей компании-производителе видеоадаптеров Video Seven. Там я помогал в разработке клона VGA. Мой коллега Том Уилсон, долгие месяцы круглосуточно работавший над разработкой VGA-чипа Video Seven, стремился сделать VGA как можно более быстрым, и был уверен, что его производительность оптимизирована почти по максимуму. Однако когда Том уже вносил в конструкцию чипа последние штрихи, до нас донеслись слухи, что наш конкурент Paradise достиг ещё большей производительности в своём разрабатываемом клоне, добавив в него FIFO.

На этом слухи заканчивались — мы не знали, ни что это за FIFO, ни насколько он помог, ничего другого. Тем не менее, Том, обычно приветливый и расслабленный человек, превратился в активного, одержимого фанатика со слишком большим процентом кофеина в крови. Исходя из этих крупиц информации, он пытался выяснить, что же удалось сделать Paradise. В конце концов он пришёл к выводу, что Paradise вероятно вставил FIFO-буфер записи между системной шиной и VGA, чтобы когда ЦП выполнял запись в видеопамять, записываемые данные сразу же попадали в FIFO, и это позволяло ЦП продолжать обработку, а не простаивать каждый раз, когда он выполнял запись в память дисплея.

У Тома не было ни логических элементов, ни достаточно времени на реализацию полного FIFO, но ему удалось реализовать FIFO глубиной в одну операцию, что позволяло процессору обгонять VGA-чип на одну операцию записи. Том не был уверен, что это даст хорошие результаты, но это было единственное, что он смог сделать, поэтому он реализовал эту систему и передал чип в производство.

Оказалось, что FIFO на одну операцию работает невероятно здорово: на то время VGA-чипы Video Seven были самыми быстрыми на рынке; они стали доказательством гениальности Тома и свидетельством того, на что способен творец под давлением обстоятельств. Однако самое замечательное в этой истории то, что конструкция FIFO компании Paradise не имела ничего общего с конструкцией Тома, и совершенно не работала. Paradise вставила FIFO-буфер чтения между памятью дисплея и стадией вывода видео VGA-чипа, что позволяло заранее выполнять считывание вывода видео, чтобы когда ЦП нужно было получить доступ к памяти дисплея, пиксели можно было брать из FIFO, а команда ЦП выполнялась мгновенно. Это и в самом деле повысило производительность, но не так сильно, как FIFO-буфер записи Тома.

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

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

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

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

Хорошая иллюстрация: эволюция трёхмерного графического движка Quake.

Самая сложная в мире задача трёхмерной графики

Последние семь месяцев я провёл в работе над Quake, наследником DOOM от компании id Software, и я предполагаю, что спустя ещё три месяца, ко времени прочтения вами этой статьи, Quake уже выйдет в виде shareware.

С точки зрения графики Quake станет для DOOM тем, чем DOOM был для его предшественника — Wolfenstein 3D. Quake добавляет настоящее произвольное 3D (игрок может смотреть вверх и вниз, наклоняться в стороны и даже падать набок), детализированное освещение и тени, 3D-монстров и персонажей вместо спрайтов DOOM. Скоро я расскажу обо всём этом подробнее, но в этом месяце я хочу поговорить о задаче, которую в своей книге называю самой сложной в трёхмерной графике: определении видимых поверхностей (отрисовке соответствующей поверхности для каждого пикселя), и об очень близкой к ней задаче — об отсечении (максимально быстром отбрасывании невидимых полигонов как способе ускорения определения видимых поверхностей). Ради краткости для обозначения определения видимых поверхностей (visible surface determination) и отсечения (culling) я буду использовать аббревиатуру VSD.

Почему я считаю VSD самой сложной задачей 3D-графики? Хотя задачи растеризации, например, наложение текстур, столь же потрясающи и важны, они имеют довольно ограниченные масштабы, и после возникновения 3D-ускорителей их решение будет перенесено в «железо»; кроме того, их масштаб зависит только от разрешения экрана, то есть они довольно скромны.

В противовес им, VSD является неограниченной задачей и для её решения сейчас используются десятки подходов. Но намного важнее то, что производительность VSD в наивном решении масштабируется в зависимости от сложности сцены, которая обычно возрастает как квадратическая или кубическая функция, поэтому быстро становится ограничивающим фактором создания реалистичных миров. Я считаю, что в следующие несколько лет VSD будет становиться всё более доминирующей проблемой в 3D-графике реального времени для PC, ведь детализация 3D-миров будет постоянно возрастать. Уже сегодня уровень Quake солидных размеров может содержать порядка 10 000 полигонов, то есть почти в три раза больше, чем в сравнимом по размеру уровне DOOM.

Структура уровней Quake

Прежде чем углубляться в VSD, позвольте упомянуть о том, что каждый уровень Quake хранится как одно громадное трёхмерное BSP-дерево. Это BSP-дерево, как и любое другое BSP, подразделяет пространство, в данном случае по плоскостям полигонов. Однако в отличие от BSP-дерева, которое я демонстрировал ранее, BSP-дерево в Quake хранит полигоны не в узлах дерева, как часть разделяющих плоскостей, а в пустых (незаполненных) листьях, как показано на рисунке 1 в виде сверху.


Рисунок 1. В Quake полигоны хранятся в пустых листьях. Тёмные области — это заполненные листья (заполненные объёмы, например, внутренности стен)

Верный порядок отрисовки можно получить, отрисовывая листья в BSP-порядке «спереди назад» или «сзади вперёд». Кроме того, поскольку BSP-листья всегда являются выпуклыми, а полигоны являются границами BSP-листьев, смотрящими внутрь, полигоны любого листа никогда не могут перекрывать друг друга и их можно отрисовывать в любом порядке. (Это общее свойство выпуклых многогранников.)

Отсечение и определение видимых поверхностей

В идеале процесс VSD должен работать следующим образом: во-первых, нужно отбросить все полигоны, которые находятся за пределами пирамиды видимости, а также отсечь все невидимые части полигонов, которые видимы частично. Затем нужно отрисовать только те пиксели каждого полигона, которые на самом деле видимы с текущей точки обзора, как показано на рисунке 2 в виде сверху, не тратя времени на многократную перерисовку пикселей; заметьте, насколько мало множество полигонов на рисунке 2, которые необходимо отрисовать. И, наконец, в идеальном мире проверки видимости частей полигонов должны быть незатратными, а время обработки должно быть одинаковым для всех возможных точек обзора, благодаря чему игра работает плавно.


Рисунок 2. Идеальная архитектура VSD отрисовывает только видимые части видимых полигонов.

В процессе выполнения этой задачи легко определить, какие из полигонов находятся полностью за пределами пирамиды видимости или частично отсечены, и вполне можно точно выяснить, какие конкретно пиксели нужно отрисовать. Увы, мир далёк от идеала, и все эти проверки требуют затрат, поэтому хитрость заключается в том, чтобы ускорять или пропускать разные проверки, всё равно создавая при этом необходимый результат.

Как я подробно объяснял в предыдущих статьях, имея BSP, можно легко и малозатратно обойти мир в порядке «спереди назад» или «сзади вперёд». Простейшее решение VSD заключается в простом обходе дерева сзади вперёд, усечении каждого полигона пирамидой видимости и его отрисовке, если его грань направлена в камеру и не отсечена полностью (алгоритм художника). Но является ли это адекватным решением?

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

К счастью, у этой конкретной проблемы есть хороший обходной путь. Как сказано выше, каждый лист в BSP-дереве описывает выпуклое подпространство, а соединённые с листом узлы ограничивают пространство. Менее очевидно то, что каждый узел в BSP-дереве тоже описывает подпространство — подпространство, состоящее из всех дочерних элементов узла, как показано на рисунке 3. Можно воспринимать это таким образом: каждый узел разбивает на две части подпространство, созданное узлами, расположенными выше в дереве, а дочерние элементы узла ещё дальше раскраивают это подпространство на все листья, исходящие из узла.


Рисунок 3: Узел E описывает затемнённое подпространство, которое содержит листья 5, 6, 7 и узел F.

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

То есть отсечение по пирамиде видимости не является проблемой, а для отрисовки сзади вперёд можно использовать BSP. Так в чём же проблема?

Перерисовка

Проблема, с которой столкнулся при разработке Quake главный автор технологий DOOM и Quake Джон Кармак, заключалась в том, что в сложном мире у множества сцен в пирамиде видимости есть огромное количество полигонов. Большинство из этих полигонов частично или полностью перекрываются другими полигонами, но описанный выше алгоритм художника требует отрисовки каждого пикселя каждого полигона в пирамиде видимости. При этом они часто отрисовываются только для того, чтобы быть перерисованы другими. В уровне Quake из 10 000 полигонов легко получить наихудший случай перерисовки, когда пиксели отрисовываются 10 или больше раз; то есть в некоторых кадрах каждый пиксель в среднем будет отрисовываться 10 или больше раз. Никакой растеризатор не обладает достаточной скоростью для компенсации порядка величин, необходимых для отрисовки сцены; хуже того, алгоритм художника создаёт огромные различия производительности между наилучшим и наихудшим случаями, что приводит к значительному изменению частоты кадров при перемещении зрителя.

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

Когда в начале марта я пришёл в id, у Джона уже был прототип движка и намеченный план, поэтому я предполагал, что наша работа будет заключаться просто в завершении и оптимизации этого движка. Однако если бы я знал историю id, то мог сообразить, что к чему. Джон создал не только DOOM, но и движки для Wolf 3D и нескольких других предыдущих игр, а также в процессе разработки изготовил несколько разных версий каждого движка (однажды он создал четыре движка за четыре недели), то есть за четыре года он написал примерно 20 движков. Неуёмное стремление Джона ко всё более новым и качественным технологиям движка Quake закончится только после выпуска игры.

Спустя три месяца после моего прихода в движке остался только один элемент исходной структуры VSD, а желание Джона «пробовать новые вещи» зашло так далеко, что мне никогда не доводилось видеть такого раньше.

Пучковое дерево

В первоначальном проекте Quake Джона отрисовка выполнялась спереди назад с использованием второго BSP-дерева, отслеживающего уже отрисованные и ещё пустые части экрана, которые нужно было закрасить оставшимися полигонами. Логически можно считать это BSP-дерево двухмерной областью, описывающей заполненные и пустые части экрана, как показано на рисунке 4, но на самом деле это трёхмерное дерево, известное под названием «пучковое дерево» (beam tree). Пучковое дерево — это набор 3D-секторов (пучков), ограниченных плоскостями, проецируемые из какой-то центральной точки (в нашем случае — точки обзора), как показано на рисунке 5.


Рисунок 4. Пучковое дерево Quake эффективно разбивает экран на 2D-области


Рисунок 5. Пучковое дерево Quake состоит из 3D-секторов, или пучков, проецируемых из точки обзора к рёбрам полигонов.

В проекте Джона пучковое дерево изначально состоит из одного пучка, описывающего пирамиду видимости; всё за пределами этого пучка считается заполненным (то есть там не нужно ничего отрисовывать), а всё внутри пучка считается пустым. При достижении нового полигона обходом BSP-дерева мира спереди назад, этот полигон преобразовывался в пучок проведением плоскостей из его рёбер через точку обзора, а все части пучка, пересекающие пустые пучки в пучковом дереве считались отрисовываемыми и добавлялись в пучковое дерево как заполненный пучок. Это продолжалось, или пока не заканчивались полигоны, или пока пучковое дерево не становилось полностью заполненным. После завершения пучкового дерева отрисовывались видимые части полигонов, попавших в пучковое дерево.

Преимущество работы с трёхмерным пучковым деревом вместо 2D-области заключалось в том, что для определения того, на какой стороне пучковой плоскости находится вершина полигона, достаточно только проверить знак векторного произведения луча к вершине и нормали к плоскости, потому что все пучковые плоскости проходят через начало координат (точку обзора). Кроме того, поскольку пучковая плоскость полностью описывается единственной нормалью, для генерации пучка из ребра полигона достаточно только скалярного произведения ребра и луча из этого ребра к точке обзора. Наконец, для описанного выше группового отсечения по пирамиде видимости можно использовать ограничивающие сферы BSP-узлов.

Поначалу свойство пучкового дерева (завершение, когда пучковое дерево становится заполненным) казалось привлекательным, потому что похоже было, что оно ограничит производительность в наихудших случаях. К сожалению, по-прежнему были возможны сцены, в которых можно было увидеть всё вплоть до неба или задней стены мира, поэтому в наихудшем случае всё равно приходилось проверять все полигоны в пирамиде видимости относительно пучкового дерева. Похожие проблемы могут также возникать при небольших трещинах из-за ограничений числовой точности. На отсечение по пучковому дереву тратится довольно много времени, и в сценах с большой дальностью видимости, напиример, при взгляде с вершины уровня, общие затраты на обработку пучков снижали частоту кадров Quake до черепашьих скоростей. То есть в конце концов выяснилось, что решение с пучковыми деревьями страдает почти от тех же болезней, что и алгоритм художника: наихудший случай гораздо хуже среднего случая, и он плохо масштабируется при повышении сложности уровня.

Новый 3D-движок каждый день

После того, как пучковое дерево заработало, Джон неустанно работал над ускорением 3D-движка, постоянно стараясь улучшить его структуру, а не внося изменения в реализацию. По крайней мере раз в неделю, а часто и каждый день, он заходил в мой офис и говорил: «Прошлой ночью я не мог спать, поэтому вот что подумал...», и я знал, что он снова слегка напряжёт мой мозг. Джон пробовал множество способов улучшения пучкового дерева, и добился определённого успеха, но гораздо интереснее было изобилие абсолютно различных подходов, которые он генерировал. Некоторые из них едва упоминались, другие реализовывались за ночь или выходные напряжённого кодинга. В обоих случаях они в результате отбрасывались или эволюционировали, пока не начинали удовлетворять нужным критериям. Вот несколько примеров таких подходов. Я расскажу о них в минимальных подробностях, надеясь, что они разбудят ваше воображение так же, как FIFO-буфер компании Paradise разбудил воображение Тома Уилсона.

Подразделяющий raycast: в экран, разделённый на сетку 8x8, выпускаются лучи; это очень эффективная операция, потому что первое пересечение с поверхностью можно найти, просто ограничив луч BSP-деревом, начиная с точки обзора, пока не будет достигнут заполненный лист. Если соседние лучи не падают на ту же поверхность, то выпускается луч посередине между ними, и так продолжается, пока все соседние лучи или не упадут на одну поверхность, или не будут находиться в соседних пикселях; затем вокруг каждого луча из полигона, на который упал луч, отрисовывается блок. Этот подход очень хорошо масштабируется, и ограничивается количеством пикселей, а перерисовка не происходит. Его проблема заключается в выпадании: высока вероятность того, что небольшие полигоны окажутся между лучами и пропадут.

Безвершинные поверхности: мир представляется в виде множества плоскостей поверхностей. Полигоны косвенным образом появляются в пересечениях плоскостей и извлекаются из плоскостей на последнем этапе перед отрисовкой. Это обеспечивает быстрое отсечение и очень небольшое множество данных (по сравнению с полигонами плоскости описываются намного компактнее), но на извлечение полигонов из плоскостей уходит много времени.

Буфер отрисовки: он аналогичен z-буферу, но только с одним битом на пиксель, обозначающим, был ли уже отрисован пиксель. Это исключает перерисовку, но ценой проверки внутренним циклом в буфере, дополнительных операций записи и промахов кэша, а хуже всего то, что значительно повышается сложность кода. Варианты такого подхода: проверка буфера отрисовки по одному байту за раз и полный пропуск полностью перекрытых байтов, или ответвление каждого байта буфера отрисовки в один из 256 развёрнутых внутренних циклов для отрисовки 0-8 пикселей; в этом процессе можно теоретически воспользоваться способностью процессоров x86 выполнения параллельного перспективного дробного деления при обработке 8 пикселей.

Отрисовка на основе интервалов: полигоны растеризируются в интервалы, которые добавляются в глобальный список интервалов и отсекаются по этому списку так, что в каждом пикселе остаётся только ближайший интервал. Необходима небольшая сортировка обходом спереди назад, потому что при наличии пересечений уже находящийся в списке интервал является более близким. Это исключает необходимость перерисовки, но ценой арифметики вычисления интервалов; кроме того, каждый полигон всё равно необходимо превращать в интервалы.

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

Прорыв

В конце концов Джон решил, что пучковое дерево — это структура второго порядка, отражающая информацию, уже косвенно содержащуюся в BSP-дереве мира, поэтому он приступил к решению задачи извлечения информации о видимости непосредственно из BSP-дерева мира. Он потратил на это неделю, в процессе создав идеальную архитектуру видимости DOOM (2D), в которой один линейный обход BSP-дерева DOOM создаёт 2D-видимость с нулевой перерисовкой. Однако решение той же задачи для 3D оказалось гораздо более сложной проблемой, и к концу недели Джона уже выводили из себя возрастающая сложность и постоянные глитчи в коде видимости. Хотя решение с непосредственной обработкой BSP уже было близко к рабочей версии, оно требовало всё большей и большей доработки, а простая и чёткая архитектура никак не складывалась. Когда однажды в пятницу я уходил с работы, Джон готовился к тому, чтобы за выходные заставить работать решение с прямой обработкой BSP.

В понедельник с утра Джон выглядел как человек, прорвавшийся в иной мир, а ещё как человек, который не очень-то много спал. Все выходные он работал над решением с непосредственной обработкой BSP, и добился его удовлетворительной работы, а также сделал намётки о том, как его можно закончить. В 3:30 утра в понедельник, когда Джон лежал в кровати и размышлял о порталах, он подумал о том, что можно предварительно вычислить и сохранить в каждом листе список всех листьев, видимых из этого листа, а затем во время выполнения программы просто отрисовывать видимые листья сзади вперёд в зависимости от того, в каком листе оказалась точка обзора, полностью игнорируя все остальные листья.

Сложность заключалась в размере: изначально несжатое множество потенциально видимых листьев (potentially visible set, PVS) занимало несколько мегабайт. Однако PVS можно было хранить как битовый вектор с 1 битом на лист. Такую структуру очень легко сильно сжать с помощью простого сжатия нулевых байтов. Также Джон предложил изменить эвристику BSP так, чтобы она генерировала меньшее количество листьев. Это было противоположно тому, что я предлагал несколько месяцев назад, а именно выбору в качестве следующего разделителя полигона, разделяющего наименьшее количество других полигонов, и на по последним данным оказалось лучшей эвристикой. Подход Джона позволял ограничивать пространство за пределами уровня так, чтобы обработчик BSP мог удалять внешние поверхности, которые никогда не увидит игрок, в результате сводя размер PVS для достаточно большого уровня до 20 килобайт.

В обмен на эти 20 килобайт ускоряется отсечение листьев за пределами пирамиды видимости (потому что учитываются только листья в PVS), а для отсечения внутри пирамиды видимости нужна всего лишь небольшая перерисовка (PVS для листа содержит все листья, видимые из любой точки листа, поэтому возникает небольшая перерисовка, обычно порядка 50%, но способная доходить до 150%). Ещё лучше то, что предварительное вычисление PVS приводит к выравниванию производительности; наихудший случай теперь не намного хуже наилучшего, потому что больше не нужна дополнительная обработка VSD, только больше полигонов и возможно небольшая дополнительная перерисовка в случае сложных сцен. Когда Джон впервые показал мне свой работающий прототип, я специально запустил самую сложную сцену — то место, где частота кадров снижалась до одноразрядных чисел, и она работала плавно, без заметных замедлений.

Джон сказал, предварительное вычисление PVS стало логическим развитием подходов, которые он рассматривал, и никакого момента «эврики» не было. Тем не менее, это было открытие совершенно нового, качественно лучшего дизайна, который наряду с пока находящимся в разработке растеризатором с сортировкой рёбер, полностью устраняющим перерисовку, становится очень близким к «идеальным» требованиям, выбранным нами с самого начала.

Упрощай и пробуй что-то новое

Что же это значит? Ровно то, что я сказал в начале: упрощай и пробуй что-то новое. Предварительно вычисленные PVS проще любых других схем, которые мы рассматривали ранее (хотя предварительное вычисление PVS — это интересная задача, которую мы обсудим в другой раз). По сути, во время выполнения программы предварительно вычисленные PVS — это просто ограниченная версия алгоритма художника. Значит ли это, что такой подход не особо глубок?

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

У моего друга Криса Хекера есть теория, что все подходы в конце концов сводятся к одному, потому что все они отражают одинаковое внутреннее состояние и функционал. С точки зрения лежащих в основе теорий это верно: как бы вы ни вычисляли перспективное наложение текстур — с помощью деления или инкрементными гиперболическими вычислениями, числа выполняют одну и ту же задачу. Однако когда дело доходит до реализации, огромную разницу может внести простое смещение решения по времени, или улучшение оптимизации под возможности «железа» или кэширование. Мой друг Терье Матисен любит повторять, что «почти всё программирование можно рассматривать как упражнения в кэшировании»; именно это и сделал Джон. Какими бы быстрыми он ни делал свои вычисления VSD, они никогда бы не стали столь скоростными, как предварительное вычисление и поиск видимости. Самым умным его ходом стало то, что он отошёл от ментальности «ускорения кода» и осознал, что на самом деле можно предварительно вычислить (по сути, кэшировать) PVS и выполнять поиск по ним.

Сложнее всего в мире — отойти от привычного, достаточно хорошего решения сложной задачи и постараться найти другое, лучшее решение. Мне кажется, что для этого лучше всего пробовать новые бредовые идеи и всегда, всегда пытаться упрощать. Одна из целей Джона заключалась в том, чтобы в каждой последующей 3D-игре было меньше кода, чем в предыдущей; он считал, что если узнаёт больше, то сможет решать задачи более качественно в меньшем объёме кода.

И пока эта система у него вполне хорошо работает.

Учись сейчас, плати вперёд

Есть ещё одна вещь, которую я бы хотел упомянуть в конце статьи. Сколько себя помню, Dr. Dobb’s Journal всегда говорил о том, что обмен информацией о программировании — это Благо. Я знаю множество программистов, сделавших прыжок в своей разработке благодаря Tiny C Хендрикса, или D-Flat Стивенса, или просто из-за чтения ежегодных подшивок DDJ. (Среди них и я, например.) Многие компании вполне объяснимо рассматривают обмен информацией совсем иначе — как потенциальную потерю прибыли, и именно это делает DDJ столь ценным для сообщества программистов.

Благодаря этой философии id Software позволила мне рассказать в этой статье о том, как работает Quake даже ещё до его выпуска. И именно поэтому id выложила полный исходный код Wolfenstein 3D на ftp.idsoftware.com/idstuff/source [прим. пер.: теперь исходники выложены на github]; нельзя просто рекомпилировать код и продавать его, но сможете узнать, как работает полномасштабная успешная игра; изучите файл wolfsrc.txt из вышеупомянутого каталога, чтобы узнать подробности того, как можно использовать код.

Поэтому помните: когда это законно, в долгой перспективе обмен информацией приносит пользу всем нам. Вы можете оплатить вперёд долг за информацию, полученную здесь и в других местах, поделившись всем, чем можете, написав статью или книгу, или опубликовав знания в Сети. Никто из нас не учится в вакууме; все мы стоим на плечах великанов — Вирта, Кнута и тысяч других. Подставьте и свои плечи, чтобы строить будущее!

Справочные материалы

Foley, James D., et al., Computer Graphics: Principles and Practice, Addison Wesley, 1990, ISBN 0-201-12110-7 (пучки, BSP-деревья, VSD).

Teller, Seth, Visibility Computations in Densely Occluded Polyhedral Environments (диссертация), выложена на http://theory.lcs.mit.edu/~seth/ вместе с другими статьями про определение видимости.

Teller, Seth, Visibility Preprocessing for Interactive Walkthroughs, SIGGRAPH 91 proceedings, pp. 61-69.