Upload
adalard-tardy
View
103
Download
0
Embed Size (px)
Citation preview
TER BL2 1
Étude des structures de données au cœur des algorithmes 3D des jeux vidéos de type FPS.
(BL2)
Encadrant : Participants :Michel BUFFA Jean-François FOURMOND
Stéphane MARIANI
Xavier MEDIONI
Jean-François RIGHIMaîtrise d’informatique 2003-2004
TER BL2 2
Introduction
• Contexte : cours de synthèse d’image très intéressant… mais seulement 6 séances– Programme de TPs/Mini projet limité,– Envie d’en savoir plus,– Choix du TER avec notre encadreur
• Sujet du TER : étude des structures de données des algorithmes 3D dans les jeux de type FPS (Doom, Quake, Unreal)…
Edit : « nos propres algorithmes » à éviter
structure de données à préciser
TER BL2 3
Doom 3 (sortie annoncée en 2004)
TER BL2 4
Unreal Tournament (1999)
TER BL2 5
Quake III (1999)
TER BL2 6
Introduction (suite)
• Intérêt avant tout pédagogique– Écriture d’un « vrai » moteur 3D– Utilisation d’OpenGL/C++/… et des maths !– Découverte d’algorithmes et de structures de
données nouveaux, non naïfs,– Réutilisation de nos travaux par Mr Buffa en
tant que tutoriaux/programmes d’exemples
TER BL2 7
Remarque importante
• La plupart des illustrations sont issues du moteur 3D que nous avons développé pour ce TER :– Fonctionnalités multiples (texture mapping,
éclairages, etc…),– 10 000 lignes de code,– C++/OpenGL/SDL,– On a notre propre environnement de test !
TER BL2 8
Plan de la présentation
• Afficher un univers immense, comment faire vite ?
• Présentation de 4 algorithmes liés à des structures de données adaptées, avec leurs implémentations
• Comparaison/synthèse de ces algorithmes
• Conclusion
TER BL2 9
Comment afficher rapidement un univers immense ?
TER BL2 10
Notre scène de test (60000 polygones, + de 8000m2 (2 terrains de foot))
TER BL2 11
Univers immense ?
• Exemples : un bâtiment, un circuit, une ville, une région...
• Un tel univers peut contenir des millions de polygones : on ne va pas tous les afficher !
• Rapidement = 60 images/s au moins !• Pour aller vite : ne dessiner que ceux qui
sont visibles (dans le champ de vision de la caméra).
TER BL2 12
Le champ de vision s’appelle le frustum
En 3D, c’est l’espace compris entre les 6 plans.
Calculer la partie visible = frustum culling
TER BL2 13
Exemple d’algorithme naïf
• Tester tous les polygones ? Beaucoup trop long.
• Si l’univers est statique, plaquer une grille avec des cases de taille égales.
• Pré-calcul : on associe une case à chaque polygone.
• On ne dessine que les polygones dont les cases sont dans le champ de vision.
TER BL2 14
Illustration de l’algorithme précédent
• vue de dessus : les cases visibles sont grisées
Champs de
vision
TER BL2 15
Mais ce n’est pas aussi simple !
• Une simple grille ne suffit pas ! Ce n’est pas efficace et on a aussi envie aussi de :– Calculer des collisions,– Avoir des algos pour tous les types
d’environnement– Ne pas afficher ce qui se trouve « derrière un
mur », etc…• Les quatre algorithmes que nous avons étudiés
répondent à certaines de ces conditions.
TER BL2 16
Algorithme à base de quadtrees
TER BL2 17
Principe
• Comme une grille, sauf que les cases ne font pas toutes la même taille.
• On associe à chaque case les polygones qu’elle contient
• Construction– On part d’une case qui fait toute la surface de l’univers– On découpe récursivement l’univers en cases de plus en
plus petites.
• Au final, on a un « arbre de cases », chaque case étant découpée en 4 cases.
TER BL2 18
Exemple de quadtree
TER BL2 19
Comparaison grille/quadtree
• Intérêt : on teste d’abord si les grands carrés sont visibles. Si ils ne le sont pas, on les élimine. Sinon, on considère des carrés plus petits.
• Beaucoup moins de tests avec le quadtree !
TER BL2 20
Exemple avec notre scène de test
11 fps
31 fps
TER BL2 21
Conclusion sur les quadtrees
• Surtout adaptés à des scènes sans superpositions (les polygones sont projetés sur un plan).
• Peu adaptés pour des bâtiments à étages : on va par exemple afficher des polygones sous le sol.
• Les prochains algorithmes répondent à ces limitations…
TER BL2 22
Algorithme à base d’Octrees
TER BL2 23
Principe
• Idem quadtrees mais en 3D…
• Plus complexe à cause de la dimension supplémentaire!
• Arbre à 8 branches
TER BL2 24
Construction récursive
• profondeur 0 :
Le cube contient la totalité des polygones constituant la scène
TER BL2 25
Construction récursive
• Profondeur 1 :
On subdivise la scène en 8 cubes plus petits.
TER BL2 26
Construction récursive
TER BL2 27
Construction récursive
TER BL2 28
Construction récursive
• On ne construit pas de cubes vides.
• 385 cubes
TER BL2 29
Exemple avec notre scène de test
Frustum non activé
=
Découpage de l’espace inutile
4 fps (frames per second)
TER BL2 30
Exemple avec notre scène de test
Profondeur 4
18% de la totalité de la scène affiché
28 fps
TER BL2 31
Exemple avec notre scène de test
Profondeur 5
10% de la totalité de la scène affiché
35 fps
TER BL2 32
Détection des collisions
On assimile le personnage à une sphère placée autour de la caméra.
Rayon de la sphère paramétrable
TER BL2 33
Détection des collisions (suite)
En rouge:
Octree en collision avec le personnage
En bleu :
Les polygones potentiellement en collision
En blanc :
Les polygones en collision avec le personnage
TER BL2 34
Algorithmes à base d’arbre BSP
TER BL2 35
Principe
• Base : diviser l’espace en deux de manière récursive pour obtenir un arbre binaire de partitionnement (BSP).
• Objectif : éliminer le traitement d’une branche entière sur un test de visualisation.
• Inconvénient : temps de calcul extrêmement long pour obtenir un arbre équilibré
nécessité de « précompiler » l’environnement
TER BL2 36
Exemple
Applet de démonstration
TER BL2 37
Fin de la récursivitéOn arrête la récursivité quand :
• la liste de faces associée à un nœud ne contient que des faces coplanaires
où
• la longueur de la liste est inférieure à une longueur donnée (optimisation à l’implémentation).
TER BL2 38
Fin de la compilationOn associe à chaque nœud une boite englobante
TER BL2 39
Parcours de l’arbrePendant l’exécution du moteur, le parcours de l’arbre se fait
sur un simple test de visibilité sur la boite englobante
TER BL2 40
Algorithme à base de portails
TER BL2 41
Principe (statique)
• Découpage du monde en Secteurs – Quand on modélise l’univers, on le découpe en
secteurs– Les secteurs sont mitoyens lorsqu’ils 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.
TER BL2 42
Principe (dynamique)
• Les parties visibles par la caméra sont recalculées récursivement.
• Parcours de graphe non orienté en profondeur–Nœuds = les pièces–Arêtes = un portail reliant deux secteurs
• Une fois le graphe parcouru, on a marqué toutes les parties visibles : on les affiche.
TER BL2 43
Avantages/Inconvénients
• N’affiche que ce qui est visible• Nécessite une modélisation préalable du monde
– Impossible de l’utiliser avec notre scène de test
• Non intégré au moteur 3D, mais tutorial de démonstration des principes, en 2D.
TER BL2 44
Modélisation des pièces
• Information dans un fichier annexe : syntaxe• Ce n’est pas toujours simple, problèmes liés
à la concavité des pièces et des coins.
TER BL2 45
Synthèse
TER BL2 46
TER BL2 47
Quatrees (simples)
• Niveau de détails dynamique dans les terrains numériques
Utilisésdans les jeux de voiture
TER BL2 48
Octrees (3D)
Dans les jeux à la 3eme personne
Idéal pour gérer les collisions
Optimal pour des mondes en hauteur
TER BL2 49
Arbres BSP (optimaux)...
... Portails (mélangés)
Utilisés dans les FPS les plus fluides .Nombreux cas particuliers, donc difficiles à implémenter.
En complément des arbres BSP.Technique du Lancer de rayons.
TER BL2 50
Conclusion
• Adéquation au cahier des charges :
– Pas de gestion des contraintes physiques (gravité, collision)
– L’implémentation de certains algorithmes n’a pu arriver à terme
TER BL2 51
Conclusion (suite)
• Méthode de travail :– Développement en parallèle des différents
modules communs– Rencontre avec un professionnel du jeu vidéo– Fréquentes réunions avec les participants– Communication intensive avec notre encadrant– Utilisation massive de l’outil Wiki
TER BL2 52
Conclusion (suite)
TER BL2 53
Conclusion (fin)
• Bénéfices personnels– Première expérience approfondie en
programmation graphique