В 1998 году Looking Glass Studios выпустила стелс-игру Thief: The Dark Project. В то время аппаратное 3D-ускорение только зарождалось, поэтому в процессе разработки оно не использовалось, игра рендерилась только программно.

Я был основным автором базовой технологии рендеринга Thief (хотя я и не писал рендереры объектов и персонажей), а также связанных с ней элементов. Тот же движок рендеринга, модифицированный другими людьми для использования аппаратного 3D-ускорения, также использовался для рендеринга System Shock 2 и Thief 2.

Движок был написан примерно в одно время с Quake (хотя игра вышла намного позже), и общий внешний вид сильно напоминает Quake. Многие технологии были скопированы из Quake или вдохновлялись им, но часто их работа немного или значительно отличалась.

Программный рендеринг Quake подробно задокументирован Майклом Абрашем (Michael Abrash) в серии статей, которые были переизданы в его книге Graphics Programming Black Book. Техники, использованные в Thief, никогда раньше не описывались, и я буду рад наконец рассказать о них, даже если сейчас они совершенно устарели. По возможности, я попробую описать их в связи с более известными техниками Quake.

Важные игры того времени с похожей технологией рендеринга:

• 22 июня 1996 — Quake 1 (QTest в феврале 1996 года)
  
• 22 мая 1998 — Unreal
  
• 19 ноября 1998 — Half-Life (сделанный на основе дополненного движка Quake 1)
  
• 30 ноября 1998 — Thief: The Dark Project
  

Содержание

• Видимость
• Уменьшение перерисовки
• Отсечение объектов
• Сортировка объектов
• Освещение и тени
• Модель CSG
• Реализация CSG
• Перспективное текстуриование
• Эффекты текстурирования
• Прочее

Видимость

В играх Looking Glass до Thief использовались миры на основе сеток. В System Shock 1 и Ultima Underworlds видимость рассчитывалась прохождением по сетке. Однако Thief мог иметь совершенно произвольную форму, поэтому его движок мне пришлось разрабатывать с нуля (я начал работу задолго до Thief и думал о движке даже до того, как мы выпустили Terra Nova: Strike Force Centauri).

Thief был основан на идее расчёта видимости и отсечения с помощью порталов и ячеек, опубликованной Сетом Теллером (Seth Teller) в его кандидатской диссертации 1992
года. Фактически рендерер мира Thief назвали «Portal», но поскольку у этого имени было новое популярное значение, я просто называл его «Thief» или «движок Thief» (но в движке было гораздо больше, чем просто рендерер, например, система объектов, AI, физика, и я не имел к этому ни малейшего отношения. Я не писал «движок Thief», только сам рендерер).

Изначально я исследовал эту идею как воображаемый Священный Грааль Looking Glass: разработку CRPG с открытыми и закрытыми пространствами, поскольку последние CRPG компании (Ultima Underworld 1 и 2, System Shock 1) были «закрытыми подземельями». Но у нас был и движок с открытыми пространствами для Terra Nova, к тому же многие из нас чувствовали желание рано или поздно создать гипотетическую Underworld 3 или что-то подобное с подземельями, открытыми пространствами, зданиями и всем подобным (это было ещё до Daggerfall). Пытаясь представить, как мы можем вырезать отверстие в ландшафте Terra Nova для добавления подземелий, я осознал, что порталы можно использовать для беспроблемной интеграции нескольких отдельных рендереров (например, рендереров открытых и закрытых пространств), размещая их на границах пространств. Поэтому за долгие рождественские каникулы я написал длинный документ, зафиксировав свои мысли. Думаю, потом эти мысли роились у меня в голове, и я знал, что у нас нет никаких идей о том, как реализовать мир без сеток. Поэтому показалось жизненно необходимым попробовать написать весь рендерер закрытых пространств с помощью порталов. И для исследований я создал одну реализацию.

Идея порталов и ячеек использовалась в Quake для предварительного расчёта зараннее вычисленного набора потенциально видимых объектов (PVS, potentially visible set). Она тоже описана в диссертации Сета Теллера. Но в Thief она применялась в реальном времени: Thief заранее вычислял порталы и ячейки, но не рассчитывал никакую дополнительную информацию о видимости. (Полагаю, что в Descent, которая была выпущена ещё до начала работы над движком Thief, это реализовано, но я не знаю подробностей.)

Движок Thief хранил модель уровня с открытыми пространствами (которые игрок мог видеть и/или ходить по ним), разделёнными на выпуклые многогранники, называемые «ячейками». Каждая ячейка содержала от нуля и более видимых «полигонов мира» вдоль границ ячейки, которые являлись видимыми поверхностями мира. Ячейки, соединённые с другими ячейками, имели особые граничные полигоны, называемые «порталами», которые помечали соседство между ячейками. Если игрок может видеть внутри заданной ячейки, то он может видеть и внутри соседних ячеек через порталы в них.

Для определения того, какая часть уровня видима в данный момент и требует рендеринга, движок выполнял поиск в ширину порталов и ячеек, начиная с точки обзора. После прохождения всех порталов достигнутые ячейки добавлялись в список видимых. Каждый рассмотренный портал преобразовывался в 3D, потом его проверяли на обращённость задней стороной, если он не был обращён, то проецировался в 2D. Затем генерировался «граничный восьмиугольник», состоящий из обычных двухмерных ограничивающих прямоугольников и ограничивающего прямоугольника, повёрнутого на 45 градусов.

Если портал вёл из ячейки A в ячейку B, то мы сравнивали граничный восьмиугольник портала с граничным восьмиугольником видимости ячейки A. Если они не пересекались, то портал был невидим. Если он был видим, то пересечение восьмиугольника ячейки A и восьмиугольника портала было частью ячейки B, которая видима через этот портал, поэтому добавлялась в список. (Было возможно, что игрок видит внутри ячейки B по разным путям, поэтому движок должен был накапливать все видимые области, что он делал, просто сохраняя консервативный граничный восьмиугольник всех восьмиугольников входящих путей вдоль путей. Если у игрока были два небольших пути видимости в одну ячейку, пути, находящихся на противоположных концах ячейки, то граничный восьмиугольник становился намного больше, обычно размером со всю ячейку.) Ячейка, содержащая точку обзора, считалась всегда видимой.

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

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

Уменьшение перерисовки

Quake уменьшал перерисовку с помощью техники буферизации интервалов («списка граней»), в которой поверхности мира (концептуально) рисовались спереди назад и каждый пиксель прорисовывался только один раз.

Thief отрисовывал полигоны сзади вперёд, поэтому они перерисовывали друг друга. Перерисовка движком Thief уже была меньше по сравнению с «наивной» перерисовкой Quake (по заранее заданному списку граней) благодаря более жёстким границам прохода порталов, описанным выше.

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

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

2D-обрезка до граничного восьмиугольника означала, что многие полигоны Thief в результате рендерились как 8-сторонние полигоны. Это создавало проблемы. Фактически, обрезка была понятной и эффективной, потому что это было всего лишь 2D вдоль простых осей, и на вершинах полигонов не было координат текстур S,T (например, U,V), ведь в Thief использовалась техника, которую я описал в PC Game Programmer's Encyclopedia. По этой технике координаты текстур задавались как базис 3D-векторов, независимых от вершин, после чего координаты текстур для интервалов и пикселей вычислялись непосредственно из векторных базисов.

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

Отсечение объектов

При перемещении объектов по уровню движок должен отслеживать, в каких ячейках находился объект. Он делает это инкрементно: используя ячейки, в которых объект был ранее, движок принимает текущее решение. Это значит, что эта часть движка могла на самом деле обрабатывать произвольные нереалистичные топологии (в которых порталы могут вести к пространствам не непоследовательно, и сворачивать пространство на себя), потому что «физика» могла выполнять такие локальные операции перемещения, но у нас никогда не было сособа реализовать такие фокусы. Позже мы начали использовать BSP-дерево для сортировки ячеек, что требовало их последовательного определения. Сам движок Thief в любом случае их не поддерживал. (На самом деле у нас был способ реализовать такие штуки: перед написанием этого движка я создал портальный движок в стиле Doom, поддерживающий пространства над пространствами. Он позволял создавать накладывающиеся друг на друга комнаты, которые могли иметь разную высоту (полагаю, в Dark Forces использовалась похожая технология) или ту же высоту (потому что на самом деле высота не влияла на работу этого движка в стиле Doom). С помощью своих коллег я даже создал для него редактор, поэтому смог позже использовать его уровни в новом, полностью трёхмерном движке. Но у нас никогда не было возможности сделать полностью трёхмерные уровни с такими свойствами.)

После определения всех ячеек, которые должны были рендериться, Thief решал, какие объекты нужно рендерить. Рендерить нужно было только объекты, находящиеся в видимых ячейках. Однако Thief также вычислял ограничивающий 2D-прямоугольник (или восьмиугольник) каждого потенциально видимого объекта и сравнивал его с граничным восьмиугольником всех ячеек, содержащих объект. (В Quake не происходило ничего такого, потому что он не обрабатывал порталы в реальном времени.)

Поскольку движок Thief лучше справлялся с полным отбрасыванием невидимых ячеек,
он мог отсекать объекты, которые в данный момент были невидимы, хотя и находились в видимых ячейках. Thief в общем случае мог обрабатывать более плотно заполненные объектами миры, чем позволял рендерер с технологией Quake. Может быть, мы и не смогли бы отобразить больше объектов на экране, но их можно было разместить на уровнях, потому что движок ограничивал только количество видимых объектов. Благодаря этому в Thief можно было создавать плотно заставленные объектами кухни, обеденные столы и шкафы.

Но на самом деле нам просто повезло, ведь мы выбирали алгоритмы не специально для этой цели. Разработка движка выполнялась намного раньше, чем постепенно начали проявляться черты гейм-дизайна Thief.

Сортировка объектов

В Quake объекты рендерились генерированием z-буфера из полигонов мира (даже несмотря на то, что полигоны мира не проходили z-тестирование) с последующим тестированием и обновлением этого z-буфера при рендеринге объектов.

В Thief z-буфер не используется. Вместо этого Thief отрисовывал мир сзади вперёд («алгоритм художника»), и перемежал рендеринг полигонов мира и объектов, чтобы они правильно отсекали друг друга.

Во многих играх эры программного рендеринга (где редко применялись z-буферы) возникали проблемы сортировки: объекты становились видимыми через стены или невидимыми перед стенами. Этого происходить не должно, а порталы/ячейки не гарантируют отсутствия таких ошибок. (Например, они проявлялись в Descent.)

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

Я не помню подробностей, но постараюсь в общих чертах рассказать о некоторых проблемах и его работе.

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

Благодаря BSP-дереву не было опасности того, что полигоны мира будут рендериться в неправильном порядке, но существовала вероятность неправильной сортировки объектов относительно друг друга или полигонов мира. Чтобы избежать этого, движок Thief (тут я снова не уверен) присваивал ячейкам номера в порядке отрисовки. Объект в ячейке N обычно должен был рендериться сразу после отрисовки (направленных внутрь) полигонов мира в ячейке N и перед отрисовкой стен ячейки N+1. Однако иногда объекты принадлежали нескольким ячейкам. Объект в ячейках M и N, где M < N, должен отрисовываться после всех стен ячейки M, но его части в ячейке M могут быть заслонены стенами в ячейке N или в любой из ячеек между M и N. (В голову приходит частый пример: коридор (ячейка) с нишей (ячейка), в которой есть факел. Факел слегка выдаётся в коридор. Ниша — это M, а коридор — N. Например, если точка обзора находится в коридоре, то коридор «ближе» к точке обзора в отношении рендеринга сзади вперёд. Например, одна из стен коридора может перекрывать части ниши.)

Чтобы справиться с такими трудностями, Thief принимал решение, приемлемо ли отрисовывать данный объект в самой ближней ячейке N (или, в сущности, в любой точке порядка отрисовки между самой дальней и самой ближней). Для этого от вычислял граничные восьмиугольники для объектов и полигонов и проверял, перекрываются ли полигоны объектами. Если полигон мира должен быть «впереди» объекта и граничные восьмиугольники пересекались, то было небезопасно перемещать объект в порядке рендеринга позже, чем полигон мира.

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

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

В Thief был совершенно другой, чрезвычайно затратный механизм, на который движок полагался для разрешения сложных проблем сортировки. Каждый объект можно было «разделить» на несколько частей, по одной на ячейку. В каждой ячейке рендерилась только та часть объекта, которая содержалась в этой ячейке. Это выполнялось не действительным разделением объекта, а множественным рендерингом, по одному на каждую «часть». Также для каждой части выполнялась динамическая обрезка объекта «пользовательской плоскостью обрезки» с помощью технологии, похожей на обрезку по пирамиде видимости (которая тоже выполялась). В сложных случаях требовалось несколько плоскостей обрезки. Однако это было необходимо только для обрезки до порталов между ячейками, в которых находился объект, и обрезка не производилась буквально по всем плоскостям, задающим каждую ячейку. Если эта техника применялась, то часть объекта могла всегда отрисовываться в ячейке или после неё. Однако, хотя это не увеличивало количество вычислений на пиксель, но требовало множественной трансформации и обрезки объекта, поэтому было довольно затратным. (Поэтому я советовал дизайнерам располагать факелы полностью в нишах.) Это было особенно плохо при рендеринге персонажей, ведь у них был скиннинг. Думаю, из-за этого приходилось несколько раз выполнять трансформации скиннинга.

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

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

После моего положительного опыта с пользовательскими плоскостями обрезки меня долгое время расстраивало, что графические процесоры не могут эффективно/удобно поддерживать их. (Даже в D3D9 они всё ещё выполнялись в пиксельном шейдере, хотя можно было использовать z-буфер и шаблон для более точного отсечения и уменьшения расчёта пиксельных шейдеров.)

Освещение и тени

Базовая техника рендеринга полигонов с наложенными текстурами и качественными предварительно рассчитанными тенями очень похожа (аналогична?) использованной в Quake. Для хранения освещённых поверхностей в Thief использовались карты освещения и кэш поверхностей. Советую изучить эту тему в заметках Майка Абраша.

Насколько я помню, эту технику добавили в движок после того, как мы (команда разработчиков Thief) увидели релиз «QTest» Quake. Однако я сомневаюсь, что в тот момент уже существовала команда разработки Thief. По данным Википедии, QTest вышел 24 февраля 1996 года. Terra Nova вышла 5 марта 1996 года, так что я думаю, что мы собрали финальную версию Terra Nova ко времени выпуска QTest. Но не припомню, что у нас уже была целая команда. На самом деле я не уверен, когда точно я создал исходную исследовательскую версию этого движка.

Объекты испускали лучи ко всем (или N верхним) источникам света для определения их видимости. В зависимости видимости объекта от источника, для него включалось или отключалось всё освещение. Так мы симулировали вход или выход объектов из тени. Но я не знаю, выпустили ли мы игру с этой техникой, или использовали проверку карты освещения на полу. Как мне помнится, мы по крайней мере применяли такую проверку, чтобы определять видимость игрока для охранников. Благодаря этому игрока не могли сбить с толку места, которые внешне выглядели находящимися в тени.

Модель CSG

Уровни Thief создавались с помощью методов конструктивной сплошной геометрии (Constructive Solid Geometry, CSG), основанных на знаниях о работе Quake. Однако технологически реализация Thief сильно отличалась от Quake.

Модель CSG в Thief была «временнoй». Лучше объяснить это на примере аналогии с Photoshop. В Photoshop есть слои. Объекты, расположенные на одном слое, перекрывают объекты на нижних уровнях, если только не используются более интересные модели смешивания. В таком случае объекты в слоях изменяют видимые объекты под ними, но не влияют на объекты над ними.

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

Обычно мы воспринимаем модель слоёв Photoshop как стек 2D-слоёв, но вместо этого можно считать вышеописанный алгоритм моделью, и думать о слоях не как о «вертикальном» стеке, а как о порядковой последовательности операций для выполнения. Именно это я и имею в виду под «временнoй» моделью, которая использовалась в Thief для CSG. (Если вертикальный стек слоёв Photoshop — вертикальное третье измерение двухмерных изображений, то модель слоёв Thief будет четвёртым измерением 3D-форм, и воспринимать его как четырёхмерное пространство не очень эффективно.)

CSG Thief получает в качестве входных данных наборы «операций», выстроенных в порядке выполнения. Эти операции являлись «расположениями кисти», где кистью было трёхмерное выпуклое твёрдое тело, а также характеристикой того, как область, покрытая этим твёрдым телом, будет изменена операцией. Всё пространство сначала твёрдое, поэтому одной операцией кисти была «вырезать в этой области отверстие», другими словами, «изменить область, покрытую этой кистью, чтобы освободить его». Например, такую операцию используют для вырезания комнаты. Другая операция располагала твёрдое тело, можно было использовать её для размещения колонны. Другая операция добавляла воду. Ещё одна — лаву. Поскольку пространство могло быть одного из 4 типов (твердь, воздух, вода или лава — эй, это же 4 классических элемента!), каждую операцию можно рассматривать по тому, какой тип вывода она создавала. Кроме того, мы сделали эти операции селективными. Например, «кисть заливки» превращала воздух в воду, но не затрагивала остальные типы. Это упрощало заполнение области водой — можно было создать её полностью из воздуха, а потом залить нижнюю часть водой. Благодаря временнoму аспекту можно было затем при желании изменить часть воды на «воздух». Можно было создавать более сложные типы кистей (воздух превратить в воду, воду — в твердь, твердь — в воздух, а лаву не трогать), но это не было особо полезно, поэтому, как мне кажется, основными типами кистей были «безусловные однотипные» и «условные однотипные».

Как и в слоях Photoshop, временнoй аспект управлялся пользователем: можно было переместить кисть вперёд или назад во времени. К сожалению, это было намного сложнее визуализировать (окна «слои» у нас не было). Не знаю, насколько радовала дизайнеров такая система.

Если сравнить с Quake, то уровень в нём начинался с полностью открытого пространства, в котором располагались твёрдые объекты. Там использовалась более традиционная для CSG операция явного вычитания. Вода создавалась первым по времени использованием всех кистей воды, поэтому эффективная временнaя последовательность операций выглядела так: только воздух => часть воздуха превращается в воду => размещение всех твёрдых частей. Поскольку вычитание было явным для «твёрдых» кистей до того, как они добавлялись в мир, вычитание не могло «случайно» удалить воду, поэтому необходимости в явной временнoй модели не было (набор доступных действий в Quake был более ограничен, но на практике в нём поддерживалось почти всё нужное. Но несмотря на большее количество действий в Thief, дизайнеры иногда шли на довольно странные последовательности операций для создания сложных форм).

Поскольку уровни Quake изначально пусты, в игре были невидимые «внешние» поверхности, требовавшие отдельного процесса обнаружения и удаления. Если уровень не был герметичным, то внешних поверхностей можно было достичь. При этом автоматизированные инструменты не могли удалить их. В Thief уровни изначально «твёрдые», поэтому необходимости в этом никогда не было. (Думаю, CSG в Unreal тоже изначально «твёрдая».)

Реализация CSG

Я понятия не имел о том, что делал, когда реализовывал систему CSG Thief (несмотря на возможность забросать вопросами Джона Кармака), поэтому сделал ужасный выбор. Система Thief разделяла мир на выпуклые многогранники и отслеживала тип каждого многогранника (воздух, твердь, вода, лава, которые я называл «средами»). Для этого я хранил мир как неизменяемое BSP-дерево. BSP-дерево классифицирует пространство как выпуклые многогранники (за исключением граней, в которых мир может иметь неограниченные формы, расширяющиеся до бесконечности).

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

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

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

В процессе разработки Thief я изменил все значения в движке CSG с float на double и уменьшил эпсилон-проблему. Всё стало лучше, что позволило улучшить работу, но не решило проблему совершенно. Однако теперь я осознаю, что гораздо лучше было бы совсем отказаться от BSP-дерева.

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

Перспективное текстурирование

В играх Looking Glass до Thief, таких как System Shock 1 и Terra Nova, для перспективного текстурирования использовался преобразователь «линий с постоянной Z».
В таких играх обычно использовали перспективное текстурирование для больших близких полигонов, а для дальних полигонов — аффинное преобразование.

В Thief использовался специально написанный перспективный преобразователь для всех полигонов. В нём применялся трюк, использованный в Quake: деление с плавающей запятой для перспективной коррекции для каждых N, которое выполнялось параллельно с наложением текстур следующих N. Трюк работал, потому что Pentium мог выполнять деление с плавающей запятой «в фоновом режиме», если после него использовались только целочисленные инструкции.

В Thief перспективная коррекция выполнялась для каждых 8 пикселей (т.е. N было равно 8). Движок Thief подстраивал коррекцию таким образом, чтобы она выполнялась для пикселей, координата X которых была кратна 8. Начало и конец диапазона пикселей могли быть меньше 8, тогда вызывался общий N-пиксельный преобразователь, но для 8-пиксельных диапазонов вызывалась процедура, предназначенная для вычисления ровно 8 пикселей.

Поскольку движок менялся со временем и изначально был предназначен для исследований, он поддерживал два разных формата хранения текстур. Один был ограничен текстурами размером 256x256, или, скорее текстурами с размерами степени двойки, сдвиг которых всегда был равен 256. Этот формат использовал внутренний цикл, похожий на тот, который я написал для PCGPE (PC Games Programmers Encyclopedia). Второй формат поддерживал произвольные текстуры, размеры которых необязательно являлись степенями двойки, но не поддерживал свёртывание. Именно его мы и выбрали, когда добавили кэшированное освещение поверхностей, потому что использование для этого текстур, кратных 256, было бы слишком затратным. Думаю, что трюк с индексацией переносом флага, использованный в этом преобразователе, я взял непосредственно у Майка Абраша.

Подробности для x86-программистов:

Вот код для второго пикселя в преобразователе текстур с размером, не являющимся степенью двойки, с развёрткой для 8 пикселей:

adc    ebx,edi
add    eax,ebp

sbb    edi,edi   ; сохранение переноса координаты v
add    esi,edx   ; обновление u

mov    byte ptr _pt_buffer+1,al
mov    al,[ebx]

mov    edi,_pt_step_table[edi*4+4]

Вот код для второго пикселя преобразователя текстур размером 256x256 с развёрткой для 8 пикселей (не использовался в релизе игры, может быть, применялся только для поверхности воды):

add    esi,edx
mov    ecx,ebx

adc    bl,dl
add    eax,ebp

adc    bh,dh
mov    al,[edi+ecx]

mov    byte ptr _pt_buffer+1,al
and    ebx,0babebeach

Интервалы в обоих фрагментах кода показывают, что они оптимизированы для Pentium. В каждом из них используются номинальные 4 цикла на пиксель. (Кроме того, они оба приводят к срабатыванию «частичного простоя регистров» в Pentium Pro.) В Pentium был двухцикловый простой «AGI», при котором нельзя было использовать регистр в течение двух циклов после его вычисления, поэтому видна выборка текстуры (из ebx или edi+ecx), предназначенная для вычисления этих регистров за два цикла до выборки. Полные 8-пиксельные процедуры используют пары инструкций Pentium 32 и 33 для 8 пикселей (хотя также существует возможность записывать правильные значения в нужные регистры).

0babebeach в конце — это константа в стиле 0xdeadbeef, полагающаяся при обновлении константы на «самомодифицирующийся» код. Это стандартный трюк для 486 и Pentium. Этот процессор имеет инструкцию «and ebx,memory_location», но она не одноцикловая, а «and ebx,#immediate» — одноцикловая. Это означало, что в коде нужно было изменить 9 фрагментов (это цикл развёрток для 8 пикселей, плюс цикл без развёрток), но текстура изменялась только после этого.

К сожалению, я совершенно упустил возможность реблокировки текстуры для улучшения использования кэша, что могло бы значительно повысить производительность (но я не уверен в этом). Я слышал, что в Build и других движках этот процесс выполнялся, и поскольку кэш поверхностей Thief состоял из блоков 8x8, наверно, поддержку такого процесса было не так сложно реализовать.

Эффекты текстурирования

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

В этот момент можно было вызвать один из двух типов функций. Наиболее частым был тип, записывающий в «буфер кадра» (который на самом деле был областью ОЗУ, переносимой позже на экран) и возвращающийся из исходной функции, вызвавшей цепочку преобразователя текстур. Другой тип функций считывал пиксели из временного буфера, модифицировал их и записывал обратно во временный буфер, а затем переходил к ещё одной функции. Теоретически можно было связать произвольные числа этих функций обработки, но на практике это не пригодилось.

В базе кода было множество таких функций:

• сэмплер для диапазона с аффинным сэмплингом смещения=256 с свёрткой текстурных координат
  
• сэмплер для диапазона с аффинным сэмплингом для произвольного смещения без свёртки и обрезки
  
• сэмплер для произвольного смещения с поиском по таблице освещения (он получал 8 различных значений освещения из временного буфера освещения)
  
• фильтр, добавлявший 8 различных 8-битных «значения палитрового освещения» из временного буфера освещения к 8 значениям текстур во временном буфере и сохранявший данные снова во временный буфер (просто две 32-битные операции суммирования)
  
• фильтр, пропускавший 8 значений текстур из временного буфера через произвольную таблицу перераспределения (таблицу поиска цветов) и сохранявший данные обратно в буфер
• функция записи в буфер кадра (32 бита за раз)
  
• функция, записывающая ненулевые значения в буфер кадра для прозрачности (использовала операцию, тестирующую за раз 4 бита на наличие нулей, поэтому была особенно эффективной, когда всё было полностью непрозрачным или полностью прозрачным)
  
• функция, пропускавшая значение в буфере кадра и значение во временном буфере через произвольную таблицу перераспределения (использовалась для эффектов «просвечиваемости»)
  

и несколько других заданных комбинаций, плюс функции для генерирования затенения по Гуро во временном буфере освещения. (И две версии каждого описанного выше типа — один с развёрткой для 8 пикселей, один для произвольных N пикселей для обработки начала и конца каждого диапазона пикселей.)

Думаю, большинство из них не использовались. В частности, палитровое освещение требовало особой настройки палитры, и я использовал его в исходном исследовательском движке для демо уровня с затенением по Гуро, работавшего на Pentium 90 при разрешении 640x400 с частотой примерно 20 кадров в секунду. Уровень представлял собой перетекстурированную версию E1M1 из Doom 1, в нём использовалась текстура, созданная Куртом Бикенбахом (Kurt Bickenbach). Мы с ним немного поэкспериментировали, пытаясь выяснить, как заставить восьмибитные текстуры выглядеть качественными и не слишком чередующимися с помощью палитрового освещения. У нас получились довольно приятные результаты, но в конце концов палитровое освещение оказалось слишком ограниченным, поэтому мы отказались от него. (Оно очень ограничивало с художественной точки зрения и не могло правильно отображать чёрный цвет. Когда мы пришли к идее игры, связанной с тенями, такое освещение очевидно оказалось совершенно неправильным, но я думаю, что мы отказались от него задолго до возникновения первых проблем.) Отказ от него означал также и отказ от соответствия полученным частоте кадров и разрешению, но в дальней перспективе это было не очень важно, потому что игры LGS были достаточно сложны и 95% времени обработки кадра всё равно проводилось не в рендерере. Кроме того, игра ещё была далека от завершения.

В движке имелась возможность указать произвольную таблицу поиска цветов (color look-up table, «clut») для каждого портала. Она позволяла раскрасить всё, видимое через портал с помощью этой таблицы. Этот процесс выполнялся не применением раскраски поверхности портала в постобработке. Такой подход потребовал бы дополнительной скорости заполнения. Поэтому вместо этого таблицы поиска сохранялись (и конкатенировались в новые таблицы), а затем применялись при рендеринге поверхностей, видимых через портал. Этот эффект можно было использовать для силовых полей и тому подобного, хотя в результате он применялся редко. (Однако надо заметить, что если одна ячейка была видима через несколько маршрутов, и у этих маршрутов были разные последовательности таблиц поиска, то не было корректного способа отрендерить её: движок Thief выбирал таблицы случайным образом. Возможно, у этой проблемы не было хорошего решения, но так как она никогда не проявлялась, это не имело значения.)

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

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

Не знаю точно, что происходило с объектом, который выдавался из воды. Думаю, для него принудительно использовалась динамическая пользовательская плоскость обрезки. Поскольку в Quake использовался z-буфер, там в одном пикселе не могли быть видимы одновременно дальняя подводная стена и поверхность воды (z-буфер может хранить только одну глубину). Поэтому поверхность воды в Quake была непрозрачной, по крайней мере, в программном рендерере. Не уверен, добавилась ли такая возможность в производных от Quake движках, например, как в Half-Life. Один из вариантов затратных решений такой: рендерить весь мир кроме воды, затем рендерить объекты, и, наконец, рендерить прозрачную воду через z-буфер (почти как это делается аппаратно). Эффект прозрачной воды с z-буфером должен был быть гораздо более затратным, чем в подходе Thief, хотя в Thief тратится больше ресурсов на треугольник/вершину, потому что приходится рендерить объект несколько раз.

В Thief большинство поверхностей использовало сэмплер без сворачивания с произвольным смещением и простую функцию записи из хранилища в память.

Думаю, рендереры объектов использовали общие библиотеки программного рендеринга LGS, поэтому я вообще не применял эти преобразователи.

Прочее

Я описал не все графические технологии, использованные в Thief. Ниже я перечислю всё то, о чём не написал. Я связываю каждую их техник с тем сотрудником LGS, который создавал её, но не уверен, что эти люди были единственными. Поэтому, чтобы не рисковать и не пропустить никого из тех, кто внёс вклад, я просто не буду называть имён, ведь в работе могло участвовать несколько человек.

Система 3D-камеры, трансформация вершин и обработка обрезки были частями общей технологической библиотеки, использовавшейся во всех продуктах LGS. (Возможно, Thief стал первым «пользователем» этой технологии — в предыдущих играх использовался фиксированный вид, поэтому они могли работать на компьютерах x86 без ускорения вычислений с плавающей запятой.) Thief объединял вместе все вершины, используемые в одной клетке, и трансформировал их одновременно, вне зависимости от того, были ли это видимые полигоны или порталы. Это стало возможным благодаря API 3D-вершин, позволявшему разделять подобные элементы. (Примерно как скомпилированные массивы вершин.)

Как я говорил выше, стандартный рендеринг объектов тоже выполнялся через общие библиотеки. Полигоны объектов сортировались с помощью BSP-дерева. Джеймс Флеминг (James
Fleming) написал очень умную систему, которая значительно снизила количество решений, принимаемых в BSP-узле. В системе использовался тот факт, что односторонние полигоны часто не могут перекрывать друг друга с любого угла. (Например, я думаю, что полигональный тор, являющийся самоперекрывающимся объектом и требующий сортировки, как будто полигоны двусторонние, можно статистически отсортировать, если бы он был сделан из односторонних полигонов.)

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

Я на какое-то время ушёл из Looking Glass. За моё отсутствие была добавлена поддержка аппаратного ускорения. (Я вернулся и добавил в генератор освещения поддержку цветного освещения и, может быть, кэш поверхностей или что-то подобное.)