Bonjour tout le monde,
Après de longs séjours sur google, gamasutra, gamedev... il me reste encore quelques questions sur les heightmaps :
1 : quel algorithme de gestion/rendu optimisé est le plus couramment utilisé dans les jeux? (MMORPG notament) J´ai étudié différents algorithmes dont celui de la subdivision en T qui a l´air pas mal, qu´en est-il?
2 : En moyenne, quelle taille font les heightmaps dans les jeux?

Les autres sont de moindre importance...

merci d´avance pour vos réponses

1. pour qqch d´efficace, geo-mip-morphing ; ca s´adapte bien a la subdivision en T au passage.
Pour aller au dela, tu peux faire des NURBS ; c´est couteux en calculs, mais tu peux reussir a avoir un LOD continu, au lieux de LODs discrets.

2. generalement les landscapes sont streamé a la demande, il n´y donc pas vraiment de taille moyenne ou maximale. Tout depend de la qualite d´un "patch" d´aire de jeu que tu veux avoir.
Sachant qu´en general, on va faire du blendmapping 3 voire 4, des normal maps, des specular maps, et details maps, etc., la taille des ressources a streamer augmente tres vite ! Sans parler des limitiations materielles des shaders : il faut bien choisir ses ressources selon ce qu´on veut rendre.. La taille des texture depend aussi bcp de ca (i.e. si tu qu´un blend mapping 2 + une normal map, c´est quasiment rien, donc tu peux facilement prendre des textures de tres haute resolution 4096x4096. A l´inverse si tu veux un truc bcp plus complexe, si tu veux garder des utilisation des bus raisonnables pour transferer les ressources, il faudra reduire la taille des textures, et faire un streaming plus fin)

3. point que je rajoute ; si tu veux un resultat potable, ne fait PAS un mapping planaire de tes textures diffuses/normal/etc sur le relief donne par la height map. Sinon tu vas avoir un mechant effet de tearing la ou les pentes sont importantes. Soit tu prends des meshs authoree en UVW directement par les artistes, soit tu recalcules manuellement tes UV en pre-processing (ce qui veut dire calculer la longueur de tranches de landscape, interpoler non lineairement pour remapper en gardant la meme densite de texture ; on se rapproche des techniques liees au "lapped textures")

merci beaucoup pour la réponse, c´est exactement ce qu´il me manquait, au passage si tu avais des documents a me conseiller, ca m´interresse.

Pour résumer donc :
- Subdivisions en T + geo-mip-mapping
- blend mapping 3 ou 4 + normal map avec des textures de petite résolution pour la plupart (cel-shading )
- dans le pre-process : calcul des UV

ai-je oublié quelque chose?

Et sinon, d´après toi que faut-il choisir entre
- faire des liste d´affichage de chaque "patch"
- appliquer le frustrum culing
- les 2 avec de plus petits patch

je pense que le frustrum culling est fondamental.
Tu peux aussi utiliser ne pas afficher les polygones qui ne sont pas orientés vers toi
(exemple : si devant toi tu as une colline, les polygones derriere la colline, tu ne les verras pas)
Ainsi bien sur que le clipping.

ouaip !

un quadtree / octree pour clipper rapidement, des patchs elementaires de petite taille, des VB/IB dynamiques, si t´es motive, de l´occlusion, etc.

cherche geopmipmapping et geopmipmorphing sur google y´a pas mal de doc (le morphing n´etant qu´une variante progressive a coup de vertex shader).
Pour le cell shadind, c´est plus une calcul d´eclairage qu´un pb de resources, a la base.

(ce que je voulais pointer par le cel shading c´est juste que les textures seront de moindre resolution)

Merci beaucoup pour ces reponses... je m´y attele de suite
(au passage si vous aviez des mails sur lesquels je pourrais eventuellement poser des questions => rodounet [at] gmail [dot] com)

Wowww...

J´ai essaiyer de lire mais, j´y comprend rien

Anywais, bientôt un livre C plus un autre c++
et les cours du zero

Noflama : rassure toi, il y a un an, j´aurais moi aussi été incapable de comprendre cette conversation, mais entre temps, j´ai eu l´occasion de créer un jeu vidéo de A à Z (pour l´école) et je me suis beaucoup documenté dans le domaine. (Jeu de course en 3D)

J´ai adoré faire ce jeu (qui était loin d´être parfait mais suffisant pour se faire une idée de comment ca se fait) donc maintenant je travaille sur un gros morceau avec quelques potes...

Bon voila, je me suis documenté et j´ai étudié plusieurs algos (merci LGV)...
mais voila, je ne vois pas l´intérêt du quadtree face à une représentation statique sur certains points, je m´explique :
(pour la représentation statique, je considère une matrice qui contiendrait des pointeurs vers les patchs.)
- défauts : les patchs sont tous de taille identique, LOD plus compliqué (quoique)
- qualités : accès immédiat à chaque patch, tests pour le frustum culling facilités (j´ai un peu étudié la question, et c´est ce qu´il me semble)

C´est surtout sur ce dernier point que cela me gène, le frustum culling... Si vous pouviez m´éclairer sur une méthode optimisée de l´appliquer à un quadtree, parceque c´est ca qui m´a fait envisager la représentation statique.

- il te faut des patchs de taille identique, sinon bonjour le merdi... le borde.. bref ce sera loin d´etre evident, pour rien d´interessant en contrepartie
- le quadtree n´est qu´une surcouche a ta grille de patch qui constituent le landscape dans sa globalite ; il n´est interessant QUE en combinaison avec le frustum culling, le but etant d´optimiser ce dernier.

le principe est le suivant : tu decoupes ton landscape selon un quadtree, et tu traverses la hierarchie a coup de frustum culling : si toute une cellule n´est pas visible, pas la peine d´inspecter ses sous cellules.
Autrement, une GRAAAANDE cellule contenant pleeeein de patchs, qui serait tres loin derriere la camera, tu l´elimines completement avec UN SEUL test d´appartenance au frustum.
Si une cellule est partiellement visible (au bord du frustum, ou avec des grandes cellules), tu raffines en descendant dans ses sous cellules.
si une cellule est completement visible, tu affiches tous les patchs de toute sa hierachie, sans te poser de questions

en qq tests seulement, tu vires BCP de patchs, et le culline se raffine aux abords du frustum, jusqu´a le definition la plus fine, definie par la taille de tes patchs.

une fois que t´as fait la liste de tes patchs, te reste plus qu´a crees des VB/IB pour collecter les vertices, et rendre tout le lanscape en un nombre minimal de primitif (idealement, chaque patch aura des caches "baked geometry", d´ou tu peux memcpy a la demande : avec ca la collection de la geometrie est extrement rapide, et le rendu aussi). Pour le morphing si tu veux blender entre les LODs de patchs, fait le a coup de vertex shader , pour pas toucher a la veritable geometrie du terrain.

qq fautes.. j´en corrige une qui fait perdre son sens a la phrase :

.. en un nombre minimal de PRIMITIVES (et non pas primitifs..)

Merci de m´avoir éclairé la dessus (le fait que l Quadtree ne servait qu´au frustum culling) et pour ce qui est de son principe je l´avais saisi...

Ce que je cherchais c´était l´algo de test de visibilité le plus efficace possible (j´ai l´impression que le truc de diviser le frustum en 6 faces et de faire des tests à tout va n´est pas efficace).
J´ai cherché par moi-même :
- j´arrive très bien à déterminer si un patch est partiellement visible
- par contre c´est plus dur pour déterminer si les autres sont à l´intérieur ou à l´exterieur

pour ce qui est de l´affichage final, j´avais penser générer des listes d´affichage au chargement de la map (un pour chaque patch en feuille du quadtree)
Je n´ai jamais touché aux shaders, aurais-tu un lien ou un document à me conseiller?

merci d´avance

(au temps pour moi, "baked geometry" serait équivalent aux listes d´affichage si je ne me trompe pas)

fais ton clipping en 2 fois :
- cone clipping + distance check
- si ca passe, alors la tu sors le frustum clipping, plus couteux mais plus precis

sur un quadtree adapte, ca fait trees peu de calculs, pour tout le landscape.

(si tu fais ton quadtree assez generique, tu peux le reutiliser facilement pour des objets.. avec un quadtree contraint des objets statiques, et un "loose" quadtree pour des objets dynamiques)

pour l´affichage, l´essentiel c´est de batcher un max les vertices ; idealement, on doit pouvoir rendre TOUT le landscape en UNE seule primitive (bon ok.. qq primitives, si on a bcp de polys et qu´on limite pour une raison qqcq a des indices 16 bits, par ex.)
l´idee est de ne surtout pas avoir "1 patch > 1 primitive a rendre", mais bien de collecter tous les vertices dans des grands buffer, pour envoyer tout ca en bloc a la carte.
Apres, que tu fasses comme tu veux, ca me derange pas, c´est juste le mechanisme sous jacent qui doit rester le meme : batcher, batcher, BATCHER, BAAAAATCHER !!
par "baked geometry", j´entends au sens large, des buffers statiques de vertices pret a etre collectes et envoyes au GPU (selon le nombre de polys, on peut aussi carreement avec un VB static dans le GPU, et re-generer uniquement un IB pour rendre les morceaux qu´on veut ; ca peut etre contre performant si on s´y prendre mal cela dit)

fracart, mon quadtree en action, on voit trés bien comment est subdivisé le terrain:
http://shadowtzu.free.fr/quadtree.jpg
http://shadowtzu.free.fr/quadtree2.jpg

j´utilise la technique que décrit LGV:
"...on peut aussi carreement avec un VB static dans le GPU, et re-generer uniquement un IB pour rendre les morceaux qu´on veut ; ca peut etre contre performant si on s´y prendre mal cela dit)"

ShadowTzu > to illustration est tres parlante pour le Quadtree

a noter qu´a partir du moment ou a introduit des deniveles importants, il est interessant de "deconnecter" les cellules du quadtree, via un offset vertical (qu´on peut par ex. calculer optimalement a coup de centroide) et ainsi miniser les bounding sphere.
dans le meme ordre d´idee, tu peux precalculer des valuations d´une fonction permettant au runtime d´avoir des BS dynamiques en fonction de la direction de dispersion maximale des projections des vertices d´un patch (> vecteurs propres, decomposition LU + Jacobi). Mais la ca va deja loin.. commence par avoir un truc qui marche, ca c´est une etape encore lointaine.
Garde cependand une chose a l´esprit, la subdivision de tes patchs DOIT dependre de criteres evolues tels que l´aire de la surface projetee en espace ecran (on se rapproche des techniques d´evaluation des mipmaps) ; la distance a la camera ne suffit pas a donner qqch de convenable si tu as de forts deniveles.

http://www.flipcode.com/articles/article_geomipmaps.pdf

ce document detaille un peu un exemple de fonction de valuation ; ca peut donner des idees, et des pistes de reflexion.

merci pour vos réponses, tout d´abord c´est sur ce document que je m´étais le plus attardé et effectivement il détaille bien tout ce qui se passe derrière.

Par contre, je n´ai pas saisi ce passage :
"Pour l´affichage, l´essentiel c´est de batcher un max les vertices ; idealement, on doit pouvoir rendre TOUT le landscape en UNE seule primitive (bon ok.. qq primitives, si on a bcp de polys et qu´on limite pour une raison qqcq a des indices 16 bits, par ex.)
l´idee est de ne surtout pas avoir "1 patch > 1 primitive a rendre", mais bien de collecter tous les vertices dans des grands buffer, pour envoyer tout ca en bloc a la carte. "

si tu pouvais expliquer plus en détail ca serait sympa

(au passage, si qqun a de la doc sur les shaders ca m´interresse, je n´ai pas peur de l´anglais ;) )

encore merci tout le monde