Voxelab on the market !

Bonjour à tous !

Grande journée pour moi puisque mon travail Voxelab, qui m’a permis de faire ces guides, vient d’arriver sur l’asset store d’Unity !

Ce projet contient tout ce qui a été couvert dans ce blog, les trois algorithmes de maillage, la gestion de chunk pour créer des mondes infinis, les shaders triplanairs et plus encore !

Si vous avez quelques roubles qui traitent ou si vous voulez soutenir ce projet vous pouvez jeter un œil sur le forum ou directement sur le magasin.

J’ai créé trois paquets différents :

Complete Edition, avec tout mon travail.

Meshing Scripts, avec les trois principales méthodes de maillage.

Triplanar Shaders,  pour texturer facilement les grands terrains et meshes procédurales.

Vous pouvez suivre le projet sur le forum d’Unity. Vous voulez en savoir plus ? Vous pouvez me contacter à contact@voxelab.fr.

Triplanar Shader

Avant d’entrer dans le sujet sachez que vous allez avoir besoin de savoir coder des shaders sous Unity. Même si ce n’est pas le cas, vous devriez pouvoir comprendre les principes de base.

Si vous vous êtes essayés au maillage procédural vous avez sans doute rencontré un problème : comment appliquer les textures ?

En répétant les textures et en utilisant la position absolue des vertices, on peut automatiquement créer les UVs nécessaires :

Textrepetition

Ainsi, si vous voulez des UVs sur une texture de taille 10×10, pour le vecteur (105x, 5y), vous aurez une UV de (0,5x, 0,5y) sur la dixième texture sur l’axe ‘x’. Mais en appliquant cette technique sur trois dimensions, des étirements de la texture apparaissent :

Streching

D’où vient le problème ? Pour représenter la direction dans laquelle est positionné un triangle, chaque vertex qui le compose a une normale qui lui est associée. Dans certaines méthodes de maillage on peut utiliser des vecteurs simples comme Vector3.Left ou on peut utiliser la fonction d’Unity mesh.recalculatenormals. Mais ce n’est pas toujours suffisant. Les textures sont alors étalées selon un seul axe, ce qui produit l’étirement que l’on voit.

La première étape est donc de calculer des normales plus proche de l’isosurface que du mesh créé. Les fonctions de densité peuvent être comprises comme des champs vectoriels. Ceci permet de calculer, en un point, une normale grâce au gradient.

Maintenant nous allons pouvoir nous pencher sur le coeur de l’article : les shaders triplanaires.
Il s’agit d’échantillonner une ou des textures et de les appliquer sur les trois axes x, y et z en fonction de la normale de la surface.

Nous allons donc devoir prendre en paramètre jusqu’à trois textures différentes. Elles seront réparties sur les axes +Y , -Y et X/Z ce qui est utile pour appliquer sur un terrain. Nous pouvons aussi y associer une valeur flottante pour pouvoir influer manuellement sur le mélange des textures :

Dans la fonction vert() on traite ces données pour pouvoir les utiliser ensuite. Il s’agit de calculer la proportion des normales pour un point précis.

Notez qu’ici on utilise les normales dans la base orthogonale du « monde », mais on peut aussi utiliser les normales de la base « local » de l’objet.

Maintenant dans la fonction surf(). On calcule le degré d’échantillonnage des textures :

Puis nos UVs via la position absolue du point :

Enfin on échantillonne nos textures qu’on interpole en fonction des normales et des étapes calculées plus haut. Il ne reste plus qu’à appliquer la couleur à notre Albedo.

Voilà un shader triplanaire simple avec pour résultat :

Triplanar

Je mets le code complet ici si vous voulez un exemple complet :

Cette méthode peut être combinée avec d’autres types de shader. Comme le bump mapping, specular, parallax fragment shader et bien d’autres. Si vous voulez quelques exemples voici une démonstration de ce que j’ai fait pour mon projet.

Dual Contouring

Dans l’article précédent, on parlait des algorithmes de Marching Cubes (MC) et Extended Marching Cubes (EMC). Ces techniques sont désignées sous le nom de Primal.

Une autre approche est appelée Dual. C’est le cas des Surfaces Nets ou du Dual Contouring (DC) que nous allons étudier ici.

Voici une représentation du fonctionnement de ces algorithmes :

dc-grid

Les Marching Cubes ont un gros défaut, celui de couper tous les détails à l’intérieur d’un cube. L’Extended Marching Cube essaie de corriger ce problème. En associant plus de données aux points, aussi appelées Hermite Data, dans ce cas la normale à l’intersection est souvent calculée par la méthode du gradient. Notez comment les vertices sont placées sur les edges et les polygones dans les cubes.

Dual Contouring prend une autre approche en produisant des vertices à l’intérieur des cubes et des polygones sur les edges. Pour chaque cube qui a un changement de signe, un vertex est placé au centroïde des intersections sur les edges. Puis pour chacun des quatre cubes de chaque edges traversés, un polygone est créé.

Pour chaque vertices généré par DC, MC créer un polygone, et pour chaque polygone, MC créer un vertex. Le contour des polygones sont donc dual d’une méthode à l’autre.

EMC et DC utilisent les données Hermites pour mieux représenter des formes aiguisées tel que des bords et des coins. Comme vous pouvez le voir sur cet exemple :

emc-box
MC / EMC / DC

EMC introduit l’utilisation de la fonction d’erreur quadratique (QEF) pour localiser ces formes. Mais EMC à deux inconvénients majeurs. D’abord elle a besoin de calculer l’angle entre les normales des intersections pour détecter si un coin existe. Ensuite elle crée de façon approximative les polygones entre les intersections des edges et le point trouvé via la QEF. Ce qui est bien pour créer des coins mais pas des edges droits.

Comme DC positionne ses vertices dans les cubes, elle autorise plus de souplesse.

En d’autres mots à chaque point d’intersection sur les bords du cubes, la normale est connue. Avec un point et une normale on peut calculer l’équation d’un plan. La QEF est la somme des carrés des distances entre le centre du cube et les plans qui le traversent.

Le but est ensuite de choisir un point dans le cube qui minimise la QEF. La méthode recommandée de base est la procédure de Grahm-Schmidt. Mais elle peut créer des résultats hors du cube. Une autre option est de créer une grille de point dans le cube et de choisir celui avec la QEF la plus basse. Ce qui augmente le coût de calcul.

Nous avons fait le tour des concepts de base du Dual Contouring. Comme cette technique peut être assez compliquée à comprendre, en particulier pour la QEF, je vous invite fortement à lire ce papier du SIGGRAPH. Il contient en plus de nombreuses explications et améliorations notamment avec un octree.

Fear the Walking Cubes

Pour l’instant nous avons suivi une règle simple : si la densité de note voxel est négative, on dessine un cube. Mais n’en déplaise à nos amis fans de Minecraft, le monde n’est pas fait de cubes.

La première technique inventée pour faire des mesh plus fidèle est celle des Marching Cubes.

Contrairement à ce qu’indique le titre, il y aucune raison d’avoir peur de ces cubes. C’est probablement la méthode la plus implémentée. Pourquoi ? Parce qu’elle est simple à faire, rapide avec presque aucun calcul et une des plus anciennes (1987). Voici quelques implémentations de cet algorithme en C, C++ ou C# et… Java, JS et Python. Voyons comment ça fonctionne.

Avec la méthode des Boxel, on forme des cubes pour représenter la surface. L’étape logique pour améliorer la finesse du mesh est de subdiviser la surface. Donc de couper le bord des cubes. Voici un champ de voxels, les rouges ont une densité négative, les bleus positive :

connectedobj

Voyons de plus près, au niveau d’un cube dont les coins sont des voxels :

cube1

Si v0 est positif et v1 négatif on sait que edge0 est traversé par notre surface. La version des Marching Cubes de base interpole la traversé des edges au milieu des deux voxels, soit 0,5 entre v0 et v1.

En testant tous les coins on peut déterminer quels edges sont coupés. Et d’une façon simplifiée comment le cube est traversé. Par exemples si v0 est le seul voxel avec une densité positive :

One Tri

Chaque coin est soit dans la surface ou hors de la surface et il y a huit coins part cubes. Il y a donc 2^8 soit 256 façons dont les edges peuvent être coupés par la surface. On peut utiliser une table statique pour stocker ces possibilités (edgeTable). Ces 256 valeurs de configuration des polygones sont pré-calculées par réflexion et symétrie à partie de 15 cas possibles :

350px-MarchingCubes.svg

Il y a jusqu’à 5 triangles par cube, et ces triangles sont eux aussi stockés dans une seconde table statique (triTable).

L’algorithme des Marching Cubes consiste donc à parcourir notre espace de cubes. Tester la densité des coins. Déterminer quels edges traversent la surface. Récupérer les positions des vertices sur les edges coupés. Et créer les triangles.

La difficulté de cette méthode est de créer les deux tables edgeTable et triTable. Heureusement, cette technique est très répandue, et ces tables sont disponibles.

Pour pousser le sujet un peu plus loin, j’ai dit un peu plus haut que le vertex sur un edge traversé est choisi sur le milieu. On peut faire mieux. Au lieu de prendre 0,5, on coupe l’edge selon l’interpolation linéaire de la densité des deux coins. C’est l’Extended Marching Cube (EMC) utilisé pour éviter l’aspect cubique et avoir ce genre de champ de voxels :

2Dintersected

Mais les Marching Cubes sont loin d’être sans défauts. Cette technique ne permet pas d’avoir des bords droits et coupe les détails qui ne passe pas par un edge. Ce qui est souvent rédhibitoire dans certaines situations. La prochaine fois on s’attaque à l’algorithme qui pour moi offre les meilleurs résultats : Dual Contouring.

Cubes à la Volée

Bienvenue dans ce dernier article qui clos cette partie sur les bases du maillage de voxels dans Unity. À la fin nous auront ce résultat que vous pouvez essayer ici :

Voxelab – Boxel

En partant de l’article précédent vous avez peut-être créé votre propre implémentation de modification de mesh en jeux. Vous allez pouvoir la comparer avec la mienne ou la faire en lisant la suite.

La première étape est de créer le prefab de notre joueur. Je prend d’habitude une capsule à laquelle j’ajoute la caméra principale. Il ne reste plus qu’à créer les scripts pour les contrôler, PlayerMouvement et FPSViewRotation. Si vous avez l’habitude d’Unity il n’y a rien de particulier, sinon voici les scripts que vous pouvez utiliser :

Et pour la camera :

Pour modifier notre terrain nous allons devoir changer le type du voxel à une coordonnée et refaire le mesh du chunk qui représente cet espace. Pour s’organiser je préfère mettre toutes les fonctions qui agissent sur les chunk dans le script ChunkManager. Voici notre fonction :

Nous faisons ensuite notre script de gameplay nommé ModifyTerrain qu’on attachera à notre prefab « Player ». Il s’agit ici de faire un raycasting pour avoir la position où le joueur clic et de l’indiquer au ChunkManager. Vous pouvez y ajouter un Debug.DrawLine pour l’éditeur.

Et c’est fini !

Je met ici le package complet du guide. Comme je l’ai dit avant il n’y a pas une seule façon de faire, donc je préfère que vous fassiez votre propre projet, mais si vous avez eu des soucis ça vous aidera peux être.

Il y a plusieurs exercices que vous pouvez essayer de faire. On arrive à enlever des cubes, mais comment les ajouter ? Pourquoi certains carrés ne sont pas édités correctement lorsqu’on enlève un cube ? Comment faire pour ajouter des bords à notre petit bout de monde ?

À partir de là votre projet peut partir dans de nombreuses directions. Donc les prochains articles concerneront des sujets plus précis.

Habillons ces cubes

C’est partit pour texturer nos cubes. Tout d’abord si vous avez déjà joué à un jeu comme Minecraft, vous savez qu’il y a plusieurs textures. Comme l’herbe, la terre ou les rochers qui représentent différents types de terrain. Dans notre cas on peut utiliser la technique d’altas pour regrouper ces textures et accélérer leur rendus. Pour l’occasion j’ai fait un atlas simple que vous pouvez utiliser, vous pouvez aussi utiliser la texture de test :

AtlastestTexture

Au passage merci à Hugues pour ses textures gratuites de qualité.

Maintenant nous allons créer un script pour représenter un Voxel :

Nous stockons les Uvs pour les vertices de nos carrés, correspondant aux différents types de textures de notre atlas entre (0 ; 0) et (1 ; 1). On ajoute aussi la taille d’un voxel pour pouvoir modifier la régularité de l’échantillonnage de notre espace.

Nous allons stocker nos voxels dans un tableau pour éviter de devoir recalculer nos densités. Voici le script Voxels :

C’est un tableau à une dimension, plus rapide qu’un tableau à trois dimensions (plus de détails ici).

Il faut garder à l’esprit la différence de représentation des voxels entre les deux espaces. La représentation orthogonale d’Unity, qui peux être des chiffres à virgule en fonction de la taille d’un voxel. Et le stockage des voxels représenté par des chiffres entiers traduit en un indexe à une dimension. Nous avons donc besoin de fonctions pour traduire les coordonnées des voxels entre ces deux espaces.

On va après ré-organiser un peu nos scripts. Nous créons un prefab World pour représenter notre scène :

On y ordonne l’instanciation de nos objets. Et on ajoute les fonctions de notre isosurface.

Il ne reste plus qu’à modifier nos anciens scripts MeshingScript et ChunkManager pour accorder leurs initialisations.

MeshingScript :

On modifie un peu aussi le script pour passer le type des voxels en paramètre. On triche un peu dans Ysquare() pour afficher de l’herbe au dessus des cubes. Il y a de meilleurs façons de faire mais c’est pour l’exemple.

Et pour ChunkManager :

On charge le prefab « Chunk » qu’on place dans l’arborescence « Assets/Resources/Chunk ». Et on récupère le lien vers MeshingScript.

Et c’est tout ! Votre scène devrait maintenant contenir uniquement le prefab « World », la caméra et la lumière. En lançant play vous devriez avoir quelque chose dans ce genre :

Textured

Je m’arrête ici pour cet article je ne veux pas trop le surcharger. Vous avez tous les indices pour faire la modification des mesh en jeu. Donc vous pouvez essayer de la faire comme exercice, sinon on aborde le sujet la prochaine fois.

Gestion de Chunk

Si on veut créer un grand terrain, avec de nombreux détails, on affronte d’abord deux problèmes. Le premier est le nombre de vertex qui augmente avec la taille du mesh et le niveau de détail. Le second est que si on veut modifier le terrain à la volée on ne veut pas refaire l’ensemble du paysage. Couplé à la limite qu’impose Unity d’environ 65k vertex par mesh pour un objet, on comprend qu’on va avoir besoin de nombreux objets.

Notre terrain va donc êtres découpé en morceaux (ou chunk). Nous allons nous concentrer dans cet article sur une version basic et simple de gestion de chunk. L’espace sera composé de 5³ chunks, chacun de taille 16³ unité.

Nous aurons comme résultats trois scripts et prefab différents, le MeshingScript, le Chunk et le ChunkManager.

La première étape est de refaire un peu notre MeshingScript. On modifie la fonction de densité pour l’adapter à notre nouvel espace.

Et le reste des changements :

On créer une fonction publique pour lancer le maillage hors de la classe. On ajoute une fonction pour modifier les composants Unity. Et on finit par une fonction pour remettre à zéro nos listes de données. Au passage , il y a un bug qui oblige a instancier sNoise hors des fonctions d’initialisation d’Unity, si quelqu’un trouve la raison et la solution je suis preneur. J’avais oublié l’ordre d’exécution des fonctions d’Unity, une fonction d’un object peut être appelé avant le Start() (ou Awake()) qui initialise l’objet).  On peut donc instancier sNoise dans la fonction Start() du MeshingScript, et l’appeler dans le Start() du ChunkManager.

On enchaîne en suite avec le ChunkManager lui même.

Plutôt direct et simple comme version. On parcours notre espace de chunk, on le traduit en coordonnées vectoriels – si vous utilisez directement des floats vous allez avoir des problèmes d’arrondis –, on créer nos chunks et on demande a notre MeshingScript de créér le mesh.

Dernière étape, le Chunk.

Ne pas oublier qu’il faut un mesh filter, renderer et collider sur le prefab du chunk.

Et le résultat :

FirstChunkManager

Le chunk Managmer va beaucoup évoluer en fonction de vos objectifs. Est-ce que vous voulez un monde infini ou avec des barrières ? Vous voulez pouvoir modifier vos mesh en jeu ? A quel point voulez vous que votre mesh soit proche de votre isosurface ? Et bien d’autres questions qui seront abordés dans de futur articles.

La prochaine fois on finit avec les bases, on parle de textures et de modification des mesh en jeu.

Les Yeux Plein de Cubes

La façon la plus simple de représenter des volumes à partir de voxels est comme nous l’avons déjà vu d’utiliser des boxels. Nous allons utiliser cette technique pour représenter une octave de Simplex Noise. L’espace représenté sera de taille 32 (unités d’Unity) sur trois dimensions. Comme expliqué dans la partie précédente, nous allons chercher les endroits où change la densité des voxels entre positifs et négatifs.  Voici un schéma simplifié sur deux axes de note mesh:

DensityBoxelMeshing
Champ de densité et boxel mesh.

Nous allons utiliser la fonction de Simplex noise trouvée ici. Il faut d’abord implémenter notre fonction de densité, sans oublier d’ajouter notre objet de noise et de l’instancier dans Start() :

Les nombres à virgules sont l’échelle et la puissance du bruit. Vous pouvez les modifier à volonté pour voir les évolutions. Attention à la limite du nombre de vertices par mesh d’un objet Unity qui est de 65k.

Maintenant nous devons parcourir chaque voxel et vérifier ses voisins pour un changement de signe dans leur densité.

La méthode la plus basique voudrais que l’on compare chaque voxel avec ses voisins suivants et précédents sur les trois axes. En réfléchissant un peu on se rend compte que cela implique de nombreuses vérifications redondantes, donc inutiles. Si le voxel v n’a pas de changement de signe avec le voxel v + 1, alors à la prochaine itération il n’y a pas besoin de vérifier v avec v – 1.

Nous allons donc choisir un coin de notre espace 32x32x32, au hasard (0, 0, 0) parce que c’est pratique pour des boucles. Itérer à travers nos voxels, vérifier leur densité seulement avec leurs voisins suivant (+1), et construire nos carrés si besoins.

Il ne reste plus qu’à modifier la fonction GetVertices() du script qui nous permet de créer le cube pour avoir notre mesh.

Et le résultat :

NoiseBoxelCameraView NoiseBoxelWireframed

Si cet aspect en particulier, vous intéresse pour créer vos mesh, je vous conseille les articles plus approfondis de 0fps. Il y montre différentes méthodes, les compares et détail ses résultats.

C’est un bon début, mais on est encore loin des paysages que l’on peut voir dans des jeux comme Minecraft. La prochaine fois sur Voxelab, comment représenter un plus grand volume ?

Des Volumes de Voxels

Comme expliqué précédemment, les voxels peuvent être associés à des scalaires pour représenter des volumes. J’utilise pour mon projet des fonctions représentant la densité d’un point, sur trois dimensions, part rapport à un volume précis.

Par exemples la fonction de densité d’une plan orienté sur l’axe Y est comme ceci:

Les nombres positifs sont hors du volume, les négatifs à l’intérieur et le zéro est sur la surface. Cette courbe est appelée Isosurface. Les techniques de création de mesh consiste donc à trouver les vertices avec une densité la plus proche de zéro possible.

les fonctions de densité peuvent représenter des objets simples comme une sphère, un cube ou une colonne. Elles peuvent aussi être combiné pour produire des formes plus complexe.

GrandCanyon

Il est aussi possible de calculer une densité en utilisant une carte de hauteur (heightmap). La densité est alors proportionnelle au niveau de gris du pixel de la carte. Cependant cette méthode ne représente que des changements d’élévation que sur deux dimensions. Donc pas d’autres caves et concaves que sur l’axe Y.

Les carte de hauteurs peuvent être créés artificiellement ou récupérés à partir de données naturelles comme sur ce site. Il est possible d’utiliser ces cartes de façons variés comme dans Voxel Quest.

Les cartes de hauteurs on l’inconvénient de proposer des reliefs qui se répètent avec la texture. Ce qui engendre une impression d’artificiel dès que l’œil repère ces motifs. Une, parmi d’autres solution est d’utiliser le Wang Tilling.

En 1983 Ken Perlin invente un algorithme de bruit qui apparaît naturel. En 2001 le Simplex Noise est créé, une amélioration moins complexe à calculer et plus facile à coder. Il existe de nombreuses implémentations disponibles sur internet, ou vous pouvez faire la votre. Des octaves de bruits peuvent être cumulés à différentes fréquences et puissances afin de créer des formes plus complexes. C’est aussi une bonne occasion de modifier la couleur des voxels pour ajouter des détails intéressants. Un bon exemple est dans les GPU Gems de Nvidia.

Les techniques pour créer ces volumes peuvent être combinés selon votre imagination pour modeler les formes que vous souhaitez. Nous verrons plus tard la possibilité de traité ces volumes comme des ensembles booléens pour les assembler facilement.

Il faut cependant se souvenir qu’il faut calculer la densité de chaque voxel qui échantillonne régulièrement l’ensemble de l’espace que vous voulez représenter. Ce qui peut être une quantité de calculs importante.

Nous savons comment créer un maillage procédural, et à partir de quoi. Il nous faut ensuite voir comment extraire les données qui nous intéressent. Et si vous avez lu mon dernier poste je suis sûr que vous avez des idées pour le prochain.

Maillage Procedural dans Unity

Un polygone est formé par un maillage (mesh). Celui ci est composé de points (vertices) qui sont liés par des lignes (edges) et qui forme les plus petites surfaces les triangles.

Dans Unity les mesh sont représentés par un composant appelé le MeshFilter. Il est ensuite envoyé à un autre composant pour être affiché à l’écran le MeshRenderer. Pour s’assurer de ne pas passer a travers le modèle il faut qu’un détecteur de collision soit présent, le MeshCollider.

Nous allons donc créer nos tableaux qui vont contenir les variables de notre mesh. Puis s’assurer que notre objet possède les bons composants. Et les ajouter manuellement ou par script si besoin.

Nous pouvons créer notre fonction qui fabrique nos données pour notre mesh :

Le tableau « triangle » contiens les indices du tableau des vertices qui forme le triangle. Il faut donc que le tableau « triangle » soient de taille trois fois supérieur au nombre de triangles. La direction vers laquelle la surface est dirigée dépend de l’ordre dans lequel sont donnés les indices dans ce tableau. Donc vous n’aurez pas la même surface avec 2, 1 et 0 ou 0, 1 et 2.

Et maintenant nous pouvons créer notre mesh :

Comme indiqué dans la documentation d’Unity il faut toujours commencer par nettoyer l’ancien mesh. On affecte les nouvelles données, les vertices et triangles. On continue avec les recommandations Unity en optimisant le mesh créé. Et enfin on affecte le mesh au collider pour lui indiquer le changement. Attention à bien lui attribuer la valeur « null » avant pour éviter des erreurs.

Et voilà ! Notre premier triangle créé de façon procédurale !

SimpleTriangle

On peut facilement créer un carré, en ajoutant un vertex et les bons indices du nouveau triangle :

Nous ajoutons au passage un matériel et une normal pour chaque vertex afin de permettre au shader de calculer la couleur de notre surface. À noter qu’il est possible d’utiliser la fonction proposer par Unity : Mesh.RecalculateNormals. Mais je préfère vous habituer à penser aux calculs des normales. Dans le cas présent elles sont très simples et on peut utiliser les variables static de Vector3 pour éviter des efforts inutiles. Et le résultat :

SimpleSquare

Vous pouvez faire un exercice simple qui est de créer un cube. Je propose une solution :

SimpleCube

Félicitation vous avez créé la représentation la plus simple d’un voxel en trois dimensions : un cube. Ou plus exactement un Boxel, qui fait plus référence à un traitement matriciel que vectoriel . Avant de faire des mesh plus élaborés comme on peut en voir dans Minecraft, il est important de comprendre comment représenter des volumes plus complexe. Et ça tombe bien puisque c’est le thème de la prochaine partie !