On a l'impression dans les grands jeux 3D, qu'on nous présente une seule et immense scène 3D.
En fait il n'en est rien. La scène est fragmentée.
En secteurs, reliés par des portails.
Et c'est le travail des concepteurs de niveau de vous faire croire que c'est une unique scène.
Et c'est leur boulot, dans des scènes "en plein air", de créer des angles morts pour y parvenir.
Admettons que vous venez d'une scène en plein air, et que vous rentriez dans un bâtiment avec une fenêtre.
Par la fenêtre vous voyez le coté de la scène "plein air". En fait vous êtes devant un portail : Un quadrilatère sur lequel (seulement) est rendue la scène "plein air".
Car ce serait un réel gâchis en temps de tracer toute la scène extérieure si c'est pour la recouvrir par les murs intérieurs alors que seule la partie non occluse par la fenêtre est visible.
Cela est nécessaire pour des raisons d'optimisation. Faire un rendu de scène sur un petit rectangle (orienté) est énormément moins coûteux que de le faire sur tout l'écran.
Les secteurs sont reliés entre eux grâce aux portails. Et c'est comme ça que les niveaux sont construits, et permettent des maps 3D infinies (ou presque).
[EDIT]
Un autre aspect, et cela semble évident :
On ne gère pas les objets qui sont hors du champ de vue. Facile dit comme ça.
Sauf qu'en 3D, on fonctionne sur les volumes, là où la 2D fonctionne en surfaces.
On matérialise le volume du champ de vue (View frustum) et on énumère les objets qui sont dedans.
Et on ne trace que ceux-là.
C'est contre-intuitif, mais tracer un objet hors champ, même s'il ne contribue pas à l'image finale car hors du champ de vue, est coûteux pour rien puisque il n'est pas visible.
Le GPU va quand même énumérer ses facettes, calculer la position de chaque facette dans la scène pour se rendre compte in fine que chaque pixel de l'objet est en dehors de l'écran. Perte de temps.
Après imaginons une scène où il y a 100.000 objets qui la constituent. On ne peut pas vérifier pour chaque objet s'il est ou non dans le champ de vue.
Au lieu d'énumérer les objets dans une liste, on stocke les différents objets dans un arbre (arborescence) qui quadrille la scène en volumes imbriqués, chaque feuille (extrémité) contenant quelques objets. On regarde si une feuille de l'arbre est visible cad dans le (volume) champ de vue, et alors on trace les objets que cette feuille contient.
On appelle ça le partitionnement de l'espace. (Il y a les kd-trees, les octrees, les BSP pour les vielles applications)
Une autre difficulté, c'est de savoir si un objet est visible ou non. On regarde s'il est (même partiellement) dans le champ de vue (plus précisément dans le volume View frustum).
C'est une detection de collision 3D entre l'objet et le view frustum.
Pour cela on utilise des volumes englobants autour de chaque objet. (Calculer la pénétration facette par facette de chaque objet contre le view frustum serait beaucoup trop lourd).
Il y en a de 2 types, les boîtes englobantes (bounding boxes) et les sphères englobantes (bounding spheres). Un bon moteur graphique 3d doit gérer les deux, car selon l'objet, l'un peut-être plus précis et adapté que l'autre.
Donc c'est une approximation. Pour des cas critiques et marginaux, on peut quand même se retrouver à tracer un objet qui est pourtant hors champ.
C'est quoi la matérialisation physique du champ de vue en 3D (c'est quoi le view frustum ?)
C'est une pyramide couchée, avec le sommet tronqué par l'écran.
La face avant (sommet coupé), c'est votre écran. Représenté dans la scène 3D. (Parallèle à l'écran évidemment)
La face arrière, c'est le plan de profondeur maximale. (Car toute scène a une profondeur maximale). Parallèle à l'écran.
Les 4 autres faces relient ces 2 faces avant et arrière. Haut bas gauche droite.
PS :
Ce qui permet d'utiliser des algorithmes simples pour détecter si un objet est ou non visible, c'est que le view frustum, une sphère ou un parallélépipède, sont tous des volumes convexes.
Et que les boîtes englobantes sont alignées sur les axes du repère de la scène. Que ce soit individuellement pour les objets, que pour le partitionnement de la scène.
En quelques produits scalaires et comparaisons, on sait si un objet, ou une partie de l'arbre qui partitionne la scène, est visible.
La contrepartie est qu'un volume englobant peut être dans le champ de vue sans que l'objet englobé le soit. False positive. Donc on le trace pour rien. D'où l'importance de bien choisir le type de volume englobant. Ça peut être automatisé. On calcule la boite englobante et la sphère englobante et on garde l'objet englobant qui a le volume le plus petit.
Imaginez un pont. Vu de dessus en 2D.
Largement rectangulaire, par exemple 10 m de largeur, 300 m de longueur.
On trace un cercle l'englobant. Le cercle est vide pour la majorité de la superficie du pont. Pas bien !
On trace un rectangle l'englobant. Là c'est plus fidèle à la superficie qu'il rempli.
Donc on choisira le rectangle comme englobant.
Maintenant imaginons une planète vue en 2D.
Un rectangle ou un carré, serait vide sur ses 4 coins.
Un cercle l'englobera parfaitement.
Donc on choisit le cercle comme englobant.
Comment on calcule un volume englobant ? C'est très simple, et c'est la même technique que l'on soit en 2 ou 3D.
Commençons par les boites englobantes alignées sur les axes.
Elles sont définies par 2 points seulement.
Le premier point est le minimum de toutes les positions des points de l'objet, et le second point, le maximum.
On énumère tous les points de l'objet, et on calcule le minimum et le maximum de leurs coordonnées.
A la fin, les minima définissent le premier point, et les maxima le deuxième.
Facile, non ?
Pour les sphères, c'est un peu différent.
D'abord il faut déterminer son centre. Facile on calcule la moyenne de tous les points de l'objet.
Ensuite on calcule le maximum des distances entre le centre et chaque point de l'objet. C'est le rayon de la sphère.
Une petite parenthèse. En fait on calcule et compare les carrés des distances. Car la racine carré est une opération coûteuse.
C'est seulement à la fin, quand on a la distance carrée maximale, qu'on applique juste une fois la racine carrée, pour avoir le rayon de la sphère.
(La relation d'ordre entre (deux valeurs réelles positives de) la fonction identité et la fonction carrée est la même. La comparaison de deux valeurs au carré et la comparaison de deux valeurs telles quelles sont en bijection. On obtient la même valeur de la comparaison. Si une valeur au carré est plus grande qu'une autre valeur au carré, la valeur telle quelle de la première sera aussi plus grande que la deuxième telle quelle. Donc on est sûr que même si on compare les distances carrées au lieu des distances telles quelles, cela revient à la comparaison des distances telles quelles. Mais vu qu'on s’intéresse à la distance telle quelle, on applique la racine carrée sur la distance finale au carrée, donc maximale, obtenue.)
A ne pas confondre avec la comparaison de la fonction carrée avec l'identité. Sur [0,1], la fonction carrée est inférieure ou égale à l'identité, mais supérieure ensuite jusqu'à l'infini.
Je ne parle ici que des valeurs positives ou nulles. Sur l'intervalle IR+
Les informaticiens n'ont pas les mêmes prérogatives que les mathématiciens. Les informaticiens associent un coût aux différentes opérations mathématiques. En temps de calcul et en mémoire. Tant qu'on peut, quand on est informaticien, on raisonne dans ce cas développé, par les carrés des distances. C'est seulement si nécessaire que l'on appliquera la racine carré. Pour les mathématiciens, c'est juste un signe, pour les développeurs, c'est une opération qui demande une vingtaine de cycles horloges du CPU.
Et les développeurs sont des radins.
(Après, pour un objet donné, pour savoir lequel des deux volumes englobants est le meilleur, il suffit de comparer leurs volumes.
Pour la boîte : on multiplie hauteur, largeur et profondeur.
Pour la sphère, 4 * Pi/3 * rayon^3.
Et on choisit le volume englobant ayant le plus petit volume)
Tous ces calculs sont faits en avance. Pas en temps réel. Lors du chargement de la map, voire encore avant, lors de la conception des niveaux (et enregistrés dans la map).
Une autre difficulté, c'est que c'est parfait pour les objets statiques, mais inadapté pour les objets animés, en mouvement.
En général on gère les objets dynamiques individuellement, on ne les intègre pas dans le partitionnement de la scène.
Dans une scène, l'essentiel affiché est constitué d'objets statiques. Même s'il y qu'une dizaine d'objets dynamiques dans la scène, c'est moins coûteux de les gérer un par un que de les intégrer dans la structure qui partitionne la scène.
Il y a un troisième système pour éliminer le plus d'objects possibles qui ne contribuent pas à la scène, c'est l'ambient occlusion.
Et c'est de deux formes.
Le premier c'est de voir si l'objet qu'on a rendu à l'image précédente a contribué à la scène. (S'il a été complètement masqué par des objets, on ne le trace plus).
Ça a un défaut très visible, si on a un faible nombre d'images par secondes, car son affichage différé, décalé d'une frame se verra.
Par exemple on a un personnage caché par une colonne. Dès que l'on se décale on devrait le voir car n'étant plus caché. Et bien on verra une frame vide, sans le personnage, avant de le voir apparaître d'un coup. Cette technique est gérée en grande partie par le GPU, qui détermine le nombre de pixels visibles de l'objet, et qui renvoit après coup ce résultat au CPU. Le résultat est reçu par le CPU à la fin du rendu de frame, d'où le décalage d'une frame pour le rendu de la prochaine frame.
L'autre technique est géométrique. Assez sensiblement proche de la technique de partitionnement de la scène en secteurs reliés par des portails. C'est géré entièrement par le CPU.
On définit deux types d'objets : les occulters, et les occulted. (C'est en anglais
En gros il y'a les objets qui masquent certains objets de la scène et ceux qui sont masqués par d'autres objets de la scène.) On ne trace pas un objet qui est derrière un autre s'il est couvert par l'objet devant lui.
Si vous utilisez un moteur 3d tout fait, ces outils sont déjà programmés et disponibles. Nul besoin de les créer, il suffit de les utiliser.
Même en ne faisant que les utiliser si vous êtes concepteur de niveau, ce n'est pas si simple.
[EDIT]
Il y a encore une optimisation, la plus simple, et entièrement gérée par le GPU, qui permet de ne pas tracer les facettes orientées vers l'arrière. On économise environ 50% de temps de tracé d'un objet.
Les facettes ont un sens en 3D. D'un coté elles sont visibles et de l'autre non.
C'est fait en calculant la composante z (profondeur) de la normale de la surface. Si elle est négative, on ne trace pas la facette. (composante z du produit vectoriel de 2 vecteurs de la face)
Seulement, il faut s'assurer que l'objet est convexe, sinon il peut y avoir des "trous".
Par exemple, dans le premier Assassin's Creed, la capuche du héro n'est pas affichée quand on la voit de l'intérieur.(Quand on regarde le personnage sur le coté). Dans cette situation, il faut faire des doubles faces. Mêmes positions, mais orientées à l'inverse.
Yppisétou !