Simplification à niveaux de détails continus

Principe

Pour résoudre ce problème de transition brutale entre les différents niveaux de détails, une autre classe de méthode est apparue. Le principe est non plus de générer séparément des maillages, mais de créer une structure générant au vol un maillage adapté au niveau de détail que l'on souhaite. Une telle structure est dite à niveaux de détails continus. (CLOD, ''Continuous Level Of Detail''). La totalité des méthodes que nous présentons ici utilisent le principe de réduction des arêtes pour simplifier le maillage. Elles diffèrent sur le choix des arêtes à réduire, ou le moment de le faire. La réduction d'arête, et son dual la séparation de sommet, sont présentés sur la figure 1.3.

Figure 1.3: Réduction d'arête et séparation de sommets

Méthodes existantes

La technique de simplification avec préservation de l'apparence [COM98] peut être vue comme une extension de la méthode de simplification par enveloppe. Au lieu de simplement contraindre la déviation de la surface à un intervalle donné, la déviation (erreur) maximale est basée sur plusieurs critères visuels de la surface simplifiée : la variation de la position de sa surface, la variation de sa couleur et la variation de sa courbure. La variation de couleur correspond aux distorsions induites entre une texture plaquée sur le maillage originel et la même texture plaquée sur le maillage simplifié^1.3. La variation de courbure correspond à la perte de détails géométriques. Afin de minimiser la variation de ces deux derniers paramètres lors de la simplification, la couleur et la courbure du maillage originel sont enregistrées dans des textures utilisées par la suite pour atténuer l'erreur visuelle de la simplification. La courbure est représentée par l'ensemble des normales à la surface.

Finalement, le processus de simplification consiste à créer un maillage simplifié par réduction d'arêtes et à plaquer la texture de couleur et de normales sur celui-ci afin de minimiser les erreurs visuelles commises^1.4. Le choix des arêtes à réduire est fait de façon à rester dans les limites autorisées.

Cette technique donne de très bon résultats visuels (figure 1.4) car le placage de la carte de normales redonne un aspect de relief saisissant (Cf. section 1.4.1.2 sur le Bump-Mapping). Cette méthode est employée actuellement dans divers moteurs de rendu en temps réel commerciaux et les toutes dernières cartes graphiques disposent de fonctionnalités dédiées à la compression de cartes de normales (ATI), spécialement utilisées dans le cas de la simplification de modèles géométriques.

Figure 1.4: Simplification avec préservation de l'apparence ([COM98]).

[Le modèle original][Le modèle simplifié][Le modèle simplifié sur lequel est plaqué une texture représentant le relief du modèle original]

Néanmoins, cette méthode ne permet pas une très grande simplification du modèle, car l'estimation d'erreur basée sur des critères visuels est très contraignante.

Garland et Heckbert [GH97] proposent une autre approche utilisant la réduction d'arêtes. Dans cette méthode, les sommets non reliés par une arête peuvent être regroupés : ils doivent se situer à une distance fixée par l'utilisateur. Parmi les paires de sommets candidates au regroupement, le choix est fait par rapport à un seuil d'erreur : le regroupement minimisant cette erreur est choisi. L'opération est effectuée itérativement jusqu'à ce que plus aucune paire de sommets ne soit regroupable. L'erreur commise lors d'un regroupement de sommets est évaluée selon un critère nommé Métrique d'Erreur Quadrique (Quadric Error Metric) qui représente la distance entre un sommet et l'ensemble de ses faces adjacentes, le tout codé dans une matrice 4x4. Cette métrique est également utilisée pour positionner le nouveau point sur l'arête en minimisant l'erreur.

Les résultats obtenus avec cette méthode sont rapides et robustes car le maillage ne nécessite pas d'être topologiquement correct. De plus, cet algorithme donne de très bons résultats lors d'une très grande la simplification. Erikson et Manocha [EM99] améliorent encore les performances de l'algorithme en terme de temps de calcul et de préservation des attributs des sommets (coordonnées de texture, normale et couleur).

Lindstrom et Turk [LT00] proposent encore une autre approche pour calculer et minimiser l'erreur commise lors de la simplification. Ils analysent l'image obtenue lors d'une simplification par réduction d'arête avec l'image du modèle originel. Ils effectuent pour cela la simplification à un niveau de détail donné, puis comparent le résultat selon un nombre fixé de points de vues positionnés autour du modèle. Les images sont comparées en termes de luminance par rapport à l'image du modèle originel. D'une autre façon, on peut dire qu'ils évaluent l'impact visuel qu'une réduction d'arête peut avoir sur l'image. C'est idéalement la meilleure façon de procéder, mais le temps de calcul est énorme, bien que les résultats obtenus soient très bons.

Les maillages progressifs (Progressive Meshes) de Hoppe [Hop96] procèdent également par réduction d'arête mais généralisent le processus de plusieurs façons. Le choix des arêtes à réduire est basé sur l'évaluation d'une fonction d'énergie à minimiser. Par ailleurs, il enregistre dans une structure de données adaptée les opérations de réduction de façon à ce que l'opération inverse de création de sommet puisse s'effectuer avec la même fonction. De plus, il guide l'évaluation de cette fonction sur les attributs du maillage, qu'il sépare en deux catégories : les attributs discrets (indice du matériau, identifiant de texture) et continus (position, coordonnées de texture, normale). Ainsi, la simplification s'adapte aux caractéristiques du maillage et plus uniquement à une erreur géométrique.

La rapidité du calcul est telle que l'algorithme peut être utilisé en temps réel directement ^1.5. De plus, la simplification adaptée aux attributs du maillage de façon unifiée donne de très bon résultats : la silhouette et l'apparence générale sont préservées. Néanmoins, comme tous les algorithmes respectant la topologie du modèle originel, les grosses simplifications ne sont pas possibles : les trous restent et jamais deux parties du modèle ne fusionnent.

Avantages

Les avantages de la simplification continue de maillage sont donc en premier lieu que les problèmes de saut entre niveaux de détails disparaissent. De plus, il n'est pas nécessaire de stocker en mémoire les différents maillages car ils sont générés au vol directement.

Inconvénients

Néanmoins ces algorithmes demandent dans l'ensemble beaucoup de temps de calcul. Même les Maillages Progressifs de Hoppe qui sont très rapides à calculer ne sont guère employés encore car dans un environnement virtuel ce n'est pas un seul modèle qui doit être simplifié mais souvent des dizaines en même temps. Dans ce cadre, les maillages statiques sont toujours utilisés car la vitesse de l'application prime sur l'espace mémoire demandé.

Un autre problème dont souffrent ces méthodes est leur inadéquation avec un environnement virtuel complet : elles ne simplifient qu'un modèle isolément alors que l'on imagine aisément que des groupes d'objets vus de loin pourraient se ramener à un seul maillage simplifié.