Aller au menu - Aller au contenu

Icône Structures de données

Avatar
Par Avatar Kevin Leonhart
Mise à jour : 23/03/2011
Difficulté : Facile Facile Creative Commons BY-SA
1 621 visites depuis 7 jours, dont 134 sur ce chapitre classé 80/786
Voici un chapitre entièrement théorique dédié aux structures de données, et plus particulièrement aux arbres. D'une manière générale ceux-ci sont très importants en programmation, mais en ce qui nous concerne ils sont absolument indispensable puisque c'est grâce à un arbre nommé graphe de scène qu'Irrlicht organise tout le contenu d'une scène 3D.
Retour en haut
Sommaire du chapitre :
Icône du chapitre
Chapitre précédent Sommaire Chapitre suivant
Retour en haut

Arbre binaire

Pour ceux qui ne le savent pas déjà, une structure de données est juste une technique de programmation permettant d'organiser des données d'une certaine manière dans le but d'y accéder plus facilement et / ou plus rapidement.

Un tableau par exemple est une structure de données. En effet dans un tableau (je parle d'un tableau en langage 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++ dont la plupart n'existent pas nativement. La bibliothèque tierce Boost par exemple contient énormément de conteneurs permettant d'organiser des données de manière intéressante [33-2].

Mais pour l'instant donc, intéressons nous aux arbres binaires. La première chose à savoir est qu'ils portent bien leur nom dans la mesure où il s'agit d'une structure de donnée arborescente. C'est à dire qui peut être représentée avec des feuilles, des nœuds et une racine. Voici à quoi ressemble un arbre binaire graphiquement :
Image utilisateur

Et maintenant un peu de vocabulaire. Le rond rose est la racine de l'arbre. Un arbre n'a toujours qu'une seule et unique racine. Tous les ronds violets sont appelés nœuds. Ils dépendent d'un nœud (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. Et les ronds verts sont les feuilles bien sûr. Elles portent bien leur nom puisque ce sont ce sont les extrémités de l'arbre. Ce qui implique qu'elles n'aient pas de fils (sinon ce serait des nœuds ;) ).


La distance entre la racine et la dernière feuille (le nombre de niveaux) est appelée la hauteur de l'arbre. Ici nous avons un arbre de hauteur 4. Et la distance entre la racine et un nœud est appelée profondeur.

La racine est par définition le nœud de niveau 0. 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 le sujet [33-1] mais ce n'est pas particulièrement important pour ce tutoriel. Le principal est que vous ayez compris le concept et les principaux termes qui s'y rapportent.
Retour en haut

Octree

Un octree est également une structure de données arborescente. La plupart du temps elle est utilisée pour partitionner l'espace. C'est à dire diviser un espace en morceaux plus petits, pour réduire les temps de calculs notamment.

Si nous regardons de plus près le mot OCTREE, on s’aperçoit qu'il est composé des deux parties suivantes :
  • OCT : qui désigne un truc à 8 trucs ^^ . Comme un octogone, une surface à 8 cotés.
  • TREE : qui signifie tout simplement "arbre" en anglais.


Un octree est donc tout simplement un arbre dont les noeuds ont 8 fils. De manière graphique ça donne le résultat suivant :
Image utilisateur

Je suppose que vous comprendrez pourquoi je n'ai pas représenté le second niveau... L'avantage d'avoir 8 fils par nœuds devient évident quand on pense à la manière dont est stocké un espace en informatique. En clair, il s'agit systématiquement d'un parallélépipède rectangle, qu'il est facile de diviser en 8 parts égales. Comme sur l'images suivante :
Image utilisateur
Si vous avez bien suivi vous devriez même être capable de me donner la hauteur de l'arbre. Niveau 1 en effet, l'espace de la scène est divisé une fois par 8. Maintenant que l'espace est partitionné en 8 le moteur 3D va pouvoir réduire les temps de calcul.

Imaginez par exemple que la caméra soit placée dans la scène de telle manière que 5/8 de l'espace total lui soit cachés. Au moment du rendu, un petit test sur l'octree et hop, on oublie ces 5/8. On ne calcule le rendu que pour les 3/8 visibles, ceux qui apparaîtront à l'écran. On peut également s'en servir pour faire de la détection de collision d'autres choses encore.

Rien n'empêche ensuite d'augmenter le niveau niveau de l'arbre. 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... :-° ) :
Image utilisateur
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 il arrive un moment où ça devient contre-productif. 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 (84). Imaginons que la caméra n'ait dans son champ que 2500 des 4096 morceaux.

Si nous augmentons le niveau de l'octree cela nous donne 32768 morceaux. Il est possible que les quelques morceaux que l'on ne calculerais pas avec une hauteur de 5 vis à vis d'une hauteur de 4 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.

Quoi qu'il en soit tout cela ne nous concerne pas vraiment pour l'instant puisqu'une fois encore, Irrlicht va gérer tout ça en interne et nous n'aurons pas besoin de nous en occuper. :)
Retour en haut

Graphe de scène

Abordons maintenant ce qui nous intéresse le plus avec l'outil qui organise absolument tout ce qui est mis dans une scène Irrlicht : le graphe de scène (que j'appellerai aussi et surtout scene manager). Quand on a compris le principe des arbres, le scene manager 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 scène manager n'a pas de nombre limite. Regardons un exemple :
Image utilisateur

Alors, vous comprenez déjà un peu mieux ? Le scene manager sert à organiser tout ce qui compose la scène de manière hiérarchique. Et pas seulement ce qui apparaîtra à l'écran comme vous pouvez le voir avec le node "camera". La racine de l'arbre englobe toute la scène, puis chaque nœud correspond à un élément précis.

Un autre élément très important concernant le scene manager est le fait que les fils héritent des propriétés spatiales de leur père. Et nous nous servirons principalement de cela pour faire des modifications sur les positions et orientations des nœuds. En effet à chaque nœud est associée une matrice qui représente ses transformations par rapport à la matrice de son père. Et à chaque fois que la matrice d'un noeud change, tous ses fils subissent donc automatiquement les transformations.

Ce qui signifie que si on effectue une rotation de 90° sur le nœud "salle", les nœuds "armoire", "objet" et "perso" pivoteront eux aussi de 90°. En revanche si on effectue une rotation de 90° sur le nœud "armoire", seul le nœud "objet" pivotera aussi de 90°. Et c'est là qu'on s'aperçoit qu'il ne faut pas faire n'importe quoi dans son scene manager. 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... :D
Retour en haut
Chapitre précédent Sommaire Chapitre suivant
Retour en haut

Partager

Retour en haut

Lire aussi

Icône
La représentation intervallaire
Icône
3D temps réel avec Irrlicht
Icône
Introduction
Icône
L'arbre de création
Retour en haut
2 commentaires pour "Structures de données"
Note moyenne : 3.60 / 4 (122 votes)
Pseudo Commentaire
Hors ligne rolus # Posté le 07/09/2008 à 11:25:09
Avatar

 si le nom de chaque noeud avait ete mis dans le cercles du graphique par rapport a un petit programe ,cela aurait ete plus facile à comprendre.
Hors ligne Leazerface # Posté le 07/11/2009 à 18:47:51
Avatar

 Je pense pas qu'il y ait mieux expliqué^^ (en même temps chuis pas allé voir ailleurs sauf les liens que tu donnes)
...Franchement tout est bien choisit, même les couleurs pour mémoriser ^^ J'espère que la suite sera aussi bien (et avec QCM sinon on retient moins bien :p)
La culture, c'est comme la confiture, moins on en a, plus on l'étale !

Ne prenez pas la vie trop au sérieux, de toute façon vous n'en ressortirez pas vivant ;p
 

Voir tous les commentaires