Преимущества использования Octree вместо BSP

Не так давно, при просмотре видео от Digital Foundry, я заметил, что в ремейке Quake 2 используются восьмеричные деревья (Octree), вместо двоичных (BSP). Я обратил на это внимание по той причине, что в моём движке Force Tech тоже используется Octree, а не BSP. У них есть ряд преимуществ, которые и хотелось осветить в этой статье.

В оригинальных играх на движке Dark Engine, функционал которого я воссоздаю в Force Tech, используются классические Leaf BSP деревья, свойственные большинству игр того времени. Но от их использования я решил отказаться в самом начале разработки по ряду причин, включая и то, что BSP не подразумевает никакого изменения геометрии в принципе. Не буду углубляться в особенности построения каждого типа дерева, просто приведу здесь две картинки из Википедии, дающие общее представление о том, что же это за деревья такие:

Если вкратце, BSP — это строго статическое представление данных, послужившее прекрасным средством визуализации виртуального мира и расчета столкновений в нём. Оно было актуально во времена программного рендеринга и фиксированного графического пайплайна в большинстве 3D игр 1990-х - начала 2000-х: Doom 1-2-3, Quake 1-2-3, Unreal 1-2, Half-Life 1-2, Blood 2 и др. А сейчас, когда пайплайн стал программируемым, и в видеокарту можно отправлять абсолютно любые данные хоть каждый кадр, оно является, скорее, узким местом, чем средством ускорения отрисовки. Ко всему прочему, оно требует перестройки всего дерева даже при незначительных изменениях геометрии. При этом всё равно придется строить дополнительную структуру для хранения остальных данных уровня.

Octree же является трёхмерным деревом, оно ограничивает и делит пространство в каждой своей ячейке на восемь равных сегментов (отсюда и название). А раз это пространство, любые данные, расположенные в нём (объекты, источники света, точки маршрута, триггеры), можно поместить в соответствующие ячейки дерева. Есть основания полагать, что многие современные проекты используют Octree, среди них Doom 2016, Wolfenstein II, Dreams (PS4/5).

Чем же Octree лучше? Своей гибкостью и универсальностью! Я использую всего одно Octree для целого ряда задач:
— хранение сведений обо всех сущностях уровня, включая объекты и геометрию;
— определение видимости при отрисовке, на основании видимости ячеек;
— хранение информации об освещенных фрагментах уровня, в том числе и для динамического Глобального Освещения;
— частичная загрузка уровней и стриминг геометрических данных;
— автоматическая "вокселизация" геометрии;
— расчет распространения звука;
— расчет поиска пути для ИИ;
— и т.д.

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

Но такой способ не был достаточно эффективным, поэтому и для него понадобились дополнительные надстройки и предвычисления в виде порталов, как в Thief и Unreal, или PVS (Potentially Visible Set), как в Quake и Half-Life. А это, в свою очередь, требовало ещё больше расчётов. Поэтому все эти данные считались в офлайне, то есть, при компиляции уровня в редакторе.

С ростом мощностей графических карт, отпала необходимость жестко экономить на отрисовке треугольников. Разработчики 90-х годов прошлого века могли только мечтать о мощностях, доступных нам сейчас: мы можем нарисовать условный уровень Quake 2, System Shock 2 или Half-Life 2 вообще без отсечения невидимой геометрии, целиком больше 60 раз за секунду! Да-да, даже самое примитивное приложение без оптимизаций и освещения способно рисовать оттекстурированные уровни этих игр целиком с огромным запасом производительности, только за счет мощности современных видеокарт и значительно более оптимизированных драйверов для них. Но стоит добавить, к примеру, расчет теней в реальном времени, как fps для отрисовки целого уровня станет удручающе низким. Почему так? Из-за избыточной обработки тех участков уровня, которые мы не видим.

Сложнее всего отсечь геометрию, которая располагается перед игроком, но заслоняется другими предметами. Сложность заключается в нахождении баланса между скоростью определения видимости и скоростью отрисовки. Можно делать очень точное определение видимости, но ценой будет время, которое можно было бы потратить на другие вычисления, поэтому мы вряд ли выиграем, если скрупулезно будем отсекать каждый лишний пиксель. Да это и не требуется, ведь простая растеризация сейчас относительно "дёшева". Поэтому балансом будет являться "приемлемое" качество отсечения ;). И самым простым и эффективным инструментом в этой задаче является Occlusion Query до сих пор использующийся во множестве проектов. Если вы, при резком выпаде из-за угла, на мгновение видели дыры в уровне, исчезающие уже в следующем кадре, знайте, это он и есть — Occlusion Query, самый простой способ отсечения невидимой геометрии!

Что же такое Occlusion Query? Во времена расцвета BSP его ещё не существовало. Это специальный запрос к графическому API для определения видимости только что нарисованных фрагментов. А раз мы говорим про способность современных видеокарт очень быстро рисовать кучи простых треугольников, почему бы не воспользоваться этой возможностью для отсечения? В самом простом случае, мы можем всегда рисовать геометрию той ячейки Octree, в которой располагается камера, а затем выполнять запросы видимости для других ячеек, по мере удаленности от камеры. При этом нам не нужно даже рисовать саму геометрию, достаточно нарисовать грани ячейки, чтобы определить, видима она или нет. Если ячейка не видна, все её вложенные ячейки мы тоже можем считать невидимыми... Profit!

Весьма специфической особенностью такого подхода является асинхронность работы видеокарты и процессора: если ждать результатов Occlusion Query от видеокарты в текущем кадре, процессор будет простаивать слишком долго и время кадра будет неприемлемо высоким (мы не успеем нарисовать 60 кадров в секунду). Поэтому секрет заключается в том, чтобы получать результат запроса в следующем кадре! Именно поэтому в стенах при резком выпаде из-за угла на мгновение мы видим дыры, исчезающие в следующем кадре — в текущем кадре с дырой, у нас ещё нет актуальной информации о видимости фрагмента — он считается невидимым и не рисуется, но уже в следующем кадре мы получим данные о его видимости, и только тогда нарисуем.

Задача определения видимости очень нетривиальна и имеет массу различных решений, но поскольку мы говорим об Octree, хотелось бы упомянуть такое коммерческое решение как Umbra3D (или Umbra middleware). Оно основывается на препроцессинге Octree для автоматической генерации порталов, чтобы определять видимость ячеек уровня уже на их основе. Поскольку все расчеты ведутся на CPU, не будет задержек ожидания запросов от видеокарты и соответствующих "миганий" видимой геометрии. Umbra3D использовалась в ряде AAA проектов, среди которых такие мастодонты как Doom 2016, Batman: Arkham Knight, Call of Duty: Ghosts, The Witcher 3, Deus Ex: Mankind Divided и даже движок Unity. В будущем я планирую углубиться в этот алгоритм и попытаюсь внедрить в Force Tech. А если не получится, уже сейчас работает, хоть и не идеально, алгоритм на основе Occlusion Query, описанный в публикации "Coherent Hierarchical Culling Revisited".

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

Эти механизмы в Force Tech ещё не реализованы, но поскольку Octree является пространственным деревом, очень удобно использовать его ячейки, равномерно распределенные по всей геометрии, как для загрузки данных с диска, так и для расчетов распространения звука и поиска пути. Ведь что такое куб в пространстве - это воксель! Все ячейки, содержащие в себе геометрию, условно можно считать твердыми, а не содержащие - пустыми (как в Minecraft'е ;)).

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

Поскольку ячейки дерева разного размера, можно использовать разные "уровни" дерева для разных целей. К примеру, для загрузки частей уровня можно использовать ячейки покрупнее, тогда как для расчета распространения звука, нужна очень мелкая сегментация, приближенная к реальной геометрии. А при удалении камеры на достаточное расстояние, можно вместо реальной геометрии рисовать воксели нужного размера, чтобы издалека отсутствующие сегменты уровня не выглядели дырами в стенах ;).

Использование Octree может быть очень разносторонним и применить всего одно дерево можно сразу для ряда разных задач! Присоединяйтесь к моим социальным сетям, чтобы наблюдать за развитием движка Force Tech. А скачать его последнюю версию, чтобы побегать по уровням Thief 1-2 и System Shock 2 можно уже прямо сейчас на моем сайте:
— Сайт: https://forcesw.com/rus
— ВК: https://vk.com/forcesoftware
— DTF: https://dtf.ru/u/687837-force-software
— Telegram: https://t.me/forcesoftware
— Twitter: https://twitter.com/Force_Software

#геймдев #инди #ForceTech