Arbres bsp
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 .
Call To Power 2 source sur Apolyton
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
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.