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

Question

Я являюсь основателем SceneMax - языка 3D-сценариев с 2005 года. Я хочу добавить рендеринг сцены, используя один объект-сетку, созданный с помощью трехмерного пакета, такого как 3ds max, и алгоритма разделения на октавы для оптимизации производительности.

Знаете ли вы, где я могу найти алгоритм, который берет файл сетки .X, разбивает его на узлы (октри) и знает, как его визуализировать? Я хочу добавить его в свой двигатель. Движок с открытым исходным кодом (Google для SceneMax, если вы заинтересованы).

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

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

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