Сравнение скриншотов

SPL
Парсинг демозаписей
Файл демо — это компактная запись игры в Quake, которой можно делиться с другими игроками или просматривать самому. Quake — многопользовательская игра, поэтому она разделена на клиент и сервер. По сути, демо записывает трафик, передаваемый от сервера к клиенту во время игры. Имея демо и установленный Quake, можно в точности воссоздать то, что видел игрок на момент записи:
Извините, данный ресурс не поддреживается. :(
Иллюстрация записи демо. Клиент (справа) общается с сервером (слева). Получаемый клиентом трафик записывается в файл демо.
Стоит заметить, что в даже однопользовательском режиме в коде сохраняются компоненты клиента и сервера, только сетевой слой заменён простой передачей в памяти, то есть демо можно записывать и в этом режиме.
Так как формат файлов демо тесно связан с протоколом Quake, его можно понять, читая соответствующий слой сетевого кода Quake. Поэтому довольно просто написать парсер формата файлов демо на Python.
При парсинге файл демозаписи можно читать примерно так же, как сценарий пьесы. Команды инициализации обрисовывают сцену, сообщая нам, какие ресурсы (уровень, модели и звуки) будут использоваться в демо:

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

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

Описанная выше последовательность повторяется для каждого кадра демо, и каждый кадр содержит команду ServerMessageUpdate для каждой сущности.
Мой код на Python для парсинга файлов демо можно найти здесь.
Парсинг ресурсов
Сам уровень описывается в файле .bsp. В нём указана информация о геометрии и текстурах уровня, а также некоторые другие структуры данных, к которым мы вернёмся позже. Формат файлов хорошо задокументирован и его достаточно легко спарсить в классы Python. Модели, описывающие такие элементы, как монстры, модели оружия и так далее, хранятся в файлах .mdl, тоже имеющих хорошую документацию. Звуки в моём проекте не обрабатываются (в видео в начале игры я просто наложил аудиозапись из игры), поэтому парсить звуковые ресурсы не нужно.
Мой код на Python для парсинга файлов .bsp и .mdl можно найти здесь (.bsp) и здесь (.mdl).
Извините, данный ресурс не поддреживается. :(
Бегущий Quakeguy. Геометрия, текстуры и данные анимации хранятся в файле .mdl. Файлы .bsp тоже содержат всё необходимое для уровня.
Загрузка в Blender
Blender имеет богатый интерфейс для написания скриптов на Python. Интерфейс Blender работает благодаря взаимодействию с Python API, поэтому всё, что можно сделать через UI, также можно реализовать скриптами. При помощи этого интерфейса Python я создал скрипт для импорта файлов .bsp и моделей в Blender. У большинства концепций из ресурсов Quake существуют прямые аналоги в Blender:

• Модели и геометрию карт Quake можно представить в виде мешей Blender.
  
• Позы моделей в моделях Quake можно представить как shape keys Blender.
  
• Данные текстур Quake можно представить в виде изображений.
  
• Координаты текстур можно закодировать в виде UV-карт Blender.
  
• Такие эффекты, как волны на воде, анимированные текстуры, а также скайбоксы можно реализовать как шейдеры.

Мой код для импорта распарсенных файлов .mdl и .bsp в Blender находится здесь (.mdl) и здесь (.bsp).
Импорт распарсенного демо заключается в считывании вводного раздела, сообщающего нам, какие игровые ресурсы (модели и карту) нужно преобразовать в ресурсы Blender, с последующим их анимированием согласно данным базовых позиций и обновлений. Для этого я использую поддержку анимации Blender. В частности, я вставляю ключевые кадры позиций, ориентации и shape key для каждой команды ServerMessageUpdate из демо. Также добавил ключевые кадры для анимированных шейдеров, например, для волн на воде, чтобы они двигались в соответствии с текущим временем в игре. Ниже показана запись, показывающая результат импорта демо из первого уровня игры. Мой код импорта файлов демо в Blender можно найти здесь.
Извините, данный ресурс не поддреживается. :(
Просматриваем демо, импортированное в Blender
Освещение
Итак, мы уже загрузили и анимировали геометрию, а также наложили часть текстур. Однако у нас пока нет источников освещения. Когда проектировались уровни оригинального Quake, источники освещения задавались как расставленные по уровню точечные источники. Процесс компиляции преобразовывал эти точечные источники света в карты освещения. Этот процесс заключается в сопоставлении текстуры низкого разрешения с каждой поверхностью уровня и вычислением того, насколько каждый тексел напрямую освещён точечными источниками света. Так как этот процесс измеряет только прямое освещение, дизайнеры уровней добавляли вторичные источники света, чтобы имитировать эффекты отражённого освещения.
Так как исходники оригинальных карт доступны, я мог бы использовать эти источники света для освещения сцены. Однако поскольку Blender сам умеет выполнять точное освещение с многократными отражениями, то при добавлении оригинальных источников света Quake количество отражённого света удваивалось бы, из-за чего сцена оказывалась бы слишком освещённой.
Вместо этого я буду освещать сцену непосредственно из информации текстур. Все текстуры Quake имеют цвета из 256-цветной палитры:

Последние 32 цвета этой палитры особенны тем, что всегда отображаются с полной яркостью, то есть даже в тени они выглядят полностью освещёнными:

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

Кроме того, я обрабатываю как испускающие свет источники некоторые модели, например, модели факелов.
Итак, наша сцена готова — мы создали геометрию, наложили текстуры и задали источники освещения. Давайте отрендерим изображение и посмотрим, что получится:


Ничего себе! Для рендеринга этого кадра на моей GeForce RTX 2060 потребовалось около 20 секунд, и он всё равно невероятно зернистый! Даже применение встроенного шумоподавителя Blender не позволило восстановить чёткое изображение. Обычно Blender без проблем справляется со сценами такого уровня сложности, так что же происходит?
Выборка по значимости
Когда Blender пытается вычислить уровень освещённости точки, он (по умолчанию) случайным образом сэмплирует из всех источников света в сцене и усредняет влияние каждого. На большинстве уровней в сцене гораздо больше источников света, чем видно в любой момент времени. Это означает, что влияние большинства источников равно нулю, а потому результат очень шумен, и это зависит от того, сэмплирован ли видимый источник света.
Проиллюстрируем эту мысль: допустим, в сцене есть 100 источников света, каждый из которых находится в квадрате показанной ниже сетки размером 10x10. Позиция камеры обозначена зелёным крестиком. Пока не обращайте внимание на красный квадрат (мы вернёмся к нему позже). Для отдельной точки, которую видит камера, влияние каждого источника задаётся яркостью квадрата. Из-за перекрытия геометрией уровня на освещённость точки влияют только пятнадцать источников.

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

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

Чтобы избежать этих проблем, мы используем стохастический подход под названием интегрирование Монте-Карло, который применяет случайное сэмплирование. Допустим, мы берём 32 сэмпла, чтобы измерить влияние на рассматриваемую точку. Мы сэмплируем 32 раз 100 источников, заменяя их каждый раз, и усредняем получившееся значение, чтобы получить среднее сэмплирования. Получаемый нами ответ случаен, потому что он зависит от сэмплируемых значений. Вот график, демонстрирующий распределение этих средних значений сэмплирования после получения 100 000 сэмплов:

Распределение средних значений сэмплирования после получения сэмплов от всех источников освещения. Среднее средних значений сэмплов обозначено красной линией.
Как видите, здесь есть дисперсия: среднее сэмплирования может иметь значения в интервале от 0 до 0,3. Такая дисперсия нежелательна, она проявляется на готовом изображении в виде шума.
Есть ли способ снижения дисперсии среднего значения сэмплирования с сохранением того же среднего (средних значений сэмплирования)? Оказывается, здесь можно использовать простую схему типа выборки по значимости (importance sampling). Если мы заранее знаем, что ни один из источников снаружи красного квадрата не влияет на готовое изображение, то просто можем взять нужные 32 сэмпла из квадрата 5x5. Так как теперь мы сэмплируем из 25 значений, а не из 100, то стоит ожидать, что среднее значения сэмплирования будет в четыре раза больше, чем при сэмплировании из полного множества источников. Поэтому мы корректируем среднее значение сэмплирования, разделив его на четыре. Вот распределение скорректированных средних при использовании новой схемы:

Распределение скорректированных средних значений сэмплирования после получения значений от подмножества источников света.
Как видите, дисперсия снизилась, однако среднее осталось тем же, поэтому мы получаем менее шумные, но всё равно правильные (в матожидании) изображения.
Это упрощённое описание того, как Blender сэмплирует источники освещения, но суть остаётся той же: шум можно снизить, если мы не будем сэмплировать источники света, не влияющие на готовое изображение. В Blender есть встроенный способ исключения из сэмплирования источников, называемый в UI Multiple Importance Sampling, а в коде — sample_as_light. Этот флаг можно анимировать при помощи ключевых кадров, поэтому мы можем вносить изменения в зависимости от текущей позиции игрока и угла поворота камеры.
То есть теперь наша задача заключается в создании эвристики для усечения максимально большого количества источников, не влияющих на текущее окно обзора. Другими словами, нам нужно избежать сэмплирования источников, которых нельзя достичь после одного отражения от камеры.
Данные видимости BSP
К счастью, в файлах .bsp есть встроенные структуры данных для решения похожей задачи. Одной из замечательных инноваций, позволявших Quake эффективно работать на «железе» 1996 года, было определение видимых поверхностей, то есть расчёт того, какие части уровня видны из каждой позиции игрока.
Для решения этой задачи файл .bsp разделяет уровень на множество разделённых объёмов, называемых листьями. Каждый лист содержит несколько граней.
Информация о видимости в BSP — это большая (но сжатая) заранее вычисленная двухмерная битовая карта, сообщающая нам, какие из листьев потенциально могут видеть друг друга. Множество листьев, которое потенциально может видеть конкретный лист, называется его потенциально видимым множеством (potentially visible set, PVS):

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

В качестве первой аппроксимации мы можем просто сэмплировать источник света только тогда, когда PVS камеры имеет общие листья с PVS источника. Если мы отрисуем PVS источника и камеры, то увидим, что пересечение и в самом деле есть, поэтому при таком способе этот источник будет сэмплироваться:

Листья PVS источника света обозначены жёлтым, а листья в PVS камеры — синим. Листья, находящиеся в обоих PVS, обозначены зелёным.
Такая система работает хорошо и немного улучшает ситуацию. Однако мы можем сделать намного больше. Проблема в том, что PVS слишком консервативен, то есть существует множество полностью перекрытых листьев, которые можно отбросить, но которые всё равно остаются в PVS. Аналогично, есть точки в PVS источника света, которые из-за ограниченной мощности источника и закона обратной квадратичной зависимости имеют очень мало освещения. Из-за этого мы всё равно сэмплируем множество источников, не влияющих на сцену.
Усечение по пирамиде видимости
Чтобы улучшить ситуацию, я снова воспользовался примером вычислений видимости в Quake и применил механизм под названием frustum culling (усечение по пирамиде видимости). Мы можем связать с камерой пирамиду видимости, то есть объём, грани которого соответствуют краям экрана, спроецированным из начальной точки камеры. Все точки, находящиеся за пределами пирамиды видимости, будут невидимыми для камеры, поэтому мы можем исключить эти листья из PVS. Благодаря этому скрываются листья, находящиеся за спиной игрока и в целом за границами обзора камеры.
Похожую концепцию можно применить и к PVS источника света: на практике, сфера влияния источника ограничена законом обратной квадратичной зависимости, поэтому вокруг каждого источника мы можем разместить ограничивающий параллелепипед, размер которого определяется яркостью источника. Поэтому мы можем уменьшить PVS источника света пересечением с этим ограничивающим параллелепипедом.
Получившаяся система основана на проверке того, пересекаются ли два уменьшенных объёма PVS:

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

После применения системы шумоподавления Blender к этому результату мы получаем ещё более чёткое изображение:


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

• Чтобы разные текстуры источников света выглядели правильно, они должны иметь разные яркости. Например, текстура прожектора должна быть намного ярче, чем вывеска с задней подсветкой. Эта информация не закодирована в игре, поэтому моя система считывает файл конфигурации, который, среди прочего, содержит красиво выглядящие значения яркости для каждой текстуры.
  
• Я обрабатываю текстуру неба как испускающую свет, используя источник солнечного света Blender.
  
• Хотя в оригинальной игре источники свет не зависят от текстур, художники обычно располагали источники рядом с моделью или текстурой, которые должны испускать свет, чтобы визуально освещение выглядело логичным. Несмотря на это, в оригинальной игре всё равно есть некоторые области с нелогичными источниками, которые в моём рендеринге выглядят слишком тёмными. Чтобы учесть это, я добавил несколько источников из исходников оригинальных карт для освещения этих областей. Расположение и яркость этих источников записаны в файл конфигурации, о котором я говорил выше.
  
• В оригинальной игре была система частиц, используемая для взрывов, эффектов телепорта и так далее. Для их отображения я использую собственную систему частиц Blender.

Есть и другие вещи, которые можно добавить:

• Отображение оружия игрока. В оригинальной игре текущее выбранное оружие отображается внизу экрана.
  
• Эффекты молний. Они видны на lightning gun и в последнем уровне первого эпизода.
  
• Спрайты. В игре есть несколько спрайтов, используемых для таких вещей, как эффект взрыва (отдельно от частиц) и пузыри.
  
• Анимированные источники света. Карты освещения оригинальной игры могли быть анимированными, что полезно для реализации мерцающих лампочек и т.п., а также для включения и отключения ламп внутриигровыми переключателями.

Заключение
Я создал систему, импортирующую в Blender файлы демозаписей Quake и все связанные с ними ресурсы. Для этого потребовалось воссоздать приличную часть клиента Quake на Python, заменить отвечающий за рендеринг код кодом, дублирующим состояние игры в Blender. Это заняло много времени, поэтому, вероятно, было бы эффективнее использовать часть кода Quake и добавить мой код на более низком уровне. С другой стороны, я создал библиотеку кода для взаимодействия с несколькими форматами файлов Quake, а также вспомогательный код (например, симплексный солвер). Это может оказаться полезным для других проектов сообщества Quake.
Кстати, о других способах применения: созданную в Blender сцену можно использовать для анализа игрока. Выигрыш или проигрыш спидранов игры часто определяется долями секунды. Если можно будет загрузить нескольких демо в одну сцену и отследить конкретно, кто находится впереди на конкретном этапе, то мы могли бы понять, где можно выиграть время.
При разработке этого проекта я постоянно вспоминал сравнение с рендерерами реального времени, в частности, с проектом Quake II RTX (Q2RTX). Даже при всех моих оптимизациях рендеринг всё равно занимает по несколько секунд на кадр, а Q2RTX выполняется в реальном времени. Blender тоже поддерживает аппаратный raytracing, почему же он всё равно настолько медленнее? Думаю, вероятные причины в следующем:

• Q2RTX использует временную фильтрацию для сглаживания изображений. Это означает, что сэмплы из предыдущих кадров вносят вклад в текущий кадр. Blender пока не полностью поддерживает временную фильтрацию, поэтому мне нужно было рендерить каждый кадр по отдельности.
  
• Моей системе необходимо определять сэмплируемые источники света в каждом кадре. Система на основе RTX может выбирать сэмплируемые источники на основе пути. Для каждой точки поверхности, у которой интегрируется каждый падающий свет, необходимо выполнять только вычисления прямых PVS (с нулевым количеством отражений). Естественно, это приводит к тому, что на каждый пиксель нужно сэмплировать меньшее количество источников. Из прочитанной мной информации я не могу с уверенностью сказать, что это справедливо для Q2RTX, но такое кажется вероятным.
  
• Трассировщик путей Blender под названием Cycles очень обобщён, то есть способен работать с множеством разных типов сцен — с геометрией разной сложности, разным количеством источников света, и так далее. В отличие от него, Q2RTX — крайне специализированный рендерер, поэтому его можно оптимизировать под конкретную задачу — рендеринг уровней Quake.

===========
Источник:
habr.com
===========
===========
Автор оригинала: Matthew Earl
===========Похожие новости:

• [Python] Ещё одна статья о том, как писать на Питоне
  
• [Работа с 3D-графикой, Софт, Удалённая работа] Архитектурный бизнес в период удаленки: практика командной работы в Archicad
  
• [Python, Разработка под iOS, Разработка под Android, Big Data] Разработка большого проекта за 6 месяцев: как не облажаться
  
• [Обработка изображений, Машинное обучение, Софт, Видеокарты, IT-компании] Nvidia выложила в открытый доступ бесплатную бета-версию нейросетевого графического редактора Canvas
  
• [Python, Алгоритмы, Big Data, Машинное обучение, Искусственный интеллект] DataScience Digest — 24.06.21
  
• [Работа с 3D-графикой, Дизайн] Быстрое освоение 3D-моделирования в ZBrush
  
• [Python, Алгоритмы, Big Data, Машинное обучение, Искусственный интеллект] DataScience Digest — 24.06.21
  
• [Python, Математика, Научно-популярное] Выращивание Магических Квадратов с помощью Python
  
• Выпуск Python-библиотеки для научных вычислений NumPy 1.21.0
  
• [Python, Программирование, Гаджеты, История IT] Декодирование сигнала с видеофона 1988 года выпуска (перевод)

Теги для поиска: #_rabota_s_video (Работа с видео), #_rabota_s_3dgrafikoj (Работа с 3D-графикой), #_igry_i_igrovye_pristavki (Игры и игровые приставки), #_quake_1, #_path_tracing, #_blender, #_python, #_speedrun, #_modelirovanie_osveschenija (моделирование освещения), #_rtx, #_quake, #_rabota_s_video (
Работа с видео
), #_rabota_s_3dgrafikoj (
Работа с 3D-графикой
), #_igry_i_igrovye_pristavki (
Игры и игровые приставки
)