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