), je voudrais votre avis sur certaines structures de données, notemment les arbres binaires.
Je me suis penché sur les BSP, et je me demandais quelle structure donner à un tel arbre... Par structure, je n'entends pas comment l'arbre est fait, avec ses sous arbres gauche et droits, mais à une organisation en mémoire...
Pour ceux que ce nom hérisse, petit rappel:
arbre BSP simple:
Les carrés A,B,C,D,E,etc... sont les noeuds de l'arbre. Les sous arbres gauche et droits correspondent aux deux subdivisions de l'espace du noeud courant, il n'y a qu'un polygône par noeud.
On peut le parcourir avec un code du genre:
Walk_BSP(node)
{
if(leftsubnode(node)!=NULL)
{
Walk_BSP(leftsubnode(node))
}
if(rightsubnode(node)!=NULL)
{
Walk_BSP(rightsubnode(node))
}
}
ce qui est un procédé extrèmement simple...
quand le code à parcouru tous les sous arbres gauche de la branche courante (leftsubnode(node)=NULL), il passe aux sous arbres droits et reprend le processus à 0, quand le noeud courant n'a plus de sous arbres, la routine quitte et revient à son précédent appel, jusqu'à ce que tous les noeuds de l'arbre aient été parcourus...
Maintenant, voici mon problème:
il est aisé avec un langage de haut niveau comme le C/C++ d'implémenter une structure d'arbres bsp, notemment par l'emploi de trucs du genre node->leftnode ou node->rightnode. Seulement, comment organiser une telle structure directement?
j'avais pensé à quelquechose de la sorte:
node dc.w pointer_leftnode,pointer_rightnode,pointer_polygon
mais je me demandais s'il n'y avait pas une approche plus efficace du point de vue de la place prise, ou de la simplicité de parcours...
est-ce qu'il y a une méthode de stockage du bsp meilleure que la mienne (sûr à 100%
), et donc vu que oui, laquelle? 
N'importe quelle idée est la bienvenue
(ah, oui, j'oubliais, le parcours doit se faire en temps réel, le plus rapidement possible, donc la structure doit être la plus simple possible
)[edit]Edité par sBibi le 01-01-2002 à 14:47:47[/edit]
