Graphique de scène

Un graphe de scène est une structure de données générale couramment utilisée par les applications d'édition graphique vectorielles et les jeux informatiques modernes, qui organise la représentation logique et souvent spatiale d'une scène graphique. Il s'agit d'un ensemble de nœuds dans une structure graphique ou arborescente . Un nœud arborescent peut avoir de nombreux enfants mais un seul parent, l'effet d'un parent étant appliqué à tous ses nœuds enfants ; une opération effectuée sur un groupe propage automatiquement son effet à tous ses membres. Dans de nombreux programmes, l'association d'une matrice de transformation géométrique (voir aussi transformation et matrice ) à chaque niveau de groupe et la concaténation de ces matrices ensemble constituent un moyen efficace et naturel de traiter de telles opérations. Une caractéristique commune, par exemple, est la possibilité de regrouper des formes et des objets liés dans un objet composé qui peut ensuite être manipulé aussi facilement qu'un objet unique.

Dans l'édition de graphiques vectoriels, chaque nœud feuille d'un graphe de scène représente une unité atomique du document, généralement une forme telle qu'une ellipse ou un chemin de Bézier . Bien que les formes elles-mêmes (en particulier les chemins) puissent être décomposées en nœuds tels que les nœuds splines , il est pratique de considérer le graphe de scène comme composé de formes plutôt que de passer à un niveau de représentation inférieur.

Un autre concept de nœud utile et piloté par l'utilisateur est le calque . Un calque agit comme une feuille transparente sur laquelle un nombre quelconque de formes et de groupes de formes peuvent être placés. Le document devient alors un ensemble de calques, dont chacun peut être facilement rendu invisible, grisé ou verrouillé (mis en lecture seule). Certaines applications placent tous les calques dans une liste linéaire, tandis que d'autres prennent en charge les calques au sein des calques à n'importe quelle profondeur souhaitée.

En interne, il n'y a peut-être aucune différence structurelle réelle entre les couches et les groupes, car ils ne sont que des nœuds d'un graphe de scène. Si des différences sont nécessaires, une déclaration de type courante en C++ consisterait à créer une classe de nœuds générique, puis à dériver les couches et les groupes en tant que sous-classes. Un membre de visibilité, par exemple, serait une fonctionnalité d'une couche, mais pas nécessairement d'un groupe.

Les graphes de scène sont utiles pour les jeux modernes utilisant des graphismes 3D et des mondes ou niveaux de plus en plus grands. Dans de telles applications, les nœuds d'un graphe de scène représentent (généralement) des entités ou des objets dans la scène.

Par exemple, un jeu peut définir une relation logique entre un chevalier et un cheval de telle sorte que le chevalier soit considéré comme une extension du cheval. Le graphe de scène comporterait un nœud « cheval » auquel serait rattaché un nœud « chevalier ».

Le graphique de scène peut également décrire la relation spatiale, ainsi que logique, des différentes entités : le chevalier se déplace dans l'espace 3D comme le cheval se déplace.

Dans ces applications de grande taille, les besoins en mémoire sont des considérations majeures lors de la conception d'un graphe de scène. Pour cette raison, de nombreux systèmes de graphes de scène de grande taille utilisent l'instanciation géométrique pour réduire les coûts de mémoire et augmenter la vitesse. Dans notre exemple ci-dessus, chaque chevalier est un nœud de scène distinct, mais la représentation graphique du chevalier (composée d'un maillage 3D, de textures, de matériaux et de shaders) est instanciée. Cela signifie qu'une seule copie des données est conservée, qui est ensuite référencée par tous les nœuds « chevalier » dans le graphe de scène. Cela permet de réduire le budget mémoire et d'augmenter la vitesse, car lorsqu'un nouveau nœud chevalier est créé, les données d'apparence n'ont pas besoin d'être dupliquées.

La forme la plus simple d'un graphe de scène utilise une structure de données de type tableau ou liste chaînée , et l'affichage de ses formes consiste simplement à parcourir linéairement les nœuds un par un. D'autres opérations courantes, telles que la vérification de la forme qui coupe le pointeur de la souris, sont également effectuées via des recherches linéaires. Pour les petits graphes de scène, cela a tendance à suffire.

L'application d'une opération sur un graphe de scène nécessite un moyen de répartir une opération en fonction du type d'un nœud. Par exemple, dans une opération de rendu, un nœud de groupe de transformation accumulerait sa transformation par multiplication de matrice, déplacement de vecteur, quaternions ou angles d'Euler . Après quoi, un nœud feuille envoie l'objet pour rendu au moteur de rendu. Certaines implémentations peuvent restituer l'objet directement, ce qui invoque l' API de rendu sous-jacente , telle que DirectX ou OpenGL . Mais comme l'implémentation sous-jacente de l' API de rendu manque généralement de portabilité, on peut séparer le graphe de scène et les systèmes de rendu à la place. Afin d'accomplir ce type de répartition, plusieurs approches différentes peuvent être adoptées.

Dans les langages orientés objet comme C++ , cela peut être facilement réalisé à l'aide de fonctions virtuelles , où chacune représente une opération pouvant être effectuée sur un nœud. Les fonctions virtuelles sont simples à écrire, mais il est généralement impossible d'ajouter de nouvelles opérations aux nœuds sans avoir accès au code source. Alternativement, le modèle visiteur peut être utilisé. Cela présente un inconvénient similaire dans la mesure où il est tout aussi difficile d'ajouter de nouveaux types de nœuds.

D'autres techniques impliquent l'utilisation de RTTI ( Run-Time Type Information ). L'opération peut être réalisée sous forme de classe transmise au nœud actuel ; elle interroge ensuite le type du nœud à l'aide de RTTI et recherche l'opération correcte dans un tableau de rappels ou de foncteurs . Cela nécessite que la carte des types vers les rappels ou les foncteurs soit initialisée au moment de l'exécution, mais offre plus de flexibilité, de rapidité et d'extensibilité.

Il existe des variantes de ces techniques et de nouvelles méthodes peuvent offrir des avantages supplémentaires. Une alternative est la reconstruction du graphe de scène, où le graphe de scène est reconstruit pour chacune des opérations effectuées. Cette méthode peut toutefois être très lente, mais produit un graphe de scène hautement optimisé. Elle démontre qu'une bonne implémentation d'un graphe de scène dépend fortement de l'application dans laquelle il est utilisé.

Les traversées sont la clé de la puissance de l'application d'opérations aux graphes de scène. Une traversée consiste généralement à démarrer à un nœud arbitraire (souvent la racine du graphe de scène), à ​​appliquer la ou les opérations (souvent les opérations de mise à jour et de rendu sont appliquées l'une après l'autre), et à descendre de manière récursive dans le graphe de scène (arbre) jusqu'aux nœuds enfants, jusqu'à ce qu'un nœud feuille soit atteint. À ce stade, de nombreux moteurs de graphes de scène remontent ensuite l'arbre, en appliquant une opération similaire. Par exemple, considérons une opération de rendu qui prend en compte les transformations : lors du parcours récursif de la hiérarchie du graphe de scène, une opération de pré-rendu est appelée. Si le nœud est un nœud de transformation, il ajoute sa propre transformation à la matrice de transformation actuelle. Une fois que l'opération a terminé de parcourir tous les enfants d'un nœud, elle appelle l'opération de post-rendu du nœud afin que le nœud de transformation puisse annuler la transformation. Cette approche réduit considérablement la quantité nécessaire de multiplication de matrice.

Certaines opérations de graphe de scène sont en fait plus efficaces lorsque les nœuds sont parcourus dans un ordre différent. C'est là que certains systèmes implémentent la reconstruction du graphe de scène pour réorganiser le graphe de scène dans un format ou un arbre plus facile à analyser.

Par exemple, dans les cas 2D, les graphes de scènes se rendent généralement eux-mêmes en commençant par le nœud racine de l'arbre, puis en dessinant de manière récursive les nœuds enfants. Les feuilles de l'arbre représentent les objets les plus au premier plan. Étant donné que le dessin se déroule de l'arrière vers l'avant, les objets les plus proches écrasant simplement les plus éloignés, le processus est connu sous le nom d'utilisation de l' algorithme de Painter . Dans les systèmes 3D, qui utilisent souvent des tampons de profondeur , il est plus efficace de dessiner d'abord les objets les plus proches, car les objets les plus éloignés n'ont souvent besoin que d'être testés en profondeur au lieu d'être réellement rendus, car ils sont occultés par des objets plus proches.

Les hiérarchies de volumes englobants (BVH) sont utiles pour de nombreuses tâches, notamment pour éliminer efficacement les objets et accélérer la détection des collisions entre eux. Une BVH est une structure spatiale, mais elle n'a pas besoin de partitionner la géométrie (voir partitionnement spatial ci-dessous).

Un BVH est un arbre de volumes englobants (souvent des sphères, des boîtes englobantes alignées sur des axes ou des boîtes englobantes orientées). Au bas de la hiérarchie, la taille du volume est juste assez grande pour englober étroitement un seul objet (ou peut-être même une fraction plus petite d'un objet dans les BVH haute résolution). Au fur et à mesure que l'on monte dans la hiérarchie, chaque nœud a son propre volume qui englobe étroitement tous les volumes situés en dessous. À la racine de l'arbre se trouve un volume qui englobe tous les volumes de l'arbre (la scène entière).

Les BVH sont utiles pour accélérer la détection de collision entre objets. Si le volume englobant d'un objet ne coupe pas un volume plus haut dans l'arbre, il ne peut pas couper d'objet en dessous de ce nœud (ils sont donc tous rejetés très rapidement).

Il existe quelques similitudes entre les BVH et les graphes de scène. Un graphe de scène peut facilement être adapté pour inclure/devenir un BVH – si chaque nœud est associé à un volume ou s'il existe un « nœud lié » spécialement conçu et ajouté à un emplacement pratique dans la hiérarchie. Ce n'est peut-être pas la vue typique d'un graphe de scène, mais il y a des avantages à inclure un BVH dans un graphe de scène.

Une manière efficace de combiner le partitionnement spatial et les graphiques de scène consiste à créer un nœud feuille de scène contenant les données de partitionnement spatial. Cela peut augmenter l'efficacité de calcul du rendu.

Les données spatiales sont généralement statiques et contiennent généralement des données de scène non mobiles sous une forme partitionnée. Certains systèmes peuvent avoir les systèmes et leur rendu séparément. C'est très bien et aucune des deux méthodes ne présente de réels avantages. En particulier, il est mauvais d'avoir le graphe de scène contenu dans le système de partitionnement spatial, car le graphe de scène est mieux considéré comme le système le plus vaste du partitionnement spatial.

Les dessins de très grande taille ou les graphiques de scène générés uniquement au moment de l'exécution (comme c'est le cas dans les programmes de rendu par lancer de rayons ) nécessitent la définition de nœuds de groupe de manière plus automatisée. Un traceur de rayons, par exemple, prendra une description de scène d'un modèle 3D et créera une représentation interne qui décompose ses parties individuelles en boîtes englobantes (également appelées dalles englobantes). Ces boîtes sont regroupées de manière hiérarchique afin que les tests d'intersection de rayons (dans le cadre de la détermination de la visibilité) puissent être calculés efficacement. Une boîte de groupe qui n'intersecte pas un rayon oculaire, par exemple, peut ignorer entièrement le test de l'un de ses membres.

Une efficacité similaire est également observée dans les applications 2D. Si l'utilisateur a agrandi un document de manière à ce qu'une partie seulement soit visible sur l'écran de son ordinateur, puis qu'il le fait défiler, il est utile d'utiliser un cadre de délimitation (ou dans ce cas, un schéma de rectangle de délimitation) pour déterminer rapidement quels éléments du graphique de scène sont visibles et doivent donc être dessinés.

En fonction des spécificités des performances de dessin de l'application, une grande partie de la conception du graphe de scène peut être affectée par des considérations d'efficacité de rendu. Dans les jeux vidéo 3D tels que Quake , les arbres de partitionnement spatial binaire (BSP) sont fortement favorisés pour minimiser les tests de visibilité. Les arbres BSP, cependant, prennent beaucoup de temps à calculer à partir des graphes de scène de conception et doivent être recalculés si le graphe de scène de conception change, de sorte que les niveaux ont tendance à rester statiques et les personnages dynamiques ne sont généralement pas pris en compte dans le schéma de partitionnement spatial.

Les graphes de scène pour les objets réguliers denses tels que les champs de hauteur et les maillages polygonaux ont tendance à utiliser des quadtrees et des octrees , qui sont des variantes spécialisées d'une hiérarchie de boîtes englobantes 3D. Étant donné qu'un champ de hauteur occupe lui-même un volume de boîte, la subdivision récursive de cette boîte en huit sous-boîtes (d'où le « oct » dans octree) jusqu'à ce que les éléments de champ de hauteur individuels soient atteints est efficace et naturelle. Un quadtree est simplement un octre 2D.

PHIGS a été la première spécification commerciale de graphe de scène et est devenue une norme ANSI en 1988. Des implémentations disparates ont été fournies par des fournisseurs de matériel Unix . Le système graphique 3D HOOPS semble avoir été la première bibliothèque commerciale de graphes de scène fournie par un seul fournisseur de logiciels. Il a été conçu pour fonctionner sur des interfaces 2D et 3D de bas niveau disparates, la première version de production majeure (v3.0) ayant été achevée en 1991.

Silicon Graphics (SGI) a publié OpenGL Performer ou plus communément appelé Performer en 1991, qui était le système de graphe de scène principal pour la plupart des produits SGI dans le futur. IRIS Inventor 1.0 (1992) a été publié par SGI, qui était un graphe de scène de haut niveau construit sur Performer. Il a été suivi par Open Inventor en 1994, une autre itération du graphe de scène de haut niveau construit sur les versions plus récentes de Performer. Vous trouverez d'autres bibliothèques de graphes de scène 3D dans la catégorie : API de graphe de scène 3D .

X3D est un format de fichier ouvert et une architecture d'exécution libre de droits permettant de représenter et de communiquer des scènes et des objets 3D à l'aide de XML . Il s'agit d'une norme ISO qui fournit un système de stockage, de récupération et de lecture de contenu graphique en temps réel intégré dans des applications, le tout au sein d'une architecture ouverte pour prendre en charge un large éventail de domaines et de scénarios utilisateur.