A jelenetgrafikon egy olyan adatstruktúra, amelyet elsősorban vektorgrafikus szerkesztőkben és számítógépes játékokban használnak . Ilyen programok például az Acrobat 3D, az Adobe Illustrator , az AutoCAD , a CorelDRAW , az OpenSceneGraph , a VRML97 és az X3D .
A jelenetgráf egy olyan struktúrát képvisel, amely egy grafikus jelenet logikus és gyakran (de nem feltétlenül) térbeli megjelenítését tartalmazza. A jelenetgráf definíciója homályos, mert a programozók, akik ezt alkalmazásokban - és különösen a játékfejlesztő iparban - implementálják, átveszik az alapelveket, és adaptálják azokat konkrét alkalmazásokhoz. Ez azt jelenti, hogy nincs egyetértés abban, hogy milyen legyen a jelenet grafikonja.
A jelenetgráf egy struktúra, például gráf vagy fa csomópontjainak halmaza . Egy facsomópontnak (a jelenetgráf határfastruktúrájában) sok gyermeke lehet, de gyakran csak egy szülője, és a szülő tevékenysége kiterjed az összes gyermekcsomópontra; egy csoporton végrehajtott cselekvés hatása automatikusan eloszlik minden elemére. Sok programban egy transzformációs mátrix (lásd még: transzformációk és mátrixok) bármely csoport szintjén történő társítása és az ilyen mátrixok szorzása hatékony és természetes módja az ilyen műveletek kezelésének. Gyakori jellemző például, hogy a kapcsolódó alakzatokat/objektumokat egy összetett objektummá lehet csoportosítani, amely ugyanolyan könnyen mozgatható, átalakítható, kiválasztható stb., mint egyetlen objektum.
Néha az is előfordul, hogy egyes jelenetgráfokon egy csomópont bármely másik csomóponthoz kapcsolható, beleértve önmagát is, vagy legalábbis tartalmaz egy másik csomópontra utaló kiterjesztést (például a Pixar PhotoRealistic RenderMan a Reyes renderelő algoritmusának és az Acrobat 3D-nek köszönhetően Adobe Systems a továbbfejlesztett interaktív manipulációknak köszönhetően).
A vektorgrafikus szerkesztőkben minden jelenetgráf levél csomópontja valamilyen oszthatatlan dokumentum egységet képvisel, általában egy alakzatot, például egy ellipszist vagy egy Bézier-görbét. Bár maguk az alakzatok (különösen az útvonalak) tovább bonthatók olyan elemekre, mint például a spline csomópontok, a gyakorlatban kényelmesebb úgy elképzelni a jelenetgráfot, mint amely alakzatokból áll, anélkül, hogy alacsonyabb reprezentációs szintre süllyedne.
Egy másik hasznos és felhasználó által definiált csomópontfogalom a réteg. Átlátszó lapként működik, amelyen tetszőleges számú alakzat és csoportjuk elhelyezhető. A dokumentum ezután rétegek halmazává válik, amelyek mindegyike láthatatlanná, áttetszővé vagy zárolhatóvá tehető (csak olvasható) szükség szerint. Egyes alkalmazások az összes fóliát egy lineáris listába rendezik, míg mások támogatják az alszinteket (vagyis a rétegeket bármely kívánt beágyazási szint rétegein belül).
Előfordulhat, hogy a rétegek és csoportok között egyáltalán nincs eredendő szerkezeti különbség, mivel a rétegek és a csoportok is csak csomópontok a jelenetgráfban. Ha különbségekre lenne szükség, akkor a C++ általános típusdeklarációval egy általános csomópont-osztályt deklarálnak, majd a rétegeket és csoportokat alosztályokként öröklik. Egy elem láthatósága például a réteg tulajdonsága lenne, de nem feltétlenül a csoporté.
A jelenetdiagram hasznos a modern játékokban, amelyek 3D grafikát és folyamatosan növekvő hatalmas világokat és szinteket használnak. Az ilyen alkalmazásokban a jelenet gráf csomópontjai (általában) entitásokat vagy objektumokat képviselnek a jelenetben.
Például egy játék meghatározhat egy logikai kapcsolatot egy lovag és egy lovag között, így a lovagot a lovag kiterjesztéseként kezelheti. A jelenet gráf egy "ló" csomópontot tartalmazna egy hozzá tartozó "lovag" csomóponttal.
A jelenetgrafikon a logikai kapcsolatok leírásán túl különböző entitások térbeli viszonyait is leírhatja: a lovag a lóval együtt mozog a háromdimenziós térben. Az ilyen nagy alkalmazásokban a memóriaigény kritikus fontosságú a jelenetgrafikon tervezése során. Emiatt sok nagy jelenetgrafikonnal rendelkező rendszer klónozást használ a memória megtakarítására és a sebesség növelésére. A fenti példában minden lovag külön jelenetcsomópont, de a grafikus ábrázolása (amely 3D-s hálóból, textúrákból, anyagokból és shaderekből áll) klónozott. Ez azt jelenti, hogy az adatok csak egyetlen példányban tárolódnak, amelyre azután a jelenetgráf összes lovagi csomópontja hivatkozik. Ez csökkenti a memóriaigényt és növeli a sebességet, mivel egy új lovag csomópont létrehozásakor nincs szükség a megjelenési információk megkettőzésére.
A jelenetgráf legegyszerűbb formája egy tömböt vagy egy linkelt lista adatstruktúrát használ, és formáinak megjelenítése csak a csomópontok egyenkénti szekvenciális iterációja. Egyéb gyakori műveletek, mint például annak meghatározása, hogy melyik alakzat metszi az egérkurzort (például grafikus felhasználói felület alapú alkalmazásokban), szintén lineáris kereséssel hajtható végre. Kis jelenetgrafikonokhoz ez általában elegendő.
A nagyobb jelenetgrafikonok a lineáris műveletek észrevehető lassulásához vezetnek, ezért az alapadatok tárolására összetettebb struktúrákat használnak, a legnépszerűbb és legelterjedtebb forma a fa. Ezekben a jelenetgrafikonokban az összetett tervezési mintát gyakran úgy tervezték, hogy a csoportcsomópontok és a levélcsomópontok hierarchikus ábrázolását hozza létre. A csoportosított csomópontokhoz tetszőleges számú gyermekcsomópont tartozhat. A csoportosított csomópontok közé tartoznak a transzformációs csomópontok és a kapcsoló csomópontok. A levélcsomópontok olyan csomópontok, amelyek ténylegesen megjelennek, vagy olyan csomópontok, amelyek valamilyen művelet eredményét mutatják. Ide tartoznak a tárgyak, sprite-ok, hangok, fények és bármi, ami valamilyen elvont értelemben "renderelhetőnek" tekinthető.
A műveletek jelenetgráfra történő alkalmazása megköveteli a művelet továbbításának valamilyen módját a csomópont típusa alapján. Például renderelés esetén egy csoporttranszformációs csomópont mátrixszorzások, vektoreltolások, kvaterniók vagy Euler-szögek felhasználásával gyűjti össze a transzformációs információkat. Ezt követően a levél csomópont elküldi az objektumot renderelésre. Egyes megvalósításokban a renderelés közvetlenül elvégezhető a használt renderelési API használatával, például a DirectX vagy az OpenGL használatával. De mivel a használt megvalósítás API-ja általában nehézségeket okoz a más platformokra történő portolás során, lehetséges a jelenetgráf és a renderelő rendszer elkülönítése. Az ilyen típusú átvitel megvalósításához többféle megközelítést is alkalmazhatunk.
Az objektum-orientált nyelvekben, például a C++-ban, ez könnyen megtehető virtuális függvényekkel, amelyek mindegyike olyan műveletet jelent, amely egy csomópontra alkalmazható. A virtuális függvényeket könnyű írni, de általában nem lehet új műveleteket hozzáadni a forráskódhoz való hozzáférés nélkül. Alternatív megoldásként a Visitor tervezési minta is használható. Ez a megközelítés azonban nem nélkülözi ugyanazt a hátrányt, mivel nem tud új típusú csomópontokat hozzáadni.
Más módszerek az RTTI-t (Run-Time Type Information) használják. A művelet végrehajtható osztályként, amelyet az aktuális csomópontnak adunk át; ezután lekérdezi a csomópont típusinformációit az RTTI segítségével, és megkeresi a helyes műveletet a visszahívások vagy függvények tömbjében. Ehhez a visszahívási vagy függvénytípusok asszociatív tömbjét kell inicializálni futás közben, de nagyobb rugalmasságot, sebességet és bővíthetőséget biztosít. Ezeknek a módszereknek változatai léteznek, és az új módszerek további előnyöket kínálhatnak. Az egyik ilyen lehetőség a jelenetgráf újraépítése az egyes végrehajtható műveletek során. Ez lassabb sebességet és jól optimalizált jelenetgrafikont eredményez. Ez azt mutatja, hogy egy jelenetgráf jó megvalósítása nagymértékben függ attól az alkalmazástól, amelyben használják.
Bypass típusokA jelenetgrafikonok bejárása kulcsfontosságú pont a jelenetgrafikonokra vonatkozó műveletek végrehajtásának teljesítményében. A bejárás általában egy tetszőleges kezdő csomópontból (gyakran a jelenetgráf gyökércsomópontjából) áll, egy művelet vagy műveletek alkalmazásából (gyakran egymás után alkalmazzák a frissítési és renderelési műveleteket), és rekurzívan lefelé mozog a jelenet gráfján (fán). gyermek csomópontokhoz, amíg el nem ér egy levél csomópontot. Ezt követően sok jelenetgráf-kezelő eszköz az ellenkező irányba halad át a fán, hasonló műveletet alkalmazva. Vegyünk például egy információt fogadó renderelési műveletet: a jelenetgráf hierarchiájának rekurzív lefelé történő bejárása során a renderelést megelőző művelet kerül meghívásra. Ha a csomópont egy transzformációs csomópont, akkor hozzáadja a saját transzformációs információit az aktuális transzformációs mátrixhoz. Miután a művelet befejezte az összes gyermekcsomópont bejárását, meghívja a renderelést követő műveletet, így a transzformációs csomópont visszavonhatja az átalakítást. Ez a megközelítés drasztikusan csökkenti a szükséges mátrixszorzások számát.
Egyes jelenetgráf-műveletek valójában hatékonyabbak, ha a csomópontokat eltérő sorrendben haladják meg, például amikor egyes rendszerek jelenetgráf-újraépítést alkalmaznak, hogy azt egy jobban értelmezhető formátumba vagy fába alakítsák át.
A 2D-s esetben például a jelenetgráf jellemzően a gyökércsomóponttól kezdve, majd rekurzívan rendereli az összes gyermek csomópontot. A levél csomópontjai a megfigyelőhöz legközelebb eső objektumokat jelentik. Mivel a renderelés a háttérből az előtérbe történik, és a közelebbi objektumok átfedik a távolabbiakat, ezt a folyamatot "festő algoritmusnak" is nevezik. A gyakran mélységi puffereket használó 3D-s rendszerekben hatékonyabb, ha először a legközelebbi objektumokat rajzolják meg, mivel a távoli objektumokat gyakran csak le kell vágni a renderelés helyett, mert közelebbi objektumok takarják őket.
A Bounding Volume Hierarchiák (BVH-k) számos feladathoz hasznosak, beleértve a hatékony kivágást és az objektumok közötti ütközések gyors észlelését. A határoló kötetek hierarchiája egy térbeli struktúra, de nem igényel geometriai particionálást (lásd alább a térfelosztásról).
A határoló térfogat-hierarchia határoló térfogatok fája (gyakran gömbök, tengelyhez igazított határolókeretek ( AABB ) vagy orientált határolókeretek). Ennek a hierarchiának a legalján a határoló térfogat az a minimális méret, amely egyetlen objektum pontos befogadásához szükséges (nagy felbontású határoló kötethierarchiák esetén akár az objektum egy kis része is). A hierarchiában feljebb haladva minden csomópontnak megvan a maga térfogata, amely szükséges az összes benne lévő kötet pontos lefedéséhez. A gyökércsomópont tartalmazza a fa összes többi kötetét (a teljes jelenetet) tartalmazó kötetet.
A határoló kötet-hierarchiák hasznosak az objektumok közötti ütközések észlelésének felgyorsítására. Ha egy objektum határoló térfogata nem metszi a fahierarchiában magasabban lévő térfogatot, akkor nem metszheti a csomópont alatti objektumokat (így nagyon gyorsan eldobják őket).
Nyilvánvalóan sok hasonlóság van a határoló kötethierarchiák és a jelenetgrafikonok között. A jelenet grafikonja könnyen adaptálható úgy, hogy magában foglalja a határoló térfogatok hierarchiáját, vagy azzá váljon; ha minden csomóponthoz tartozik egy kötet vagy egy beépített "kötetcsomópont" a hierarchia megfelelő helyére. Ez eltérhet egy tipikus jelenetdiagramtól, de előnyökkel jár, ha a határoló térfogatok hierarchiáját belefoglalja a jelenetdiagramba.
A térpartíció és a jelenetgráf kombinálásának hatékony módja egy levéljelenet csomópont létrehozása, amely adatokat tartalmaz a térpartícióról. Ezek az adatok általában statikusak, és valamilyen külön formában tartalmaznak adatokat a szinten lévő nem mozgatható objektumokról. Egyes rendszerek külön rendszereket és azok megjelenítését tartalmazhatják. Ez normális, és egyik módszernek sincs különösebb előnye. Különösen rossz gyakorlat a jelenetgráf térfelosztási rendszerben való tárolása, mivel jobb a jelenetgráfot a térfelosztás feletti rendszerként értelmezni.
Röviden: a térfelosztást úgy tervezték, hogy jelentősen felgyorsítsa a jelenet grafikonjának feldolgozását és megjelenítését.
Számos objektum vagy grafikon renderelésének szükségessége, amelyek futás közben teljesen generálódnak (ahogyan a sugárkövetést használó programokban történik), további automatizálással kell meghatározni a csomópontok csoportjait. A sugárkövető például leírja egy jelenetben lévő 3D-s modellt, és összeállítja a belső reprezentációját úgy, hogy az egyes részeket határoló dobozokra osztja. Ezek hierarchikusan vannak csoportosítva, hogy a sugármetszésvizsgálat (a láthatósági folyamat részeként) hatékonyan kiszámítható legyen. Egy sugárral nem metsző csoportdoboz például teljesen kihagyhatja az összes összetevő ellenőrzését.
Hasonló hatékonyság érhető el a kétdimenziós alkalmazásokban. Ha a felhasználó úgy nagyította ki a dokumentumot, hogy annak csak egy része látható a számítógép képernyőjén, majd görget a részen belül, akkor hasznos egy határolókeret (vagy ebben az esetben egy határolókeret) segítségével gyorsan meghatározni, hogy melyik a jelenetgrafikon elemei láthatók, ezért meg kell jeleníteni.
Egy alkalmazás konkrét renderelési teljesítményétől függően a jelenetgrafikonok többsége úgy alakítható ki, hogy megfeleljen neki. A 3D-s videojátékokban (például a Quake-ben) a bináris térfelosztás (BSP) fákat előnyben részesítik a láthatósági tesztek számának minimalizálása érdekében. A térpartíciós fák azonban sok időt igényelnek a jelenetgráf-séma kiszámításához, és újra kell számítani őket, ha a jelenetgráf séma megváltozik; ezért a szintek általában statikusak maradnak, és a dinamikus objektumokat általában nem veszik figyelembe a térfelosztási sémában.
A szabályos sűrű csúcsú objektumok jelenetgrafikonjai, például a magasságtérképek és a sokszöghálók általában négyfákat és oktrákat használnak, amelyek a 3D-s határolókeret-hierarchia speciális változatai. Mivel maga a magasságtérkép bizonyos határfelületet foglal el, rekurzívan nyolc részre osztja, amíg el nem éri a magasságtérkép egyes elemeit. A négyfa egy oktfa kétdimenziós változata.
A PHIGS volt az első kereskedelmi specifikáció a jelenetgráfokhoz, és 1988-ban vált ANSI-szabványsá. A Unix hardvergyártók egészen eltérő implementációkat szállítottak. A HOOPS 3D Graphics System volt az első kereskedelmi jelenetgrafikon-könyvtár egyetlen szoftvergyártótól. Teljesen eltérő 2D és 3D interfészeken való futtatásra szánták, az első terjesztésre szánt kiadás 3.0-s főszámmal 1991-ben készült el. A Silicon Graphics hamarosan kiadta az IRIS Inventor 1.0 rendszert (1992), amely jelenetgrafikon volt. az IRIS GL 3D API-ra épül. 1994-ben követte az Open Inventor, egy többplatformos jelenetgrafikon, amely az OpenGL tetejére épült.
Az X3D egy jogdíjmentes, nyílt szabványú fájlformátum és futásidejű architektúra 3D jelenetek és objektumok XML használatával történő megjelenítésére és kommunikálására. ISO-szabványként fogadták el, amely rendszert biztosít az alkalmazásokba ágyazott valós idejű grafikus tartalom tárolására, visszakeresésére és megjelenítésére; mindezt egy nyitott architektúrán belül, hogy az alkalmazások és felhasználói forgatókönyvek széles skáláját támogassa.