Retourner au sommaire des cours
Avant toutes choses je tiens à remercier Stan Melax qui m'a gentiment aidé à passer son algorithme en DirectX et Xna et m'a laissé la possibilité d'utiliser pour ce cours quelque schémas qu'il avait réalisé.
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 suivante explicite cela :
On y voir l'affichage d'une voiture sous différentes résolutions (le poucentage indiqué au dessus de chaque modèle correspond au nombre de vertices utilisé par rapport à l'original). Le modèle à 10% reste tout à fait acceptable et similaire à l'original. Il est donc tout à fait imaginable de l'utiliser à grande distance à la place d'un modèle plus "complet" et plus lourd à manipuler.
Les MRM (multi resolution mesh) occupent une place prépondérante dans les moteurs 3D : Utilisés pricipalement pour libérer du traitement GPU sur l’affichage des objets lointains il est aussi employé 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). Nous allons donc dans ce cours chercher un moyen pour créer et utiliser des MRM dans nos applications. Ce moyen, c'est bien evidemment un algorithme qui va etre en mesure de calculer la réduction du nombre de vertices dans une forme 3D en sauvegardant au maximum son aspect général lors de cette transformation. L'algorithme
Une complexité qui rebute
Si on se tourne vers les moteurs de recherche sur le net (live.com, google.fr) à l'aide des mots clés "MRM algorithme" on trouve un grand nombre de travaux de chercheurs et de passionnés sur ce sujet. Pourtant la plupart des algorithmes qu'on y trouve sont inexploitables : soit ils sont trop gourmants en calculs et donc inexploitable en temps réel, soit le resultat change l'aspect de la forme 3D ou bien encore la complexité est telle qu'il est tout bonnement incompréhensible. Quelques pasionnés ont toutefois trouvé un moyen de réaliser des réductions de résolutions relativement simplement. Nous retiendrons ainsi la méthode utilisé par Stan Melax parce qu'à priori la meilleure et, cerise sur le gâteau, l'une des plus simples.
Réduction par Fusion de Meshs
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. Le principe est trivial : à chaque réduction de résolution on fusionne deux vertices (que nous nommerons ici u et v).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.
Le schéma ci-dessus explicite tout cela. La figure A montre l'état du modèle avant la baisse de résolution. La figure B montre le même modèle après la fusion de deux de ces vertices. Le modèle garde son aspect mais en utilisant un vertex et deux faces en moins.
Ce 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 : comme dit précédemment, il est primodial 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 afin de provoquer la plus fine modification visuelle à l'écran. L'image suivante illustre celà :
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 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 :
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).
Le principe peut se résumer ainsi : on parcourt tous les triangles connectés à u. Il est nécessaire, pour chacun de ces triangles, d'analyser le cout de la fusion avec v. On calcul celà en analysant l'impacte de la transformation des triangles afin de déterminer l'ampleur de la modification. Il y'a deux types de modifications : Soit les triangles sont connectés uniquement à u, et, dans ce cas ils sont modifiés pour être reliés à v, soit les triangles sont liés à u et v à la fois et doivent etre supprimés du modèle. La figure A et B au début de cette annexe illustre celà parfaitement.
Passons aux choses sérieuses
Pour l'heure la classe ProgressiveMesh que vous pouvez reprendre est industrialisable mais est encore améliorable :
-
Il reste à associer un poid à chaque vertex pour la transformation.
-
A réaliser un tris sur la liste de vertices pour classer par ordre de coût de transformation.
-
A réaliser des méthodes d'optimisation comme dans la classe Mesh de Direct3DX (fusionner les vertices qui sont assez proches pour ne faire qu'un).
Passons maintenant au code.
Celui-ci se trouve à l'intérieur d'une DLL nommée ArcaneEngine.Objects. Deux types de données nous interesse :
- ProgressiveMesh<T>
- Resolution
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 pouvant être 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éens pour l'heure) :
ProgressiveMesh<VertexPositionNormalTexture> mesh = new ProgressiveMesh<VertexPositionNormalTexture>(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();
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 VertexPositionNormalTexture). 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 resolution les buffers et array de vertices actuellement affichés.
Pour changer la résolution deux choix. Soit vous utilisez la propriété 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.
Nous n'analyserons pas ici le code qui reste assez simple. A l'intérieur de la classe ProgressiveMesh se trouve la region "Multi resolution computing" qui contient les méthodes liées au calcul de la resolution. La méthode ComputeEdgeCostAtVertex détermine le cout de la fusion d'un vertex, la méthode Collapse réalise cette fusion et MinimumCostEdge permet de trouver le vertex ayant le coût le plus bas pour une fusion. A noter que la classe ProgressiveMesh possède deux types internes : Vertex et Triangle qui permettent d'opérer sur les vertices et les faces plus facilement.
Une analyse du code par vos propres moyens devrait eclaircir tous les points encore obscurs à vos yeux. N'hesitez pas a poster des commentaires pour toutes questions.
A l'intérieur de la classe Game1 se trouve le code qui montre comment utiliser notre classe ProgressiveMesh. L'application principale contient en outre un ensemble de classes statiques qui contiennent des ensembles de vertices et d'indices permettant de charger un MRM. Elles héritent toutes de l'interface IData qui permet une utilisation générique de ces dernières.
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)
Sample
Vous pouvez télécharger les trois samples ici.
Conclusion
L'application au final se présente ainsi :
L'interface graphique est rudimentaire mais nous l'améliorerons avec l'arrivée de l'annexe portant sur l'UI. Les touches Page Haut et Page Bas permettent de passer d'une résolution à une autre. Les touches + et - permettent de modifier la resolution plus finnement en changeant le nombre de vertices affichés. La souris permet de déplacer la camera autour du mesh affiché. Enfin la touche espace permet de changer de modèle. L'application affiche 6 modèles :
-
Beethoven
-
Fourmi
-
Un terrain
-
Porsche
-
Vache
-
Lapin
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 en perdant ainsi tout son aspect. Notez de même que le modèle fourmi montre les limites de notre système sur les formes 3D disposant de peu de vertices ...
A bientôt sur ce Blog !
Valentin Billotte
N'hesitez surtout pas à me faire part de vos incomprehensions afin de pemettre d'améliorer ce cours pour le rendre plus accessible aux autres (trèèèès important)!
Vous pouvez télécharger les trois samples ici.
Retourner au sommaire des cours