Skip to topic | Skip to bottom
Home
Linfo
Linfo.AlgosJeux3DRapportr1.2 - 01 Jun 2004 - 13:53 - FourmondJeanFrancoistopic end

Start of topic | Skip to actions

Rapport du projet

Note

Ceci est une version de travail, on commence à réfléchir au plan, puis à remplir les différentes parties

Introduction, présentation du sujet

Lors du cours d'introduction à la synthèse d'images de MichelBuffa nous avons usrtout étudié les bases de la visualisation 3D : bases mathématiques, calculs en coordonnées homogènes, projection 3D vers 2D, algoithmes d'élimination des faces cachées, clipping 2D et 3D, gestion des éclairages, lissage des facettes (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 (personne n'a pu intégrer le texture mapping par exemple, faute de temps).

Par ailleurs, le logiciel développé est un simple visualisateur 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, etc...

La plupart des jeux vidéos ou des applications de réalité virtuelle permettent aujourd'hui d'explorer des environnement trtè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 tridimensionelle de cet univers consiste en des millions de polygones, comment les "trier" afin de ne considèrer que la partie de ces informations qui correspond à ce qui doit réellement être dessiné 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 (cf schéma), si on veut dessiner à l'écran ce que voit un individu situé à la case de coordonnées (3, 5) par exemple, il est inutile de considérer les cases qui sont en dehors de son champ de vision. On a donc déjà une algorithme permettant sde 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 !

Quatre algorithmes 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 értudiés sont :

  • Quadtree,
  • Octree,
  • Portail,
  • arbres BSP (Binary Space Partition tree).

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 apermis 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 univers semblable au temple que l'on peut voir dans le film "Troie" avec Brad Pitt, actuellement sur les écrans. Vous verrez que certaines parties de cezt univers ce prêtent mieux à certains algorithmes que d'autres. Une section de comparaison des algorithmes est présentée dans le rapport.

Moteur 3D utilisé par les programmes de démonstration de ces algorithmes

Avant tout, nous présentons ici les caractéristiques du moteur 3D que nous avons développé pour illustrer les algorithmes précités.

Qu'est-ce qu'un moteur 3D

Fonctionalités principales

  • Chargement de fichiers décrivant l'univers à explorer
  • 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 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 visualisation dans notre cas), etc...
  • Mode de visualisation : file de fer, etc...
  • Gestion des déplacements, des collisions,...
  • Gestion de la physique, des interactions, etc...
  • Gestion du clipping (comment déterminer la partie du monde qui est visible), c'est là qu'interviennent nos algorithmes...

Nous avons toutes ces fonctionalités...

Architecture modulaire

Ici prensenter dans un schéma à la UML les principaux modules, mais en restant très haut niveau...

Technologies utilisées

Le moteur est écrit en C++, utilise Open GL etc...

Algorithme à base de quadtree

Idée de base

Découper l'espace récursivement en carrés... avantages, etc... contraintes, etc...

Programme de démonstration

Ici vous pouvez télécharger une petite démo, cliquez juste sur le lien, et voici les touches... regardez bien ce que ca donne quand on fait cecie ou cela...

Problèmes rencontrés ?

Algorithme à base d'octree

Algorithme à base d'arbre BSP

Algorithme à base de portail

Synthèse sur l'étude de ces algorithmes

Complexité, utilisation mémoire, performances

Tableau récapitulatif

ici un tableau qui explique dans quels cas les algos sont recommandés, en ligne les cas de figure, en colonne les algos, et des croix... Un autre tableau qui dit quels algos sont dynamiques (univers qui change en cours de route ou pas), comment on peut prendre en compte des personnages animés dans cet univers, (ben, on fait une seconde passe en Z-Buffer, tout simplement, comme dans quake, cf le black book de michael abrash etc... ?)

Conclusion

Travail réalisé, adéquation au cahier des charges

Bilan de cette expérience

Annexes

Compte rendu de la réunion avec Nicolas Peri

Ressources web, références bibliographiques

etc...

-- MichelBuffa - 01 Jun 2004
to top

Linfo.AlgosJeux3DRapport moved from Minfo.LeRapport on 01 Jun 2004 - 13:53 by FourmondJeanFrancois - put it back
You are here: Linfo > AlgosJeux3D? > AlgosJeux3DRapport

to top

Copyright © 1999-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding WIKIDeptinfo? Send feedback