Arbres bsp

Soyez le premier à donner votre avis sur cette source.

Snippet vu 9 921 fois - Téléchargée 31 fois

Contenu du snippet

Ce tutoriel prétend aider à la compréhension des BSDP trees utilisés pour la conception d'objets et de niveaux dans les doom-likes comme quake ou duke-nukem .

Source / Exemple :


Les arbres BSP
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

1.Intro

Mettre au point un jeu n'est pas les simple fait  de superposer des polygonesdans 

une ligne vertexielle  . l'utilisation de l'algo , des collisions et bien 

d'autres problèmes auxquels il faut faire face... pfffuuu :-|| en vue d'une 

execution rapide du code.

2. Théorie

Les arbres BSP représentent une région dans l'espace. Un arbre est composé de 

noeuds qui possèdent en tout et pour tout deux childs ( enfants) et de feuilles 

(noeuds terminaux sans child). Un noeud équivaut à un partitionnement de 

l'espace. Le partitionnement génère deux  espaces neutres , un au devant dit 

framed ( il est visible )  et un en arrière du noeud dit hidden ( caché ).
  
2-1 Pour une application 2D :

Dans Doom on utilise un  BSPtree pour réprésenter le monde dans lequel évolue le 

perso principal. Dans ce cas ,l'arbre entier représente le monde 2D. Le noeud 

principal génère le partitionnement du monde en deux espaces sur la base d' 

équations conditionnelles. le premier espace ( disons niveau ) est devant la 

ligne donc visible et le second est derrière la ligne ( donc caché ). Chaque 

niveau équivaut à un sous-arbre, qui est lui aussi un arbre BSP. Logique , 

nest-ce pas ? :) 
Chaque noeud englobe un segment de ligne généré by le partitionnement. Le segment 

de ligne renferme toutes les informations telles que l'architecture , la hauteur 

ou l'ID ( très important dans un arbre , sinon après on se melange ) de la 

texture . Il peut etre utilisé comme un mur dans le monde ( un mur est une unité 

parcellaire qui sert à spécifier l'ID de chaque monde ). Les sous-arbres sont ici 

des feuilles à la seule condition que l'espace qu'ils représentent ne contient 

pas d'autres murs à l'intérieur( sinon ça donne deux ID pour un meme monde 

:°)).Mais l'avantage de cette double partition est que  le mur sera utilisé pour 

partitionner de nouveau l'espace( mais cette technique est peu recommandée aux 

débutants , car la logique est très barbare, meme si elle à servi à la 

réalisation de l'excellent Myst.)

2-2 Pour une application 3D :

Pourdes applications 3D, c'est un peu la meme chose . A la seule entrave que 

l'espace est partitionné avec des plans 3D.

3- Différents types de BSPT :

Il existe deux principales méthodesde conception d'arbres BSP. 

3-1 Les node-based BSP trees:
Les noeuds englobent l'ensemble des polygones et des plans utilisés pour le 

partitionnement. 
Les feuilles sont vides si vous utilisez cette méthode(en général , seuls les 

niveaux multiples de mortal kombat et de Dead or Alive possèdent des noeuds 

pleins encore appelés threadnodes! :o§)

3-2 Lesleafy BSP trees:
Les noeuds englobent uniquement les plans du partitionnement. 
Les feuilles contiennent tous les polygones qui composent le monde 2d OU 3D. 
Les arbres BSP sont le plus souvent utilisés lorsque l'on a affaire à des 

polygones-mères utilisés pour la construction d'un arbre symbolisant 

graphiquement une représentation limitée d'un objet. Ledit objet est intérirement 

fait à base de solide, et extérieurement entouré de vide, les polygones elles 

représentent la limite frontale entre ces deux espaces.
 
L'arbre achevé tout devient plus facile , chaque feuille symbolise soit de 

l'espace solide, soit du vide.

4. Construire un arbre BSP

L'algo mis en place pour strucuturer un node-based BSP tree est  très simple. Ce 

algo est très approprié pour des mondes statiques( c'est-a-dire avec des niveaux 

prédéfinis et liés entre eux ), utilisés en général dans les jeux d'action 3D 

.C'est le cas d' un certain Quake qui est strucuturé en un arbre BSP statique qui 

représente tout simplement un monde et tout une partitons d'objets faciles à 

concevoir  (vies,armes, ammunitions, objets, ennemis, portes, bonus et bien 

d'autres...) qui peuvent bouger( changer de point d'initialisation , se déplacer, 

touner en boucles, etc...) à travers tout le monde spécifique.

....:Passons à la construction de l'arbre en lui-meme:.... 

Le code suivant est la transcription codale codale ou si vous voulez le 

pseudo-code de l'explication littérale ci-dessus. 	
Relisez ce code des dizaines et des zidanes de fois . :}=

Si vous avez pigé ça , alors vous avez tout pigé , ok?! :s)

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)

Une fois la logique maitrisée. Passons a la structuration d'un arbre 2D  composé 

d'un espace dans lequel on définit une région fermée (composée de polygones, pour 

faire plus simple) doté d'un intérieur solide. Ladite région est donc logiquement 

entourée d'espace ........................? (hint = vide, bien sur)
Prenons le cas d'une région solide délimitée zone par zone par 4 polygones A, B, 

C et D. 
Ou nous représentons 4 polygones sur la gauche et une zone quiaffiche les 

identifiants de ces polygones sur la droite (A,B,C et D dans l'ordre vertical, 

pour faire plus simple , ;). 
Pour chaque  segment équivaut une logique de visibilité dirigée outover  la 

région solide .

Application
1- Créons un noeud principal, à l'aide de Marie J-Blidge ? , mais non, d'un 

segment A qui sera visible bien sur.:(0)ahahahahoha... 
2 - Traçons une ligne intermédiaire applée surA  qui parcourt le segment A. Les 

segments B, C et D sont bien evidemment  derrière la ligne rose et bien sur 

cachés par rapport à celle ci.
Cela veut dire en langage simpson que le joueur se trouve actuellement au niveau 

1 de Duke Nukem checks Jessica Marquez down with a bombcannonX et que ce dernier 

n'a pas accès au niveau tant qu'il est dans le niveau ( je detaillerai les 

conditions des branches d'accès dans un autre tutorial, vous verrez , c'est 

simple !).
Placons  trois segment dans la liste des faces B, C et D arrières.
On remarque que la face avant devient vide  vide puisqu'il n'y a aucun polygones 

devant le segment A. La liste vide est alors représentée par le child ( l'enfant 

visible ) du noeud principal, d'une feuille d'espace vide. 
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( explication pédagogique ). 
Le partitionnement de l'enfant caché du noeud principal se fait alors automat , 

mais vous pouvez le faire manuellement si vous etes de l'ULM ! ...Mais qu'est-ce 

que je raconte moi??? ?:}?  
Servons-nous à présent du segment B , pour la mem opération .
Dans des jeux comme Duke Nukem ou Quake , Unreal , l ' hypothétique segment B , 

ne serait pas choisit , mais à titre d'exemple , il serait impossible de se 

servir d'un segment Dc parcellé , réservé au haut niveau et long à détailler dans 

un simple tutoriel de quelques ko .
Le segment Dc sert notamment à la sursaturation des frames dans une méthode de 

modulage et qu'il sert principalement à la création de la partie inter-treminaux 

du jeu ( très complexe pour devoir le détailler dans un premier cours ).
	
Donc si vous avez bien effectuer l'opération observez la ligne rose pour le 

segment B. Elle n'entre pas et n'entrera en aucune façon que ce soit dans 

l'espace avant du segment A de la premiere opération.
Ceci est simplement du au fait que la partition initiale se fait derrière le 

segment A ( mais les programmeurs de Lara Croft Tomb Raider 3  ont réussit à 

contourner le problème, d'ou les nombreux bugs. Ce n'est pas très conseillé ) , 

incroyable , non ? )
Toutes ces applications sur le passage des objets derrière , dans ou devant le 

segment ne sont pas fait juste pour vous faire passer le tepms .
C'est une opération essentielle si vous voulez vraiment saisir le fonctionnement 

interne des arbres BSP.Mais faite une pause de temps en temps , sinon continuons 

si vous voulez etre de vrais Jedi.:§=}

Essayons maintenant de partionnerle devant du noeud (le duo  C et Dv). utilisons 

Dv comme segment de partitionnement. 
C est l'unique polygone à classifier et il se trouve derrière le segment 

Dv(disons Dv ownChildLast ( Dv pourqi*uoi est-tu si complexe ? ). La liste de 

devant etant vide vide créeons une feuille représentant un espace vide . 

 
Il ne reste plus que deux noeuds à traiter, C et Dc. Nous pouvons effectuer les 

deux opérations en une seule étape, car l'avantage dans un programme aussi simple 

que le notre les deux segments n'ont aucuns polygones à classifier.
1- Attribuons leur tout d'abord deux noeuds qui seront tout simplement des 

feuilles , car vous l'aurez compris , il faut etre sur mars pour voir un noeud 

child enfanter d'un noeud principal §§:! : 
2 - Utilisons une feuille pour représenter la partie solide derrière le polygone 

(signe plus) et une seconde feuille pour représenter l'espace vide devant le 

polygone (signe moins). 
Le résultat  obtenu est l'arbre BSP final ( ouuuuuuuf ).
 
Tout est bien qui finit bien...........................................
 , mais non , Chuck Norris a faillit me deboiter la tete , il n'en a pas eu pour 

son argent :
Eh oui, je rigole , je rigole , mais le gros problème qui se pose est le fait de 

choisir les polygones pour partitionner l'espace du monde en sous-espaces. 
Comment faire ?
Eh bien soit on  choisit le polygone qui cause le moins de parcelisation ( 

éclatements segmentaires)  de segments ( et on se retrouve avec des niveaux 

limités), ou alors on choisit le polygone qui fait le plus d'éclatements( là , 

les mondes et les sous moins sont infiniments plus abutis ) mais hélas le nombre 

important de données générées dans l'arbre devient un problème très récurrant  

surtout au sommet de l'arbre.

5. L' Applet de Paton J.Lewis

 Paton J.Lewis est le developpeur de l'applet du meme nom . Il se sert notamment 

du node-based BSP trees pour des mondes 2D.
Lorsque vous jouez un Doom ou un Resident Evil , vous voyez la carte qui se 

trouve sur un coin en heut de l'écran pour vous permettre de vous diriger? Eh 

bien , c'est grace à cet applet que l'on a accès à cette fonction.
La carte de laquelle on se sert pour se répérer est en meme temps interactive 

avec avec le niveau dans lequel le personnage évolue.
Il faut notamment se servir de la souris pour lier et partitionner les arbres de 

l'applet.
 

6. Algorithmes et arbres BSP

Choisir un algorithme dépend de la forme  que l'on veut assigner au BSP
Elimination de facettes ,détection de collision,ajout alléatoire de personnages 

c'est à vous de voir, mais en tout cas l'algorithme n'est pas le meme.

 Les plus utilisés par les developpeurs sont le tri ordonné des polygones, le 

test de position d'un point et le test des segments de droite.

6.1. Le tri ordonné des polygones
Le BSP a pour role premier de trier des polygones par rapport à un point de vue 

donné. 
Les z-buffers fonctionnent  les faces polygonales très rapidement,et le tri est 

plus aisé.Les polygones sont donc déssinées  de l'avant vers l'arrière , bonne 

chose , car tous les polygones ne sont pas dessinés Toutefois, les polygones qui 

se voient appliqués  une couche de transparence dite couche Alpha ,doivent  être 

rendus du fond vers l'avant si'il faut avoir un rendu à la limite du respectable.
Ce algo revet une logique logique :) 
:Si vous disposez d' 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 

effacer ou s'imposer sur tout objet ou polygone 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".
Ci-dessous , vous trouverez un exemple de 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
           //l'ordre importe peu 
           front.GetSortedPolyList(pList, camera);
           back.GetSortedPolyList(pList, camera);
   }
}

void leaf::GetSortedPolyList( list<polygon3>*pList, point& camera)
{
   return;
}

6.2. Le test de position d'un point

Tester la position d'un point dans un monde est également une fonction d'un BSP 

Tree. 
A partir d'un point donné et/ou d'un arbre, il est facile de spécifier si un 

point est situé dans une région vide ou dans une region solide (Ce point est 

représenté dans l'arbre par une feuille vide ou solide).
Méthode le plus souvent utilisé pour la détection des collisionsle plus souvent 

pour la détection de collision.
L'algo généré cela est fastoche . 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). Par contre 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 .C'est 

très simple très logique et vous avez lz choix de variez la structure des niveaux 

comme bon vous semble . 
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  solide, alors le point est situé dans une région pleine , 

résultat = il y a collision. 
Si la feuille est  vide, alors le point est situé dans une région non pleine , 

logiquement il n'y a donc pas de................. ({hint [[collision)] hint ) , 

collision , bien sur .

 le pseudo code correspondant à l'algotesteUr de 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
           // initialisation de l'arbre arrière
           return back.TestPoint(pt);
   }
}

bool leaf::TestPoint(point& pt)
{
   if (solid)
       return true;
   return false;
}

6.3. Le test des segments de droite

Cet algo  retourne "vrai" s'il existe un segment de droite non coupé entre deux 

points qui sont les extrémités du segment. Sinon, il retourne "faux". 
Une autre méthode permet de dire que l'algorithme retourne "vrai" si et seulement 

si le segment de droite est child donc appartient à 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".Et vous etes un pro et à vous le nouveau 

QuakeBlasterNukemGeoMystWekillbabelander...
:} Bon courage !
Ecrivez-moi et faites attention au powerkick de Chuck Norris the best !

Salut, nooounouuuuu ! d:0) animaniacs imitation !

Conclusion :


Call To Power 2 source sur Apolyton

A voir également

Ajouter un commentaire Commentaires
Messages postés
32
Date d'inscription
lundi 6 novembre 2000
Statut
Membre
Dernière intervention
20 septembre 2006

sorry, je parlais bien entendu de la ligne 168.
Messages postés
32
Date d'inscription
lundi 6 novembre 2000
Statut
Membre
Dernière intervention
20 septembre 2006

bonjour,
je dois comprendre tout ce charabia pour l'école.

mon esprit s'est arrêté à la ligne 68 quand tu dis de réaliser un make_leaf sur frontlist... alors que makeleaf demandais un bool en param...
tu devrais écrire makenode à cet endroit là pour générer les découpages internes à la frontlist.
De plus, qd j'ai vu qu'on traitait la frontlist indépendamment, j'ai évidemment regarder plus bas au sujet de l'autre éventuelle liste, et c'est bien ce que tu réalises sur la backlist.

Donc assurément, une erreur involontaire s'est glissée sur cette ligne 68 ;)
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

je me suis arrêté de lire à l'endroit où tu as tappé le code justement, j'aurais bien aimé des commentaires à côté de celui-ci, je sais que tu considères que tout ce qui précède est le commentaire mais c'est pas easy.

quoiqu'il en soit, je te félicite pour cette article, (que je n'ai pas lu en entier), c'est assez clair, les mots sont assez souvent les bons ^^ c'est pas pleins de fautes qui piquent aux yeux. J'avais lu récemment un article sur les BSD Trees, en anglais, et ils pointaient vers cette page:

http://symbolcraft.com/graphics/bsp/bsptreedemo_french.html

une applet java extraordinaire ^^ amusez-vous à dessiner des murs dans la zone de dessin et à vous déplacer dans la zone, à tourner sur vous même, tout est géré et l'arbre est représenté dichotomiquement.
Messages postés
368
Date d'inscription
mercredi 14 novembre 2001
Statut
Membre
Dernière intervention
1 septembre 2008

Un peu compliqué, il manque du code, mais c'est bien le seul tutorial digne de ce nom que j'ai trouvé en francais.

Un grand bravo. Faudrai juste que tu mettes un zip avec des exemples.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.