График сцены - Scene graph

Архитектура OpenSceneGraph, 3D-графика с открытым исходным кодом API поддержка многофункциональной и широко распространенной реализации графа сцены.

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

Графики сцены в инструментах редактирования графики

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

Еще одна полезная и управляемая пользователем концепция узла - это слой. Слой действует как прозрачный лист, на котором можно разместить любое количество фигур и групп фигур. Затем документ становится набором слоев, любой из которых можно удобно сделать невидимым, затемнить или заблокировать (сделать доступным только для чтения). Некоторые приложения помещают все слои в линейный список, в то время как другие поддерживают слои внутри слоев с любой желаемой глубиной.

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

Графики сцен в играх и 3D-приложениях

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

Например, игра может определять логические отношения между рыцарем и лошадью, так что рыцарь считается продолжением лошади. Граф сцены будет иметь узел "лошадь" с прикрепленным к нему узлом "рыцарь".

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

В этих больших приложениях требования к памяти являются основными соображениями при проектировании графа сцены. По этой причине многие системы с большим графом сцены используют создание экземпляров геометрии для снижения затрат на память и увеличения скорости. В нашем примере выше каждый рыцарь является отдельным узлом сцены, но графическое представление рыцаря (состоящее из трехмерной сетки, текстур, материалов и шейдеров) является экземпляром. Это означает, что сохраняется только одна копия данных, на которую затем ссылаются любые узлы «рыцарь» в графе сцены. Это позволяет сократить бюджет памяти и увеличить скорость, поскольку при создании нового узла Knight данные о внешнем виде не нужно дублировать.

Реализация графа сцены

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

Операции с графом сцены и отправка

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

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

Другие методы включают использование RTTI (Информация о типе времени выполнения ). Операция может быть реализована как класс, который передается текущему узлу; затем он запрашивает тип узла, используя RTTI, и ищет правильную операцию в массиве обратные вызовы или функторы. Это требует, чтобы отображение типов для обратных вызовов или функторов было инициализировано во время выполнения, но обеспечивает большую гибкость, скорость и расширяемость.

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

Обходы

Обходы являются ключом к возможности применения операций к графам сцены. Обход обычно состоит из начала с некоторого произвольного узла (часто корня графа сцены), применения операции (операций) (часто операции обновления и рендеринга применяются одна за другой) и рекурсивного перемещения вниз по графу сцены (дерево ) к дочерним узлам, пока не будет достигнут листовой узел. На этом этапе многие движки графа сцены затем возвращаются вверх по дереву, применяя аналогичную операцию. Например, рассмотрим операцию визуализации, которая принимает во внимание преобразования: при рекурсивном перемещении по иерархии графа сцены вызывается операция предварительной визуализации. Если узел является узлом преобразования, он добавляет собственное преобразование к текущей матрице преобразования. Как только операция завершает обход всех дочерних узлов узла, она вызывает операцию пост-рендеринга узла, чтобы узел преобразования мог отменить преобразование. Такой подход резко снижает необходимое количество матричного умножения.[нужна цитата ]

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

Например, в двухмерных случаях графы сцены обычно визуализируются, начиная с корневого узла дерева, а затем рекурсивно рисуют дочерние узлы. Листья дерева представляют собой самые передние объекты. Поскольку рисование происходит сзади наперед, а более близкие объекты просто перезаписывают более удаленные, этот процесс известен как использование Алгоритм художника. В 3D-системах, в которых часто используются буферы глубины, более эффективно сначала отрисовывать ближайшие объекты, так как удаленные объекты часто нуждаются только в проверке глубины, а не на реальном рендеринге, поскольку они перекрываются более близкими объектами.

Графики сцен и иерархии ограничивающих объемов (BVH)

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

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

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

Есть некоторое сходство между BVH и графами сцены. Граф сцены может быть легко адаптирован для включения / превращения в BVH - если каждый узел имеет связанный том или есть специально созданный «связанный узел», добавленный в удобном месте в иерархии. Возможно, это не типичный вид графа сцены, но есть преимущества включения BVH в граф сцены.

Графики сцен и пространственное разбиение

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

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

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

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

В зависимости от особенностей производительности отрисовки приложения, на большую часть дизайна графа сцены могут повлиять соображения эффективности отрисовки. В 3D-видеоиграх, таких как Землетрясение, разделение двоичного пространства (BSP) деревья сильно отдают предпочтение для минимизации тестов на видимость. Однако для вычисления BSP-деревьев из графов сцены дизайна требуется очень много времени, и их необходимо пересчитывать, если граф сцены дизайна изменяется, поэтому уровни имеют тенденцию оставаться статическими, а динамические символы обычно не учитываются в схеме пространственного разделения.

Графики сцены для плотных обычных объектов, таких как поля высот и полигональные сетки, как правило, используют квадродеревья и Octrees, которые представляют собой специализированные варианты иерархии трехмерной ограничительной рамки. Поскольку поле высоты занимает сам объем блока, рекурсивное деление этого блока на восемь подбоксов (отсюда «окт» в октодереве) до достижения отдельных элементов поля высоты является эффективным и естественным. Квадродерево - это просто двумерное октодерево.

Стандарты

ФИГС

ФИГС была первой коммерческой спецификацией графа сцены и стала стандартом ANSI в 1988 году. Разрозненные реализации были предоставлены Unix поставщики оборудования. В Графическая система HOOPS 3D похоже, это была первая коммерческая библиотека графов сцены, предоставленная одним поставщиком программного обеспечения. Он был разработан для работы на разрозненных двухмерных и трехмерных интерфейсах нижнего уровня, и первая основная производственная версия (v3.0) была завершена в 1991 году. Вскоре после этого, Силиконовая Графика выпущенный IRIS Inventor 1.0 (1992), который представлял собой граф сцены, построенный на основе IRIS GL 3D API. За этим последовало Открыть Inventor в 1994 г. - переносимый граф сцены, построенный на основе OpenGL. Дополнительные библиотеки графов 3D-сцен можно найти в Категория: API-интерфейсы 3D-сцен.

X3D

X3D это Безвозмездная открытые стандарты формат файла и архитектура времени выполнения для представления и передачи трехмерных сцен и объектов с помощью XML. Это ISO -аттифицированный стандарт, который обеспечивает систему для хранения, извлечения и воспроизведения графического контента в реальном времени, встроенного в приложения, в пределах одного открытая архитектура для поддержки широкого спектра доменов и пользовательских сценариев.

Смотрите также

использованная литература

Книги

  • Лелер, Wm и Мерри, Джим (1996) 3D с ОБРУЧАМИ, Эддисон-Уэсли
  • Вернеке, Джози (1994) Наставник Inventor: программирование объектно-ориентированной трехмерной графики с помощью Open Inventor, Эддисон-Уэсли, ISBN  0-201-62495-8 (Выпуск 2)

Статьи

внешние ссылки