Seasons - Tests de visibilité (frustum culling)

Salut tout le monde !

Prêts pour un nouveau "tech post" avec une vidéo bonux intégrée ? Cette fois-ci on va parler des tests de visibilité dans Seasons.

La semaine dernière, j'ai donc tenté d'améliorer le code de rendu pour réduire le temps que nous passons à fabriquer les images.

>> Contexte

Jusqu'à présent, je ne m'étais pas trop soucié de l'optimisation du rendu (faut croire que je me soucie de pas grand chose en fait !). Quelques techniques d'optimisation avaient bien été implémentées... Mais comme nous sommes passé d'un affichage style 2D à style 3D (souvenez-vous), le tout est devenu très buggué... jusqu'à la semaine dernière !

>> Frustum

La chose principale que l'on essaie de faire lorsque l'on veut optimiser l'affichage, c'est de n'envoyer au rendu que les objets qui seront visibles depuis le point de vue de la caméra. Ça peut sembler logique mais c'est une chose qui n'est pas automatiquement gérée par un quelconque hardware. On doit donc prendre en charge tout cela du côté du moteur de jeu (côté CPU la plupart du temps) afin de d'alléger le rendu. On appelle le procéder le "culling" (l'élimination des parties cachées). 

Pour parvenir à déterminer ce qui est visible de ce qui ne l'est pas, on peut compter sur l'utilisation intensive du frustum. Le frustum est une structure géométrique prenant très souvent la forme d'une pyramide tronquée. Cette forme représente ce que voit la caméra et comment elle projette ce qu'elle voit sur son capteur CCD qu'est l'écran.

Un frustum et sa caméra

Les objets partiellement ou entièrement contenus dans le frustum de la caméra sont potentiellement visible à l'écran. Potentiellement car ces objets peuvent être cachés par d'autres objets plus proches et/ou plus gros également présents à l'intérieur du frustum.

L'algorithme

Comme vous l'aurez compris, l'idée est d'empêcher certains objets d'être dessinés en testant leur visibilité avec le frustum de la caméra. Voici le pseudo-code (algorithme).

FONCTION mise à jour/rendu
{ POUR CHAQUE Objet dans la liste des objets du niveau FAIRE { SI l'Objet courant est dans le frustum ALORS { rendre l'objet (ou le mettre à jour, ou effectuer une action) } }
}

Et voici un petit schéma pour illustrer la situation. On y montre une scène composée de 25 objets et d'un frustum, le tout en vue de dessus.

Le frustum et les 25 objets, le dernier film dans vos salles

Seulement 3 des objets de la scène sont à l'intérieur du frustum et seront donc envoyés au rendu.

Avec cette technique, on évite de rendre 22 objets mais on doit quand même parcourir TOUS les objets de la scène afin de savoir au cas par cas qui est potentiellement visible et qui ne le sera définitivement pas. Notre scène d'exemple ne contient que 25 objets, mais dans le cas de scènes plus complexes, on va passer un temps fou à tester beaucoup d'objets... et dans le jeu vidéo plus qu'ailleurs, on évite de passer trop de temps machine à calculer une image sous peine d'avoir un jeu qui perd en fluidité.

Le rêve américain, c'est de mettre moins de 16 millisecondes pour construire une image du jeu.

Pour éviter de parcourir tous les objets de la scène, on peut tenter de faire des groupements d'objets. Ces groupes vont contenir des objets spatialement proches.

>> Élimination par grille

Il existe une multitude de manières de regrouper des objets afin de simplifier le travail d'élimination des parties cachées. On peut citer les BSP, les portails ou encore les Quadtree et autres Octree... mais nous n'utiliserons aucune de ces méthodes. Nous n'allons pas élaborer de zones hiérarchiques ("tree" insinue arborescence) mais nous allons nous contenter d'une grille 3D régulière.

Parce que nous ne sommes pas dans le cas d'un jeu réellement en 3D (dans le sens où les objets affichés ont des épaisseurs infimes et sont toujours face caméra, et que la caméra regarde toujours le long d'un axe donné), alors nous pouvons nous permettre d'opter pour une solution moins "complexe" que celles sus-citées.

Ce que nous voulons, c'est retirer au plus tôt quelques objets supplémentaires de la boucle du pseudo code précédent, aussi vite que nous le pouvons. En ayant un système plus élaboré, on perdrait plus de temps à maintenir ce système que de conserver notre grosse boucle.

Voici un exemple simpliste de grille 3D. La grille est composée de cellules de couleurs différentes.

Mini grille régulière

On remarque que 2 cellules sont visibles car contenues dans le frustum de la caméra. On note aussi que cette grille est vraiment simpliste, mais c'est pour l'exemple !

L'algorithme

Le pseudo code mettant en jeu une grille est un peu plus complexe que le précédent car il se compose de 2 étapes.

La première étape consiste à enregistrer un objet nouvellement créé dans une ou des cellules de la grille.

FONCTION ajout d'objet/déplacement d'objet
{ dé-enregistrer l'Objet de la grille 3D (si il était enregistré) trouver les cellules de la grille qui contiennent l'Objet (facile à faire car la grille est régulière) enregistrer l'Objet dans les cellules trouvées (dans le meilleur des cas l'Objet se trouve que dans une seule cellule)
}

Et voici l'équivalent du pseudo code de mise à jour rendu de tout à l'heure !

FONCTION mise à jour/rendu
{ déterminer quelles sont les cellules visibles autour de la caméra (facile à faire car la grille est régulière) POUR CHAQUE Cellule visible par la caméra FAIRE { POUR CHAQUE Objet enregistré dans la cellule courante FAIRE { SI l'Objet n'a pas encore été traité ALORS { SI l'Objet courant est dans le frustum ALORS { rendre l'objet (ou le mettre à jour, ou effectuer une action) marquer l'objet comme traité (pour ne pas être traité une 2eme fois durant la même image dans le cas où l'objet était enregistré dans plusieurs cellules) } } } }
}

Et voici l'illustration des objets et des cellules sur une même image.

Frustum, cellules, grille et objets : le megamix

Comme vous pouvez le constater, 2 cellules sont visibles, et 7 objets sont testés avec le frustum (au lieu de 25 précédemment).

Réglages

Pour avoir une élimination des plus efficaces, il convient d'effectuer des réglages sur le nombre et la taille des cellules. En effet, si la taille des cellules est trop petite, alors on aura beaucoup de cellules et dans le pire des cas on obtiendra 1 objet par cellule, ce qui revient à ne pas utiliser de grille et de cellules du tout, en pire.

Si les cellules sont trop grandes, on se retrouve dans la même situation car dans un cas extrême la scène ne contiendrait une grille composée que d'une seule cellule, ce qui revient à ne pas utiliser de grille.

Il faut donc trouver le juste milieu, et pour cela il convient déjà de créer des niveaux afin d'avoir l'échelle des objets qui y sont positionnés. De là on peut ajuster la taille des cellules.

>> C'est dans la boite

Pour pouvoir déterminer si un objet est dans le frustum, on doit connaitre son encombrement. Pour déterminer cet encombrement le plus rapidement possible, nous n'utilisons pas directement le maillage d'un objet ni même sa boite englobante orientée (OOBB, Oriented Object Bounding Box) mais plutôt une enveloppe englobante plus simpliste encore : la boite englobante alignée aux axes du monde (AABB, Aligned Axis Bounding Box).

Voici un exemple de l'évolution d'une AABB en comparaison d'une OOBB sur un maillage de chat qui subit diverses rotations (non, ce n'est pas Buster).

Maintenant vous voyez un chat pivotant, sans prendre de drogue (en haut l'AABB, en bas l'OOBB)

En utilisant une AABB plutôt qu'une OOBB, on rend le calcul de visibilité super simple et rapide (ou efficace et pas cher, comme vous préférez). Pour mieux comprendre pourquoi une telle facilité, voici des exemples de situations de positionnement entre 2 AABB.

Quelques unes des configuration possibles entre 2 AABB

On ne présente pas toutes les combinaisons possibles, mais l'algorithme utilisé pour savoir si oui ou non 2 AABB se superposent prendra dans tous les cas le même nombre de calculs, quelque soit la configuration. Revoici nos AABB mais cette fois-ci avec des vecteurs tracés entre certains des coins des boites :

AABB et vecteurs reliant les coins bas-gauche et haut-droit

Les vecteurs tracés connectent toujours le coin bas-gauche d'une boite avec le coin haut-droit de l'autre boite.

Il devient alors facile de remarquer que 2 AABB se superposent quand les 2 vecteurs ainsi formés pointent une direction Nord-Est. On peut aussi dire que 2 AABB se superposent dans les cas particuliers où les vecteurs pointent une direction Nord (vecteur vertical pointant vers le haut) ou Est (vecteur horizontal pointant vers la droite).

Je ne vous écrirais pas le pseudo code ici, mais on voit bien que le calcul est vite fait, et qu'il fait bien toujours le même nombre d'opérations.

>> Résultats dans le jeu

C'est bien joli tous ces trucs théoriques, mais si on matait une petite vidéo maintenant ?

Vous allez y voir plein de boites englobantes, des rouges (pour les objets), une bleue (représentant la coupe du frustum le long du plan vertical autour de Z = 0) des vertes (pour les cellules de la gille).

La boite bleue varie de taille uniquement pour montrer comment les objets sont rejetés ou acceptés. Changer la taille laisse apparaître un phénomène de poping pour bien mettre en évidence le culling.

Du point de vue du framerate, voici quelques chiffres relevés sur ce niveau qui reste toutefois assez petit/simple :

- 48 fps sans aucune optimisation de visibilité
- 55 fps quand les AABB des objets sont testés directement avec le frustum (sans l'usage d'une grille)
- 60+ fps quand on utilise une grille ("+" car le moteur limite le framerate à 60 fps)

Tout ceci sur mon PC pas terriblement récent (P4 C 2.8Ghz et sa copine Geforce 7600Gt, AGP s'il vous plait !).

>> Pour conclure

C'était une première passe d'optimisation, il y en aura forcément d'autres. On ne vise pas des configurations de fous, donc il faudra qu'on s'applique à ce que le jeu tourne sur une grande variété de machines.

Dans un prochain article sur l'optimisation, on pourra pleinement parler de choses passées sous silence ici, comme le Batching, ou l'utilisation de buffer dynamiques vs. buffer statiques ou d'autres joyeusetés du genre.

Pour le moment, place à vos remarques et expériences vis à vis de la visibilité dans les jeux (en tant que joueur ou développeur) ! 

Hop, je ne suis plus visible.

Guillaume