Previous Entry Share Next Entry
Быстрое введение в OpenSceneGraph. Часть 4.
alex_bobkov

Часть 4 посвящена ключевой теме – графу сцены.

OpenGL и DirectX — низкоуровневые графические интерфейсы. Они принимают на вход только геометрические примитивы (точки, линии, треугольники). Для отрисовки каждого кадра нужно явно задать последовательность команд по отправке на отрисовку примитивов и изменению состояния отображения.

Такой подход обеспечивает высокую гибкость и возможность тонкой настройки последовательность команд для достижения максимальной производительности рендеринга. Однако чем сложнее трехмерная сцена, чем больше трехмерных объектов используется, тем больше времени тратится на рутинные действия: отправку примитивов на отрисовку, переключение состояний отображения. Это сильно замедляет разработку приложения.

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

Возникают новые задачи, связанные с этими сущностями. Например, перемещение и вращение 3д-объектов, переключение видимости, проверка видимости, настройка материалов и источников света, наложение теней, постобработка и другие.

1. Что такое граф сцены, что он может и для чего нужен

Чтобы работать единообразно со всеми этими сущностями и при необходимости создавать новые типы сущностей, придумана структура данных — граф сцены. Граф сцены (scene graph) — это древовидная иерархическая структура данных, которая позволяет организовать логическое и пространственное представление трехмерной сцены для эффективного рендеринга. Как правило, граф сцены — это направленный ациклический граф.

Для реализации графа сцены используется паттерн ООП “Компоновщик”.

Листья графа могут содержать геометрию для отрисовки, промежуточные узлы осуществляют группировку дочерних узлов и могут дополнительно выполнять действия над своими подграфами.

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

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

Пример графа сцены:

Геометрия дома и геометрия стола заданы в своих собственных локальных СК, в которых центры СК совпадает с центрами объектов. Узел Table transform хранит матрицу преобразования, которая определяет положение стола в системе координат дома. Например, с помощью матрицы стол можно сдвинуть к северной стене. Узел House transform хранит матрицу преобразования, которая определяет положение объектов, заданных в системе координат дома, в системе координат города (мировой СК). Абсолютное положение стола в мировой СК определяется произведением 2х матриц преобразования.

Группу узлов, образующих подграф внутри графа, можно интерпретировать как один 3д-объект, состоящий из частей. Например, можно воспринимать и дом, и стол внутри него, как единый объект, хотя на нижнем уровне он состоит из нескольких геометрических объектов. Это решает задачу управления положением объектов на сцене. Достаточно изменить матрицу у одного промежуточного узла, как изменяется положение на сцене сразу у всего объекта и его частей. Так, изменяя только House transform, можно двигать дом вместе со всеми вложенными объектами.

Другое важное свойство узлов графа сцены - хранение состояния отображения. Для узлов можно настраивать состояние отображения через специальные атрибуты. Примеры атрибутов: шейдеры, текстуры, параметры материалов, параметры смешивания цветов и другие. Узел хранит состояние отображения с помощью хранилища атрибутов состояния. Каждый узел наследует все атрибуты состояния всех родительских узлов вплоть до корневого узла и добавляет к ним атрибуты из своего хранилища. Т.е. атрибут, добавленный к некоторому узлу, оказывает влияние на весь его подграф.

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

Существуют также глобальные операции, которые могут применяться ко всему графу сцены целиком. Такие операции осуществляются путем обхода графа в глубину (depth-first).

Одна из самых важных таких операций - отсечение невидимых объектов (culling).

OpenGL производит отсечение на уровне отдельных вершин после выполнения матричных преобразований в середине графического конвейера. В случае большого количества невидимых объектов это серьезно влияет на производительность. Поэтому важно проверять объекты целиком, а не отдельные вершины. Если объект не попадает в области видимость виртуальной камеры, то его не нужно отправлять на отрисовку на видеокарту.

Древовидная структура графа сцены позволяет легко организовать отсечение невидимых объектов (culling). Для этого для каждого узла графа сцены вычисляется ограничивающая сфера (bounding shpere), т.е. минимальная сфера, которая охватывает сферы всех подузлов данного узла.

Перед началом рендеринга кадра выполняется этап отсечения. На этом этапе осуществляется проход по графу по следующему правилу. Для текущего узла проводится проверка на пересечение его ограничивающей сферы с пирамидой видимости. Если сфера не попадает в область видимости, то весь подграф текущего узла отбрасывается. Если сфера пересекает пирамиду, то проверяются сферы всех подузлов и так далее. При этом строится список всех видимых листьев графа. Лист графа сцены может содержать несколько геометрических объектов, но при этом являются минимальной единицей отсечения.

На этапе рендеринга список видимых листьев графа сцены сортируется так, чтобы минимизировать переключения состояния.

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

Можно подвести некоторый промежуточный итог. Основные функции графа сцены:

  • единообразное представление всех элементов трехмерной сцены;
  • гибкое управление отдельными 3д-объектами и группами 3д-объектов, как единым целым: изменение их положения, ориентации, состояние отображения;
  • отбрасывание невидимые объектов.

2. Группировка объектов в графе сцены

Когда объектов в трехмерной сцене становится много, возникает вопрос: а как именно нужно эти объекты группировать в графе сцены?

Граф сцены - очень гибкая структура данных и позволяет объекты группировать произвольно. Однако необходимо стремиться, чтобы структура графа сцены отражала логические и/или пространственные связи между объектами. Рассмотрим несколько примеров.

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

2.2. 3д-модель машины содержит кузов и 4 одинаковых колеса. 3д-модель колеса можно не дублировать 4 раза. Колесо можно сделать в локальной СК, а положение относительно корпуса задавать с помощью узла преобразования. Чтобы получить 4 колеса, нужно 4 узла преобразования. Узел Car transform задает положение машины как целого: корпуса и колес вместе.

2.3. Если имеется множество однотипных объектов (например, домов), то их всех можно разместить на одном уровне:

Однако это приведет к тому, что на этапе отсечения будет проверяться видимость всех домов без исключения.

Можно оптимизировать производительность, если сгруппировать объекты в виде квадродерева. В этом случае все пространство рекурсивно разбивается на квадраты. Большой квадрат разбивается на 4 меньших квадрата. Ведется подсчет количества объектов в каждом квадрате. Разбиение прекращается, когда количество объектов в квадрате станет меньше заданного значения Nmax. Пример разбиения пространства из Википедии:

Каждому квадрату ставится в соответствие группирующий узел графа сцены. В итоге граф сцены начинает выглядеть так:

Если в область видимости попадают не все объекты, то такая структура графа позволяет более эффективно отсекать невидимые объекты, делая меньшее число проверок.

Если в сцене имеются объекты другого типа, например, деревья, то есть 2 основных варианта:

  • Построить единое квадродерево для объектов всех типов;
  • Для каждого типа объектов строить отдельное квадродерево.

Первый вариант - это группировка по пространственному признаку. Второй вариант - по логическому. В разных ситуациях могут быть полезны разные варианты группировки.

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

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

Если 3д-модель создается в 3д-редакторе, то обычно используется пространственная группировка, т.к. модель загружается из файла уже в виде целого подграфа.

3. Классы OpenSceneGraph

Эталонная реализация графа сцены представлена в графической библиотеке OpenSceneGraph (OSG), которая является надстройкой над OpenGL. Алгоритмы работы графа сцены и примеры его применения удобно проиллюстрировать с помощью классов OSG:

Основные классы OSG, которые формируют каркас графа сцены:

osg::Node - базовый класс, от которого наследуются все другие классы.

osg::Geode - листовой узел графа сцены, содержит один или несколько геометрических объектов.

osg::Group - базовый класс для всех промежуточных узлов, содержит список дочерних узлов.

osg::Transform - базовый класс для всех узлов, которые занимаются преобразованием систем координат.

osg::MatrixTransform - узел, который содержит матрицу преобразования в явном виде.

osg::PositionAttitudeTransform - узел, который содержит матрицу преобразования в виде отдельно вектора перемещения, кватерниона вращения и вектора масштабирования.

Для работы с дочерними узлами класс osg::Group содержит ряд методов, смысл которых понятен из названия:

bool addChild(osg::Node* child);

bool insertChild(unsigned int index, osg::Node *child);

bool removeChild(osg::Node *child);

bool removeChildren(unsigned int pos,unsigned int numChildrenToRemove);

bool replaceChild(osg::Node *origChild, osg::Node* newChild);

unsigned int getNumChildren();

bool setChild(unsigned  int i, osg::Node* node);

osg::Node* getChild(unsigned  int i)

bool containsNode(const osg::Node* node)

unsigned int getChildIndex(const osg::Node* node);

osg::MatrixTransform содержит метод setMatrix для задания матрицы преобразования и соответственно getMatrix для ее получения.

osg::PositionAttitudeTransform содержит методы getPosition/setPosition, getAttitude/setAttitude, getScale/setScale, getPivot, setPivot для получения/задания сдвига, вращения, масштабирования и центра вращения.

При экспорте 3д-объекта из 3д-редактора сразу формируется подграф сцены из составных объектов этого 3д-объекта. Загрузить сразу весь подграф можно с помощью функции:

osg::Node* osgDB::readNodeFile(std::string filename);

4. Глобальные действия над графом сцены

Обычно все глобальные действия над графом сцены выполняются внутри OSG. Если 3д-объекты не требуется изменять в процессе работы, то достаточно один раз сформировать граф сцены при запуске приложения. Дальше OSG будет сам обходить граф и осуществлять рендеринг.

Во время подготовки кадра граф сцены обходится как минимум один раз - это обход для отсечения невидимых объектов. Если к узлам прикреплены функции обратного вызова EventCallback или UpdateCallback, то выполняется еще 2 обхода (event traversal и update traversal). Дополнительно при необходимости может выполняться обход графа для поиска пересечения луча с 3д-объектами.

Можно придумать множество других действий над графом сцены, для которых нужно производить обход. Невозможно все эти действия реализовать в виде методов класса osg::Node. Поэтому для универсального выполнения действий над графом применяется паттерн ООП “Посетитель” (Visitor).

Диаграмма классов паттерна:

Для каждого действия над графом создается свой класс ConcreteVisitor, который наследуется от базового абстрактного класса Visitor. В этих классах имеется набор перегруженных методов apply() для выполнения действий над отдельными типами узлов.

В классе osg::Node определен метод accept(), который принимает на вход экземпляр посетителя. Внутри этого метода происходит вызов метода apply() посетителя. После выполнения действия внутри метода apply() вызывается метод узла traverse(), который в случае группы рекурсивно вызывает accept() у всех дочерних узлов.

Диаграмма последовательности:

Вся логика взаимодействия с посетителем заложена в классах osg::Node и osg::Group. Через методы accept() и traverse() они обеспечивают рекурсивный обход графа.

Вся полезная нагрузка заложена в методах apply() посетителя. Благодаря полиморфизму ООП, для разных типов узлов автоматически вызываются разные варианты метода apply().

Если требуется исключить некоторые узлы графа из обхода, то применяется система битовых масок. Маска - целое число размером 4 байта. Каждый узел графа имеет свою маску (по умолчанию 0xffffffff). Посетитель тоже имеет свою маску (по умолчанию 0xffffffff). Можно менять маски как посетителя, так и отдельных узлов. Во время обхода метод apply() вызывается, только если операция “побитовое и” маски посетителя и текущего узла дает значение не 0.

Для выполнения некоторого нового действия над графом сцены нужно создать класс, производный от osg::NodeVisitor, переопределить у него нужные методы apply(). Зачастую достаточно переопределить универсальный метод apply(osg::Node&), который применяется для всех узлов графа. Затем нужно создать экземпляр посетителя и передать его в метод accept() корня графа сцены или любого подграфа.

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

Пример посетителя, который ищет в графе сцены узел с заданным именем:

struct FindNodeVisitor: public osg::NodeVisitor
{
    FindNodeVisitor(const std::string& name):
        osg::NodeVisitor(osg::NodeVisitor::TRAVERSE_ALL_CHILDREN),
        _name(name)
    { }
    virtual void apply(osg::Node& node)
    {
        if (node.getName() == _name)
        {
            _node = &node;
            return;
        }
        traverse(node);
    }
    std::string _name;
    osg::ref_ptr<osg::Node> _node;
};

Пример использования посетителя:

FindNodeVisitor visitor;
root->accept(visitor);
if (visitor._node.valid())
{
   //do something
}

5. Локальные действия узлов графа сцены

Во время работы приложения узлы графа сцена могут выполнять разные действия и влиять на рендеринг самого узла и его дочерних узлов.

Есть 2 основных способа добавить функциональность к узлу: через функции обратного вызова и через переопределение метода traverse().

Каждому узлу можно прикрепить функции обратного вызова 3х типов: EventCallback, UpdateCallback, CullCallback. К одному узлу может быть прикреплено любое количество функций одного типа.

Функции EventCallback предназначены для обработки событий ввода (клавиатуры и мыши) и реакции на эти события, специфичные для данного узла.

Функции UpdateCallback предназначен для модификации узла, например, для анимации, перемещения объекта.

Функции CullCallback определяют нужно ли отображать объект, или его нужно отсечь.

Функции обратного вызова реализуются в виде классов с переопределенной операцией (). Пример:

class MyUpdateCallback: public osg::NodeCallback
{
        virtual void operator()(osg::Node* node, osg::NodeVisitor* nv)
        {
            std::cout<<"update callback - pre traverse"<<node<<std::endl;
            traverse(node,nv);
            std::cout<<"update callback - post traverse"<<node<<std::endl;
        }
};

Чтобы обход продолжался дальше (вызывались функции обратного вызова дочерних узлов), необходимо вставить метод traverse (как в примере выше).

Пример добавления к узлу функции обратного вызова:

node->setUpdateCallback(new MyUpdateCallback);

Можно также создать производный класс от любого класса OSG и переопределить в нем метод traverse(), который вызывается при каждом обходе графа сцены. В методе traverse можно также выполнять те же самые операции, что и в функциях обратного вызова.

6. Оптимизация производительности

3д-объекты могут состоять из нескольких частей (деталей, подобъектов). Удобно для каждой детали иметь свою геометрию, свой узел графа сцены (osg::Geode). Это показано на рисунке:

Это позволяет:

  • Изменять положение и ориентацию детали относительно основного объекта (если сверху над каждым геодом вставить MatrixTransform)
  • Изменять состояние отображения (текстуры, шейдеры)
  • Привязывать к детали метаданные, доступные, например, при клике мышкой

Однако, если таких деталей становится очень много, то это приводит к снижению производительности из-за 2 основных причин:

  • проверка видимости детали (этап отсечения)
  • накладные расходы на вызов функции отрисовки OpenGL для каждой детали

Один узел osg::Geode может хранить несколько геометрических объектов (класс osg::Drawable). Первая причина устраняется, если несколько деталей поместить в один узел Geode:

Чтобы устранить накладные расходы на вызов функций отрисовки, необходимо дальнейшее укрупнение геометрии. Близкорасположенные детали с одинаковой текстурой можно объединить в одну геометрию. Дальше можно несколько текстур объединить в текстурный атлас. И так далее.

Но при этом теряется возможность присоединения метаданных и удобной работы с каждым отдельным объектом.

7. Дополнительные узлы графа сцены

Помимо хранения геометрии, группировки геометрии, задания матриц преобразования узлы графа сцены могут выполнять и другие роли. Здесь краткий обзор еще нескольких узлов (на самом деле их в несколько раз больше):

osg::LOD - управляет уровнями детализации. Дочерние узлы хранят версии 3д-объекта разных уровней детализации. В зависимости от расстояния до камеры osg::LOD отображает один из дочерних узлов.

osg::PagedLOD - то же самое, что и osg::LOD, только дочерние узлы не хранятся в памяти, а подгружаются из внешних файлов при необходимости.

osg::Switch - позволяет выборочно отображать дочерние узлы.

osg::AutoTransform - изменяет матрицу преобразования в зависимости от расстояния до камеры так, чтобы видимый размер объекта на экран был постоянным.

osg::Billboard - ориентирует объект так, чтобы он всегда смотрел на камеру (перпендикулярно взгляду).

osg::LightSource - задает положение источника света.

osg::Camera - дополнительная камера. Применяется для следующих задач: отрендерить подграф в текстуру, отобразить подграф в экранных координатах (текст, меню), отрендерить подграф с измененными матрицами проекции и/или вида, отрендерить подграф в отдельный вьюпорт в рамках основного окна.

osgParticle::ParticleSystemUpdater - обновляет положение частиц в системе частиц каждый кадр.

osgParticle::ParticleProcessor - базовый класс для операций над частицами.

osgShadow::ShadowedScene - создает тени на 3д-объектов.

osgVolume::VolumeNode - класс для объемного рендеринга.

Некоторые из этих классов будут рассмотрены подробнее в следующих частях.


?

Log in