Etude des structures de donne s au coeur des algos 3D des
FPS.(BL2) Vos noms ici, encadreur, etc
Page 2
Introduction Contexte : cours de synthse dimage trs in tressant
mais seulement 6 sances Programme de TPs/Mini projet limit, Envie
den savoir plus, Choix du TER avec notre encadreur Sujet du TER :
tude des structures de donn es et des algorithmes dans les jeux 3D
de t ype FPS (Doom, Quake, Unreal)
Page 3
Introduction (suite) Intrt avant tout pdagogique Ecriture dun
vrai moteur 3D, y compris limplme ntation de nombreux concepts vus
en cours.. Utilisation dOpenGL/C++/ et des maths ! Dcouverte
dalgorithmes et de structures de donnes n ouveaux, non nafs,
Rencontre avec un dveloppeur de jeux vido, Rutilisation de nos
travaux par Mr Buffa en tant que tu toriaux/programmes
dexemples
Page 4
Plan de la prsentation Afficher un univers immense, comment
fair e vite ? Prsentation de 4 algorithmes lis des stru ctures de
donnes adaptes, avec leurs impl mentations Comparaison/synthse de
ces algorithmes Conclusion
Page 5
Remarque importante La plupart des illustrations sont issues du
moteur 3 D que nous avons dvelopp pour ce TER Fonctionnalits
multiples (texture mapping, clairages, etc), 12000 lignes de code,
Conception objet pense vers lextensibilit (pour pouv oir changer
les algorithmes de rendu facilement), C++/Open GL, Notre
plate-forme de test !
Page 6
Comment afficher rapidement un univers immense ?
Page 7
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 l a camra).
Page 8
Le champ de vision sappelle le frustum En 3D, cest lespace
compris entre les 6 plans. Calculer la partie visible = frustum
culling
Page 9
Exemple dalgorithme Un univers 3D = des millions de polygones,
Si lunivers est plat, il suffit de plaquer une grille dont chaque
case fait par exemple 10m2 Il suffit, quand on se dplace, de ne
dessiner que c e qui se trouve dans les cases qui coupent le cham
ps de vision. Si on a pr-calcul lassociation polygones/case, et si
lunivers est statique, on a rapidement la liste de s cases visibles
et donc la liste des polygones visib les
Page 10
Illustration de lalgorithme prc dent Champs de vision Partie
visible Partie non visible
Page 11
Mais ce nest pas aussi simple ! Une simple grille ne suffit pas
! Ce nest pas effica ce et on a aussi envie aussi de : Calculer des
collisions, Grer les niveaux de dtails, Ne pas afficher ce qui se
trouve derrire un m ur etc Les quatre algorithmes que nous avons
tudis rp ondent certaines de ces conditions.
Page 12
Scne de test (60.000 polygones, 4000m2)
Page 13
Algorithme base de quadtrees
Page 14
Principe Comme une grille, sauf que les cases ne font pas t
outes la mme taille. Permet la gestion des niveaux de dtails On
associe chaque case les polygones quelle co ntient Construction On
part dune case qui fait toute la surface de lunivers On 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
Page 15
Exemple de quadtree Chaque feuille contient une list e de
polygones
Page 16
Comparaison grille/quadtree Beaucoup moins de tests avec le
quadtree ! Trs utilis pour reprsenter des modles numriq ues de
terrain (gestion dynamique du niveau de d tails, pas implment dans
notre TER)
Page 17
Exemple avec notre scne de test Ici une image avec une autre
profondeur (sanbs quad), et comparer les perfs
Page 18
Conclusion sur les quadtrees Surtout adapt des scnes 2D/2D et
demie (grille s dlvation, modles numriques de terrains) Peu adapts
pour des btiments tages, tant don n quon ne considre que les
projections des poly gones au sol quoique Les prochains algorithmes
rpondent ces limitati ons
Page 19
Algorithme base dOctrees
Page 20
Principe Idem quadtrees mais en 3D Plus complexe cause de la di
mension suppl mentaire!
Page 21
Construction rcursive
Page 22
Page 23
Page 24
Page 25
Page 26
Detection des collisions Legende ic i ! A quoi cor respondent
les couleur s ?
Page 27
Rsultats Bien meilleur nombre dimages/s quavec le s quadtrees,
Trs intressant pour la dtection de collisio ns
Page 28
Algorithmes base darbre BSPs
Page 29
Principe Etc
Page 30
Algorithme base de portails
Page 31
Principe Dcoupage du monde en Secteurs Quand on modlise
lunivers, on le dcoupe en secteurs Les secteurs sont mitoyens
lorsquils ont une partie comm une, par exemple un mur Portail =
partie qui relie deux secteurs Par exemple une porte Deux secteurs
sont voisins si il y a une partie de l un visib le quand on se
trouve
Page 32
Principe (dynamique) Entre chaque image les parties visibles
par la camer a sont recalcul2es Recherche des parties visibles =
parcours de graphe non orient en profondeur Nuds = les pices Artes
= un portail reliant deux secteurs Une fois le graphe parcouru, on
a marqu2 toutes les parties visibles on les affiche
Page 33
Avantages/Inconvnients N affiche pas les parties derriere les
murs Ncessite une modlisation af hoc du monde Impossible de
lutiliser avec notre scne de test Non intgr au moteur 3D, mais
tutorial de dmonstration des principes, en 2D.
Page 34
Modelisation des pieces Information dans un fichier annexe >
syntaxe On a considere que c etait des parallelepipipedes Ce n est
pas toujours le cas Editeur automatisant
Page 35
Page 36
Synthse
Page 37
Heighmap autre facon de creer un monde Pour illustrer la
diffrence Quadtree/Octree Si il y a une montagne les quadtrees
montre nt leurs limites screen
Page 38
En dautres termes Quadtree : dans les jeux = circuit de
voitures, ET modle numrique de terrain + frustum = LO D Octree :
dans les jeux style Lara BSP : le plus utilise quake like, unreal,6
optimisati ons multiples (arbres quilibrs, etc) Portails : peu
utiliss en tant que tels souvent rajo uter sur un algo lancer de
rayon
Page 39
Quatrees en compl2ment du frustum dans les te rrains num2rique
> niveau de detail dqns les jeux de voiture
Page 40
ca depend du type de camera
Page 41
Octrees dans les lara like efficaces avec les collisions
Page 42
Arbres BSP...... Portails utilis2s dans les FPS les plus
c2l7bres mixes aux BSP 5lancer de rayon-