Simplification de maillages

Objectif			L'objet de départ est une forme 3D représentée par un maillage de triangles. Le maillage de départ est dense et on se propose de le simplifier en supprimant des triangles. Par ailleurs, on garde à l'esprit qu'il peut être intéressant de remonter au maillage initial dense. C'est pour cela que l'on choisit de simplifier en effondrant des arêtes car c'est une méthode assez simplement réversible.

Principe			Pour choisir les arêtes que l'on va effondrer, on définit une énergie de maillage qui est d'autant plus faible que le maillage considéré est proche de l'original. Ensuite on effondre les arêtes qui garde cette énergie la plus faible possible quand on les effondre.

Algorithme			On simule l'effondrement de chaque arête pour déterminer celle qui entraîne la plus faible variation en cas d'effondrement. On effondre ainsi l'arête trouvée. On resimule l'effondrement uniquement pour les arêtes proches de celle qui a été effondrée. On trouve ainsi une nouvelle arête à effondrer et on reprend en (2)

Choix du point			Lors de l'effondrement, il faut choisir la position du point résultat - l'objectif étant toujours de minimiser l'énergie du maillage final. Pour cela, on effectue une descente de gradient à pas constant. Pour améliorer la qualité du résultat, on part de trois points de départ différents: les deux extrémités et le milieu de l'arête.

Energie			La fonction d'énergie que l'on utilise se décompose en deux parties: E_dist = S d²(x_i,S) où les x_i sont les sommets du maillage original, S la surface du maillage simplifié et d(x_i,S) la distance de x_i à S. E_spring = S d²(v_i,v_j) où (v_i,v_j) parcourt tous les couples de sommets du maillage simplifié. E_dist est la partie principale qui tend à rapprocher le maillage résultat du maillage original. E_spring permet d'assurer que le maillage ne présente pas de fortes aspérités.

Résultats obtenus			Le modèle de départ est formé de 5772 facettes. J'ai effectué différents niveaux de simplification (entre crochets le nombre d'effondrements effectués): 5752 [10], 5672 [50], 5572 [100], 5272 [250], 4772 [500], 3772 [1000], 2772 [1500], 772 [2500]. Par ailleurs, j'ai aussi effectué les calculs pour une expression de E_spring différente: j'ai sommé pour chaque point les distances au carré entre lui et chacun de ces ancètres dans la simplification. Voir les images

Bibliographie			Mesh optimization de Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald et Werner Stuetzle Progressive Meshes de Hugues Hoppe