Etude des structures de donnes au coeur des algos 3D des FPS.(BL2)

Vos noms ici, encadreur, etc

IntroductionContexte : cours de synthse dimage trs intressant mais seulement 6 sancesProgramme de TPs/Mini projet limit,Envie den savoir plus,Choix du TER avec notre encadreurSujet du TER : tude des structures de donnes et des algorithmes dans les jeux 3D de type FPS (Doom, Quake, Unreal)

Introduction (suite)Intrt avant tout pdagogiqueEcriture dun vrai moteur 3D, y compris limplmentation de nombreux concepts vus en cours..Utilisation dOpenGL/C++/ et des maths !Dcouverte dalgorithmes et de structures de donnes nouveaux, non nafs,Rencontre avec un dveloppeur de jeux vido,Rutilisation de nos travaux par Mr Buffa en tant que tutoriaux/programmes dexemples

Plan de la prsentationAfficher un univers immense, comment faire vite ?Prsentation de 4 algorithmes lis des structures de donnes adaptes, avec leurs implmentationsComparaison/synthse de ces algorithmesConclusion

Remarque importanteLa plupart des illustrations sont issues du moteur 3D que nous avons dvelopp pour ce TERFonctionnalits multiples (texture mapping, clairages, etc),12000 lignes de code,Conception objet pense vers lextensibilit (pour pouvoir changer les algorithmes de rendu facilement),C++/Open GL,Notre plate-forme de test !

Comment afficher rapidement un univers immense ?

Univers immense ?Rapidement = 60 images/s au moins !Exemples : un btiment, un circuit, une ville, une rgion...Un tel univers peut contenir des millions de polygones : on ne va pas tous les afficher !Pour aller vite : ne dessiner que ceux qui sont visibles (dans le champ de vision de la camra).

Le champ de vision sappelle le frustum

En 3D, cest lespace compris entre les 6 plans.Calculer la partie visible = frustum culling

Exemple dalgorithmeUn univers 3D = des millions de polygones,Si lunivers est plat, il suffit de plaquer une grille dont chaque case fait par exemple 10m2Il suffit, quand on se dplace, de ne dessiner que ce qui se trouve dans les cases qui coupent le champs de vision.Si on a pr-calcul lassociation polygones/case, et si lunivers est statique, on a rapidement la liste des cases visibles et donc la liste des polygones visibles

Illustration de lalgorithme prcdentChamps de visionPartie visiblePartie non visible

Mais ce nest pas aussi simple !Une simple grille ne suffit pas ! Ce nest pas efficace et on a aussi envie aussi de :Calculer des collisions,Grer les niveaux de dtails,Ne pas afficher ce qui se trouve derrire un mur etcLes quatre algorithmes que nous avons tudis rpondent certaines de ces conditions.

Scne de test (60.000 polygones, 4000m2)

Algorithme base de quadtrees

PrincipeComme une grille, sauf que les cases ne font pas toutes la mme taille.Permet la gestion des niveaux de dtailsOn associe chaque case les polygones quelle contientConstructionOn part dune case qui fait toute la surface de luniversOn dcoupe rcursivement lunivers en cases de plus en plus petites.Au final, on a un arbre de cases, chaque case tant dcoupe en 4 cases

Exemple de quadtree

Chaque feuille contient une liste de polygones

Comparaison grille/quadtree

Beaucoup moins de tests avec le quadtree ! Trs utilis pour reprsenter des modles numriques de terrain (gestion dynamique du niveau de dtails, pas implment dans notre TER)

Exemple avec notre scne de testIci une image avec une autre profondeur (sanbs quad), et comparer les perfs

Conclusion sur les quadtreesSurtout adapt des scnes 2D/2D et demie (grilles dlvation, modles numriques de terrains)Peu adapts pour des btiments tages, tant donn quon ne considre que les projections des polygones au sol quoiqueLes prochains algorithmes rpondent ces limitations

Algorithme base dOctrees

PrincipeIdem quadtrees mais en 3DPlus complexe cause de la dimension supplmentaire!

Construction rcursive

Construction rcursive

Construction rcursive

Construction rcursive

Construction rcursive

Detection des collisionsLegende ici ! A quoi correspondent les couleurs ?

RsultatsBien meilleur nombre dimages/s quavec les quadtrees,Trs intressant pour la dtection de collisions

Algorithmes base darbre BSPs

PrincipeEtc

Algorithme base de portails

Principe (statique)

Dcoupage du monde en Secteurs Quand on modlise lunivers, on le dcoupe en secteursLes secteurs sont mitoyens lorsquils ont un mur commun.Deux secteurs A et B sont voisins si une partie de B est visible depuis A.Portail = partie qui relie deux secteurs

Principe (dynamique)

Les parties visibles par la camra sont recalcules rcursivement. Parcours de graphe non orient en profondeurNuds = les picesArtes = un portail reliant deux secteurs

Une fois le graphe parcouru, on a marqu toutes les parties visibles : on les affiche

Avantages/InconvnientsNaffiche que ce qui est visibleNcessite une modlisation ad hoc du mondeImpossible de lutiliser avec notre scne de testNon intgr au moteur 3D, mais tutorial de dmonstration des principes, en 2D.

Modlisation des picesInformation dans un fichier annexe : syntaxeCe nest pas toujours simple, problmes lis la concavit des pices et des coins.

Synthse

Heighmap autre facon de creer un mondePour illustrer la diffrence Quadtree/OctreeSi il y a une montagne les quadtrees montrent leurs limitesscreen

En dautres termesQuadtree : dans les jeux = circuit de voitures, ET modle numrique de terrain + frustum = LODOctree : dans les jeux style Lara BSP : le plus utilise quake like, unreal,6 optimisations multiples (arbres quilibrs, etc)Portails : peu utiliss en tant que tels souvent rajouter sur un algo lancer de rayon

Quatrees (simples)

en complment du frustum dans les terrains numriques niveau de dtail dynamique

Utilissdans les jeux de voiture

ca depend du type de camera

Octrees (efficaces)Dans les jeux la 3eme personneEfficaces avec les collisions

Pour des mondes en hauteurs

Arbres BSP (optimaux)...... Portails(mlangs)Utiliss dans les FPS les plus fluides .Nombreux cas particuliers, donc difficiles implmenter.

En complment des arbres BSP.Technique du Lancer de rayons