Progressive Mesh (PMesh) / MultiResolutionMesh (MRM) in Managed DirectX

L’utilisation de MRM est une véritable merveille pour accroître de manière significative les performances de ses applications. Le principe est simple : transformer un model 3D détaillé et formé de très nombreux polygones en une version allégée utilisant moins de faces mais aillant un aspect aussi similaire que possible.


Cette technique est la plupart du temps couplée avec la camera pour réduire proportionnellement la qualité du modèle 3D en fonction de la distance à laquelle il se trouve de la camera.


Au final, nous pouvons ainsi grappiller des FPS et libérer le GPU en lui évitant d’afficher des modèles détaillés au loin, là ou une version grandement allégée donne le même résultat à l’écran.


L’image suivant explicite cela :


 


 


 


La porche a 25% donne le même affichage a grande distance que le modèle a 100%.


 


Microsoft nous a gratifiés d’une classe ProgressiveMesh efficace qui répond spécifiquement à ce besoin. Cette classe possède pourtant quelques lacunes :


 


  • Elle est lourde à charger.
  • Elle ne peut pas se charger de manière asynchrone.
  • Elle ne permet pas un contrôle de l’opération de « réduction » de vertices.
  • Elle ne permet pas de gérer les vertices forts (vertices qui ne doivent pas être supprimés lors d’une opération de réduction).

 


Je vous invite d’ailleurs à regarder le sample fourni avec le SDK DirectX.


 


Les MRM occupent une place prépondérante dans mon moteur 3D : Je les utilise  pour libérer du traitement GPU sur l’affichage des objets lointains  et aussi dans l’occlusion culling (l’occlusion consiste à supprimer de l’affichage les objets qui sont cachés par d’autres objets nous y reviendrons dans un autre post). Avant l’utilisation des MRM mon jeu affichait vaillamment 60 FPS pour à peu près 40000 faces affichées. C’est loin d’être mauvais, mais proche d’être bon… Je n’utilisais pas encore l’affichage de lacs, d’effets spéciaux, d’IA, d’effets météorologiques… Au final je serais descendu en deçà de la barre fatidique des 30 FPS. Après cette technique et avant l’utilisation du culling je suis revenu à 80fps.


 


 


Avant de continuer il convient de tester votre motivation à utiliser un algorithme autre que ceux qui existent déjà sur le “marché”. Je pense là bien entendu à la classe ProgressiveMesh de DirectX. Pour ma part plusieurs raisons m’ont poussées à utiliser mon propre code plutôt que celui de Microsoft.


 


  • Le résultat de la classe ProgressiveMesh pour une portion de terrain ne m’allait pas du tout (mes portions sont carrés, la réduction réduisait la surface de ces carrés mais aussi leur forme !).
  • Je voulais avoir un contrôle absolu sur mon code.
  • Je voulais être capable de pouvoir ajouter des effets sans contraintes à la réduction de faces.
  • Enfin je voulais avoir un chargement asynchrone

  


L’algorithme


  


 J’ai donc cherché un moyen de réduire les meshes que j’affichais. J’ai d’abord porté mon choix sur les régions de mon terrain de jeu. Un terrain de jeu dans mon moteur est découpé en X * Y régions carrées. Une région est composée de 32*32 cases soit 1024 faces. Je suis donc parti sur une réduction du nombre de cases. Le premier niveau de réduction m’affichait ainsi 16*16 carrés pour une région. Et ainsi de suite. L’algorithme pour faire ce travail n’était pas trop dur. Il souffrait pourtant de grosses lacunes : les carrés qui disparaissaient pouvaient correspondre au sommet d’un monticule à l’écran, le monticule semblait ainsi translaté par la réduction de faces.  Je n’avais pas de niveaux intermédiaires entre 16*16 et 32*32. La région semblait ainsi soudainement détériorée. Enfin, cet algorithme ne fonctionnait que pour des régions, le résultat pour un arbre ou un personnage était inexploitable.


Je me suis donc tourné vers Google à l’aide des mots clés “MRM algorithme“. J’ai étudié un grand nombre de travaux de chercheurs et de passionnés et j’ai retenu la méthode de Stan Melax parce qu’à priori la meilleure et, cerise sur le gâteau, l’une des plus simples. Melax se base lui-même sur les travaux de H.Hoppes, un développer de MSR (Microsoft Research) dont est issue vraisemblablement l’algorithme se trouvant derrière la classe ProgressiveMesh de Direct3D. Cet algorithme vise a réduire la complexité d’un model 3D par l’intermédiaire de fusions de vertices. S’ensuit :


 


  • La suppression des triangles qui possèdent à la fois les vertices u et v.
  • La mise à jour des triangles qui utilisaient u sur l’un de leurs trois points afin qu’ils utilisent v à la place.
  • La suppression du vertex u.

 


 


A chaque réduction de complexité, deux vertices u et v sont sélectionnés et l'un deux est "fusionné" avec l'autre (ici respectivement u et v).


 


 


 


Le processus est répété jusqu’à atteindre le nombre de vertices ou de faces voulu.


 


Choix de u et v


 


Cette méthode est relativement simple sur le papier et réduit effectivement sans grandes difficultés un model 3D. Il ne faut pourtant pas crier victoire trop vite : j’ai indiqué au départ qu’il fallait que le model “réduit” garde une apparence similaire au model complexe originel. Il convient donc de choisir avec intelligence les sommets u et v à fusionner avec de provoquer la plus fine modification visuelle à l’écran.


 


 


 Le choix du vertex est important !


Le choix du sommet à supprimer est important pour garder une apparence aussi similaire que possible à l’original (image extraite de l’article de Stan Melax avec l’aimable autorisation de l’auteur). 


 


 


C’est là ou le bat blesse : la plupart des algorithmes propose pour ce choix des calculs lourds et inutilisables en temps réel. Sur ce point, Stan Melax a montré son savoir faire. Il part d’un principe élémentaire : les surfaces coplanaires ne demandent pas autant de vertices pour être rendue à l’écran que les surfaces avec un relief prononcé (comme les courbes). Il est plus facile de réduire la complexité des premières, que celle des secondes. Le coût pour la disparition d’un sommet pourrait se traduire ainsi : c’est le résultat de la multiplication de la taille du sommet par l’importance dans la courbe sur laquelle il se trouve.


 


 


Pour la fusion uv, visant à déplacer u vers v nous avons l’algorithme :


 


  • Calculer la taille du sommet (distance u à v).
  • Déterminer l’ensemble des triangles qui possède à la fois u et v.
  • Pour chacun des triangles connectés à u :
    • Calculer le produit orthonormé de la normal du triangle courant avec chacun des triangles qui possèdent à la fois u et v. En extraire le plus petit produit.
  • Calculer le plus gros des plus petits produits : C’est la coùt de la fusion.

La formule mathématique pour calculer ce cout est la suivante est la suivante :


 


 


where Tu is the set of triangles that contain u and Tuv is the set of triangles that contain both u and v.
où Tu est l’ensemble des triangles qui possèdent u and Tuv l’ensemble des triangles qui contiennent à la fois u et v (image extraite de l’article de Stan Melax avec l’aimable autorisation de l’auteur). 


 


 


En fait on parcours tous les triangles connectés à u (u va disparaitre donc ces triangles vont être modifiés pour être connecté a v). Pour chacun de ces triangles on analyse le cout de la fusion avec v. Ce coùt se calcul en analysant la transformation de deux triangles en un seul triangle afin de déterminer l’ampleur de la modification (l’un connecté à u seulement et l’autre connecté à uv qui disprait).


 


 


Le code


 


Vous trouverez un sample DirectX à la fin de cet article. Pour l’heure la classe ProgressiveMesh que vous pouvez reprendre est industrialisable mais est encore améliorable :


 


  • Je n’ai pas terminé l’association d’un poid à chaque vertex pour la transformation.
  • Je n’ai pas faire de trie sur la liste de vertices pour classer par ordre de coùt de transformation.
  • Je n’ai pas fait de méthodes d’optimisation comme dans la classe Mesh de Direct3DX (fusionner les vertices qui sont assez proches pour ne faire qu’un).

 


Trève de bavardage voyons le code.


 


J’ai placé le code que vous pouvez reprendre dans un répertoire du projet nommé “HereAreTheClassesToAddToYourProject” (si ca c’est pas explicite :) ). On y trouve 4 types :


 


  1. ProgressiveMesh<T>
  2. Resolution
  3. VertexAttributeType
  4. VertexAttribute

 


La création d’un mesh progressif et son affichage se fait en trois étapes.


 


Tout d’abord la création de l’objet (étape asynchrone ) en passant au constructeur la liste des vertices qui composent le mesh, la liste des indices pour relier les vertices et enfin les poids associés aux vertices (un tableau de boolèéns pour l’heure) :

ProgressiveMesh<ObjectVertex> mesh = new ProgressiveMesh<ObjectVertex>(vertices, ints, null);


Puis le chargement des buffers 3D lorsque le device a été créé

mesh.Load(this._device);


Enfin l’affichage du mesh

this.mesh.Render();


Comme on le voit la gestion des MRM est beaucoup plus simple qu’avec la classe de Direct3DX.


Revenons sur la généricité de la classe. Le développeur doit indiquer un argument de spécificité a la classe générique ProgressiveMesh (ici ObjectVertex). Il s’agit en fait de la classe utilisée pour le type de vertices.


A partir de cet argument, la classe pourra extraire les positions de chaque vertices et, avec les indices, calculer les différentes résolutions. Elle pourra en outre extraire le format des vertices pour l’affichage, elle pourra aussi renvoyer à l’utilisateur pour chaque résolution es buffers et array de vertices actuellement affichés.


Pour être capable de lire cette structure parfaitement, le développeur doit ajouter a certains membres un attribute qui va indiquer si le champ est l’abscisse, l’ordonnée ou la profondeur de la position du vertex, s’il s’agit du format du vertex ou si il ne s’agit pas d’un champs interessant pour le calcul des résolutions.


Il est donc néccessaire de se créer une custom structure de vertices en lieu et place du sempiternel CustomVertex.PositionNormalTextured.


Voici par exemple une partie de la structure ObjectVertex :


 


    /// <summary>


    /// <para>Custom vertex types.</para>


    /// </summary>


    [StructLayout(LayoutKind.Sequential)]


    public struct ObjectVertex


    {


        /// <summary>


        /// <para>Vertex position on X-axis.</para>


        /// </summary>


        [VertexProperty(VertexPropertyType.X)]


        public float X;


        /// <summary>


        /// <para>Vertex position on Y-axis.</para>


        /// </summary>


        [VertexProperty(VertexPropertyType.Y)]


        public float Y;


        /// <summary>


        /// <para>Vertex position on Z-axis.</para>


        /// </summary>


        [VertexProperty(VertexPropertyType.Z)]


        public float Z;


       


        /// <summary>


        /// <para>Vertex’s normal x value.</para>


        /// </summary>


        public float Nx;


 


        /// <summary>


        /// <para>Vertex’s normal y value.</para>


        /// </summary>


        public float Ny;


 


        /// <summary>


        /// <para>Vertex’s normal z value.</para>


        /// </summary>


        public float Nz;


 


 


        /// <summary>


        /// <para>TerrainTexturedVertex’s format.</para>


        /// </summary>


        [VertexProperty(VertexPropertyType.Format)]


        public const VertexFormats Format =(VertexFormats)0x112;


 


 


J’ai juste utilisé reflector sur sur la structure PositionNormalTextured, j’ai copié collé la classe dans mon code et j’ai rajouté les attributes.


Pour changer la résolutions deux choix. Soit vous utilisez la propriétés NumberOfVertices pour indiquer directement le nombre de vertices a afficher. Soit vous utilisez la property Resolution en donnant un membre de l’énumération :


 

   public enum Resolution

    {

        /// <summary>

        /// <para>No resolution : no mesh rendered.</para>

        /// </summary>

        None = 0,

 

        /// <summary>

        /// <para>No resolution : no mesh rendered.</para>

        /// </summary>

        Dynamic = -1,

 

        /// <summary>

        /// <para>Ten percents of the mesh’s vertices used to render it.</para>

        /// </summary>

        Lowest = 10,

 

        /// <summary>

        /// <para>Twenty five percents of the mesh’s vertices used to render it.</para>

        /// </summary>

        Low = 25,

 

        /// <summary>

        /// <para>Fivety percents of the mesh’s vertices used to render it.</para>

        /// </summary>

        Medium = 50,

 

        /// <summary>

        /// <para>Seventy five percents of the mesh’s vertices used to render it.</para>

        /// </summary>

        High = 75,

 

        /// <summary>

        /// <para>One hundred percents of the mesh’s vertices used to render it.</para>

        /// <remarks>Full vertices are used.</remarks>

        /// </summary>

        Full = 100

 

    }


Le changement de la résolutiond’un mesh demande un leger temps de calcul à priori invisible à l’écran.


 


 


Les liens


 


Evidemment en première place le site de Stan Melax 


http://www.melax.com/polychop/


 


Ensuite le site de Hugues Hoppes


http://research.microsoft.com/~hoppe/


(déprimant parcequ’on voit qu’il fait des trucs super, mais on comprend rien)


 


Le site de reflector que j’utilise pour extraire le code de CustomVertex.PositionNOrmalTextured 


http://www.aisto.com/roeder/dotnet/


 


 


Conclusion

 

L’application au final se présente ainsi :

 

Application de test


 


Je me base sur les samples de DirectX. Détail croustillant j’ai pris le projet ProgressiveMesh de H.Hoppes j’ai supprimé tout le code et j’ai rajouté le miens pour que l’interface soit similaire :)


 


La barre de scroll ou la combobox de resolution changent le détail du mesh courant.


La checkbox permet de voir en fil de fer ou non (en mode solide vous pouvez voir à quel point certains meshs ne changent pratiquement pas de forme).


Enfin la combobox Mesh vous permet de choisir entre 5 modèles de meshs : Porche, Terrain, Lapin, Vache, Fourmi (ce dernier montre les limitation de la réduction de résolution sur un mesh fin).


 


 


A noter que le modèle terrain sert à voir l’utilité du tableau de poids passé au constructeur. Sans ce poid, la portion de terrain “s’arrondit” au fil de la réduction de résolution…


 


N’hesitez pas à me faire des retours surtout ! Pour ma part je vais peaufiner encore le code pour faire fonctionner cette classe dans mon moteur.


 


[Soon]


 


Valentin Billotte



Sample 


telecharger Vous pouvez télécharger le sample ici.

One thought on “Progressive Mesh (PMesh) / MultiResolutionMesh (MRM) in Managed DirectX”

Leave a Reply

Your email address will not be published. Required fields are marked *


*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>