Nous avons mis en ligne une nouvelle démo : marching cubes sandbox que vous pouvez voir ici : http://www.spacegoo.com/marchingCubes
Pour les gens qui ne sont pas compatibles, nous avons réalisé une vidéo capture d’écran :

Dans cette démo, nous avons implémenté l’algorithme marching cubes dans un version modifiée. En effet, webgl ne permet pas d’accéder au geometry shader comme dans le code original. Nous avons donc du migrer la génération des vertex du côté du javascript, avant d’en faire le rendu par WebGL.

Rappelons brièvement comment fonctionne l’algorithme. Il s’agit de générer une géométrie à partir d’une fonction appelée « fonction de densité ». Celle-ci prend la forme Par exemple, si on veut générer une sphère, on prendra

On divise ensuite l’espace en cubes ou « chunks » pour récupérer la terminologie initiale. Ceux-ci sont disposés dans l’ordre idoine (celui des z-croissants) au sein du cône de vue WebGL. Chacun d’entre eux est ensuite divisé en une grille de 32*32*32 « voxels » pour lesquels on va générer les vertex. Pour décider si l’on en génére ou non, on regarde les valeurs de la fonction au huit sommets du « voxel ». Si cette valeur est positive, on attribue la valeur 1 au sommet, sinon la valeur 0. On se retrouve avec 256 cas possibles, qui se réduisent à 14 modulo le groupe de symétrie du cube. Voici ces cas (l’image est tirée du site nVidia) :

Une fois qu’on a parcouru tous les voxels, on se retrouve donc avec un tableau contenant les sommets et les faces à générer.
Il y a alors deux problèmes.

La plupart des calculs qu’on effectue aboutissent à un voxel qui ne génère pas de vertex, soit qu’il soit complètement en dehors de la surface, soit qu’il soit complètement en dedans.

Une fois qu’on a généré la géométrie, la plupart des vertex sont générés en plusieurs exemplaires, ce qui alourdit le rendu. De plus, les vertex index buffers de webgl sont limités à 65536 sommets, puisqu’ils sont encodés sur des short.

Pour résoudre ces problèmes, nous avons choisi en première approche une solution qui n’est pas optimale, mais permet d’aboutir simplement à de bons résultats.
Nous avons rêglé le premier problème en remplaçant chaque chunk par un octree dont la racine est le chunk en question et dont on subdivise les cellules seulement si elles doivent générer des vertex. Par une astuce, on peut aussi s’assurer que la fonction de densité ne sera jamais évaluée deux fois au même endroit.
Le deuxième problème est beaucoup plus complexe, et nous avons choisi de générer les vertex doubles, mais de faire une passe de calcul supplémentaire où on les enlève. Nous faisons ceci par un tri rapide simultané sur les deux buffers (vertex et index) et puis en supprimant les doublons.

Cette solution a l’avantage d’être rapide car le tri rapide ne prend que peu de temps. L’inconvénient est qu’au cours du calcul, juste avant la phase de tri, les buffers sont énorme (plus de 4 fois plus gros que nécessaire) ce qui surcharge de travail le garbage collector javacript et peut rapidement saturer la mémoire du navigateur. Il faut noter en passant que notre première implémentation de l’octree était récursive ce qui, quand ça ne faisant pas planter la call stack de javascript, explosait le garbage collector. Nous avons donc préféré l’implémenter à la main.
Nous avons donc pour projet d’optimiser cela en reprenant l’idée originale de l’algorithme, qui consiste à « marcher » dans l’octree en suivant les composantes connexes de la surface à mailler.
Mais cela fera l’objet d’un autre article plus détaillé!