Notre projet s'inscrit dans le Projet Jeunes Chercheurs du GdR ISIS. Son but était de développer des techniques d'analyse multirésolution pour les séquences 3D animées dans le cas de maillages triangulés.
Nous avons divisé notre travail en deux parties.
Cette page web présente l'ensemble de nos travaux.
Nous avons repris l'interface déjà existante qui permettait d'afficher les cas statiques (.off) et nous l'avons améliorée afin qu'elle puisse traiter les fichiers dynamiques (.wrl). Cette interface permet aussi de choisir quel type et combien de subdivisions l'on souhaite appliquer à notre fichier. Afin de travailler sur un cas régulier, l'interface nous permet de créer un tore paramétrable que l'on peut animer. L'interface est composée de 2 parties : à gauche se trouve l’affichage des mesh 3D et à droite se trouve l’onglet de configuration.
Un masque est une matrice dont on peut extraire les stencil pour subdiviser un maillage. Dans le cas d'un maillage composé de quadrilatères, ce masque est une matrice. Dans notre cas, notre maillage est composé de triangles, donc chaque ligne d'une matrice est un peu décalée par rapport à celles du dessus et du dessous.
A partir du masque, pour récupérer les stencils, il faut prendre une valeur sur deux en partant du milieu, puis en partant des valeurs autour du milieu. L'exemple dans le cas spatial devrait bien aider à comprendre le fonctionnement.
Nous avons utilisé le schéma de Loop pour implémenter la subdivision spatiale. C'est une subdivision avec une box-spline à 6 directions et qui nous garantit une continuité C2.
Construction du masque: Pour construire le masque, il faut regarder la box-spline six directions du schéma de Loop. Chaque direction décrit la manière de translater le masque temporaire pour arriver à la version suivante du masque.
Pour implémenter cet algorithme, nous faisons cela en trois étapes :
La deuxième étape ne pose pas de problème particulier car, comme cela peut se voir avec le stencil, nous n'avons besoin que des sommets voisins du sommet sur lequel nous sommes en train de travailler. Un simple VertexVertexIterator d'OpenMesh suffit donc.
En revanche, la première étape était un peu plus difficile à implémenter. En effet, nous travaillons sur les faces, et comme le montre le schéma ci-dessous, lorsque nous travaillons sur la face hachurée en vert, nous avons besoin des coordonnées des points pointés par une flèche bleue pour calculer le nouveau point indiqué par la croix.
Or, OpenMesh ne nous permet pas d'avoir accès directement au point qui ne se trouve pas sur la face. Nous avons donc rajouté deux propriétés aux demi-arêtes :
Les résultats de cet algoritme ont été très concluants, et ce pratiquement immédiatement. Voici une image du tore avant subdivision et une image du tore après subdivision :
|
Pour le schéma temporel pur, nous avons utilisé une box-spline à 4 directions dans le temps. Elle nous permet d'avoir une continuité C2 de même.
Le masque obtenu est le masque [1 4 6 4 1] que nous appliquons à chaque frame.
L'implémentation de cet algoritme n'a posé aucune réelle difficulté, et les tests ont été passés avec succès rapidement.
Ce schéma n'est pas le but de notre projet, mais il est intéressant de noter que le schéma spatio-temporel découplé revient en fait à faire une subdivision purement spatiale suivie d'une subdivision purement temporelle. Nous avons obtenus de très bons résultats, justes et rapides, très rapidement puisque ce n'était que la concaténation de deux algorithmes déjà implémentés et testés.
Ce point était vraiment l'objectif principal de notre projet. Nous devions implémenter le schéma spatio-temporel couplé à une seule direction temporelle, comme ceci :
Cependant, après avoir implémenté ce schéma, nous nous sommes aperçus qu'il ne donnait pas les résultats escomptés. En effet, lors d'une séquence avec un maillage qui ne bouge pas, les anciens points sont influencés par leur voisins dans l'espace alors que les nouveaux points ne le sont pas.
Nous avons donc essayé d'implémenter un schéma spatio-temporel couplé un peu différent, en rajoutant une direction temporelle :
Avec ce schéma, nous avons obtenu le masque suivant :
puis nous en avons déduit les stencils suivants :
a | la nouvelle coordonnée des sommets existants à la frame t |
b | la nouvelle coordonnée des nouveaux sommets à la frame t |
a' | la nouvelle coordonnée des sommets existants à la frame t+1 |
b' | la nouvelle coordonnée des sommets existants à la frame t+1 |
L'implémentation de l'algorithme a été assez rapide là aussi. Mais cette fois ci, les résultats étaient bons.
Il n'y a rien à faire du point de vue temporel, seul le cas spatial doit être revu afin de traiter les sommets irréguliers, c'est-à-dire dont la valence (v) est différente de 6.
Les stencils de Loop modifiés nous ont été donnés :
L'implémentation de cet algoritme n'a pas été très difficile, compte-tenu de la façon dont nous avions implémenté le cas régulier. Les résultats avec un maillage semi-régulier (cheval de Basile Sauvage) sont très bons.
Nous avons appliqué la même méthode que dans le cas découplé, ce qui nous donne les stencils suivants :
L'idée était de généraliser la méthode appliquée dans le cas régulier.
Pour cela, on cherche à trouver alpha et beta de manière à ce que le schéma de subdivision soit convergent et continu.
Nous avons utilisé la méthode de calcul des valeurs propres de la matrice de subdivision dans le domaine de Fourier développé dans l'article de recherche de L. Barthe, C. Gerot, M.A. Sabin and L. Kobbelt intitulé "Simple computation of the eigencomponents of a subdivision matrix in the Fourier domain"
Le point fort de cette méthode est que la taille des blocs de la matrice de subdivision ne dépend plus de la valence du sommet irrégulier, on a donc plus qu'un unique calcul à effectuer pour toutes les valences.
Nous avons donc calculé la transformée de Fourier de la matrice de subdivision et plus précisement le bloc pour la fréquence w=0.On obtient une matrice du type suivant.
On a cherché les valeurs propres dans le cas général mais nous n'avions pas une puissance de calcul suffisante pour obtenir un résultat probant.
Nous avons alors remarqué que dans le cas régulier alpha=2*beta, on a donc imposé alpha=2*beta dans le cas général. Cela nous a permis d'obtenir un résultat très interessant: pour beta = 6/v, on obtient exactement les mêmes valeurs propres que dans le cas régulier. Il est à noter que pour v=6, on retombe bien sur les valeurs d'alpha et beta du cas régulier
L'implémentation nous donne de bons résultats, cette méthode semble être valide.
L'analyse multirésolution consiste à étudier la subdivision afin de pouvoir déterminer les valeurs d'un "ancien" point seulement à partir des nouveaux points . Cela permet ainsi d'avoir une méthode de calcul réversible. Les équations pour le cas spatial pur du schéma de Loop nous ont été fournies. Nous avons du les comprendre et les implémenter dans notre interface. Nous avons de même déterminé les équations réversibles dans le cas temporel pur.
Le cas découplé est simple, il faut alterner le spatial pur et le temporel pur. La seule difficulté est de stocker les détails dans le bon ordre, c'est-à-dire ne pas mélanger les détails spatiaux et les détails temporels (en intervertissant, il est possible de chercher des détails qui n'existent pas).
Le but du projet est néanmoins l'implémentation d'une analyse spatio-temporel couplée. Nous avons cherché à déterminer les équations sans néanmoins arriver à des résultats concluants, ni pour le spatio-temporel à six directions, ni pour le spatio-temporel couplé en rajoutant les deux directions temporelles. Dans chacun des cas, les équations étaient plus compliquées et n'aboutissaient pas.
Avec plus de temps, il aurait fallu creuser les schémas, peut-être changer la modélisation, et essayer avec d'autres stencils (notamment un mélange du couplé et du non couplé).
L'image suivant nous montre bien comment le schéma fonctionne dans le cas spatial pur. Les anciens points et les détails (ici nuls dans la subdivion) sont en entrée. En ressort l'ensemble des nouveaux points. On obtient ainsi les équations suivantes pour coder l'analyse :
Nous avons fait ce choix plutôt qu’un vecteur de vecteur de coordonnées car le nombre de points augmente seulement lors de subdivisions spatiales ou spatio-temporelles et que nous avons jugé plus intéressant de rajouter les nouveaux points après les anciens points.
Les coordonnées se composent des informations (x, y, z) mais aussi du niveau de profondeur du point donné par le champs depth, de son handle donné dans openMesh par le champs v_it (ATTENTION : on ne modifie le handle du point que pour la première frame, il est inintéressant de modifier cette donnée sur toutes les frames)
La structure de l’arbre ne force pas un arbre quaternaire, il est possible d’augmenter ou de diminuer le nombre de nœuds.
Il est possible d’afficher l’arbre complet, ou seulement les faces d’un niveau de profondeur donné.
Les subdivisions inverses ne marchant pas sur les subdivisions couplées, nous avons décidé de prendre comme convention qu’une subdivision couplée correspondait à la succession d’une subdivision spatiale puis temporelle.
Nous avons choisi ce format plutôt qu’une succession de .dat car les faces restant les même au cours de l’animation, il nous semblait que cela serait une perte de mémoire que de dupliquer cette information.
|
Tout d'abord, ce projet nous a permis de connaitre des librairies connues en image. OpenMesh est une librairie qui est fort utile dans les cas simples mais dès que l'on rentre dans des cas plus complexes, elle est beaucoup moins pratique! Nous avons pu par ailleurs découvrir l'outil OpenGL pour visualiser notre surface
Il nous a aussi permis d'appréhender le travail de chercheur: on peut passer beaucoup de temps sur un problème sans pouvoir malheureusement implémenter quoi que ce soit. On peut aussi tomber sur des résultats auxquels on ne s'attendait pas qui nécessite de revoir la théorie sous un autre angle.
Ce projet a été très formateur car il nous a permis à la fois de découvrir de nouveaux outils mais aussi de mener à bien un projet long (1 mois), ce qui nécessite une bonne organisation surtout lorsque l'on est un groupe de 4 personnes.