Home

Rapport - Département Informatique

1. des carr s sinon on va trop afficher trop de rectangles inutiles e Illustration avec des carr s pour chaque carr on peut au pire en afficher un seul qu on ne voit pas Avec des rectangles quelconques il peut y en avoir plus Dans notre programme avec les quadirees on a un rectangle initial de c t s X Z Pour pouvoir utiliser cette m thode il vaut donc mieux avoir un carr initial de c t max X Z quitte avoir des carr s vides Cette optimisation n est pas possible quand on consid re les rectangles comme des colonnes voir ci dessus la 2e m thode de test de frustum dont la taille en Y est bien sup rieure celle en X et Z Quadtrees dynamiques Parfois les mondes en 3D sont tellement grands plusieurs centaines de Mo voire plusieurs Go qu on ne peut pas les charger enti rement en m moire On ne peut donc pas construire un quadtree contenant tous les polygones d s le d but de l ex cution Dans ces cas l le programme lit sur le disque les informations sur le monde en 3D en fonction de la position de la cam ra dans ce monde et modifie le quadtree en fonction de ce qu il a lu Conclusion Les quaditrees sont une structure de donn es assez simple qui permet de d couper l espace en rectangles L algorithme ne comporte pas de grosses difficult s impl menter mais n est vraiment efficace que dans des cas pr cis Par exemple il est optimal quand la cam ra a une orientation fixe et qu on est dan
2. l tape 2 sinon la sph re n est pas en collision avec le polygone o Etape 2 Trouver le point d intersection entre la sph re et le plan du polygone Si on est ici on peut affirmer qu il y a intersection entre la sph re et non pas le polygone mais le plan du polygone L objectif est donc de savoir si le point d intersection est l int rieur du polygone ou l ext rieur Pour cela on va utiliser la fonction bool nsidePolygon qui prend le point d intersection et le triangle et qui renvoie vrai si le point est l int rieur du p rim tre du polygone faux sinon Mais avant tout il faut r cup rer ce point d intersection Comme la sph re poss de un nombre infini de points il peut y avoir un million de points en collision avec On sait obtenir le vecteur normal d un polygone ce qui va nous permettre de savoir de quel cot est tourn le polygone On a la fonction qui renvoie la distance du centre de la sph re au plan ClassifySphere met jour la variable distance pass e en r f rence et la normal nous donne l orientation du plan Voici un sch ma pour mieux comprendre Paint inside vNormal vCenter b CA l voffset _ vPosition En fait on projette le centre de la sph re sur le plan dans la direction de la normale On le fait en multipliant la normale par la distance du centre de la sph re au plan On obtient ainsi un vecteur qu on nommera vOffset sur le sch ma d o vOffset VNormal distanc
3. nombre final de faces dans l arbre nombre de faces initial dans le fichier Diff rentes solutions ont t propos es pour d terminer le choix des pivots mais seulement deux ont t retenues pour des impl mentations efficaces d algorithmes bas s sur les arbres BSP Choisir les pivots al atoirement Le choix al atoire des pivots est double tranchant on peut trouver un arbre acceptable en terme de grossissement comme un arbre disproportionn grossissement gt 800 Dans ce cas il faut calculer plusieurs arbres BSP avec une fonction de choix de pivot al atoire ce qui sous entend un temps de calcul plus long bien que le temps de compilation d un arbre ne soit pas un facteur suffisamment d terminant si il permet d obtenir un arbre optimis pour le parcours car plus d arbres calculer mais surtout une occupation m moire accrue car il faut stocker les arbres pour ensuite les comparer Choisir comme pivot la premi re face de la liste Instinctivement on aura tendance penser que c est un mauvais choix Et on aura raison En effet les faces de la liste sont dans l ordre dans lequel elles sont lues dans le fichier repr sentant l environnement et il y a videmment beaucoup de faces la suite des autres s rement gr ce un copier coller gt Les plans de coupe seront donc choisi dans l ordre dans lequel ils sont rencontr s ce qui revient Choisir comme pivot le plan qui coupe le moins de faces
4. Pitch Ces termes sont inspir s des termes de l aviation Ainsi quand on conna t ces 4 donn es on peut en d duire un droite orient e de l espace d finissant vers o pointe la cam ra cf fonction lookAt de glut Cette droite peut etre repr sent e par un Vecteur et un Point par exemple Une fois ce Vecteur connu on peut construire le frustum associ la cam ra c est dire une portion de l espace devant la cam ra repr sentant le volume visible par l avatar Dans un fps classique le joueur fait varier 2 de ses angles le heading et le pitch Dans les fps nouvelle g n ration Battlefield 1942 BF Vietnam Soldner Le joueur peut se servir de v hicules a riens et dans ce cas les 3 angles sont Mais de fa on naturelle avion h licopt re Moi en 2D je n ai besoin que du heading Si j avais voulu cr er le frustum en 3D il m aurait suffit de rajouter l angle pitch de la cam ra dans les calculs d extraction des 8 points De plus mon frustum tant une coupe d un Frustum 3D il poss de seulement 4 plans que j ai appel s front back right et left Revenons au Frustum La librairie OPENGL poss de des m thodes d extraction du frustum Or je suis en 2D et je ne me sers pas de cette librairie il a fallu que je r crive les m thodes de cr ation from scratch Ici interviennent des notions de g om trie analytique dans l espace Ce calcul se fait en 2 passes Premi re passe extraction g om trique
5. charger par le moteur 3D Vous verrez que certaines parties de cet environnement se pr tent mieux certains algorithmes que d autres Une section de comparaison des algorithmes est pr sent e dans le rapport R partition de t ches e Elaboration du Moteur 3D Jean Francois Fourmond e Elaboration du chargeur de fichier du moteur 3D St phane Mariani e Elaboration d un environnement 3D pour le chargeur Xavier M dioni et Jean Fran ois Righi e Elaboration du frustum culling Jean Francois Fourmond et St phane Mariani M thode de travail Nous avons t ch de communiquer le plus possible e Par l interm diaire du Wiki avec des mises jour quotidiennes o en communiquant entre nous sur une page d di e o en montrant r guli rement l avanc e de notre travail sur nos pages respectives e Par des r unions fr quentes entre les membres de l quipe e Nous avons aussi rencontr Nicolas Peri d veloppeur de jeux vid os sur diff rentes plateformes et avons longuement communiqu avec lui notamment sur nos algorithmes et les techniques utilis es dans les jeux actuels Moteur 3D utilis par les programmes de d monstration de ces algorithmes Le moteur 3D Avant tout nous pr sentons ici les caract ristiques du programme que nous avons d velopp pour illustrer les algorithmes pr cit s Il s agit d un moteur 3D Qu est ce qu un moteur 3D Un moteur 3D peut se d finir comme un programme calculant des images
6. affichables avec un minimum de fluidit que l on peut mesurer par le taux de rafraichissement et simulant le d placement d une cam ra virtuelle et ou d objets dans un environnement en trois dimensions Une fois nos algorithmes de partitionnement de l espace en t te nous avons choisi de commencer par impl menter un moteur 3D commun qui pourrait donc tre utilis par chacun de nous Le travail a t d coup en deux parties e Le moteur lui m me e Le chargeur de fichiers Le moteur lui m me Avant tout il faut pr ciser que nous n utilisons aucune optimisation d Open GL Par exemple nous envoyons la carte graphique les polygones un par un ce qui n est pas du tout optimal Nicolas Peri nous a dit qu il fallait les envoyer par paquets de plusieurs centaines pour avoir de bonnes performances sinon cela revient utiliser la carte en sous r gime Les seules optimisations qui font aller le programme plus vite sont donc nos algorithmes que nous d tailleront plus bas Fonctionnalit s e Visualisation 3D l aide de cam ras virtuelles quand on se prom ne dans l univers tridimensionnel ce qu on voit sur l cran c est le point de vue d une personne comme dans les jeux de type FPS ou d une cam ra virtuelle situ e quelque part dans l univers qui regarde dans une certaine direction Cette cam ra poss de des caract ristiques telles que la focale la taille de la pellicule la taille de la fen tre de visualisati
7. avons surtout tudi les bases de la visualisation 3D bases math matiques calculs en coordonn es homog nes projection 3D vers 2D algorithmes d limination des faces cach es clipping 2D et 3D gestion des clairages lissage des faces Gouraud Phong et texture mapping Malheureusement en 6 s ances nous n avons pu impl menter dans notre programme d velopp en TP et mini projet l ensemble de ces algorithmes faute de temps Par ailleurs le logiciel d velopp tait un simple visualiseur d objets 3D en aucun cas un logiciel lourd permettant par exemple de se promener dans des univers importants tels qu un b timent ou un paysage de plusieurs kilom tres Or la plupart des jeux vid os ou des applications de r alit virtuelle permettent aujourd hui d explorer des environnement tr s grands Se pose alors un probl me r curent dans ces applications tant donn que la somme des donn es n cessaires la repr sentation tridimensionnelle de cet univers consiste en des milliers voire des millions de polygones comment les trier afin de ne consid rere que la partie de ces informations qui correspond ce qui doit r ellement tre dessin e sur l cran La solution est algorithmique Imaginons que l on classe dans une simple grille 2D dont chaque case fait 10 m tres de c t les objets tridimensionnels qui composent l univers explorer si on veut dessiner l cran ce que voit un individu il est inutile de c
8. loign est l infini si la cam ra se trouve dans un espace clos et un mur est pr sent devant le champs de vision de la cam ra le d coupage de l espace fait que tous les cubes cr s se trouvant derri re ce mur seront affich s en plus de ce mur De m me comme nous l avons vu l algorithme g n re de nouvelles faces et ainsi plus la subdivision est grande plus le nombre de cube est important et plus le nombre de faces augmente Ceci est assez contraignant lorsqu on d cide de s loigner au maximum de la sc ne avec le m me nombre de subdivision car tous les cubes sont dans le champs de vision de la cam ra et ainsi beaucoup plus de polygones sont affich s compar au nombre total dont se compose la sc ne au d part Ceci nous am ne la partie suivante e Extension En effet en supposant que l on d coupe la sc ne et que l on s loigne afin d avoir toute la sc ne dans le champs de vision Du fait que les polygones chevauchant les cubes sont dupliqu s beaucoup plus de polygones sont affich s dans ce cas que ce que sont affich s sans subdivision Ainsi intervient la notion de niveau de d tail ou Level Of Details LOD en anglais Le but est de stocker dans l arbre pour chaque n ud des listes correspondantes des niveaux de d tail diff rents Ainsi lors de l affichage on teste l loignement de la cam ra par rapport un cube et on affiche la liste de polygones du niveau de d tail correspondant Il est vident q
9. s Total nodes drawn 7829 puisqu ils sont tous dans notre champ de vision pour finir Etape 7 Niveau 6 dans l arbre Nous voici donc une profondeur laquelle on ne distingue plus du tout l objet en mode fil de fer donc voici uniquement l image en mode textur L arbre se compose de 42921 n uds terminaux c est dire de feuilles contenant des surfaces le m me nombre de n uds est affich puisqu ils sont tous dans le champs de vision de la camera dans le frustum e Cas d arr t Le processus de subdivision tant r cursif on ne va pas continuer de subdiviser l infini II y a en effet diff rentes mani res de mettre fin l it ration o quand on a construit un nombre de niveaux fix par avance o la taille des cubes atteint un certain seuil o le nombre de polygones maximum fix l avance que doit contenir un cube a t d pass o le nombre de n ud de maximum fix a t d pass Dans les exemples ci dessus la profondeur est un param tre r glables par l utilisateur donc le cas d arr t correspond au niveaux de profondeur e Calcul du nombre d octree Profondeur Octal Taille de l octree Nb total d octree 0 8 0 1024 1 1 8 0 8 1 512 9 2 8 0 8 1 8 2 128 13 3 8 0 8 1 8 2 8 3 64 585 4 8 0 8 1 8 2 8 3 8 4 32 4681 D 8 0 8 1 8 2 8 3 8 4 8 5 16 3 449 6 n 8 299593 Utilisation Une fois que le processus de cr ation de l arbre est termin on poss de une
10. structure de donn es d crivant un volume li l espace occup par notre sc ne organis de mani re hi rarchique Comme nous l avons vu au d but le partionnement d espace seul est inefficace et ainsi il doit tre au moins coupl au frustum culling Le but du frustum culling est d essayer de trouver une m thode pour n afficher que les polygones vus par le frustum de vue Le frustum de vue peut tre consid r comme l angle sous lequel est vue une sc ne On peut assimiler au champ de vision chez humain par exemple Le point fort du frustum culling intervient lorsqu on travaille avec une structure hi rarchique Notre monde tant d coup partitionn dans une structure d arbre Si l on teste un n ud de haut niveau alors on a pas besoin de tester les n uds de niveau inf rieur On en d duit par cela que l on ne va pas faire le test du frustum sur tous les objets du monde mais on va les ranger de mani re hi rarchique Consid rons que la sc ne est constitu e de 100 objets avec seulement une de visible et qu on les range de mani re hi rarchique Normalement avec une m thode lin aire on va simplement tester chaque objet et regarder si oui ou non il est visible ou pas Il en r sulte donc 100 tests Maintenant consid rons le cas binaire Avec une premi re v rification on peut r duire le nombre de 50 avec la seconde de 25 ensuite de 13 ensuite de sept puis de quatre puis deux puis une Ce qui fait six v rifi
11. tre plate et convexe Ce format de fichier 3D ne prend pas en compte la sauvegarde du mat riau du nom du mat riau de couleur et de la texture qu il lui est associ Ce format n est pas de la meilleure utilit pour les jeux mais dans notre cas il convient tr s bien nous apporterons cependant quelques modifications au format du fichier afin d apporter ce format les concepts de mat riaux et de couleurs de l objet e Classes et Structures Dans le fichier Structs h On a la d finition de la structure de Face Pour conna tre le type de face il suffit de faire un test sur le bool en isAQuad qui est vrai si la face est un quadrilat re faux si la face est un triangle On a la d finition de la structure de Materiau Cette structure contient les informations n cessaires la description d un mat riau c est dire un nom un nom de fichier auquel on trouve l image de la texture un identifiant et une couleur de base La Classe Model3D Comme son nom l indique cette classe permet de d finir un mod le Quelle est la diff rence entre un mod le et un objet Le mod le contient un tableau d objets ainsi qu un tableau de mat riaux que l on va utiliser avec les objets Cette notion intervient lors du texturage Dans le fichier obj chaque l ment du d cor est d fini sous forme de groupe d abord la liste des sommets puis les faces qui vont former l l ment en question A cet l ment du d cor on va associer un
12. Algo OCTREE ggg D Moteur 30 TER Algo OCTREE wem m z J r mie a Lie F m On observe ais ment que des polygones sortent du cube Notre objectif aurait tait de couper les polygones pour obtenir a retouch avec Photoshop ogg ou Moteur FO TER amp lgo CCTREE em Moteur 30 TER Alga CCTREE o Tentative de clipping avec l algorithme de Sutherland Hodgman La premi re tape tait de partir d un plan et de son quation ainsi que d un polygone avec sa liste de sommets et d effectuer ce clipping d apr s l algorithme de Sutherland Hodgman Jean francois Fourmond a impl ment dans un programme part cet algorithme en mode fil de fer j ai donc r cup r ce programme et j ai ainsi rajouter le d coupage des texture En th orie et en pratique a marche on obtient a Motour 30 TER On remarque alors dans la figure de droite que lorsqu une face carr est travers e par le plan dans un ce ses coins on obtient un polygone 5 cot s et un triangle c est pourquoi il est non textur Notre moteur ne stocke que des faces carr s et des faces triangulaires donc en reliant deux sommets de ce polygones on aurait obtenu une face triangulaire et une face carr Dans le pire des cas on g n re trois faces partir d une seule sinon deux ce qui augmente consid rablement le nombre de polygones plus le niveau de profondeur
13. cal au centre Soit distance le segment rouge d cal au centre alors distance distanceX distance Y pythagore On voit nettement que si distance lt radius alors il y a intersection entre le carr le cercle En fait le fait de calculer distance lt radius nous permet d viter de calculer la racine carr de distance En fait il est plus optimal d lever radius au carr puis de faire la comparaison plut t que de chercher la racine carr de distance On renvoie donc vrai si distance lt radius faux sinon o bool IsOverlappsCameraWithFace Cette fonction pr sente dans la classe cam ra d l gue le calcul la fonction bool SpherePolygonCollision c est celle ci que nous allons tudier o bool SpherePolygonCollision Cette fonction retourne vrai si la sph re intersecte le triangle pass en param tre II s agit de la seule fonction appeler pour v rifier si une sph re est en collision avec un polygone Voici les diff rentes tapes de recherche o Etape 1 Positionner la sph re par rapport au plan du polygone Tout d abord rappelons que les plans sont infinis nous faut une fonction qui renvoie la position de la sph re par rapport au plan afin de savoir si elle est compl tement devant compl tement d rriere ou en intersection avec ce plan On a donc la fonction int ClassifySphere qui retourne BEHIND FRONT ou INTERSECTS Si ClassifySphere retourne INTERSECTS alors on va
14. cution Une fois les bounding box de chaque n ud calcul e on sauvegarde dans un fichier la structure arborescente avec les listes de faces et les bounding box associ es chaque n ud Pour l ex cution il n est pas n cessaire de conserver les quations de plan Parcours de l arbre pendant l ex cution Apr s le chargement du fichier repr sentant l arborescence de l environnement compil l objectif est d liminer un maximum de faces qui ne sont pas dans le champ de vision en un minimum de temps Pour ce faire le principe du parcours de l arbre est le suivant Si la bounding box du n ud courant est dans le champ de vision alors on affiche la liste de faces associ e au n ud courant puis on r it re le test pour chacun de ses fils Si la bounding box du n ud courant n est pas dans le champ de vision on sait qu aucune des faces de la liste associ e au n ud courant n est dans le champ de vision mais on sait aussi qu aucun de ses fils ne devra tre affich s et on peut arr ter la r cursivit Une branche enti re de l arbre peut tre occult e du traitement sur un simple test de visibilit ce qui met en valeur l int r t de chercher obtenir un arbre quilibr la compilation Programmes impl ment s Compilateur d arbres BSP L objectif tait de programmer une interface graphique au compilateur d arbres BSP avec la possibilit de voir les 3 premiers plans de coupe la racine de l arbre et ses
15. d s le d part de la profondeur Notre constructeur de quadtree prend donc en param tre la profondeur choisie les coordonn es x et z des coins du rectangle encadrant le monde Il construira r cursivement ses fils en d cr mentant la profondeur chaque niveau et ce tant qu elle sera gt 0 Passons la 3D Comment tester si le rectangle figure en 2D associ un n ud ou une feuille du quadtree est l int rieur du champ de vision de la cam ra champ d fini par des plans dans l espace 3D La solution qui vient l esprit est simplement de tester la m thode qu on a vue dans le paragraphe sur le frustum culling avec les 4 sommets du rectangle Mais quelle coordonn e en y donner ces sommets On a deux m thodes Avant tout on remarque que l on n a pas besoin des 6 plans du frustum seuls 4 suffisent En effet avec les quadirees les polygones sont regroup s dans des rectangles peu importe leur coordonn e en Y Donc on a pas besoin de consid rer les plans top et bottom du frustum 1 re m thode Si on ne met pas de Y cela revient dire qu on consid re que les rectangles sont sur le plan d quation Y 0 Mais on veut plut t que ces rectangles correspondent au niveau du sol qui n est pas forc ment 0 Le programme permet de monter ou de descendre la coordonn e en Y et d afficher le d coupage du monde 3D en rectangles e Exemple avec Y gt hauteur max du temple et profondeur 8 Il y a un pr
16. de 4 points du plan qui sont les points d accroche du frustum Un dessin valant mieux que de long discours je vous pr sente donc ma m thode de construction du frustum De fa on g om trique M thode de construction g om trique du frustum r cup ration des points nearLeft nearRight FarLeft et FarRight point d accroche du plan Far Fo re ns LE has paint d accroche du plan e Near p position r cup ration des points RealFarRight et compos e de translations et rotations RealFar Left B et F Th or me de Thal s je vous invite lire les sources de la classe Frustum pour plus de pr cisions Deuxi me passe calcul des quations des 4 plans Petits rappels Math matiques les classes Plan Vecteurs et Point Un Point est caract ris par 3 coordonn es R elles x y et z ce sont donc des float en C Un Vecteur est caract ris par 3 coordonn es R elles x y et z ce sont donc des float en C Pour d finir un Vecteur v le constructeur en C il faut 2 Points origine o0 et extr mit e On a alors V X X O X V y O y V Z e Z O Z L quation d un Plan dans l espace est alpha x beta y gamma z delta Ce qui signifie qu un Point de coordonn es x y z appartenant ce plan v rifie cette quation Pour trouver l quation d un plan il existe plusieurs m thodes Analytique g om trique trigonom trique Je vous expose ici celle
17. deux fils avec la possibilit d imposer les quations de ces plans pour la compilation si des plans de coupe optimum sont vidents pour l utilisateur Malheureusement les probl mes rencontr s lors de l impl mentation furent plus difficiles r soudre que pr vu et je n ai pu aboutir un programme fini En effet une des principales difficult s par rapport aux quadirees ou aux octrees est de g rer les plans de coupe presque coplanaires c est dire coplanaires dans la r alit mais cause de l approximation des nombres r els ils ne sont pas coplanaires par l ordinateur Avant de g rer cela ces plans presque coplanaires engendraient des d coupes multiples en lamelles ultra fines ce qui g n rait un nombre consid rable de faces suppl mentaires L impl mentation d arbres BSP doit se faire avec une extr me minutie et la d tection d erreurs devient tr s difficile Ajoix D Compiloteur BSP COMPILATEUR BSP PLAN 2 PLAN 5 Moteur 3D utilisant l arbre BSP compil L algorithme du parcours de l arbre me semble op rationnel mais je n ai pas eu la possibilit de le tester car je n ai pas pu terminer le compilateur Conclusion sur l utilisation des arbres BSP Les arbres BSP offrent de tr s bonnes performances dans la simulation d un d placement dans un environnement indoor compos d une multitude de pi ces Ces performances se mesurent par la fluidit d affichage nombre d images par seco
18. donn e membre visualOctreeOfNode Cette donn e va contenir le dessin du cube tr s utile pour du d bugage En effet lorsqu un n ud terminal une feuille est cr on ajoute les lignes repr sentant le cube du n ud dans la liste de visualOctreeOfNode Ainsi a chaque affichage d un n ud on a la possibilit ou non d afficher le cube englobant e Changement de profondeur L int r t de l impl mentation d un moteur bas sur l algorithme des octree est le fait de pouvoir r gler le param tre profondeur afin d tre en mesure d observer les changements de performance Dans l absolu deux m thodes se sont pr sent s afin de rendre le param tre profondeur r glable Soit on fixe une profondeur de d part et ainsi chaque utilisation on construit un arbre de m me profondeur Avantage On cr l arbre qu une seule fois donc le changement visuel de profondeur est situ au niveau du parcours de l arbre Ainsi le changement de profondeur est instantan Inconv nient La profondeur est fix e au d part on se retrouve coinc entre deux bornes Soit on recr un nouvel arbre a chaque changement de profondeur Avantage On peut cr des arbres de profondeur infinie en supposant que les performances de la machine nous le permettent Inconv nient L arbre est recr chaque fois et pour une sc ne disposant d un tr s grand nombre de polygone et selon le niveau de profondeur il faut attendre que l arbre
19. dont je me suis servie Elle s apparente un probl me math matique et je l ai trait comme tel Si on poss de 1 Point de l espace et un vecteur normal ce plan on peut en d duire l quation du plan Pour trouver le vecteur normal un plan on peut de servir du produit vectoriel de 2 Vecteurs appartenant ce plan Pour trouver 2 Vecteurs du Plan il suffit d avoir 3 Points A B C appartenant au Plan Le calcul de la normale se fait donc par Vecteur Normal Vecteur A B Vecteur A C o repr sente le produit vectoriel Je ne rentre pas dans les d tails du calcul mais invite le lecteur lire mes sources pour les calculs math matiques classe Vecteur Une fois le vecteur normal trouv il suffit de le normaliser Normaliser un vecteur non nul consiste diviser chacune de ses coordonn et s par la norme de ce Vecteur La Norme d un Vecteur tant la distance entre ses points extr mit et origine cf sources pour le calcul Une fois le Vecteur Normal trouv et le Point M d ancrage du Plan d finit nous avons toutes les informations en main pour trouver l quation du Plan Pour cela il faut se servir des propri t s du produit scalaire et de l appartenance du Point M au Plan Ainsi Vecteur NormalVecteur Normal Vecteur O M 0 o repr sente le produit scalaire et M appartient au Plan on en d duit alors les param tres alpha beta gamma et delta du Plan cf constructeur de la class
20. du programme pour compiler le monde parait que certaines entreprises de jeux videos travailleraient sur un algo permettant de se passer de ce fichier ainsi le monde serait compil a la vol e info ou intox Pr sentation de l algorithme Apr s r flexion nous avons d cider de vous pr senter l algorithme sur les portails l aide d un soft 2D en vue de dessus La structure principale de l algorithme bas sur les portails est la classe Frustum II n est pas ais de montrer des transformations de frustum en 3D En effet cela s apparente a des effets sp ciaux visuels motion blur zoom etc Les librairies OpenGL et Directx poss dent une m thode d extraction du frustum Cette m thode consiste r cup rer les matrices Modelview et Projection lien Mais nous n avons pas voulu nous en servir et avons pr f r tout r crire from scratch Ainsi la classe cam ra qui lui est troitement li e est inspir e de celle utilis e dans le moteur 3D mais poss de ses propres fonctionnalit s De plus l algo fonctionne avec un fichier annexe conservant les informations des pi ces en 3D il aurait fallu un diteur de pi ces cf Annexe en construction pour pouvoir avoir une sc ne compl te De plus les fonctionnalit s int ressantes comme le clipping n auraient pas t visibles En effet en 2D on peut tout de m me afficher le monde entier et surligner ce qui serait effectivement envoy a la carte 3D Enfin je ti
21. englobante du fait qu elle s adapte beaucoup mieux que la sph re En fait chaque objet devrais contenir une bounding box et une bounding sph re De ce fait on pourrait rejeter certain objet directement avec le test de la sph re et faire le test avec la bounding box uniquement si le test de la sph re r ussi La seconde optimisation intervient dans le parcours de l architecture Dans notre cas la m thode g n rale est de commencer la recherche partir du n ud racine et de v rifier s il est visible Si c est le cas on va v rifier chacun des 8 n uds fils sinon on arr te la recherche Cette m thode est r cursive et s applique donc sur tous les n uds du cube Une fois qu on arrive aux n uds terminaux de l arbre s ils s av rent visibles alors on affiche leur contenu Maintenant consid rons un n ud non terminal une feuille si ce n ud est compl tement visible quel est l int r t de v rifier la visibilit des n uds fils on va utiliser tord des cycles CPU pour calculer des choses que l on sait d j Dans ce cas on affiche le n ud ainsi que tous ses descendants sans tester les n uds Par contre le seul cas ou on doit tester les n uds fils est quand le n ud racine intersecte avec le frustum La troisi me optimisation est de ne pas v rifier l intersection si la camera est compl tement l int rieur Dans ce cas la on sait que le volume intersecte avec le frustum Ensuite on proc de comme on l a expliqu ci de
22. environnements ext rieurs parce qu on a pas de plan de coupe efficace e Difficult d impl mentation Les quadtrees et les octrees sont les plus simples impl menter Les arbres BSP et les portails sont bien plus complexes mettre en oeuvre Les quadtrees et octrees peuvent tre cr s pendant l ex cution mais les arbores BSP n cessitent une phase de pr compilation de l environnement et les portails ont besoin d informations suppl mentaires correspondant aux pi ces e Utilisation m moire Les arbres BSP utilisent de la place sur le disque en raison du stockage de l environnement compil La quantit de m moire occup e pour stocker un arbre BSP apr s chargement est galement plus importante qu avec un quadtree ou un octree En effet l algorithme de compilation tant essentiellement bas sur des plans de coupe cela engendre un grossissement non n gligeable du nombre de faces composant l environnement Les octrees prennent plus de place que les quadtrees car on a plus de subdivisions de l espace un octree a 8 fils contre 4 pour un quadtree Conclusion Ad quation avec le cahier des charges Nous avions pr vu de faire une tude d taill e de chacun des algorithmes et de r aliser pour chacun d eux un programme d illustration p dagogique mettant en valeur leurs caract ristiques Ceci a t fait pour les quaditrees et les octrees avec des programmes bas s sur un moteur 3D commun Le programme avec les arbres BS
23. est bas c est dire plus le nombre de cubes est important o Adaptation avec les octree Le clipping jusque la parait fonctionnel mais ne reste pas convainquant quant aux performances qu il engendrerait malgr a il aurait apport un effet assez plaisant lors de la simulation d clatage de notre monde que nous verrons par la suite La mise en place du clipping a engendr certaines modifications notre structure de d part En effet nous ne pouvons plus travailler avec des pointeurs sur les objets du fait que ces objets vont tre sujet des modifications sp cifiques aux cubes dans lequel ils sont pr sents Nous verrons dans la partie consacr e l impl mentation des octree quelles modifications structurelles ont t apport es et pourquoi La premi re tape de la mise en place du clipping de polygone dans notre moteur a t d affecter chaque n ud terminaux de l arbre autrement dit les feuilles contenant les objets les six quations de plans de ses six faces Deuxi me tape pour chaque noeud terminal et pour chaque objet on parcoure un chaque face de sa liste et on proc de son traitement et ce en fonction des six plans du cube o Sila faces est l ext rieur du cube on ne la garde pas o Sila face est l int rieur du cube on la garde sans la couper o Sila face intersecte un plan alors il faut la couper La d tection des faces traversant les plans de cube fonctionne Voici deux images de notre m
24. qui revient projeter vA vCenter sur vA vB R sultat On voit nettement que si le produit scalaire des deux vecteurs est inf rieur la norme du vecteur VAVB alors le point vA est plus proche de la sph re que ne l est vB sinon c est l inverse Simulation d clatage de la sc ne Afin de cr er cette simulation d clatage on a du faire intervenir dans la structure de l octree une nouvelle donn e membre on rappelle la structure d un octree Class Octree private I tableau des 8 branches descendantes du noeud courant Octree tabOctreeNodes f8 permet de savoir si on a subidvis le noeud courant ou pas bool subdivided I taille du cube pour le noeud courant float widthNode Il Centre X Y Z du noeud courant Coord3D centerOfNode Il decalage du noeud pour l eclatage de la map Coord3D shiftOfNode 1 stocke les objets qui devront etre affich s avec ce noeud Object3D m_pObject3D le dessin du cube repr sentant l octree du noeud VisualOctree visualOctreeOfNode tableau des 6 plans du cube du noeud Plane tabPlanesOfNodes 8 6 En comparant la structure pr sent pr c demment on remarquera la pr sence de la donn e membre shiftOfNode Au m me titre que chaque n ud cube poss de un centre et une taille il contient de m me un vecteur d calage Ce vecteur doit tre d fini pour chaque octree dans la r cursivit lors de la cr ation du n ud du fait qu il doi
25. se construise R sultats Au regard des deux m thodes pr sent es ci dessus et du fait que Jean Francois Fourmond a impl ment l algorithme des quadtree bas sur la premi re m thode il me paraissait int ressant d appliquer la seconde m thode afin de comparer les avantages et inconv nients respectifs On rappelle par ailleurs que notre impl mentation but p dagogique nous incite switcher entre les diff rents niveaux de profondeur mais dans un jeu de type FPS l arbre est cr une seule fois et ainsi il n est pas reconstruit au cours de l ex cution o Cot code Afin de travailler toujours sur la m me variable nous avons choisi de placer l initialisation ainsi que la destruction des donn es des Octree dans les fonctions respectives InitOctree DestroyOctree et non dans le constructeur destructeur de base de la Classe octree De se fait lors d un changement de profondeur il suffit d appeler les m thodes DestroyOctree qui lib re les zones m moires allou es au donn es membres de l octree racine en particulier la zone m moire allou e au stockage des objets de chaque n ud ainsi que la zone m moire allou e pour tous les n uds partant de la racine puis la m thode InitOctree qui r initialise certaines donn es membre Il ne suffit plus qu a relancer la m thode de cr ation des n uds avec un niveau de profondeur diff rents Gestion des collisions Introduction Dans cette partie nous a
26. sont encore moins performants que les octrees si on a des tages parce qu on va afficher toute la hauteur d un b timent En revanche les portails qui sont bas s sur des pi ces ne peuvent pas tre utilis s dans des environnements ext rieurs Si on est dans un monde sans pi ces et donc sans murs tout sera affich avec les portails m me les polygones qui sont derri re la cam ra Il est pr f rable d utiliser les quadirees ou les octrees pour ce genre d environnements En effet on souhaitera afficher les polygones aussi loin que possible et les quaditrees et octrees permettent de ne presque pas afficher de polygones qui sont hors du champ de vision Les quaditrees et octrees sont donc utilis s dans les environnements en ext rieur mais pas dans les m mes cas Par exemple si on est dans une ville on a des immeubles de forme rectangulaire pos s sur le plan du sol Ca ne servirait rien de les d couper en cubes a ne ferait qu augmenter le nombre de polygones affich s Par contre si on a des montagnes constitu es d un certain nombre de polygones il vaut mieux avoir des octrees car on peut ainsi afficher une partie des polygones de la montagne seulement selon qu on regarde en bas ou son sommet Avec les quaditrees on affiche tous les polygones contenus dans un rectangle quelque soit leur hauteur On risque donc d en afficher qui sont au dessus ou en dessous du champ de vision Les arbres BSP ne sont pas efficaces avec les
27. une intersection avec notre monde en d autres mots les cubes contenant au moins une surface On observe pr sent e profondeur est de 1 Depth 1 e l arbre contient 8 n uds au total en fait ce sont 8 feuilles Total ends nodes 8 e 8 n uds sont effectivement affich s Total nodes drawn 8 puisqu ils sont tous dans notre champ de vision e Etape 3 Niveau 2 dans l arbre On r p te ce processus de subdivision pour obtenir le niveau 2 de l arbre chaque nouveau niveau cr la taille des cubes est divis e par deux par rapport au niveau pr c dent ra mateo JD TER Aigo CCTR E g zZ Moim 30 TEE digo OCTR E On observe maintenant e profondeur est de 2 Depth 2 e l arbre contient 64 noeuds au total Total ends nodes 64 e 64 n uds sont effectivement affich s Total nodes drawn 64 puisqu ils sont tous dans notre champ de vision on saute quelques tapes Etape 6 Niveau 5 dans l arbre Il est tr s int ressant d observer que plus le niveau de profondeur est bas plus l agencement des cubes se rapproche de la forme de l objet Ce ph nom ne est du au fait qu on ne garde pas les cubes vides et seuls les cubes contenant des surfaces sont cr s et affich s ra Moteur ID TER Mis CCTR E D Moteur 10 TER go CCTR E On observe maintenant e profondeur est de 5 Depth 5 e l arbre contient 7829 n uds au total Total ends nodes 7829 e 7829 n uds sont effectivement affich
28. visent d couper l univers en secteurs Ce qui relie un secteur un autre est le fait que si on se trouve dans un secteur et si on peut voir une partie d un autre secteur alors ils sont voisins Et la partie qui les relie est un portail En fait cette structure de donn es permet lorsqu on se d place de ne consid rer que les polygones appartenant au secteur courant plus les polygones des secteurs voisins Pour calculer ces secteurs et d terminer leurs relations de voisinage c est assez simple On regarde si depuis un secteur on peut voir des l ments qui ne sont pas dans le secteur courant La difficult consiste dans cette phase justement d terminer ce qui est visible depuis un secteur donn On se base sur le champs de vision plan top plan left plan far plan near m plan right VX plan bottom Pour entrer dans les d tails de l algorithme on va prendre quelques exemples les secteurs sont des pi ces compos s de polygones Comprenez par pi ce une salle en 3D comme un salon ou une chambre et contenant des portes qui les relient Comme une pi ce de la vie de tous les jours II faut un fichier annexe contenant des informations sur les pi ces hauteur largeur position et des informations sur les portails Un portail est un polygone apartenant simultan ment 2 pi ces dans notre cas 2 pointeurs sur des pi ces Il est donc n cessaire de loader un fichier sp cial au lancement
29. visible Frustum Portail invisible Pour le moteur 2D et le frustum je me suis servi de la d mo de Jean Fran ois sur les quadtrees en 2D Le frustum avait un petit bug non bloquant Il a fallu que j crive un fichier texte dans lequel je conserve les infos sur les pi ces et les portails dont voici la syntaxe NB_PIECES nbpieces NB_PORTAILS nbPortails piece indice sommet1X sommet1Y sommet2X sommet2Y portail indice sommet1X sommet1 Y sommet2X sommet2Y pieceA pieceB nbpieces est le nombre de pi ces pr sentent dans le monde nbPortail est le nombre de portails pr sents dans le monde Une pi ce est caract ris e par un indice et 2 sommets qui sont les coins oppos s d un rectangle ou d un parall l pip de dans le cas de la 3D Un portail est caract ris par un indice 2 sommets cela repr sente un segment et les indice des 2 pi ces qu il relie II n y a pas d analyse s mantique donc je pars du principe que le fichier texte est bien form C est dire que le nombre de ligne commen ant par pi ce est gal NB_PIECES Idem pour NB _PORTAILS De plus les pi ces doivent tre coll es et les portails bien plac s J en suis arriv la conclusion qu il fallait un Editeur cf Annexe Polygones et portails En introduction j ai dit qu un portail tait un polygone sp cial Or il n y avait pas de stucture de donn e polygone dans la d mo pr c dente J ai donc repris mes classes r crit une nouve
30. C est premi re technique bas sur un principe logique limiter au maximum le grossissement On compare chaque face du monde avec toutes les autres et on choisit celle qui coupe le moins de faces Cette m thode a une complexit en temps en O n sur les faces de chaque n ud En effet pour la premi re subdivision on compare toutes les faces entre elles pour choisir un pivot A la suite de cela une face est choisi et on divise l espace en deux une fois que les faces coplanaires sont associ es au n ud courant ici la racine les faces avant vers le fils droit et les faces arri re vers le fils gauche On recommence ensuite la comparaison sur le fils droit et sur le fils gauche Dans cette m thode le temps de compilation devient vraiment tr s long pour finalement obtenir des r sultats pas si satisfaisants En pratique il est logique que le premier pivot soit un plan qui contienne un mur groupe de faces afficher limitrophe de l environnement puisque c est lui qui coupe le moins de faces Ce qui implique que la totalit de l environnement va se trouver du m me cot de ce mur Il faut au moins quatre murs limitrophes pour d limiter un environnement en fait trois murs et un plancher en supposant que cette environnement soit munis de r gles physiques comme les collisions et la gravit et on peut raisonnablement imaginer qu ils seront les pivots des premiers niveaux de l arbre construit Ce qui va nous amener une situ
31. Ceci montre que cette m thode n est pas adapt e pour les programmes permettant d orienter la cam ra n importe o puisque quel que soit le plan choisi il pourra des polygones quelque part Toujours le m me probl me si on se met en hauteur et qu on regarde le sol en fixant la hauteur du sol 19 comme coordonn e y des carr s le sol s affichera tr s bien Mais si on se met en mode fil de fer et qu il y a des polygones sous le sol ceux qui sont sur les c t s risquent de ne pas s afficher de la m me fa on que pour le mur ci dessus Ce n est pas facile de se repr senter le probl me C est une question de perspective on croit qu on devrait voir des polygones mais si on les projette sur le plan Y hauteur ils sortent du champ de vision e exemple en marron les lignes du sol en noir le 5015 50 le couloir ne s affiche pas bord gauche de l cran plan left du frustum Sur l image ci dessus on voit des zones de l cran qui ne sont pas affich es parce qu on a Y 19 alors que ces zones sont bien en dessous de 19 Si on abaisse le Y tout s affichera mais il y aura encore moins de polygones affich es au dessus du sol quand on regardera en haut Ceci montre que cette m thode n est pas non plus adapt e aux environnements plusieurs tages La d formation de la sc ne par la cam ra n est pas le seul probl me Imaginons qu on fixe hauteur du sol pour les rectangles Si on est dans le temple et qu
32. Etude des structures de donn es au c ur des algorithmes 3D des jeux de type FPS Encadrant Michel BUFFA Participants Jean Fran ois FOURMOND St phane MARIANI Xavier MEDIONI Jean Fran ois RIGHI Table des mati res Avant propos Introduction et pr sentation du sujet R partition de t ches M thode de travail Moteur 3D utilis par les programmes de d monstration de ces algorithmes Le moteur 3D Qu est ce qu un moteur 3D Le moteur lui m me Fonctionnalit s Technologies utilis es Architecture Le chargeur de fichiers Conception de l environnement Les quadtrees Qu est ce que c est quoi a sert Concr tement Passons la 3D Clipping l horizon Optimisations possibles Level Of Details Optimisation du frustum culling Quadtrees dynamiques Conclusion Les Octrees Introduction Structure et m thode de cr ation Utilisation Optimisations possibles Impl mentation Stockage des Octree Conception de l arbre Gestion des collisions Simulation d clatage de la sc ne Conclusion Les arbres BSP Historique D finition Limitation des arbres BSP Construction de l arbre BSP partir d un fichier monde Compilation Choix du plan de partitionnement Choisir les pivots al atoirement Choisir comme pivot la premi re face de la liste Choisir comme pivot le plan qui coupe le moins de faces Choisir le pivot en vue d obtenir un arbre quilibr Conclusion sur le
33. P bas sur le m me moteur n a pu tre achev temps Le programme concernant les portails a t r alis en deux dimensions et n utilise donc pas le moteur 3D commun L tude et l impl mentation de ces algorithmes a pris plus de temps que ce que nous avions pr vu et les notions de contraintes physiques abord es dans le cahier des charges comme la gravit et la gestion des collisions n ont pu tre impl ment es faute de temps La gestion des contraintes physiques n cessite en r alit une tude pouss e difficilement r alisable dans le temps imparti en plus de l tude des algorithmes de partitionnement de l espace et pourrait elle seule faire l objet d un TER Bilan Personnel Bien que l aspect visuel de notre travail puisse d gager un certain cot ludique il faut garder l esprit le fait qu il y a un gros travail d tude et d impl mentation derri re tout cela En effet notre travail a t majoritairement tourn vers des notions complexes d algorithmique et de g om trie dans l espace Il nous a fallu en plus apprendre l API Open GL pour mettre en place un moteur 3D performant et nous familiariser avec des outils de mod lisation d environnement 3D comme Blender Tout ce travail nous a apport des connaissances sur l laboration des programmes interactifs en 3D simulant un d placement dans un environnement virtuel L utilisation intensive du Wiki voir les statistiques a permis une bonne organisation de notre tra
34. P stocke ses donn es dans un n tree c est dire un arbre dont les n uds parents ont un nombre vari s de fils de z ro n Le n ud racine de l arbre contient tous les objets de la sc ne Plus les n uds s loignent du n ud racine moins ils contiennent d objet jusqu ce qu on ait une feuille qui contienne seulement un objet ou une surface L objectif de cet algorithme est de g rer et trier les informations concernant les objets dans la sc ne relativement aux autres en minimisant le temps n cessaires pour afficher les surfaces dans un ordre correct de devant en arri re ou l inverse La deuxi me forme d OSP est id ale pour les applications dans lesquelles la plupart de l espace est occup par des objets et dans lesquelles les objets ont approximativement la m me taille L objectif de cet algorithme est de g rer les informations de la sc ne en utilisant une structure octal tree dans laquelle chaque n ud parent poss de huit fils pour stocker les donn es II semble effectivement bien adapt pour traiter notre monde c est pourquoi c est ce deuxi me cas que nous avons impl ment et que nous allons tudier Structure et m thode de cr ation Un octree n est rien d autre qu une structure de donn e Voici un sch ma qui met bien en vidence la relation entre le d coupage de l espace et la structure d arbre Racine Niveau 0 DOOUOUGO Niveau 1 Soccoc Feuilles Niveau 2 Nous allons expliquer la m
35. ace Ainsi on pourra avoir une vue de dessus globale du monde en 3D e offre une vitesse de d placement constante on va la m me vitesse o quelque soit la rapidit de l ordinateur Pour cela l ampleur de chaque d placement d pend du temps coul entre 2 images Par exemple un d placement sera deux fois plus important si on est 10 images seconde que si on est 20 images seconde o qu on regarde en la verticale en haut ou en bas ou qu on regarde droit devant o etonne va pas plus vite si on avance en strafant que si on avance ou on strafe seulement e Plusieurs modes de visualisation sont disponibles o Mode sommets on affiche que les sommets des polygones o Mode fil de fer on affiche que le contour des polygones o Mode textur on affiche les polygones en leur plaquant des textures e Affichage de texte l cran o Nombre d images par seconde de polygones affich s informations relatives un algorithme particulier etc o On utilise pour cela la librairie BMF font Technologies utilis es Le moteur est crit en C La librairie utilis e pour le fen trage est la SDL Elle est portable et permet de g rer simplement les v nements utilisateur Toute le rendu texte et 3D se fait l aide de l API Open GL Open GL permet de g rer facilement la mise en place d un environnement en 3D et utilise l acc l ration mat rielle des cartes graphiques Les performances sont donc bien meilleures que
36. an de partitionnement est d terminant Nous avons vu pr c demment que certains plans de partitionnement ou pivots peuvent entra ner des d coupes de faces donc un grossissement de l arbre non n gligeable Le rendu final en terme d image affich e ne d pend pas de l arbre BSP Par contre le temps de calcul du rendu de l image d pend du nombre de faces Il n existe pas d algorithme permettant de choisir le plus petit arbre Il est impossible de tous les calculer et de choisir le plus petit parce qu il y en a beaucoup trop Nous verrons aussi par la suite que l arbre BSP le plus petit en terme de grossissement n est pas forc ment le plus adapt un parcours optimis pour le rendu pendant l ex cution du programme Par exemple pour une bouteille de Klein de 3720 sommets il existe environ 102160 arbres diff rents mais quivalents quivalent dans le sens o l image rendue est identique Afin de se rendre compte de la variation du grossissement d un arbre l autre pour le m me objet voici une tude statistique r alis e en calculant al atoirement pr s de 20 000 arbres quivalents sur la bouteille de Klein pr sent e ci dessus Nombre d arbres avant un grossissement donne Calculs al atoires 19460 arbres calcul s 978h sur un 400MHz l S 397 moyenne 439 o 487 0 834 vo Extrait d une tude r alis e par professeur de MP Le grossissement est calcul de la mani re suivante grossissement
37. ation similaire celle ci On va obtenir un arbre qui ne sera pas quilibr Le parcours d un arbre tel que celui ci quivaut peu de chose pr s parcourir une liste d ensemble de faces coplanaires On perd donc la possibilit d liminer le traitement d une branche enti re sur le r sultat d un test sur le n ud Choisir le pivot en vue d obtenir un arbre quilibr Apr s avoir constat que la m thode pr c dente ne permettait pas un parcours performant de l arbre voir sections Initialisation du champ bounding box de chaque et Parcours de l arbre des recherches ont t faites pour diviser l environnement de mani re quilibrer l arbre On part du principe suivant m me si cela doit engendrer plus de faces lorsqu on parcours l arbre on raisonne en ensemble de faces coplanaires On parcoure donc toutes les faces et on regarde combien de faces sont devant et derri re le plan porteur puis on choisit celle qui engendre la diff rence minimale entre le nombre de faces avant et nombre de faces arri re Cette m thode de choix de pivot est galement en O n sur les faces de chaque n ud Le nombre de faces engendr es par les d coupes n tant que peu contr lables il est judicieux de stopper la r cursivit lorsque l arbre atteint une certaine hauteur ou lorsque les feuilles contiennent un nombre de faces permettant d tre trait es plus vite l impl mentation Par exemple afin de minim
38. aura pas t atteint De m me on teste le nombre d objets que contient le n ud s il est inf rieur au nombre d objet maximum que l on a d fini l avance on arr te la r cursivit Par exemple si on souhaite au minimum 20 objets par n uds on ne pourra pas subdiviser et obtenir des n uds avec moins de 20 objets Si ces deux tests ne sont pas valid s on s arr te et on stocke la liste des objets avec laquelle on est entr dans le tableau d objets du n ud sur lequel on est en train de travailler o Etape 3 Cr ation des listes d objets pour les 8 nouveaux n uds C est ici que l on va d finir si oui ou non un objet est dans un n ud ou pas Pour cela on aura pr alablement cr pour chaque objet sa bounding box cube englobant au chargement de notre monde Pour chaque n ud de l arbre des octree on conna t les coordonn es des sommets du cube gr ce aux coordonn es du centre et de la taille du cube Ceci nous permet donc d tre en mesure de savoir si un objet se trouve l int rieur d un cube ou pas Dans l hypoth se o l objet est dans le cube on ne va pas le stocker enti rement on parcours la liste des faces de l objet et on fait le traitement qu on a vu dans la partie consacr e au clipping Si la faces est l ext rieur du cube on ne la garde pas si la face est l int rieur du cube on la garde sans la couper Si la face intersecte un plan on la garde sans la couper Lorsqu une face chevauche
39. c certains murs de cette pi ce sont potentiellement visibles La fonction affichePortail portailCourant est alors appel e Cette fonction marque le portail comme visible puis appelle la fonction affichePiece sur les 2 pi ces reli es par le portail Cet algorithme est donc un parcourt de graphe en profondeur o les n uds sont Les n uds tant les pi ces les ar tes tant les portails Ray Casting impl mentation je pense que je modifierai ma fonction affichepiece de cette mani re src www flipcode com Frustum fr function renderSector sector for each polygon in current sector if ffacing polygon continue if clip polygon fr NULL continue if polygon PORTAL markVisible if polygon PORTAL Push fr fr adjustFrustum fr polygon renderSector polygon sector Pop fr Optimisations et r flexions Calcul matriciel Ma classe Matrice poss de 3 lignes et 3 colonnes les coordonn es ne sont donc pas homog nes Ce qui me permet de gagner des calculs Recherche de pi ce courante Je parcours toutes les pi ces avec une boucle for pour trouver la pi ce courante Meshes J ai crit cette classe elle existe dans mon code Mais je ne l ai pas utilis Elle servirait englober un groupe de polygones afin de diminuer les tests de clipping R cursion Terminale vs Iteration Il y a 2 fonctions s appelant l une l autre dans cette algorithme Elles sont toutes les deux pos
40. cations au total ce qui est beaucoup plus rapide que 100 En fait la m thode lin aire doit effectuer N it rations la ou la m thode binaire en effectue seulement log N log base 2 Ainsi chaque fils occupent un morceau du volume de l octree parent Lorsqu on sait que le n ud parent n est pas visible on peut affirmer que les n uds fils ne le seront pas non plus En g rant le monde de cette mani re on peut rapidement cacher et afficher une tr s grande partie du monde avec seulement quelques tests Voici un exemple d utilisation du frustum culling En rouge sur l image de gauche le frustum de vue et a droite la vue r elle de la cam ra partir du point rouge Si l on active le frustum culling seul les 4 cubes dessiner en vers sur l image de gauche sont r ellement dessiner sur l image de droite Ceci est d ailleurs confirmer par le nombre de n uds affich s Total nodes drawn 4 compar au nombre total de n uds cr s Total end nodes 8 Optimisations possibles La premi re optimisation est assez triviale Si l on tudie les deux m thodes vues pr c demment d intersection avec le frustum il est incontestable que le test d intersection de la sph re avec le frustum est beaucoup plus rapide que le test d intersection du cube Ceci veut dire qu il serait plus convenable d effectuer d abord le test de la sph re avant de faire celui du cube La boite englobante de l objet est dans certain cas mieux qu une sph re
41. choix du pivot Initialisation de la bounding box de chaque n ud Parcours de l arbre pendant l ex cution Programmes impl ment s Compilateur d arbres BSP Moteur 3D utilisant l arbre BSP compil Conclusion sur l utilisation des arbres BSP Les Portails Qu est ce qu un portail Pr sentation de l algorithme Notions mises en jeux dans l algorithme Les pi ces les portails et la r currence Comment repr senter une pi ce et un portail Polygones et portails Visibilit clipping vs Bouding Box Premi re passe extraction g om trique de 4 points du plan qui sont les points d accroche du frustum Deuxi me passe calcul des quations des 4 plans Petits rappels Math matiques les classes Plan Vecteurs et Point Visibilit Le recalcul du frustum L algorithme Ray Casting impl mentation Optimisations et r flexions Conclusion et Annexes Synth se sur l tude de ces algorithmes Conclusion Avant propos Ce rapport ayant t con u sur le wiki il comporte des liens permettant d acc der nos r f rences nos programmes pour Windows et de passer rapidement d une partie du rapport une autre Nous vous conseillons donc si vous tes sur la version papier de pr f rer la version en ligne l adresse suivante http deptinfo unice fr cgi bin twiki bin edit Minfo AlgosJeux3DRapport Introduction pr sentation du sujet Lors du cours d introduction la synth se d images de Michel Buffa nous
42. culaire perpendiculaire ne align s aux perpendiculaire d termin par par pi ces p axes du monde des plans de coupe division de E division des ai division de D composition r gions carr es ae surface devant Type de division r gions du niveau en de plus en plus et derri re le ak cubiques pi ces petites plan Possibilit Po d utilis avec les oui oui oui d 7 w d collisions j MONS pi ces Utilis avec le adi a ouj oui frustum culling m O n Chargement A COMP ERI AG Qi O p 8 sur les face de des pi ces avec construction p profondeur chaque n ud celui du monde Complexit de O log n sur un O n sur les recherche O p log p O p log p arbre quilibr pi ces Algorithme oui oui oui oui statique Algorithme possible mais non non non dynamique complexe Nous allons ici comparer les algorithmes tudi s montrer leurs avantages inconv nients en fonction de l environnement 3D dans lequel on se trouve des difficult s d impl mentation etc e Environnements Quand on est l int rieur d un b timent les quadtrees et les octrees ne sont pas recommand s En effet si on est face un mur qui occupe tout l cran on affichera quand m me tous les polygones visibles qui sont derri re et qui sont moins loin que le plan far du frustum Avec les arbres BSP on peut viter ce probl me ainsi qu avec les portails o l on n affiche que ce qu on voit Les quadirees
43. dans le champ de vision on teste deux fois si ses sommets sont dans le champ de vision une fois avec Y hauteur maximale du monde et une fois avec hauteur minimale du monde En fait on teste avec les 8 sommets de la colonne Ca fait deux fois plus de tests qu avec la premi re m thode mais on est sur que tous les polygones visibles sont affich s Par contre on risque parfois d afficher beaucoup de rectangles inutiles parce qu on un petit bout de leur colonne est visible m me s il n y a pas de polygones dans la partie qu on voit ce qui fait que les performances sont moins bonnes qu avec la 1 re m thode Et quand quand on affiche un rectangle on affiche tous ses polygones quelle que soit leur hauteur donc par exemple si on est au dessus du sol on va quand m me afficher tous les polygones du sous sol qui appartiennent aux rectangles du champ de vision ce qui diminue les performances quand il y a des tages On verra que les octrees r pondent ce probl me Clipping l horizon On remarque en testant le programme que les performances varient beaucoup selon l endroit du monde o l on regarde Par exemple si on se met en hauteur et qu on regarde en bas on voit tous les polygones du monde et le nombre d images par seconde est aussi bas que s il n y avait pas de quadirees Par contre si on se place dans un coin et qu on oriente la cam ra vers une tour la rapidit sera optimale Parfois les terrains sont immenses et on ne peut pa
44. de l arbre subdivise de mani re hi rarchique l espace en deux selon un plan Le n ud racine subdivise le monde l espace en deux sous espaces puis chacun des deux fils subdivise son tour l un des deux sous espaces en deux nouvelles parties La division se r p te de mani re r cursive jusqu ce que l on ait attribu un sous espace chaque l ment de base l l ment de base tant un ensemble de polygones coplanaires qui sont les faces du monde afficher Cette structure de donn es permet de d terminer les l ments de base qui ne se trouvent pas dans le champ de vision donc qu il n est pas n cessaire d afficher en se servant des propri t s de parcours des arbres possibilit d liminer le traitement co teux en temps processeur et en ressources graphiques d un branche enti re de l arbre sur le r sultat d un test peu co teux en temps processeur sur un n ud de l arbre Limitation des arbres BSP Avant de d crire plus en d tail leur fonctionnement il faut pr ciser que la r alisation d un arbre BSP n cessite un temps de calcul si important qu il n est pas possible de le construire dynamiquement pendant l ex cution m me en essayant de le calculer au chargement du programme En effet il faut plusieurs minutes on peut m me arriver un temps de calcul de l ordre de heure en fonction de la puissance de l ordinateur et du nombre de polygones constituant le monde pour construire un arbre BSP de mani re ef
45. deux cubes elle se trouve donc dupliqu e ce n est pas tr s optimal et dans une version ult rieure il sera n cessaire de corriger ce point par exemple travailler avec des pointeurs sur objet et placer un bool en qui nous dit si une face a d j t affich e par un autre n ud ou pas On parcourt donc tous les objets de notre sc ne et apr s traitement des faces on distribue dans chacune des huit listes correspondant au huit nouveaux n uds les objets qui apparaissent respectivement dans les huit cubes o Etape 4 Cr ation des nouveaux n uds lancement de la r cursivit A partir de la on poss de les huit listes correspondant aux huit sous n uds nous reste plus qu a cr ces n uds en leur attribuant chacun leur liste respective Il est vident que si une liste est vide on ne lance pas de r cursivit avec la liste vide sinon on lance la r cursivit pour chacun de ces n ud en retournant l tape 1 Voici une image mettant en valeur la r cursivit On autorise seulement le stockage dans les cubes TOP RIGHT FRONT et BOTTOM RIGHT FRONT Toutes la map a t charg e mais seuls les deux cubes souhait s sont remplis La Classe VisualOctree Cette classe sert uniquement au stockage des lignes d finissant les cubes des noeuds Voici sa stucture class VisualOctree private Il liste des lignes vector lt Coord3D gt vLines On remarque dans la structure Octree la pr sence de la
46. dice 2 est un portail reliant la pi ce 3 la pi ce 4 L algorithme en lui m me reste inchang on lance une r currence et pour tous les polygones de la pi ce Si il est visible on l affiche La d mo marchait bien mais il me restait encore 2 choses r gler Le clipping et la diminution de frustum Visiblit clipping vs Bouding Box Depuis le d but de ma partie du rapport je me sers du terme voir si je vois le portail p alors je vois la pi ce B Si je vois le mur i alors je l affiche Et j ai pr cis qu un polygone tait visible si il tait dans le frustum Il faut donc que j explique ce test de visibilit Pour expliquer cette notion je vous propose des rappels de ce qu est le frustum et ma mani re de le cr er Si vous avez d j lu le petit article de Jean Fran ois Fourmond ce propos Vous trouverez s rement des redites mais je pense tre plus pr cis au niveau g om trique et analytique Nous vous conseillons donc de lire les deux pour avoir une vue d ensemble et de commencer par celui de JF pour les sch mas les classes Frustum et Cam ra Un frustum est li une cam ra nous allons nous int resser celle ci en premier lieu La classe Cam ra la classe cam ra repr sente l avatar que l utilisateur d place dans le monde virtuel elle est caract ris e par une vitesse une position et 3 angles heading Yaw pitch et roll cf figure ci dessous Z heading rev roll
47. e ensuite on veut r cup rer le points d intersection sur le plan d ou vPosition vCenter vOffset o Etape 3 Le point d intersection est il dans le p rim tre du polygone Une fois qu on a le point d intersection on doit regarder si le point d intersection est l int rieur du polygone ou pas Si c est le cas c est qu il y a collision entre la sph re et le polygone sinon on passe l tape 4 pour une derni re tentative Comment savoir si le point d intersection trouv appartient au polygone C est le r le de la fonction bool nsidePolygone On sait que le point appartient au m me plan que le polygone donc on peut r duire le probl me en 2D Voici un sch ma qui rend le probl me trivial point dans le triangle paint hors du triangle wB AYB b ntersection VA WC somme des angles 360 Intersection somme des angles 360 Comme on peut le constater il suffit de faire la somme des trois angles et regarder si elle est gale 360 degr s ou 2P1 Pour cela on cr les vecteurs vA vintersection VB vintersection et VC vintersection puis on fait appelle a une fonction qui calcul l angle entre les vecteurs deux deux Le calcul de l angle entre deux vecteurs se retrouve facilement voici deux vecteurs on cherche alpha Paint inside norme vA norme vB cos alpha produitScalaire vA vB d ou alpha acos produitScalaire vA vB norme vA norme vB Donc dans l hyp
48. e Plan Visibilit Une fois tous les plans calcul s on peut alors faire des tests de visibilit Dans le cas de la derni re d mo pr sent le test de visibilit s apparentait un test de Bouding Box Ainsi un polygone tait consid r comme visible si au moins un de ces sommets tait pr sent dans le frustum Les explications de ce cas de figure sont faites dans l article de Jean Fran ois Or si les deux Sommes taient l ext rieur du frustum et que le polygone coupait le frustum comme dans le cas du grand segment du milieu sur la figure ci dessous Le polygone tait consid r comme non visible alors qu il l tait effectivement La solution ce probl me a t de clipp les polygones sur le frustum Clipp signifie r cup rer la partie du polygone se trouvant dans le frustum Pour cela je me suis servi de l algorithme de Sutherland Hodgeman Voici en pseudo code C la mani re dont je l ai impl ment C est une version pur e d un post que j ai plac dans le wiki donc il se peut qu il y ai des encore des erreurs Appel bool clipPolygone listePolygonelfi new Polygone Variables ArreteCourante c est un segment out in et in out selon le type de rep re main gauche ou main droite point inter point d intersection de l ArreteCourante avec le plan si il a lieu d etre Pseudo Code bool clip Polygone p Polygone pRes lles deux points courants Point extermit Point origine bool cli
49. e rectangle en 4 rectangles gaux et de m me proportions que celui qui les contient chacun des 4 rectangles cr s a pour taille en X et en Z la moiti de la taille du rectangle qui a t coup Chaque fils du n ud racine sera associ un de ces rectangles Chaque n ud fils avec son rectangle associ Ci dessus et dans le programme on a choisi d associer le premier fils au coin haut gauche le deuxi me fils au coin bas gauche le troisi me fils au coin bas droite le quatri me fils au coin haut droite Ensuite chaque rectangle associ un fils pourra tre divis en 4 et ainsi de suite On partitionne donc r cursivement l espace en rectangles On appellera profondeur le nombre de fois qu on divisera le monde en rectangles Cette profondeur correspond la hauteur du quadtree Le rectangle initial correspond une profondeur de 1 e Ici en profondeur 3 Comme on le voit ci dessus chaque feuille du quadtree est associ e une partie du monde donc chaque feuille conna tra les polygones situ s dans le rectangle correspondant A quoi a sert Si on se contente de d couper le monde en rectangles a ne changera rien la vitesse d ex cution Les quadtrees servent quelque chose si on les utilise avec le frustum culling On a vu que le frustum culling consistait liminer les polygones hors du champ de vision de la cam ra mais aussi qu il serait trop long de tester si chaque
50. e texture un mat riau tous ces l ments sont donc des objets d finis par la classe Object3D On cr donc autant d objets que de groupes Le mod le contient au final un tableau de tous ces objets ainsi qu un tableau de tous les mat riaux n cessaires On y trouve aussi une fonction Draw permettant d afficher le mod le La Classe Object3D Cette classe englobe tous les l ments n cessaires la d finition d un objet c est a dire d un l ment du d cor ou du mod le On y trouve donc un tableau dynamique de sommets un tableau dynamique de faces l identifiant du materiau qui est l index dans le tableau des textures La Classe Loaderob Cette classe est donc le chargeur de fichier Pour l explication voici le d roulement de la mise en structure On ouvre le fichier en lecture On a des tableaux temporaires dans le loader on pr cise bien un tableau dynamique un vector utilisation de la STL car on ne conna t pas d avance le nombre de sommets que l on va lire et de m me pour les faces On lit des sommets et on les stocke dans le tableau temporaire des sommets ensuite on lit des faces et on les stocke dans le tableau temporaire des faces Si lorsqu on est en train de lire des faces une information concernant un sommet est lue en l occurence le caract re lu est un v c est que l on vient de finir de lire un objet donc un l ment du mod le auquel cas on construit un nouvel objet partir des tableaux te
51. en fonction de leur diff rence de faces avant arri re En effet on attribut un score chaque face de la liste qui d pend des ces deux param tres et on garde comme pivot la face qui obtient le meilleur score Une m thode de calcul de score qui permet d obtenir d assez bons r sultats est Score Face Courante 2 x Nb Faces Coupees abs Nb Faces Devant Nb_ Faces Derriere Nb Faces Coplanaires La face obtenant le score minimum est lue pour servir de pivot J ai dit que cette m thode de calcul de score permettait d obtenir d assez bons r sultat En effet les meilleurs m thodes pour compiler les arbres BSP et choisir leurs pivots ont t test es et impl ment es par de grandes soci t de jeux vid o Id Software pour la saga des Quake Epic Games pour tous les Unreal et il semble tr s difficile d avoir des informations pr cises sur leurs travaux Initialisation de la bounding box de chaque n ud Le champ bounding box de chaque n ud va servir pour tester un n ud et liminer ventuellement le traitement d une branche de l arbre On l initialise de la mani re suivante Si le n ud est une feuille alors sa boite englobe toutes les faces de sa liste associ e Sinon elle englobe les faces de sa liste associ e et aussi les boites englobantes de ses fils Ce champ nous permettra de faire un test de visibilit pour les faces de la liste associ e au n ud et pour les n ud fils pendant l ex
52. ender Render E Blender Render E nr 3 _ Tr ere re i ER ro SE T TT Le ER a r a A Entr e du sous terrain Blender Render Le sous terrain Blender Render Plan du sous terrain vue de dessus V c136088 Faber CetTIES TANES LAS Mb JAIME Sites 1 even 00 ic Nous avons une classe Frustum commune que chacun utilisera en fonction des besoins de son algorithme Nous avons aussi impl ment un programme de d mo de frustum culling en 2D bas sur cette classe et vu de dessus cf Wiki Les quaditrees Les quadirees sont bien plus vieux que les jeux vid os en trois dimensions En effet les quadirees sont une structure de donn es invent e en 1974 par Finkel and Bentley et utilis e la base en traitement et en compression d images Nous verrons ici leur utilit dans les applications en 3D Qu est ce que c est Les quadirees sont des arbres 4 branches Ils vont permettre de diviser le monde en 3D en 4 parties Prenons l exemple d un monde sph rique Regardons ce monde vu de dessus Ses dimensions en X et en Z sont comprises dans un rectangle ou un carr si X Z e llustration monde en 30 rectangle contenant ce monde en 30 origine du repre OpenGL Ce rectangle va tre associ au n ud racine du quadtree II faudra toujours garder l esprit qu un n ud ou une feuille d un quadtree est associ un rectangle Maintenant on divise l
53. ens pr ciser que tous les calculs vectoriels et analytiques sont faits en 3D en se servant de Points ayant une coordonn e en z gale z ro Notions mises en jeux dans l algorithme Les notions primordiales sont Une pi ce est un secteur du monde virtuel Un portail est un polygone sp cial du monde virtuel il relie deux pi ces p1 p2 entre elles La r currence est le principe sur lequel est bas l algo Le frustum est un volume symbolisant le champs de la cam ra Le clipping est une technique qui permet de r cup rer la partie visible d un polygone Les pi ces les portails et la r currence le pr dicat de base et la r currence La classe pi ce est un secteur du monde le monde est form d un tableau dynamique de pi ces mais on s en sert comme une liste pour les fonctions de recherche d l ment C est un volume de l espace qui repr sente un pi ce de la vie de tous les jours salon chambre Deux pi ces peuvent tre reli es entre elles par un portail c est un polygone sp cial Apart Ici le terme voir signifie tre dans le frustum que ce soit en 2D ou en 3D c est la m me chose Imaginons un pi ce et une pi ce B mitoyennes reli es entre elles par un portail p figure 1 Si je suis dans la pi ce A et que je vois le portail p alors je vois la pi ce B Ceci est le pr dicat de base de l algorithme La figure 2 apporte un probl me int ressant En effet si je me trouve dans
54. eud Plane tabPlanesOfNodes 8 6 En tudiant cette structure on remarque que l on stocke dans un octree non pas un pointeur sur un objet mais un objet ce qui n est pas du tout optimal ni en m moire ni en temps d ex cution En effet cette modification r sulte de la tentative de clipping de polygone vue pr c demment qui modifie les objets Il est donc impossible de travailler avec des pointeurs sur les objets puisque l on stocke dans les n uds des objets diff rents Il est important de savoir ou est ce que l on va stocker les objets On peut les stocker soit dans les n uds terminaux soit dans chaque n ud de l arbre Nous avons choisi dans notre impl mentation de stocker les objets dans les feuilles de l arbre il n y a pas de raison pr cise Nous allons pr sent expliquer grossi rement comment on cr notre arbre o Etape 1 Cr er la racine a partir d une liste d objets Afin de commencer le processus r cursif il nous faut un point de d part la racine de l arbre On cr donc une variable de type Octree sur laquelle on peut lancer la r cursivit en appelant la fonction principale qui cr e l octree partir de la liste de tous les objets de la sc ne o Etape 2 V rification du cas d arret Doit on stopper la r cursivit ou pas On a choisi comme cas d arret de fixer l avance la profondeur laquelle on souhaite cr l octree La r cursivit va continuer tant que ce niveau de profondeur n
55. ficace Cette tape est appel e compilation de l arbre BSP Construction de l arbre BSP partir d un fichier monde Compilation Chaque n ud de l arbre contient les informations suivantes e un plan orient qui coupe une zone de l espace en deux une partie avant et une partie arri re e un ensemble de faces port es par ce plan e une boite englobante bounding box que l on remplira apr s les calculs des plans de coupe e un fils gauche et un fils droit de type n ud La racine de l arbre repr sente donc la premi re subdivision de l espace d acme Par convention on consid rera que le fils gauche contient les faces situ es devant le plan d fini par le n ud courant et que le fils droit contient les faces situ es devant le plan d fini par le n ud courant Apr s le chargement d un fichier repr sentant un monde on se retrouva dans la situation suivante en supposant que l on choisisse une liste cha n e dont chaque maillon repr sente une face Q ooo A partir de l on subdivise le monde en deux selon un plan de partitionnement afin de construire les fils du n ud Le plan de partitionnement est un plan porteur d une face du monde Nous verrons par la suite comment choisir judicieusement un plan de partitionnement Une fois ce plan choisit on distingue quatre types de face e les faces coplanaires ce plan que l on stockera dans une liste de faces que l on appellera liste assoc
56. i e au n ud e les faces plac es derri re le plan de partitionnement sont stock es dans la liste associ e au fils gauche e les faces plac es devant le plan de partitionnement sont stock es dans la liste associ e au fils droit e et les faces coup es par le plan de partitionnement qui ont la fois une partie devant et une partie derri re le plan Prenons l exemple suivant vue de dessus Ici le plan Pi porteur de la face F1 a t choisi comme plan orient de partitionnement la fl che bleue indiquant la partie avant du plan Les faces F1 et F4 sont coplanaires Pi et sont donc ajout es la liste associ e la racine de l arbre La face F2 est situ e devant le plan Pi et est ajout e la liste associ e au fils droit La face F3 est situ e derri re le plan Pi et est ajout e la liste associ e au fils gauche La face F5 quand elle est coup e par le plan Pi dans ce cas on coupe la face F5 en deux de la fa on suivante On calcule l intersection de Pi et de F5 et on d coupe F5 en F5f qui est ajout e l ensemble de faces situ es devant Pi liste associ e au fils droit et en F5b qui est ajout e l ensemble des faces situ es derri re Pi liste associ e au fils gauche Apr s la premi re subdivision on a un arbre dans la configuration suivante R E FI PC F2 F5f Fs Fse Choix du plan de partitionnement Afin d optimiser la future lecture de l arbre le choix du pl
57. i me vache est simplifi e 60 elle contient seulement 40 du nombre des polygones de la premi re De pr s on ne voit pas bien les diff rences avec la premi re alors de loin a passerait totalement inaper u e La troisi me elle est simplifi e 90 par rapport la premi re Dans Quake3 par exemple les personnages et les items armes bonus sont repr sent s en trois niveaux de d tails Le Level Of Details combin aux quaditrees donne de tr s bons r sultats Optimisation du frustum culling Pour savoir si un rectangle tait visible ou non on devait tester si chacun de ses 4 ou 8 sommets selon le mode de test tait l int rieur du champ de vision ou pas Il est possible de diminuer le nombre de tests en les rempla ant par un test d intesection d une sph re avec le frustum Cette sph re a pour centre le centre du rectangle tester et passe par tous les points du rectangle Son rayon est la distance de son centre n importe quel point Pour savoir si un rectangle est dans le champ de vision on calcule la distance entre son centre et les plans du frustum au lieu de calculer la distance entre chaque sommet du rectangle et les plans du frustum C est une approximation il peut y avoir des rectangles affich s alors qu ils sont non visibles mais a r duit le nombre de tests 1 au lieu de 4 pour chaque plan du frustum Cependant cette approximation est acceptable seulement quand les rectangles ressemblent
58. ils bas droit et fHD le fils haut droit e xmin zmin sont les coordonn e du sommet en haut gauche du rectangle associ au quadtree et xmax zmax celles du sommet en bas droite e list Object est un vector tableau dynamique de pointeurs vers les objets 3D Avec cette m thode de nombreux polygones risquent d tre affich s plusieurs fois c est pour a qu un bool en isDisplayed a t rajout dans la classe Object3D Quand on affichera un objet d une feuille du quadtree on le marquera comme d j affich pour qu il ne soit pas encore affich par les autres feuilles Ceci est possible parce qu on a des pointeurs vers un tableau d objets global dans les feuilles Quand on modifie un Object3D a le modifie donc pour toutes les feuilles On a parl du remplissage mais pas de la cr ation des quadtrees Avant de remplir l arbre il faut le cr er Il y a plusieurs fa ons de d terminer quelle hauteur de l arbre s arr ter e La premi re est de s arr ter de cr er des fils quand le rectangle associ un n ud a une taille inf rieure une taille fix e e La deuxi me pourrait tre de s arr ter quand les rectangles contiennent moins d un certain nombre de polygones mais elle ne peut tre utilis e que dans des mondes en 3D o les polygones sont r partis p riodiquement sinon on ne conna t pas l avance le nombre de polygones contenus dans les rectangles e La troisi me celle utilis e ici est de d cider
59. iser les temps de rendu OpenGL dispose dans son API de listes d affichage Une petite explication s impose lorsque le programme envoie une face la carte graphique pour l afficher il le fait par le bus AGP Donc chaque fois qu une face est envoy e vers la carte graphique on paye un passage par le bus AGP Open GL offre la possibilit d envoyer les faces par groupe gr ce aux listes d affichage donc de ne faire qu un trajet par le bus AGP pour un ensemble de faces De plus les faces contenues dans la liste d affichage sont compil es afin d obtenir un temps de calcul position clairages reflets transparence plus rapide sur ces faces Mais l utilisation d une liste d affichage n am liore r ellement les performances que si la liste contient au moins 200 faces En se basant sur ce que l on sait maintenant sur les arbres BSP et les listes d affichage 200 400 faces est une longueur de liste associ e un n ud qui repr sente un bon compromis pour stopper la r cursivit de la compilation de notre arbre Conclusion sur le choix du pivot Les m thodes de choix de pivot bas s sur les comparaisons de faces sont en O n sur le nombre de faces de chaque n ud Les algorithmes sur les arbres BSP datent du d but des ann es 80 et de multiples recherche sur les choix de pivot ont t r alis es Aujourd hui on ne compare plus les faces uniquement en fonction du nombres de d coupe qu elles vont engendrer on
60. issantes Pour que a aille plus vite il va falloir liminer le plus possible de polygones qui ne sont pas visibles C est l qu interviendront le frustum culling et nos algorithmes Conception de l environnement Le sujet de notre TER tant l tude des algorithmes de partitionnement de l espace l objectif tait de concevoir un environnement compos d une quantit de polygones suffisamment importante pour voir une diff rence cons quente lorsque la cam ra virtuelle se d place dans l environnement non partitionn et lorsqu elle se d place dans l environnement partitionn gr ce un des algorithmes tudi s Le logiciel utilis pour r aliser cet environnement est Blender un logiciel de mod lisation 3D sous licence GPL RTE j TE PER EE iIa rera ee comme z Les op rations de conversion de formats de fichier ont t r alis es avec une version d valuation de Deep Exploration 3 M C rp dsgborstesn CHaccinafieghe Crise Syrth d igara HH PARLAK POSTES pea RITES ri 2 E all x SRB 8506 6 GE Aa EI A us Cm 000 to Ts LE Rendre Bathar Fije x i Ca i 7 4 ah Srca BMW Pile de Fis obj Y Sete 5 iPad Fe za Cour Rein LC Pense OURS Es cas Ce bein Pr Ces i LA ge ou OC ape per Faber G Lee fe des ne D CALE hi O Career r L ri C Dbe l ijen i x LA bia t LI rrer Some omes 5 P Ais H Chers U Fous SI aber as LE Eee LA Fe LU iieii Tiet i P
61. itionn es en position terminale Donc on peut dire que c est de l it ratif la hauteur de pile reste inchang e Je suis aller voir Mr Roy Professeur l UNSA afin qu il m aide me faire un jugement Or apr s des tests avec un de ses coll gues nous nous sommes rendu compte qu un programme compil avec g et ayant ces 2 fonctions void f1 f2 void f2 f2 int main F1 s arr tait tout seul au bout d un temps relativement court Ainsi la gestion de la r cursivit du compilateur g est elle floue N ayant pas encore d diteur de pi ces je n ai pas test mon programme avec un grand nombre de salles Et j ai du mal a avoir un point de vue quant son comportement avec un grand nombre de pi ces Conclusion et Annexes L algorithme d affichage des portails est donc un parcours de graphe non orient Ce graphe est repr sent par une structure physique de pi ces et de portails Les informations sur cette structure tant contenues dans un fichier annexes La recherche de la pi ce courante est lin aire par rapport au nombre de pi ce du monde et le parcours de graphe est en grand to de nombre pi ces nombre de portails Ce projet m a demand des connaissances aussi bien math matiques niveau Premi re Terminale S qu informatiques r currence Je tiens pr ciser que la m thode de d coupage d un monde virtuel gr ce aux portails est inusit e voire obsol te En effet on ne t
62. la pi ce A et que je regarde vers la droite Je vois le portail 1 donc je vois la pi ce B Mais je vois aussi la pi ce C via le portail 2 Ceci n est pas pris en compte dans le pr dicat c est ici qu intervient la notion de r currence Pour chaque pi ce visible je vais visiter tous les portails visibles associ s cette pi ce et it rer sur le pr dicat Ainsi pour le cas de la figure 2 l algorithme va permettre de consid rer que la pi ce C est visible de la pi ce A portail p Figure 1 piece E pi ce pi ce E pi ce C portall Figure 2 Mais on a alors probl me de cas d arr t Le processus d crit ci dessus est une boucle sans fin car de la pi ce A je vois le portail 1 Donc je vois la pi ce B et je consid re alors la pi ce B Dans la pi ce B je vois le portail 1 donc je vois la pi ce A et ainsi de suite Il faut donc marquer les pi ces et les portails d j visit s Ce processus s apparente donc a un parcours de graphe non orient en profondeur partir d un n ud sp cial Comment repr senter une pi ce et un portail L algorithme marche donc th oriquement il faut maintenant l impl menter A partir de maintenant je vais entrer dans les d tails de mon code J ai eu besoin d une structure de pi ce de portail et de frustum Voici un screenShot du premier prototype que j ai crit et un lien Enix Seulement les pi ces B E Portail
63. lision avec la sph re rayon de sph re 175 15 On observe que le nombre de polygones blancs en collision a augment Dans celle ci on a r duit la taille de la sph re et on s est rapproch pour bien observer la couleur dont chacun est d tour MOSS RMERTED NO i OMODE SPACE SPEED _ Moteur D TER Algo OCTREE 133 polygones test s 14 en collision avec la sph re rayon de sph re 51 89 Fonctions utilis es o bool IsOverlappsCameraWithCube Comme nous l avons vu cette fonction permet de savoir si il y a intersection entre un octree disons son cube et la sph re de la cam ra Nous avons en param tres les coordonn es du centre du cube x y z ainsi que sa taille width taille 2 Paint inside Sph re de la Cam ra position x position y position z Vue de dessus Vue 3D en pseudo code Si position x gt d1 alors distanceX position x d1 si position y gt d2 alors distance position x d2 si position z gt d3 alors distanceZ position x d3 si distanceX 2 distance Y distanceZ2 lt radius alors il y a intersection entre le cube et la sph re Le pseudo code crit ci dessus s applique dans le cas de figure du sch ma Il est vident que dans l hypoth se ou la sph re est de l autre cot du cube il est n cessaire d inverser les soustractions Voici l explication en 2D qui sera peut tre plus explicite Vue 2D Soit distanceX le segment bleu d
64. lle syntaxe et fait une nouvelle d mo Dont voici un screenShot et un lien vers l ex cutable Polygones sans Clipping polygone visible portail visible Ici le but tait de se passer de l affichage de la classe Piece le carr gris de la ere D mo et de n afficher que les polygones la formant les murs Deux nouvelles Structures de donn es apparaissent la classe Polygone et la classe Sommet qui lui est associ e Il a alors fallu que je r crive ma syntaxe Voici la nouvelle et derni re syntaxe sommet indice x y polygone indice indiceSommet1 indiceSommet2 pi ce indice indiceSommet1 indiceSommet2 linkPolygone indicePolygone indicePi ce portail indicePolygone indicePi ce1 indicePi ce2 Comme on peut le remarquer il n y a plus crit ni le nombre de pi ces ni le nombre de portails C est devenu inutile Je me suis inspir de la syntaxe des obj Donc la premi re chose faire est de charger tous les sommets Puis de cr er les polygones par exemple polygone 3 2 9 signifie que le polygone d indice 3 comme sommets les points d indice 2 et 9 Ensuite on crit les informations sur les pi ces de la m me mani re que pr c demment sauf que les coins sont des sommets charg s Apr s cela les polygones sont li s aux pi ces On peut et doit dans le cas des portails linker un polygone plusieurs pi ces Enfin on fait un setPortail sur certains polygones du monde portail 2 3 4 signifie que le polygone d in
65. llons voir comment utiliser les octrees pour d tecter les collisions II ne faut pas oublier qu un octree ne sert pas juste au rendu et peut tre utilis aussi bien pour la d tection de collision Dans notre impl mentation les collisions ne sont pas g r es physiquement au sens propre du terme c est dire que lorsque la cam ra se trouve en intersection avec un mur par exemple elle n est pas bloqu e En fait les termes appropri s dans notre cas sont d tection de collision c est dire que en temps r el lorsque l utilisateur se d place sur la sc ne nous seront en mesure d observer quelles sont les polygones qui potentiellement peuvent tre en collision et de plus les faces qui sont r ellement en collision avec notre cam ra La gestion des collisions fait appel des notions math matiques parfois un peu complexes et ainsi les diff rentes fonctions de base comme les fonctions d intersection plan sph re ou intersection sph re polygone ou autre fonctions de g om trie spatiale n ont pas t impl ment es de z ro mais ont t trouv s sur divers site consacr la programmation des jeux Ces fonctions ont t largement comment es dans le code et de plus nous allons les tudier dans ce qui suit Le travail a donc consist les implanter avec les octrees ce qui n est pas une mince affaire _ Premi re tape la cam ra Pour la suite nous allons devoir sch matiser le corps que l on veut d placer da
66. lus petits et le nombre de polygones affich s va se rapprocher du nombre optimal On pourra dans notre programme observer le nombre de polygones affich s par rapport au nombre total et la hausse du nombre d images par seconde que cela entraine e Exemple en profondeur 6 Cependant un parcours r cursif est co teux et quand la profondeur est trop importante les performances se d gradent Il faut qu une augmentation de profondeur se traduise par une baisse importante du nombre de polygones affich s pour tre efficace Concr tement On a vu qu un objet 3D tait une structure contenant un tableau de polygones et qu on avait une liste d objets 3D en variable globale Ici la solution choisie pour repr senter les polygones dans le quadtree a t de donner chaque n ud et chaque feuille un tableau de pointeurs vers les objets 3D du tableau global On a donc pas de duplication des objets 3D On a donc pas directement acc s aux polygones par le quadtree il faut passer par l objet qui les contient ce qui vite de faire trop de pointeurs et conomise donc de la place Il a fallu ensuite choisir o placer l acc s aux objets 3D dans les feuilles ou dans chaque n ud C est la premi re solution qui a t choisie on ne remplit que les vector des feuilles Les n uds interm diaires auront acc s aux objets r cursivement par leurs fils ce qui vite de copier les pointeurs chaque niveau Dans le moteur 3D de base cha
67. mations sur les sommets les faces ainsi que le NOM de la texture dont il est compos On rappelle qu un objet correspond un groupe donc une texture La seconde tape consiste donc parcourir tous les objets du mod le et associer chaque objet un identifiant correspondant un num ro de mat riau nous dirons qu un mat riau est caract ris par un identifiant de mat riau ainsi qu une texture On remarque que les textures ne sont toujours pas charg es en m moires C est le r le de la troisi me tape L objet Model3D poss de un tableau de Mat riau contenant les informations de tous les mat riaux intervenant dans la sc ne ou disons sinon tous les mat riaux dont les objets du mod le sont constitu s Ainsi il suffit de parcourir ce tableau de mat riaux et de cr la texture partir du nom de fichier Il en r sulte en fin de compte un tableau de texture index par un num ro d identifiant et contenant les donn es de textures d un mat riau d sign par cet identifiant Chaque objet ayant un identifiant de mat riau il suffit de charger lors de l affichage la texture contenue l index num ro d identifiant dans le tableau des textures Ce moteur permet donc de charger un univers en 3D et s y d placer mais tel quel dans un monde tel que celui qu on a cr compos de plus de 60000 polygones textur s le nombre d images par seconde est tr s bas peine plus de 10 images par seconde pour des machines tr s pu
68. mporaires que l on vient de remplir et on ajoute cet objet ainsi cr la liste des objets du mod le Petite pr cision technique puisque l on ne conna t pas d avance le nombre d objet dans le mod le les conteneurs utilis s d objets et de mat riaux pour le mod le sont des vector STL des tableaux dynamiques Par contre lorsqu on construit un objet avec des tableaux temporaires on conna t avant la taille des tableaux dynamiques on peut par cons quent allouer la place n cessaire c est pourquoi la classe Object3D travaille avec des tableaux et non des tableaux dynamiques Les fichiers obj ne contenant pas d information sur les mat riaux on va devoir les cr er et mettre en relation un objet et sa texture avec nos propres fonctions Il y a deux fonctions qui se chargent de a une qui ajoute un mat riaux et une qui met en relation un objet avec un mat riaux Nous d taillons ci dessous la fa on de proc der e Fonctionnement global Comment charger une sc ne et ou sont plac s les fonctions d appel Le chargement global de l objet lecture des donn es du fichier et chargement des textures se fait dans le fichier main cpp dans une fonction d initialisation La premi re tape et de charger le mod le notre monde partir d un fichier dans une variable donc de type Model3D A pr sent nous poss dons donc en m moire une variable de type Model3D contenant un tableau d Object3D ces derniers poss dant donc les infor
69. nde ou bien par le pourcentage de polygones de l environnement affich Ces deux m triques sont en troite relation dans la mesure ou le taux de rafra chissement d pend directement du nombre de polygones affich s pour une m me configuration mat rielle Dans un environnement ext rieur ils sont nettement moins adapt s En effet ces environnements disposent galement de plans de coupe mais les plans de coupe sont calcul s en fonction des meilleurs scores obtenus par les plans porteurs des faces de l environnement Et les meilleurs plans de coupe dans les environnements ext rieurs ne sont pas bons Les grandes tendues planes avec par exemple des arbres et quelques b timents obtiennent de tr s mauvais scores car ce type de configuration n autorise qu un volume de vision profond ce qui ne permet que l occlusion des n uds se trouvant derri re la cam ra L efficacit des arbres BSP est mettre en parall le avec la difficult de leur impl mentation En partant de peu de connaissances sur le sujet il a fallu tudier les structures de donn es r aliser un environnement vaste afin de voir les performances de chaque algorithme tudi apprendre utiliser un librairie telle qu Open GL impl menter un compilateur d arbres BSP et r aliser un moteur bas sur ces m mes arbres BSP en un temps excessivement restreint pour un tel volume de travail Les Portails Qu est ce qu un portail Les algorithmes base de portail
70. ns notre sc ne par une sph re en l occurrence notre cam ra La sph re reste une assez bonne approximation en terme de volume et de forme pour la plupart des objets joueur ou voiture par exemple On englobe notre cam ra par cette sph re en d finissant une donn e membre radius dans notre Classe Cam ra qui sera le rayon de la sph re Nous avons choisi de placer ce param tre r glable par l utilisateur afin de d tre en mesure de visualiser les diff rences de comportement selon la taille de la sph re e Octree amp d tection des collisions Les travaux vont s orienter principalement autour de deux l ments l arbre des octrees et la cam ra L objectif de la manipulation est de faire appel chaque rendu une fonction qui va utiliser l arbre des octrees en fonction de la camera Pour se faire on va cr une fonction OverlappsCamera Camera cam que l on appelle sur la racine de l arbre Principe Si la sph re englobante de la cam ra est pr sente dans un octree il y a possibilit quelle soit en collision avec les polygones de cet octree et il est impossible qu elle soit en collision avec les polygones des autres octrees Les test de collisions seront donc fait seulement sur un nombre de polygones pr cis ceux des octrees concern s et non sur tous les polygones de la sc ne De m me que pour l affichage le nombre de polygones tester est consid rablement restreint compar au nombre de polygones total comp
71. obl me avec cette m thode en effet tant que la cam ra est l horizontale tout s affiche correctement mais d s qu on l oriente vers le haut ou vers le bas des polygones risquent de ne plus tre affich s e Exemple Le probl me est que lorsqu on regarde vers le haut ou vers le bas la cam ra d forme la sc ne et des lignes verticales apparaissent pench es comme les murs dans l image ci dessus Si les murs apparaissaient droits il n y aurait pas de trous Si on fait attention on remarque qu au niveau du sol ici le sol est 19 en y et non 0 le mur qu on voudrait voir affich est totalement en dehors du champ de vision donc les quatre sommets du carr auquel il appartient sont gauche du plan left du frustum si le carr est assez petit donc si la profondeur est assez grande et donc il est normal que ce bout du mur ne soit pas affich e Illustration bord droit de l cran plan right du frustum bord d une rang e de briques le mur n est pas un rectangle g ant mais un assemblage de palygones carr s sol ici plan y 18 4 Si on veut voir correctement le mur il faut tester les quations de plans avec Y hauteur du mur et non plus Y 0 Ainsi cette hauteur les carr s contenant le mur sont dans le champ de vision e ici on teste avec y 29 Seulement maintenant il risque d y avoir des trous au niveau du sol si on oriente la cam ra trop bas alors qu avant il n y en avait pas
72. on regarde vers le plafond on va voir le ciel C est normal on teste si les carr s sous nos pieds sont au dessus de notre t te Bien sur le test est n gatif donc on affiche pas tous les rectangles qui ont leurs 4 sommets derri re le plan near du champ de vision de la cam ra e llustration partie affich e de l objet partie non affich e de l objet plan near du frustum Fi objet afficher c t d un carr correspondant un quadtree cam ra En fait cette m thode n est satisfaisante qu avec des applications o les polygones sont tous pos s sur un seul plan et o on ne peut pas orienter librement la cam ra Typiquement des jeux de courses de voitures ou de strat gie avec vue de dessus par exemple Mais pour les jeux de type FPS a ne convient pas et il faut trouver une autre solution 2 me m thode La 2e m thode est plus lente mais elle permet d afficher dans tous les cas tous les polygones visibles II faut pour cela ne plus consid rer des rectangles sur un plan horizontal mais les lever dans l espace en colonnes Le haut de ces rectangles sera la coordonn e Y maximale du monde en 3D et le bas le Y minimal e Exemple e llustration avec le moteur 3D Le programme permet de passer d une m thode l autre Voir le mode d emploi fourni en annexe sur le Wiki pour conna tre les fonctionnalit s associ es chaque touche Pour savoir si un rectangle est
73. on dans notre cas un champ de vision comme on verra plus bas e Ce moteur 3D permet le m me type de contr les que les jeux de type FPS o on marche avec le fl ches du clavier en avant ou en arri re en pas chass s strafe o on s oriente avec la souris horizontalement 360 l utilisateur choisi son sens de rotation verticalement 180 on peut au maximum regarder au dessus de nous on en dessous pas en arri re e 2 modes de d placement sont propos s o Un mode de d placement dans le plan C est le m me mode que dans les jeux de type FPS on marche sur un plan horizontal qu on choisit et on y reste Par exemple si on regarde en haut et qu on avance avec le clavier on va marcher en avant tout en regardant en haut mais toujours en restant au niveau du sol Ce mode est accompagn d une modification l g re de la position de la cam ra en Y selon la fonction sinus Ainsi la cam ra monte et descend quand on avance de mani re simuler un effet course pieds o Un mode de d placement dans l espace Le mode de d placement dans le plan n est pas tr s pratique pour bien observer tout le monde en 3D et les effets des algorithmes de partitionnement c est pourquoi nous avons rajout un mode de d placement dans l espace Dans ce mode on est plus attach au sol et on peut voluer librement dans l espace Maintenant quand on regarde en haut et qu on veut avancer avec le clavier on va monter dans l esp
74. onde dans lesquelles seules les faces qui chevauchent au moins deux cubes sont affich es Celle de gauche en profondeur 1 et non textur e celle de droite en profondeur 4 et textur e RE D mn a ii HS A Jr j Suite de longues heures d impl mentations et bien que th oriquement le clipping de polygones tait possible la poursuite de cette impl mentation n a pu arriver terme en effet apr s notre rendez vous avec Michel Buffa il s est av rer que la mise en place du clipping de polygones n tait pas n cessaire nous ne l avions pas cit dans le cahier des charges et ainsi certains facteurs comme le manque de temps nous a incit stopper en cours notre progression Cependant son impl mentation a t r alis e et la majeure partie restante du travail se situe dans la correction d erreurs Classes et Structures La Classe Octree Voici comment elle est structur e Class Octree private 1 tableau des 8 branches descendantes du noeud courant Octree tabOctreeNodes 8 permet de savoir si on a subidvis le noeud courant ou pas bool subdivided I taille du cube pour le noeud courant float widthNode I Centre X Y Z du noeud courant Coord3D centerOfNode 1 stocke les objets qui devront etre affich s avec ce noeud Object3D m_pObject3D le dessin du cube repr sentant l octree du noeud VisualOctree visualOctreeOfNode I tableau des 6 plans du cube du no
75. onsid rer les cases qui sont en dehors de son champ de vision On a donc d j un algorithme permettant de simplifier la quantit de donn es traiter Ceci n est qu un exemple simple nous verrons dans ce rapport que de nombreux cas se pr sentent et qu un simple algorithme base de grille ne suffit pas toujours Les quatre algorithmes les plus utilis s seront pr sent s chacun portant le nom de la Structure de donn es sur laquelle il est bas e Pour chacun des programmes de d monstration but p dagogique ont t r alis s Monsieur Buffa compte les utiliser l an prochain pour illustrer son cours Les algorithmes tudi s sont Quaditrees Jean Fran ois Fourmondi Octrees St phane Mariani Portails Jean Fran ois Righi Arbres BSP Binary Space Partition tree Xavier Medioni Par ailleurs pour illustrer ces algorithmes un moteur 3D a t r alis version beaucoup plus aboutie que celui d velopp en cours Il utilise la librairie OpenGL et la librairie SDL Il est noter qu en TP de synth se d images nous avons d velopp le moteur 3D from scratch sans l aide d aucune librairie ce qui nous a permis de bien comprendre les m canismes internes L utilisation d une librairie 3D telle qu Open GL s est donc trouv facilit e Ce moteur 3D sera d taill dans une section d di e Pour nous faire une id e des avantages et inconv nients de ces algorithmes nous avons cr e un environnement en 3D
76. osant notre monde C est dans ce principe que r side l int r t du partionnement d espace o Etape 1 V rifier la position de la camera Au d part on lance la fonction sur la racine de l arbre On rappelle que la racine de l arbre est un n ud auquel on associe un cube englobant toutes la sc ne On va donc v rifier si notre cam ra est dans ce cube ou pas Il faut bien avoir l id e que si la cam ra n est pas pr sente dans ce cube il n y a absolument aucune chance qu elle soit en collision avec les polygones de ce cube Pour cela on va utiliser la fonction sOverlappsCameraWithCube qui prends en param tre les coordonn es du centre du cube octree sur lequel on fait les tests d intersection avec la sph re ainsi que la taille du cube Si un cube intersecte avec notre cam ra alors les polygones de ce cube deviennent potentiellement aptes tre en collision avec notre sph re gt on va alors l tape 2 Sinon si le n ud est subdivis alors on lance la r cursivit sur chacun de ses fils puisque les polygones sont stock s dans les feuilles o Etape 2 D tecter les polygones Si l on est ici c est que la sph re englobante de la cam ra intersecte avec un cube Tous les polygones sont donc potentiellement suspect pour la collision Pour obtenir une vue loign e afin de bien comprendre le rayon de la sph re a t tr s largement augment Voici deux images de profondeur diff rentes la premi re de profondeur
77. oth se o le point d intersection est dans le p rim tre du polygone il y a collision Sinon on passe l tape 4 o Etape 4 V rifier si la sph re intersecte avec les ar tes du polygone Ici le point d intersection n est pas dans le p rim tre du polygone Comme on travaille avec une sph re on peut encore tre en collision cause du rayon de la sph re Pour cela il faut calculer le point le plus proche appartenant une arr te du polygone Ceci est fait en prenant le point pour lequel la distance point d intersection point le plus proche sur une arr te du polygone est minimale Il va falloir faire ceci sur chacune des trois ar tes du triangle La fonction bool EdgeSphereCollision renvoie vrai si un point de la sph re intersecte avec une des ar tes du triangle faux sinon Si n importe quelle partie de la sph re intersecte avec les ar tes du polygone alors il y a collision Ceci est fait uniquement si le centre de la sph re est l ext rieur des ar tes du polygones Pour chaque ar te du polygone on doit trouver le point le plus pr s du centre de la Sph re Si la distance de ce point est inf rieure au rayon de la sph re il y a collision Comment trouver le point d une ar te le plus proche de la sph re voici un sch ma explicatif Paint inside vCenter Le principe est assez simple on cr les vecteurs vA vCenter et vA vB et on calcule le produit scalaire des deux vecteurs ce
78. p true int cptSegmentsClip s lt Sommet gt listeSommets vide lt Sommet gt listeSrc p gt toSommets cr e une liste de sommets qui definissent le polygone Pour toutes les arretes faire on parcourt toutes les arretes il faut un pointeur sur l arreteCourante extremit arreteCourante S1 origine arreteCourante S2 Pour chaque plan du volume faire float distanceFromOrigine Toplan d1 plan distance origine float distanceFromOrigine Toplan d2 plan distance extremit Selon le signe de d1 et d2 il y a 4 cas possibles out clip false ce segment n est pas dans le volume c est sur IN in out pointinter Point pointinter calculerintersection extremite origine plancourant extremit pointinter out in pointinter Point pointinter calculerintersection extremite origine plancourant origine point inter return clip Ainsi dans la derni re version de ma d monstration lien ne sont affich s que les parties visibles des polygones Le recalcul du frustum Un probl me reste encore r gler illustrer par ce screenshot y Z bug occlusion Ici il y a un portail consid r comme visible alors qu il ne l est pas Le frustum doit tre recalculer dans le cas o l embrasure du portail est petite C est le m me principe que le lancer de rayon ray casting et est loin d tre un probl me trivial Dans la d monstration v0 9 5 en mode nightmare j ai commence
79. peut donc se promener avec beaucoup d images par seconde Optimisations possibles Level Of Details Mais le clipping l horizon est rendu obsol te par les capacit s des cartes graphiques actuelles Nicolas Peri nous a dit qu aujourd hui une m thode tr s utilis e est le Level Of Details LOD Nous ne l avons pas impl ment mais voici des explications On calcule tout d abord plusieurs repr sentations du monde en 3D plus ou moins d taill es Au lieu de ne pas du tout afficher les objets trop lointains et de le masquer par du brouillard on affiche une simplification des objets Par exemple les statues de notre monde contiennent chacune plusieurs milliers de polygones Cela ne sert rien d en afficher autant quand on est l autre bout du monde car on ne peut les distinguer On ne verrait pas la diff rence avec un assemblage d une dizaine de polygones constituant une statue avec une forme tr s simplifi e C est ce que permet le LOD Pour chaque feuille du quadtree visible on affiche une repr sentation ou une autre des objets qu elle contient en fonction de la distance qui la s pare de la cam ra Les repr sentations simplifi es sont calcul es en fusionnant des polygones voisins Un programme comme VizUp fait a tr s bien Nous l avons test avec une version VRML de l objet vache du cours de synth se d images e Voici des images e La premi re est la vache normale avec tous ses polygones e La deux
80. polygone est visible ou pas Les quadtrees permettent d liminer un grand nombre de polygones tr s rapidement Pour ce faire au lieu de d cider si chaque polygone du monde est dans le champ de vision ou non on va d cider si un rectangle contenant des polygones est dans le champ de vision ou non Ce qui va diminuer de beaucoup le nombre de tests effectuer Explications consid rons un monde en 3D carr toujours vu de dessus Imaginons qu il contient 4096 polygones triangulaires r partis uniform ment dans le carr Tester si chaque polygone est visible reviendrait faire 4096 3 sommets 12288 tests pour n afficher que les polygones visibles et aucun autre Maintenant si on teste si les carr s qui les contiennent sont dans le champ de vision de la cam ra que va t il se passer On teste d abord si le carr encadrant le monde est dans le champ de vision Si non a veut dire que la cam ra est hors des limites du monde le dos tourn vers l ext rieur Donc on arr te et on affiche aucun polygone Si oui on va ensuite regarder les 4 carr s correspondant aux fils de la racine du quadtree Si ils ne sont pas dans le champ de vision on ne s en pr occupe plus Si ils ont visibles enti rement ou en partie on va encore les diviser en 4 et consid rer leurs fils jusqu une certaine profondeur sp cifi e avec 1 lt profondeur lt hauteur du quadtree Par exemple sur l image ci dessous tir e du programme de d mo de fru
81. que image on parcourait le tableau des objets 3D et pour chacun on affichait tous ses polygones Maintenant on part de la racine du quadtree et on descend jusqu la profondeur voulue en liminant les branches correspondant des rectangles hors du champ de vision Si on est au niveau des feuilles on affichera le contenu de chacune d elles Sinon on descendra r cursivement des n uds o on se trouve jusqu aux feuilles pour les afficher Voici comment on r partit les objets dans les diff rentes feuilles Pour chaque objet on consid re sa bounding box Si un des sommets de la bouding box est situ l int rieur du rectangle associ une feuille on ajoute un pointeur vers l objet au vector de cette feuille Pour aller jusqu aux feuilles on part du n ud racine et on descend r cursivement en ne consid rant que les n uds fils dont le rectangle contient au moins un sommet de la bouding box Illustration sur un exemple simple on a un quadtree de hauteur 2 et un objet 3D form d un seul polygone triangulaire Le rectangle rouge est sa bouding box toujours vue de dessus On voit que 2 feuilles sur les 4 auront dans leur vector le m me pointeur sur l objet Ceci nous fait une structure simple de quadtree dans le code class Quaditree public Quadtree HG BG fBD HD int xmin zmin xmax zmax vector lt Object3D gt list Object e fHG est le fils haut gauche fBG le fils bas gauche fBD le f
82. r impl menter une piste pour r gler ce probl me J extrait le point m dian d un portail quand il est clipp par le frustum L algorithme Voici un squelette de l algorithme C est un r sum de ce que l impl mentation faite dans la classe Monde L algorithme en lui m me est divis en 3 fonctions affiche affichePiece affichePortail affichePiece et affichePortail s appellent l une l autre ces appels se font en position terminale cf Annexe Au moment o la carte graphique demande une nouvelle frame trame afficher la fonction affiche est appel e La premi re action de cette fonction est de recalculer le frustum selon la position et les angles de la cam ra ici le Heading seulement La seconde est de trouver la pi ce courante o se trouve la cam ra Une fois cette pi ce connue la fonction affichePiece pieceCourante est appel e La premi re action entreprise dans cette fonction est de marquer la pi ce comme ayant t visit e La seconde est de clipper tous les polygones sur le frustum Cela revient trouver si ils sont visibles et plus pr cis ment extraire leur sous partie visible si cette partie est nulle le polygone n est pas visible Si ce polygone est normal un mur par exemple on l envoi la carte graphique faire des paquets et non un par un Si ce polygone est un portail non marqu la pi ce voisine associ e ce portail est dans le champs de vision Don
83. rei O her L She Local 20 modes Textres Shusiers Maine Le Que DO GOOM EMA D GA el sem i La a i z Dat e D Tip isades in i maeror Fra 500 arida L environnement qui a t con u a t model dans le but d tre compos d une multitude de polygones Par exemple au lieu de se servir d un seul grand polygone rectangulaire pour repr senter le sol j ai pr f r utiliser une multitude de dalles mises bout bout Au final l environnement est compos de plus de 60 000 polygones Pour pouvoir avoir un ordre de grandeur les niveaux de Quake Id Software sont compos s d environ 10 000 polygones J ai essay de reconstituer un environnement similaire celui du film Troie sorti le 13 Mai en France avec Brad Pitt Orlando Blum Diane Kruger dont voici certains clich s du tournage Le d lai impos pour rendre le TER ne m a h las pas permis de m attarder trop longtemps sur la r alisation de l environnement Il se d compose en une muraille avec des tours afin de d limiter l environnement un temple entour par un plan d eau des marchands d armes un labyrinthe sous terrain nt Sn Vue d ensemble BlenderRender La muraille Blender Render Le temple Blender Render Blender Render Blender Render Temple vu de l int rieur Blender Render E Mhe Un marchand d armes Blender Render 1 4 0 x Bl
84. rouve que le jeu Descent Parallax software qui soit bas dessus et il date de plus de 10 ans Ce qui repr sente beaucoup dans le monde du jeu vid o Les 3 axes de rotation de la cam ra taient libres c est la raison pour laquelle ce produit tait malheureusement peu jouable Mais c est en partie cause du monopole du moteur de Quake qui t repris par tous les FPS depuis les derni res ann es Pour conclure je pense qu un jeu 3D bas sur les portails n apporterait rien a l univers du jeu vid o Mais le principe d occlusion culling et de frustum 2D peut tre repris sur des plateformes de types t l phone portable PDA en r seau par exemple Je vous ai pr sent ici tout le travail concernant l impl mentation des algorithmes des portails Or je n ai pas fait que a pendant ce TER j ai aussi aider Xavier concevoir le Monde De plus j ai eu plusieurs id es qui me sont venues lors de l impl mentation et je vous les pr sente dans les annexes du Wiki Enfin je voudrais finir par dire que le C n est peut tre pas l outil id al pour faire des maths et un langage comme Mapple me semble plus adapt Synth se sur l tude de ces algorithmes Quadtrees Octrees Arbre BSP Portails Environnement optimal ext rieur plat ext rieur int rieur int rieur Construction de gt D RT _ l ex cution f l ex cution l ex cution pr compilation arbre _ graphe non Re de perpendi
85. s afficher les polygones jusqu l infini De plus il y a souvent de fortes chances pour que les polygones lointains soient cach s par d autres polygones plus proches et donc pas ou tr s peu visibles La solution utilis e dans de nombreux jeux vid os est de clipper les polygones l horizon De la m me mani re qu on ne souhaite pas afficher les polygones qui taient gauche ou droite du champ de vision de la cam ra on n affichera pas ceux qui sont plus loin que le plan far du frustum Au lancement du programme le plan far est une distance de 1000 unit s Open GL de la cam ra ce qui fait que quelque soit l endroit l int rieur des murailles o l on se place si on est au niveau du sol on pourra quand m me voir les polygones les plus loign s Le programme permet d avancer ou de reculer ce plan far par rapport la cam ra Le probl me quand on n affiche pas les polygones qui sont derri re le plan far est que a cr e une coupure tr s visible qui n est pas agr able pour l utilisateur Pour r soudre ce probl me notre programme comme un certain nombre de jeux utilise le brouillard fog On rajoute avec Open GL un effet de brouillard au niveau de la cassure qui la masque progressivement e La m me image sans et avec brouillard Le fait d avancer le plan far et de mettre du brouillard est tr s pratique dans les couloirs de notre sous sol par exemple o l on n a pas besoin de voir tr s loin et o on
86. s un environnement ext rieur et sans tages Dans notre environnement ce n est donc pas l algorithme le plus efficace En fait nous nous sommes aper us que les quadirees ne sont pas vraiment adapt s aux jeux 3D de type FPS o l orientation de la cam ra est libre et les niveaux tr s vari s Les Octrees Introduction Un octree est une mani re de subdiviser l espace 3D Le premier objectif des octrees est de r duire le nombre de comparaisons requis afin de d terminer les polygones de notre monde que l on va traiter qu il s agisse d affichage de tests de visibilit de tests de collision ou bien de niveau de d tails Les octrees engendrent une r duction significative du temps requis pour trier les polygones dans un monde et les afficher et ils s av rent tre le plus optimal pour des jeux pr sentant de grandes variations relativement un axe par exemple Flight simulator Il est important de comprendre que l application de l algorithme des octrees n est qu une tape dans le processus d limination des surfaces et ainsi son unique utilisation sera inutile et engendrera une perte de performance consid rable En effet celui ci doit tre coupl au processus d limination en fonction du point de vue Frustum culling Il existe deux formes d OSP Octree Space Partionning 1 les OSP travaillant sur les objets de la sc ne 2 les OSP travaillant sur le volume de l espace que forme notre monde La premi re forme d OS
87. si on faisait tous les calculs rotations de matrices projection du monde 3D sur l cran en 2D placage de textures etc nous m mes car a d charge les CPU des t ches li es l affichage N tant pas familiaris s Open GL auparavant nous avons avant tout d apprendre l utiliser Architecture Notre moteur 3D est inspir d un exemple de GameTutorials mais a t totalement repens et modifi Il conserve toutefois des bouts de code comme l initialisation de la SDL et d Open GL la gestion des v nements ou le calcul du nombre d images par seconde Le moteur 3D de base est constitu d un fichier main cpp qui r agit aux v nements avec la SDL d une classe Camera d une classe Scene et d une classe Coord3D La classe Coord3D correspond une coordonn e dans l espace X Y Z La classe Camera a les attributs suivants e Un de type Coord3D qui repr sente sa position dans l espace e Un autre de type Coord3D qui repr sente le point de l espace que la cam ra regarde point de vis e e Un 3e de type Coord3D qui repr sente le vecteur directeur vertical Avec ces 3 attributs on pourra se d placer dans l espace en utilisant Open GL Les v nements clavier et souris enregistr s par la SDL modifieront la position et le point de vis e de la cam ra ce qui la fera se d placer La classe Scene s occupe de l affichage du monde en 3D chaque tour de boucle la classe Scene dessinera le monde en 3D en fonc
88. ssus Impl mentation Stockage des Octree Conception de l arbre Introduction Une fois les donn es du fichier mises en m moire il faut maintenant cr er les octree comme d finis en th orie Pour cela on a cr un module Octree ainsi qu un module VisualOctree Au cours de notre impl mentation nous avons sugg r bien que cela ne soit pas rentable au niveau performance de clipper les polygones lorsque ceux ci se trouvent cheval sur deux cubes Cette notion de clipping a constitu temporellement une entrave dans notre progression c est pourquoi une section consacr e celui ci a t vot e afin d expliquer les probl mes rencontr s et pourquoi son impl mentation n est pas arriv terme e Le probl me du clipping de polygones o Mise en situation Clipping signifie coupure Alors pourquoi souhaite t on couper un polygone De mani re g n ral on coupe un polygone au niveau du champs de vision effectivement a ne sert a rien de balayer un polygone dans sa partie externe du champs de vision Ici ce n est pas de a qu il s agit On souhaite couper les polygones qui chevauchent des cubes lors du d coupage du monde en cube Reprenons l exemple de la tour toujours les deux modes de rendu M A r E a ppr 1 Moteur 30 TER Algo OCTREE OOW a Moteur 30 TER Algo CCTREE LL Supposons que l on garde seulement la partie d tour e en vert on obtient ceci mm Moteur 3D TER
89. stum culling en 2D fourni en annexe on est en profondeur 4 Le champ de vision est repr sent par les segments rouges la cam ra peut ici voir l infini Les carr s gris s sont ceux qui sont visibles par la cam ra On affiche donc tous leurs polygones e llustration Chacun de ces carr s contient 4096 43 soit 64 polygones On a 8 carr s en gris donc on affiche 512 polygones sur 4096 On remarque qu il y a des polygones qui ne sont pas visibles mais qui sont quand m me affich s parce qu un bout du carr dans lequel ils sont contenus est visible Le nombre de polygones affich n est pas minimal Mais regardons le nombre de tests effectu s e 4 tests pour le carr initial Ce carr est visible donc on le divise en 4 et on regarde chacun de ces fils e 44 16 tests pour les carr s de profondeur 2 Mais 3 de ces 4 carr s sont totalement hors du champ de vision donc on ne consid re plus que le carr en bas droite e 44 16 tests pour les carr s de profondeur 3 Un des 4 est totalement hors du champ de vision il en reste donc 3 e 4 4 3 48 tests pour les carr s de profondeur 4 Il a donc fallu 4 16 16 48 84 tests au lieu de 12288 pour savoir quels polygones afficher donc m me si on affiche l g rement plus de polygones qu en les testant tous le nombre de tests d risoires rend la m thode avec les quadtrees beaucoup plus efficace De plus si on descend en profondeur les carr s vont tre de plus en p
90. t tenir compte du d calage de son n ud parent On a fix un d calage de n ud de width 4 c est compl tement arbitraire ainsi plus on plonge dans l arbre plus l espace entre les cubes est petit A chaque affichage il suffit d ajouter les coordonn es de cette variable tous les sommets qu il s agisse des sommets d un objet ou des sommets des cubes des ocirees Voici quelques images profondeur 0 et 1 ji Moteur 10 TER QUE Moteur 30 TER LE S Moteur MO TER GHE 2 Moteur 30 TER me profondeur 4 Moteur 30 TER mode textur r alis avec la version quasi finale du moteur m i Moteur 30 TER Algo OCTREE Em RES FRUSTUH ACT ATE COLLISION DESACTATHE Conclusion e R sultats o Cot impl mentation L algorithme des octrees a t assez facile impl ment sans doute le plus difficile reste son traitement en particulier la gestion des collisions physiques avec glissement de la cam ra lors du blocage sur un mur Comme nous l avons vu l pop e du clipping a contraint un changement de structure ce qui n a pas rendu le code optimal lors de la construction de l arbre le manque de temps ne nous permet pas de faire les modifications d ici la remise des livrables cependant nous avons pris note des changements apporter pour une version ult rieure De m me concernant la reconstruction de l arbre chaque changement de profonde
91. thode de cr ation tape par tape Pour construire les structures dont on a besoin l id e est de proc der de mani re r cursive On va simultan ment cr er une suite de d coupages imbriqu s et une structure d arbre associ e Etape 1 Niveau 0 dans l arbre Pour cr er l octree initial on cherche obtenir la dimension maximum de notre sc ne notre monde puis on ajuste les dimensions pour obtenir un cube II s agit en fait du cube englobant de la sc ne enti re et on affecte ainsi ce cube au n ud racine de notre arbre Ce n ud racine contient donc ce niveau tous les polygones de la sc ne Supposons que la sc ne soit cette tour il s agit d une des tours de notre monde Pour chaque tape nous verrons pour une m me profondeur les deux modes de rendu car d pass une certaine profondeur le mode fil de fer n est plus tr s explicite acteur ID TEE digo CCTR E g Moteur 10 TEE aao CCTR E Nous pouvons donc observer malgr que ce ne soit pas tr s lisible e profondeur est de O Depth 0 sur l image e l arbre contient un n ud Total ends nodes 1 car un cube a t cr e un n ud est effectivement affich Total nodes drawn 1 puisqu il est dans notre champ de vision Etape 2 Niveau 1 dans l arbre Ensuite on subdivise le cube englobant en 8 cubes plus petits l int rieur du cube cr pr c demment on obtient donc 4 cubes en haut et 4 cubes en bas On ne garde que les cubes ayant
92. tion de la position et de l orientation de la cam ra Le chargeur de fichiers e Introduction Quand on a un grand nombre de polygones il est difficile de les d finir dans le code De plus on veut pouvoir changer d environnement 3D Ces environnements sont d crits dans des fichiers et c est pour cela que nous avons impl ment un chargeur permettant de les lire et de les charger en m moire Nous utiliserons pour notre moteur le format de fichier obj En effet ayant eu l occasion de le manipuler et donc de nous familiariser avec celui ci lors de l laboration du projet de synth se d image et de m me correspondant bien aux exigences de notre travail nous avons jugez opportun de l exploiter e Description du format ob Voici les differents l x mes n cessaires la d finition d objet 3D o commentaire La ligne est comment e jusqu la fin de la ligne o ghnomgroupe numeroelementdansgroupe Un groupe est quivalent un objet il est suivi des sommets qui forment les faces ainsi que de ses faces o V float float float Un sommet vertex et sa position dans l espace Le premier sommet list a comme index 1 et les sommets subs quents sont num rot s s quentiellement o fintintint Une face polygonale Les entiers sont ind x s respectivement dans un tableau de sommets Dans notre fichier les polygones contiennent trois ou quatre sommets La sp cification du fichier obj pr cise que chaque face doit
93. u une liste de niveau de d tail bas contiendra beaucoup moins de polygones qu une liste de niveau de d tail sup rieur Ceci permet de palier au surplus d affichage de polygones lorsqu on visualise la sc ne enti re Les arbres BSP Historique Henry Fuchs Zvi Kedem et Bruce Naylor ont t les premiers impl menter cet algorithme Leur premier article On Visible Surface Generation by A Priori Tree Structures est paru en 1980 ce moment l ils utilisaient les arbres BSP pour d terminer l ordre d affichage des polygones en fonction de la profondeur pour pallier les faiblesses de l algorithme du peintre En effet il n y avait pas de carte graphique sur les ordinateurs du d but des ann es 80 et le calcul du depth buffer tampon de profondeur faisait chuter les performance On a commenc utiliser les arbres BSP au d but des ann es 90 Le premier jeu les utiliser et en faire une impl mentation qui donne un rendu fluide est Doom en 2D d velopp par John Carmack et John Romero Doom tant devenu tr s populaire dans le monde du jeu vid o de nombreux autres jeux se sont mis utiliser les BSP Aujourd hui de nombreux moteurs de jeux utilisent les BSP la sage des Quake Id Software Unreal Epic Game D finition Un arbres BSP Binary Space Partition Tree est une structure de donn es o sont subdivis s des espaces afin d isoler ce que l on pourra appeler des l ments de base Chacun des n uds
94. un l autre deux afin d illustrer ceci En rouge les cubes concern s c est dire ceux qui intersectent avec la sph re englobante de la cam ra En bleu les polygones suspects la couleur des polygones est plus significatif en mode textur REMARQUE Les images n ont pas t retouch es avec un logiciel de dessin les polygones se d tourent de la couleur appropri e en temps r el image de gauche 224 polygones test s 0 en collision avec la sph re rayon de sph re 175 15 image de droite 260 polygones test s 0 en collision avec la sph re rayon de sph re 175 15 On observe bien que les polygones bleus correspondent tous les polygones du cube en rouge o Etape 3 Tester les collisions sur les polygones Maintenant que l on conna t les polygones qui peuvent tre en collision avec la sph re il ne suffit plus que de tester si il y a effectivement collision ou pas Pour cela on a la fonction sOverlappsCameraWithFace qui renvoie vrai si la sph re est en collision avec le polygone pass en param tre faux sinon Dans l hypoth se ou il y a intersection on dessine ces polygones en blanc Dans les images qui suivent l image de droite est la m me sauf que l on a l g rement avancer Moteur 40 TER Ag OCTREE LE Moteur 10 TER aigo CCTREE 67 polygones test s 4 en collision avec la sph re rayon de sph re 175 15 67 polygones test s 46 en col
95. ur la m thode utilis nous permet de ne pas tre born et ainsi de cr des arbres de profondeur illimit e Nous avons choisi cette m thode afin de diff rer de celle de Jean francois Fourmond dans l tude des quaditrees Cependant il s av re que d pass un certain niveau le nombre d octrees tant tellement grand que l on se retrouve born par les performances de la machine c est pourquoi nous auront beaucoup de mal a d pass la profondeur 9 De ce fait la modification de ce point serait apporter dans une version ult rieure e Avantages L avantage des octrees dans l absolu est que l arbre est pr calcul si nous ne changeons pas de niveau de profondeur dans notre cas et ainsi les performances de la machine sont concentr es sur son utilisation De m me la structure hi rarchique des octrees engendrent un d coupage du monde rendant le rep rage facile dans la sc ne En effet nous avons vu lors de la gestion des collisions qu avec seulement quelques tests il nous tait possible de retrouver la position de la cam ra dans la hi rarchie globale des octrees ceci est tr s int ressant en particulier pour la gestion des collisions dans laquelle on a sans cesse besoin de conna tre la position de la cam ra par rapport aux polygones de la sc ne e Inconv nients II s av re cependant que les octrees restent non optimaux dans les espaces ferm s En effet nous supposons que notre plan far le plan du frustum le plus
96. vail et nous a incit communiquer le plus possible Par ailleurs la rencontre avec Nicolas Peri ancien tudiant en ma trise d informatique et d veloppeur de jeux vid o sur PC X Box et GSM nous a appris les techniques utilis es dans les jeux actuels ainsi que les outils et les m thodes de travail dans les entreprises les d veloppant

Rapport - Département Informatique

Contents

Download Pdf Manuals

Related Search

Related Contents

Rapport - D&eacute;partement Informatique

Contents

Download Pdf Manuals

Related Search

Related Contents

Rapport - Département Informatique