Discussion :

[Radikal333]

Bonjour à tous,

je développe un petit moteur 3D (C++ DirectX) et je m'interroge sur la gestion de la scène.

Apparemment un gestionnaire de scène consiste en un arbre organisant les différents éléments de la scène pour en optimiser le rendu. Voici mes questions:

- Quels éléments l'arbre doit-il gérer? (meshes-lumieres-sons...)
- Que doit ou peut contenir un noeud?
- Selon quels criteres doit-on trier l'arbre: est-ce selon l'ordre d'affichage, le frustrum, la position, ou plutot selon le management des ressources c'est à dire les effets/textures/etc. ?
- Que vient faire l'octree/quadtree dans tout ca?

Merci pour vos idées!

[alt3]

Par exemple un arbre BSP ?
(mais il doit exister mieux).

[Radikal333]

Mais je pensais que les arbres BSP (comme les octree/quadtree) s'intercalaient apres la gestion des objets de la scène, c'est à dire:
1. On range les objets dans un arbre selon certains criteres (lesquels?)
2. Dans la boucle de rendu, on parcours l'arbre pour récupérer ces objets (peut etre en en éliminant déjà une partie)
3. L'arbre BSP (par exemple) prend chaque objet (ou chaque polygone?) et détermine si oui ou non il doit être affiché

Finalement le fond de ma question, c'est comment on stocke en mémoire les objets de la scene. Car si on fait un "bete" tableau d'objets, on se prive de pas mal d'optimisations qui auraient pu être réalisées par un arbre, non? (genre éviter trop de changements de l'état du device)

[alt3]

Je ne suis pas un spécialiste, mais ce qui est sûr c'est que l'arbre BSP est valable uniquement pour les polygones statiques.

Pour les choses dynamiques, après c'est plus complexe, ca dépend de la nature des objets (particules, deformables, physics).

[Radikal333]

ok, merci pour tes précisions alt3. L'arbre BSP effectue donc bien seulement un tri. Cependant ma question demeure: comment stocker les objets?

[khayyam90]

Bien le bonjour,

Un scene manager doit gérer tous les objets d'une scène et ce, de manière hiérarchique. Des objets peuvent être fils d'autres objets.

Chaque noeud de l'arbre possède sa propre matrice de transformation. Le parcours de l'arbre se fait en profondeur d'abord en empilant et dépilant ces matrices de transformations. Chaque transformation d'un noeud est exprimée en fonction du noeud parent. La transformation absolue d'une feuille de l'arbre est le produit des matrices de tous les éléments parents.
Et chaque noeud peut posséder des objets tels que des meshs, mais il peut aussi ne rien posséder d'autre que sa matrice de transformation.

Cet arbre, aussi appelé scene graph n'est pas forcément suffisant pour stocker correctement une scène. Il peut être intéressant de le combiner avec un bsp/quadtree/octree.

Je m'avance peut-être, mais disons que le scene graph est plus adapté aux objets mobiles et les arbres de partionnement sont plus adaptés aux objets fixes. Evidemment, rien n'empêche de faire figurer un objet dans le scene graph et dans un arbre de partitionnement ... en ne stockant que des pointeurs dans tes arbres tu peux avoir des handles sur tes objets un peu partout.

[Radikal333]

nickel, merci pour ta réponse c'est exactement ce que je voulais savoir.
Dernière petite question avant de mettre résolu:
Est-ce le loadeur de map qui détermine la construction du scene graph?

Car je me dit la chose suivante: puisqu' un objet fils récupère toutes les transformations de son parent, la matrice propre à l'objet fils est en fait un "mouvement" relatif au parent.
Donc finalement, la profondeur de notre arbre de scene est faible! (peu d'objets ont un mouvement relatif à un autre objet). En un mot, peut-etre qu'il suffit d'indiquer dans le fichier contenant l'objet (mesh par ex) les dépendances avec les autres objets ?

[Bakura]

Pour repondre a l'octree/quadtree, c'est un partitionement de l'espace, afin, par exemple, d'eliminer rapidement des donnees qui ne seront pas visible.

Pour le cas de l'octree (je ferai un tuto dessus), c'est tres simple. Pour faire court, chaque noeud est subdivise en 8 autres noeuds. Lors de l'ajout d'un element, tu parcours l'arbre : si la boite englobante de l'objet (ou AABB), est contenue entierement dans le noeud de l'octree, on subdivise, jusqu'a ce qu'on atteigne un niveau de recursion maximal, ou alors si la boite englobante de l'objet chevauche l'AABB d'un noeud, auquel cas l'objet est ajoute dans le noeud parent.

C'est tres simple dans le principe, et tres simple a coder. Apres j'ai reussi a le faire correctement pour des donnees statiques, des que ca bouge, c'est tout un autre probleñe...

[granquet]

Chaque noeud de l'arbre possède sa propre matrice de transformation. Le parcours de l'arbre se fait en profondeur d'abord en empilant et dépilant ces matrices de transformations.

en train de developper mon moteur 3D (juste pour deconner, pas pour faire un truc qui marche ), cet affirmation me laisse perplexe
pourquoi faire un DFS (Depth First Search) et pas un BFS (Breadth First Search)?
les objets étant empilé avec une relation parent/enfant, ça me semblait plus logique d'afficher tous les objets du même niveau à la suite et ainsi pouvoir éliminer plus vite les branches à ne pas afficher.

peut être pour limiter le nombres de "transformations de la matrice"?

[bafman]

non, il faut bien faire une recherche en profondeur d'abord.
le resultat au niveau clipping des fils sera le même, mais comme on empile des matrices, on evite d'avoir à remonter l'ensemble de la hierarchie à chaque fois.

on peut bien entendu contourner le problème en stockant deux version de la matrice des noeud : une matrice locale et une matrice globale, et lors d'une modification d'un noeud, on met a jours ses fils. ca a le double aventage de limiter les calculs de matrice dans les environnement fortement statiques et d'avoir toujours sous la main la matrice d'affichage du noeud, mais par contre, ca augmente l'occupation memoire de chaque noeud, et c'est consommateur en cas d'envirennement fortement dynamique (car chaque modification de noeud va provoquer un recalcule de tout le sous arbre)

[granquet]

effectivement, après réflexion, c'était idiot de partir sur un parcours en largeur (BFS)
je voulais faire un truc compliqué qui tiendrais compte du nombre de polygones total a afficher et qui adapterais la profondeur de parcours de l'arbre en fonction d'un ratio polygone/nombre d'objet ... mais finalement je me dis que je vais plus y perdre qu'y gagner, et puis comme disais l'autre: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil."

[bob25]

oui il faut pas confondre l'arbre d'affichage (avec sa matrice par noeud), qui sert un peu comme les bones à gérer des rapports parent/child entre des objets en mouvement, (par exemple une voiture dont chaque roue est enfant de chaque piston qui est enfant du chassis...) et les arbres spatiaux (octree etc) qui font partie des modeles de subdivisions d'espace et qui servent à ranger les données (les bsp sont bien pour gérer les architectures et les octree une bonne roue de secours pour les maillages plus anarchiques)


pour un environnement qui bouge souvent on fait un arbre avec la partie statique du décor dans un premier temps, et ensuite rajouter les parties mobiles qui ont leur propre structure, par exemple les arbres de sphere pour les décors animés avec des bones


[edit]plus precisement aux questions de radikal:

- Quels éléments l'arbre doit-il gérer? (meshes-lumieres-sons...)
- Que doit ou peut contenir un noeud?

un arbre et ses noeuds et feuilles peuvent contenir ce que tu veux. normalement il faut tout ranger dedans y compris les sons d'ambiance etc. les arbres en 3d c'est exactement comme les grille pour la 2d ça sert à ranger toutes les données du jeu.

- Selon quels criteres doit-on trier l'arbre: est-ce selon l'ordre d'affichage, le frustrum, la position, ou plutot selon le management des ressources c'est à dire les effets/textures/etc. ?

l'arbre sert à gérer l'ordre des faces et le culling essentiellement il se base sur la structure polygonale surtout (on coupe là où il y a des polygones)
on peut ensuite optimiser pour les matériaux, par exemple en combinant un arbre bsp avec des secteurs (chaque secteur ayant un matériau unique), mais c'est secondaire.

- Que vient faire l'octree/quadtree dans tout ca?

le quad tree c'est une grille en 2d avec des cases de diffrentes tailles pour économiser l'espace mémoire.

les octree c'est la même chose en 3d

[Radikal333]

Merci pour toutes ces réponses, c'est nettement plus clair maintenant.

Un problème demeure concernant l'héritage des objets et la gestion de la physique. Sur l'exemple de la voiture, si la matrice de position de la roue est relative à celle du piston, elle-même relative à celle du chassis, nous avons un arbre du style:

Chassis
|
Piston
|
Roue

et si la voiture bouge, le piston et la roue suivent le mouvement (heureusement). Donc si chaque noeud contient la matrice de position relative de l'objet, on calcule la position de chaque objet en parcourant l'arbre de sa racine jusqu'à l'objet en question tout en multipliant les matrices.

Hors si maintenant je souhaite gérer la physique genre rotation de la roue et son contact avec le sol, la matrice calculée par le moteur physique (Newton en l'occurence) est absolue, c'est à dire non relative aux parents de la hierarchie ce qui brise tout le concept de hierarchie des matrices!

Qu'en pensez vous (dites moi si je me suis mal exprimé) ?

[bob25]

c'est normal c'est le moteur physique qui gère les relations entre les roues et le chassis donc pas besoin d'arbre, mon exemple était donc un mauvais exemple

[Radikal333]

Donc par exemple simplement un arbre contenant les objets hierarchisés (dans le sens logique du terme et non technique) dont chaque noeud possède la matrice de position absolue?

[bob25]

un meilleur exemple: si tu veux mettre une lumière de gyrophare il faut qu'elle soit enfant de ton objet chassis (pareil pour les phares etc)

les relations parent child ont du sens pour ce genre de truc


exemple: si j'ai une scène avec 3 spheres qui bougent sur un decor je n'ai pas besoin de relations parent/child entre ces objets, donc tous les objets sont enfants du noeud racine

pour commencer le developpement d'un jeu il n'y a pas besoin d'aller plus loin


si je veux ensuite qu'une de mes trois boules ait une petite boite dont la position soit toujours la même par rapport à la boule alors je l'ajoute en child à la boule, mais ça c'est des effets esthétiques qu'on ajoute une fois que le moteur de jeu tourne avec des boules et des cubes



l'important c'est l'arbre spatial qui gère le gros du gameplay

en toute logique ton moteur physique en utilise déjà un pour tester les colllisions, mais je ne sais pas s'il gère l'affichage des polygones et la generation/destruction d'objets selon si la camera les voit ou pas, c'est pourquoi il te faudra probablement créer un autre arbre pour gérer ça.


quand à l'arbre de matrices de transformations c'est un truc qu'on voit après, pour les effets visuels uniquement

[Radikal333]

OK je comprend mais alors comment déduire la matrice d'un objet si certaines sont obtenues par produit des matrices parent et d'autres sont directement fournies par le moteur physique? Avec un booléen indiquant si l'objet est soumis à la physique ou non?

EDIT: il est vrai que les relations parent/enfant sont peu nombreuses dans un monde 3D mais puisqu'elles existent (imagines un personnage tenant une épée ou un gun) il faut bien les gérer.

[bob25]

oui un objet enfant du bone main du personnage aussi c'est un bon exemple

[Radikal333]

OK merci j'y vois plus clair. En fait, je ne peux pas séparer la gestion de la physique de la hierarchie des objets pour la raison suivante:

si je souhaite modéliser une voiture (toujours la même, avec ses pistons et tout ), je dois gérer un arbre de hierarchie dont les matrices sont
- absolues si gérées par le moteur physique
- relatives pour les relations parent/enfant

Evidemment ce modèle hybride a un gros défaut: c'est le moteur physique qui gère toute la transformation de la roue de la voiture donc pour cette roue on ne tire pas avantage des relations parent/enfant!

[bob25]

alors en fait heu j'essaye de répondre avec mes mots ^^

si je fais bouger une voiture avec juste les trucs du moteur physique

l'arbre de ma scene est comme ça:

noeud racine de la camera
-chassis
-roue1
-roue2
...
-terrain

on a donc que des matrices absolue



si j'ajoute un truc non géré par le moteur physique genre un gyrophare:


-noeud racine de la camera
-chassis
--gyrophare
-roue1
-roue2
...
-terrain


là les liens de parenté dans l'arbre de matrices d'affichage servent a quelque chose