Kohtauskaavio on tietorakenne, jota käytetään ensisijaisesti vektorigrafiikkaeditoreissa ja tietokonepeleissä . Esimerkkejä tällaisista ohjelmista ovat Acrobat 3D, Adobe Illustrator , AutoCAD , CorelDRAW , OpenSceneGraph , VRML97 ja X3D .
Kohtauskaavio edustaa rakennetta, joka sisältää loogisen ja usein (mutta ei välttämättä) tilaesityksen graafisesta kohtauksesta. Kohtausgraafin määritelmä on sumea, koska sitä sovelluksissa - ja erityisesti pelikehitysteollisuudessa - toteuttavat ohjelmoijat ottavat perusperiaatteet ja mukauttavat ne tiettyihin sovelluksiin. Tämä tarkoittaa, että ei ole yksimielisyyttä siitä, mikä kohtauskaavion tulisi olla.
Kohtauskaavio on joukko solmuja rakenteessa, kuten kaaviossa tai puussa . Puusolmulla (kohtauskaavion rajapuurakenteessa) voi olla useita lapsia, mutta usein vain yksi vanhempi, ja vanhemman toiminto ulottuu kaikkiin sen alisolmuihin; ryhmälle suoritetun toiminnon vaikutus jakautuu automaattisesti kaikkiin sen elementteihin. Monissa ohjelmissa muunnosmatriisin (katso myös muunnokset ja matriisit) liittäminen minkä tahansa ryhmän tasolla ja tällaisten matriisien kertominen on tehokas ja luonnollinen tapa käsitellä tällaisia operaatioita. Yhteinen piirre on esimerkiksi kyky ryhmitellä toisiinsa liittyviä muotoja/objekteja yhdistelmäobjektiksi, jota voidaan siirtää, muuntaa, valita jne. yhtä helposti kuin yksittäinen objekti.
Joskus käy myös niin, että joissain kohtauskaavioissa solmu voidaan linkittää mihin tahansa toiseen solmuun, mukaan lukien itseensä, tai ainakin sisältää laajennuksen, joka viittaa toiseen solmuun (esim. Pixarin PhotoRealistic RenderMan Reyes-renderöintialgoritmin ja Acrobat 3D:n ansiosta. Adobe Systems parannettujen interaktiivisten käsittelyjen ansiosta).
Vektorigrafiikkaeditoreissa jokainen kohtauskaavion lehtisolmu edustaa jotakin jakamatonta asiakirjayksikköä, yleensä muotoa, kuten ellipsi tai Bézier-polku. Vaikka itse muodot (erityisesti polut) voidaan jakaa edelleen elementeiksi, kuten spline-solmuiksi, käytännössä on kätevämpää ajatella kohtausgraafia koostuvan muodoista laskematta alemmalle esitystasolle.
Toinen hyödyllinen ja käyttäjän määrittämä solmukonsepti on kerros. Se toimii läpinäkyvänä levynä, jolle voidaan sijoittaa mikä tahansa määrä muotoja ja niiden ryhmiä. Asiakirjasta tulee sitten joukko tasoja, joista jokainen voidaan tehdä näkymätön, läpikuultava tai lukita (vain luku) tarpeen mukaan. Jotkut sovellukset järjestävät kaikki tasot lineaariseen luetteloon, kun taas toiset tukevat alitasoja (eli kerroksia minkä tahansa halutun sisäkkäisen tason kerrosten sisällä).
Tasojen ja ryhmien rakenteessa ei välttämättä ole luontaista eroa, koska sekä kerrokset että ryhmät ovat vain solmuja kohtauskaaviossa. Jos eroja tarvittaisiin, yleinen solmuluokka ilmoitettaisiin C++ yleisellä tyyppimäärityksellä ja sitten tasot ja ryhmät periytyvät alaluokkiksi. Esimerkiksi elementin näkyvyys olisi kerroksen ominaisuus, mutta ei välttämättä ryhmän ominaisuus.
Kohtauskaavio on hyödyllinen nykyaikaisissa peleissä, joissa käytetään 3D-grafiikkaa ja jatkuvasti kasvavia valtavia maailmoja ja tasoja. Tällaisissa sovelluksissa kohtauskaavion solmut (yleensä) edustavat kokonaisuuksia tai objekteja kohtauksessa.
Peli voi esimerkiksi määritellä loogisen suhteen ritarin ja ritarin välillä, jolloin ritari voidaan pitää ritarin jatkeena. Kohtauskaaviossa olisi "hevos"-solmu ja siihen liittyvä "ritari"-solmu.
Loogisten suhteiden kuvauksen lisäksi kohtauskaavio voi kuvata myös eri entiteettien tilasuhteita: ritari liikkuu kolmiulotteisessa avaruudessa yhdessä hevosen kanssa. Tällaisissa suurissa sovelluksissa muistivaatimukset ovat kriittisiä kohtauskaavion suunnittelussa. Tästä syystä monet järjestelmät, joissa on suuria kohtauskaavioita, käyttävät kloonausta muistin säästämiseksi ja nopeuden lisäämiseksi. Yllä olevassa esimerkissä kukin ritari on erillinen kohtaussolmu, mutta sen graafinen esitys (joka koostuu 3D-verkosta, tekstuureista, materiaaleista ja varjostimista) on kloonattu. Tämä tarkoittaa, että tiedot tallennetaan vain yhteen esiintymään, johon sitten kaikki kohtauskaavion ritarisolmut viittaavat. Tämä vähentää muistivaatimuksia ja lisää nopeutta, koska uutta ritarisolmua luotaessa ulkoasutietoja ei tarvitse kopioida.
Kohtausgraafin yksinkertaisin muoto käyttää taulukkoa tai linkitettyä listatietorakennetta, ja sen muotojen näyttö on vain solmujen peräkkäinen iteraatio yksitellen. Lineaarisella haulla suoritetaan myös muita yleisiä toimintoja, kuten sen määrittäminen, mikä muoto leikkaa hiiren kohdistimen (esimerkiksi GUI-pohjaisissa sovelluksissa). Pienille kohtauskaavioille tämä yleensä riittää.
Suuremmat kohtauskaaviot johtavat lineaaristen operaatioiden huomattavaan hidastumiseen, joten perustietojen tallentamiseen käytetään monimutkaisempia rakenteita, suosituin ja yleisin muoto on puu. Näissä kohtauskaavioissa yhdistelmäsuunnittelukuvio on usein suunniteltu luomaan hierarkkinen esitys ryhmäsolmuista ja lehtisolmuista. Ryhmitellyillä solmuilla voi olla mikä tahansa määrä liitettyjä alisolmuja. Ryhmitettyihin solmuihin kuuluvat muunnossolmut ja kytkentäsolmut. Lehtisolmut ovat solmuja, jotka todellisuudessa renderöidään, tai solmuja, jotka näyttävät jonkin toiminnon tuloksen. Näitä ovat esineet, spritet, äänet, valot ja kaikki, mitä voidaan pitää "renderoitavina" jossain abstraktissa mielessä.
Toimintojen soveltaminen kohtauskaavioon vaatii jonkin tavan välittää toiminto solmutyypin perusteella. Esimerkiksi renderöinnin tapauksessa ryhmämuunnossolmu kerää muunnosinformaatiota käyttämällä matriisikertoja, vektorien siirtymiä, kvaternioneja tai Euler-kulmia. Tämän jälkeen lehtisolmu lähettää objektin renderöitäväksi. Joissakin toteutuksissa renderöinti voidaan tehdä suoraan käyttämällä renderöintisovellusliittymää, kuten DirectX tai OpenGL. Mutta koska käytetyn toteutuksen API aiheuttaa yleensä vaikeuksia siirrossa muille alustoille, on mahdollista erottaa kohtauskaavio ja renderöintijärjestelmä. Tällaisen siirron toteuttamiseksi voidaan käyttää useita lähestymistapoja.
Oliopohjaisissa kielissä, kuten C++, tämä on helppo tehdä virtuaalisilla funktioilla, joista jokainen edustaa toimintoa, jota voidaan soveltaa solmuun. Virtuaalifunktioita on helppo kirjoittaa, mutta uusia toimintoja ei yleensä voi lisätä ilman pääsyä lähdekoodiin. Vaihtoehtoisesti voidaan käyttää Visitor-suunnittelumallia. Mutta tämä lähestymistapa ei ole ilman samaa haittaa, koska ei voida lisätä uudenlaisia solmuja.
Muut menetelmät käyttävät RTTI:tä (Run-Time Type Information). Toiminto voidaan suorittaa luokkana, joka välitetään nykyiselle solmulle; sitten se kysyy solmun tyyppitiedot RTTI:n avulla ja etsii oikean toiminnan takaisinkutsujen tai funktioiden joukosta. Tämä vaatii assosiatiivisen joukon takaisinsoitto- tai funktiotyyppejä, jotka alustetaan suorituksen aikana, mutta tarjoaa enemmän joustavuutta, nopeutta ja laajennettavuutta. Näistä menetelmistä on olemassa muunnelmia, ja uudet menetelmät voivat tarjota lisäetuja. Yksi tällainen vaihtoehto on rakentaa kohtauskaavio uudelleen jokaisen suoritettavan toiminnon aikana. Tämä johtaa hitaampaan nopeuteen ja hyvin optimoituun kohtauskaavioon. Tämä osoittaa, että kohtauskaavion hyvä toteutus riippuu suuresti sovelluksesta, jossa sitä käytetään.
OhitustyypitKohtauskuvaajan läpikulku on avainkohta, kun saavutetaan toimintojen soveltaminen kohtauskaavioihin. Läpikulku koostuu yleensä mielivaltaisesta aloitussolmusta (usein kohtauskaavion juurisolmusta), toiminnon tai toimintojen soveltamisesta (usein päivitys- ja renderöintitoiminnot suoritetaan peräkkäin) ja rekursiivisesti alaspäin siirtyminen kohtauskaaviossa (puussa) lapsisolmuihin, kunnes saavutetaan lehtisolmu. Sen jälkeen monet kohtauskaavioiden hallintatyökalut kulkevat puun läpi vastakkaiseen suuntaan käyttämällä samanlaista toimintoa. Harkitse esimerkiksi renderöintioperaatiota, joka vastaanottaa tietoja: näkymäkaaviohierarkian rekursiivisen alaspäin kulkemisen aikana hahmonnusta edeltävä operaatio kutsutaan. Jos solmu on muunnossolmu, se lisää omat muunnostietonsa nykyiseen muunnosmatriisiin. Kun toiminto on ohittanut kaikki alisolmut, se kutsuu renderöintiä seuraavan toiminnon, jotta muunnossolmu voi kumota muunnoksen. Tämä lähestymistapa vähentää dramaattisesti vaadittujen matriisikertoloiden määrää.
Jotkin kohtauskuvaajan toiminnot ovat itse asiassa tehokkaampia, kun solmut kulkevat eri järjestyksessä, esimerkiksi kun jotkin järjestelmät käyttävät kohtauskuvaajan uudelleenrakennusta muuntaakseen sen jäsentävämpään muotoon tai puuhun.
Esimerkiksi 2D-tapauksessa kohtauskaavio renderöi tyypillisesti alkaen juurisolmusta ja renderöi sitten rekursiivisesti kaikki lapsisolmut. Lehtisolmut edustavat tarkkailijaa lähinnä olevia kohteita. Koska renderöinti tapahtuu taustalta etualalle ja lähemmät kohteet menevät päällekkäin kauempana, tämä prosessi tunnetaan myös "maalarialgoritmina". Usein syvyyspuskureita käyttävissä 3D-järjestelmissä on tehokkaampaa piirtää ensin lähimmät kohteet, koska usein kaukana olevat kohteet tarvitsee vain leikata renderöinnin sijaan, koska ne peittyvät lähempänä olevien kohteiden peitossa.
Rajaavat tilavuushierarkiat (BVH:t) ovat hyödyllisiä useissa tehtävissä, kuten tehokkaassa leikkaamisessa ja objektien välisten törmäysten nopeassa havaitsemisessa. Rajattavien volyymien hierarkia on spatiaalinen rakenne, mutta se ei vaadi geometrista osiointia (katso tilan osiointi alla).
Rajaava tilavuushierarkia on puu rajaavista tilavuuksista (usein pallot, akselin suuntaiset rajauslaatikot ( AABB ) tai suunnatut rajauslaatikot). Tämän hierarkian alaosassa rajaava tilavuus on vähimmäiskoko, joka tarvitaan tarkalleen yhden objektin sisältämiseen (ehkä jopa jonkin pienen osan objektista korkearesoluutioisten rajoitustilavuushierarkioiden tapauksessa). Tätä hierarkiaa ylöspäin noustessa jokaisella solmulla on oma tilavuutensa, mikä on tarpeen kaikkien sisältyvien tilavuuksien kattamiseksi tarkasti. Juurisolmu sisältää taltion, joka sisältää kaikki muut puun volyymit (koko kohtaus).
Rajaavat tilavuushierarkiat ovat hyödyllisiä nopeuttamaan kohteiden välisten törmäysten havaitsemista. Jos objektin rajaava tilavuus ei leikkaa puuhierarkiassa ylempänä olevan tilavuuden kanssa, se ei voi leikata minkään kyseisen solmun alapuolella olevien objektien kanssa (joten ne kaikki hylätään hyvin nopeasti).
On selvää, että rajaavien tilavuushierarkioiden ja kohtauskaavioiden välillä on monia yhtäläisyyksiä. Kohtauskaaviota voidaan helposti mukauttaa sisältämään rajallisten tilavuuksien hierarkia tai siitä tulee hierarkia; jos jokaiseen solmuun on liitetty tilavuus tai sisäänrakennettu "volyymisolmu" lisätty sopivaan paikkaan hierarkiassa. Tämä voi erota tyypillisestä kohtauskaaviosta, mutta rajallisten tilavuuksien hierarkian sisällyttämisestä kohtauskaavioon on etuja.
Tehokas tapa yhdistää avaruusosio ja kohtauskaavio on luoda lehtikohtaussolmu, joka sisältää tiedot avaruusosiosta. Nämä tiedot ovat yleensä staattisia ja sisältävät tietoja ei-liikkuvista kohteista tasolla jossain erillisessä muodossa. Jotkut järjestelmät voivat sisältää erilliset järjestelmät ja niiden visualisoinnin. Tämä on normaalia, eikä kummallakaan menetelmällä ole erityisiä etuja. Erityisesti on huono käytäntö tallentaa kohtauskaavio tilan osiointijärjestelmään, koska kohtauskaavio on parempi ymmärtää tilan osioinnin yläpuolella olevana järjestelmänä.
Lyhyesti sanottuna: tilan osiointi on suunniteltu nopeuttamaan merkittävästi kohtauskaavion käsittelyä ja renderöimistä.
Tarve hahmontaa monia objekteja tai kaavioita, jotka luodaan kokonaan ajon aikana (kuten tapahtuu ohjelmissa, jotka käyttävät hahmonnukseen säteenseurantaa), edellyttää solmuryhmien määrittelyä lisäautomaation avulla. Säteen jäljitin esimerkiksi ottaa kuvauksen 3D-mallista kohtauksessa ja kokoaa sen sisäisen esityksen jakamalla yksittäiset osat rajauslaatikoihin. Ne on ryhmitelty hierarkkisesti, jotta säteiden leikkaustesti (osana näkyvyysprosessia) voidaan laskea tehokkaasti. Esimerkiksi ryhmälaatikko, joka ei leikkaa säteen kanssa, voi ohittaa kaikkien komponenttiensa tarkistamisen.
Samanlainen tehokkuus saavutetaan kaksiulotteisissa sovelluksissa. Jos käyttäjä on suurentanut asiakirjaa niin, että vain osa siitä näkyy tietokoneen näytöllä, ja vierittää sitten sitä osaa, on hyödyllistä käyttää rajoitusruutua (tai tässä tapauksessa rajoitusruutua) määrittääkseen nopeasti, mikä kohtauskaavion elementit ovat näkyvissä, ja siksi ne on renderöitävä.
Sovelluksen erityisestä renderöintisuorituskyvystä riippuen suurin osa kohtauskaaviosta voidaan suunnitella sopivaksi. 3D-videopeleissä (kuten Quake) binääritilan osiointipuut (BSP) ovat erittäin edullisia näkyvyystestien määrän minimoimiseksi. Tilaosiopuut vaativat kuitenkin paljon aikaa näkymäkaavion skeeman laskemiseen, ja ne on laskettava uudelleen, jos kohtauskaaviokaavio muuttuu; siksi tasoilla on taipumus pysyä staattisina, eikä dynaamisia objekteja yleensä oteta huomioon tilan osiointijärjestelmässä.
Säännöllisten tiheiden kärkipisteiden kohteiden, kuten korkeuskarttojen ja monikulmioverkkojen, kohtauskaavioissa käytetään tyypillisesti nelipuita ja oktreja, jotka ovat erikoisversioita 3D-rajauslaatikoiden hierarkiasta. Koska itse korkeuskartalla on rajallinen tilavuus, se jaetaan rekursiivisesti kahdeksaan osaan, kunnes korkeuskartan yksittäiset elementit saavutetaan. Nelipuu on kaksiulotteinen versio oktresta.
PHIGS oli ensimmäinen kaupallinen kuvaus kohtauskaaviosta, ja siitä tuli ANSI-standardi vuonna 1988. Unix-laitteistotoimittajat toimittivat melko erilaisia toteutuksia. HOOPS 3D Graphics System oli ensimmäinen kaupallinen kohtauskaaviokirjasto yhdeltä ohjelmistotoimittajalta. Sen oli tarkoitus toimia täysin erilaisilla 2D- ja 3D-liitännöillä, ja ensimmäinen jakeluun tarkoitettu julkaisu päänumerolla 3.0 valmistui vuonna 1991. Hyvin pian Silicon Graphics julkaisi IRIS Inventor 1.0 -järjestelmän (1992), joka oli kohtauskaavio. rakennettu IRIS GL 3D API:n päälle. Sitä seurasi vuonna 1994 Open Inventor, monialustainen kohtauskaavio, joka on rakennettu OpenGL:n päälle.
X3D on maksuton avoimen standardin tiedostomuoto ja ajonaikainen arkkitehtuuri 3D-kohtausten ja -objektien esittämiseen ja viestimiseen XML:n avulla. Se on hyväksytty ISO-standardiksi, joka tarjoaa järjestelmän sovelluksiin upotetun reaaliaikaisen graafisen sisällön tallentamiseen, hakemiseen ja renderöimiseen. kaikki avoimessa arkkitehtuurissa tukemaan monenlaisia sovelluksia ja käyttäjien skenaarioita.