Discussion :

[zenux]

Bonjour,

Je cherche un type de partitionnement adapté à une scène qui serait composé de :
- Une ville avec des maisons où l'on peut rentrer à l'intérieur et où il y a des gens qui se baladent dans les rues.
- Des champs/forêt autour de cette ville.
En d'autres mots : un scène d'intérieur et extérieur dynamique.

J'ai été voir la faq et les arbres BSP ne semblent pas être ce qu'il y a de meilleure pour les terrains et les scènes dynamiques.
Les portails, c'est bien pour la ville mais j'aime pas l'idée de se faire "chi**" à dire au moteur 3d ce qui est un mur, une fenêtre, une porte, etc.

Il reste les octree que j'ai déjà programmé mais ce n'est pas ce qu'il y a de meilleure pour les scènes dynamiques d'après ce que j'ai lu.

J'ai trouvé ce .pdf qui propose une amélioration des octree : http://www.cs.nmsu.edu/CSWS/techRpt/2003-004.pdf .
Si j'ai bien compris, il y a deux améliorations :
- Si une feuille de l'arbre contient trop d'objet, on la re-divise.
- Si un objet est à cheval sur deux nœuds, on va voir le parent de ses nœuds et on ajoute l'objet à ce parent. (Donc les objets ne se trouve plus forcément sur les feuilles de l'arbre et donc on n'a plus d'objet les mêmes dans 2 nœuds différents).

Le problème, c'est que je ne suis pas une bête de l'anglais et je ne comprend pas en quoi ces 2 améliorations ferait que l'octree serait plus adaptée a une scène dynamique, j'ai du louper quelque chose...

Existe t-il des solutions miracles ? Des techniques meilleures que les octree ? Des améliorations des octree pour les scène dynamique expliqué simplement pour moi qui ne comprend pas bien l'anglais ?

Merci d'avance...

[Ange_blond]

Salut,

De l'experience limitée que j'ai des octree, d'une part les "améliorations" que tu as trouvé sont pour moi les bases de l'octree... donc en soit n'ont rien à voir avec des améliorations... mais ça n'engage que moi.

Sinon, une chose envisageable serait peut etre d'utiliser 2 structures de partitionnement :

un octree pour les elements statiques (foret, arbres, maison, portes...) et une autre structure, plus orientée dynamique, pour les bonhommes qui se déplacent, et toutes les entités mobiles d'ailleurs...

Ce n'est qu'une idée apres tout... y'a probablement plus simple à faire.

[zenux]

C'est peut-être des améliorations de base mais le pdf du dessus, c'est la seul que j'ai trouvé qui expliquait ces 2 "améliorations". Tu en a d'autre ? (Même en anglais, j'essayerai de me débrouiller). Sur le net, je trouve par exemple plein de documents qui disent qu'il faut toujours mettre les objets aux feuilles de l'arbre mais jamais au niveau supérieur !

En effet, j'ai déjà pensé à utiliser 2 structures différentes : une pour les objets statiques et une autre pour les objets dynamiques mais qu'est ce que je doit utiliser pour les objets dynamiques ?

Dans la FAQ, je ne trouve rien :
- Arbre bsp : c'est indiqué clairement que c'est n'est pas adapté pour les objets dynamiques.
- Les portails ça peut être bien pour les gens qui se trouvent à l'intérieur des maison mais si les gens se trouvent dans la rue, ça n'a plus beaucoup d'effet.
- Octree : comme on viens de le dire, ce n'est pas adapté.

[Ange_blond]

Les avantages des structures de partitionnement, c'est justement que si un systeme est lourd, le partionnement sera long, mais fait une seule fois.

Apres, il existe surement des algo qui permettent non pas de recalculer le partitionnement a chaque frame, mais plutot de le mettre à jour en ne modifiant que ce qu'il faut... Mais c'est vrai que pour les scene dynamiques, il n'existe pas grand chose à ma connaissance

Sinon pour ce qui est de mettre des objet dans les "branches" et non les feuilles, c'est une question d'adapter son arbre aux données qu'on traite... il y a souvent des discutions à ce sujet (par ici je crois d'ailleurs), mais a ma connaissance pas de standards... donc fait au mieux pour ton probleme à toi.

Je n'ai qu'une faible connaissances des ses structures, je n'ai utilisé qu'un simple quadtree y'a des années... donc google ça... tu trouvera surement des choses... sauf si qqun par ici a des idées nouvelles à apporter

[zenux]

Ok merci. Je vais laisser le sujet encore ouvert quelques jours au cas où quelqu'un aurait des infos à propos du partitionnement pour une scène dynamique ou des améliorations pour les octree.

Je vais faire des recherches sur ce forum pour voir si je trouve quelque chose d'intéressant

[zenux]

Je re-post un message, parce que je viens de penser à une chose plutôt très pourri pour cette optimisation :

"Si un objet est à cheval sur deux nœuds, on va voir le parent de ses 2 nœuds et on ajoute l'objet à ce parent. (Donc les objets ne se trouve plus forcément sur les feuilles de l'arbre et donc on n'a plus d'objet les mêmes dans 2 nœuds différents)"
==> c'est tout mignon dit comme ça mais selon moi il y a en gros problème qui ferais que cette optimisation n'en est plus du tout une :

Si un objet se trouve a cheval entre deux nœud au milieu de mon octree, cet objet va obligatoirement se retrouver dans le nœud mère et donc il sera affiché tout le temps. Je ne comprend pas....

[Ange_blond]

Oui ça revient à ça en effet...

S'il est en plein centre, ... alors y'a pas 50 choix possibles.

Tu peux choisir de le mettre dans un fils au hasard , mais ça peut donner des résultats différents de ce que tu attend...

[zenux]

Hum, moi je dit rien de tel qu'un bon vieux octree classique, lol.
Je vais donc re-programmer un octree classique avec aussi des portails et je pense que ça fera l'affaire

[Camel LowFilter]

en fait là tu cherche un système générique qui serait capable de tout faire, intérieurs, extérieurs, statique, dynamique...

en 2d c'est facile à faire, le problème c'est qu'en 3d si on applique les mêmes principes on défonce ram et cpu, c'est pourquoi on n'utilise pas de système générique en 3d, mais des optimisations complexes (arbres, modules) qui excluent la généricite.
Si tu regardes l'unreal engine par exemple, rien n'est générique, il combine une série de structures non génériques: c'est une indigeste bouillie qui mélange bsp, secteurs, zones, static meshes, portails, antiportails, et les structures d'ageia par dessus.. et tu n'as pas les moyens d'epic software.

Je te conseille donc de simplifier ton développent au maximum.

Déjà laisse tomber la mixité intérieurs / extérieurs, c'est trop long à développer, les logiques sont trop différentes.
Par exemple pour le calcul d'occlusion, en intérieur on se base surtout sur les portails, en extérieur on utilise surtout les antiportails - les deux sont combinables mais ça double le travail.
En intérieur la principale difficulté porte surtout sur la cohérence de l'architecture (précision des lightmaps, découpage propre du bsp ou des secteurs, etc), en extérieur le principal problème est surtout de gérer les arrières plans (réduction polygonale, simplification des textures, etc).

Laisser tomber les intérieurs pour commencer, essaye déjà de bien coder un extérieur.

Tu n'es pas obligé d'utiliser un octree. Un grille en 3d (soit un octree, qu'on choisit par dépit car la grille uniforme péterait la ram) est utile pour une structure qui raisonne vraiment en 3d (des ponts, des tunnels, des étages de parking souterrain ou aérien...)

Mais si la logique de ton jeu est 2d (une voiture sur un sol plat ou une heightmap) tu peut tout faire avec des static meshes rangés dans une grille uniforme en 2d, et tu retrouveras toute la souplesse du gameplay à 2 dimensions. Cette méthode est très utilisée pour les développements à petit budget.

[zenux]

Merci bien pour l'info, c'est plus ou moins ce que je comptait faire : commencer par l'extérieur.

[Camel LowFilter]

Ensuite il est possible de développer un rendu d'intérieurs et le combiner avec mais ça commence à faire beaucoup de travail.

Bon courage

[smashy]

Petit info concernant les octrees.

Effectivement, un objet a cheval sur deux noeuds va etre deplace sur le noeud mere ...

Si l objet est vraiment au centre de la scene , il va se retrouver sur un noeud RACINE qui est toujours afficher

Il existe un structure "LooseOctree" (voir Game Developpement Series ) qui y remedie.

L'idee c'est que les noeuds se chevauchent ...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
  +-----+
       +-----+
    A   B   C

On voit donc apparaitre 3 cas , suivant qu un objet est dans un noeud , dans l'autre noeud ou les deux
conclusion : tu n'est pas obliges de remonter les objets au niveau superieur et ca c est chouette.

[zenux]

Oki merci, pour l'instant, j'ai tout mis dans les feuilles de l'arbre avec un petit flag dans la classe des objets 3d afin de savoir si il se trouve dans plusieurs nœuds ou pas et ça fonctionne très bien.

Je regarderai au looseOctre plus tard parce que je n'ai pas bien compris le principe surtout dans le cas où j'ai des grands objets qui traversent plusieurs nœuds.

[smashy]

En fait, le principe est simple :

un Octree est un arbre tel que un noeud fait la moitie de la taille de don noeud pere.

En partant d'un noeud racine, on peut attribuer un niveau aux noeud (0 pour la racine , 1 pour ses fils ...)

Etant donne que les noeuds se chevauchent sur une certaines distances D (en fonction du niveau D = alpha / (niveau^2) ). On peut dire que si un objet a une taille inferieur a D. Il peut etre contenu entierement dans un noeud de ce niveau

[zenux]

Sans trop avoir réfléchi, je suppose que D ne peut pas être plus grand que la longueur d'un octree feuille. Donc je suis limité dans la taille de mes objets...je regarderai à tout ça quand j'aurais le temps pour voir si c'est plus intéressant qu'un octree classique et un petit flag.

[epsilon68]

moi je stokais mes triangles du model dans un octree.
effectivement le triangle devait se situer dans le noeud parent s'il etait trop grand pour etre rangé dans un des fils.

ce n'est absolument pas genant ....

[zenux]

moi je stokais mes triangles du model dans un octree.
effectivement le triangle devait se situer dans le noeud parent s'il etait trop grand pour etre rangé dans un des fils.

ce n'est absolument pas genant ....

Laisse moi deviner :
- Soit tu as des modèles à très peu de polygone
- Soit tu as des modèles à beaucoup de polygone mais ils sont statique
Autrement je vois mal comment avoir quelque chose de performant en faisant ça par triangle.

Et toujours le même problème qu'avant : si tu as un triangle qui se trouve au milieu de ta scène, il sera dans le noeud parent et donc il sera tous le temps affiché...bof

[unmanos]

Peut etre tu devrais regarder du cote des BVT ou BVH pour Dynamic Voume Tree/Hierarchy ou DBVT/DBVH pour son equivalent dynamique. C'est ce qu'utilise des moteurs de physique commerciaux de physique comme Havok pour gerer leur collisions.

L'avantage est que c'est generique, pas de secteurs de taille fixe a l'avance, c'est dynamique (ton monde peut changer de taille). De par sa structure en arbre, ca peut gerer des objets tres petits comme des objets tres grand sans difference. Ca peut aussi bien servir pour faire un raycast sur un mesh de plusieurs dizaines de milliers de polygones comme pour recuperer la liste des objets a partir d'une boite ou d'un fustrum.

C'est ce que nous utilisons depuis quelques annees et franchement c'est tres rapide, les performances sont un peu moins bonne qu'un octree, mais c'est tellement plus flexible... et surtout DYNAMIQUE!

[zenux]

Ok merci, je regarderai bientôt à ses dbvh

[Bakura]

J'avais trouvé très récemment un papier très intéressant qui parlait d'une méthode pour utiliser de manière très efficace l'occlusion culling en hardware. Ça a l'air d'être très efficace d'après la démo que j'ai pu testé :

http://www.cg.tuwien.ac.at/research/...g04-chcull.pdf

Puis amélioré dans ce papier :

http://www.cg.cs.uni-bonn.de/docs/pu...al-optimal.pdf

Concernant l'octree, voici un papier qui décrit un octree totalement dynamique. J'avais testé leur code et ma foi ça marchait vraiment bien, l'octree était totalement dynamique et même avec des centaines d'objets à mettre à jour par frame ça restait très rapide : http://www.cs.nmsu.edu/~joshagam/Sol...teup-print.pdf (EDIT : c'est les détails d'implémentation du papier que tu cites dans ton premier post)


Sinon, j'ai une petite question sur le partitionnement des scènes. En fait, jusqu'ici j'ai toujours utiliser l'octree en y stockant l'AABB d'un objet. Ainsi, si la moitié de l'objet est visible, ben tout l'objet va être rendu, alors que la moitié aurait pu être écartée. Généralement, est-ce que on utilise cette solution, ou alors chaque modèle 3D est subdivisé en plusieurs ? (est-ce le modèle est subdivisé au lancement de l'application ? Ou est-il fait de plusieurs "sous-meshs" par l'artiste ?)