dev.gamez.lv

[dev]

Gribeeju aprunaaties par taadu lietu kaa optimizeeta render queue, kas ir dabiiga katras 3d engiines sastaavdalja..

Esmu izveidojis diezgan effektiivu un universaalu sisteemu, bet uztraucos par optimizaaciju, taa kaa tagad lietoju diezgan neoptimaalu sisteemu..

Ideja taada - katraa ciklaa noskaidroju redzamos objektus un iegruuzhu vinjus iekshaa render queuee (lv - rindaa ), kur tie tiek automaatiski sakaartoti peec materiaala (sheidera), kas patiesiibaa arii ir shiis sisteemas galvenais uzdevums. Tas nu taa kaa buuutu ljoti optimali un darbojas 100% ok, bet probleema ir ar taalaako darbiibu - proti naakamo kadru: kamera kustas un dazhi objekti vairs nav redzami - un te arii rodas probleema. Ko dariit? Principaa man ir 2 varianti:
1) cikla saakumaa iztiiru render queui pilniibaa tukshu un lieku iekshaa visu pa jaunu. Taads variants man ir tagad un straadaa diezgan labi. Tachu liek aizdomaaties par dinamiskajaam atminjas struktuuraam, kas tiek par jaunu aizpildiitas katraa kadraa un nepaartraukto atminjas 'chakareeshanu' - es gan protams render queuee glabaaju tikai pointerus ar attieciigaam atsleegaam (sheideriem), bet nu vienalga ir aizdomas, ka tas nav labs variants..
2) Ja objekts ir bijis render queuee un iziet no skata - iznjemu to aaraa un paareejos atstaaj neskartus. Izklausaas labi - bet ir milziigas probleemas ar aatru objekta atrashanu dinamiskaa datu struktuuraa un arii iznjemshana ir galiigi leena lieta (no STL vektora lineaaraa laikaa)... nu un patiesiibaa tieshi aatras atrashanas probleema ir diezgan liela (liidz dzeeshanai nemaz netiekot).. un turklaat shis veids sarezgjii kopeejo situaaciju un sisteema vairs nav tik universaala..

esmu meegjinaajis veel dazhus pseidovariantus, bet tie ir efektiivaaki tikai noteiktos gadijumos.. kopsumaa pirmais (brute force ) algoritms skjiet visefektiivaakais (seviskji labi tas rezams pie lielaaka skaita objektu, kur citas metodes pateeree lielu laiku mekleejot objektus un veicot iteraacijas pa objektu sarakstiem.)



tad nu gribeeju izraisiit augliigu diskusiju par sho teemu.. .. varbuut kaads var padaliities ar pieredzi un zinaashanaam??

[GiGa]

Neesmu gan taada veida render queue taisiijis, bet vispaar algoritmos man patiik brute force pieeja
Es domaaju neko daudz labaaku par 1. variantu neatradiisi. Bet kas tev par lielo atminjas chakareeshanu notiek? Kaada vaina variantam ar MAX_ENTRIES iespeejamajiem queue elementiem, kur, lai katru elementu pievienu tev tikai atliek uzsetot kaadu pointer un NowElements++; ? Vari jau protams biki advanceetaaku metodi - glabaa PlaceForElements, un ja queue tiek paarpildiits, pievieno vietu jauniem elementiem PlaceForElements+=ReserveStep; (protams uztaisot jaunu queue, nokopeejot jau esoshos elementus, un nodzeeshot veco queue) Un nedzees to visu aaraa starp kadriem. Taadaa veidaa, ja nu kadraa peeksni paraadaas par 200 potenciaaliem queue objektiem vairaak kaa pirms tam atminjas allocate'oshana notiks tikai vienreiz un paliks uz visiem naakamajiem kadriem. Hmm, vai arii probleema pavisam kaut kur citur, un es te pa velti muldu

[Hobits]

Man personiigi otrais varints izklausaas tiiri labs, ja objektu nau loti daudz, tad var izmantot linkedlistu lai aatri pievienotu un aisvaaktu objektus, pievienosanu var taisiit peec insertion-sort, t.i. iemest objetu uzreiz konkreetaa vietaa listaa, taadaa veidaa nebuutu nepieciesama atseviska sorteesana. Tikai viens bet, kaa objekti tiek pievienoti, jeb kaa efektiivi noteikt kuri objekti jau ir listaa lai tos nevajadzeetu pievienot. Peec kaada principa tu vispaar meklee objektus un kaa tev vinji ir sakaartoti?

[dev]

Nu man ideja ir taada (princips nedaudz paskatiits no Ogres) - visa render queue sastaav no vairaakaam render grupaam. Katrai render grupai ir hash tabula (STL map), kur kaa atseega ir sheideris. Pie katras atsleegas ir piekaartots saraksts (STL vektors), kuraa tad arii tiek iegruusti visi rendereejamie objekti, kas piederaas pie shiii materiaala. Taadejaadi notiek automaatiska sorteeshana peec sheideriem.
Un tieshi shii dinamiskaa sisteema rada probleemas - praktiski nav iespeejams atrast objektu nelineaaraa laikaa (man skjiet).

buus jaaizmeegjina vektoru aizvietot ar tiiru linkoto listu un jaaglabaa tieshaas noraades kopaa ar objektiem, lai var uzreiz objektu iznjemt no saraksta nemaz nemekleejot.. (vispaar jaapdamomaa, jo ieprieksh skjiet es shaadu variantu jau atzinu par nederiigu, bet tagad atkal man liekas tiiri labs.. laikam jaaiet guleet.. )

To Hobic: katram objektam ir bools, kas noraada vai dotais objekts ir vai nav pievienots listee. tad nu pie visibility chekinga arii atiieciigi riikojos - ja objekts nav pievienots, bet ir redzams, tad pievienoju un otraadi ..
un btw - insertion sorts vareetu buut gruuti realizeejams, taa kaa materiaalu skaits nav zinaams un mainiigs, un es pat nezinu kaa to vareetu realizeet (tiiri tehniski) .. turklaat shaada objektu pievienoshana (iespraushana) sarakstaa ir ljoti leena (ja ir jaapievieno daudzi objekti katraa kadraa - katrs objekts lineaaraa laikaa) .. kautgan var jau viltiigi riikoties (nu pat izdomaaju kaa ), bet nu mana pieeja skjiet ir effektiivaaka (ar hashtabulaam).

To Giga: jaa - probleema ir citur un tavs variants ir paaraak vienkaarshs un leens, un neder nekaadai sorteeshanai.. (sorteet jau var, bet ja tas ir aaveic katraa kadraa, tad freimreits tieksies uz 0)

[bubu]

Nu ja jau nepatīk meklēt pa sarakstiem lineārā laikā, tad jālieto binārie (AVL, Red-Black) koki, kur meklēšana notiek log(n) laikā.

[dev]

arii tas neder - par leenu ( ja jaameklee daudzi objekti katraa ciklaa).. AVL turklaat veel prasiitu ieveerojamu laiku balanseeshanaa pie liela skaita objektu..
.. bet nu labi - domaaju, ka kautko izdomaashu..

[Hobits]

He, nu patiesiibaa tavu pieeju ar stl mapu arii vareetu nosaukt par insertion-sortu, tikai tas ir automatizeets no stl pusses.

[dev]

nu jaa var jau nosaukt (teoreetiski jau ideja un rezultaats ir liidziigi)

ceru, ka liidz vakaram kaut ko uztaisiishu, ja nee tad pagaidaam atstaashu bruteforce un kjershos pie liimenja optimizaacijas..

btw - kaads ir darbojies ar Occlusion Culling (DX9) t.i. jauna metode 100% perfektai redzamo objektu noteikshanai (no jau it-kaa redzamo objektu saraksta ko dod visibility culling algoritms) ??? Lasiju ka Serious am Engine 2 atbalsta shaadu fiichu un esot noveerojams diezgan liels aatruma uzlabojums..
mani interesee dazhas tiiri tehniskas detaljas..

[GiGa]

http://www.gamedev.net/reference/programming/features/occlusionculling/

Iisi sakot darbojas taa, ka (zemaakaa rezoluucijaa) norenderee visus objektus(vai vinju bounding objektus) tikai depth bufferii un tad katru renderee velreiz, paskatoties vai kaads pixelis uz ekraana reaali tiek izmainiits, ja nee, nu tad droshi var atmest sho objektu no peedeejaa kraasainaa un shadereetaa rendera.

[dev]

jee... uztaisiiju objektu dinamisku aizvaakshanu no renderqueues.. - notesteeju, pie liela sakita objektu FPS ir taads pats (laikam taa atminjas chakareeshana nemaz nav ilga), tachu aatrums palielinaas, ja neviens objekts no daudzajiem nav redzams.

to GIGA: nu sho rakstu es ar lasiju, bet gribeeju zinaat ko vairaak..