Программист Майкл Абраш, в середине 90-х приглашённый Джоном Кармаком для работы над движком первого Quake, написал в процессе разработки серию статей. Это вторая колонка из данной серии. Перевод первой находится здесь.
Должен признаться: меня достал классический рок. В последний раз я с радостью слушал что-нибудь из Cars или Boston довольно давно, около 20 лет назад. Кроме того, меня никогда особо не привлекали Боб Сигер и Queen, не говоря уже об Элвисе, так что здесь мало что изменилось. Но я понимал, что нечто изменилось, когда мне хотелось переключить радио, услышав Allman Brothers, или Steely Dan, или Pink Floyd, или, господи, прости, Beatles (но только на таких вещах, как «Hello Goodbye» и «I’ll Cry Instead», а не «Ticket to Ride» или «A Day in the Life»; я ещё не зашёл настолько далеко). Долго искать причины этого не пришлось; я слушал одни и те же песни четверть века, и просто от них устал.
Я рассказываю это всё таким образом потому, что когда мы с моей дочерью однажды вечером ехали из кафе, в машине впервые была включена радиостанция «Альтернативы нет».
Мы говорим о десятилетней девочке, росшей на постоянной диете из старых хитов. Ей нравятся мелодии, легко запоминающиеся песни и хорошие певцы. Ничего из этого не найдёшь, слушая станцию про альтернативный рок. Поэтому неудивительно, что когда я включил радио, она первым делом сказала «Фу!»
Но вот что меня удивило: послушав какое-то время, она сказала: «Знаешь, папа, а на это на самом деле интересно».
Это не только намекнуло мне о том, какая музыка будет грохотать по всему дому, когда она станет тинейджером. Её быстрое принятие альтернативного рока (по сравнению с моим длящимся десяток лет увлечением музыкой собственной юности) напомнило мне кое о чём, что легко забывается, когда становишься старше и образ жизни становится устоявшимся. Это напомнило мне, что необходимо сохранять открытость сознания и быть готовым — более того, стремиться — пробовать новые вещи. Программисты склонны привязываться к знакомым подходам, и предрасположены использовать их, если они достаточно адекватно справляются с задачами. Но в программировании всегда есть альтернативы, и я обнаружил, что часто они стоят изучения.
Но учитывая постоянно меняющуюся природу Quake, мне вообще-то не должно было понадобиться такое напоминание.
Творческий поток
В январе я описал творческий поток, который привёл Джона Кармака к решению использовать предварительно вычисленные потенциально видимые наборы (potentially visible set, PVS) полигонов для каждой возможной точки обзора в Quake (игре, которую мы совместно разрабатываем в id Software). Предварительное вычисление PVS означает, что вместо того, чтобы тратить кучу времени на поиск в базе данных мира полигонов, видимых с текущей точки обзора, мы можем просто отрисовать все находящиеся в PVS полигоны сзади вперёд (позаимствовав порядок из BSP-дерева мира; обсуждение BSP-деревьев см. в наших колонках за май, июль и ноябрь 1995 года), и получить правильную отрисовку сцены совершенно без поиска, позволив отрисовке сзади вперёд выполнить последний этап удаления невидимых поверхностей (hidden-surface removal, HSR). Это была потрясающая идея, но для архитектуры Quake путь ещё не был завершён.
Отрисовка подвижных объектов
Например, до сих пор стоял вопрос о том, как правильно сортировать и отрисовывать подвижные объекты; на самом деле, этот вопрос после выхода январской колонки мне задавали больше всего, поэтому я уделю ему время. Основная проблема в том, что движущаяся модель может попасть в несколько листьев BSP, и при перемещении модели эти листья изменяются; наряду с возможностью нахождения в одном листе нескольких моделей, это означает, что нет простого способа, позволяющего использовать порядок BSP для отрисовки моделей в правильно отсортированном порядке. Когда я написал январскую колонку, мы отрисовывали спрайты (например взрывы), подвижные модели BSP (например двери) и полигональные модели (например монстров), усекая каждый из них листьями, которых они касаются, а затем отрисовывая соответствующие части, когда каждый лист BSP достигал своей очереди при обходе сзади вперёд. Однако это не решило проблему сортировки нескольких подвижных моделей в одном листе относительно друг друга, а также оставляло неприятные проблемы со сложными полигональными моделями.
Джон решил проблему сортировки для спрайтов и полигональных моделей на удивление низкотехнологичным способом: теперь мы записываем их в z-буфер. (То есть перед отрисовкой каждого пикселя мы сравниваем значение расстояния до него, или z, со значением z пикселя, уже находящегося на экране. Новый пиксель отрисовывается, только если он ближе уже существующего.) Сначала мы рисуем основной мир — стены, потолки и тому подобное. На этом этапе никакого тестирования z-буфера не используется (как мы вскоре увидим, определение видимых поверхностей мира выполняется другим способом); однако мы заполняем z-буфер значениями z (на самом деле значениями 1/z, о чём сказано ниже) для всех пикселей мира. Заполнение Z-буфера — это гораздо более быстрый процесс, чем была бы z-буферизация всего мира, потому что здесь нет ни считывания, ни сравнений, только запись значений z. После завершения отрисовки и заполнения z-буфера мира мы можем просто отрисовать спрайты и полигональные модели с помощью z-буферизации и получить идеальную сортировку.
Когда используется z-буфер, неизбежно возникают вопросы: как это влияет на занимаемую память и производительность? При разрешении 320x200 он требует 128 КБ памяти, нетривиально, но не так много для игры, требующей для работы 8 МБ. Влияние на производительность: около 10% при заполнении z-буфера мира, и примерно 20% (показатели сильно варьируются) при отрисовке спрайтов и полигональных моделей. Взамен мы получаем идеально отсортированный мир, а также возможность создания дополнительных эффектов, например, взрывов и дыма из частиц, потому что z-буфер беспроблемно позволяет отсортировать эти эффекты в мире. В целом, применение z-буфера значительно повысило визуальное качество и гибкость движка Quake, а также достаточно серьёзно упростило код, ценой вполне приемлемых затрат памяти и производительности.
Выравнивание и повышение производительности
Как я сказал выше, в архитектуре Quake первым отрисовывается сам мир, без считывания или сравнения z-буфера, просто заполнением z-буфера значениями полигонов мира по z. После чего поверх мира с помощью полной z-буферизации отрисовываются подвижные объекты. Пока я говорил только о том, как отрисовывать подвижные объекты. В оставшейся части колонки я поговорю о другой части уравнения отрисовки — рисовании самого мира, когда весь мир хранится как одно BSP-дерево и никогда не движется.
Как вы можете помнить из январской колонки, нас волновала и «сырая» производительность, и её усреднение. То есть, мы хотели, чтобы код отрисовки выполнялся как можно быстрее, но в то же время чтобы разница скорости отрисовки средней сцены и самой медленной в отрисовке сцены была как можно меньше. Нет ничего хорошего в средних 30 кадрах в секунду, если 10% сцен отрисовываются с частотой 5 fps, потому что дёрганность в таких сценах будет чрезвычайно заметна по сравнению со средней сценой. Лучше усреднить частоту 15 кадрами в секунду в 100% случаев, даже несмотря на то, что средняя скорость отрисовки станет в два раза меньше.
Вычисляемые заранее PVS стали важным шагом в сторону более высокой и уравновешенной производительности, потому что устранили необходимость определения видимых полигонов — достаточно медленного этапа, хуже всего проявлявшего себя в самых сложных сценах. Тем не менее, в некоторых местах реальных игровых уровней предварительно вычисленные PVS содержат в пять раз больше полигонов, чем видно на самом деле; в сочетании с выполняемым сзади вперёд устранением скрытых поверхностей (HSR) это создавало «горячие зоны», в которых частота кадров заметно снижалась. Сотни полигонов отрисовывались сзади вперёд, и большинство из них сразу же перерисовывались более близкими полигонами. «Сырая» производительность в целом тоже снижалась на средние 50% перерисовки, возникающей из-за отрисовки всего в PVS. Поэтому хотя отрисовка сзади вперёд наборов PVS сработала в качестве последнего этапа HSR и стала улучшением по сравнением с предыдущей архитектурой, она не была идеальной. Джон думал, что наверняка существует более совершенный способ использования PVS, чем отрисовка сзади вперёд.
И он на самом деле нашёлся.
Отсортированные интервалы
Идеальная последняя стадия HSR для Quake должна была отбрасывать все полигоны в PVS, которые на самом деле оказывались невидимыми, и отрисовывать только видимые пиксели оставшихся полигонов без перерисовки. То есть каждый пиксель отрисовывался бы ровно один раз и без снижения производительности, разумеется. Одно из решений (требующее, однако, затрат) заключается в отрисовке спереди назад, сохранении области, описывающей перекрытые в текущий момент части экрана и усечении каждого полигона границами этой области перед отрисовкой. Звучит многообещающе, но на самом деле это примерно напоминает решение с деревьями пучков, которое я описывал в январской колонке. Как мы выяснили, этот подход требует траты лишних ресурсов и имеет серьёзные проблемы с выравниванием нагрузки.
Можно поступить гораздо лучше, если переместить последний этап HSR с уровня полигонов на уровень интервалов и использовать решение с отсортированными интервалами. По сути, такой подход состоит из превращения каждого полигона в набор интервалов, как показано на Рисунке 1, с последующей сортировкой и усечением интервалов друг относительно друга, пока для отрисовки не останутся только видимые части видимых интервалов, как показано на Рисунке 2. Это может показаться очень похожим на z-буферизацию (которая, как я говорил выше, слишком медленна для применения в отрисовке мира, хотя и подходит для менее крупных подвижных объектов), но здесь есть важные различия. В отличие от z-буферизации, попиксельно сканируются только видимые части видимых интервалов (хотя все рёбра полигонов всё равно нужно растеризировать). Ещё лучше то, что сортировка, выполняемая z-буферизацией для каждого пикселя, становится поинтервальной операцией с отсортированными интервалами, и так как неотъемлемым свойством списка интервалов является связанность, каждое ребро сортируется только относительно некоторых интервалов в той же строке, и усекается только несколькими интервалами при горизонтальном наложении. Хотя обработка сложных сцен всё равно происходила дольше, чем простых, наихудшие случаи были не так плохи, как при использовании деревьев пучков или при сортировке сзади вперёд, потому что отсутствует перерисовка и сканирование скрытых пикселей, сложность ограничена пиксельным разрешением, а связность интервалов ограничивает сортировку наихудших случаев в любой области экрана. В качестве бонуса вывод отсортированных интервалов находится именно в том виде, который нужен низкоуровневому растеризатору: в формате набора дескрипторов интервалов, каждый из которых состоит из координаты начала и длины.
Генерация интервалов
Если вкратце, то решение с отсортированными интервалами достаточно близко соответствует нашим исходным критериям; хотя он не избавляет от затрат, они всё же не совсем ужасны. Он полностью устраняет перерисовку и сканирование пикселей перекрытых частей полигонов, и склонен к выравниванию производительности в наихудших случаях. Мы не полагались бы только на отсортированные интервалы в качестве механизма устранения скрытых поверхностей, но предварительно вычисленные PVS снижают количество полигонов до такого уровня, с которым отсортированные интервалы справляются достаточно хорошо.
Итак, мы нашли нужный нам подход; осталось только написать код и с этим покончено, правда? И да, и нет. Концептуально подход с отсортированными интервалами прост, но на удивление сложен в реализации: необходимо принять пару важных решений о дизайне, требуется немного математики и присутствуют хитрые подводные камни. Давайте сначала рассмотрим решения по дизайну.
Рёбра против интервалов
Первое решение заключается в выборе того, что нужно сортировать: интервалы или рёбра (оба этих понятия относятся к общей категории «отсортированных интервалов»). Хотя результаты в обоих случаях будут одинаковыми (список интервалов, которые нужно отрисовать без перерисовки), реализации и последствия для производительности сильно различаются, так как сортировка и усечение выполняются очень отличающимися структурами данных.
При сортировке интервалов эти интервалы хранятся в сегментах памяти отсортированных по x связанных списков, обычно по одному сегменту на растровую строку. Каждый полигон в свою очередь растеризируется в интервалы, как показано на Рисунке 1. Каждый интервал сортируется и усекается в сегмент памяти той растровой строки, в которой находится интервал, как показано на Рисунке 2, так что в любой момент времени каждый сегмент содержит ближайшие встреченные интервалы, всегда без наложений. При таком подходе необходимо генерировать все интервалы для каждого полигона по очереди, а каждый интервал сразу же сортируется, усекается и добавляется в соответствующий сегмент памяти.
Рисунок 2: интервалы из полигона A с Рисунка 1 сортируются и усекаются по интервалам из полигона B, при этом полигон A находится на постоянном расстоянии 100 по оси Z, а полигон B находится на постоянном расстоянии 50 по оси Z (полигон B расположен ближе к камере).
При сортировке рёбер эти рёбра хранятся в сегментах памяти отсортированных по x связанных списков согласно их начальной растровой строке. Каждый полигон в свою очередь разбивается на рёбра, совместно создавая список всех рёбер в сцене. Когда все рёбра всех полигонов в пирамиде видимости добавятся в список рёбер, весь список сканируется за один проход сверху вниз, слева направо. Сохраняется список активных рёбер (active edge list, AEL). При каждом шаге к новой растровой строке рёбра, оказывающиеся на этой растровой строке, удаляются из AEL, активные рёбра переходят к их новым координатам по x, рёбра, начинающиеся с новой растровой строки, добавляются в AEL, и рёбра сортируются по текущей координате x.
Для каждой растровой строки сохраняется отсортированный по z список активных полигонов (active polygon list, APL). Проходится по порядку отсортированный по x AEL. При встрече с каждым новым ребром (то есть когда каждый полигон начинается или завершается при движении слева направо), активируется связанный с ней полигон и сортируется в APL (в случае начинающего ребра), как показано на Рисунке 3, или деактивируется и удаляется из APL (в случае замыкающего ребра), как показано на Рисунке 4. Если ближайший полигон изменился (то есть ближайшим является новый полигон или ближайший полигон закончился), для полигона, только что переставшего быть ближайшим, создаётся интервал начиная с точки, где полигон является первым, потому что он ближайший и заканчивающийся в координате x текущего ребра, и текущая координата x записывается в полигон, который теперь является ближайшим. Эта сохранённая координата позже используется как начало интервала, созданного, когда новый ближайший полигон перестаёт находиться впереди.
Рисунок 3: активация полигона при обнаружении в AEL начинающего ребра.
Рисунок 4: деактивация полигона при обнаружении в AEL замыкающего ребра.
Не волнуйтесь, если не понимаете до конца описанное выше; это просто краткий обзор сортировки рёбер, чтобы остальная часть колонки была понятней. Подробное объяснение будет в следующей колонке.
Интервалы, сгенерированные при сортировке рёбер, оказываются точно такими же интервалами, которые возникли бы в результате сортировки интервалов; различие заключается в промежуточных структурах данных, использованных для сортировки интервалов в сцене. При сортировке рёбер интервалы хранятся внутри рёбер до генерации окончательного набора видимых интервалов, поэтому сортировка, усечение и создание интервалов выполняются, когда каждое ребро добавляет или удаляет полигон, на основании состояния интервала, определяемого ребром и набором активных полигонов. При сортировке интервалов интервалы мгновенно становятся явными при растеризации каждого полигона, и эти промежуточные интервалы затем сортируются и усекаются относительно интервалов в растровой строке для создания окончательных интервалов; поэтому состояния интервалов постоянно заданы в явном виде, и вся работа выполняется непосредственно с интервалами.
И сортировка интервалов, и сортировка рёбер работают хорошо, они успешно использовались в коммерческих проектах. Для Quake мы выбрали сортировку рёбер, частично из-за того, что она кажется более эффективной и имеет превосходную горизонтальную связанность, обеспечивающую минимальное время сортировки, в отличие от потенциально затратной сортировки в связанные списки, которая может потребоваться при сортировке интервалов. Однако более важной причиной стало то, что при сортировке рёбер мы можем делить рёбра между соседними полигонами, и это примерно вдвое уменьшает работу по сортировке, усечению и растеризации рёбер, а также достаточно сильно уменьшает базу данных мира благодаря тому, что рёбра становятся общими.
И последнее преимущество сортировки рёбер заключается в том, что она не различает выпуклые и вогнутые полигоны. Для большинства графических движков это не очень важный аспект, но в Quake усечение, преобразование, проецирование и сортировка рёбер стали основным узким местом, поэтому мы делаем всё возможное для снижения количества полигонов и рёбер, и в этом отношении очень помогают вогнутые полигоны. Хотя вогнутые полигоны можно обрабатывать и сортировкой интервалов, это влечёт за собой значительное снижение производительности.
Тем не менее, окончательного ответа о наилучшем подходе нет. В конце концов, сортировка интервалов и сортировка рёбер выполняют один функционал, и выбор между ними — вопрос удобства работы. В следующей колонке я подробнее расскажу о сортировке рёбер с полной её реализацией. В оставшейся части этой колонки я заложу фундамент для следующей, рассказав о ключах сортировки и вычислении 1/z. В процессе я сделаю несколько отсылок к аспектам сортировки рёбер, которые пока не были рассмотрены подробно; прошу прощения, но это неизбежно, и всё станет понятным только к концу следующей колонки.
Ключи сортировки рёбер
Теперь, когда мы знаем, что выберем сортировку рёбер, и используем её для создания интервалов ближайших к зрителю полигонов, возникает вопрос: как узнать, что эти полигоны самые близкие? В идеале мы бы просто хранили ключ сортировки каждого полигона, и при появлении нового ребра сравнивали бы ключ её поверхности с ключами других текущих активных полигонов, чтобы с лёгкостью определить, какой из полигонов ближе всего.
Звучит слишком уж хорошо, но это возможно. Если, например, ваша база данных мира хранится как BSP-дерево, а все полигоны усечены в BSP-листья, тогда порядок обхода BSP будет правильным порядком отрисовки. Поэтому, например, если вы обходите BSP сзади вперёд, назначая каждому полигону при его достижении инкрементно большее значение ключа, то полигоны с более высокими значениями ключей гарантировано находились бы перед полигонами с меньшими ключами. Этот подход какое-то время использовался в Quake, но теперь применяется другое решение по причинам, которые я скоро объясню.
Если у вас нет BSP или подобной структуры данных, или у вас много подвижных полигонов (BSP не очень эффективно обрабатывает подвижные полигоны), то ещё один способ достижения целей заключается в сортировке всех полигонов относительно друг друга перед отрисовкой сцены и назначении соответствующих ключей согласно их пространственным отношениям в видовом пространстве. К сожалению, в общем случае это чрезвычайно медленная задача, потому что каждый полигон нужно сравнивать с каждым другим. Существуют техники улучшения производительности сортировки полигонов, но я не знаю никого, кто бы выполнял общую сортировку полигонов на PC в реальном времени.
Альтернатива заключается в сортировке по расстоянию z от зрителя в экранном пространстве; это решение хорошо соответствует превосходной пространственной связности сортировки рёбер. При встрече с каждым новым ребром на растровой строке можно вычислять расстояние по z соответствующего полигона и сравнивать с расстояниями других полигонов, после чего полигон можно сохранить в APL.
Однако получение расстояний по z может быть сложной задачей. Не забывайте, что нам нужно иметь возможность вычислять z в любой произвольной точке полигона, потому что ребро может возникать и заставлять полигон сортироваться в APL в любой точке экрана. Мы можем вычислять z непосредственно из экранных координат x и y и уравнения плоскости полигона, но, к сожалению, этого нельзя делать очень быстро, потому что z для плоскости не меняется в экранном пространстве линейно; однако 1/z меняется линейно, поэтому мы используем это значение. (Обсуждения линейности в экранном пространстве и градиентов для 1/z см. в серии статей Криса Хекера по наложению текстур в прошлогоднем журнале Game Developer.) Ещё одно преимущество использования 1/z заключается в том, что разрешение увеличивается при уменьшении расстояния, то есть при применении 1/z у нас всегда будет лучшее разрешение глубины для близких объектов, которые важнее всего.
Очевидный способ получения значения 1/z в любой произвольной точке полигона заключается в вычислении 1/z в вершинах, интерполяции их по обоим рёбрам полигона и интерполяция между рёбрами для получения значения в нужной точке. К сожалению, для этого необходимо выполнять много работы вдоль каждого ребра; хуже того, при этом требуется деление для вычисления шага 1/z на пиксель в каждом интервале.
Лучше будет вычислять 1/z непосредственно из уравнения плоскости и экранных x и y интересующего нас пикселя. Уравнение имеет следующий вид:
где z — это координата в видовом пространстве z точки на плоскости, которая проецируется в экранные координаты (x’,y’) (точкой начала координат для этих вычислений служит центр проецирования, точка на экране прямо перед точкой обзора), [a b c] — это нормаль к плоскости в видовом пространстве, а d — расстояние от точки начала координат видового пространства до плоскости вдоль нормали. Деление выполняется только один раз для каждой плоскости, потому что a, b, c и d являются для плоскостей константами.
Полное вычисление 1/z требует двух умножений и двух сложений, и каждая операция должна выполняться с плавающей запятой, чтобы избежать ошибок диапазона значений. Такой объём вычислений с плавающей запятой кажется затратным, но на самом деле это не так, особенно на процессорах Pentium, где значение 1/z плоскости в любой точке можно вычислить на языке ассемблера всего за шесть циклов.
Если вам интересно, то вот быстрый вывод уравнения 1/z. Уравнение плоскости для плоскости имеет следующий вид:
где x и y — координаты видового пространства, a, b, c, d и z определены выше. Если мы выполним подстановку
и 
(из определения перспективного проецирования; y меняет знак, потому что увеличивается вверх в видовом пространстве, но вниз в экранном пространстве). Выполнив перестановку, получаем:
Обратив и разложив уравнение, получаем:
Позже я покажу сортировку по 1/z в действии.
Quake и сортировка по z
Выше я упоминал, что Quake больше не использует в качестве ключа сортировки порядок BSP; на самом деле, теперь как ключ теперь применяется 1/z. Несмотря на элегантность градиентов, вычисление из них 1/z очевидно медленнее, чем просто сравнение с ключом порядка BSP, так почему же в Quake мы перешли к использованию 1/z?
Основная причина — это снижение количества полигонов. Для отрисовки в порядке BSP необходимо следовать определённым правилам, в том числе, полигоны при пересечении с BSP-плоскостями должны разделяться. Это разделение значительно увеличивает количество полигонов и рёбер. Благодаря сортировке по 1/z, мы можем оставлять полигоны неразделёнными, но всё равно получать правильный порядок отрисовки, поэтому нам нужно обрабатывать гораздо меньше рёбер; при этом отрисовка в целом ускоряется, несмотря на дополнительные затраты на сортировку по 1/z.
Ещё одно преимущество сортировки по 1/z заключается в том, что она решает проблемы сортировки, упомянутые в начале статьи: перемещение моделей, которые сами по себе являются небольшими BSP-деревьями. Сортировка в BSP-порядке мира здесь не сработает, потому что эти модели являются отдельными BSP, и не существует простых способов встроить их в последовательный порядок BSP мира. Мы не хотим использовать для этих моделей z-буферизацию, потому что они часто являются крупными объектами (например, дверьми), и мы не хотим терять преимущества снижения перерисовки, которые обеспечивают закрытые двери, когда отрисовываются через список рёбер. При использовании сортированных интервалов рёбра подвижных BSP-моделей просто помещаются в список рёбер (сначала усекая полигоны, чтобы они не пересекались со сплошными поверхностями мира для избегания сложностей, связанных со взаимным проникновением) вместо со всеми рёбрами мира, а остальным занимается сортировка по 1/z.
Движемся дальше
В статье, без сомнений, изложено огромное количество информации, и многое ещё не уложилось в вашей голове. Код и объяснение из следующей статьи должны будут помочь; если вы хотите взглянуть заранее, то к моменту прочтения этой статьи код должен быть доступен на ftp.idsoftware.com/mikeab/ddjsort.zip. Стоит также взглянуть на Computer Graphics Фоли и Ван Дама или Procedural Elements for Computer Graphics Роджерса.
На данный момент непонятно, как в результате Quake должен сортировать рёбра — в BSP-порядке или по 1/z. На самом деле, нет никаких гарантий, что сортированные интервалы в любой форме станут окончательным решением. Иногда кажется, что мы меняем графические движки так же часто, как ставят Элвиса на радиостанциях, посвящённых хитам 50-х (но, можно надеяться, с гораздо более эстетически приятными результатами!), и мы без всяких сомнений будем рассматривать альтернативы вплоть до даты выпуска игры.
