Simplification à niveaux de détails statiques

Principe

La simplification statique correspond aux méthodes générant un ensemble discret de versions simplifiées d'un modèle complexe donné. Lors du rendu, il suffit de choisir le bon modèle à afficher en fonction de la distance d'observation. Différents types d'algorithmes ont été développés pour générer ces maillages simplifiés. Nous ne détaillerons pas leur fonctionnement en profondeur, mais décrirons leurs principales caractéristiques, avantages et inconvénients. Pour plus de détails, voir [Lue01], sur lequel est basée cette partie.

Méthodes existantes

Une première classe d'algorithmes est formée par ceux qui emploient la décimation de maillage, comme [SZL92]. Le principe est de choisir des sommets dans le maillage complexe et de les supprimer. Les trous ainsi créés sont remaillés en employant diverses méthodes qui réduisent le nombre final de faces tout en préservant la topologie du modèle. L'algorithme procède en plusieurs passes en choisissant à chaque fois si un sommet peut être supprimé selon deux critères : le sommet sera enlevé si sa suppression préserve la topologie du maillage et si la retriangulation du trou qu'il crée donne des faces à une distance du maillage originel inférieure à un certain seuil.

Avec cette méthode, les maillages simplifiés créés sont des sous-ensembles du maillage de base, ce qui permet de préserver les attributs des sommets (couleur, normale, coordonnées de texture) De plus, la qualité des modèles simplifiés peut être améliorée en déplacant les sommets créés pour qu'ils améliorent l'aspect visuel final [GH97].

Néanmoins le fait qu'ils préservent la topologie du maillage empêche une très grande simplification. D'autre part, ces algorithmes sont très long à calculer.

Une autre type d'algorithme, le regroupement de sommets (Vertex Clustering) de Rossignac [RB93] procède, comme son titre l'indique, en regroupant certains sommets entre eux. Pour cela dans un premier temps, une importance est attribuée à chaque sommet du maillage complexe selon divers critères tels que la courbure de la surface en ce point ou la taille des faces qui lui sont connexes. Ainsi, des sommets attachés à de grandes faces ou des sommets de grande courbure seront considérés plus importants que les autres et donc seront gardés le plus longtemps possible. Ensuite, une grille 3D est superposée au modèle puis tous les sommets appartenant à une cellule sont regroupés au sommet le plus important de la cellule. Ainsi, plus la grille est grosse, plus la simplification est importante.

Des améliorations ont été proposées [LT97] permettant d'adapter localement la résolution de la grille, ou de calculer l'importance d'un sommet.

Cette techniques est très rapide ($o(n)$, avec $n$ = le nombre de sommets) et ne demande pas beaucoup de mémoire.

Néanmoins, la topologie du modèle original n'étant pas préservée, les résultats visuels sont moins satisfaisants qu'avec la méthode précédente. De plus, on ne peut pas pas prévoir le nombre de polygones générés.

Une autre approche basée sur des cellules 3D (Voxels, Eléments de volume) a été proposée par [HHK⁺95]. La première passe consiste à ''voxéliser'' le modèle complexe, c'est dire à le transformer en une représentation volumétrique. Un voxel sera ''plein'' ou ''vide'' en fonction de la position de son centre : à l'intérieur ou à l'extérieur du modèle. Ensuite, une filtre passe-bas est appliqué sur le volume, qui est ainsi rééchantillonné de façon plus grossière. Ainsi, les petites variations de géométrie (de haute fréquence) sont éliminées. Finalement, le maillage est reconstruit en appliquant l'algorithme du marching cube [LC87].

Cette technique ne préserve pas la topologie du modèle et a tendance à lisser les arêtes ce qui réduit son intérêt car on perd la silhouette du modèle.

La simplification par surfaces enveloppantes de Cohen [CVM⁺96] permet d'obtenir des très bons résultats graphiques en forçant la déviation géométrique entre le modèle original et le modèle simplifié à résider dans un espace fixé. Cet espace est défini en positionnant deux surfaces autour et à l'intérieur de la surface du modèle à simplifier. Ces surfaces sont créées en déplaçant la surface originelle d'un petit intervalle $\varepsilon$ le long des normales des sommets : $+\varepsilon$ pour la surface externe et $-\varepsilon$ pour la surface interne. Cet intervalle est spécifié par l'utilisateur. Les deux enveloppes englobantes ne doivent pas s'intersecter : l'intervalle $\varepsilon$ est modifié par sommet le cas échéant. Le processus de simplification est le même que la décimation de maillage : des sommets sont supprimés, mais les choix des sommets sont faits de façon à ce que le maillage résultant reste dans les deux enveloppes.

Le principal avantage de cette méthode est la fidélité du maillage résultant car la topologie est respectée. De plus, l'intervalle de simplification $\varepsilon$ peut être basé sur la distance d'observation : croissant avec l'éloignement et fonction de la différence visuelle avec la surface originelle.

Néanmoins, les calculs sont lourds, les modèles ne peuvent pas être très simplifiés et la méthode n'est pas très robuste : si la surface n'est pas orientable ou topologiquement correcte^1.2, les calculs échouent.

Avantages

De façon générale, ces algorithmes sont faciles à utiliser dans une application de réalité virtuelle interactive car les modèles sont précalculés à l'avance : on génère les différents niveaux de détails d'un modèle et on les utilise directement lors du rendu, en choisissant l'un ou l'autre en fonction de la distance d'observation.

Inconvénients

Le plus gros problème de ces modèles pré-générés utilisés dans le cadre d'une simulation est que la transition entre un niveau de détail et un autre peut donner un effet de saut (popping) très gênant. Ceci est dû au fait qu'entre un niveau de détail et un autre, des polygones apparaissent ou disparaissent brusquement.