Я знаю о деревьях BSP, Octrees и Portal, которые использовались в течение длительного времени. Но современные игры все еще используют эти системы, или они используют новые вещи?
Если это возможно с плюсами и минусами, учитывая рендеринг и обнаружение столкновений.
Ответы:
Да, Unreal Engine 3, например, все еще использует BSP - главным образом потому, что он используется во время процесса CSG. Doom3 / id tech 4 использует порталы, и я думаю, что я прочитал кое-что, что id Tech 5 вернулась к деревьям BSP. В некоторых играх тоже используются октреи. Насколько я понимаю, в игре UE3 перешел на более динамичный подход с запросами на окклюзию, но я был бы удивлен, если бы они не использовали BSP, чтобы хотя бы определить, какие статические сетки видны. В других играх может использоваться только выборочный просмотр (например, Civilization). Это действительно зависит от того, какую игру вы смотрите.
Причина, по которой BSP и все еще есть, в том, что вы не можете добиться большего успеха. Если у вас статическая геометрия, BSP отлично подходит, если вы правильно ее построили. Это требует от вас написания BSP-компоновщика, хотя это сложно (но это может произойти бесплатно, если ваше CSG-решение использует один из них). Octrees и более динамические решения (например, полагающиеся на запросы окклюзии для всего) проще в реализации, имеют более длительное время выполнения. Стоимость, но не требует (дорогой) предварительной обработки уровней. Это компромисс, который некоторые игры готовы делать (например, Crytek хочет, чтобы все работало в режиме реального времени, поэтому они не тратят время на обработку для создания статической структуры ускорения.) Другие подходы времени выполнения, например, включают растеризацию программного обеспечения. CPU и выполнение запросов окклюзии на CPU (используется движком Frostbite.)
Для действительно современного подхода, взгляните на Umbra , который является промежуточным ПО для запросов видимости. Если вы немного поищете в Интернете, вы должны найти некоторые из основных тезисов, которые описывают ранние начала Umbra.
Итог: то, хотите ли вы использовать BSP / Octree / no AS, будет сильно зависеть от типа игры, которую вы хотите создать. Если ваши уровни в основном статические, вы должны воспользоваться этим и построить некоторую статическую структуру ускорения. Если все динамично, вам нужен, конечно, другой подход.
Для обнаружения столкновений я бы взглянул на Bullet и PhysX и их алгоритмы обнаружения столкновений. Но я чувствую, что физические решения менее связаны с видимостью, чем раньше - физическое решение может захотеть использовать BVH на основе GPU, в этом случае нет особого смысла пытаться использовать это для запросов о видимости.
источник
Честно говоря, я не знаю, какие двигатели следующего поколения используют в эти дни, но я скажу вам, что я знаю. Легко запутаться между оптимизацией и структурой данных, используемой для этой оптимизации. Все перечисленные ниже вещи предназначены для оптимизации, но я укажу, какие именно структуры данных.
BSP : структура данных - для обнаружения пересечения между динамически движущимися объектами и статической геометрией мира. Раньше использовался как для обнаружения столкновений, так и для правильного рендеринга геометрии без zbuffer, но он больше не используется для рендеринга, поскольку у нас сейчас достаточно памяти для буфера az. Технически они генерируются немного по-другому, но все же считаются одним и тем же типом дерева. Требуется предварительная обработка.
Octree или Kd-Tree : Структура данных - используется для определения того, какие объекты находятся в одной «ячейке» или области, чтобы избежать проверки n ^ 2 на всех динамических объектах.
Это не единственные, но, вероятно, наиболее распространенные. Есть также много оптимизаций, которые позволяют движку избегать рендеринга геометрии в целом. Но следующее просто исключает геометрию, и это обычно все, для чего она используется:
Порталы : Технически не структура данных, но для отбора требуется специальная структура. Используется для выбора видимости геометрии мира и геометрии динамического объекта из вида. Я думаю, что требуется предварительная обработка, чтобы разделить мир на области. Но я на самом деле не реализовал это, поэтому я не знаю.
Отбор окклюзии : Оптимизация - используется для отбора видимости для любых объектов, например, для динамических объектов.
Обычный выборочный вид : Оптимизация - отбирает объекты, которые не видны с камеры.
Больше выбора окна просмотра : Оптимизация - Обычный выбор окна просмотра может быть оптимизирован еще больше при использовании октодерева. Вы можете удалить целые ячейки октодерева, которые находятся за камерой или не находятся в поле зрения. Это включает участки местности (если вы снаружи). Все, что не отбраковано октройным деревом, вы выполняете "регулярный выборочный просмотр". Тогда все, что осталось, вы бы сделали.
Отбор задней поверхности : Оптимизация - отбор геометрии от камеры для предотвращения растеризации. Обычно делается аппаратно, если состояние рендеринга установлено правильно.
Структуры данных особого случая:
Деревья AABB или деревья Sphere : это своего рода структуры данных особого случая. Они превращают вогнутую форму в выпуклую. Например, персонаж с костями технически вогнут. Это разбивает это в меньшие выпуклые части. Может использоваться как оптимизация для обнаружения столкновений, отбора видимости динамических объектов (обычно) и облегчает проведение испытаний на пересечение, поскольку оно выпуклое. Это будет, скажем, октри, так как они обычно являются динамическими объектами. Они также могут быть использованы для помощи в оптимизации выбраковки окклюзии.
Нет причины, по которой вам нужно использовать одну структуру для представления всего (например, графа сцены). На мой взгляд, вам лучше использовать разные структуры данных для разных задач, а не пытаться использовать какое-то дерево общего назначения. Например, движок, над которым я сейчас работаю, я планирую реализовать комбинацию BSP / Octree / AABB Tree со следующими оптимизациями: выборка окклюзии, область просмотра и, конечно же, выборка задней поверхности. Это означает, что у меня будет одно дерево BSP, одно дерево и, возможно, несколько деревьев AABB в этом дереве.
Выбор лучших структур данных и алгоритмов / оптимизаций - это, пожалуй, самая большая и самая полезная вещь, которую вы можете сделать для своего движка.
источник