Simplification Out-of-Core des

modèles polygonales complexes

KRAEMER Petra

SERROUKH Youssef

TATUT Georgiana-Alina

Encadré par : REUTER Patrick

Maillage

Approximation par morceaux par l’assemblage de facettes

Modèle polygonal décrit par les coordonnées 3D Stockage du maillage

Soupe de polygones Polygones indexés

Motivation

Informations à différentes résolutions Oversampling Traitement plus rapide du maillage (rendu,

compression, analyse de la surface) Modèle trop grand pour l’affichage, traitement,

transmission et stockage en mémoire central

Solution : Out-of-Core Simplification

Caractéristiques d’un algorithme de simplification Préservation de la topologie Gestion d’une soupe de polygones Coût de mémoire Facilité d’implémentation et d’utilisation Encodage Transition continue Utilisation dépendante du point de vue Prise en compte des attributs Orienté erreur ou budget

Algorithme de Lindstrom

Hybride : clustering de sommets avec erreur quadratique clustering de sommets (Rossignac et Borrel ’93) erreur quadrique (Garland et Heckbert ’97)

Algorithme OoCS

1. pour chaque triangle t Є Tin {

2. on calcule les coordonnées de chaque sommet

3. définir une table de hachage dynamique de clusters

4. pour chaque sommet vin de t

5. définir une clé de hachage

6. si pour un cluster donné on a pas de représentant

7. créer un nouveau sommet vout

8. sa matrice quadrique est initialisée à zero

Suite Algorithme OoCS

9. si aux moins 2 sommets de t Є un même cluster10. t est réduit à une arête ou à un point et mit à l’écart11. sinon 12. Vout += vt

13. Tout += t14. calculer la matrice quadrique Qt de t15. pour chaque sommet de t16. Qv += Qt

17. }18. pour chaque cluster V19. calculer les coordonnées du sommet représentatif 20. retourner (Vout ,Tout ) dans un format approprié

Clustering des sommets

Rossignac et Borrel : 1993 introduction de l’idée de simplification par Clustering.

• Le modèle est au préalable triangulé.• L’utilisation d’une grille régulière.• Pour chaque sommet un poids est attribué.• Le sommet de représentation:

• La somme pondérée des sommets (lisse la surface) • Le sommet de poids maximal (élimine les détails)

Exemple de clustering de sommets

Quadrique (1)

Chaque cluster associé un seul sommet dit « représentatif » qui appartiendra au maillage simplifié

Problématique comment déterminer la position du sommet « représentatif » afin de minimiser l’erreur introduite par le processus de simplification

Solution utiliser une quadrique (Garland et Heckbert)

Quadrique (2) Chaque cluster matrice quadrique associée Qc Triangle en train d’être traité quadrique

Q associée:

n - vecteur de dimension 4 compose de la normale au plan défini par le triangle et le produit scalaire de ses trois sommets

Remarque: la matrice Q décomposée:

Cluster de chaque sommet repartition de Q : Qc = Qc + Q

Position sommet «représentatif»

Trouver la position du sommet équivalent a résoudre

le système linéaire

x - la position optimale du sommet «représentatif»

Si x dehors du cluster ramené à l’intérieur

En fait : x minimise la somme des carrés des volumes des tétraèdres formes par x et les triangles à l’intérieur du cluster

Tests et résultats (1)

Original Buddha 1,087,716 triangles

OoCS 204,750 triangles

OoCS 62,354 triangles

Tests et résultats (2)

Original dragon871,306 triangles

OoCS/Quadrics47,228 triangles

OoCS/Vertex grading47,228 triangles

OoCS/Vertex mean47,228 triangles

Tests et résultats (3)

Original statue 386,488,573 triangles

OoCS3,122,226 triangles

Tests et résultats (4)

Conclusion

Algorithme rapide : O(n) On a pas besoin d’espace mémoire

important Représentation du modèle d’entrée

comme soupe de polygones Facile à implémenter

Références Out-of-Core Simplification of Large Polygonal Models.

Lindstrom, SIGGRAPH 2000. Surface Simplification using Quadric Error Metrics.

Garland and Heckbert, SIGGRAPH 1997. Fast and Memory Efficient Polygonal Simplification.

Lindstrom and Turk, IEEE 1998. Geometric Simplification and compression.

Rossignac, SIGGRAPH 1997. Pré-traitement de grosses données pour la

visualisation interactive. Décoret, Thèse 1992.