Interested Article - Граф сцены

Граф сцены — структура данных , используемая главным образом в векторных графических редакторах и компьютерных играх . Примеры таких программ включают Acrobat 3D, Adobe Illustrator , AutoCAD , Corel DRAW, 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 ) либо ориентированные ограничивающие параллелепипеды). В самом низу этой иерархии ограничивающий объём имеет размер, минимально необходимый для того, чтобы точно вмещать один объект (возможно, даже некоторую небольшую часть объекта в случае с иерархиями ограничивающих объёмов высокого разрешения). Если идти вверх по этой иерархии, каждый узел имеет свой объём, который необходим для того, чтобы в точности охватывать все вмещаемые объёмы. Корневой узел содержит объём, вмещающий в себя все остальные объёмы в дереве (всю сцену).

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

Очевидно, что между иерархиями ограничивающих объёмов и графами сцены много общего. Граф сцены может быть легко адаптирован для включения иерархии ограничивающих объёмов либо превращении в неё; если каждый узел имеет ассоциированный объём или встроенный «узел объёма», добавленный в подходящее место в иерархии. Это может отличаться от типичного графа сцены, но есть преимущества от включения иерархии ограничивающих объёмов в граф сцены.

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

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

Комбинирование методов

Вкратце: разбиение пространства призвано заметно ускорить обработку и визуализацию графа сцены.

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

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

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

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

Стандарты

PHIGS

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

X3D

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

См. также

Литература

Leler, Wm and Merry, Jim (1996) 3D with HOOPS , Addison-Wesley
Wernecke, Josie (1994) The Inventor Mentor: Programming Object-Oriented 3D Graphics with Open Inventor , Addison-Wesley, ISBN 0-201-62495-8 (Release 2)
Bar-Zeev, Avi.
Carey, Rikk and Bell, Gavin (1997).
Helman, Jim; Rohlf, John (1994).