Affichage intelligent de terrains en Xna avec la technique BilLOD

Synthèse :

L'affichage d’un terrain est l'une des parties les plus importantes à aborder dans le développement de jeux. Non pas parce que, conceptuellement parlant, il est l'élément visuel le plus important à l'écran, mais parce qu'il est le principal facteur jouant sur les performances et la qualité de votre application. Il est donc important d'utiliser des techniques qui visent à réduire au maximum la charge supportée par votre jeu pour afficher le terrain tout en préservant sa qualité d'affichage.

Téléchargez le code source

Niveau : débutant

Expérience avec C#/.NET ? Connaissance du langage C# et du framework Xna requise
Expérience en environnement Windows ? Aucune
Microsoft Visual Studio  ? 2008, à partir de la version Express

Si vous êtes un développeur de jeux vous avez forcement déjà travaillé sur l’affichage d’un terrain. Il s’agit généralement du point critique de tout jeu. Non pas parce que, conceptuellement parlant, il est l’élément le plus important visible à l’écran, mais parce qu’il est le principal facteur jouant sur les performances et la qualité de votre application. Il est donc important d’utiliser des techniques qui visent à réduire au maximum la charge supportée par votre jeu pour afficher le terrain tout en préservant sa qualité d’affichage.  Cet article présente justement une technique qui tente d’apporter une réponse à cette problématique en Xna.

Réalisant une étude de moteur de jeu destiné à aider les développeurs de jeux participants au concours Imagine Cup j’ai donc tout naturellement privilégié cet aspect important en cherchant un moyen d’afficher un monde 3D sans limite réelle de taille avec un niveau de détails acceptable.

Il existe nombre de techniques d’affichage de monde explicités par des articles intéressants. Ceux-ci sont souvent basés sur un compromis désagréable qui porte sur un choix entre la taille du terrain ou le niveau de qualité. En outre, ils s’accompagnent souvent d’algorithmes rédhibitoires.

Cet article ne se présente pas comme la seule réponse possible à l’affichage de terrains en Xna mais entend juste apporter une solution efficace fonctionnant pour cette technologie sachant que la plupart des exemples existants sur le Web sont réalisés en DirectX et OpenGL.

Nous découperons notre étude en plusieurs phases :

• D’abord nous décrirons la problématique posée par l’affichage de terrains et expliciterons le besoin d’optimisation.
• Nous décrirons ensuite la méthode utilisée pour découper notre terrain en un QuadTree.
• Nous expliciterons la façon dont nous réduisons le détail du terrain à distance tout en gardant au maximum son aspect à proximité.
• Nous décrirons d’une manière plus technique l’implémentation de cette technique.
• Enfin nous verrons  les possibles optimisations offertes au lecteur.

La problématique

Imaginons que nous voulions modéliser une région de 10 km sur  10km avec un degré de détail sur 1 mètre (1 kilomètre = 1000 mètres). Nous avons donc (sans optimisation) une grille de 100000*100000 à afficher. Continuons dans le brutal en précisant que chaque vertex de la grille possède une taille mémoire égale à approximativement de 40 octets. On atteint alors  environ 4 gigas de données à afficher. Le matériel du joueur lambda actuel ne permet pas de manipuler de telles charges mémoire. Autre problème, un tel terrain modélisé en une grille statique demande le rendu de 200 millions de triangles par frame. Cette façon de procéder est un désastre. A partir du moment où la taille du terrain devient importante et  où l’on ajoute au terrain les ingrédients habituels d’un jeu, comme des modèles 3D, une interface utilisateur, des animations,  les performances d’un jeu ne peuvent plus suivre. C’est là ou la charge prise par le terrain pour son affichage prend toute son importance.

Il est donc important que la part de puissance CPU et/ou GPU prise par l’affichage du terrain soit la plus basse possible afin de garder du temps de traitement pour les autres besoins du jeu.  Les univers virtuels offerts par la plupart des jeux modernes sont gigantesques et ne peuvent plus être réalisé à l’aide d’une simple grille statique

Le besoin d’optimisation est donc clair. J’invite le lecteur à se rendre sur http://www.vterrain.org pour découvrir quelques présentations de techniques autres que celle présentée ici.

Si nous avions un cahier des charges à respecter, nous aurions :

• Garder l’aspect du terrain au maximum en réduisant autant que faire ce peut la charge induite par son affichage
• Rendre la gestion du terrain par le code propre et accessible
• Utiliser une technique efficace et simple et rapide.
• Respecter une approche QuadTree pour optimiser les performances et répondre aux besoins de traitement des jeux.

Le QuadTree

La première étape consiste donc à gérer notre futur terrain par l’intermédiaire d’un QuadTree.

Un QuadTree est une structure de données de type arbre dans laquelle chaque nœud peut compter jusqu'à quatre enfants. Les QuadTrees sont le plus souvent utilisés pour partitionner un espace bidimensionnel (en 3D l’abscisse et la profondeur) en le subdivisant récursivement en quatre nœuds. Chaque nœud possède 4 enfants et ainsi de suite. Le parcours d’un tel arbre est simple et prend en moyenne toujours le même temps : a chaque niveau, il n’y a au maximum que 4 tests à effectuer pour être « autorisé » à descendre au niveau inférieur.  Cet aspect est important eu égard à la mission qui nous incombe ici : « Afficher un terrain avec le maximum de détails pertinents en utilisant le minimum de ressources ». Le but est donc de limiter au maximum le parcours d’un tel arbre au travers de ses nœuds en rendant ces tests « intelligents » et simples.

Principe

Le QuadTree (souvent utilisé pour le rendu de terrain) apporte donc une réponse intelligente au problème d’optimisation. D’abord il ne permet de charger les données que lorsqu’elles sont nécessaires. La charge induite par la représentation d’un nœud à l’écran dépend de la profondeur du nœud dans l’arbre. Inversement, plus tôt on estime qu’un nœud n’a pas à être affiché dans le parcours d’un arbre, plus grande est l’optimisation d’affichage qui est réalisée (on limite par la même occasion le nombre de triangles à afficher). Nous expliciterons tout cela au fil de cet article.

La vraie question à se poser pour optimiser l’affichage de notre arbre est « quel tests sont à réaliser pour déterminer la pertinence de l’affichage d’un nœud à l’écran ». Nous y viendrons rapidement. Pour l’heure concentrons-nous sur la manière dont nous allons gérer l’arbre dans notre code.

Gestion de l’affichage de l’arbre

Au départ notre terrain ne fera qu’un seul nœud : le nœud racine (voir l’image précédente). Celui-ci aura pour dimension la taille du terrain. Un nœud à l’écran correspond à une surface carré composée de 9 vertices :

1. Nord
2. Nord Est
3. Est
4. Sud Est
5. Sud
6. Sud Ouest
7. Ouest
8. Nord Ouest
9. Centre

Le QuadTree se basera sur un heightfield (un tableau à deux dimensions contenant l’ensemble des hauteurs Y de chaque vertex à l’écran). Chaque vertex de chaque nœud dans le QuadTree possède une hauteur dont la valeur est puisée dans le heightfield.

Au départ, seuls les sommets du  nœud sont visibles, soit : Nord Est, Sud Est, Nord Ouest, Sud Ouest. Son rendu correspond à peu près à l’image suivante :

Ces quatre vertices affichés nous permettent de dessiner deux triangles format la surface carrée du nœud. A chaque mise à jour du terrain, pour chaque nœud actuellement visible, nous calculons la visibilité de chacun des vertices. Chaque mise à jour d’un nœud s’accompagne d’un redécoupage des triangles qui le composent. L’image suivante explicite quelques configurations possibles pour un nœud :

L’algorithme pour cette partie serait :

//Pour chacun des vertices Nord, Est, Sud, Ouest
If ( !Vertex.Visible && VertexTest())
	Vertex.Visible = true ;
Else if (Vertex.Visible && !VertexTest())
	Vertex.Visible = false;

Le test de cet algorithme prend en compte la distance à laquelle se trouve le vertex et le besoin croissant de détail à mesure que la camera s’approche de celui-ci. Nous reviendrons sur la nature de ce test plus tard.
Dans un second temps il est nécessaire de calculer la visibilité des enfants du nœud courant.  Un nœud se compose de quatre enfants comme l’image suivante le montre :

Plus on pénètre profondément dans le QuadTree plus le maillage se resserre et permet d’afficher un terrain plus détaillé.

L’algorithme pour cette partie à ce stade de notre étude serait :

//Pour chacun des quatres enfants Nord West, Nord Est, Sud Ouest, Sud Est
If ( !Child.Visible && ChildTest())
	Child.Visible = true ;
Else if (Child.Visible && ! ChildTest())
	Child.Visible = false;

Là encore, le test de cet algorithme prend en compte la distance à laquelle se trouve l’enfant et le besoin croissant de détail à mesure que la camera s’approche de celui-ci. Nous reviendrons sur la nature de ce test plus tard.

Lorsqu’un enfant est visible, ses vertices et ses propres enfants sont soumis aux deux algorithmes que nous venons de voir. Nous sommes donc dans un principe de récursivité.

On calcule les triangles composant un nœud en ne prenant pas en compte les parties occultés par les enfants :

Le principe de base du BilLOD est donc relativement simple. Vertices et enfants à afficher sont soumis à chaque mise à jour du terrain à un ensemble de tests qui déterminent leur visibilité. L’affichage de nœud se fait de manière récursive en parcourant le QuadTree du nœud racine à chaque nœud feuille de chaque branche.

Améliorations

Nous parlions précédemment du partage de vertices entre un enfant et un parent. L’image précédente illustrait ce point. Cette particularité peut être à l’origine d’un bug graphique assez désagréable illustré par l’image ci-dessous :

On y voit un espace entre deux nœuds qui laisse entrevoir le bleu du fond d’écran. Ce problème est dû à la non activation d’un vertex chez le nœud voisin. Explicitons ce problème en image. Schématiquement les nœuds concernés par ce bug sont les suivants :

Soit en réalité :

Le vertex Ouest de l’enfant rouge est activé mais pas le vertex Est de l’enfant jaune. Il y’a donc un delta entre les deux cotés communs des deux enfants. Pour résoudre ce bug il suffit simplement de valider le vertex est de l’enfant jaune :

Au final on obtient une continuité parfaite :

Imaginons maintenant que le vertex sud de l’enfant jaune devienne visible. Le nœud parent ne possède que deux enfants situés au nord ouest et au nord est. Activer ce vertex posera le même problème graphique que précédemment :

Malheureusement, contrairement au cas précédent, il n’y a pas d’enfant au Sud Ouest. Il est donc nécessaire de créer un enfant à cette position (bien que le « ChildTest » de notre algorithme pour cet enfant renvoie false) et de lui activer son vertex Nord :

L’ajout du vertex sud de l’enfant blanc à provoqué à la création de l’enfant Sud Ouest et l’activation du vertex Sud du nœud parent. Ce vertex Sud peut lui-même provoquer la modification des nœuds voisins. On assiste là à des effets en cascade qui ne sont pas vraiment contrôlable mais sont, fort heureusement, limités. L’image suivante montre l’impacte de l’activation de plusieurs enfants profondément dans le QuadTree en bas à droite du terrain.

noeud

On remarque que les nœuds situés à l’opposé du terrain sont impactés.

Activation/désactivation du nœud dans le QuadTree

Quelques années auparavant j’ai lu un excellent article d’une personne nommée Stan Melax auteur d’une technique ingénieuse permettant de calculer de manière dynamique l’aspect d’un modèle 3D à différent niveau de résolution. Les articles sur les meshs progressifs sont soumis aux mêmes lois que ceux sur les terrains : soit l’algorithme de réduction est trop compliqué, soit il est mal adapté. Stan Melax a trouvé une manière intelligente de résoudre ce problème. Il étudie le coût  de la disparition de chaque vertex en étudiant leur impact sur la forme globale. Il est alors capable de réduire progressivement la résolution du modèle 3D en supprimant dans un ordre logique les vertices les moins impactant. Sa force réside dans le calcul du coût d’un vertex qui s’avère être une formule simple et efficace. Nous procéderons de la même manière.

La courbe, l’élément à retenir

Pour parler simple, on mesure l’aspect d’un terrain à ses formes. On mesure une forme à ses courbes. La question est alors : comment définir une courbe ? Répondre à cette question permettrait de déterminer les emplacements du terrain où il faut garder un niveau détail important et ceux qui peuvent être dégradé.

Il existe un grand nombre de technique pour transformer une courbe en une fonction mathématique. Nous revenons dans ce cas à la problématique du départ : ne pas surcharger trop le processeur. Nous l’avons vu, il est nécessaire d’appliquer la formule trouvée à tous les vertices et à tous les enfants des nœuds. Une formule trop couteuse en instructions détériorera les performances de l’application.

La solution est en fait simple. Nous l’avons dit, notre terrain est découpé en nœuds appartenant tous à un arbre. Chaque courbe du terrain est donc constituée de nœuds qui sont en fait des surfaces carrés dont la taille varie

La normale, ordre de grandeur d’une courbe

Plus la courbe est importante, plus les nœuds qui la composent forment un angle important. Prenons pour exemple une courbe vue de profil :

On y voit ensemble de nœuds collés côte à côte. A l’endroit où la courbe est réellement importante on remarque que les nœuds forment un angle important. Au contraire à l’endroit où il n’y a pas de courbe mais une simple pente, les nœuds côtes à côtes ne forment pas d’angle mais semblent appartenir à un même plan. On le remarque encore plus si on affiche les normales de chacun des nœuds :

Nous sommes maintenant proches de trouver la formule ! Tous les lycéens savent que la fonction mathématique qui mesure l’angle entre deux vecteurs est le produit scalaire (dot product).

L’angle maximum que l’on peut trouver dans une courbe d’un terrain tel que nous le concevons tend vers les 90° (la valeur 90° ne pouvant être atteinte dans le mesure ou les nœuds ne peuvent se chevaucher). Cos 90 valant 0 on peut en déduire que plus la courbe formée par les vecteurs est importante plus leur produit scalaire s’approche de 0 (A*B*Cos(90) = A*B*0 = 0). Au contraire si la valeur du produit scalaire augmente, c’est que la courbe formée par les deux nœuds tend vers la « droite » (A*B*Cos(0) = A*B*1 = AB).  Voyons tout cela en image :

Le produit scalaire entre la normale du parent et celles des enfants va renvoyer ici une valeur clairement  différente de 0 : nous sommes sur une surface, certes inclinée, mais plane. Inutile de découper le nœud.

Prenons maintenant une courbe prononcée

L’angle entre les trois normales est plus prononcé. Le nœud originel (symbolisé par la ligne en pointillée noire) doit être découpé en sous-nœuds. On peut trouver dans cette façon de procéder une certaine logique : une surface plane se modélise facilement avec peu de polygones. Une surface courbée en demande beaucoup plus. Voici pour terminer la courbe en wireframe :

Méthode d’activation

La méthode Child Test devra donc comparer la normale de l’enfant à tester avec celle du nœud parent auquel il appartient. Si l’angle entre les deux normales dépasse un seuil limite alors la méthode renvoie true.

Test de désactivation

La désactivation d’un enfant ne se fait que lorsqu’une série de facteurs est rencontré :

• L’enfant n’a plus de vertices visibles
• L’enfant n’a plus de sous-enfants
• La méthode de Test renvoie false.

Activation/désactivation du vertex dans le nœud

De l’interpolé au réel

La gestion de la visibilité des vertices ne suit pas la même logique que celle décrite précédemment. Ici il n’est pas question de courbes  mais de delta.  Seuls les vertices situés sur les cotés d’un nœud sont à tester. Soit Nord, Est, Sud, Ouest. Lorsqu’un nœud est créé, ceux-ci ne sont pas visibles. Situé entre deux vertices sommets on peut déduire leur hauteur facilement. Voici un exemple de nœud vu de coté :

On y voit les vertices Nord Ouest et Sud Ouest activé (visibles)) et le vertex Ouest  désactivé.

Ce dernier semble être sur la droite parcourant les deux sommets. En fait il n’en est peut être rien. Pour l’heure nous avons interpolé (déduit) sa position (Si Sud Ouest est à une hauteur de 10 et Nord Ouest à une hauteur de 20, on peut raisonnablement penser qu’Ouest sera à une hauteur de 15). Pourtant en réalité  il se trouve peut être à une position tout autre :

On y voit une distance delta qui sépare la position du vertex Ouest interpolée de sa position réelle. Cette différence de hauteur mesure le degré de réalité du nœud actuellement affiché avec une version plus détaillée.

Afficher le nœud avec seulement les 4 vertices sommets affichés ne rend donc pas bien compte de la réalité du terrain affiché par le nœud.

Méthode d’activation

La méthode d’activation est ici très simple, il nous suffit de déterminer la valeur delta (une simple différence de hauteur) et de déterminer si elle dépasse, là aussi, un seuil.

Test de désactivation

La désactivation d’un vertex ne se fait que lorsqu’une série de facteurs est rencontré :

• Le vertex n’appartient pas à un nœud enfant
• La méthode de Test renvoie false.

Détail Progressif

C’était l’un des pré requis de notre technique : nous devons optimiser l’affichage en fonction de la position de la caméra. Pour l’heure nos deux fonctions de tests (pour les vertices et les enfants de nœuds) ne prennent pas en compte la position de la caméra et la position de l’élément à tester.

Nous l’avons vu dans les deux algorithmes dédiés aux vertices et aux nœuds, un test est réalisé pour déterminer si un vertex ou un enfant doit être affiché ou non. La qualité du terrain affiché doit être fonction de la position de la caméra pour le confort du joueur. Plus une zone du terrain est proche de la camera plus elle doit être détaillée. Le but est aussi de préserver au maximum l’aspect du terrain au loin avec un minimum de vertices et de progressivement détailler lorsque la caméra s’approche.

Détail progressif pour le QuadTree

Pour l’heure la méthode de test se base sur l’ouverture de l’angle formé par la normale d’un enfant avec son parent.  Cette façon de procéder n’est pas forcement pertinente à distance.

Si un angle de quelques degrés est visible lorsqu’on est proche des nœuds qui le composent, cet angle n’est pas forcement détectable à distance. Il n’est alors pas nécessaire d’activer l’enfant.

Voici l’implémentation de cette méthode de test :

private bool ChildTest(Vector3 childNormal, BoundingBox boundingBox, Vector3 cameraPosition)
{
    //by default, the four childs of the root node are visible.
    if (this.Depth < 1)
        return true;

    //get the closest point to the camera and check the distance
    float distanceCameraToPoint = Vector3.Distance(GetBoundingBoxClosestPointToPoint(boundingBox, cameraPosition), cameraPosition);
    //compute the dot product between parent normal and child normal
    float dotprod = 1 - Vector3.Dot(childNormal, this.CenterVertex.Value.Normal);

    //check with the threshold
    return (distanceCameraToPoint / this.ParentTree.QuadTreeDetail) < (dotprod);
}

Par défaut les nœuds situés au sommet de l’arbre sont rendus visibles. Nous déterminons ensuite la distance entre la position de la caméra et le point le plus proche de celle-ci dans la boundingbox englobant l’enfant. Le produit scalaire est ensuite calculé. Nous testons alors si la division de cette distance par un seuil paramétrable  est inférieure au produit scalaire.

Il est à noter que cette méthode de test peut très bien être adaptée pour soumettre le QuadTree à une autre technique d’optimisation.

Détail progressif pour le vertex

La encore, la méthode de test pour les vertices ne prend pas en compte la distance à la caméra. Nous devons déterminer si la distance entre la position réelle du vertex et sa position interpolée dépasse un seuil paramétrable.

Voici la méthode de test :

public bool VertexTest(Vector3 vertexPosition, Sides side, Vector3 cameraPosition)
        {
            //get the distance between interpolated height position and real height position
            float lengthToTest = this._realToInterpolatedVertexHeight[(int)side];
            //get the distance from the camera position to the vertex position
            float distanceCameraToPoint = Vector3.Distance(vertexPosition, cameraPosition);

            //check with the threshold
            return lengthToTest * this.ParentTree.VertexDetail > distanceCameraToPoint;
        }

Le delta entre les deux vertices (interpolé et réel) est stockée en mémoire. Nous la rapatrions. Nous déterminons ensuite la distance entre le vertex et la caméra. Un test est alors effectué pour déterminer si le delta conjugué au seuil dépasse la distance à la caméra. Tout comme précédemment cette méthode de test peut très bien être adaptée pour soumettre le les vertices de chaque nœud à une autre technique d’optimisation.

Améliorations

Notre algorithme, à ce stade, fonctionne parfaitement : il n’affiche les détails que là où ils sont pertinents, libères les ressources au maximum et utilise un quadtree.

Rappelons que pour l’heure, la pertinence de l’affichage d’un nœud se mesure à l’aide du produit scalaire de sa normale avec la normale de son parent direct. Cette façon de procéder est plutôt satisfaisante mais nous pouvons l’améliorer. Les deux images suivantes illustrent un bug graphique assez désagréable qui modifie l’aspect du terrain à courte distance :

On remarque que la bosse visible sur la première image est réduite fortement par le seul fait d’avoir avancé légèrement la caméra. Notre algorithme a pourtant parfaitement fonctionné. Nous avons simplement validé un seuil obligeant un nœud à se découper.  Il nous faut donc limiter au maximum l’application de notre algorithme a proximité de la caméra. Nous allons donc instaurer un second seuil qui va représenter ce que nous entendons par « proximité ».

La nouvelle méthode de test se présente donc comme ceci :

/// <summary>
/// <para>Check the relevance of a child.</para>
/// </summary>

private bool ChildTest(Vector3 childNormal, BoundingBox childBoundingBox, Vector3 cameraPosition)
{
    //by default, the four childs of the root node are visible.
    if (this.Depth < this.ParentTree.MinimalDepth)
        return true;

    //get the closest point to the camera and check the distance
    float distanceCameraToPoint = Vector3.Distance(GetBoundingBoxClosestPointToPoint(childBoundingBox, cameraPosition), cameraPosition);
    //compute the dot product between parent normal and child normal
    float dotprod = 1 - Vector3.Dot(childNormal, this.CenterVertex.Value.Normal);

    //check with the threshold
        return ((distanceCameraToPoint - this.ParentTree.QuadTreeDetailAtFront) / this.ParentTree.QuadTreeDetailAtFar) < (dotprod);
}

Nous avons maintenant deux seuils, un seuil de visibilité proche permettant d’affiche les détails au maximum à une distance spécifiée et un seuil de visibilité à distance qui gère les détails au delà du seuil précédent en respectant une fonction affine comme nous le faisions jusqu’alors.

L’avantage est alors incontestable. Pour preuve, regardez l’image ci-dessous :

Je suis allé au centre d’un terrain, j’ai stoppé l’application de l’algorithme (assimilable à une sorte de pause dans la gestion du QuadTree) et j’ai pris de l’altitude. On remarque que les détails semblent s’amoindrir lorsqu’on s’éloigne du centre. C’est effectivement le cas :

Au centre de l’écran, près du cratère, les détails sont au maximum. Si nous étions au sol, nous ne verrions aucune aspérité du terrain proche être modifiée en déplaçant la caméra. Au contraire, en s’éloignant les détails s’amenuisent mais garde toutefois l’aspect global du terrain.

Ce n’est pas tout, nous sommes maintenant capable de générer un aspect climatique et géographique bien connu : une ligne montagneuse. Regardez l’image suivante :

Il s’agit de la ligne bleue des Vosges parfaitement visible depuis le nord de la Franche-Comté en France. Plus on regarde au loin plus un brouillard se fait sentir dans une teinte bleutée. En appliquant notre algorithme modifié et un brouillard nous sommes capables de générer une ligne d’horizon épurée au maximum afin de réduire d’un nouveau cran les ressources prises par l’affichage du terrain. Retournons sur notre terrain, mais cette fois ci en étant proche du sol :

Nous avons ajouté un brouillard bleu pour simuler cet effet. Les montagnes à distance ne sont plus visibles que par la différence de couleur que celui-ci leur procure. L’algorithme garde bien l’aspect à proximité mais aussi à distance. Pourtant à distance, les détails pourraient être encore épurés dans la mesure où le brouillard nous cache nombre d’aspérité. Voici maintenant la même vue mais avec un seuil de visibilité à distance grandement réduit :

Nous obtenons un affichage relativement similaire mais avec 1300 primitives en moins !

Code et optimisation

Le code donné avec cet article est volontairement sommaire pour des raisons de compréhension. Son but est de tester la technique Billod décrite ici de manière simple et lisible sans chercher en aucune manière tout type d’optimisation.

Description des classes « métier »

Quatre classes sont réellement métier :

Le terrain est géré tout naturellement par une classe nommée Terrain. Nous reviendrons plus tard sur sa possible utilité. Terrain est un conteneur de QuadTrees. Il représente le terrain dans sa globalité.

• L’arbre est représenté par une instance de la classe QuadTree. QuadTree représente une portion de terrain. C’est un conteneur de QuadNodes.
• Les nœuds de l’arbre sont créés à l’aide de la classe. QuadNode. C’est un conteneur de TerrainVertex.
• Enfin les 9 vertices d’un nœud sont des TerrainVertex. QuadNode représente un nœud.

La majeure partie du traitement se situe à l’intérieur de la classe QuadNode. Celle-ci dispose de deux méthodes importantes : Initialize et Update.  La méthode Initialize s’occupe de charger le node avec toutes les informations liées à sa position dans le QuadTree. Elle rend visible les 4 sommets, elle détermine les nœuds voisins (pour le partage de vertices). Elle calcule en outre, les deltas, les normales, les boundingbox. Elle n’est appelée qu’une fois à chaque création d’un nœud.

La méthode Update effectue les tests sur les quatre vertices « cotés » (Nord, Est, Sud, Ouest) et sur les quatre enfants potentiels (Nord Ouest, Nord Est, Sud Ouest, Sud Est) à chaque mise à jour de l’arbre.

C’est la classe QuadTree qui initialise le premier node et débute le traitement sur l’arbre. Toutes les x secondes (paramétrable) elle lance un update asynchrone sur tous les nœuds instanciés pour mettre à jour l’arbre en fonction de la position de la caméra.

L’instanciation d’un QuadTree se réalise en précisant la taille de celui-ci, sa profondeur et sa location :

QuadTree tree = new QuadTree(treeDepth, rootNodeSize, location);

La structure TerrainVertex contient le vertex à afficher. Un vertex peut être partagé sur plusieurs nœuds.

Le code de ces quatre classes importantes a été simplifié à l’extrême et largement commenté. S’il reste des points noirs n’hésitez pas à me contacter.

Thread Update

Une solution simple et rapide à implémentée à été choisie pour la mise à jour du terrain. Un backgroundWorker est lancé au démarrage de l’application et s’occupera de la mise a jour du terrain de manière asynchrone.

Cette façon de procéder évite tout ralentissement du jeu lors de l’update. Les données d’affichages (VertexBuffer et IndexBuffer) sont stockées dans une pile et utilisé dans la méthode Render. Dans l’exemple fourni avec cet article, nous n’effectuons un Update que toutes les 4 secondes.

Optimisations

En dehors des améliorations portant sur le code, voici quelques pistes pour augmenter la qualité du rendu et la puissance de la technique Billod.

Plusieurs optimisations sont possibles :

• Nous effectuons deux parcours de l’arbre à chaque Update (l’un pour mettre à jour l’arbre, l’autre pour extraire la liste triangles à afficher). Il y’ peut être un point à améliorer ici.
• Le backgroundWorker pour un jeu Xna  n’est pas un choix judicieux. Un thread normal encapsulé dans une gestion adaptée serait plus efficace.
• La mise à jour toutes les X secondes n’est pas forcement la meilleure solution. Il y’a plusieurs autres pistes possible : mettre à jour que lorsque la caméra est déplacée. Prévoir les déplacements du joueur et mettre à jour en conséquence. Enfin, il faut savoir que l’état final d’un arbre ne s’obtient pas en un seul Update. Il est peut être préférable dans certains cas d’attendre la version finale de l’arbre en appelant la méthode Update autant de fois qu’il le faut avant de générer les données d’affichage.
• Verrouiller l’arbre. On peut le deviner, il arrive que des seuils pour l’activation ou la désactivation d’un enfant ou d’un vertex soient vraiment très faibles. Autant éviter le calcul du test pour eux et considérer qu’ils ne seront jamais activés.
• Interpoler les transitions. Lorsqu’un nœud est découpé ou fusionné, ou bien lorsqu’un vertex change d’état (visible/caché), la transition est visible à l’œil nu. Il peut être utile de découper cette transition en plusieurs étapes progressive pour adoucir les changements visuels.
• S’appuyer sur la classe Terrain. Pour l’heure nous n’affichons qu’un seul Arbre. La classe terrain peut être un sérieux tremplin pour tenter de gérer plusieurs arbres qui seront liés les un aux autres. Cette façon de procéder permettrait de réaliser des horizons à l’aide de QuadTree tellement éloignés qu’ils en seraient réduits à quelques vertices.
• Nous chargeons le Heightfield en entier dès le départ en analysant une image en noir et blanc (plus la couleur lue est noire, plus l’altitude est faible.). C’est une façon efficace de procéder pour réaliser un exemple ce l’est moins dans le cadre d’un jeu affichant un monde d’une très grande taille. Il serait peut être judicieux de stocker l’array de hauteur dans un fichier et de ne lire que ce que le QuadTree a besoin à chaque Update. Ceci libérerait la mémoire.
• Le code source n’a pas été optimisé pour des raisons de lisibilité. A vous de restaurer un code rapide et efficace !

Le programme d’exemple

Ce programme n’est qu’un rapide exemple d’implémentation du terrain Billod. Les classes métier sont toutefois rapidement adaptables au besoin de chacun. Le projet est réalisé en Xna 3.0. Il est toutefois adaptable au 2.0.

Les commandes pour interagir avec le monde sont :

• Souris : Cliquer pour tourner la caméra.
• Touches fléchées : déplacement de la caméra dans la direction courante.
• Touche W : Mode Wireframe On/Off.
• Page Haut / Page Bas : Seuil de test éloigné des enfants.
• Touche left Shift + Page Haut / Page Bas : Seuil de test proche des enfants.
• Touche left Shift + Touches fléchées : déplacement rapide.
• Touche left Alt + Touches fléchées : déplacement lent.

Le test du terrain Billod se fait simplement en se déplaçant sur le terrain et en étudiant l’évolution du terrain.

A noter qu’il est possible de modifier une parties des paramètres influant sur l’affichage à l’aide du fichier de configuration de l’application.

Vous pouvez réutiliser le code source à votre guise. Je demande juste de me référencer dans vos « credits » :)

Références / Remerciements

Le site de Stan Melax : http://www.melax.com.  Quelqu’un de très pragmatique à l’origine d’une technique de Progressive Mesh très intelligente sur laquelle je me suis basé. Je profite de cet article pour le remercier de sa gentillesse et de ses échanges à l’époque où je travaillais sur les progressive meshes en Xna.

« Continuous LOD Terrain Meshing Using Adaptive Quadtrees” par Thatcher Ulrich. Une méthode assez proche de la mienne mais plus orientée vers la recherche de deltas. C’est l’une des rares méthodes sur le web utilisables dans un jeu. La technique Billod possède un QuadTree assez similaire à son « Adaptive QuadTree » mais sa gestion du heightfield est bien plus intelligente que la mienne. Sa gestion du détail est par contre, à mon goût, moins précise.

La page d’Hugues Hoppe : http://research.microsoft.com/~hoppe/. L’un des maîtres du terrain rendering. Tout est bluffant mais illisible pour le néophyte et pas forcement adapté au monde du jeu vidéo.

Virtual Terrain Project : http://www.vterrain.org/. Le site incontournable regroupant un ensemble de publications autour de la gestion de terrain.

Et d’une manière plus personnelle Mathieu Laussel, un ami modeleur 3D (de génie) avec qui je réalise un éditeur de monde et qui a bien voulu patienter le temps que j’écrive cet article. Mais aussi Boris Driss un passionné de développement de jeux avec qui les échanges étaient plus qu’intéressants.