Octree Culling: Ottimizzare il rendering
(you can find it in "Game Programming Tutorials" if the link is broken) / Controlla in "Game Programming tutorials" su alcuni browser questo link non funziona per qualche motivo oscuro.
Using a Octtree in your game is highly reccomended / L'utilizzo di un Octree è caldamente consigliato
In the above image you see Daniel Sudmann Octree at work with a framerate of 333 fps with 2500 items and antialiasing turned on in pair with anisotropic filtering. Without this octree you will get a framerate of 60 fps (if you are lucky) / Nell'immagine qui sopra vedete all'opera l'Octree di Daniel Sudmann con un framerate di 333 fps ottenuto con 2500 oggetti visualizzati con tanto di filtro anisotropico e antialiasing. Senza questo Octree otterrete un framerate di 60 fps (se siete fortunati)
I'm working also on a improved version of the Daniel Sudmann's Octree, actually i'm getting 800 fps on a 2.0 Ghz processor. The new code is stable as the original but cannot be easily readed. I will release it OpenSource as attachment with the source release of my game. /
Sto lavorando inoltre su una versione potenziata dell'Octree di Daniel Sudman, attualmente riesco ad ottenere un framerate di 800 fps su un processore da 2.0 Ghz. Il nuovo codice è stabile quanto l'originale ma non può essere letto facilmente. Verrà rilasciato OpenSource assieme alla release del mio gioco.
You can zoom images by clickin 'em . / Puoi ingrandire le immagini cliccandoci sopra
This month we are back with an article about Daniel Sudmann's Octtree Manager. A very simple and powerfull tool that can be used to improve performance in rendering Scenes with lots of geometries. First of all we link back to the original code of Daniel Sudmann. All you have to do is to add the .cpp file and the .h file to your project. Include it where needed and contemplate the result. ;-)
Generally modern 3D cards can handle few, but elaborated meshes better than lots of little meshes. By contrast this is not always what a game developer want. For example if you are going to draw a forest in your game you usually have to draw lots of geometries. With few or lot i'm not referring to any particular number. In these terms "few" can be up to 300 meshes. and "lots" up to 3000. This depends on many things. If the mesh is particulary elaborated "few" can become 10 and "lots" can become 100.
A realtime 3d strategy game can have up to thousands units that need also to be animated and moved along paths that are handled by AI. Luckily not all meshes have to be drawed at once on the screen. If all goes well on the screen there will be a maximum of few hundreds units (at least 10 time faster than drawing every unit that is in the game).
The question is, how can we know wich units are on the screen and wich not?
There are several answers. One of them is "Use a Octree Scene Manager". Well Irrlicht has a Built-in octree scene manager, but it is not very good (compared to Sudi's one :) ). If you are in doubt, the Irrlicht OctreeScene manager is very stable, but also do some checks that are not necessary. (and also it checks every node if you don't mind to organize your scene nodes hierarchically). Sudi thinked about that and created his own OcttreSceneManager that organize everything automatically. On the other side the Irrlicht Octree is very flexible and has many other little advantages that usually are not used.
How a OcttreeSceneManagerWorks?
Theorycally it is not hard to understand.
First you must create a cube big enough to contain your entire game world. Than you divide the cube in 8 littler cubes. You divide those cubes again and so on. You must put all your game Items into the right cube. If the item is big it will be fitted into bigger cubes (after only 2,3 or 4 divisions). If the cube is little it will be putted into a littler cube. After that, empty cubes have to be removed from the game. (or you can instead prevent the creation of empty cubes by simply creating just-in-time the nodes you need for contain your game items).
After the tree is created you have only to use it.
First of all you start to check wich cubes are inside (partially or totally) in your screen.
Cubes that are inside your screen are keeped. Cubes that are outside the screen are "culled" and not rendered.
The check is not done in every node (or at least is not done in a good octree manager as Sudi's one).
First are checked bigger cubes. Cubes that are totally outside the screen are not rendered.
Cubes that are partially in the screen are keeped and their sub-cubes will be checked again.
Cubes that are totally in the screen are drawed , they don't need more checks since every future check on their sub-cubes will be positive.
Of course when I speak of screen I mean the 3D area of the world that is rendered on the screen (and wich is called "frustum").
Questo mese ritorniamo con un articolo sull' OctreeSceneManager di Daniel Sudmann. Uno strumento veramente semplice e potente che permette di migliorare il rendering delle scene che contengono un sacco di oggetti. Prima di tutto vi linko il codice originale di Sudmann, in modo da potervi tenere sempre aggiornati su suoi cambiamenti o per poter fare domande ulteriori sul suo utilizzo. Non vi resta che aggiungere i sorgenti al vostro progetto e guardare il semplice esempio di utilizzo. Poi contemplate il risultato ;-)
In generale le schede grafiche moderne possono gestire meglio poche mesh complesse piuttosto che tante mediamente elaborate. Purtroppo non è sempre quello che uno sviluppatore di videogiochi desidera. Per esempio se stai per disegnare una foresta nel tuo gioco normalmente avrai da gestire molti oggetti (gli alberi, le fronde, l'erba).
Con "molti" o "pochi" non mi riferisco ad un numero particolare di oggetti. A seconda della complessità degli stessi il numero può variare considerevolmente (specialmente se le mesh sono animate o legate ad un sistema di ragdoll).
Un gioco di strategia 3D in tempo reale può dover gestire fino a diverse migliaia di oggetti alcuni dei quali sono animati e devono seguire percorsi che vengono decisi dall'IA. Per fortuna non tutte le mesh devono essere disegnate contemporaneamente sullo schermo e se tutto va bene solo una piccola parte delle unità totali sarà disegnata sullo schermo.
La domanda è per l'appunto come facciamo a sapere quali unità sono sullo schermo e quali no?
Ci sono diverse risposte possibili. Una di esse è "Usare un OctreeManager". Irrlicht ha un Octree Manager built-in che però non è dei migliori (specie se comparato con quello di Sudi :) ). Se sei in dubbio su quale Octree Manager utilizzare, quello di Irrlicht è molto stabile ma esegue controlli che non sono necessari. (inoltre tende e controllare ogni singolo nodo se non ti preoccupi di organizzare la scena gerarchicamente). Sudi ha pensato un attimo a come fare e ha creato il suo Octtree Scene Manager che organizza tutto in modo automatico. D'altro canto anche l' Octree di Irrlicht ha dei piccoli vantaggi che però di solito non sono utilizzati.
Come funziona un OctreeManger?
In teoria non è difficile da comprendere (anzi è solo l'implementazione che può causare problemi :) e il disturbo di implementarlo ci è stato tolto fornendo una semplice interfaccia per l'utilizzo.)
Per prima cosa si deve creare un cubo abbastanza grande da contenere l'intero mondo di gioco. Dopodichè si divide il cubo in altri 8 cubetti e continui a dividere fino ad ottenere i cubetti di dimensione minima. Tutto ciò che va fatto è inserire gli oggetti del gioco nel cubo giusto. Gli oggetti più grossi possono occupare i cubi più grossi. Mentre gli oggetti più piccoli vengono inseriti nei cubi più piccoli. Generalmente se un oggetto piccolo è collocato a metà tra due cubetti questo verrà inserito nel nodo-padre che contiene quei due cubetti (più ovviamente gli altri 6). Dopodichè i cubi vuoti vanno rimossi dal gioco. (in alternativa è possibile creare solo i cubi strettamente necessari aggiungendo quelli necessari man mano che vengono inseriti oggetti nel gioco).
Ora abbiamo un albero organizzato non ci resta che utilizzarlo. Per farlo bisogna controllare quali cubi sono sullo schermo (completamente o parzialmente) e quali no. I Cubi che sono dentro lo schermo vengono tenuti quelli che sono totalmente fuori dallo schermo vengono scartati così come i loro cubi-figlio.
Ovviamente il controllo non deve venire fatto per ogni singolo cubo (almeno non in un OctreeManager realizzato con oculatezza). Si inizia con il controllare i cubi più grossi. Così se un cubo è fuori dallo schermo vengono automaticamente scartati tutti i suoi figli senza doverli controllare ulteriormente.
Se un cubo è parzialmente all'interno dello schermo i suoi cubi-figlio vengono ulteriormente controllati.
I cubi che sono totalmente all'interno dello schermo invece vengono disegnati interamente senza ulteriori controlli (infatti pare ovvio che se un cubo è nello schermo anche i suoi cubi figlio lo saranno).
Ovviamente quando parlo dello schermo mi riferisco alla zona 3D del mondo che è renderizzata e che ha la forma di un tronco di piramide (viene chiamata "frustum").
If you notice errors or broken links please let me know by sending an e-mail to me. Thanks / Se noti errori o link mancanti fammelo sapere tramite un email. Grazie