Графа сцены общая структура данных обычно используется векторной графикой редактирования приложений и современные компьютерные игр, которые организуют логическое и часто пространственное представление графической сцены. Это набор узлов в графической или древовидной структуре. Узел дерева может иметь много дочерних узлов, но только одного родителя, причем эффект родителя применяется ко всем его дочерним узлам; операция, выполняемая в группе, автоматически распространяется на всех ее членов. Во многих программах связывание матрицы геометрического преобразования (см. Также преобразование и матрицу) на каждом уровне группы, и объединение таких матриц вместе является эффективным и естественным способом обработки таких операций. Общей особенностью, например, является возможность группировать связанные формы и объекты в составной объект, которым затем можно манипулировать так же легко, как одним объектом.
Графики сцены в инструментах редактирования графики
При редактировании векторной графики каждый конечный узел в графе сцены представляет некоторую элементарную единицу документа, обычно такую форму, как эллипс или путь Безье . Хотя сами формы (в частности, пути) могут быть дополнительно разложены на узлы, такие как узлы сплайна , целесообразно рассматривать граф сцены как состоящий из форм, а не переходить на более низкий уровень представления.
Еще одна полезная и управляемая пользователем концепция узла - это слой . Слой действует как прозрачный лист, на котором можно разместить любое количество фигур и групп фигур. Затем документ становится набором слоев, любой из которых можно удобно сделать невидимым, затемнить или заблокировать (сделать доступным только для чтения). Некоторые приложения помещают все слои в линейный список, в то время как другие поддерживают слои внутри слоев с любой желаемой глубиной.
Внутри может вообще не быть реальной структурной разницы между слоями и группами, поскольку они оба являются лишь узлами графа сцены. Если необходимы различия, объявление общего типа в C ++ будет заключаться в создании общего класса узла, а затем наследовании слоев и групп как подклассов. Например, элемент видимости может быть элементом слоя, но не обязательно группы.
Графики сцен в играх и 3D-приложениях
Графики сцен полезны для современных игр с использованием трехмерной графики и все более больших миров или уровней. В таких приложениях узлы в графе сцены (как правило) представляют сущности или объекты в сцене.
Например, игра может определять логические отношения между рыцарем и лошадью, так что рыцарь считается продолжением лошади. Граф сцены будет иметь узел "лошадь" с прикрепленным к нему узлом "рыцарь".
Граф сцены может также описывать пространственные, а также логические отношения различных объектов: рыцарь перемещается в трехмерном пространстве вместе с лошадью.
В этих больших приложениях требования к памяти являются основными соображениями при проектировании графа сцены. По этой причине многие системы с большими графами сцены используют создание экземпляров геометрии для снижения затрат на память и увеличения скорости. В нашем примере выше каждый рыцарь является отдельным узлом сцены, но графическое представление рыцаря (состоящее из трехмерной сетки, текстур, материалов и шейдеров) является экземпляром. Это означает, что сохраняется только одна копия данных, на которую затем ссылаются любые узлы «рыцарь» в графе сцены. Это позволяет сократить бюджет памяти и увеличить скорость, поскольку при создании нового узла Knight данные о внешнем виде не нужно дублировать.
Реализация графа сцены
В простейшей форме графа сцены используется массив или структура данных связанного списка , и отображение его форм - это просто вопрос линейного перебора узлов один за другим. Другие общие операции, такие как проверка того, какая форма пересекает указатель мыши , также выполняются с помощью линейного поиска. Для небольших графов сцены этого достаточно.
Операции с графом сцены и отправка
Применение операции к графу сцены требует некоторого способа диспетчеризации операции на основе типа узла. Например, в операции визуализации узел группы преобразования будет накапливать свое преобразование путем умножения матриц, смещения вектора, кватернионов или углов Эйлера . После чего листовой узел отправляет объект на рендеринг в рендерер. Некоторые реализации могут визуализировать объект напрямую, что вызывает базовый API визуализации , такой как DirectX или OpenGL . Но поскольку базовой реализации API рендеринга обычно не хватает переносимости, вместо этого можно разделить граф сцены и системы рендеринга. Для выполнения этого типа диспетчеризации можно использовать несколько различных подходов.
В объектно-ориентированных языках, таких как C ++ , этого легко добиться с помощью виртуальных функций , каждая из которых представляет операцию, которая может быть выполнена на узле. Виртуальные функции легко написать, но обычно невозможно добавлять новые операции к узлам без доступа к исходному коду. В качестве альтернативы можно использовать шаблон посетителя . Такой же недостаток заключается в том, что так же сложно добавлять новые типы узлов.
Другие методы включают использование RTTI ( информации о типе времени выполнения ). Операция может быть реализована как класс, который передается текущему узлу; Затем он запрашивает тип узла с помощью RTTI и ищет правильную операцию в массиве обратных вызовов или функторов . Для этого требуется, чтобы сопоставление типов с обратными вызовами или функторами было инициализировано во время выполнения, но обеспечивает большую гибкость, скорость и расширяемость.
Существуют вариации этих методов, и новые методы могут предложить дополнительные преимущества. Одна из альтернатив - перестроение графа сцены, при котором граф сцены перестраивается для каждой выполняемой операции. Это, однако, может быть очень медленным, но дает хорошо оптимизированный граф сцены. Он демонстрирует, что хорошая реализация графа сцены сильно зависит от приложения, в котором он используется.
Обходы
Обходы - это ключ к возможности применения операций к графам сцены. Обход обычно состоит из начала с некоторого произвольного узла (часто корня графа сцены), применения операции (операций) (часто операции обновления и рендеринга применяются одна за другой) и рекурсивного перемещения вниз по графу сцены (дерево ) к дочерним узлам, пока не будет достигнут листовой узел. На этом этапе многие движки графа сцены затем возвращаются вверх по дереву, применяя аналогичную операцию. Например, рассмотрим операцию визуализации, которая учитывает преобразования: при рекурсивном перемещении вниз по иерархии графа сцены вызывается операция предварительной визуализации. Если узел является узлом преобразования, он добавляет собственное преобразование к текущей матрице преобразования. Как только операция завершает обход всех дочерних узлов узла, она вызывает операцию пост-рендеринга узла, чтобы узел преобразования мог отменить преобразование. Такой подход резко снижает необходимое количество умножения матриц. [ необходима цитата ]
Некоторые операции с графом сцены на самом деле более эффективны, когда узлы проходят в другом порядке - именно здесь некоторые системы реализуют перестройку графа сцены, чтобы переупорядочить граф сцены в более простой для анализа формат или дерево.
Например, в двухмерных случаях графы сцены обычно визуализируются, начиная с корневого узла дерева, а затем рекурсивно рисуют дочерние узлы. Листья дерева представляют собой большинство объектов переднего плана. Поскольку рисование происходит сзади наперед, а более близкие объекты просто перезаписывают более удаленные, этот процесс известен как использование алгоритма художника . В 3D-системах, в которых часто используются буферы глубины , более эффективно сначала рисовать ближайшие объекты, поскольку более удаленные объекты часто нуждаются только в проверке глубины, а не на реальном рендеринге, поскольку они перекрываются более близкими объектами.
Графики сцен и иерархии ограничивающих объемов (BVH)
Иерархии граничных объемов (BVH) полезны для множества задач, включая эффективное отбраковку и ускорение обнаружения столкновений между объектами. BVH - это пространственная структура, но она не обязана разделять геометрию (см. Пространственное разбиение ниже).
BVH - это дерево ограничивающих объемов (часто сфер, выровненных по оси ограничивающих рамок или ориентированных ограничивающих рамок). Внизу иерархии размер объема достаточно велик, чтобы плотно охватить один объект (или, возможно, даже некоторую меньшую часть объекта в BVH с высоким разрешением). По мере подъема по иерархии каждый узел имеет свой собственный том, который плотно охватывает все тома, находящиеся под ним. В корне дерева находится том, охватывающий все тома дерева (всю сцену).
BVH полезны для ускорения обнаружения столкновений между объектами. Если ограничивающий объем объекта не пересекает объем выше в дереве, он не может пересекать какой-либо объект ниже этого узла (поэтому все они очень быстро отклоняются).
Есть некоторое сходство между BVH и графами сцены. Граф сцены может быть легко адаптирован для включения / превращения в BVH - если каждый узел имеет связанный том или есть специально созданный «связанный узел», добавленный в удобном месте в иерархии. Возможно, это не типичный вид графа сцены, но включение BVH в граф сцены дает свои преимущества.
Графики сцен и пространственное разбиение
Эффективный способ объединения пространственного разделения и графов сцены - создание конечного узла сцены, который содержит данные пространственного разделения. [ требуется пояснение ] Это может повысить вычислительную эффективность рендеринга.
Пространственные данные обычно статичны и обычно содержат неподвижные данные сцены в некоторой секционированной форме. [ требуется пояснение ] Некоторые системы могут иметь системы и их визуализацию отдельно. Это нормально, и у обоих методов нет реальных преимуществ. В частности, плохо иметь граф сцены, содержащийся в системе пространственного разделения, поскольку граф сцены лучше рассматривать как более обширную систему для пространственного разделения. [ Нейтральность является спорным ]
Очень большие чертежи или графы сцены, которые создаются исключительно во время выполнения (как это происходит в программах рендеринга с трассировкой лучей ), требуют определения групповых узлов более автоматизированным способом. Например, трассировщик лучей возьмет описание сцены 3D- модели и построит внутреннее представление, которое разбивает его отдельные части на ограничивающие прямоугольники (также называемые ограничивающими плитами). Эти блоки сгруппированы иерархически, так что тесты пересечения лучей (как часть определения видимости) могут быть эффективно вычислены. Например, групповая рамка, которая не пересекает луч глаза, может полностью пропустить тестирование любого из своих элементов.
Аналогичная эффективность сохраняется и в 2D-приложениях. Если пользователь увеличил документ так, чтобы на экране компьютера была видна только его часть, а затем прокручивает его, полезно использовать ограничивающую рамку (или, в данном случае, схему ограничивающего прямоугольника), чтобы быстро определить, какая сцена элементы графика видны и, следовательно, их нужно нарисовать.
В зависимости от особенностей производительности отрисовки приложения, на большую часть дизайна графа сцены могут повлиять соображения эффективности рендеринга. В 3D-видеоиграх, таких как Quake , деревья с разбиением на двоичное пространство (BSP) сильно отдают предпочтение для минимизации тестов на видимость. Однако для вычисления BSP-деревьев из графов сцены дизайна требуется очень много времени, и их необходимо пересчитывать, если граф сцены дизайна изменяется, поэтому уровни имеют тенденцию оставаться статическими, а динамические символы обычно не учитываются в схеме пространственного разделения.
Графики сцены для плотных регулярных объектов, таких как поля высот и полигональные сетки, как правило, используют квадродеревья и октодеревья , которые являются специализированными вариантами иерархии трехмерной ограничительной рамки. Поскольку поле высот занимает сам объем блока, рекурсивное деление этого блока на восемь подбоксов (отсюда «окт» в октодереве) до тех пор, пока не будут достигнуты отдельные элементы поля высоты, является эффективным и естественным. Квадродерево - это просто двумерное октодерево.
Стандарты
ФИГС
PHIGS была первой коммерческой спецификацией графа сцены и стала стандартом ANSI в 1988 году. Разрозненные реализации были предоставлены поставщиками оборудования Unix . Система трехмерной графики HOOPS оказалась первой коммерческой библиотекой графов сцены, предоставленной одним поставщиком программного обеспечения. Он был разработан для работы на разрозненных двухмерных и трехмерных интерфейсах нижнего уровня, а первая основная производственная версия (v3.0) была завершена в 1991 году.
SGI
В 1991 году Silicon Graphics (SGI) выпустила OpenGL Performer или более часто называемый Performer, который стал основной системой графа сцен для большинства продуктов SGI в будущем. IRIS Inventor 1.0 (1992) был выпущен SGI и представлял собой высокоуровневый граф сцены, построенный на основе Performer. За ним последовал Open Inventor в 1994 году, еще одна итерация графа сцены высокого уровня, построенная на основе более новых выпусков Performer. Дополнительные библиотеки графов 3D-сцен можно найти в разделе Категория: API-интерфейсы 3D-сцен .
X3D
X3D - это бесплатный формат файлов с открытыми стандартами и архитектура времени выполнения для представления и передачи трехмерных сцен и объектов с помощью XML . Это сертифицированный ISO стандарт, который обеспечивает систему для хранения, извлечения и воспроизведения графического контента в реальном времени, встроенного в приложения, в рамках открытой архитектуры для поддержки широкого спектра доменов и пользовательских сценариев.
Смотрите также
- График (структура данных)
- Теория графов
- Разделение пространства
- Дерево (структура данных)
Рекомендации
Книги
- Лелер, Вм и Мерри, Джим (1996) 3D с ОБРУЧАМИ , Эддисон-Уэсли
- Вернеке, Джози (1994) Наставник изобретателя: Программирование объектно-ориентированной трехмерной графики с помощью Open Inventor , Эддисон-Уэсли, ISBN 0-201-62495-8 (Выпуск 2)
Статьи
- Бар-Зеев, Ави. «Сцены: прошлое, настоящее и будущее»
- Кэри, Рикк и Белл, Гэвин (1997). "Справочное руководство по VRML 97 с аннотациями"
- Джеймс Х. Кларк (1976). «Иерархические геометрические модели для алгоритмов видимой поверхности» . Коммуникации ACM . 19 (10): 547–554. DOI : 10.1145 / 360349.360354 .
- Хелман, Джим; Рольф, Джон (1994). "IRIS Performer: высокопроизводительный набор инструментов для многопроцессорной обработки трехмерной графики в реальном времени"
- PEXTimes - «Неофициально, расширение PHIGS для X. Официально PEX не было аббревиатурой».
- Штраус, Пол (1993). «IRIS Inventor, набор инструментов для 3D-графики»
Внешние ссылки
- Java3D
- Авиатрикс3D
- LG3D
- OpenSG
- IRISPerformer
- OpenSceneGraph
- Библиотека визуализации