Généralités sur les arbres BSP

Un article de Bahamut.

Le but de cet article est de vous présenter de manière théorique les arbres BSP.

[modifier] Préambule

L'élaboration d'un jeu ne se résume pas à une simple liste de polygones à représenter sur un écran. Il existe un certain nombre de problèmes complexes auxquels le concepteur doit faire face. Ces problèmes doivent être résolus le plus élégamment que possible pour une meilleure compréhension de l'algorithme utilisé mais aussi le plus efficacement que possible pour une meilleure rapidité d'exécution du code. C'est le challenge de la programmation graphique.

Un certain nombre de problèmes graphiques complexes, tels que la détection de collision ou du lancer de rayon sur des objets, relèvent du partitionnement spatial. Vous avez besoin de savoir où les objets (définis par une représentation limitée de polygones) existent par rapport aux autres objets qui les entourent. Vous pouvez bien sûr les trouver facilement, mais en contre-partie vous devez utiliser des algorithmes complexes et lents. Pour exemple, vous voulez voir si un lancer de rayon traversant un espace, frappe un polygone. Le moyen le plus lent serait de tester chacun leur tour, tous les polygones sur le rayon. De plus, l'intersection entre un rayon et un polygone n'est pas une opération triviale, alors s'il y a plusieurs milliers de polygones, la vitesse de cet algorithme peut rapidement décroître.

Une relation spatiale des polygones est une solution. Les arbres BSP sont l'un des moyens les plus utilisés pour partitionner un espace.

[modifier] Un peu de théorie

Les arbres BSP sont une spécialisation des arbres binaires et ils représentent une région dans l'espace. L'arbre est composé de noeuds (un noeud possède exactement deux enfants) et de feuilles (noeuds terminaux qui ne possèdent aucun enfant). Un noeud représente un partitionnement de l'espace. Le partitionnement crée deux nouveaux espaces, un au devant (visible) du noeud et un en arrière (caché) du noeud.

Dans les applications 2D, comme Doom (dans laquelle est utilisé un arbre BSP pour représenter le monde où doit évoluer un marine de l'espace), l'ensemble de l'arbre représente entièrement le monde 2D. Le noeud principal définit le partitionnement du monde en deux pièces selon une ligne d'équation, l'une des pièces est devant la ligne et l'autre pièce derrière la ligne. Chacune des deux pièces est représentée par un sous-arbre, lui aussi un arbre BSP. Chaque noeud contient un segment de ligne utilisé dans le partitionnement. Le segment de ligne, avec d'autres informations tels que la hauteur et l'identifiant de la texture, deviendra un mur dans le monde. Les sous-arbres deviennent des feuilles si et seulement si l'espace qu'ils représentent ne contient pas d'autres murs à l'intérieur. Si ce n'est pas le cas, le mur sera utilisé pour partitionner de nouveau l'espace.

Dans les applications 3D, les choses sont à peu près semblables. L'espace est partitionné avec des plans 3D.

Il existe deux principaux types d'arbres BSP. Dans la première méthode (appelée arbres BSP basés sur les noeuds ou node-based BSP trees), les noeuds contiennent l'ensemble des polygones et des plans utilisés pour le partitionnement. Les feuilles sont vides. Dans l'autre méthode (appelée arbres BSP basés sur les feuilles ou leafy BSP trees), les noeuds contiennent uniquement les plans de partitionnement. Les feuilles contiennent tous les polygones qui composent le monde complexe 2D ou 3D. Je vais parler uniquement de la première méthode à propos des BSP basés sur les noeuds, mais les BSP basés sur les feuilles sont couramment utilisés.

Les arbres BSP sont surtout utilisés quand les polygones utilisés pour la construction d'un arbre représentent une représentation limitée d'un objet. L'objet possède conceptuellement un intérieur fait de solide, et un extérieur entouré de vide, et les polygones représentent la frontière entre ces deux milieux. Quand l'arbre est complet, chaque feuille représente soit un espace solide, soit un espace vide.

[modifier] Construction d'un arbre BSP

L'algorithme pour créer un node-based BSP tree est simple et récursif. Il convient notamment aux mondes statiques. D'ailleurs, c'est le cas dans la plupart des mondes où les joueurs naviguent dans les jeux 3D, comme Quake qui consiste en un arbre BSP statique (représentant un monde) et un ensemble d'objets (vies, munitions, joueurs, ennemis, portes, etc.) qui peuvent bouger à travers le monde.

Je vais aller à travers la construction de l'arbre en procédant étape par étape. Le pseudo-code correspondant à l'algorithme décrit ci-dessus est le suivant :

struct node
   polygon poly
   plane part_plane
   ptr front
   ptr back
   vector<polygon> coplanar_polygons
 
struct leaf
   bool solid
 
leaf Make_Leaf(bool solid)
   leaf out = new leaf
   out.solid = solid
   return out
 
polygon Get_Splitting_Polygon(vector<polygon>input_list)
   polygon out = polygon that satisfies some hueristic
   remove out from input_list
   return out
 
node Make_Node(vector<polygon> input_list)
   vector<polygon> front_list, back_list
   node out = new node
   chosen_polygon = Get_Splitting_Polygon(input_list)
   out.part_plane = Make_Plane_From_Polygon(input_list)
   out.poly = chosen_polygon
   for(each polygon current in input_list)
       switch(out.part_plane.Classify_Polygon(current))
           case front
               add current to front_list
           case back
               add current to back_list
           case coplanar
               add current to node.coplanar_polygons
           case split
               split current into front and back polygons
               add front to front_list
               add back to back_list
   if (front_list is empty)
       out.front = Make_Leaf (false)
   else
       out.back = Make_Leaf (front_list)
   if (back_list is empty)
       out.back = Make_Leaf(true)
   else
       out.back = Make_Node(back_list)
   return out
 
   node Make_BSP_Tree(vector<polygon> input_list)
       return Make_Node(input_list)

Nous allons illustrer la prochaine étape d'un exemple d'arbre 2D. Le monde que nous allons décrire est composé un espace dans lequel est défini une région fermée (composées de polygones) pour laquelle l'intérieur est solide. Cette région est entourée d'espace vide. Prenons l'exemple d'une région solide délimitée par quatre polygones appelés respectivement A, B, C et D. La figure 1 montre le cas initial, avec les polygones sur la gauche et une liste sur la droite. Chacun des segments possède une normale de visibilité qui est dirigée en dehors de la région solide (représentée en bleu).

Pour créer le noeud principal, nous allons utiliser le segment A (pris au hasard). Traçons une ligne intermédiaire (ligne rose) parcourant le segment A. Les segments B, C et D sont tous derrière cette ligne et sont donc cachés par rapport à celle ci. De ce fait, nous allons placer les trois segment dans la liste des faces arrière (zone verte). La liste des faces de devant (zone jaune) est vide puisqu'il n'y a aucun polygones devant le segment A. La liste vide est représenté par l'enfant visible du noeud principal, d'une feuille d'espace vide (signe moins). La liste des faces cachées n'est pas vide, ce qui nécessite un partitionnement en un sous espace derrière le segment A. Le résultat de la première partition est représenté par la figure 2.

Une fois le partitionnement de l'enfant caché (façon de parler) du noeud principal effectué, je vais utiliser le segment B. Dans les applications réelles, ça ne serait pas ce segment qui serait choisi, mais j'ai choisi de prendre le segment B pour diversifier l'exemple. Dans ce cas de sélection, nous traçons une seconde ligne intermédiaire (rose) qui parcourt le segment B. Le segment C est devant cette ligne mais le segment D est partiellement devant et partiellement derrière la ligne rose. On doit alors éclater le segment D en deux pièces, l'une complètement devant (appelée Dv), et l'autre complètement derrière (appelée Dc). Cette étape est illustrée par la figure 3.

Note : regardez bien la ligne rose pour le segment B. Elle n'entre pas dans l'espace de devant du segment A (zone non colorée), parce qu'on partitionne seulement derrière A. C'est un point très important que vous devez assimiler si vous voulez réellement comprendre le fonctionnement interne des arbres BSP.

Je vais maintenant partitionner le devant du noeud (liste de C et Dv). J'utilise Dv comme segment de partitionnement. C est l'unique polygone à classifier et il se trouve derrière le segment Dv. La liste de devant est vide, et de ce fait, je crée une feuille représentant un espace vide (signe moins). Voir la figure 4 pour illustration.

A ce stade, il ne reste plus que deux noeuds à traiter, C et Dc. Pour rapidement conclure ce tutorial de construction d'arbre, je vais effectuer les deux opérations en une étape. Tous deux n'ont aucuns polygones à classifier. Tous deux se voient attribuer deux noeuds enfants qui ne seront ni plus ni moins que deux feuilles : une feuille pour représenter la partie solide derrière le polygone (signe plus) et une feuille pour représenter l'espace vide devant le polygone (signe moins). Ce résultat est l'arbre BSP final, qui apparaît ci dessous dans la figure 5. J'ai dessiné des fines lignes à partir des feuilles vers les sous espaces qu'elles représentent.

Un problème qui doit se poser est comment choisir les polygones pour partitionner l'espace du monde en sous-espaces. Deux solutions peuvent vous satisfaire : choisir le polygone qui cause le moins d'éclatement de segments, ou choisir le polygone qui fait le plus d'éclatement. Dans cette deuxième solution, un problème qui peut se poser est le nombre important de données que cela peut générer dans l'arbre et plus particulièrement au sommet de l'arbre. Pour plus d'informations sur cette seconde solution reportez vous sur l'article "Foley's Computer Graphics".

[modifier] Un outil de construction : Applet de Paton J.Lewis

L'Applet illustrée ci dessous a été développée par Paton J.Lewis pour simuler la construction d'un arbre BSP pour un univers 2D. La méthode utilisée est le node-based BSP trees.

Dans la fenêtre en haut à gauche, vous ajoutez vos segments de droite (polygones vus de dessus) à l'aide de la souris. Lorsque vous ajoutez un segment, l'arbre BSP représenté dans la fenêtre du milieu se construit au fur et à mesure. L'Applet propose d'autres fonctionnalités tel que le déplacement et la rotation du point de vue avec parcours dans l'arbre (rond rose). Pour plus d'info, consultez le site de l'auteur.

[modifier] Algorithmes sur les arbres BSP

Il existe un certain nombre d'algorithme pour créer un arbre BSP. Le type d'algorithme employé dépend fortement de l'utilisation que l'on veut donner au BSP : s'il s'agit de faire de l'élimination de facettes, ou de la détection de collision, l'algorithme est différent.

Dans ce chapitre, je vais traiter des trois principaux algorithmes les plus fréquemment utilisés pour les arbres BSP. Il s'agit du tri ordonné des polygones, le test de position d'un point et le test des segments de droite.

[modifier] Le tri ordonné des polygones

L'une des premières utilisations des arbres BSP est de trier une liste de polygones par rapport à un point de vue donné. Cette technique était utilisée bien avant les z-buffers matériels, quand les polygones avaient besoin d'être dessinés de l'arrière vers l'avant pour être rendus correctement. Maintenant, les z-buffers fonctionnent bien plus vite en rejetant les faces le plus rapidement que possible, c-à-d dessiner les polygones de l'avant vers l'arrière : un net avantage puisque tous les polygones ne sont pas dessinés contrairement à la première méthode. En revanche, les polygones pour lesquels on applique une couche Alpha (transparence), ils doivent forcément être rendus du fond vers l'avant pour obtenir un rendu correct.

Le concept fondamental derrière cet algorithme est le suivant : si vous avez un certain plan qui découpe la scène en deux pièces et que vous vous trouvez sur l'un des côté du plan alors rien derrière ce plan ne peut obstruer ce qui se trouve devant le plan. Armé de cette règle, tout ce que vous avez à faire est de parcourir l'arbre. A chaque noeud, vous essayez de voir de quel côté est tourné la caméra. Si elle est au devant, alors vous ajoutez tous les polygones derrière le plan (en traversant par le noeud de derrière), puis tous les polygones compris dans le plan (les polygones partitionnés et coplanaires), et finalement les polygones qui sont placé devant le plan (en traversant le noeud de devant). Dans le cas contraire, on effectue les mêmes opération mais dans l'ordre inverse. Les feuilles de l'arbres retournent quant à elle un "return".

L'algorithme correspondant est simple et récursif. Voici le pseudo code pour trier une liste de polygones en fonction de la distance :

void node::GetSortedPolyList(list<polygon3>*plist, point& camera)
{
   switch (node.part_plane.Classify_Point(camera))
   {
       case front
           back.GetSortedPolyList(pList, camera);
           add all node polygons to pList
           front.GetSortedPolyList(pList, camera);
       case back
           front.GetSortedPolyList(pList, camera);
           add all node polygons to pList
           back.GetSortedPolyList(pList, camera);
       case coplanar
           //order doesn't matter
           front.GetSortedPolyList(pList, camera);
           back.GetSortedPolyList(pList, camera);
   }
}
 
void leaf::GetSortedPolyList( list<polygon3>*pList, point& camera)
{
   return;
}

[modifier] Le test de position d'un point

Une réelle grande utilisation des arbres BSP est de tester la position d'un point dans un monde. A partir d'un point donné et d'un arbre, vous pouvez dire si un point est situé dans une région vide ou solide (représenté dans l'arbre par une feuille vide ou solide). C'est utilisé le plus souvent pour la détection de collision.

L'algorithme qui permet de réaliser cela est extrêmement simple. A chaque branche de l'arbre, vous testez le point par rapport au plan. Si le point est situé devant, vous parcourez la branche de devant (parcours vers le bas). Mais si le point est situé derrière le plan, alors vous parcourez l'arbre par la branche de derrière. Et si le point est situé sur le plan, vous parcourez l'une des deux branches (A vous de fixer laquelle !). Une fois que vous arrivez sur une feuille, vous savez alors dans quelle région de l'espace, le point est situé. Si la feuille est dite solide, alors le point est situé dans une région pleine (il y a collision). Si la feuille est dite vide, alors le point est situé dans une région non pleine (il n'y a pas de collision).

Voici le pseudo code correspondant à l'algorithme pour tester la position d'un point dans l'espace :

bool node::TestPoint(point& pt)
{
   switch(node.part_plane.Classify_Point(pt))
   {
       case front
           return front.TestPoint(pt);
       case back
           return back.TestPoint(pt);
       case coplanar
           // Let's drop down the back tree
           return back.TestPoint(pt);
   }
}
 
bool leaf::TestPoint(point& pt)
{
   if (solid)
       return true;
   return false;
}

[modifier] Le test des segments de droite

Cette algorithme consiste à retourner vrai s'il existe un segment de droite non coupé entre deux points (extrémités du segments). Sinon, il retourne faux. Une autre approche permet de dire que l'algorithme retourne vrai si et seulement si le segment de droite siège dans des feuilles non solides.

L'algorithme est le suivant : à partir du sommet de l'arbre, vous comparez le segment de droite au plan à un noeud donné. Si le segment de droite est complètement devant, vous parcourez l'arbre par l'enfant (noeud) de devant. Si le segment de droite est complètement derrière le plan, alors vous parcourez l'arbre par l'enfant de derrière. Et si le segment traverse le plan, alors ce segment doit être éclaté en deux pièces (une devant et une derrière). Finalement, si aucun du segment n'est arrivé dans une feuille solide, alors l'algorithme retourne vrai.

[modifier] Références bibliographiques

1. Advanced 3D Game Programming using DirectX 8.0 - par Peter Walsh - édition Wordware
2. Principles and Practice, Second Edition - par Foley, James D. et al. Computer Graphics - C. Addison-Wesley
3. Real-Time Rendering - par Moller, Tomas et Eric Haines - A K Peters Ltd - 1999
4. FAQ BSP Tree sur le site de Silicon Graphics