Conversion d'un maillage animé en modèle animé par squelette

Guillaume Royer, Raphaël Goujet, Simon Rousseau

Introduction

Le but de notre projet était d'écrire un programme permettant la conversion automatique d'un maillage animé en un modèle animé par squelette. Notre travail s'est basé sur l'article de recherche Automatic Conversion of Mesh Animations into Skeleton-based Animations, de Edilson de Aguiar, Christian Theobalt, Sebastian Thrun et Hans-Peter Seidel.

Ce type de conversion présente un intérêt indéniable dans l'animation 3D. En effet, une fois le squelette obtenu, il suffit de le mettre dans une position donnée pour que le maillage soit recalculé automatiquement autour de cette position. Traditionnellement, le squelette d'animation est construit à la main, donc son obtention automatique constitue un gain de temps considérable.

L'algorithme que nous avons eu à implémenter se décompose en cinq étapes :

Réalisation de l'interface

L'implémentation de l'interface proprement dite s'est faite en utilisant la librairie Qt. Nous avons d'abord réalisé un travail commun avec les autres groupes du projet image pour le chargement des fichiers .WRL, la lecture et l'affichage de l'animation. L'interface est gérée grâce à Viewer et la librairie QGLViewer.

La seconde partie de l'implémentation s'est faite tout au long du projet. Une première grosse modification a été la fusion entre notre interface d'animation et l'interface d'un groupe de l'année dernière travaillant sur l'algorithme Varshape Approach. Cet algorithme étant en partie le point de départ du nôtre, nous reviendrons plus tard sur les modifications que nous avons apportées à celui-ci au delà de cet aspect de fusion d'interface. Nous avons donc réussi à faire fonctionner leurs algorithmes sur des fichiers .WRL en entrée en réalisant la fonction LoadWRL qui forme un fichier .OFF du mesh à t=0 de l'animation. Leurs algorithmes sont donc appliqués sur le mesh à t=0.
La dernière partie de l'implémentation de l'interface a été d'ajouter l'accès à nos algorithmes pour le WRL chargé. Ajoutant ces fonctions à chaque avancée de notre projet, le point suivant aurait été de gérer l'affichage d'un squelette.

Présentation de notre algorithme

Segmentation

Cette première partie consistait à découper le maillage animé en k parties approximativement rigides.

Pour déterminer les k clusters, il faut utiliser l points prélevés dans le mesh. Ces l points représentent le "centre" des régions obtenues par l'algorithme Varshape Approximation à un temps de référence t=0. Nous avons pu réaliser cette étape en intégrant le projet de Damien Rumiano et Emile de Weerd puis en utilisant leur algorithme. Cependant, au delà de la compréhension de leur algorithme, nous avons dû ajouter des méthodes et des structures de données pour prélever les informations qui nous sont utiles en sortie de leur algorithme.

Une fois les coordonées des l points prélevées pour t=0, il a fallu récupérer les coordonnées de ces points pour chaque frame en parcourant méthodiquement le fichier .WRL.

Pour résumer cette étape, on échantillone l points du mesh et à chaque triangle est affectée une zone à l'aide du Varshape Approximation. L'étape suivante permet de réunir ces l zones en k clusters cinématiquement rigide.

Nous avons donc implémenté une fonction qui prenait un nuage de points animés, et qui retournait la répartition des points entre les différents clusters. Pour cela, nous nous sommes appuyés sur un article de Ng, Jordan et Weiss intitulé On Spectral Clustering: Analysis and an algorithm. L'algorithme en question s'appuyait sur la méthode des k-means, appliquée à des points en dimension k obtenus après diverses transformations de la matrice d'affinité du nuage de points. L'algorithme concernait un nuage de points statique : c'est pourquoi nous avons eu à le modifier pour pouvoir l'appliquer à un nuage de points animé. Ainsi, il a fallu générer une matrice d'affinité différente, qui prenait en compte l'évolution des points, les moyennes et écarts-types de leurs distances mutuelles au cours du temps.

Topologie

Nous parcourons pour déterminer l'adjacence des clusters les triangles du mesh puis nous regardons leur cluster et ceux de leurs voisins. S'il y'a une différence, les deux clusters en questions sont considérés comme voisins et les sommets du triangle sont ajoutés à la frontière entre les deux clusters. On calcule le barycentre de ces points pour déterminer l'articulation barycentrique qui est une première approximation des articulations retenues pour le squelette. Nous n'avons pas limité le nombre de clusters voisins possibles. En effet, dans la publication, il est question d'une heuristique visant à limiter les clusters voisins à deux pour le calcul des articulations.On a procédé différement en utilisant tous les voisins et en reportant le problème au calcul des articulations. En effet, on a observé que par exemple, dans le cas d'un personnage animé, le torse est cinématiquement articulé avec la tête et les deux bras. Nous n'avons donc pas voulu nous limiter à l'heuristique qui peut cependant améliorer le temps de calcul.

Articulations

Dans cette partie, on récupère en entrée les points échantillonnés et leur position au cours du temps. Ensuite, on calcule les matrices de transformation Mi,tr->t. Ces matrices permettent de calculer la position du cluster i au temps t, à partir de la position du cluster i au temps tr, c'est-à-dire que

Mi,tr->tpi,tr,n = pi,t,n

où pi,t,n est la position du ne point du ie cluster au temps t. Les matrices permettent de ramener les deux clusters (dont on veut étudier l'articulation qui les lie) à la position-référence d'un des deux clusters, afin de n'avoir comme inconnue à déterminer qu'une seule position (x,y,z) (au lieu d'une séquence de positions).

Une fois ces matrices obtenues, on minimise une formule spécialement élaborée pour ce problème par les auteurs de l'article. L'argument réalisant le minimum est la position de l'articulation que l'on étudie. Pour obtenir la position de l'articulation au cours du temps, il suffit de multiplier le résultat de la minimisation par .5*(Mi,tr->t+Mj,tr->t) où i et j sont les numéros des segments reliés par cette articulation. On obtient alors la position au cours du temps de toutes les articulations entre clusters contigus. Cependant, deux zones contiguës n'ont parfois pas besoin d'une articulation entre elles, car cela n'a pas de réalité cinématique.

Pour résoudre ce problème, nous n'avons pas suivi l'heuristique proposée car elle n'est pas efficace pour les clusters ayant plus de deux clusters cinématiquement voisins. Nous avons suivi une autre méthode proposée dans une publication citée dans l'article : élaborer un graphe des articulations et des clusters, et en extraire l'arbre couvrant de poids minimal (Automatic Learning of Articulated Skeletons from 3D Markers Trajectories de Edilson De Aguiar, Christian Theobalt et Hans-Peter Seidel, 2006). Cela permet de bâtir la hiérarchie des articulations et des os, utile pour la partie suivante.

Os

À ce stade de l'algorithme, on a obtenu les points d'articulation, mais les os qui les relient ne sont pas de longueurs constantes au cours du temps. C'est dû au fait que les parties rigides du maillage ne le sont qu'approximativement. Afin d'imposer à chaque os une longueur fixe, nous avons parcouru les articulations les unes à la suite des autres, en calculant à chaque fois la longueur optimale de l'os adjacent. La longueur optimale était obtenue en minimisant une fonction qui cumulait les écarts entre les longueurs d'os, et entre les positions des articulations. On obtient alors le squelette final, aux os de longueurs fixes.

Il s'agit ensuite de recréer l'animation, mais sous forme de modèle animé par squelette. Nous n'avons pas eu le temps d'implémenter cette fonction. Il s'agissait de définir une position de référence pour le squelette, et, pour chaque position, de calculer les angles d'Euler des rotations aux articulations à l'aide de l'algorithme CCD décrit dans l'article Multi-dimensional input techniques and articulated figure positioning by multiple constraints de Badler, Manoochehri et Baraff (1987).

Poids de skinning

Dans cette partie, que nous n'avons pas eu le temps d'implémenter, on attribue, pour chaque point du mesh, des "poids de skinning" c'est-à-dire que l'on calcule la dépendance de chaque point vis-à-vis des os voisins pour la déformation pendant l'animation. Ce calcul se fait via la résolution d'une équation de la chaleur, décrite dans l'article Discrete Laplacian Operators: No Free Lunch de Wardetzky, Mathur, Kaelberer et Grinspun (2007). Nous pensons que cela n'aurait pas été la partie du programme la plus difficile à implémenter, étant donné le nombre de publications à ce sujet. Ensuite il aurait fallu concevoir une fonction animant le mesh à l'aide du squelette en utilisant les paramètres d'animation calculés dans la partie "Os" et les poids de skinning. La documentation pour cette partie est tout aussi abondante, et l'implémentation aurait ainsi été sans difficultés. Les problèmes à résoudre auraient plutôt concerné les petits bugs à corriger (certainement ardus à débusquer), et l'optimisation du temps de calcul.

Résultats obtenus

Nous observons l'ensemble des résultats avec le dauphin animé. La première étape que l'on observe est l'application du VSA sur t=0. On demande en nombre de régions 1% du nombre de sommets.

On applique ensuite l'application des clusters : les régions se regroupent par régions rigides dans l'animation. (ici avec k=4 clusters)

Nous avons pu ensuite observé à l'aide de messages de debuggage que le tableau de booleans stockant l'adjacence des clusters et le tableau des articulations barycentriques semblent corrects. Le reste n'a pas pu être observé à cause de notre problème avec les librairies.

Analyse critique

Problèmes rencontrés

Nos trois principales difficultés ont été les suivantes :

Comprendre l'article et les articles cités

Le problème était que les articles cités étaient nombreux, faisant eux-mêmes référence à d'autres articles. Pour pouvoir commencer à implémenter, il fallait imaginer une structure de données adaptée, et cela aussi a pris du temps, car il fallait pouvoir extraire ces données des fichiers VRML.

Comprendre, faire marcher et modifier l'implémentation de l'algorithme VSA de 2007, ainsi que l'interface, OpenMesh, QT, et QGLViewer pour pouvoir faire marcher le programme final sur ensipsys et nos pc personnels

Cela a occupé plus d'une semaine, du fait de problèmes d'installation à répétition. Les libraires n'étaient pas simples à installer, et comme nous n'avions pas assez d'expérience en Linux cela ne nous a pas facilité la tâche.

Intégrer des librairies extérieures comme NewMat (de Robert Davies), levmar (de Manolis Lourakis) et graph (dans les librairies boost)

C'est le principal problème rencontré en fin de projet. Nous avons dû procéder par tâtonnement, et passer en fin de compte plus de temps à essayer de faire marcher ces librairies extérieures plutôt qu'à implémenter/déboguer l'algorithme. Cela nous a vraiment beaucoup ralentis.

Pistes pour l'amélioration

Rendre le code plus robuste

C'est-à-dire intégrer une gestion des erreurs approfondie, que ce soit pour les inversions de matrices, ou le manque de points dans les clusters (source d'erreurs dynamiques).

Intégrer les librairies extérieures

C'est le principal point bloquant, une grande partie du code, la plus intéressante, n'a pas pu être testée à cause de cela. Les essais/erreurs d'inclusion de librairies étaient vraiment fastidieux.

Tester les différentes variantes dans le code

De nombreux paramètres sont à notre disposition pour améliorer le programme : options d'optimisation dans les librairies extérieures, variantes locales dans le code comme l'utilisation des articulations barycentriques ou les moyennes de matrices.

Tester la valeur de différents paramètres comme K (nombre de clusters)

Et même à long terme rajouter le calcul de K optimal comme suggéré, dans l'algorithme des K-means lui-même.

Bilan du projet

Notre principal regret est de n'avoir pas pu nous concentrer sur les points essentiels de l'algorithme à cause de problèmes extérieurs. Alors que nous abordions la partie centrale du programme, que les résultats les plus intéressants allaient pouvoir être obtenus, nous avons été confrontés à des problèmes sans fin d'intégration de librairies.

Mais les points positifs, au bout de ces 4 semaines, sont nombreux : nous avons appris des points plus fins de C++ (comme le passage de pointeur de fonction en paramètre), nous avons amélioré notre connaissance de Linux, nous avons appris à nous immerger rapidement dans du code inconnu, et enfin nous avons découvert QT et OpenMesh. Nous avons aussi appris à travailler en groupe en autonomie, à gérer les problèmes de toutes sortes en répartissant le travail le plus efficacement possible en gardant un oeil sur les ressources disponibles (temporelles, informatiques, humaines).