Graf scény je datová struktura používaná především ve vektorových grafických editorech a počítačových hrách . Příklady takových programů zahrnují Acrobat 3D, Adobe Illustrator , AutoCAD , CorelDRAW , OpenSceneGraph , VRML97 a X3D .
Graf scény představuje strukturu, která obsahuje logické a často (ale ne nutně) prostorové znázornění grafické scény. Definice grafu scény je nejasná, protože programátoři, kteří jej implementují v aplikacích - a zejména v průmyslu vývoje her - berou základní principy a přizpůsobují je pro použití v konkrétních aplikacích. To znamená, že neexistuje shoda v tom, jaký by měl být graf scény.
Graf scény je sada uzlů ve struktuře, jako je graf nebo strom . Uzel stromu (v limitní stromové struktuře grafu scény) může mít mnoho potomků, ale často pouze jednoho rodiče, přičemž akce rodiče se rozšiřuje na všechny jeho podřízené uzly; účinek akce provedené na skupině se automaticky rozdělí na všechny její prvky. V mnoha programech je sdružování transformační matice (viz také transformace a matice) na úrovni jakékoli skupiny a násobení takových matic účinným a přirozeným způsobem, jak takové operace zvládnout. Společnou vlastností je například možnost seskupovat související tvary/objekty do složeného objektu, který lze přesouvat, transformovat, vybírat atd. stejně snadno jako jeden objekt.
Někdy se také stává, že v některých grafech scén může být uzel propojen s jakýmkoli jiným uzlem, včetně sebe sama, nebo alespoň obsahuje rozšíření, které odkazuje na jiný uzel (například PhotoRealistic RenderMan společnosti Pixar díky vykreslovacímu algoritmu Reyes a Acrobat 3D od Adobe Systems díky vylepšeným interaktivním manipulacím).
V editorech vektorové grafiky představuje každý listový uzel grafu scény nějakou nedělitelnou jednotku dokumentu, obvykle tvar, jako je elipsa nebo Bézierova cesta. Přestože samotné tvary (zejména cesty) lze dále rozkládat na prvky, jako jsou spline uzly, v praxi je vhodnější uvažovat o grafu scény tak, že se skládá z tvarů bez sestupování na nižší úroveň zobrazení.
Dalším užitečným a uživatelem definovaným konceptem uzlu je vrstva. Funguje jako průhledný list, na který lze umístit libovolný počet tvarů a jejich skupin. Dokument se poté stane sadou vrstev, z nichž každá může být podle potřeby neviditelná, průsvitná nebo uzamčená (pouze pro čtení). Některé aplikace uspořádají všechny vrstvy do lineárního seznamu, zatímco jiné podporují podúrovně (tj. vrstvy uvnitř vrstev libovolné požadované úrovně vnoření).
Mezi vrstvami a skupinami nemusí být vůbec žádný podstatný rozdíl ve struktuře, protože vrstvy i skupiny jsou pouze uzly v grafu scény. Pokud by byly potřeba rozdíly, třída generického uzlu by byla deklarována pomocí deklarace generického typu C++ a vrstvy a skupiny by se pak zdědily jako podtřídy. Viditelnost prvku by například byla vlastností vrstvy, ale ne nutně skupiny.
Graf scény je užitečný v moderních hrách, které využívají 3D grafiku a neustále rostoucí obrovské světy a úrovně. V takových aplikacích uzly grafu scény (obvykle) představují entity nebo objekty ve scéně.
Hra může například definovat logický vztah mezi rytířem a rytířem, takže rytíře lze považovat za rozšíření rytíře. Graf scény by měl uzel „kůň“ s přidruženým uzlem „rytíř“.
Kromě popisu logických vztahů může graf scény také popisovat prostorové vztahy různých entit: rytíř se pohybuje trojrozměrným prostorem společně s koněm. V takto velkých aplikacích jsou požadavky na paměť při návrhu grafu scény kritické. Z tohoto důvodu mnoho systémů s velkými grafy scén používá klonování pro úsporu paměti a zvýšení rychlosti. Ve výše uvedeném příkladu je každý rytíř samostatným uzlem scény, ale jeho grafické znázornění (sestávající z 3D sítě, textur, materiálů a shaderů) je klonováno. To znamená, že data jsou uložena pouze v jedné instanci, na kterou se pak odkazují všechny rytířské uzly grafu scény. To snižuje požadavky na paměť a zvyšuje rychlost, protože při vytváření nového rytířského uzlu není potřeba duplikovat informace o vzhledu.
Nejjednodušší forma grafu scény používá pole nebo datovou strukturu propojeného seznamu a zobrazení jeho forem je pouze sekvenční iterací uzlů jednoho po druhém. Další běžné operace, jako je určování, který tvar se protíná s kurzorem myši (například v aplikacích založených na grafickém uživatelském rozhraní), se také provádějí lineárním vyhledáváním. U malých grafů scén to obvykle stačí.
Větší grafy scén vedou ke znatelnému zpomalení lineárních operací, proto se používají složitější struktury pro ukládání základních dat, nejoblíbenější a nejčastější formou je strom. V těchto grafech scén je složený návrhový vzor často navržen tak, aby vytvořil hierarchickou reprezentaci skupinových uzlů a listových uzlů. Seskupené uzly mohou mít libovolný počet připojených podřízených uzlů. Seskupené uzly zahrnují transformační uzly a přepínací uzly. Listové uzly jsou uzly, které jsou skutečně vykresleny, nebo uzly, které zobrazují výsledek nějaké akce. Patří sem předměty, skřítci, zvuky, světla a cokoli, co lze v nějakém abstraktním smyslu považovat za „renderovatelné“.
Aplikace operací na graf scény vyžaduje určitý způsob předání operace na základě typu uzlu. Například v případě vykreslování by uzel skupinové transformace akumuloval transformační informace pomocí násobení matic, vektorových posunů, čtveřic nebo Eulerových úhlů. Poté listový uzel odešle objekt k vykreslení. V některých implementacích lze vykreslování provádět přímo pomocí použitého rozhraní API pro vykreslování, jako je DirectX nebo OpenGL. Ale protože API použité implementace obvykle vede k potížím při portování na jiné platformy, je možné oddělit graf scény a vykreslovací systém. K uskutečnění tohoto druhu přenosu lze použít několik přístupů.
V objektově orientovaných jazycích, jako je C++, to lze snadno provést pomocí virtuálních funkcí, z nichž každá představuje operaci, kterou lze aplikovat na uzel. Virtuální funkce se snadno píší, ale obvykle není možné přidávat nové operace bez přístupu ke zdrojovému kódu. Alternativně lze použít návrhový vzor Návštěvník. Tento přístup však není bez stejné nevýhody kvůli nemožnosti přidávat nové druhy uzlů.
Jiné metody používají RTTI (Run-Time Type Information). Operaci lze provést jako třídu, která je předána aktuálnímu uzlu; poté se dotazuje na informace o typu uzlu pomocí RTTI a vyhledá správnou operaci v řadě zpětných volání nebo funktorů. To vyžaduje asociativní pole zpětných volání nebo typů funktorů, které mají být inicializovány za běhu, ale poskytuje větší flexibilitu, rychlost a rozšiřitelnost. Existují variace těchto metod a nové metody mohou nabídnout další výhody. Jednou z takových možností je přestavět graf scény během každé ze spustitelných operací. Výsledkem je nižší rychlost a dobře optimalizovaný graf scény. To ukazuje, že dobrá implementace grafu scény je vysoce závislá na aplikaci, ve které je použit.
Typy přemostěníProcházení grafem scény je klíčovým bodem při dosahování výkonnosti aplikací operací na grafy scény. Procházení se obvykle skládá z libovolného počátečního uzlu (často kořenového uzlu grafu scény), aplikace operace nebo operací (často se operace aktualizace a renderu aplikují jedna po druhé) a rekurzivního pohybu po grafu scény (stromu) k podřízeným uzlům, dokud není dosaženo listového uzlu. Poté mnoho nástrojů pro správu grafů scén prochází stromem v opačném směru a aplikuje podobnou operaci. Uvažujme například operaci vykreslování, která přijímá informace: během rekurzivního sestupného procházení hierarchie grafů scény je vyvolána operace, která předchází vykreslení. Pokud je uzel transformačním uzlem, přidá do aktuální transformační matice své vlastní transformační informace. Poté, co operace dokončí procházení všemi podřízenými uzly, zavolá operaci následující po vykreslení, takže transformační uzel může transformaci vrátit zpět. Tento přístup drasticky snižuje počet požadovaných multiplikací matic.
Některé operace s grafy scény jsou ve skutečnosti efektivnější, když se uzly procházejí v jiném pořadí, například když některé systémy aplikují přebudování grafu scény, aby jej převedly do lépe analyzovatelného formátu nebo stromu.
Ve 2D případě se například graf scény obvykle vykresluje počínaje kořenovým uzlem a poté rekurzivně vykresluje všechny podřízené uzly. Listové uzly představují objekty nejblíže pozorovateli. Protože vykreslování probíhá od pozadí do popředí, přičemž bližší objekty se překrývají s těmi vzdálenějšími, je tento proces také známý jako „malířův algoritmus“. Ve 3D systémech, které často používají hloubkové vyrovnávací paměti, je efektivnější nejprve nakreslit nejbližší objekty, protože vzdálené objekty často stačí pouze oříznout místo vykreslení, protože jsou zakryty bližšími objekty.
Bounding Volume Hierarchies (BVH) jsou užitečné pro řadu úkolů, včetně efektivního ořezávání a rychlé detekce kolizí mezi objekty. Hierarchie ohraničujících objemů je prostorová struktura, ale nevyžaduje dělení geometrie (viz o dělení prostoru níže).
Hierarchie ohraničujících objemů je strom ohraničujících objemů (často koule, osově zarovnané ohraničující rámečky ( AABB ) nebo orientované ohraničující rámečky). Na samém konci této hierarchie je ohraničující objem minimální velikost nezbytnou k tomu, aby přesně obsahoval jeden objekt (možná dokonce nějakou malou část objektu v případě hierarchií ohraničujících objemů s vysokým rozlišením). V této hierarchii má každý uzel svůj vlastní objem, který je nezbytný pro přesné pokrytí všech obsažených objemů. Kořenový uzel obsahuje svazek obsahující všechny ostatní svazky ve stromu (celou scénu).
Hierarchie ohraničujících svazků jsou užitečné pro urychlení detekce kolizí mezi objekty. Pokud se ohraničující objem objektu neprotíná s objemem výše ve stromové hierarchii, nemůže se protínat s žádnými objekty pod tímto uzlem (takže jsou všechny velmi rychle vyřazeny).
Je zřejmé, že mezi hierarchiemi hraničních objemů a grafy scén existuje mnoho podobností. Graf scény lze snadno upravit tak, aby zahrnoval nebo se stal hierarchií ohraničujících objemů; pokud má každý uzel přidružený svazek nebo vestavěný „uzel svazku“ přidaný na vhodné místo v hierarchii. To se může lišit od typického grafu scény, ale zahrnutí hierarchie hraničních objemů do grafu scény má své výhody.
Efektivní způsob, jak zkombinovat prostorový oddíl a graf scény, je vytvořit uzel listové scény, který obsahuje data o prostorovém oddílu. Tato data jsou obvykle statická a obsahují data o nemovitých předmětech v úrovni v nějaké samostatné podobě. Některé systémy mohou obsahovat samostatné systémy a jejich vizualizaci. To je normální a žádná z těchto metod nemá žádné zvláštní výhody. Zejména je špatnou praxí ukládat graf scény v systému rozdělení prostoru, protože je lepší chápat graf scény jako systém nad rozdělením prostoru.
Stručně řečeno: rozdělení prostoru je navrženo tak, aby výrazně urychlilo zpracování a vykreslení grafu scény.
Potřeba vykreslovat mnoho objektů nebo grafů, které jsou generovány kompletně za běhu (jak se to stává v programech, které pro vykreslování používají sledování paprsků), vyžaduje definici skupin uzlů s další automatizací. Například ray tracer vezme popis 3D modelu ve scéně a sestaví jeho vnitřní reprezentaci rozdělením jednotlivých částí do ohraničujících rámečků. Jsou seskupeny hierarchicky, takže test průniku paprsků (jako součást procesu viditelnosti) lze vypočítat efektivně. Například skupinový rámeček, který se neprotíná s paprskem, může zcela vynechat kontrolu všech jeho součástí.
Podobné účinnosti je dosaženo u dvourozměrných aplikací. Pokud uživatel zvětšil dokument tak, že na obrazovce počítače je vidět pouze jeho část, a poté v této části posouvá, je užitečné použít ohraničovací rámeček (nebo v tomto případě ohraničovací rámeček) k rychlému určení, který prvky grafu scény jsou viditelné, a proto musí být vykresleny.
V závislosti na konkrétním výkonu vykreslování aplikace může být většina grafu scény navržena tak, aby jí vyhovovala. Ve 3D videohrách (jako je Quake) jsou stromy binárního dělení prostoru (BSP) vysoce preferovány, aby se minimalizoval počet testů viditelnosti. Stromy oddílů prostoru však vyžadují mnoho času na výpočet schématu grafu scény a musí být přepočítány, pokud se schéma grafu scény změní; proto mají úrovně tendenci zůstat statické a dynamické objekty se ve schématu rozdělení prostoru obvykle neberou v úvahu.
Grafy prostředí pro objekty s pravidelnými hustými vrcholy, jako jsou výškové mapy a polygonové sítě, obvykle používají kvadrantové stromy a osmistromy, což jsou specializované verze hierarchie 3D ohraničovacího rámečku. Protože samotná výšková mapa zabírá určitý ohraničující objem, rekurzivně ji rozdělujeme na osm částí, dokud nedosáhneme jednotlivých prvků výškové mapy. Kvadrantový strom je dvourozměrná verze oktree.
PHIGS byla první komerční specifikace pro graf scény a stala se standardem ANSI v roce 1988. Dodavatelé unixového hardwaru dodávali zcela odlišné implementace. HOOPS 3D Graphics System byla první komerční knihovna scénových grafů od jediného dodavatele softwaru. Bylo zamýšleno běžet na zcela odlišných 2D a 3D rozhraních, přičemž první vydání určené k distribuci s hlavním číslem 3.0 bylo dokončeno v roce 1991. Velmi brzy společnost Silicon Graphics vydala systém IRIS Inventor 1.0 (1992), což byl graf scény postavený na IRIS GL 3D API. Po něm v roce 1994 následoval Open Inventor, multiplatformní graf scén postavený na OpenGL.
X3D je bezplatný formát souborů s otevřenými standardy a běhová architektura pro reprezentaci a komunikaci 3D scén a objektů pomocí XML. Je přijat jako norma ISO poskytující systém pro ukládání, načítání a vykreslování grafického obsahu v reálném čase vloženého do aplikací; vše v rámci otevřené architektury pro podporu široké škály aplikací a uživatelských scénářů.