I. INTRODUCTION 

Le but de ce projet de fin d'étude 98 était de programmer un logiciel permettant à plusieurs utilisateurs de se promener et de communiquer dans une version virtuelle des bâtiments de l'ESSI. Pour ce faire nous avons découpé le développement de l'application en trois grande partie : 
• Le moteur 3D, qui s'occupe d'afficher à l'écran une vue subjective du bâtiment.
• La détection de collision. Une partie complexe qui permet de rendre un effet réaliste du déplacement des utilisateurs dans l'ESSI.
• La partie réseau, qui s'occupe de tout ce qui est communication des positions, actions et messages entre les différents utilisateurs.
Le langage utilisé pour programmer le logiciel est le C++. Il a été choisit car, étant un langage objet, il permet une maintenance et une organisation facile. De plus, il a permis de faire la fusion entre les différentes parties de manière efficace.

II. LE MOTEUR 3D 

Arbre BSP Optimisation Textures Interface Objets 

Un moteur 3D permet de visualiser des scènes en trois dimensions de manière réaliste. Dans notre cas les scènes sont définies par une suite de polygones (ou facettes) formant des objets en 3 dimensions. Pour avoir des performances optimums et une certaine portabilité nous avons utilisé la librairie openGL qui nous permet d'utiliser certaines cartes accélératrices 3D existantes sur différentes plateformes. Nous avons aussi utilisé le format de fichier BSP, créé par les programmeurs du logiciel QUAKE, qui nous fournit les données des différentes scènes sous forme d'arbre BSP ce qui permet un tri de facettes efficace. 

II.1. Les Arbres BSP 

Une des méthodes d'affichage, lorsque l'on affiche une vue de caméra dans un univers en trois dimensions défini par des polygones, consiste à commencer par afficher les facettes les plus éloignées jusqu'au facettes les plus proches de la caméra. Un des problèmes majeurs lorsque l'on programme un moteur 3D est le tri de ces facettes. Les arbres BSP offrent une solution efficace à ce problème. 

Comme son nom l'indique : un arbre BSP (Binary Space Partitionning) découpe l'espace en sections binaires. Ce partitionnement permet de positionner la caméra dans l'espace par rapport aux facettes et ainsi de savoir dans quel ordre les afficher. 

II.1.a Exemple Simple 

Prenons un exemple en deux dimensions : 

Dans cet exemple chaque noeud de l'arbre contient un segment qui correspondra à une facette verticale orientée par sa normale. L'espace (ici le plan) sera partitionné par la droite associée au segment courant. 

Pour créer un arbre BSP on commence par prendre le premier segment et le placer à la racine de l'arbre. Ensuite on insère dans l'arbre un noeud pour chaque segment de la scène. L'arbre étant binaire, chaque noeud a deux fils : un pour les segments se trouvant devant le segment courant et un autre pour les segments se trouvant derrière. 



Dans cet exemple les segments (B et D) se trouvant devant la facette A sont placés à sa droite dans l'arbre et les segments (C) se trouvant derrière sont placés à gauche. Nous pouvons aussi remarquer que le segment D se trouve à la fois devant et derrière le segment B. Le segment D est donc découpé en deux segments : D1 se trouvant devant B et D2 se trouvant derrière B. 

Ensuite pour afficher la scène on va parcourir l'arbre de manière récursive. Pour chaque noeud de l'arbre on va comparer la position de la caméra avec le segment courant : si la caméra est devant le segment associé au noeud courant on procédera à l'affichage des segments se trouvant derrière le segment courant en premier. Ensuite, on affichera ceux se trouvant devant. Si la caméra est derrière le segment courant on affiche d'abord les segments se trouvant devant, puis ceux se trouvant derrière. 

Dans notre exemple : 



La caméra est devant A on va donc afficher C, puis A, puis passer au noeud contenant B. La caméra se trouve devant B on va donc afficher D2, puis B et pour finir D1.

II.1.b Particularité du BSP utilisé 
Dans notre cas l'arbre BSP n'est pas exactement formé de la même manière. Au lieu d'avoir une facette par noeud toutes les facettes sont rangées dans les feuilles de l'arbre. Une feuille contient un groupe de facettes formant un polyhèdre convexe. C'est à dire que quelque soit l'ordre dans lequel on affiche les facettes d'une feuille il n'y aura jamais deux facettes se recouvrant. 

Chaque noeud contient un plan orienté qui servira au partitionnement de l'espace. Le parcours de l'arbre se fera à partir de ces plans orientés de la même manière que pour les segments de l'exemple précédent.

II.2. Optimisation 
Chaque scène peut contenir plusieurs milliers de facettes, ce qui implique que l'affichage de toutes ces facettes demande une forte capacité de calcul et peut provoquer une certaine lenteur pour une application demandant un affichage temps-réel. Plusieurs méthodes sont utilisées pour réduire le nombre de facettes à afficher. 

II.2.a Les listes de visibilité 

Une de ces méthodes consiste à rajouter une information sur les feuilles visibles à partir d'une autre. Dans chacune des feuilles de l'arbre on rajoute un tableau contant un indicateur sur la visibilité des autres feuilles lorsque la caméra se trouve dans la feuille courante. 

Dans cet exemple chaque salle du plan correspond a une feuille. Si nous nous trouvons dans la feuille 1 il est certain que quelque soit la direction où l'on regarde et quelque soit la position de la caméra nous ne pourrons voir la feuille 4. Donc la liste de visibilité de la feuille 1 sera 1,2,3. De même pour la feuilles 4 la liste de visibilité sera 2,3,4. Pour les feuilles 2 et 3 toutes les feuilles seront visibles. 

Pour des scènes de grande taille avec beaucoup de salles cette méthode peut réduire grandement le nombre de facettes à afficher.

II.2.b La pyramide de vue 
Une autre méthode pour réduire le nombre de facettes à afficher est d'utiliser la pyramide de vue de la caméra. Si une facette est hors de la pyramide de vue, il n'est pas nécessaire de l'afficher car elle sera hors de l'écran. En exploitant se fait, on peut inclure dans chaque noeud de l'arbre une définition d'une boite qui englobe toutes les facettes contenues par les feuilles que l'on peut atteindre à partir de ce noeud. Si la boite englobante est hors de la pyramide de vue alors il est inutile de continuer le parcours de l'arbre au niveau du noeud courant. 

Dans cet exemple la boite englobante (en pointillés) des feuilles 3,4 et 5 est hors de la pyramide de vue de la camera. Donc, les feuilles 3,4 et 5 ne seront pas affichées alors qu'elles font partie de la liste de visibilité de la feuille 1.

II.3. Les Textures 
L'affichage des différentes textures sur les facettes présente quelques particularités même si la librairie openGL facilite cette opération. 

II.3.a Les coordonnées de textures dans un fichier BSP 

D'ordinaire pour afficher une texture sur un polygone, on associe chaque sommet du polygone avec une coordonnée en deux dimensions, correspondant à une position dans la texture. L'inconvénient d'une telle méthode est qu'elle prend une certaine place. Les fichiers BSP, sans les informations sur les textures, étant déjà de taille conséquente, une autre méthode à été mise en oeuvre. Au lieu de stocker une coordonnée de texture pour chaque sommet d'une facette on stocke deux vecteurs (vS et vT) et deux distances (dS et dT) par facette. Ces données permettent de calculer pour chaque sommet d'une facette les coordonnées de texture qui lui sont associées. 

Ceci est fait en effectuant le produit scalaire entre les coordonnées du sommet avec vS (respectivement vT) et en ajoutant la distance dS (respectivement dT). Le résultat obtenu S (respectivement T) nous donne la coordonnée horizontale (respectivement verticale) sur la texture. 

S=Sommet.vS+dS 

T=Sommet.vT+dT

Cette méthode permet de réduire la taille d'un fichier BSP surtout pour les scènes ayant des facettes avec un grand nombre de sommets.
II.3.b Les Textures avec openGL 
L'application des textures sur des facettes avec openGL a causé quelque problèmes: 
• La librairie openGL nécessite des textures dont les dimensions sont de la forme 2^n x 2^n. C'est à dire que la largeur et la hauteur d'une texture doit être une puissance de 2. Hors les textures dans un fichier BSP ne sont pas réduite à cette contrainte (Elle doivent juste avoir des dimensions multiples de 8). Ceci a provoqué des problèmes lors de l'implémentation du moteur en openGL. Il a fallu modifier la taille des textures qui n'avaient pas des dimensions adaptées. Cela a été fait en rajoutant une bordure noire à la texture de manière à lui donner une bonne dimension.
• Dans un fichier BSP certaines textures sont composées de plusieurs parties. Pour les afficher correctement il faut prendre la partie droite de la texture et l'afficher en surimpression sur la partie gauche. Ceci implique deux applications de texture par facette. Plusieurs solutions s'offre à ce problème : Il est possible de créer deux textures à partie de la première ou de remplacer la texture par une autre. Pour des raisons d'efficacité la deuxième solution a été mise en oeuvre.
II.3.c Le MipMapping 
L'affichage des textures de manière ordinaire peut donner des images de mauvaise qualité à cause du problème de l'aliasing. C'est à dire que lorsque la facettes sur laquelle on applique une texture est éloignée de la caméra des effets indésirables, dus au sous-echantillonage de la texture, apparaissent. 

Dans l'exemple ci-dessus on peut remarquer que des détails de la textures disparaissent lorsque l'on réduit la texture sans se préoccuper de l'aliasing. Alors que le résultat avec anti-aliasing est bien meilleur. 

Plusieurs solutions d'anti-aliasing sont possibles pour résoudre ce problème: 

• On peut appliquer un filtre de lissage sur l'image calculée. Cette méthode est efficace mais est très lente et n'est pas adaptée si on n'a pas la matériel adéquat.
• Une autre solution est de fournir une série de textures plus petites que l'on affichera lorsque la facette est à une certaine distance de la caméra. Ces textures sont une version plus petite et lissée de la texture principale. Cette méthode, qui s'appelle le MipMapping , est utilisé dans les fichiers BSP qui contiennent les textures sous différentes tailles.
II.4. L'interface utilisateur 
Le programme se voulant être portable l'interface utilisateur a été réalisé grâce à une librairie complémentaire d'openGL : GLUT (GL utility tools). 

Cette librairie permet entre autre de gérer les périphériques du système utilisés par le programme. GLUT a été utilisé principalement pour gérer le clavier. Malheureusement GLUT n'est pas complète dans ce domaine et ne permet pas de détecter lorsqu'une touche a été relâchée. Elle se contente de générer un événement lorsqu'une touche a été enfoncée. Ceci a causé quelques problèmes lors du développement de l'interface et a bridé nos objectifs de développement du logiciel. 

Il aurait été possible d'utiliser une autre bibliothèque complémentaire d'openGL, appelée GLAUX, mais nous n'avions pas une version de la librairie permettant d'utiliser les possibilités des cartes 3D installées dans nos ordinateurs. 

Une autre solution aurait été d'utiliser des fonctions spécifiques au système. Mais ceci aurait limité la probabilité de notre programme et nous aurait fait dépasser le temps que nous avions pour développer le logiciel.

II.5 Les objets 
Pour avoir une représentation des autres utilisateurs connectés au réseau et donc présent dans la scène, il a fallu gérer l'affichage d'autres objets en 3 dimensions. 

Ces objets ne font pas partie de l'arbre BSP et donc les facettes qui les constituent ne sont pas triées à l'affichage. Ceci implique l'utilisation d'une autre méthode pour pouvoir afficher correctement ces objets à l'écran. Cette méthode est celle du Z-Buffer. 

Le Z-Buffer est un tableau dont chaque case correspond à un pixel de l'image. Dans chacune de ces cases se trouve la distance entre la facette affichée et la camera. Cette distance sera utilisée pour déterminer si un objet est visible ou pas. Lorsque l'on affiche la scène définie par l'arbre BSP on remplit chaque case du tableau par cette distance. Après avoir effectué cette opération, on affiche les facettes correspondant aux objets représentant les différents utilisateurs. Les pixels des facettes de ces objets ne seront pas affichés à l'écran si la distance entre eux et la caméra est plus grande que celle déjà placée dans le Z-Buffer. Cette opération est effectuée de manière efficace par openGL, pour peu que l'on ait une carte accélératrice 3D.

III. Détection de Collision. 

Première approche Solution Adoptée 

La détection de collision va nous permettre de détecter toutes collisions entre l'utilisateur et les murs ou le sol. Cela nous permettra en outre de pouvoir monter des escaliers ( ou de les descendre) et de ne pas traverser les murs.

III. 1. Première approche. 
Au tout départ, la détection de collision devait utiliser au mieux la structure des arbres BSP et des feuilles de l'arbre pour une optimisation maximum. Un algorithme de détection de collision a donc été développé dans cette optique là. 

Le principe consistait à dire que nous nous trouvions dans une feuille, ce qui est pour le moins évident puisque où que nous nous trouvions dans le niveau notre position correspondait à l'emplacement d'une feuille dans l'arbre. Ainsi on pouvait tester toutes collisions éventuelles avec l'une des faces qui se trouvait dans cette feuille. 

Ensuite si l'on pouvait sortir de cette feuille, on cherchait la feuille dans laquelle on devait se trouver après l'éventuel déplacement et on effectuait les mêmes tests sur cette nouvelle feuille. 



Le premier problème survenu est que certaines feuilles représentent un volume spatial si petit que celles-ci n'étaient pas testées. On pouvait donc passer à travers certains murs qui semblait ne pas exister!!! 



Le deuxième problème était encore bien plus ennuyeux puisqu'il s'agissait de détecter la présence ou non d'un sol sous nos pieds. A priori rien de bien complexe. Il suffisait de tester les faces de la feuille où l'on se trouvait qui possède une normale en z ( i.e. vers le haut). La surprise que nous réservait le BSP était que certaines feuilles sont coupées horizontalement, surtout lorsqu'on s'approchait des marches, ce qui devenait encore plus problématique pour gérer la montée des marches. En effet, le test pour trouver dans quelle feuille l'on se trouvait s'effectuait au niveau de la caméra. On se retrouvait donc dans certaines feuilles sans sol ni plafond.... 



Les tests ont encore continués pour trouver une méthode s'adaptant à ces problèmes. Mais de nouveaux problèmes sont alors apparus toujours dus à la spécificité du BSP et à la façon dont il est construit. 

Il s'est donc avéré que le peu de connaissance que nous avions au sujet de la construction de l'arbre par rapport à la modélisation de l'ESSI, le peu de documents disponibles quant à cette même construction et à la façon dont la détection de collision est effectuée ne permettait pas d'utiliser cette méthode là de manière efficace.

III. 2. Solution Adoptée. 
La solution finalement adoptée est bien plus générale que la précédente pour assurer la détection de collision. 

On possède une liste de pointeurs sur des feuilles. En fait toutes les feuilles de chaque niveau sont ici représentées. Dans chaque feuille toutes les faces sont représentées par leur boite englobante (ou bouding box) et leur normale. Chaque feuille est elle aussi représentée par sa boite englobante générale ainsi que toutes ses faces. 

On procède ensuite à un choix parmi toutes les feuilles, i.e. que l'on cherche toutes les feuilles dont la bounding box rentre en collision avec la bounding box de la caméra. On obtient ainsi toutes les feuilles qui sont proches de la position de la caméra et donc, toutes les faces qui en sont proches!!!!

On procède ensuite à un test qui nous permet de savoir si le mouvement effectué doit traverser une face pour être effectivement appliqué. Ainsi on pourra réduire le mouvement latéral (en x ou en y) selon la nature de la face rencontrée. Pour la détection du sol on utilisera le même système en sachant que l'on veut rester à une certaine distance du sol lors de nos déplacements. 

On effectuera ces tests dans l'ordre indiqué au dessus, i.e. que les déplacements latéraux (en x et y) seront calculés en premier pour pouvoir mettre à jour la hauteur z à laquelle on se trouve après ce déplacement s'il est réussi. 

En outre, un test de gravité a lieu. C'est à dire que si aucune face n'est trouvée juste en dessous de la personne il tombera jusqu'à la prochaine face. On attendra alors que l'utilisateur fasse à nouveau un mouvement.

VI. IMPLÉMENTATION RÉSEAU 

Objectifs. Réalisation. Améliorations. 

VI.1 Objectifs.

Cette partie du projet devait permettre à plusieurs utilisateurs distants physiquement mais ayant un accès à Internet et ayant le programme exécutable installé sur leur machine de se rencontrer et d'interagir de façon fluide en direct dans un lieu virtuel. 
Pour un maximum de réalisme, l'aspect réseau de ce projet devait présenter les caractéristiques suivantes: 
•  Accepter un grand nombre de participants, même au cours d'une session préexistante.
•  Permettre un temps de latence court, quelque soit la localisation physique des participants i.e. : un temps de réponse rapide permettant une forte interactivité.
•  Selon le degré de réalisme souhaité, gérer la synchronisation des clients c.a.d si 2 actions sont effectuées simultanément, les faire apparaître comme simultanées malgré un temps de trajet des paquets réseau plus long de la part d'un des participant.
•  Ne pas encombrer le réseau / effectuer un partage de charge.
Deux techniques différentes permettaient la réalisation de cette partie. D'un coté, une technique basée sur une diffusion unicast c.a.d d'un client vers un et un seul autre, s'appuyant sur les protocoles TCP(Transport Control Protocol) ou UDP(User Datagram Protocol). D'un autre coté, une technique dite broadcast ou multicast permettant la diffusion d'un client vers plusieurs autres. Le tableau ci-dessous présente les différences majeures entre ces  approches. 
 

Les différentes approches étaient envisageables. 

Approche unicast Client/Serveur :

Un client  envoie son message au serveur qui s'occupe de le redistribuer aux destinataires. Pour un message, et N destinataires, le client envoie 1 paquet, et le serveur retransmet N paquets. 

Cela permet une synchronisation des utilisateurs, un contrôle de flux et un contrôle des données. 
Inconvénients : le serveur est un goulot d'étranglement. Coût élevé d'une communication d'un client à un autre client. 

Une autre approche Unicast:

Un client diffuse successivement à tous les clients. Pour 1 message, et N clients, il envoie N paquets. 

L'approche unicast nécessite d'envoyer autant de messages qu'il existe de processus destination, ce qui peut entraîner une surcharge importante du réseau et donc un temps de latence élevé. 

Approche multicast ou broadcast:

Un client diffuse à tous les clients, tel un émetteur radio. Pour 1 message et N clients, il envoie 1 Paquet. 

L'avantage majeur d'une approche Broadcast/Multicast réside dans le fait que dans ce cas, le nombre de paquets émis est extrêmement réduit, et donc plus efficace. 
Bien sûr, toute solution hybride était également possible, et c'est d'ailleurs ce type de solution, associant une connexion unicast TCP et une connexion Multicast que nous avons utilisé. 
 

VI.2. Réalisation.

L'implémentation de cette partie, comme le reste du projet a été réalisée en C++, de façon à favoriser une approche objet du problème. Bien que la version présentée du projet soit disponible uniquement sous Windows pour des raisons matérielles, la partie réseau a été développée de façon la plus portable possible et une grande partie du code à été développé aussi bien pour les architectures UNIX (Solaris/Linux) que Windows(NT/95). 
Les différentes classes réalisées sont: 
• Socket, une classe encapsulant les appels réseaux et gérant les protocoles TCP unicast, UDP unicast, UDP broadcast, UDP multicast et offrant une interface unifiée que ce soit sous UNIX ou sous Windows.
• Id et IdServer, deux  classes permettant l'identification des participants de façon unique grâce à la mise en place d'un serveur TCP.
• Messages, une classe de données encapsulant les données transitant sur le réseau et permettant d'identifier son correspondant et mettant en place un mécanisme simple de détection de perte de paquets.
• Actor, une classe représentant en mémoire les personnages présents dans une partie et offrant des méthodes permettant  la diffusion des  infos concernant les joueurs sur le réseau.
• Actuator, une classe , qui associée aux classes Socket et Messages permet d'implémenter un mécanisme simple d'invocation de méthodes à distance.
• Mutex, une classe encapsulant le système de sémaphore d'exclusion mutuelle utilisé en conjonction avec les thread (Windows uniquement).
• List et FIFO, une implémentation générique(template) minimale de liste et de files FIFO.
Notre projet, tel qu'il fonctionne actuellement utilise a la fois un protocole de diffusion multicast et un protocole de diffusion unicast TCP.  Le schéma suivant permet d'avoir une vue d'ensemble de l'architecture réseau utilisée: 

Pour pouvoir converser entre eux, les différents clients doivent pouvoir être identifiés de façon unique. L'IDServer est une mini base de donnée des identifiants disponibles. Lors de son lancement, le client émet une requête vers l'IDServer, afin d'obtenir un identifiant unique. Une fois celui ci obtenu, le client peut émettre sur le canal multicast sans risque de se voir confondre avec un autre client. Lors de sa déconnection, le client doit indiquer à l'IDServer qu'il quitte la partie et que par conséquent son identifiant pourra par la suite être utilisé par un autre client. 

Durant la période de communication "normale" du client, c.a.d après son initialisation et son identification, plusieurs threads ayant chacun un rôle spécifique sont lancés. 
Nos quatre threads s'occupent de: 

• L'émission des données concernant le client
• La réception des informations en provenance des autres clients.
• L'émission périodique de données complètes décrivant le joueur.
• La destruction des informations concernant les clients inactifs.

L'émission des données concernant le client

Dans cette partie, seules les informations minimales sont envoyées. Les données traitées concernent principalement les déplacements. A chaque déplacement du personnage, un paquet réduit dont le corps représente une action telle que avancer, reculer, tourner à gauche ou tourner à droite, est envoyé. 

La réception des informations en provenance des autres clients.

Le client récupère dans cette partie les informations en provenance des autres clients et met à jour une base de données représentant l'état global du système. 

L'émission périodique de données complètes décrivant le joueur.

En utilisant le protocole UDP Multicast, on s'expose à une perte de paquets possible. Pour pallier ce problème, on envoie de façon régulière un paquet d'information spécial dit Heartbeat décrivant de façon complète l'état du client. Ce paquet permet de remettre à jour l'état global du système pour les clients qui auraient perdus des informations. 

La destruction des informations concernant les clients inactifs.

On a vu ci dessus que chaque client envoit de façon régulière des informations. Si, au bout d'un temps donné, on constate qu'on ne reçoit plus d'informations en provenance d'un client, on considère que celui ci s'est déconnecté. Toutes les informations le concernant sont alors supprimées. 

VI.3 Améliorations.

Plusieurs améliorations importantes peuvent être apportées en ce qui concerne la synchronisation des personnages. Mais l'amélioration la plus fondamentale semble être la réduction du nombre de paquets émis sur le réseau. En effet, il était initialement prévu qu'un paquet serait émis lorsqu'un utilisateur appuierait sur une touche, indiquant le début d'une action, ainsi que lorsqu'il relâcherait cette touche lors de la fin de  cette action. Toutes les positions intermédiaires devaient être interpolées. 
Cependant, le système de gestion du clavier utilisé (GLUT) ne permet pas de différencier l'enfoncement d'une touche du relâchement de cette touche. C'est pourquoi une autre méthode a été utilisée. Tant que l'utilisateur effectue une action (avance par exemple), un flux continu de paquets est émis indiquant l'action courante. 
En fait, pour pouvoir réaliser la méthode présentée précédemment, il serait nécessaire d'utiliser des primitives propres au système d'exploitation utilisé (ici Windows). On perdrait alors en portabilité, mais on gagnerait en efficacité.

V. CONCLUSION 

Malgré l'utilisation de méthodes d'optimisations pour l'affichage des facettes, expliquées dans la section sur le Moteur3D , la complexité du modèle de l'ESSI utilisé a bridée les performances concernant la rapidité de l'affichage. Ce ralentissement est perceptible lorsque que l'utilisateur se trouve dans une salle contenant un grand nombre de facettes ou dans une salle ayant un connexion directe avec une de ces salles. Par exemple, les salles contenant les ordinateurs et le couloir menant à ces salles. 

Au niveau de la détection de collision, le sujet était plus qu'intéressant. On regrettera l'absence de documentations à propos de ce sujet. Mais de ce fait la création des algorithmes de détection en était d'autant plus intéressante. 

L'utilisation de cartes 3DFX sous Windows nous a permis d'expérimenter un environnement hard/soft inhabituel à l'ESSI. Ceci était particulièrement intéressant. 

On pourra regretter la mauvaise configuration des machines HP, qui nous aura fait perdre un temps non négligeable et nous aura empêché de développer le programme sur cette plateforme comme cela était initialement prévu.

VI. RÉFÉRENCES 

• OpenGL Programming Guide
• Mimaze the multicast internet maze 
• An Introduction Tutorial for Developing Multi  User Virtual Environments