Ardor3D est un arbre de scène [Ardor3D is a scene tree]

Français English
J’ai récemment expliqué à un utilisateur du moteur 3D Ardor3D pourquoi ce graphe de scène ne repose pas sur un graphe au sens général du terme et je me suis dit qu’il serait opportun de faire un article à ce sujet au lieu de répéter la même chose à chaque fois. I recently explained to a user of the 3D engine Ardor3D why this scene graph is not based on a graph in a general sense of the term and I thought it would be appropriate to make an article about it instead of repeating the same thing every time.
Les principaux développeurs d’Ardor3D prétendent qu’ils utilisent une structure de données appelée « graphe acyclique orienté ». Je vais vous montrer pourquoi cela est assez approximatif. The main developers of Ardor3D claim they use a data structure called « directed acyclic graph ». I will show you why this is pretty rough.
Tout d’abord, la relation entre les nœuds d’Ardor3D est la relation père → enfants, elle n’est pas symétrique. « Le nœud A a pour seul enfant le nœud B » n’équivaut pas à « Le nœud B a pour seul enfant le nœud A ». En conséquence, la structure de données d’Ardor3D est bien orientée. At first, the relationship between the nodes of Ardor3D is the relationship father → children, it is not symmetrical. « Node A has a single child node B » is not equivalent to « Node B has a single child node A ». Consequently, the data structure Ardor3D is oriented.
De plus, une structure de données acyclique est une structure de données sans le moindre cycle. Un cycle est un chemin dont les deux nœuds aux extrémités sont identiques. Ardor3D ne permet pas de créer un tel chemin, il boucle jusqu’à lancer une StackOverflowError (sans mon patch) ou bien il lance une IllegalArgumentException si le potentiel nœud père est un descendant du potentiel nœud fils (avec mon patch), cela inclut le cas où les deux nœuds sont identiques. En conséquence, la structure de données d’Ardor3D est bien acyclique. Moreover, an acyclic data structure is a data structure without any cycle. A cycle is a path whose two extremities are identical nodes. Ardor3D does not create such a path, it repeatedly loops until it launches a StackOverflowError (without my patch) or it launches an IllegalArgumentException if the potential parent node is a descendant of potential child node (with my patch), this includes the case in which both nodes are identical. Consequently, the data structure of Ardor3D is acyclic.
Ensuite, un graphe est une structure de données qui permet de relier des nœuds par des arêtes. En ce sens, Ardor3D est bien un graphe. Ainsi, la structure de données d’Ardor3D est bien un graphe acyclique orienté. Then, a graph is a data structure that connects nodes by edges. In this meaning, Ardor3D is a graph. Thus, the data structure of Ardor3D is a directed acyclic graph.
Enfin, chaque nœud d’Ardor3D a zéro ou plus nœuds fils et au plus un nœud père. J’ai montré précédemment que sa structure de données est bien un graphe acyclique orienté. Par définition, un graphe acyclique orienté connexe dont chaque nœud a zéro ou plus nœuds fils et au plus un nœud père est un arbre orienté donc sa structure de données est bien un arbre. Finally, each node of Ardor3D has zero or more child nodes and at most one parent node. I have previously shown that its data structure is a directed acyclic graph. By definition, a connected directed acyclic graph in which each node has zero or more child nodes and at most one parent node is a directed tree then its data structure is a tree.
Je pense qu’il est important d’éviter toute confusion entre les arbres et les graphes. Tous les arbres sont des graphes mais tous les graphes ne sont pas des arbres. Les développeurs de certains moteurs 3D ne font pas toujours la différence entre un arbre et un graphe acyclique orienté comme ils utilisent des algorithmes de parcours qui marchent aussi bien avec les uns qu’avec les autres. En fait, à ma connaissance, le seul moteur 3D supportant partiellement les graphes cycliques est celui que j’avais écrit pour la version alpha de TUER. J’avais également modifié JMonkeyEngine pour qu’il les supporte à son tour. Je dois avouer que cela donne quelque chose d’assez bâtard comme j’incorpore des graphes cycles (graphes non-orientés constitués d’un unique cycle) à l’intérieur d’un arbre. J’espère que vous comprenez mieux pourquoi je préfère parler d’arbres de scène plutôt que de graphes de scène, ce terme est aussi plus approprié pour d’autres moteurs 3D et APIs dont JMonkeyEngine, MSG, Aviatrix3D, Xith3D, Java3D, 3DzzD, JIRR, Ogre4J, etc… I think it is important to avoid confusion between trees and graphs. All trees are graphs but all graphs are not trees. The developers of some 3D engines do not always make the difference between a tree and a directed acyclic graph as they use search algorithms that also work well with the formers and with the latters. In fact, as far as I know, the only 3D engine partially supporting cyclic graphs is the one I wrote for the alpha version of TUER. I also modified JMonkeyEngine so that it supports them too. I must admit that it gives something quite bastard as I incorporate circular graphs (non-oriented graphs consisting of a single cycle) within a tree. I hope you understand better why I prefer speaking of scene trees rather than scene graphs, this term is more appropriate for other 3D engines and APIs which JMonkeyEngine, MSG, Aviatrix3D, Xith3D, Java3D, 3DzzD, JIRR, Ogre4J, etc…
Licence Creative Commons
Cet article est mis à disposition selon les termes de la Licence Creative Commons Attribution – Pas d'Utilisation Commerciale – Partage à l'Identique 3.0 non transposé
Creative Commons License
This article is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
Auteur : Julien Gouesse Author: Julien Gouesse

A propos gouessej

Ingénieur en informatique, militant politique d'extrême-gauche, développeur de logiciels libres multi-plateformes. Engineer in computer science, far left-wing political activist, developer of free open source cross-platform softwares.
Cet article, publié dans Jeux vidéo, est tagué , . Ajoutez ce permalien à vos favoris.