Sommaire

• Introduction
• La Saillence
• Le triceratops
• Le loup
• Le dragon
• Conclusion

Introduction

L'algorithme de simplification de maillage implémenté est celui de Garland & Heckbert. La qualité globale de la simplification est souvent plutôt bonne, on arrive à préserver la forme général de l'objet.

Cependant on traite de la même manière tous les sommmets du maillage, alors que certains mériteraient d'être préservés plus longtemps car il représente un endroit "sensible" du maillage, c'est à dire que sa suppression entraine une modification importante dans la forme générale de l'objet.

C'est ce que l'on a essayé de faire en ajoutant un critère de salience à nos sommets. Ce critère prend en compte la salience à plusieurs échelles comme il est expliqué dans l'article "Mesh saliency". Il s'agit de mettre en valeur les sommets étant le plus sur des "coins" et des "pics" par rapport à d'autres qui sont situés sur plan par rapport à leurs voisins. Cette mise en valeur se traduit par une augmentation du coût des contractions correspondantes à ces sommets. De cette manière, nous arrivons à préserver plus d'informations importantes quant à la forme générale de l'objet.

Nous allons le voir sur quelques exemples.

La Saillence

Nous allons ici présenter brièvement le critère de saillence utilisé dans notre algorithme.

La valeur de saillence en un sommet dépend de la distance de ses voisins et de leur courbure. Pour plus de précision, nous vous invitons à consulet l'article "Mesh saliency"

Dans l'algorithme de Garland & Heckbert, le coût de la contraction entre deux sommets ne dépend que de ses voisins directs. Prendre en compte le critère de saillence, c'est regarder, en plus des voisins directs, tous les voisins étant "proches" de ce sommet. Pour ce faire, on va comparer les différence de saillence entre plusieurs échelles : on va calculer plusieurs valeurs de saillence en modifiant la valeur de la distance à partir de laquelle un sommet un considéré comme proche.
Pour promouvoir les sommets ayant plus d'importance, on va multiplier par un certain facteur la valeur de la saillence dès qu'elle est supérieur à un certain seuil.

Nous avons mis en argument de notre programme 3 argument relatifs au critère de saillence :

• epsilon : correspond à la distance à partir de laquelle les sommets seront considérés comme voisin à l'échelle la plus petite. Cette valeur, qui doit être comprise entre 0 et 1, correspond à un pourcentage de la diagionale de la bouding box.
  Valeur usuelle : 0.003
  
• lambda : valeur par laquelle on multiplie la saillence quand elle est supérieure à un certain seuil ( strictement supérieur à 1).
  valeur usuelle : 100
  
• alpha : valeur du seuil à partir duquel la saillence est multipliée par lambda. Correpond à un pourcentage du maximum de saillence (compris entre 0 et 1).
  valeur usuelle : 0.8
  

Le triceratops

Ce maillage représente un tricératops. Pour illustrer le prise en compte du caractère de saillence, nous allons afficher les normales aux sommets, cela permet de visualiser la concentration de sommets, c'est à dire l$ où l'on a conservé le plus d'information.

Sur le premier exemple, le tricéraptos est simplifié à 80% uniquement suivant l'algorithme de Garland-Heckbert : les sommets sont répartis de façon relativement homogène sur le maillage, et on reconnait bien la forme globale du dinosaure.

Le deuxième exemple présente quant à lui une simplification à 80% prenant en compte le critère de salience (epsilon = 0.005% et lambda = 100) : ici, on remarque une population de sommets bien plus importante au niveau de la crête et des pattes du tricératops, parties présentant une salience élevée, afin de conserver au mieux les détails du maillage.

Tricératops initial, tricératops simplifié à 80% des sommets avec Garland-Heckbert et tricératops simplifié à 80% des sommets avec le critère de salience.

Le loup

Pour se rendre compte, visuellement, de ce que peut apporter le critère de saillence, nous allons voir ce que l'on obtient sur un maillage de loup. Le maillage de départ contient 7066 sommets pour 13992 faces.

Maillage original

Et comparons ce que l'on obtient en utilisant l'algorithme de Garland & Heckbert original et ce que l'on obtient en ajoutant le critère de saillience :

loup simplifié à 90% sans saillence

loup simplifié à 90% avec saillence

On voit bien que sur les secondes images que la gueule du loup (surtout au niveau des crocs) est mieux définie dans le cas de la saillence. De plus, la forme générale de l'animal est également bien conservée.

Cependant, il est difficile de choisir arbitrairement quels paramètre utiliser pour un maillage. En effet, suivant la géométrie de l'objet, on peut trop favoriser les zones localement "pointues" au dépend de la forme globale de l'objet, ou au contraire de ne pas en tenir assez compte (c'est ce qui arrive quand on supprime trop de sommets).

Le dragon

Nous allons faire le même travaile, mais ce coup ci avec un maillage de dragon plus important : 50184 sommets pour 100400 faces.

Maillage original

Et comparons ce que l'on obtient en utilisant l'algorithme de Garland & Heckbert original et ce que l'on obtient en ajoutant le critère de saillience :

dragon simplifié à 95% sans saillence

dragon simplifié à 95% avec saillence

Encore une fois, on observe une meilleure conservation des détails ( surtout remarquable au niveau des dents), tout en conservant la forme globale de l'objet.

Conclusion

Si simplifier à l'aide d'un critère de salience permet à quantité d'information égale, d'avoir beaucoup plus de detail sur un modèle, les performances en souffre un peu. En effet, avant d'effectuer la contraction des sommets, on doit effectuer une étape de prétraitement durant laquelle on calcule la saillence en chaque sommet, et pour cela, il faut parcours tous les voisins de tous les sommets. Par exemple pour le loup (7066 sommet), cela prend 4.5 secondes alors qu'avec le dragon (50 184 sommets), on atteint 1 min 45 sec. Pour un maillage de 237 000 sommets, le temps de calcul atteint les 4 minutes.
Ceci dit, L'algorithme tel que nous l'on avons écrit n'est pas peut être pas optimisé à fond, de plus l'utilisation de multithreading permettrait de gagner en performance.

Néanmoins, pour des maillages importants, l'utilisation du critère de saillence pour applications temps réel est inenvisageable. De plus, les paramètres ne sont pas exactement les mêmes suivant ce que l'on cherche à obtenir et suivant les caractéristiques du maillage (taille, densité de point, ...), et la vitesse d'execution peut dépendre de ces paramètres (puis on a de voisins à visiter, plus cela prend de temps).