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)
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
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)
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.
Contact : Vincent Caron <vincent _at_ zerodeux.net>