Рендеринг сетки с использованием алгоритма Octree

Есть несколько вариантов, но один из подходов к построению октодерева:

1. Начните с одного узла (т.е. куба), охватывающего всю вашу сцену или разделяемый объект.
2. Для каждого элемента в вашей сцене / объекте (например, меш, поли или любой другой уровень детализации, над которым вы работаете):
   1. Убедитесь, что этот элемент полностью входит в узел.
   2. Если да, разделите узел на восемь потомков, затем рекурсивно выполните шаг 2 для каждого потомка.
   3. Если нет, переходите к следующему узлу, пока не останется никаких узлов.
   4. Добавьте элемент к наименьшему узлу, который может его содержать.

Также часто останавливают рекурсию на основе некоторой эвристики, например, если размер узлов или количество элементов в узле меньше определенного порога.

См. это руководство по флипкоду для более подробной информации о построении октодерева.

Когда у вас есть октодерево, вы можете использовать несколько подходов для его рендеринга. Основная идея состоит в том, что если вы не можете «видеть» узел, значит, вы не можете видеть и его дочерние элементы, поэтому все внутри этого узла (и его дочерних элементов) не нуждается в визуализации.

Отбор Frustum легко реализовать, и есть ли вопрос "вы это видите?" протестируйте, используя усеченную пирамиду вашей проекции обзора. Gamedev.net есть статья обсуждает отсечение усеченной пирамиды и некоторые другие подходы.

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

Важно сначала рассмотреть типы файлов сетки, которые вам придется поддерживать.

Фактически существует 3 различных типа объектов. 1. Открытая естественная местность. Это очень хорошо подходит для квадродерева, так как октодерево вносит ненужную сложность. Нет особых причин вводить 3-е измерение, если оно не даст вам большого прироста производительности. 2. Открытая местность с множеством высоких объектов. Это очень хорошо вписывается в октодерево, так как октодерево позволяет вам удалять элементы на вертикальной оси из рендеринга, а в такой сцене, как эта, их много. Я, честно говоря, не могу назвать ничего, что могло бы подходить под это с моей головы. 3. Замкнутые пространства или модели персонажей / статические сетки. Это очень хорошо вписывается в деревья BSP. Дерево BSP позволяет объектам, полностью отображаемым на экране, или замкнутым пространствам отображать столько полигонов, сколько необходимо.

Я бы рекомендовал добавить 1 и 3, предполагая, что 1 - это даже тип модели, который вам нужно поддерживать. # 3 очень стандартен для шутеров от первого лица или моделей персонажей, и добавление поддержки для него может дать вам максимальную отдачу от затраченных средств. Общая идея состоит в том, чтобы удалить как можно больше геометрии из рендера, поэтому дерево квадратов для 95% игровых миров игроков на открытом воздухе идеально подходит. У октодерева есть применение, но меньше, чем вы думаете.

Каждый из этих алгоритмов относительно легко написать. Например, много лет назад я написал октодерево за 3 часа. Обычно они обрабатываются во время загрузки, части геометрии добавляются к каждому квадрату (если четырехугольник / октодерево) или к дереву (если BSP), а затем выполняется рендеринг. Есть много отличных статей через быстрый поиск в Google, которые я оставлю для вашего исследования. Небольшое примечание: дерево BSP также может обрабатывать обнаружение столкновений и является идеальным кандидатом для моделей персонажей и статических сеток. Таким образом, это алгоритм, на который я бы рекомендовал не торопиться, чтобы убедиться, что он достаточно гибкий для многократного использования.