Разбиение объектного пространства сцены путём построения octree-дерева

Have you ever stood and stared at it, Morpheus?
Marveled at its beauty. Its genius. Billions of people just living out their lives... oblivious.

Did you know that the first Matrix was designed to be a perfect human world?
Where none suffered, where everyone would be happy. It was a disaster. No one would accept the program.
Entire crops were lost.

Some believed we lacked the programming language to describe your perfect world.
But I believe that, as a species, human beings define their reality through suffering and misery.

Agent Smith. The Matrix.

Хотя в Королевстве статьи такого типа публикуются нечасто, я всё же попросил разрешения у Королевы сделать это, так как на тематику статей сайта никакие ограничения не накладываются, а сама программа написана на Object Pascal в среде Delphi. Для тех, кто читал мои ранние статьи по DirectX, хочу предупредить, что свои исследования в области прикладного API вроде DirectX и OpenGL я прекратил, и теперь больше занимаюсь алгоритмами, необходимыми для реализации трёхмерной графики. Ну да это так, к слову.

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

Обычно тем, кто только начинает пробовать свои силы в 3D-пространстве, трудно понять, для чего же нужно разбиение пространства. Действительно, если опыты не выходят за рамки "солнышка и земли вокруг него", то заниматься этим нет смысла. Но допустим, мы взялись за рендеринг сложной сцены, вроде уровня Quake 3. Количество полигонов в сцене может достигать нескольких десятков тысяч (из года в год это значение неудержимо растёт), и если этот массив данных целиком отправлять на графический конвейер в каждом кадре, ни о какой интерактивности в игре и речи быть не может. Графический процессор будет тратить время на просчёт каждого полигона у каждого объекта, даже если в результате он жестоко не попадёт на экран.

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

Здесь я собираюсь рассмотреть метод разделения объектного пространства, который называется octree (по-моему, от латинского octa - восемь, и английского tree - дерево). Восьмеричное дерево. Вообще подобные алгоритмы были разработаны ещё в 70-х годах, например, для точного описания ландшафта, но позже нашли своё применение в компьютерной графике.

Данный алгоритм производит разделение объектного пространства на восемь подпространств. Общую схему работы можно представить следующими шагами:

Помещаем всю сцену в выровненный по осям куб. Этот куб описывает все элементы сцены и является корневым (root) узлом дерева.
Проверяем количество примитивов в узле, и если полученное значение меньше определённого порогового, то производим связывание (ассоциацию) данных примитивов с узлом. Узел, с которым ассоциированы примитивы, является листом (leaf).
Если же количество примитивов, попадающих в узел, больше порогового значения, производим разбиение данного узла на восемь подузлов (подпространств) путём деления куба двумя плоскостями. Мы распределяем примитивы, входящие в родительский узел, по дочерним узлам. Далее процесс идёт рекурсивно, т. е. для всех дочерних узлов, содержащих примитивы, выполняем пункт 2.

Данный процесс построения дерева может содержать несколько условий прекращения рекурсии:

Если количество примитивов в узле меньше или равно пороговому значению.
Если рекурсия (количество делений) достигла какой-то определённой глубины вложенности.
Если количество созданных узлов достигло порогового значения.

Содержание Назад Вперед