A Survey of Polygonal Simplification Algorithms

by David Luebke


University of Virginia - Department of Computer Science


Résumé de l'article original de D.Luebke.



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 :

Classification des algorithmes

On recense 4 mécanismes principaux de simplification : 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 !) :
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.
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. 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. 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. 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. 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. 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'. 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. 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 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.

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.