Граф сцени

Граф сцени (англ. scene graph) — загальна структура даних, що зазвичай використовується в застосуваннях для роботи з векторною графікою і в сучасних комп'ютерних іграх, яка впорядковує логічне і часто (але не обов'язково) просторове представлення графічної сцени. Прикладами таких програм є Acrobat 3D, Adobe Illustrator, AutoCAD, CorelDRAW, OpenSceneGraph, OpenSG, VRML97, X3D, Hoops і Open Inventor.

Граф сцени є колекцією вузлів у структурі графу або дерева. Вузол дерева (у загальній структурі дерева графу сцени) може мати багато дочірніх вузлів але найчастіше лише один спільний корінь, і ефекти, що застосовуються до кореня застосовуються і до всіх його дочірніх вузлів; операції виконані з групою автоматично переносять їх ефект на всіх членів групи. У багатьох програмах, ефективним і природним способом здійснювати операції є об'єднання геометричних матриць перетворення (див. також перетворення і матриці) на кожному рівні групування і зв'язування таких матриць разом. Загальним функціоналом, наприклад, є можливість групувати пов'язані фігури/об'єкти у складений об'єкт, який можна переміщувати, перетворювати, виділяти тощо, так само просто як і будь-який окремий об'єкт.

Визначення графа сцени нечітке, оскільки програмісти, які здійснюють його реалізацію в додатках і, зокрема, в індустрії розроблення ігор беруть базові принципи та адаптують їх для застосування в конкретних додатках. Це означає, що немає домовленості про те, яким має бути граф сцени. Термін «граф сцени» іноді плутають з поняттям «канвас», оскільки деякі реалізації канваса містять функціональність графу сцени.

Граф сцени в графічних редакторах

У векторних графічних редакторах кожен листовий вузол графа сцени представляє деяку неподільну одиницю документа, зазвичай форму, наприклад, еліпс або шлях Безьє. Хоча форми самі по собі (зокрема, шляхи) можуть бути декомпоновані й далі на такі елементи, як вузли сплайнів, на практиці зручніше вважати, що граф сцени складається з форм, не опускаючись на нижчий рівень представлення.

Іншою корисною концепцією вузла, яка визначається користувачем, є шар. Він діє як прозорий аркуш, на якому може бути розміщено будь-яку кількість форм та їхніх груп. Потім документ стає набором шарів, кожен з яких за необхідності може бути зроблений невидимим, напівпрозорим або заблокований (доступний тільки для читання). Деякі додатки розташовують усі шари у вигляді лінійного списку, тоді як інші підтримують підрівні (тобто шари в шарах будь-якого бажаного рівня вкладеності).

Між шарами й групами може не бути взагалі ніякої внутрішньої відмінності в структурі, оскільки як шари, так і групи є лише вузлами графа сцени. Якщо будуть потрібні відмінності, за допомогою оголошення загальних типів C++ був би описаний загальний клас вузла, а потім успадковані шари і групи як підкласи. Видимість елемента, наприклад, була б властивістю шару, але не обов'язково групи.

Граф сцени в іграх і 3D-додатках

Граф сцени є корисним у сучасних іграх, що використовують 3D-графіку та постійно зростаючі величезні світи та рівні. У таких додатках вузли графа сцени (зазвичай) представляють сутності або об'єкти на сцені.

Наприклад, у грі може бути визначено логічний зв'язок між лицарем і конем, отже, лицар розглядається як розширення коня. У графі сцени був би вузол "кінь" із прив'язаним вузлом "лицар".

Крім опису логічних відносин, граф сцени також може описувати просторові відносини різних сутностей: лицар рухається тривимірним простором разом із конем. У таких великих додатках під час проєктування графа сцени вимоги до пам'яті є визначальними. З цієї причини багато систем із великими графами сцени використовують клонування для скорочення витрат пам'яті та збільшення швидкості. У наведеному вище прикладі кожен лицар - окремий вузол сцени, але його графічне представлення (що складається з 3D-сітки, текстур, матеріалів і шейдерів) піддається клонуванню. Це означає, що дані зберігаються тільки в єдиному екземплярі, на який потім посилаються всі вузли "лицарів" графа сцени. Це дає змогу скоротити вимоги до пам'яті та збільшити швидкість, оскільки під час створення нового вузла "лицар" не потрібно дублювати інформацію про зовнішній вигляд.

Реалізація графа сцени

Найпростіша форма графа сцени використовує масив або структуру даних зв'язний список, а відображення його форм є лише послідовна ітерація вузлів один за одним. Інші загальні операції, як-от визначення, яка форма перетинається з курсором миші (наприклад, у додатках, що базуються на графічному інтерфейсі користувача) також здійснюються шляхом лінійного пошуку. Для невеликих графів сцени цього зазвичай достатньо.

Масштабніші графи сцени призводять до помітного сповільнення лінійних операцій, тож використовуються складніші структури зберігання основних даних, найпопулярніша та найзагальніша форма - це дерево. У цих графах сцени складовий шаблон проєктування часто покликаний створити ієрархічне представлення вузлів угруповання і листових вузлів. Згруповані вузли можуть мати будь-яку кількість прикріплених дочірніх вузлів. Згруповані вузли включають вузли трансформацій і комутаційні вузли. Листові вузли - це вузли, які насправді підлягають візуалізації, або вузли, на яких видно результат будь-якої дії. До них належать об'єкти, спрайти, звуки, джерела освітлення і все, що можна розглядати як таке, що підлягає "рендерингу" в деякому абстрактному сенсі

Операції над графом сцени та пересилання

Застосування операцій до графа сцени вимагає деякого способу пересилання операції, заснованого на типі вузла. Наприклад, у разі візуалізації вузол трансформації групи накопичував би інформацію про трансформацію за допомогою множення матриць, зміщення векторів, кватерніонів або кутів Ейлера. Після чого листовий вузол відправляє об'єкт на візуалізацію. У деяких реалізаціях візуалізація може здійснюватися безпосередньо, за допомогою використовуваного API візуалізації - такого, як DirectX або OpenGL. Але, оскільки API використовуваної реалізації зазвичай призводить до складнощів у перенесенні на інші платформи, можна розділяти граф сцени і систему візуалізації. Щоб здійснити цей вид пересилання, можуть бути застосовані кілька підходів.

В об'єктноорієнтованих мовах, таких як C++, це легко здійснити за допомогою віртуальних функцій, кожна з яких представляє операцію, яку можна застосувати до вузла. Віртуальні функції прості в написанні, але зазвичай немає можливості додавати нові операції без доступу до вихідного коду. Як альтернативу може бути використано шаблон проєктування "Відвідувач". Але цей підхід не позбавлений того самого недоліку через неможливість додавати нові види вузлів.

Інші методи використовують RTTI (Run-Time Type Information, динамічна ідентифікація типу). Операція може бути виконана у вигляді класу, який передається в поточний вузол; потім він запитує інформацію про тип вузла з використанням RTTI і здійснює пошук коректної операції в масиві функцій зворотного виклику або функторів. Це вимагає того, щоб асоціативний масив типів функцій зворотного виклику або функторів було ініціалізовано під час виконання програми, але надає більшу гнучкість, швидкість і розширюваність. Існують різновиди цих методів, і нові методи можуть пропонувати додаткові переваги. Одним із таких варіантів є перебудова графа сцени під час кожної з виконуваних операцій. Це призводить до зниження швидкості та створення добре оптимізованого графа сцени. Це показує, що хороша реалізація графа сцени сильно залежить від програми, в якій він використовується.

Стандарти

PHIGS

PHIGS був першою комерційною специфікацією графу сцени, і став стандартом ANSI в 1988. Розрізнені реалізації були надані виробниками обладнання на Unix. HOOPS 3D Graphics System була першою комерційною бібліотекою, що надавала функціонал графу сцени. Вона дозволяла виконувати низькорівневі 2D і 3D інтерфейси в 1991. Згодом, Silicon Graphics випустила IRIS Inventor 1.0 (1992), що було збіркою графу сцени поверх програмного інтерфейсу IRIS GL 3D API. За нею слідувала Open Inventor в 1994, переносний граф сцени на базі OpenGL.

X3D

X3D є безоплатним відкритим стандартом формату файлів і архітектури програм часу виконання для представлення і передачі 3D сцен і об'єктів на основі XML. Це міжнародний ISO-одобрений стандарт, який надає структуровану систему для збереження, відкриття і програвання вмісту з графікою реального часу вбудованою в застосування, і все це на базі відкритої архітектури, аби надати підтримку великій кількості доменів і сценаріїв користувачів.

Посилання

• Java3D
  • Aviatrix3D [Архівовано 1 квітня 2004 у Wayback Machine.]
  • LG3D
• OpenSG
• OpenSceneGraph [Архівовано 4 квітня 2009 у Wayback Machine.]
• OSG.JS [Архівовано 16 березня 2013 у WebCite] Javascript Implementation of OpenSceneGraph
• Visualization Library