Граф сцены — это общая структура данных , обычно используемая приложениями для редактирования векторной графики и современными компьютерными играми, которая организует логическое и часто пространственное представление графической сцены. Это набор узлов в графе или древовидной структуре. Узел дерева может иметь много потомков, но только одного родителя, при этом эффект родителя применяется ко всем его дочерним узлам; операция, выполняемая над группой, автоматически распространяет свой эффект на всех ее членов. Во многих программах связывание матрицы геометрического преобразования (см. также преобразование и матрица ) на каждом уровне группы и объединение таких матриц вместе является эффективным и естественным способом обработки таких операций. Например, общей чертой является возможность группировать связанные фигуры и объекты в составной объект, которым затем можно манипулировать так же легко, как и одним объектом.
В векторном графическом редактировании каждый конечный узел в графе сцены представляет некоторую атомарную единицу документа, обычно форму, такую как эллипс или путь Безье . Хотя сами формы (особенно пути) могут быть далее разложены на узлы, такие как узлы сплайна , практичнее думать о графе сцены как о составленном из форм, а не переходить на более низкий уровень представления.
Еще одна полезная и управляемая пользователем концепция узла — это слой . Слой действует как прозрачный лист, на котором можно разместить любое количество фигур и групп фигур. Затем документ становится набором слоев, любой из которых можно удобно сделать невидимым, затемненным или заблокированным (сделать доступным только для чтения). Некоторые приложения помещают все слои в линейный список, в то время как другие поддерживают слои внутри слоев на любой желаемой глубине.
Внутри может не быть никакой реальной структурной разницы между слоями и группами, поскольку они оба являются просто узлами графа сцены. Если различия необходимы, то общим объявлением типа в C++ будет создание универсального класса узла, а затем выведение слоев и групп в качестве подклассов. Например, член видимости будет функцией слоя, но не обязательно группы.
Графы сцены полезны для современных игр, использующих 3D-графику и все более крупные миры или уровни. В таких приложениях узлы в графе сцены (обычно) представляют сущности или объекты на сцене.
Например, игра может определить логическую связь между рыцарем и лошадью, так что рыцарь будет считаться расширением лошади. Граф сцены будет иметь узел «лошадь» с присоединенным к нему узлом «рыцарь».
Граф сцены может также описывать пространственные и логические взаимоотношения различных сущностей: рыцарь движется в трехмерном пространстве, пока движется конь.
В этих больших приложениях требования к памяти являются основными соображениями при проектировании графа сцены. По этой причине многие большие системы графа сцены используют геометрическое инстансирование для снижения затрат памяти и увеличения скорости. В нашем примере выше каждый рыцарь является отдельным узлом сцены, но графическое представление рыцаря (состоящее из 3D-сетки, текстур, материалов и шейдеров) инстансируется. Это означает, что сохраняется только одна копия данных, на которую затем ссылаются любые узлы «рыцаря» в графе сцены. Это позволяет сократить бюджет памяти и увеличить скорость, поскольку при создании нового узла рыцаря данные о внешнем виде не нужно дублировать.
Простейшая форма графа сцены использует массив или структуру данных связанного списка , а отображение его форм — это просто вопрос линейной итерации узлов один за другим. Другие общие операции, такие как проверка того, какая форма пересекает указатель мыши, также выполняются с помощью линейного поиска. Для небольших графов сцены этого обычно достаточно.
Применение операции к графу сцены требует некоторого способа диспетчеризации операции на основе типа узла. Например, в операции рендеринга узел группы преобразований будет накапливать свое преобразование путем умножения матриц, смещения векторов, кватернионов или углов Эйлера . После чего конечный узел отправляет объект для рендеринга рендереру. Некоторые реализации могут напрямую рендерить объект, что вызывает базовый API рендеринга , такой как DirectX или OpenGL . Но поскольку базовая реализация API рендеринга обычно не обладает переносимостью, вместо этого можно разделить граф сцены и системы рендеринга. Чтобы выполнить этот тип диспетчеризации, можно использовать несколько различных подходов.
В объектно-ориентированных языках, таких как C++ , этого можно легко добиться с помощью виртуальных функций , где каждая представляет операцию, которая может быть выполнена на узле. Виртуальные функции просты в написании, но обычно невозможно добавлять новые операции к узлам без доступа к исходному коду. В качестве альтернативы можно использовать шаблон посетителя . У него есть аналогичный недостаток, заключающийся в том, что добавлять новые типы узлов также сложно.
Другие методы включают использование RTTI ( Run-Time Type Information ). Операция может быть реализована как класс, который передается текущему узлу; затем он запрашивает тип узла с помощью RTTI и ищет правильную операцию в массиве обратных вызовов или функторов . Это требует, чтобы отображение типов в обратные вызовы или функторы было инициализировано во время выполнения, но обеспечивает большую гибкость, скорость и расширяемость.
Существуют вариации этих методов, и новые методы могут предложить дополнительные преимущества. Одной из альтернатив является перестроение графа сцены, когда граф сцены перестраивается для каждой выполненной операции. Это, однако, может быть очень медленным, но создает высокооптимизированный граф сцены. Это показывает, что хорошая реализация графа сцены сильно зависит от приложения, в котором она используется.
Обходы являются ключом к силе применения операций к графам сцены. Обход обычно состоит из начала в некотором произвольном узле (часто корне графа сцены), применения операции(й) (часто операции обновления и рендеринга применяются одна за другой) и рекурсивного перемещения вниз по графу сцены (дереву) к дочерним узлам, пока не будет достигнут конечный узел. В этот момент многие движки графа сцены затем возвращаются к дереву, применяя аналогичную операцию. Например, рассмотрим операцию рендеринга, которая учитывает преобразования: при рекурсивном обходе вниз по иерархии графа сцены вызывается операция предварительного рендеринга. Если узел является узлом преобразования, он добавляет свое собственное преобразование к текущей матрице преобразования. Как только операция завершает обход всех дочерних узлов узла, она вызывает операцию пост-рендеринга узла, чтобы узел преобразования мог отменить преобразование. Такой подход радикально сокращает необходимое количество умножения матриц. [ необходима цитата ]
Некоторые операции с графом сцены на самом деле более эффективны, когда узлы обходят в другом порядке — именно здесь некоторые системы реализуют перестройку графа сцены, чтобы переупорядочить граф сцены в более простой для анализа формат или дерево.
Например, в 2D-случаях графы сцены обычно визуализируют себя, начиная с корневого узла дерева, а затем рекурсивно прорисовывают дочерние узлы. Листья дерева представляют самые передние объекты. Поскольку прорисовка выполняется сзади вперед, а более близкие объекты просто перезаписывают более дальние, этот процесс известен как использование алгоритма художника . В 3D-системах, которые часто используют буферы глубины , эффективнее сначала прорисовывать самые близкие объекты, поскольку более дальние объекты часто требуют только проверки глубины вместо фактической визуализации, поскольку они перекрыты более близкими объектами.
Иерархии ограничивающих объемов (BVH) полезны для множества задач, включая эффективную выборку и ускорение обнаружения столкновений между объектами. BVH — это пространственная структура, но она не должна разбивать геометрию (см. пространственное разбиение ниже).
BVH — это дерево ограничивающих объемов (часто сфер, выровненных по осям ограничивающих рамок или ориентированных ограничивающих рамок). Внизу иерархии размер объема достаточно велик, чтобы плотно охватить один объект (или, возможно, даже некоторую меньшую часть объекта в BVH высокого разрешения). По мере того, как вы поднимаетесь по иерархии, каждый узел имеет свой собственный объем, который плотно охватывает все объемы под ним. В корне дерева находится объем, который охватывает все объемы в дереве (всю сцену).
BVH полезны для ускорения обнаружения столкновений между объектами. Если ограничивающий объем объекта не пересекает объем выше в дереве, он не может пересекать ни один объект ниже этого узла (поэтому все они очень быстро отклоняются).
Между BVH и графами сцены есть некоторые сходства. Граф сцены можно легко адаптировать для включения/превращения в BVH – если каждый узел имеет связанный с ним том или есть специально созданный «связанный узел», добавленный в удобном месте в иерархии. Это может быть нетипичным видом графа сцены, но включение BVH в граф сцены имеет свои преимущества.
Эффективным способом объединения пространственного разбиения и графов сцены является создание конечного узла сцены, содержащего данные пространственного разбиения. [ необходимо пояснение ] Это может повысить вычислительную эффективность рендеринга.
Пространственные данные обычно статичны и, как правило, содержат неподвижные данные сцены в некоторой разделенной форме. [ требуется разъяснение ] Некоторые системы могут иметь системы и их рендеринг отдельно. Это нормально, и нет никаких реальных преимуществ ни у одного из методов . В частности, плохо иметь граф сцены, содержащийся в системе пространственного разбиения, поскольку граф сцены лучше рассматривать как более масштабную систему для пространственного разбиения. [ нейтральность оспаривается ]
Очень большие рисунки или графы сцены, которые генерируются исключительно во время выполнения (как это происходит в программах рендеринга трассировки лучей ), требуют определения узлов группы более автоматизированным способом. Например, трассировщик лучей возьмет описание сцены 3D- модели и построит внутреннее представление, которое разобьет ее отдельные части на ограничивающие рамки (также называемые ограничивающими плитами). Эти рамки сгруппированы иерархически, так что тесты пересечения лучей (как часть определения видимости) могут быть эффективно вычислены. Например, групповая рамка, которая не пересекает луч глаза, может полностью пропустить тестирование любого из своих членов.
Подобная эффективность сохраняется и в 2D-приложениях. Если пользователь увеличил документ так, что на экране компьютера видна только его часть, а затем прокручивает его, полезно использовать ограничивающую рамку (или, в данном случае, схему ограничивающего прямоугольника), чтобы быстро определить, какие элементы графа сцены видны и, следовательно, должны быть нарисованы.
В зависимости от особенностей производительности отрисовки приложения, на большую часть дизайна графа сцены могут влиять соображения эффективности рендеринга. В 3D-видеоиграх, таких как Quake , деревья двоичного разбиения пространства (BSP) в значительной степени предпочтительны для минимизации тестов видимости. Однако для вычисления деревьев BSP из графов сцены дизайна требуется очень много времени, и их необходимо пересчитывать, если граф сцены дизайна изменяется, поэтому уровни, как правило, остаются статичными, а динамические персонажи, как правило, не рассматриваются в схеме пространственного разбиения.
Графы сцены для плотных регулярных объектов, таких как поля высот и полигональные сетки, как правило, используют квадродеревья и октодеревья , которые являются специализированными вариантами иерархии 3D-ограничительных рамок. Поскольку поле высот само занимает объем рамок, рекурсивное подразделение этой рамок на восемь подрамок (отсюда «oct» в октодереве) до тех пор, пока не будут достигнуты отдельные элементы поля высот, является эффективным и естественным. Квадродерево — это просто 2D-октодерево.
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 стандарт, который предоставляет систему для хранения, поиска и воспроизведения графического контента в реальном времени, встроенного в приложения, все в рамках открытой архитектуры для поддержки широкого спектра доменов и пользовательских сценариев.