Граф сцены

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

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

Содержание

  • 1 Графики сцены в инструментах редактирования графики
  • 2 Графы сцены в играх и 3D-приложениях
  • 3 Реализация графа сцены
    • 3.1 Операции и отправка графа сцены
      • 3.1.1 Переходы
  • 4 Графики сцен и иерархии ограничивающих объемов (BVH)
  • 5 Графики сцен и пространственное разбиение
  • 6 Стандарты
    • 6.1 PHIGS
    • 6.2 X3D
  • 7 См. Также
  • 8 Ссылки
    • 8.1 Книги
    • 8.2 Статьи
  • 9 Внешние ссылки

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

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

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

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

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

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

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

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

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

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

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

Операции и диспетчеризация графа сцены

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

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

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

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

Обходы

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

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

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

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

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

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

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

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

Графы сцены и пространственное разделение

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

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

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

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

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

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

Стандарты

PHIGS

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

X3D

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

См. Также

Ссылки

Книги

  • Лелер, Wm and Merry, Jim (1996) 3D с HOOPS, Addison-Wesley
  • Wernecke, Josie (1994) The Inventor Mentor: Programming Object-Oriented 3D Graphics with Open Inventor, Addison-Wesley, ISBN 0-201-62495-8 (Выпуск 2)

Статьи

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

Последняя правка сделана 2021-06-07 04:48:02
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте