TER BL21 Étude des structures de données au cœur des algorithmes 3D des jeux vidéos de type FPS....

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