Граф сцены — структура данных, используемая главным образом в векторных графических редакторах и компьютерных играх. Примеры таких программ включают Acrobat 3D, Adobe Illustrator, AutoCAD, CorelDRAW, OpenSceneGraph, VRML97 и X3D.
Граф сцены представляет структуру, которая содержит логическое и зачастую (но не обязательно) пространственное представление графической сцены. Определение графа сцены нечёткое, поскольку программисты, осуществляющие его реализацию в приложениях, — и, в частности, в индустрии разработки игр — берут базовые принципы и адаптируют их для применения в конкретных приложениях. Это означает, что нет договорённости о том, каким должен быть граф сцены.
Граф сцены представляет собой набор узлов такой структуры, как граф или дерево. Узел дерева (в предельной структуре дерева графа сцены) может иметь множество потомков, но зачастую только одного предка, причём действие предка распространяется на все его дочерние узлы; эффект действия, выполненного над группой, автоматически распространяется на все её элементы. Во многих программах ассоциирование матрицы преобразования (см. также трансформации и матрицы) на уровне любой группы и умножение таких матриц представляет собой эффективный и естественный способ обработки таких действий. Общей особенностью, к примеру, является способность группировать связанные формы/объекты в составной объект, который можно перемещать, трансформировать, выбирать и т. д. так же просто, как и одиночный объект.
Иногда бывает и так, что в некоторых графах сцены узел может быть связан с любым другим, включая самого себя, или, по крайней мере, содержит расширение, которое ссылается на другой узел (например, PhotoRealistic RenderMan студии Pixar благодаря алгоритму визуализации Reyes и Acrobat 3D компании Adobe Systems благодаря улучшенным интерактивным манипуляциям).
Граф сцены в графических редакторах В векторных графических редакторах каждый листовой узел графа сцены представляет некоторую неделимую единицу документа, обычно форму, например, эллипс или путь Безье. Хотя формы сами по себе (в частности, пути) могут быть декомпозированы и дальше на такие элементы, как узлы сплайнов, на практике удобнее считать, что граф сцены состоит из форм, не опускаясь на более низкий уровень представления.
Другой полезной и определяемой пользователем концепцией узла является слой. Он действует как прозрачный лист, на котором может быть размещено любое число форм и их групп. Затем документ становится набором слоёв, каждый из которых при необходимости может быть сделан невидимым, полупрозрачным или заблокирован (доступен только для чтения). Некоторые приложения располагают все слои в виде линейного списка, в то время как другие поддерживают подуровни (то есть слои в слоях любого желаемого уровня вложенности).
Между слоями и группами может не быть вообще никакого внутреннего различия в структуре, поскольку и слои, и группы являются лишь узлами графа сцены. Если потребуются различия, с помощью объявления общих типов C++ был бы описан общий класс узла, а затем наследованы слои и группы как подклассы. Видимость элемента, например, была бы свойством слоя, но не обязательно группы.
Граф сцены в играх и 3D-приложениях Граф сцены является полезным в современных играх, использующих 3D-графику и постоянно возрастающие огромные миры и уровни. В таких приложениях узлы графа сцены (обычно) представляют сущности или объекты на сцене.
Например, в игре может быть определена логическая связь между рыцарем и конём, таким образом, рыцарь рассматривается как расширение коня. В графе сцены был бы узел «конь» с привязанным узлом «рыцарь».
Помимо описания логических отношений, граф сцены также может описывать пространственные отношения различных сущностей: рыцарь движется по трёхмерному пространству вместе с конём. В таких больших приложениях во время проектирования графа сцены требования к памяти являются определяющими. По этой причине многие системы с большими графами сцены используют клонирование для сокращения расходов памяти и увеличения скорости. В примере выше каждый рыцарь — отдельный узел сцены, но его графическое представление (состоящее из 3D-меша, текстур, материалов и шейдеров) подвергается клонированию. Это означает, что данные хранятся только в единственном экземпляре, на который затем ссылаются все узлы «рыцарей» графа сцены. Это позволяет сократить требования к памяти и увеличить скорость, поскольку при создании нового узла «рыцарь» не потребуется дублировать информацию о внешнем виде.
Реализация графа сцены Простейшая форма графа сцены использует массив либо структуру данных связный список, а отображение его форм есть лишь последовательная итерация узлов один за другим. Другие общие операции, такие как определение, какая форма пересекается с курсором мыши (например, в приложениях, основанных на графическом интерфейсе пользователя) также осуществляются путём линейного поиска. Для небольших графов сцены этого обычно достаточно.
Более масштабные графы сцены приводят к заметному замедлению линейных операций, так что используются более сложные структуры хранения основных данных, наиболее популярная и общая форма — это дерево. В этих графах сцены составной шаблон проектирования зачастую призван создать иерархическое представление узлов группировки и листовых узлов. Сгруппированные узлы могут иметь любое количество прикреплённых дочерних узлов. Сгруппированные узлы включают узлы трансформаций и коммутационные узлы. Листовые узлы — это узлы, которые в действительности подлежат визуализации, либо узлы, на которых виден результат какого-либо действия. Они включают объекты, спрайты, звуки, источники освещения и всё, что может рассматриваться как подлежащее «рендерингу» в некотором абстрактном смысле.
Операции над графом сцены и пересылка Применение операций к графу сцены требует некоторого способа пересылки операции, основанного на типе узла. Например, в случае визуализации узел трансформации группы накапливал бы информацию о трансформации с помощью умножения матриц, смещения векторов, кватернионов или углов Эйлера. После чего листовой узел отправляет объект на визуализацию. В некоторых реализациях визуализация может осуществляться напрямую, при помощи используемого API визуализации — такого, как DirectX или OpenGL. Но, поскольку API используемой реализации обычно приводит к сложностям в переносе на другие платформы, можно разделять граф сцены и систему визуализации. Чтобы совершить этот вид пересылки, могут быть применены несколько подходов.
В объектно-ориентированных языках, таких как C++, это легко осуществить с помощью виртуальных функций, каждая из которых представляет операцию, которую можно применить к узлу. Виртуальные функции просты в написании, но обычно нет возможности добавлять новые операции без доступа к исходному коду. В качестве альтернативы может быть использован шаблон проектирования «Посетитель». Но этот подход не лишён того же недостатка из-за невозможности добавлять новые виды узлов.
Другие методы используют RTTI (Run-Time Type Information, информацию времени выполнения о типах). Операция может быть выполнена в виде класса, который передаётся в текущий узел; затем он запрашивает информацию о типе узла с использованием RTTI и осуществляет поиск корректной операции в массиве функций обратного вызова или функторов. Это требует того, чтобы ассоциативный массив типов функций обратного вызовы или функторов был инициализирован во время исполнения программы, но предоставляет большую гибкость, скорость и расширяемость. Существуют разновидности этих методов, и новые методы могут предлагать дополнительные преимущества. Одним из таких вариантов является перестроение графа сцены во время каждой из исполняемых операций. Это приводит к снижению скорости и созданию хорошо оптимизированного графа сцены. Это показывает, что хорошая реализация графа сцены сильно зависит от приложения, в котором он используется.
Виды обхода Обход графа сцены — ключевой момент в достижении быстродействия применения операций к графам сцены. Обход обычно состоит из произвольного начального узла (часто это корневой узел графа сцены), применения операции или операций (зачастую операции обновления и визуализации применяются одна за другой) и рекурсивного движения вниз по графу сцены (дереву) к дочерним узлам, пока не будет достигнут листовой узел. После этого многие средства для управления графами сцены осуществляют обход дерева в обратном направлении, применяя аналогичную операцию. Например, рассмотрим операцию визуализации, которая принимает информацию: во время рекурсивного нисходящего обхода иерархии графа сцены вызывается операция, предшествующая визуализации. Если узел является узлом трансформации, он добавляет собственную информацию о трансформации к текущей матрице трансформации. После того как операция заканчивает обход всех узлов-потомков, она вызывает операцию, следующую за визуализацией, поэтому узел трансформации может отменить трансформацию. Этот подход радикально сокращает число необходимых умножений матриц.
Некоторые операции графа сцены в действительности более эффективны, когда обход узлов осуществляется в различном порядке, например, когда некоторые системы применяют перестроение графа сцены, чтобы преобразовать его в более пригодный для разбора формат или дерево.
В двумерном случае, например, граф сцены обычно осуществляет визуализацию, начиная с корневого узла, а затем и рекурсивную визуализацию всех дочерних узлов. Листовые узлы представляют наиболее близкие к наблюдателю объекты. Поскольку визуализация происходит от заднего плана к переднему, когда более близкие объекты перекрывают дальние, этот процесс также известен, как «алгоритм живописца». В трёхмерных системах, которые часто используют буферы глубины, более эффективно сначала рисовать наиболее близкие объекты, поскольку удалённые объекты зачастую требуют только отсечения вместо визуализации, потому что они перекрываются более близкими объектами.
Граф сцены и иерархия ограничивающих объёмов Иерархии ограничивающих объёмов (Bounding Volume Hierarchies, BVHs) полезны для ряда задач, включая эффективное отсечение и быстрое определение столкновений между объектами. Иерархия ограничивающих объёмов — это пространственная структура, однако она не требует разбиения геометрии (см. о разбиении пространства ниже).
Иерархия ограничивающих объёмов — это дерево ограничивающих объёмов (часто это сферы, выравненные по осям ограничивающие параллелепипеды (AABB) либо ориентированные ограничивающие параллелепипеды). В самом низу этой иерархии ограничивающий объём имеет размер, минимально необходимый для того, чтобы точно вмещать один объект (возможно, даже некоторую небольшую часть объекта в случае с иерархиями ограничивающих объёмов высокого разрешения). Если идти вверх по этой иерархии, каждый узел имеет свой объём, который необходим для того, чтобы в точности охватывать все вмещаемые объёмы. Корневой узел содержит объём, вмещающий в себя все остальные объёмы в дереве (всю сцену).
Иерархии ограничивающих объёмов полезны для увеличения скорости обнаружения столкновений между объектами. Если ограничивающий объём объекта не пересекается с объёмом, находящимся выше по иерархии дерева, он не может пересекаться ни с какими объектами ниже этого узла (поэтому они все отбрасываются очень быстро).
Очевидно, что между иерархиями ограничивающих объёмов и графами сцены много общего. Граф сцены может быть легко адаптирован для включения иерархии ограничивающих объёмов либо превращении в неё; если каждый узел имеет ассоциированный объём или встроенный «узел объёма», добавленный в подходящее место в иерархии. Это может отличаться от типичного графа сцены, но есть преимущества от включения иерархии ограничивающих объёмов в граф сцены.
Граф сцены и разбиение пространства