Projet image 2012 : Déformation interactive d'animations 3D

De Ensiwiki
Aller à : navigation, rechercher


Project schedule.png
Titre du projet Projet Image 2012 : Déformation interactive d'animations 3D
Cadre Projets de spécialité
Page principale Projets de spécialité image

Encadrants Franck Hetroy


L'équipe

Alex Grandjean (MMIS-IRVM)

Michaël Guirao (ISI-AST)

Sabine Notheisen (MMIS-IRVM)

Gabriel Simi (MMIS-IRVM)


Présentation du sujet

Contexte

Ce sujet s’inspire du travail effectué par les chercheurs de Pixar dans le domaine de l’animation de maillages 3D [1]. Les personnages étudiés sont représentés par des maillages constitués au minimum d'environ 10000 points. L'animation de ces personnages peut être très coûteuse en terme de calculs. C'est pourquoi on cherche différentes méthodes pour améliorer l'animation des personnages en 3D.

ChatNerv.png

Idée

On s’intéresse ici à une technique d’animation de personnages consistant à plonger le personnage à animer dans une cage, définie comme un maillage plus grossier, donc plus simple et par conséquent moins coûteux en terme de calculs. On relie les points du personnage à ceux de la cage, afin que le déplacement de la cage implique le déplacement du personnage. On s’intéresse ici à étendre cette méthode aux animations, c’est-à-dire que nous ne considérons plus uniquement des modifications spatiales, mais également temporelles. On utilise l’opérateur d’Alembertien pour définir une cage sur chaque frame de l’animation. La modification d’une cage sur une frame entraînera alors la modification sur les cages des frames précédentes. Il existe diverses méthodes pour lier le maillage et sa cage. La première a été d'utiliser des cordonnées barycentriques (le sommet du maillage est défini comme barycentre des sommets de la cage). Mais cette méthode comporte certains inconvénients, et ne sera donc pas traitée ici (pour plus de précisions à ce sujet, voir [1]). On utilisera plutôt les coordonnées dites harmoniques, présentées dans l'article [1], qui sont plus complexes mais plus précises.

ChatCage.png


Objectif

L'objectif de ce projet est de réimplémenter la technique d'animation par cages proposées dans l'article, et d'étudier si cette technique peut être étendues aux animations (cela correspond à l'ajout d'une dimension temporelle). On s'intéresse en parallèle à essayer de générer automatiquement une séquence de cages pour une animation, à partir de la donnée d'une cage de base.


Base de travail

Nous avons développé notre projet à partir d'une interface graphique de visualisation de maillages et d'animations fournie, issue d'un projet d'une année précédente. Cette interface est implémentée en C++ et utilise la librairie QGLviewer. Nous avons donc repris ce code comme base afin d'améliorer l'interface pour pouvoir y ajouter les options nécessaires à la réalisation de notre projet.


Interface de création de cage

Pour pouvoir tester les algorithmes que nous allons implémenter, nous avons eu besoin de créer une interface afin de construire une cage autour d'un maillage. Cette interface nous permet de créer une cage à partir de rien, puis de la sauvegarder dans un fichier au format .off.

Le menu de création de cage permet à l'utilisateur de placer des points un par un, de les déplacer jusqu'à la position voulue puis de les relier en facettes triangulaires. Les points de la cage sont symbolisés par des sphères dont le rayon s'adapte en fonction de la taille du maillage; elles sont de différentes couleurs selon leur indice afin de faciliter leur identification. Pour la création de cages bien fermées, une option de remplissage des facettes triangulaires a été rajoutée. Les facettes déjà créées se colorent en noir, ainsi, il est bien plus facile de détecter les trous.

Exemple d'utilisation de l'interface

Calcul des coordonnées harmoniques

La technique d'animation par cage mise en place par Pixar nécessite le calcul des coordonnées harmoniques de chaque point du maillage. Cela consiste à définir, pour chacun des points du maillage, une coordonnée h_i par sommet de la cage C_i. On peut alors exprimer chaque point M du maillage en fonction des sommets de la cage de la façon suivante:
  M = \sum_i h_i C_i

Coordonnées harmoniques en 3D

On s'intéresse tout d'abord à calculer les coordonnées harmoniques sur un maillage en 3 dimensions. Pour ce faire, on choisit d'implémenter l'algorithme proposé par DeRose et Meyer [3], notamment du fait de sa relative simplicité. On va tout d'abord discrétiser l'espace, sur une boîte englobant le maillage et sa cage. On va ensuite décrire l'état de chaque point de cet espace discret: on veut savoir s'il se trouve sur une face de la cage, à l'intérieur ou à l'extérieur de la cage. On utilise pour cela divers algorithmes de remplissages.
On commence par tracer les différentes arètes de toutes les faces de la cage avec un algorithme de type bresenham, on remplit ensuite ces différentes faces définissant la cage. Une fois cela tracé, on utilise un remplissage de type FloodFill en 3D pour caractériser la zone exterieure à la cage qui ne sera pas prise en compte dans nos calcul, nous ne travaillons que sur l'intérieur de la cage et plus précisement sur les sommets du maillage.
On résout ensuite l'équation de Laplace sur cet espace pour chaque sommet de la cage en procédant dimension par dimension. En effet, la résolution de l'équation de Laplace en dimension  d implique de connaître une solution de l'équation sur les dimensions  n < d . Concrètement, on résout tout d'abord l'équation de Laplace sur les arêtes de la cage (cela revient à une simple équation linéaire) avec les conditions suivantes sur les sommets :

 \forall i , h_i(C_j)=\delta_{i,j} 

Une fois les coordonnées sur les arêtes obtenues, on résout l'équation sur l'intérieur des faces de la cages, en utilisant les coordonnées calculées sur les arêtes comme conditions de Dirichlet. Cela correspond à la résolution en 2 dimensions. Enfin, la résolution de l'équation sur l'espace entier se fait en considérant les coordonnées sur les faces comme conditions limites. La description de l'espace faite au préalable permet de résoudre l'équation uniquement sur l'intérieur de la cage et non sur l'extérieur, où les coordonnées harmoniques ne sont pas définies.

Algorithme de résolution de l'équation de Laplace

Afin de résoudre l'équation de Laplace dans l'espace, on utilise un algorithme de moyennes successives. Pour chaque point de l'espace, on calcule sa coordonnée harmonique comme moyenne des coordonnées harmoniques de ses voisins. On itère cette opération plusieurs fois afin d'obtenir une précision suffisante. Cela nécessite d'avoir calculé au préalable les valeurs aux limites, comme décrit précédemment.

Coordonnées harmoniques sur une animation

Calculer les coordonnées harmoniques sur une animation revient à étendre le calcul fait précédemment en rajoutant une dimension temporelle. L'équation à résoudre devient alors une équation de d'Alembert, de la forme suivante:

 -\frac{\partial^2}{c^2 \partial t^2} f +\Delta f = 0 , où le paramètre  c^2 correspond à la vitesse de la lumière.

Cependant, afin d'observer l'influence de ce paramètre temporel, on choisit de remplacer la valeur  \frac{-1}{c^2} par un paramètre  \alpha variable.

Chaque point de l'animation va donc être exprimé en fonction de tous les sommets de toutes les cages de l'animation. On doit donc résoudre l'équation d'alembertienne sur toutes les frames de l'animation, et ce pour tous les sommets des cages.


On calcule tout d'abord comme précédemment les coordonnées harmoniques en 3D sur chaque frame (ces coordonnées seront toutes nulles sauf sur la frame contenant le sommet de la cage considéré). On applique ensuite l'algorithme des moyennes successives en tenant compte en plus de la valeur de la coordonnée harmonique du point aux frames précédente et suivante, pondéré par le coefficient  \alpha .

La difficulté vient du fait qu'on doit calculer à quelle position le point d'une frame  t s'est déplacé dans la frame  t+1 . Pour cela, on exprime le point en fonction des coordonnées barycentriques des 3 sommets voisins les plus proches (car on connaît la position des sommets sur les différentes frames). Cette solution permet un bon compromis entre la précision et la rapidité du calcul.


Génération automatique de cages sur une animation

L'un des objectif du projet est d'implémenter est de tester la génération automatique de cages sur une animation. En effet, on a constaté précédemment que la construction d'une cage précise et efficace n'était pas chose aisée. Devoir donc construire une cage propre manuellement sur chaque frame serait assez coûteux. On va donc créer les cages sur toutes les frames à partir de la donnée d'une seule, la première. Pour cela, on va exprimer les coordonnées des sommets de la cage en fonction des sommets du maillage, c'est-à-dire l'opération inverse de celle décrite précédemment.

Connaissant les coordonnées harmoniques de la cage en fonction du maillage, on peut calculer la position de la cage aux frames suivantes, en l'exprimant en fonction du maillage.

Nous avons essayé deux approches différentes afin de résoudre ce problème.

La première méthode consiste à réutiliser l'algorithme décrit précédemment, qui calculait les coordonnées harmoniques du maillage en fonction de la cage. Cette fois, on définit les conditions de Dirichlet sur le maillage, afin de calculer les coordonnées harmoniques sur l'intérieur de la cage. On exprime ainsi les coordonnées harmoniques sur les sommets de la cage en fonction de ceux du maillage.

L'autre approche consiste à inverser le système de coordonnées harmoniques obtenu avec l'algorithme de la partie précédente. On utilise ici une résolution par méthode des moindres carrés avec une décomposition en valeurs singulières (svd decomposition). Cette méthode nous a permis de résoudre une équation du type  Ax=b avec  A une matrice ayant un très petit déterminant (de l'ordre de  10^-13 donc une matrice non inversible). La matrice A ayant plus de lignes que de colonnes, il existe différents vecteurs x qui résolvent ce système, nous avons donc pu sélectionner les lignes les plus pertinentes et ainsi obtenir des résultats satisfaisants.


Voyons cela un peu plus en détail :

nous voulons résoudre Ax=b, à l'aide de la décomposition en valeurs singulières, on obtient A=USV^{T} avec U et V des matrices orthogonales et S une matrice diagonale.

En remplaçant A dans l'équation on obtient: USV^{t}x=b et au final x=VS^{-1}U^{t}b.


Cependant S est une matrice diagonale dont les coefficients peuvent être très petits et par conséquent leur inverse est très grand, c'est pourquoi on utilise la formule suivante :

 \forall i , x=\sum_i \frac{1}{\sigma_i} V_i(U_i^{t})*b

U_i correspond à la ième colonne de U et \sigma_i correspond à S_{i,i} et on somme sur les i tels que  \sigma_i ne soit pas trop petit. Nous avons obtenu de bons résultats avec cette méthode.


Résultats

Création d'une cage

Nous avons implémenté diverses options permettant de créer manuellement une cage sur un maillage. Cela nous a permis de générer les cages suivantes:


Cependant, on note certaines limitations à cette méthode de cage. Tout d'abord, lors de la création de la cage, on doit prendre garde à ce qu'il n'y ait aucune intersection entre les faces de la cage, afin de ne pas fausser le calcul des coordonnées harmoniques.

De plus, cette méthode de cage n'est pas applicable sur des maillages présentants des intersections entre différentes parties du corps. Sur l'exemple suivant, on constate que le bras et le ventre ne peuvent être séparé. On ne peut donc pas créer de cages permettant d'animer independamment le bras du ventre du personnage, ce qui est assez problématique.

Maillage impossible à recouvrir d'une cage

Enfin, notre interface graphique de création manuelle de cages peut rencontrer quelques problèmes de précision. En effet, il est parfois difficile de placer un point de la cage avec une grande précision? Par exemple, sur l'image suivante, il est ardu de placer précisément un point entre le bras et le pull-over du personnage, du fait du peu de distance entre les deux. Cela va entraîner qu'après le calcul des coordonnées harmoniques, le déplacement du bras pourra entraîner le déplacement de certaines faces du pull.

Pull-over et bras trop proches


Déplacement de la cage en 3D

On teste tout d'abord le déplacement d'une cage juste sur une seule frame (sans animation). Le principal problème rencontré est lié à la complexité temporelle de notre algorithme. En effet, le temps de calcul de notre algorithme est assez élevé, vu qu'il nécéssite de nombreux parcours de matrices en trois dimension. De plus, on constate que plus le maillage comporte de points, plus la discrétisation de l'espace doit être fine, pour éviter une déformation du maillage. Or, le temps de calcul devient très vite important sur des matrices de grande taille.


D'après l'article de recherche, la taille de la grille utilisée varie entre  2^4 et  2^5 . Or, d'après les tests que nous avons effectués, une taille aussi faible ne permet pas d'obtenir un maillage de qualité suffisante. On constate en effet sur l'image ci-dessous que le maillage est très peu précis et déborde à l'extérieur de la cage. Les résultats obtenus avec nos tests nous montrent donc des résultats différents que ceux attendus.

Cette limitation nous a empêché de travailler avec des maillages précis. Cependant, on constate ci-dessous que le déplacement de la cage entraîne bien la modification du maillage, et seules les faces proches du point de la cage déplacé sont impactées.

ImgAnim1.png ImgAnim2.png ImgAnim3.png ImgAnim4.png

Génération de cages : résultats

La génération automatique de cages a soulevé assez rapidement certains problèmes. Tout d'abord, nous avons constaté précédemment qu'on doit prendre garde lors de la création de la cage à ce qu'il n'y ait aucune intersection entre les faces de la cage et avec les faces du maillage. Or, avec le déplacement de la cage au cours du temps, cette condition n'est pas vérifiée lors de la création des cages sur toutes les frames. On peut alors se retrouver avec des cages incohérentes sur certaines frames de l'animation. Une solution pour éviter ce problème serait de calculer au préalable la distance minimale au cours de l'animation entre différentes faces du maillage, et de créer la cage de base suffisamment proche du maillage pour éviter ce phénomène de recoupement.


Ensuite, les coordonnées harmoniques calculées avec nos différentes méthodes se sont avérées peu concluantes. En effet, le calcul des coordonnées harmoniques de la cage par résolution de l'équation de Laplace donne des résultats très faibles et peu précis, ce qui donne une cage presque inutilisable. Cela provient notamment de la discrétisation de l'espace effectuée dans notre algorithme. Comme le maillage est plus petit que la cage, très peu de points ont une valeur non nulle à la base de l'algorithme (seule les arètes contenant le sommet pour lequel on calcule les coordonnées ont des valeurs non nulles), et donc peu de valeurs vont se propager jusqu'aux points de la cage. Cette méthode apparait donc difficile à mettre en place avec notre algorithme et les ressources que nous disposons actuellement.

La seconde méthode s'est avérée plus concluante, ainsi nous obtenons les résultats suivants sur plusieurs frames de l'animation du chat: Chat1.png Chat2.png Chat3.png Chat4.png

Nous pouvons voir que la cage se déplace avec le chat. Cependant, sur certaines frames (c'est le cas pour 2 frames de l'animation du chat) , la cage a un comportement inattendu :

ChatFou.png


Bilan

On a pu voir sur ce projet les avantages et les limitations de l'animation par cage. En effet, cette méthode permet d'animer un personnage de manière simple en un temps relativement court (le calcul des harmoniques est long, mais n'est effectué qu'une seule fois, et le résultat peut être conservé). Cependant, avec des ressources limitées, il est difficile d'obtenir des résultats précis (les maillages sont plus ou moins déformés par rapport à l'original). L'application de cette méthode aux animations semble intéressante en théorie, mais a soulevé un certain nombre de problèmes qui nécessiteraient un temps de travail plus important afin d'obtenir des résultats plus concluants.

Remerciements

A Tigrou notre mascotte, qui nous a soutenu tout le long du projet

Chat.jpg

Bibliographie