1.Sujet du projet n.2 - 96/97

Le but de ce projet etait d'etudier les arbres BSP (Binary Space Partitionning ( tree )). Pour cela, il fallait cree un logiciel permettant de lire un fichier contenant un arbre BSP et de l'afficher. Le format choisit pour cette etude a ete le format .bsp du logiciel QUAKE d' Id Software. Mais avant toute chose il fallait comprendre ce qu'etait un fichier BSP.

Retour sommaire

2.C'est quoi un BSP tree?

Comme son nom l'indique, un BSP tree permet de separer un espace en section binaire. Chaque noeud de l'arbre contient une face, qui coupe l'espace en deux partie distinctes selon le plan qui lui est associe. Un noeud contient aussi 2 fils : un representant l'espace devant le plan de coupe et l'autre representant l'espace derriere ce meme plan. Si une face est coupee par le plan de coupe on la scinde en deux parties, une devant le plan et l'autre derriere. Cette representation est utilisee dans different domaines dont la synthese d'images en 3 dimensions . On utilise un arbre BSP dans la synthese d'image 3D pour faciliter l'affichage des differents polygones. L'un des grands problemes de la synthese d'images est de trier efficacement les polygones a afficher pour que ceux qui sont derrieres soient affiches avant ceux qui sont devant, les arbres BSP sont une solution efficace a ce probleme.

Voici un petit exemple de construction d'arbre BSP.



A gauche se trouve l'arbre et a droite les differents segments. On commence par cree un neoud racine avec le premier segment A. Ensuite, on place tous les segments devant A (B) a gauche du noeud contenant A et tous les segments derriere A (C) a droite du noeud. Si un segment est a la fois devant et derriere A (D) on le coupe en deux (D1 et D2) et on place les nouveaux segments dans l'arbre.

Retour sommaire

3.Le BSP dans Quake

L'arbre BSP est utilise de maniere legerement differente dans Quake.Chaque noeud contient un plan de coupe mais ne contient pas de face. Les faces se trouvent groupees dans les feuilles de l'arbre. Chaque groupe de faces dans une feuille est tel que toute les faces ne peuvent se couper entre elles (polygone convexe), se qui implique que l'on peut afficher les faces d'une feuille sans se soucier de l'ordre dans lequel on le fait. Chaque noeud contient aussi une "bouding box" qui encadre tout ses fils, ce qui nous permet de tester facilement si un noeud (et tous ses fils) se trouve dans la pyramide de vue et donc d'eliminer rapidement un grande partie de l'arbre. De plus, une feuille contient une liste qui nous indique quelles autres feuilles sont visibles a partir de la feuille courante. Cette liste facilite encore une fois le clipping des parties invisibles. Un fichier .BSP utilise par QUAKE contient aussi d'autres informations importantes pour le decor telles que les textures et leur orientation et les objets mobiles represente par d'autres arbres BSP independants.

Retour sommaire

4.Le developpement du logiciel

Une premiere difficulte rencontree lors du developpement du lecteur de .BSP est que les .BSP sont fait a l'origine sur des ordinateurs a base de processeur intel (des PC quoi) se qui implique que les donnees qui ont une taille d'un mot ont leur partie basse avant leur partie haute, de meme pour les donnees de taille double mot. Il a donc fallu ecrire une serie de fonctions qui lisent les fichiers PC et les transcrivent en format SUN.

Une fois cette etape franchie, il a fallu decortiquer la specification des fichier .BSP et retirer les informations pertinentes : Le coordonees des points, les aretes, les faces, l'arbre BSP, les textures.

Ensuite , nous sommes passe a l'adaptation de notre logiciel graphique VISU, elabore lors du cours de synthese d'images avec Michel Buffa (voir Listing en annexe).

Finalement nous sommes arrive a deux version du logiciel :

La premiere affiche le niveaux en fils de fer et en faces pleines en niveau de gris. Cette version est la plus rapide et permet de visualiser facilement le fichier .BSP

La deuxieme (qui n'est pas aboutie) aurait du permettre de visualise le fichier .BSP en fils de fer , en faces pleine et aussi avec les textures qui ont ete applique aux faces.

La structure du programme ressemble a ceci :



Main.c contient les fonctions de chargement et initialisation du programme. Graphics.c est le module principal ou se trouvent la fonction de gestion de la fenetre graphique et la fonction de gestion de l'interface. Camera.c (En fait s'apelle object.c) contient la definition de l'objet camera. Matrix.c contient un bibliotheque qui permetg d'utilise un type matrice et un type coordonne 3D. BspPrint.c est le module qui gere l'affichage d'un arbre BSP avec le cliping et le reste. Bspobject.c contient la definition d'un arbre BSP et les fonctions permettant de le cree a partir d'un fichier .BSP de Quake. Finalement, Pcio.h contient des fonctions lisant un mot,un double mot et un reel sur d'un fichier provenant d'un PC.

Retour sommaire

5.Apport du projet et developpements ulterieurs

Ce projet nous a permis principalement de comprendre ce qu'est un arbre BSP et comment ont peut l'utiliser pour la synthese d'images en 3D. De plus, nous avons pus voir comment etait fait un logiciel de qualite tel que QUAKE. Finalement , nous avons pus ameliore notre methode lors de la programmation de logiciel de grande taille a plusieurs (seprations des taches dans le programme et entre binomes etc..).

Si le temps et le courage sont present il serait interessant de continuer le programme en ajoutant les caracteristiques suivantes : Ajout de la texture au moteur 3D, utilisation d'une technique permettant un affichage encore plus rapide (Span or Edge sorting), Gestion de entites mobiles, etc...

Retour sommaire

6.Telechargement et mode d'emploi

Vous pouvez telecharger les sources et le programme sous forme d'un ficher tar ici -> bsp.tar

Pour utiliser le programme tapez sur la ligne de commande : visu -obj filename.bsp

Apres un court instant, le programme affichera le niveau correspondant au fichier .bsp. Pour selection sa direction il faut appuyer sur le bouton du centre et bouger la souris. Pour avancer il faut appuyer sur le bouton de droite de la souris. Pour afficher le niveau en fil de fer il faut appuyer sur la touche 'L' du clavier. Pour afficher le niveau en face pleine il faut appuyer sur le touche 'F' du clavier. Enfin, pour quitter le programme il faut appuyer sur la touche 'Q' du clavier.

Retour sommaire

7.Les Cliches

Voici quelques cliches du programme lisant le niveau du groupe qui etait en charge de modeliser l'ESSI. Vous pouvez d'ailleurs, aller vers leur page.



Les escaliers du hall pour monter vers les salles du niveau audessus.



Le couloir pour aller dans les salles machines.



Une des salles.

Retour sommaire