Граф сцены — это общая структура данных, обычно используемая приложениями для редактирования векторной графики и современными компьютерными играми, которая организует логическое и часто пространственное представление графической сцены. Это набор узлов в графе или древовидной структуре. Узел дерева может иметь много дочерних узлов, но только одного родителя, при этом эффект родителя применяется ко всем его дочерним узлам; операция, выполняемая над группой, автоматически распространяет ее эффект на всех ее членов. Во многих программах связывание матрицы геометрического преобразования (см. также преобразование и матрица ) на каждом уровне группы и объединение таких матриц вместе является эффективным и естественным способом обработки таких операций. Например, общей особенностью является возможность группировать связанные формы и объекты в составной объект, которым затем можно манипулировать так же легко, как и одним объектом.
При редактировании векторной графики каждый листовой узел в графе сцены представляет некоторую атомарную единицу документа, обычно такую фигуру, как эллипс или путь Безье . Хотя сами фигуры (особенно пути) могут быть далее разложены на узлы, такие как узлы сплайна , практично думать о графе сцены как о состоящем из фигур, а не о переходе на более низкий уровень представления.
Еще одна полезная и управляемая пользователем концепция узла — это слой . Слой действует как прозрачный лист, на котором можно разместить любое количество фигур и групп фигур. В этом случае документ становится набором слоев, любой из которых можно удобно сделать невидимым, затемнить или заблокировать (сделать доступным только для чтения). Некоторые приложения помещают все слои в линейный список, в то время как другие поддерживают слои внутри слоев на любую желаемую глубину.
Внутри может вообще не быть никакой структурной разницы между слоями и группами, поскольку они оба являются просто узлами графа сцены. Если необходимы различия, объявление общего типа в C++ должно заключаться в создании универсального класса узла, а затем выведении слоев и групп в качестве подклассов. Например, элемент видимости может быть элементом слоя, но не обязательно группы.
Графы сцен полезны для современных игр, использующих 3D-графику и все более крупные миры или уровни. В таких приложениях узлы графа сцены (обычно) представляют сущности или объекты на сцене.
Например, игра может определять логические отношения между рыцарем и лошадью, чтобы рыцарь считался продолжением лошади. Граф сцены будет иметь узел «лошадь» с прикрепленным к нему узлом «рыцарь».
Граф сцены может также описывать пространственные, а также логические отношения различных объектов: рыцарь движется в трехмерном пространстве так же, как движется лошадь.
В таких крупных приложениях требования к памяти являются основным фактором при разработке графа сцены. По этой причине многие системы графов больших сцен используют создание экземпляров геометрии для снижения затрат памяти и увеличения скорости. В нашем примере выше каждый рыцарь представляет собой отдельный узел сцены, но графическое представление рыцаря (состоящее из 3D-сетки, текстур, материалов и шейдеров) является экземпляром. Это означает, что сохраняется только одна копия данных, на которую затем ссылаются любые «рыцарские» узлы в графе сцены. Это позволяет сократить бюджет памяти и повысить скорость, поскольку при создании нового рыцарского узла данные внешнего вида не нужно дублировать.
Самая простая форма графа сцены использует структуру данных массива или связанного списка , а отображение его форм — это просто вопрос линейного повторения узлов один за другим. Другие распространенные операции, такие как проверка того, какая фигура пересекает указатель мыши, также выполняются посредством линейного поиска. Для небольших графов сцен этого обычно бывает достаточно.
Применение операции к графу сцены требует некоторого способа диспетчеризации операции в зависимости от типа узла. Например, в операции рендеринга узел группы преобразований будет накапливать свое преобразование путем умножения матрицы, смещения вектора, кватернионов или углов Эйлера . После чего листовой узел отправляет объект на рендеринг в средство рендеринга. Некоторые реализации могут отображать объект напрямую, что вызывает базовый API рендеринга , например DirectX или OpenGL . Но поскольку базовой реализации API рендеринга обычно не хватает переносимости, вместо этого можно разделить граф сцены и системы рендеринга. Для реализации такого типа диспетчеризации можно использовать несколько различных подходов.
В объектно-ориентированных языках, таких как C++ , этого можно легко достичь с помощью виртуальных функций , каждая из которых представляет собой операцию, которую можно выполнить над узлом. Виртуальные функции легко писать, но обычно невозможно добавлять новые операции к узлам без доступа к исходному коду. В качестве альтернативы можно использовать шаблон посетителя . Это имеет аналогичный недостаток: так же сложно добавлять новые типы узлов.
Другие методы включают использование RTTI ( Информация о типе времени выполнения ). Операцию можно реализовать как класс, передаваемый текущему узлу; затем он запрашивает тип узла, используя RTTI, и ищет правильную операцию в массиве обратных вызовов или функторов . Это требует, чтобы карта типов для обратных вызовов или функторов была инициализирована во время выполнения, но обеспечивает большую гибкость, скорость и расширяемость.
Существуют вариации этих методов, и новые методы могут предложить дополнительные преимущества. Одной из альтернатив является перестроение графа сцены, при котором граф сцены перестраивается для каждой выполненной операции. Однако это может быть очень медленно, но дает высокооптимизированный граф сцены. Он демонстрирует, что хорошая реализация графа сцены во многом зависит от приложения, в котором он используется.
Обходы — это ключ к возможностям применения операций к графам сцен. Обход обычно состоит из начала с некоторого произвольного узла (часто корня графа сцены), применения операции(й) (часто операции обновления и рендеринга применяются одна за другой) и рекурсивного перемещения вниз по графу сцены (дерево ) к дочерним узлам, пока не будет достигнут листовой узел. На этом этапе многие движки графов сцен затем перемещаются вверх по дереву, применяя аналогичную операцию. Например, рассмотрим операцию рендеринга, которая учитывает преобразования: при рекурсивном обходе иерархии графа сцены вызывается операция предварительного рендеринга. Если узел является узлом преобразования, он добавляет собственное преобразование к текущей матрице преобразования. Как только операция завершает обход всех дочерних элементов узла, она вызывает операцию пост-рендеринга узла, чтобы узел преобразования мог отменить преобразование. Такой подход радикально сокращает необходимое количество умножения матриц. [ нужна цитата ]
Некоторые операции с графом сцены на самом деле более эффективны, когда узлы просматриваются в другом порядке — именно здесь некоторые системы реализуют перестроение графа сцены, чтобы изменить порядок графа сцены в более простой для анализа формат или дерево.
Например, в 2D-случаях графы сцены обычно визуализируются, начиная с корневого узла дерева, а затем рекурсивно рисуют дочерние узлы. Листья дерева представляют собой большинство объектов переднего плана. Поскольку рисование происходит сзади вперед, причем более близкие объекты просто перезаписывают более дальние, этот процесс известен как использование алгоритма Художника . В 3D-системах, которые часто используют буферы глубины , более эффективно сначала рисовать ближайшие объекты, поскольку более дальние объекты часто требуют только проверки глубины, а не фактического рендеринга, поскольку они перекрываются более близкими объектами.
Иерархии граничных объемов (BVH) полезны для решения множества задач, включая эффективный отбор и ускорение обнаружения столкновений между объектами. BVH — это пространственная структура, но она не требует разделения геометрии (см. пространственное разделение ниже).
BVH — это дерево ограничивающих объемов (часто сфер, ограничивающих рамок , выровненных по осям или ориентированных граничных рамок). В нижней части иерархии размер объема достаточно велик, чтобы плотно охватить один объект (или, возможно, даже некоторую меньшую часть объекта в BVH высокого разрешения). По мере восхождения по иерархии каждый узел имеет свой собственный том, который плотно охватывает все тома, находящиеся под ним. В корне дерева находится том, охватывающий все тома дерева (вся сцена).
BVH полезны для ускорения обнаружения столкновений между объектами. Если ограничивающий объем объекта не пересекает объем выше в дереве, он не может пересекать ни один объект ниже этого узла (поэтому все они очень быстро отклоняются).
Есть некоторое сходство между BVH и графами сцен. Граф сцены можно легко адаптировать для включения или превращения в BVH — если с каждым узлом связан том или в удобном месте в иерархии добавлен специально созданный «связанный узел». Возможно, это нетипичный вид графа сцены, но включение BVH в граф сцены имеет свои преимущества.
Эффективным способом объединения пространственного разделения и графов сцены является создание конечного узла сцены, содержащего данные пространственного разделения. [ необходимо разъяснение ] Это может повысить вычислительную эффективность рендеринга.
Пространственные данные обычно статичны и обычно содержат данные неподвижной сцены в некоторой секционированной форме. [ необходимы разъяснения ] Некоторые системы могут иметь системы и их рендеринг отдельно. Это нормально, и ни у одного из методов нет реальных преимуществ. В частности, плохо содержать граф сцены в системе пространственного разделения, поскольку граф сцены лучше рассматривать как более обширную систему пространственного разделения. [ нейтралитет оспаривается ]
Очень большие рисунки или графы сцен, которые генерируются исключительно во время выполнения (как это происходит в программах рендеринга с трассировкой лучей ), требуют определения групповых узлов более автоматизированным способом. Например, трассировщик лучей возьмет описание сцены 3D- модели и построит внутреннее представление, которое разбивает ее отдельные части на ограничивающие рамки (также называемые ограничивающими плитами). Эти поля сгруппированы иерархически, чтобы можно было эффективно вычислять тесты пересечения лучей (как часть определения видимости). Например, групповой блок, который не пересекает глазной луч, может полностью пропустить тестирование любого из своих членов.
Аналогичная эффективность сохраняется и в 2D-приложениях. Если пользователь увеличил документ так, что на экране компьютера видна только часть его, а затем прокручивает его, полезно использовать ограничивающую рамку (или в данном случае схему ограничивающего прямоугольника), чтобы быстро определить, какая сцена элементы графа видимы и, следовательно, их действительно необходимо отрисовать.
В зависимости от особенностей производительности рисования приложения, на большую часть дизайна графа сцены могут влиять соображения эффективности рендеринга. В 3D-видеоиграх, таких как Quake , деревья разделения двоичного пространства (BSP) широко используются для минимизации тестов на видимость. Однако деревьям BSP требуется очень много времени для вычисления на основе графов сцены проектирования, и их необходимо пересчитывать, если граф сцены проектирования изменяется, поэтому уровни имеют тенденцию оставаться статичными, а динамические символы обычно не учитываются в схеме пространственного разделения.
Графы сцен для плотных регулярных объектов, таких как поля высот и полигональные сетки, как правило, используют квадродеревья и октадеревья , которые являются специализированными вариантами иерархии трехмерных ограничивающих рамок. Поскольку поле высот само занимает объем блока, рекурсивное разделение этого блока на восемь подблоков (отсюда и «окт» в октете) до тех пор, пока не будут достигнуты отдельные элементы поля высот, является эффективным и естественным. Квадродерево — это просто двумерное октодерево.
PHIGS была первой коммерческой спецификацией графа сцены и стала стандартом ANSI в 1988 году. Поставщики аппаратного обеспечения Unix предоставили различные реализации . Система 3D-графики HOOPS, похоже, была первой коммерческой библиотекой графов сцен, предоставленной одним поставщиком программного обеспечения. Он был разработан для работы на разных низкоуровневых 2D- и 3D-интерфейсах, а первая основная производственная версия (v3.0) была завершена в 1991 году.
Silicon Graphics (SGI) выпустила OpenGL Performer или, чаще называемый Performer, в 1991 году, который стал основной системой графов сцен для большинства продуктов SGI в будущем. IRIS Inventor 1.0 (1992) был выпущен SGI и представлял собой высокоуровневый граф сцены, построенный на основе Performer. За ним последовал Open Inventor в 1994 году, еще одна итерация графа сцен высокого уровня, построенная на основе более новых версий Performer. Дополнительные библиотеки графов 3D-сцен можно найти в категории: API-интерфейсы 3D-графиков сцен .
X3D — это бесплатный формат файлов с открытыми стандартами и архитектурой времени выполнения для представления и передачи 3D-сцен и объектов с использованием XML . Это стандарт, ратифицированный ISO , который обеспечивает систему хранения, поиска и воспроизведения графического контента в реальном времени, встроенного в приложения, и все это в рамках открытой архитектуры для поддержки широкого спектра областей и пользовательских сценариев.