Introduction

Les modèles polygonaux sont actuellement prédominants dans le domaine de la 3D temps réel, et ce pour plusieurs raisons : leur simplicité mathématique facilite les traitements, le matériel permettant un rendu accéléré est largement disponible, et la plupart des modèles utilisés en CAD (splines, surfaces implicites ...) sont réductibles à un modèle polygonal. Mais dans la plupart des cas, la complexité intrinsèque de la scène empêche un rendu interactif. Plusieurs solutions :

• augmenter les détails visuels au niveau de chaque polygone (Gouraud, texture mapping, ...)
• repérer rapidement de larges parties cachées du modèle
• simplifier la complexité polygonale du modèle tout en garantissant une qualité minimale de rendu. C'est le sujet de cet article !

Classification des algorithmes

On recense 4 mécanismes principaux de simplification :

• Echantillonnage : (sampling) on commence par ré-échantilloner le modèle soit en choisissant des points sur sa surface, soit en superimposant une grille 3D de voxels. La qualité de sortie de l'algorithme est controlé par la densité d'échantillonnage.
• Subdivision adaptative : on établit d'abord un modèle fortement simplifié (en utilisant récursivement une des 4 méthodes cités ici !), puis on divise itérativement les polygones jusqu'à ce que l'on se rapproche du modèle original selon un critère choisi. Cette méthode est principalement utilisé pour les terrains, ou le modèle simplifié est simple à établir, et la méthode de subdivision permet d'augmenter la densité de polygones seulement autour de pics ou de détails anguleux.
• Décimation : chaque étape de l'algorithme retire un sommet ou un polygone du modèle, et retriangule les trous obtenus à chaque itération.
• Fusion de sommets : (vertex merging) cette méthode fusionne deux sommets voisins en un seul, et ce récursivement. On utilise classiquement la méthode dite du edge collapse qui ne fusionne que deux sommets possédant une arête en commun.

Chaque méthode a ses avantages et inconvénients, bien entendu. On utilise trois critères pratiques pour faire son choix parmis ses 4 méthodes (et leur descendance !) :

• View-dependent vs. view-independent : l'approche traditionnelle du LOD (Level Of Detail, type view-independent) consiste à précalculer des avatars simplifiés du modèle original, puis de sélectionner un avatar lors du rendu, en se basant par exemple sur la distance. Une conception plus moderne du problème consiste à évaluer en permanence un modèle simplifié qui satisfasse des critères de qualité de rendu (on tiendra donc compte de la projection et des techniques de rendu).
• Métrique : on utilise couramment deux critères pour mesurer le dégré de simplification d'un algorithme. On fixe soit un degré de fidélité (distance entre les surfaces du modèle original et simplifié par ex.), soit un 'budget de polygones' (naturel pour les méthodes de décimation). Une bonne méthode de simplification permet d'utiliser les deux métriques simultanément.
• Préservation de la topologie : un algorithme qui préserve la topologie du modèle original a souvent l'interêt de fournir une simplification de bonne qualité (trous et excroissances conservées, etc) mais suppose précisément que le modèle original soit topologiquement correct, ce qui est rarement le cas dans le cadre de la visualisation interactive ! Les algorithmes irrespectueux envers la topoligie (principalement locale) fournissent toutefois une sortie de qualité médiocre, mais souvent satisfaisante en première approche.

Catalogue des algorithmes

Une liste rapide de 10 méthodes recensées en 1997, avec leurs points forts et leurs points faibles. Pour une justification et une étude des méthodes, suivre les références... Il m'est difficile ici de faire plus synthétique à propos d'un survey !


1. Décimation de modèles triangulés (Decimation of Triangle Meshes)

Schroeder, Zarge, Lorenson [Schroeder 92]

Cet algorithme est classiquement utilisé en sortie du fameux marching cubes afin d'éliminer la surabondance de détails géométriques. Il procède en plusieurs passes, en considérant à chaque itération la suppression de sommets en fonction de la conservation de la topologie locale (changement de courbure par ex.) et d'une distance entre le modèle original et le modèle optimisé. Chaque trou obtenu par extraction de sommets (et de leurs triangles associés) sont retriangulés.

• Intérêt : simple, utilise un sous-ensemble des sommets originaux (réutilisation possible des normales, etc ...)
• Inconvénient(s) : ...

2. Ré-échantillonnage de surfaces polygonales (Re-Tiling Polygonal Surfaces)

Turk [Turk 92]

Cette méthode combine les mécanismes de ré-échantillonnage et de décimation. Un nombre de points choisis est distibué sur la surface, puis réparti de manière 'homogènes' en simulant une force de répulsion et en cherchant la stabilité du système. Ensuite la technique de mutual tesselation est appliquée pour obtenir un modèle utilisant à la fois les sommets du modèle original et les nouveaux sommets répartis sur la surface. Enfin, une décimation est appliquée pour obtenir le résultat de la qualité voulue.

• Intérêt : qualité du résultat (topologie, aspect), contrôle du niveau de détail
• Inconvénient(s) : temps de calcul !

3. Approximations 3D multi-résolution (Multi-Resolution 3D Approximations for Rendering Complex Scenes)
Rossignac, Borrel [Rossignac 92]

On assigne tout d'abord un 'poids' à chaque sommet, en se basant par exemple sur la courbure locale et la surface des triangles avoisinants. On superpose ensuite une grille tridimensionnelle, puis on élit un sommet par cube unité, en comparant les poids des concurrents. Il suffit d'ajuster la taille de la maille de grille pour sélectionner une résolution de sortie.

• Intérêt : robuste et rapide
• Inconvénient(s) : irrespectueux de la topologie, dépend de l'orientation du modèle, critères de fidélité et de budget innaplicables

4. Clustering (Model Simplification Using Vertex Clustering)

Low, Tan [Low 97]

Cette méthode est dérivée de celle de Rossignac-Borrel. La grille 3D est remplacée par des voisinages (cubes) placés sur les sommets les plus importants. Les paramètres de contrôles sont alors le nombre de 'sommets importants' élus et la taille de l'arête du voisinage.

• Intérêt : moins sensible à l'orientation que R.-B.
• Inconvénient(s) : idem R.-B.

5. Simplification dynamique hiérarchique (H.D.S.)

Luebke, Erikson [Luebke 97]

Une méthode view-dependent basée sur la décimation. Une méthode de décimation est appliquée, et chaque extraction de sommet est représentée dans un arbre de sommets. On obtient une représentation hiérarchique du modèle. Cette méthode exploite également la cohérence temporelle du rendu, en détectant les triangles à retirer ou ajouter entre chaque image, afin d'accélérer le calcul du maillage.

• Intérêt : critères de qualité de rendu, budget de polygone et qualité de modèles applicables
• Inconvénient(s) : ... (c'est la méthode de l'auteur :) !)

6. Simplification par voxelisation (Voxel-based Object Simplification)

He, Hong, Kaufman, Varschney, Wang [He 95]

On ré-échantillonne le modèle en voxels, on applique un filtre passe-bas (FFT 3D), puis on re-triangule à l'aide des marching cubes suivi d'une décimation.

• Intérêt : topologie conservée
• Inconvénient(s) : détails émoussés, temps de calculs prohibitifs

7. Simplification par enveloppes (Simplifications Envelopes)

Cohen, Varschney, Manocha, Turk, Weber, Agrawal, Brooks, Wright [Cohen 96]

On crée deux enveloppes surfaciques du modèle en déplaçant légèrement les sommets selon les normales. On applique ensuite une méthode de décimation qui a pour critère de contraindre la surface résultant entre les surfaces 'intérieure' et 'extérieure'.

• Intérêt : conservation de la topologie, critère de qualité applicable
• Inconvénient(s) : calculs des critères complexes et couteux

8. Optimisation du maillage (Mesh Optimization)

Hoppe, DeRose, Duchamp, McDonald, Stuetzle [Hoppe 93]

On sur-échantillonne tout d'abord le modèle pour évaluer la déviation au cours de la simplification. On soumet un ensemble de sommets à la suppression (critères de courbure locale, etc) puis de manière globale on évalue une fonction d'énergie garante de la qualité et la cohésion du modèle. Si l'énergie n'est pas augmentée, on supprime effectivement les sommets.

• Intérêt : grande qualité du modèle résultant, critères de simplification fins, budget de polygones applicables
• Inconvénient(s) : complexe à implémenter, relativement couteux

9. Maillage progressif (Progressive Meshes)

Hoppe [Hoppe 97]

Un modèle 'progressif' est constitué d'un modèle de base (obtenu par décimation), et d'un historique des fusions de sommets utilisées lors de la décimation. En choisissant un point dans l'historique on peut choisir la résolution de modèle de sortie

• Intérêt : streaming de données géométriques, LOD continu, rapidité
• Inconvénient(s) : ...

10. Analyse multi-résolution (Multiresolution Analysis of Arbitrary Meshes)

Eck, DeRose, Duchamp, Hoppe, Lounsbery, Stuetzle [Eck 95]

Le modèle est de type 'maillage progressif', le modèle de base étant obtenu cette fois par une méthode plus complexe : on fait grossir des zones de Voronoï de manière itérative autour du maillage original, puis on re-triangule par Delaunay.

• Intérêt : stricte conservation de la topologie
• Inconvénient(s) : requiert une topologie stricte ! Complexe ...

Conclusion

La tendance des algorithmes est l'optimisation de rendu, et notamment par la méthode du edge collapse, efficace et simple. La métrique constitue le critère le moins bien défini : le respect de la topolgie, et surtout la notion de qualité de rendu (liée aux technologies actuelles et à celle de notre oeil !) reste à préciser. Les aspects les plus prometteurs semblent être ceux de la 'compression de maillage' et de la transmission progressive d'information 3D.