Stockage des objets (Preprocessing)

Bonsoir à tous,

Je me lance dans la création de moteurs de jeux en OpenGL, j'essaie d'abord de me documenter sur les bases, les traitements en computer graphics en général. Parmi tout ceci j'ai quand même une question qui reste sans réponse: Est-ce que les objets qui doivent être dessinés doivent être stockés (temporairement) au lieu d'être affiché directement ?

Il y a beaucoup d'algorithmes qui requièrent une vue globale de tout ce qui est à dessiner comme le "Frustum culling", le LOD ("Level of Details"), Raycasting (je suppose aussi). Ces algorithmes doivent bien traiter les données avant qu'elles soient affichées, sinon ça ne sert à rien justement. Il faut donc forcément que les objets soient stockés dans une structure de "mise en attente" pour pré-traitements, ou est-ce que je trompe ?

Si tel est bien le cas, quelles sont les structures que l'on utilise en général (sachant que je fais du C), les algorithmes. Auriez-vous des articles en parlant, des sources à lire svp ? Merci de m'éclairer dans cette obscurité sans fond.

Bonjour,

Pour le frustrum culling, le calcul peut être fait avant l'affichage, à la volé. Il faudra juste se préparé une boite de collision, pour savoir si l'objet est dans l'écran ou pas.
Du coup, s'il n'est pas dans l'écran, on n'affiche pas. Point final :D

-> Donc pour un objet 3D, on calculera à l'avance une boite englobante, pour faire les calculs rapidement.

Le LOD, je crois qu'il est fait aussi à la volée par les shaders. Je ne suis pas à 100% sur là dessus. Sinon il peut aussi être fait par un post processing, selon le schéma suivante:

Rendu simple de la scène -> Tout dans une texture -> Affichage de la texture à l'écran avec un shader, le shader fait une operation de post processing ( LOD pour notre cas ) -> écran

Merci de ta réponse

Bien, je commence à saisir. Il faut gérer les données/vertices lorsqu'on veut les dessiner.

Cependant, cela ne sera pas applicable de cette manière pour la gestion des collisions, non? On utilise des formes simple genre boite et paralléle à l'axe d'origine? Il faut stoquer ces boites pour tester?

Concernant les shaders, ce sera pas pour demain pour moi. J'ai beaucoup à faire avant.

Citation:

---

Envoyé par LittleWhite

Bonjour,

Pour le frustrum culling, le calcul peut être fait avant l'affichage, à la volé. Il faudra juste se préparé une boite de collision, pour savoir si l'objet est dans l'écran ou pas.
Du coup, s'il n'est pas dans l'écran, on n'affiche pas. Point final :D

-> Donc pour un objet 3D, on calculera à l'avance une boite englobante, pour faire les calculs rapidement.

Le LOD, je crois qu'il est fait aussi à la volée par les shaders. Je ne suis pas à 100% sur là dessus. Sinon il peut aussi être fait par un post processing, selon le schéma suivante:

Rendu simple de la scène -> Tout dans une texture -> Affichage de la texture à l'écran avec un shader, le shader fait une operation de post processing ( LOD pour notre cas ) -> écran

---

je ne vois pas bien comment on peut faire du LOD a la volée, par LOD on entend bien un chargement différent de mesh/textures/animation selon la distance, non ? comment faire cela dans les shaders ? à moins que tu ne té réfères à la tesselation, mais c'est assez couteux il me semble

et je comprends encore moins la notion de LOD après le rendu

Citation:

---

et je comprends encore moins la notion de LOD après le rendu

---

Première passe, on fait le rendu de la scène ( pas de problèmes dessus ).On sauvegarde aussi le buffer de profondeur,
Deuxième passe, on floutte ce qui est a une distance qui ne nous plait pas ( utilisation du buffer de profondeur pour connaitre les distances, floutage en faisant une moyenne des pixels alentours de celui qui est vérifié ( merci le rendu vers texture ).

Pour le chargement des données, c'est tout au début, on charge une textures, et on fait un mipmapping dessus, pour faire plus ou moins de détails selon la distance.

Citation:

---

Cependant, cela ne sera pas applicable de cette manière pour la gestion des collisions, non? On utilise des formes simple genre boite et paralléle à l'axe d'origine? Il faut stoquer ces boites pour tester?

---

La gestion de collision est faite du coté CPU, ce qui veut dire, avant même d'executer les fonctions d'affichages.
Forme simple comme des boites oui, mais pas de besoin nécessaire. On stocke les boites, avec les objets ( pour eviter de les régénérés à chaque image :aie: ).

Ca ressemble plus au Depth of field qu'au Lod, qui consiste à dessiner moins de poly lorsqu'un objet est loin (exemple la sphère).

Sinon pour la structure des boites, vous faites simplement deux x, y, z, minimum et maximum et vous les stoquer dans un tableau de toutes les boites, par exemple? Ou alors vous séparez les boites d'objets mobiles?
Quand tu dis avec l'objet, c'est pas très précis puisque pour le moment je n'ai pas structure contenant chaque objet à dessiner. Aussi faut il calculer la boite selon un axe local de l'objet, ca évite de recalculer la boite pour une translation, parcontre pour une rotation?

Merci encore.

Citation:

---

Envoyé par jamesb

Ca ressemble plus au Depth of field qu'au Lod, qui consiste à dessiner moins de poly lorsqu'un objet est loin (exemple la sphère).

Merci encore.

---

hum, en effet LittleWhite, je crois que tu m'as décrit le depth of field et non pas le level of details, celui-ci permettant de limiter le nombre de vertex envoyés au GPU avant le rendu afin d'éviter de rendre des détails qui ne seront pas visible à l'oeil nu

Oui je pense que j'ai faux.

Pour le LOD je ne sais pas le faire :s.

Pour les rotations, oui, il faudra recalculer la boite. Sinon, on peut aussi utiliser une sphère de collision, qui est moins précise.
Quand je dis, attaché à l'objet, d'un point de vue du design de l'application. Sinon, oui je garde juste les points en min et max. ( Qui sont généré au début, qui sont dans les coordonnées de l'objet ).

Je reviens avec une solution que j'ai vu aujourd'hui même pour le LOD.

On utilise un shader qui à deux chemins potentiels de rendu, le pseudo code serait:

Code:

---

1 2 3 4 5 6 7 8 9

if ( distance < 30 ) { // Rendu complet des objets et utilisation des effets de la mort qui tue } else { // Rendu partiel ... ou au moins, utilisation d'effet simpliste }

---

Distance est la distance entre la camera et l'objet en question ( en coordonnées monde )

oui mais le problème c'est que tu dévolues la "simplification" au shader, ce qui alourdit les calculs et le rendu(sans compter les branchements qu'il faut éviter)

tandis que si tu créer différents meshes pour un même objets au préalable, tu n'as plus qu'à choisir le mesh adéquat juste avant l'envoi de la géométrie au shader

coût de l'opération pour le CPU et le GPU = zéro :ccool:

le problème par contre c'est la place que prennent toutes ces "versions" d'un même objet en RAM

Citation:

---

Envoyé par coda_blank

tandis que si tu créer différents meshes pour un même objets au préalable, tu n'as plus qu'à choisir le mesh adéquat juste avant l'envoi de la géométrie au shader

---

Ça se fait, ça, dans les jeux?

Le branchement conditionnel, dans le shader, c'est pas trop lourd. Sinon, on peut toujours utiliser deux shaders, et on utilise celui qui convient, lors de l'affichage ( Cout CPU un peu ( pour le calcul de la distance à la camera ( peut être deporté sur le GPUY ) , cout GPU, y a plus de branchement, content? )

Citation:

---

Envoyé par LittleWhite

Ça se fait, ça, dans les jeux?

Le branchement conditionnel, dans le shader, c'est pas trop lourd. Sinon, on peut toujours utiliser deux shaders, et on utilise celui qui convient, lors de l'affichage ( Cout CPU un peu ( pour le calcul de la distance à la camera ( peut être deporté sur le GPUY ) , cout GPU, y a plus de branchement, content? )

---

ben en prod en général on essaye de pas alourdir le rendu et de précalculer un maximum de trucs, après j'ai pas d'exemples précis sous la main

en fait je ne comprends pas pourquoi tu veux faire ça absolument dans le shader :aie:

comme je l'ai déjà dit , le LOD ça veut dire envoyer le moins de géométrie possible en fonction de la distance

postes des exemples, on y verra plus clair je pense :ccool:

EDIT : je viens de tomber sur cet article : http://khayyam.developpez.com/articles/3d/irrlicht/lod/

l'auteur expose les deux façons pour faire du LOD :

Citation:

---

I-1. Le LOD, c'est quoi ?
Comment gérer un objet situé très loin d'une caméra ? Si cet objet possède des milliers de facettes, doit-on toutes les dessiner ? Même si l'objet n'apparaîtra que sur une poignée de pixels ? La gestion du niveau de détail (Level Of Details) répond à cette problématique. L'idée maîtresse d'un niveau de détail est de simplifier un objet en fonction de la distance qui le sépare d'un point de vue donné.

On peut ainsi diminuer le nombre de facettes d'un maillage pour pouvoir l'afficher plus rapidement et décharger la carte graphique. Les performances de l'application 3D n'en seront que meilleures.


I-2. Différents types de LOD

I-2-A. LOD fixe
Une gestion de niveau de détail par un LOD fixe affichera un maillage ou un autre selon la distance qui le sépare de la caméra. Ainsi, il va falloir charger tous les maillages qui peuvent participer à l'objet et déterminer à chaque frame celui qu'il faudra afficher. La liste des maillages devra être accompagnée d'une liste des distances correspondant à chaque maillage. Chaque maillage sera affichable sur une zone qui lui est propre.

Néanmoins, un oeil averti pourra repérer les changements de forme lors des passages d'un maillage à un autre. Tout l'art du LOD fixe consistera à déterminer les distances de changements de maillages et les maillages eux-mêmes pour minimiser les changements visibles.


I-2-B. LOD progressif
La gestion progressive du niveau de détail peut offrir de meilleurs résultats notamment en termes de visualisation : le maillage se modifie lui-même pour retirer ou rajouter des facettes, toujours en fonction du point de vue de la caméra.

La gestion progressive du niveau de détail est plus complexe à mettre en oeuvre puisqu'il va falloir, entre autres, manipuler directement les facettes et les vertices du maillage. Le premier avantage est que les changements du maillage ne seront presque pas perceptibles pour l'utilisateur. Une telle méthode de LOD nécessitera aussi moins de mémoire puisqu'un seul maillage devra être chargé. Néanmoins, il faudra corriger le maillage à chaque changement de position de la caméra et de l'objet, ce qui peut s'avérer plus coûteux en termes de performances.

---

chaque méthode a ses inconvénients bien sûr 8-)

Citation:

---

La gestion progressive du niveau de détail est plus complexe à mettre en oeuvre puisqu'il va falloir, entre autres, manipuler directement les facettes et les vertices du maillage. Le premier avantage est que les changements du maillage ne seront presque pas perceptibles pour l'utilisateur. Une telle méthode de LOD nécessitera aussi moins de mémoire puisqu'un seul maillage devra être chargé. Néanmoins, il faudra corriger le maillage à chaque changement de position de la caméra et de l'objet, ce qui peut s'avérer plus coûteux en termes de performances.

---

Et puis je ne vois pas comment on peut faire. Prenons l'exemple d'un modèle 3D... je ne vais pas me mettre à afficher un vertex sur deux :aie:
Je viens de voir l'exemple, il parle surtout du terrain. Pour le terrain, je trouve que ce n'est pas une mauvaise idée.

Pour l'exemple, je connais une application qui utilise les deux chemins dans un shader ... mais c'est la technique fixe ... et puis ça utilise un branchement.

Citation:

---

Envoyé par LittleWhite

Et puis je ne vois pas comment on peut faire. Prenons l'exemple d'un modèle 3D... je ne vais pas me mettre à afficher un vertex sur deux :aie:
Je viens de voir l'exemple, il parle surtout du terrain. Pour le terrain, je trouve que ce n'est pas une mauvaise idée.

---

J'ai implémenté il y a quelques jours quelque chose de ce genre pour mon terrain générés par procédure. J'ai une grille carrée de points avec plusieurs couches. La couche la plus basse (0) contient les points de base tandis que les autres couches (>0) contiennent 4 points (en carré) du niveau inférieur en faisant la moyenne des hauteurs. C'est une séparation en quadtree. Ensuite j'affiche selon la distance une couche plus ou moins profonde, ce qui ajoute du détail. Loin = couche élevée = peu de points; proche = couche basse = beaucoup de points. Une petite démo de mon actuel terrain: [ame="http://www.youtube.com/watch?v=VsI3JggyhpA"]YouTube- OpenGL first terrain with LOD (Level of Detail)[/ame]

Cependant cette méthode calculée à chaud pose problème avec de grande map car je modifie aléatoirement des points pour créer des collines et autre. Peut-être serait-il préférable de favoriser le calcul des points à partir de la couche 0 chaque frame que de stocker tout ces niveaux de détails et de les modifier ? Cela s'appelle LOD ou ROAM, me semble. Ce serait comme l'a dit coda_blank du LOD progressif.

Bonjour!
Vraiment très sympa cette vidéo, tu crois que tu pourrais distribuer les sources histoire de voir comment tout cela est fait ? :)

Pas mal du tout la démo.

C'est fait exprès, lorsque vous faites le mode remplie ( non fil de fer ) que l'on voit la séparation entre les niveaux de détails ?
Sinon ... c'est niquel, mais on dirait que le LOD ce n'est pas trop possible sur un modèle quelconque en 3D. Le terrain a l'avantage qu'il est "régulier"

Bonjour,

il y longtemps je me souviens avoir planché sur un problème similaire de niveau de détail pour un mesh quelconque ( terrain ou objet )

Je me souviens mettre servis des barycentres des faces pour réduire le nombre de vertex de mes meshs, ca donnait si je me souviens bien des résultats convenables.


Je me souvenais juste qu'il y avait quelque inconvénient sur la description du mesh. Par exemple dans le cas de faces triangulaires il fallait que chacune des faces soient voisines à 3 faces maximum (au maximum une face voisine par arrêtes, si non trop compliqué à gérer). Et que comme c'était un procédé par récurrence si on voulait passer du niveau de détail 0 à 3, il était nécessaire de calculer les niveau intermédiaires ( 1 et 2). Enfin comme c'est généralement du précalculé c'est pas trop gênant si on dispose de la mémoire suffisante.


Si je retrouve ça, je vous le poste mais c'est pas garantie ça doit bien faire 3 ans.

En gros sur le principe pour un triangle cela permet de réduire 3 points en 1 point :aie:

Juste une piste comme ça.:mouarf::mouarf:

Citation:

---

Envoyé par Aladore

Bonjour!
Vraiment très sympa cette vidéo, tu crois que tu pourrais distribuer les sources histoire de voir comment tout cela est fait ? :)

---

Peut-être, il faut voir parce que le projet comporte d'autres "sous-projet" dont celui-ci pour le terrain. Je pourrais le distribuer sous licence GPLv3 par exemple. Pour rappel ce n'est qu'un essai et pour preuve, la consommation mémoire est importante et le changement du terrain à chaud prend du temps.

Citation:

---

Envoyé par LittleWhite

Pas mal du tout la démo.

C'est fait exprès, lorsque vous faites le mode remplie ( non fil de fer ) que l'on voit la séparation entre les niveaux de détails ?
Sinon ... c'est niquel, mais on dirait que le LOD ce n'est pas trop possible sur un modèle quelconque en 3D. Le terrain a l'avantage qu'il est "régulier"

---

La séparation entre les différents niveaux est un "bug" bien connu de ce type d'algorithme, c'est des "cracks" et c'est normal pour le moment car je n'ai rien prévu pour faire la transition entre deux niveaux de détails. Ce crack résulte du fait qu'un triangle de niveau n+1 est collé à deux triangles de niveau n, donc y'a une hauteur de différent et donc un crack visible. Il est surtout visible en mode normal. (cf: http://www.gamasutra.com/view/featur...ng_.php?page=2)

Citation:

---

Envoyé par Robxley

Je me souvenais juste qu'il y avait quelque inconvénient sur la description du mesh. Par exemple dans le cas de faces triangulaires il fallait que chacune des faces soient voisines à 3 faces maximum

---

Ça me fait penser au binary tree de l'algorithme ROAM. C'est sûrement l'approche que je vais utiliser pour aller plus loin avec les terrains. Si le code est sous la main, je suis intéressé :) merci.

J'ai aussi implémenté un algorithme basique de frustum culling basé sur le produit scalaire entre le vecteur de vue et le vecteur allant de la caméra aux groupes de points de niveau le plus élevé. Si le produit est négatif on affiche le groupe de points concernés sinon on cache.

Salut,

Pour le problème de la division en quadTree et des effets de bord entre chaque quad de tailles différentes comme dans la video que tu nous as présentée, pour palier à ce problème il existe des méthodes de division différente tel que la division dite en "T avec découpe en étoile" qui conserve la liaison entre les sommets entre 2 subdivisions. Enfin l'idéal reste quand même le ROAM comme dit plus haut.

Voici le lien d'un document dont je m'étais servi et qui explique bien la subdivision en T, ROAM pour un terrain :

http://www.g-truc.net/article/lod.pdf

Si ca peut aider :ccool:

Citation:

---

Envoyé par Robxley

Salut,

Pour le problème de la division en quadTree et des effets de bord entre chaque quad de tailles différentes comme dans la video que tu nous as présentée, pour palier à ce problème il existe des méthodes de division différente tel que la division dite en "T avec découpe en étoile" qui conserve la liaison entre les sommets entre 2 subdivisions. Enfin l'idéal reste quand même le ROAM comme dit plus haut.

Voici le lien d'un document dont je m'étais servi et qui explique bien la subdivision en T, ROAM pour un terrain :

http://www.g-truc.net/article/lod.pdf

Si ca peut aider :ccool:

---

Dans mon projet j'ai faut des patch de terrain qui se superposent, comme ça les raccords se bouchent tout seuls et rien ne ce vois. par contre il y a quelques triangles en plus


http://img1.imagilive.com/0609/screen_maillage.jpg