dimanche 1 avril 2012

18# Moteur de terrain en voxels



J'ai commencé il y a peu à travailler sur un moteur de terrain en voxels, dans le but de faire un jeu dont la nature n'est pas encore tout à fait définie (je programme toujours en C++, avec OpenGl et SFML). Pour l'instant vous pouvez vous régaler de ces images, je posterai probablement une vidéo plus tard.


Les voxels, depuis l'épidémie de minecraft, vous en avez probablement déja entendu parler: c'est tout bêtement une entitée basique contenant quelques informations (Position, couleur, texture) et graphiquement représentée par un cube. Un voxel dans un espace en trois dimension est comparable à un tile ou un pixel dans un espace en deux dimensions. Toutefois je ne compte pas faire une énième pâle copie de minecraft, et j'ai choisi le voxel car c'est simplement un moyen pratique de travailler en 3D, et que son rendu donne un certain côté rétro que j'aime beaucoup.
Au niveau du fonctionnement, dans le principe, je stocke mes voxels dans un tableau tridimensionnel. Visualisez un tableau qui comporte des cases dans les trois dimensions:

Chaque case de ce tableau contient des informations de couleurs uniquement (je ne compte pas utiliser de texture). Ici nous avons un tableau de 3*3*3 voxels. Les coordonées des informations dans le tableau constituent par la même occasion les  coordonnées du voxel correspondant. On appelle un voxel de la façon suivante pour accéder ou modifier ses propriétés: tableau3D[i][j][k], où i j et k sont des indices permettant de parcourir le tableau. La structure du prorgamme est plutôt simple à concevoir, à partir de là il suffit, à chaque raffraichissement d'image d'afficher graphiquement un cube aux coordonnées dites du tableau et avec les propriétés indiquées.
Seulement les choses se compliquent vite: avec cette méthode, si je veux afficher ce cube de 3*3*3 voxels, tout va bien, mais en pratique il me faudrait afficher plusieurs centaines de milliers de voxels à chaque frame. Or afficher tous ces voxels sans distinction prend beaucoup trop de ressources, même pour un ordinateur actuel normalement constitué, et au dela de plus ou moins 20*20*20 voxels, soit 8 000 voxels et donc 8 000*6 = 48 000 faces, le framerate chute à moins de 5 FPS, ce qui devient très vite injouable.
Il a donc fallu créer des algorithmes de tri, entre autres le plus évident: ne pas considérer les voxels déja entourés par six autres voxels (donc ceux dont toutes les faces sont cachées), et chez les autres voxels existants, ne pas afficher les faces en contact avec une autre. Avec quelques autres modifications liées au dessin directement avec OpenGl, je parviens maintenant à afficher des zones de 100*100*100 voxels avec un framerate d'environ 15 FPS, ce qui est toujours très insuffisant.
Le terrain est destructible, et grâce à quelques algorithmes je peux facilement créer des formes géométriques simples (sphères, parallélépipèdes), et je planche sur un moyen de créer d'autres formes, comme des polygones réguliers (triangles, pentagones, etc ...) extrudés en hauteur. L'optimisation des performances n'est pas finie non plus et il faut que je me renseigne sur d'autres moyens d'affichage en OpenGl, comme les VBO, mais je n'en sais pas plus.
Je donnerai des nouvelles sur l'avancement de temps en temps.
Si vous avez des suggestions par rapport à ce projet je veux bien les entendre, et si quelqu'un s'y connait en OpenGl j'aimerai beaucoup qu'il m'explique quelques trucs :] !

8 commentaires:

  1. Moi j'ai un rubick's cube chez moi mai

    RépondreSupprimer
  2. Même que des fois vu un et c'était

    RépondreSupprimer
  3. Pour le moment tu utilise les display list ? peut-être tu pourrais créer une sorte de Z-buffer pour les cubes entiers (en modifiant le sens de parcourt de ton tableau selon l'orientation de la camera pour pas commencer à afficher le cube le plus éloigné)

    RépondreSupprimer
  4. Justement, pour l'instant je n'utilise pas de display list. Mais c'est prévu !
    Pour le moment je dois modifier mon tableau tridimensionnel pour "l'aplatir" en une seule dimension et le rendre plus rapide à parcourir, et partitionner le terrain en "chunks", des sortes de blocs virtuels englobant des groupes réguliers de voxels. Puis l'idée est de faire en sorte que chaque chunk possède une display list contenant les faces des voxels à afficher, et que le terrain possède une display list appellant les display list des chunks concernés (comme ça on apelle pas les chunks vides, par exemple). Depuis que j'ai écrit ce post j'ai repensé pas mal de choses sur la structure du programme et j'ai pas encore implémenté tout ça mais il y a de fortes chances pour que ça augmente grandement les performances. Par contre, pour le moment je compte faire des appels au dessin direct dans les display list (avec glBegin et glEnd et des dizaines d'appels à glVertex3f, parce que j'ai pas encore compris comment me servir des vertex-array ou des VBO...
    Je pensais m'attaquer au culling par la suite et j'avais lu qu'afficher ma géométrie dans le sens que tu me proposes permettait de faire de l'occlusion culling, mais j'avoue que je ne saurais pas comment m'y prendre efficacement ...

    Mais tu m'as l'air de t'y connaître dans ce domaine dis moi ? :D

    RépondreSupprimer
  5. En fait, je savais que tu modélisais en 3D, mais c'est le même jargon et tu te préoccupes aussi de ce genre de question ?

    RépondreSupprimer
  6. oui alors pour ce qui est de mes connaissances disons que j'essaye de comprendre opengl depuis qlq mois et puis je grappille des infos à droite à gauche autour du sujet. Cependant pour tous ce qui est programmation je pense les choses de manière très théorique ^^.

    Ensuite pour aplatir ton tableau, tu peux peut-être représenter chaque élévation par une liste chainé. De cette manière si le cube le plus haut d'une colonne se situe à 2 et que le point le plus haut de ton chunk est a 255 tu économise le parcourt de 252 "case" vide. (purement théorique t'as vu ^^)

    Ensuite si ton terrain sera amené à évoluer au cour de la partie, il me semble que l'utilisation de display-list est à bannir. D'après ce que j'ai compris, une display-list est en qlq sorte une compilation de l'affichage de ta géométrie. Dc ça t'obligerai à "recompiler ton chunk à chaque modification.
    A mon avis, le mieux est effectivement de passer par l'utilisation des VBO mais alors là je dois t'avouer que je n'ai absolument pas compris comment m'en servir. Si il y a des extension d'opengl à ajouter ou seulement des include à faire... J'en sais rien ^^

    voilà en tout cas je serais ravi de t'aider comme je le peux ;).

    RépondreSupprimer
    Réponses
    1. cool que cool !

      Dans mon cas, l'interêt d'une display list ne perd pas son sens car ça permet un rendu très rapide, et pour le problème de staticité il est contournable: chaque chunk ayant sa propre display list, si je modifie un voxel dans un chunk il faudra que je recompile la display list du susdit chunk avec les nouvelles propriétés (ce qui prend relativement du temps). Mais les chunks sont relativement petits (plus ou moins 10*10*10 cubes) alors la recompilation prendra d'autant moins de temps, et comme il y aura plus souvent des rendus à faire que des recompilations, c'est une approche justifiée :D

      Supprimer
  7. Utilisez un vbo est des indices si besoin. le but étant d'utiliser le moins de draw call possible. C'est là qu'est le bottleneck de votre programme.

    RépondreSupprimer