Les structures de données

Les arbres binaires sont une structure de données...
Je vous entends d'ici me demander :


Eh bien c'est juste une technique de programmation qui vous permet d'organiser des données pour pouvoir les retrouver plus facilement et / ou plus rapidement.


En effet, dans un tableau (je parle d'un tableau en langage C et C++ bien sûr) les données sont rangées de façon contiguë, ce qui permet de les retrouver plus facilement.
Il est bien plus simple de gérer un tableau de 20 cases que de gérer 20 variables indépendantes.

Il existe beaucoup de structures de données différentes en C++, et la plupart n'existent pas nativement.
Les listes, les piles ou encore les arbres binaires par exemple, sont aussi des structures de données.


Intéressons-nous donc aux arbres binaires.

La première chose à savoir est qu'ils portent bien leur nom.
En effet, il s'agit d'une structure de donnée arborescente, qui peut être représentée avec des feuilles, des noeuds et une racine.

Voilà à quoi ressemble un arbre binaire graphiquement :

Vous voyez le rond rose ? Et bien c'est la racine.

Tous les ronds violets sont appelés noeuds. Il dépendent d'un noeud (ou d'une racine) au dessus d'eux mais ont également 1 ou 2 fils.

Quand un élément de l'arbre possède un ou deux éléments inférieurs, ceux-ci sont appelés fils.
Et comme il y a déjà assez de mots à retenir comme ça, on les appelle chacun gauche et droit.

Vous l'aurez deviné, dans l'autre sens on appelle l'élément père.
Le rond violet le plus à gauche est donc le père du rond vert le plus à gauche, qui est son fils gauche.


Les feuilles bien sûr !
Elles portent bien leur nom, ce sont les extrémités de l'arbre.
Ce qui implique qu'elles n'aient pas de fils (sinon ce serait des noeuds ).

Encore deux petites choses à savoir :

- la distance entre la racine et la dernière feuille est appelée la hauteur de l'arbre ;
- pour parler de la distance entre la racine et un noeud, on dit la profondeur de ce noeud.

Alors à partir de maintenant, je ne veux plus jamais entendre le mot distance en ce qui concerne les arbres binaires, compris ?


Le rond violet le plus à gauche sera donc un noeud de profondeur 1.

Voilà, vous connaissez maintenant l'essentiel sur les arbres binaires.
Il existe de nombreuses autres choses à savoir sur eux, mais ce n'est pas vraiment l'objet de ce tuto.
Le principal est que vous ayez compris le concept et les principaux termes qui s'y rapportent.
Si vous voulez en savoir plus, je vous recommande le très bon article de Wikipedia à ce sujet.
(Et pour les plus avides de connaissances, il y a aussi ce tuto très complet de Romuald Perrot.)
Bonne lecture.

Bon, maintenant que nous avons vu ce qu'est un arbre binaire, je peux vous l'avouer : on ne s'en servira pas pour utiliser Irrlicht.


Parce que ce que nous allons voir maintenant fonctionne un peu sur le même principe.

Un octree est aussi une structure de données arborescente.
Mais dans notre cas celle-ci va spécifiquement servir à... partitionner l'espace !

En gros, on va diviser notre scène en une multitude de petits morceaux pour réduire les temps de calculs.
...Ben au fait, j'ai quasiment tout dit . Il reste quelques petits détails techniques à voir, mais dans l'esprit c'est ça.


Voyons un peu de quoi est composé le mot OCTREE :
- du préfixe OCT, qui désigne un truc à 8 trucs . Comme un octogone, une surface à 8 cotés.
- du suffixe TREE, qui signifie tout simplement "arbre" en anglais.

Un octree est un arbre dont les noeuds peuvent avoir 8 fils.

De manière graphique, ça donne ça :

Je suppose que vous comprendrez pourquoi je n'ai pas représenté le second niveau.

Maintenant soyons un peu plus concrets. Du fait de son architecture (8 fils par noeuds), un octree va diviser l'espace dans lequel se déroule votre scène par multiples de 8.
Ce qui, graphiquement, ressemblerait à ça (j'ai pris un cube comme espace pour faire simple, mais ça marche pour n'importe quel parallélépipède rectangle) :

Si vous avez bien suivi, vous pouvez être capable de me donner la hauteur de l'arbre. Alors?
1 niveau en effet. L'espace de la scène est divisé une fois par 8.


Ha ha ! Voilà la question qu'on doit se poser. C'est bien beau de partitionner l'espace mais concrètement, qu'est-ce qu'on en a à faire ?!
Et bien la réponse a déjà été donnée plus haut.

Cela permet de réduire les temps de calcul...

Bon ok, j'avoue que c'est un peu vague.
Imaginez que votre caméra est placée dans la scène de telle manière que 5/8 de l'espace total de la scène lui sont cachés.
Et bien au moment du rendu, un petit test sur votre octree et hop, on oublie ces 5/8.
On ne calcule le rendu que pour les 3/8 visibles.
Les octrees, c'est magique.

On peut aussi s'en servir pour faire de la détection de collision et autres.


En effet !
Mais qui vous a dit qu'on ne pouvait diviser que par 8 ?
Pas moi en tout cas ! On peut avoir un octree de taille très élevée, le principe ne change pas.
Voici ce que donne un octree d'une hauteur de 2 (je n'ai redivisé que le cube ayant le plus de faces visibles... ) :

Il y a quand même une petite remarque à faire sur la hauteur que peut avoir un octree.
En effet, diviser l'espace c'est bien, mais on est pas là non plus pour faire de l'infiniment petit.


Pour reprendre l'exemple de la caméra, si on fait un octree d'une hauteur de 4, on aura un espace divisé en 4096 (8^4).
Imaginons que la caméra n'ait dans son champ que 2500/4096.
Il est possible que les quelques 32768èmes que l'on n'aurait pas calculés en augmentant la hauteur d'un niveau soient négligeables.
Tout dépend de la taille de votre espace, et de ce qu'il y a dedans...
Il est possible aussi que le temps qu'on passe à parcourir l'octree soit supérieur au temps qu'on aurait gagné en le faisant plus petit.

On va maintenant voir l'outil qui organise absolument tout ce que vous mettrez dans votre scène : le graphe de scène (que j'appellerai aussi scenegraph).

Vous allez voir, quand on a compris le principe des arbres, le graphe de scène est d'une simplicité et d'une efficacité effarante.

La première chose à savoir est qu'il s'agit là aussi d'une structure de données arborescente.
Mais, alors que les arbres binaires ne pouvaient avoir que deux fils par noeuds et les octrees 8, le graphe de scène n'a pas de nombre limite de fils pour un noeud !

Regardons un exemple :

Alors, vous comprenez un peu mieux ?
Un graphe de scène sert à organiser tout ce qui compose votre scène de manière hiérarchique.

La racine de l'arbre englobe toute la scène.
Puis chaque noeud correspond à un élément de la scène.

Mais ce qui est très important dans le graphe de scène, c'est le fait que les fils héritent des propriétés de leur père.
Et nous nous servirons principalement de cela pour faire des modifications sur les matrices.


Et à chaque fois que la matrice d'un noeud change, tous ses fils subissent donc automatiquement les transformations aussi.

Ce qui signifie que si on effectue une rotation de 90° sur la racine du graphe de scène, toute la scène pivotera de 90°.
En revanche, si on effectue une rotation de 90° sur l'armoire, seule elle-même et les noeuds qui en dépendent la subiront.

Et c'est là qu'on s'aperçoit qu'il ne faut pas faire n'importe quoi dans son graphe de scène !
Si vous faites en sorte qu'une salle dépende d'un objet qui s'y trouve plutôt que l'inverse, il risque de vous arriver des bricoles...