Les graphes de scène

Posté par  (site web personnel) . Édité par Julien Jorge. Modéré par devnewton 🍺. Licence CC By‑SA.
Étiquettes :
45
24
nov.
2022
C et C++

Deuxième partie de mon triptyque qui prend pour prétexte la sortie du graphe de scène VulkanSceneGraph pour parler un peu 3D. Dans le volet précédent, nous avons évoqué les bonds technologiques qui ont permis le rendu 3D raster, tel que nous le connaissons aujourd'hui, basé sur OpenGL et Vulkan. Aujourd'hui, parlons de graphes de scènes.

Considérant qu'une scène, c'est la définition graphique d'un monde à représenter à l'écran, un graphe de scène, c'est une structure qui hiérarchise les différents éléments de la scène au sein d'un graphe, car cette représentation est particulièrement pertinente.

Sommaire

En pratique, il existe de nombreuses manières de construire un graphe de scène, qui seront adaptées à l'utilisation que l'on en fait. Le graphe de scène sous-jacent à Blender n'a par exemple rien à voir avec celui du dernier Call of Duty.

Un graphe de scène commence souvent par un nœud racine, sur lequel sont attachés une hiérarchie de nœuds pouvant représenter des transformations dans l'espace (translations, rotations…), des changements d'état (couleurs, shader courant…), de la géométrie (formes géométriques simples, amas de triangles) et autres types de nœuds plus exotiques, nous y reviendrons.

Rendre la scène à l'écran, c'est donc traverser le graphe en profondeur, et appliquer à chaque visite de nœud la transformation à effectuer.

Graphe de scene

Par exemple, en visitant ce graphe, l'on va indiquer à l'API 3D d'effectuer les actions suivantes:

  • Appliquer la matrice m1
  • Mettre l'attribut couleur à rouge
  • Afficher une sphère
  • Enlever l'attribut couleur
  • Appliquer la matrice m2
  • Mettre l'attribut couleur à vert
  • Afficher un cube
  • Enlever l'attribut couleur
  • Enlever la transformation m2
  • Enlever la transformation m1
  • Afficher un tore

Voyons maintenant plus en détail les avantages liés à l'utilisation du graphe de scènes

Hiérarchiser la géométrie

En structurant sa scène avec des nœuds de transformation auxquels sont ajoutés les géométries, il est bien plus aisé de gérer des transformations complexes d'objets liés les uns aux autres. Prenons par exemple un bras robotique: la position de la main dépend de la position du coude, qui elle même dépend de la position de l'épaule. Plutôt que d'appliquer une transformation complexe à la main qui prendrait en compte tous les paramètres du coude et de l'épaule, il est bien plus simple d'avoir une série de matrices de transformations d'un objet relatif à son parent: le coude est rattaché à l'épaule, et la main au coude. En contrôlant la rotation au niveau de l'épaule, les transformations vont s'appliquer en combinant chaque matrice et la main va suivre le mouvement.

Élimination des géométries non visibles

Vous connaissez peut-être l'aphorisme qui dit que le code le plus rapide est celui que l'on exécute pas. De la même manière, la géométrie la plus rapide est celle que l'on affiche pas, et il est donc très utile de déterminer très tôt quels sont les objets que l'on aura pas besoin d'afficher à l'écran. Les graphes de scène sont particulièrement utiles pour cela.

L'approche générale est, pour chaque nœud, de déterminer un volume simple qui l'engloble ainsi que tous ses enfants. On peut utiliser des sphères ou des boites alignés sur les axes, et on les calcule à l'avance. On visite ensuite le graphe : pour chaque nœud enfant de la racine, on calcule l'intersection du volume englobant du nœud avec le frustum, la pyramide tronquée représentant ce que la caméra peut voir. Si le volume englobant est complètement à l'extérieur, le nœud (et par extension tous ses enfants) peut être éliminé. Si le volume englobant est complètement à l'intérieur du frustum, le nœud et tous ses enfants doivent être affichés. S'il est à cheval sur le frustum, alors on visite chaque enfant et on applique récursivement la même opération.

Optimisation du rendu

L'optimisation du rendu d'une scène peut certainement faire l'objet d'un livre entier, mais notons cependant qu'à chaque rendu, il est important de réduire au maximum le nombre d'appels vers la carte graphique. Ainsi, il est plus efficace de charger à l'avance les géométries dans les tampons de la carte graphique, et il est plus efficace de changer le moins possible les états comme la position des lumières, le shader courant, et ainsi de suite.

On peut donc analyser le graphe afin de le transformer pour combiner les nœuds qui peuvent l'être. Par exemple, plutôt que de sélectionner le shader approprié pour chaque géométrie, l'on peut grouper les géométries utilisant le même shader, et ne le sélectionner qu'une fois.

Combinaison des nœuds shaders

De même, si l'on permet au graphe d'être un graphe acyclique plutôt qu'un arbre, l'on peut atteindre le même nœud à travers des chemins différents, et donc représenter le même objet avec des transformations différentes (pensez à une forêt qui contient de nombreuses fois le même arbre) permettant par exemple d'économiser de la place dans les tampons de géométrie, voire de permettre certaines formes de cache.

Combinaison des nœuds de geometrie

Et bien d'autres

Mentionnons encore quelques opérations où un graphe de scène est bien utile.

  • Gestion des niveaux de détail : un nœud LOD peut avoir une série d'enfants correspondant au même objet plus ou moins détaillé, et afficher l'objet approprié selon la distance à la caméra : inutile d'utiliser des milliers de polygones pour afficher un objet qui fait 2 pixels sur l'horizon !

  • Le picking : à partir d'un point à l'écran, on peut appliquer les transformations inverses et trouver la liste d'objets situés sous le point, ce qui permet à l'utilisateur de sélectionner un objet

Utilisation avancée des graphes de scènes

Une scène d'un moteur graphique moderne est extraordinairement complexe et nécessite de nombreuses passes : souvent, le moteur va rendre une partie de la scène dans une texture en ayant appliqué des calques ou des shaders, et utiliser ensuite cette texture dans le rendu final, par exemple pour gérer les ombres ou encore les réflexions (pensez à un objet qui se reflète dans de l'eau, par exemple). Le rendu final lui-même est parfois rendu dans une texture avant d'être affiché à l'écran afin d'appliquer des shaders sur l'ensemble de l'écran, par exemple pour émuler une vue à travers des lunettes de vision nocturne, ou encore un affichage flou si le personnage est ivre. Par l'utilisation judicieuse de nœuds spécialisés, comme de nœuds caméra par exemple, ou carrément de nœuds d'effets qui gèrent les ombres automatiquement, il est possible de fournir au développeur une série d'outils de haut niveau, optimisés, et prêts à l'emploi. C'est exactement le but suivi par OpenSceneGraph, et c'est là dessus que nous finirons cette série.

  • # Entity Component System

    Posté par  (site web personnel) . Évalué à 6.

    Une question qui me turlupine quand même, c'est comment intégrer efficacement un SceneGraph et un ECS.

    Le but des ECS c'est de stocker les données de manière contigüe en mémoire, afin de gagner en performance lors de l'accès aux données.

    On va donc avoir un tableau de "transform", un tableau de "shader", un tableau de "mesh", etc… (tableau dans le sens non-IT du terme, l'implémentation peut être un array, un sparse set, un vector, etc… ce n'est pas de ça que je parle ici quand je dis tableau)

    Et on va ensuite avec une fonction "render" qui va itérer sur ces tableaux. Et les caches du CPU seront bien content.

    Sauf que un SceneGraph, c'est un graphe acyclique. Donc des pointeurs vers des structures qui contiennent des pointeurs vers d'autres structures.

    Je vois alors 2 solutions :

    • le composant "transform" contient une référence vers le noeud du SceneGraph : mince on doit faire un aller/retour entre le CPU et la RAM, le gain de perf est nullifié
    • les noeuds du SceneGraph ont une référence vers l'entité, chaque frame on doit vérifier si l'entité existe encore et synchroniser le SceneGraph, puis mettre à jour le composant "transform" de l'entité : aucune idée du coût en performance de faire ça a chaque frame

    Y-a-t-il d'autres solutions ?

    https://link-society.com - https://kubirds.com - https://github.com/link-society/flowg

    • [^] # Re: Entity Component System

      Posté par  (site web personnel) . Évalué à 3. Dernière modification le 06 décembre 2022 à 12:24.

      Un graphe de transformation hiérarchique doit forcément être résolu à un moment donné.

      La façon de le faire dépend du type de jeux et du besoin ; as-tu vraiment besoin de X niveaux de hiérarchie sur l’entièreté des objets de ta scène ?

      Le logiciel Maya stock deux matrices par nœud (une transformation locale et une transformation monde) et un système de propagation d’un flag de dirty. Quand un parent bouge, le flag est propagé sur la hiérarchie qui recalcule la transformation monde de chaque nœud.

      Cette méthode n’est pas adaptée au jeu vidéo.

      Pour les mouvements sur des personnages, un skinning GPU, mais sans interpolation (une seule matrice par point) permet de gérer une hiérarchie, façon « jouet transformer ».

      Tu peux ajouter, au-dessus de ce skin GPU, une hiérarchie de transformations qui feront donc partie du skinning. C’est à double tranchant, car ces opérations (qui donneront le même résultat) seront donc générées autant de fois que d’objets. Tu peux minimiser ça par des concepts avancés comme le Tansform feedback, pour calculer la hiérarchie globale en une fois et réutiliser les transformations monde résultantes sur les objets.

      Si cette hiérarchie de joints est déterminé à l’avance (leur nombre et l’ordre), ton vextex shader hard codera l’ordre de résolution des transformations et devrait être en mesure de déterminer la position finale de chaque transformation (et donc, points).

      Tu remarqueras que laisser ça au GPU rend la problématique orthogonale aux considérations ECS.

      C’est comme ça que je ferais.

  • # Joli vulgarisation

    Posté par  . Évalué à 2.

    Merci, super article !
    Ça me fait remonter à loiiiiiin…

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.