Introduction à la sélection apprise de mouvement

Blog, R&D, Tech

La sélection par recherche de mouvement (« Motion Matching ») constitue un moyen simple et puissant d’animer les personnages de jeu vidéo. Contrairement à d’autres méthodes, elle ne nécessite pas beaucoup de travail manuel une fois que la configuration de base est établie : il n’est pas nécessaire de structurer les clips dans des graphes, de les découper et de les synchroniser minutieusement, ou encore de créer explicitement de nouvelles transitions entre les états. Mais pour bien fonctionner, la sélection par recherche de mouvement a besoin de beaucoup de données de capture de mouvement sans offrir un moyen de les combiner ou de les comprimer, ce qui s’avère couteux en ressource mémoire. Nous présentons dans cet article une solution à ce problème, que nous appelons sélection apprise de mouvement (« Learned Motion Matching »). Cette solution se sert de l’apprentissage statistique pour réduire considérablement l’utilisation de la mémoire.

La sélection par recherche de mouvement

Tout d’abord, tâchons de comprendre comment la sélection par recherche de mouvement fonctionne. Pour commencer, examinons les données avec lesquelles nous allons travailler : des animations longues et non structurées, qui sont généralement des captures de mouvement. En voici un exemple :

En utilisant de telles données, comment pourrions-nous animer un personnage de sorte qu’il suive une trajectoire arbitraire, telle que la suivante ?

La méthode de la sélection par recherche de mouvement permet de résoudre ce problème. Elle consiste à effectuer une recherche en boucle dans toutes les animations pour trouver un clip qui, si joué immédiatement à la suite du clip courant, serait mieux adapté pour garder le personnage sur la bonne trajectoire. Le résultat brut est une mosaïque de clips courts collés les uns à la suite des autres, de la façon suivante :

Comment prendre la décision d’arrêter de jouer un clip pour un autre ? Précisons qu’un clip est une courte animation, soit une succession de trames (« frames ») qui peut commencer à n’importe quel endroit de nos animations sources. Au vu de la quantité d’information qu’un clip représente, la tâche n’est pas simple !

Une bonne solution consiste à choisir manuellement certaines de ces informations, que nous appellerons des caractéristiques de sélection. Dans notre scenario, nous voudrions que les caractéristiques de sélection d’un clip reflètent deux éléments : la trajectoire que le personnage suivra immédiatement à partir de la première trame, afin que nous puissions choisir des clips qui collent mieux à la trajectoire désirée, et la pose du personnage à la première trame, de sorte que nous puissions choisir un clip dont le départ est en continuité naturelle de l‘animation courante. Voici ce que nous trouvons : pour la trajectoire, nous avons juste besoin de quelques échantillons de positions et d’orientation du personnage à partir de la première trame, et pour la pose, nous ne retenons que les positions des pieds, leur vitesse linéaire et la vitesse linéaire globale du personnage, et ce uniquement pour la première trame. Voici une illustration de ces caractéristiques :

Ces informations sont beaucoup plus concises et gérables. Non seulement sont-elles plus faciles à comprendre pour nous, mais elles facilitent grandement la tâche de l’algorithme qui doit régulièrement décider du meilleur clip à jouer. Pour une trame donnée, nous rassemblons toutes les caractéristiques dans un vecteur, que nous appelons le vecteur de caractéristiques de sélection (voir le tableau coloré dans la vidéo ci-dessus). Il s’agit d’une représentation numérique concise de la capacité d’une trame à résoudre la tâche, dans notre cas celle de suivi de trajectoire. Nous empilons les vecteurs issus de toutes les trames de nos animations sources pour obtenir une grande matrice que nous appelons matrice des caractéristiques de sélection. Quand vient le moment de chercher un meilleur clip à jouer, nous formons un vecteur de caractéristiques requête à partir de la pose courante du personnage et de la prochaine portion de trajectoire désirée, puis nous recherchons dans la matrice la ligne qui s’approche le plus de la requête. A cette ligne-là correspond une trame dans nos animations sources et c’est à partir de cette trame que l’animation du personnage reprend. Voici un aperçu de la procédure :

Tournons-nous maintenant vers la discontinuité qui arrive aux changements de clips. Même si nous avons pris soin d’inclure des caractéristiques qui permettent de favoriser la continuité de la pose, nous en incluons en même temps d’autres qui favorisent le suivi de trajectoire. Ces deux types de caractéristiques sont en conflit et cela revient à dire que nous acceptons une certaine discontinuité de mouvement en échange de l’adhésion du personnage à sa trajectoire cible. Puisque la discontinuité n’est pas très grande, elle peut facilement être supprimée à l’aide de techniques d’interpolation telles que l’inertialisation. Voici ce que cela donne sur notre exemple :

Finissons en appliquant une technique de cinématique inverse simple pour réduire les glissements des pieds au sol lors des transitions, et voici le résultat final :

Problème résolu ! En utilisant d’autres types de caractéristiques, nous pouvons résoudre d’autres tâches telles que l’interaction avec des accessoires, la navigation sur un terrain accidenté, ou même des réactions vis-à-vis d’autres personnages. Il s’agit de l’ingrédient secret derrière plusieurs systèmes d’animation à succès dans les jeux récents.

Passage à l’échelle

Maintenant que nous savons comment fonctionne la sélection par recherche de mouvement, de combien de données avons-nous besoin pour créer un jeu AAA ? De nombreux facteurs doivent être pris en compte, notamment les types de déplacement requis (marche, course lente, course normale, course rapide, déplacement latéral lent, déplacement latéral rapide, saut, position accroupie, etc.), les actions disponibles et leurs paramètres (ouvrir une porte, s’asseoir sur une chaise, ramasser un objet, monter à cheval, etc.) et les différentes combinaisons de mouvements et d’actions (marcher, marcher en tenant une arme légère, marcher en tenant arme lourde à deux mains, etc.). De plus, tous ces facteurs peuvent être aggravés par l’existence de plusieurs sortes d’archétypes (comme plusieurs types de civils, de militaires, etc.) ainsi que par les différents états d’un personnage (blessé, ivre, etc.). Pour notre méthode de sélection par recherche de mouvement, cela se chiffre facilement en centaines de mégaoctets, voire parfois de gigaoctets d’animations. Soulignons un point en particulier : la sélection par recherche de mouvement ne combinera pas des animations à votre place. Si vous disposez d’une animation pour marcher et d’une autre pour boire, l’algorithme que nous avons décrit plus haut ne prévoit rien pour animer un personnage qui marche en buvant, il faut que vous fournissiez ce type d’animation si vous en avez besoin.

Par ailleurs, non seulement devons-nous garder toutes ces animations en mémoire, mais la matrice des caractéristiques de sélection vient s’y ajouter. Sa taille est proportionnelle à la fois au nombre de caractéristiques et à la quantité de données d’animation utilisées. Naturellement, cela se ressent également au niveau de la performance à chaque fois qu’on cherche le meilleur clip à adopter.

Dans notre travail de recherche, nous nous efforçons de trouver un système optimisé qui produit un résultat identique à la méthode de sélection par recherche de mouvement mais qui ne nécessite pas de conserver autant de données en mémoire. Le nouveau système ne doit pas perturber la manière de travailler des animateurs. Ces derniers doivent pouvoir continuer à se servir de la sélection par recherche de mouvement et capturer ou créer autant d’animations qu’ils le souhaitent. Notre objectif pour le système optimisé est de livrer le même résultat d’animation mais pour une fraction du coût mémoire. Nous faisons pour cela appel à l’apprentissage statistique.

La sélection apprise de mouvement

Pour commencer, nous devons penser de façon plus abstraite à notre système d’animation et le considérer davantage comme un système logique qui admet des commandes en entrée (qu’il s’agisse d’une trajectoire à suivre, d’actions de joueur sur sa manette, etc.) et qui produit en sortie une animation fluide et continue. Un système d’animation basé sur la sélection par recherche de mouvement, comme nous l’avons vu, accomplit cela en s’appuyant les données d’animation qui lui sont fournies, ainsi que sur la matrice des caractéristiques de sélection.

Précisons davantage les choses : une animation est une séquence de trames, chacune étant référencée par un index de trame. Cet index indique l’endroit où la trame est stockée dans les données d’animations. Pour lire un clip, nous devons incrémenter l’index courant à chaque trame et extraire la pose complète correspondante des données d’animation. La recherche du meilleur clip est effectuée périodiquement, une fois toutes les quelques trames. Pour chaque recherche, les caractéristiques requête sont comparées aux lignes de la matrice des caractéristiques de sélection pour trouver la meilleure trame à jouer. L’animation du personnage reprend alors à partir de cette trame-là. Le diagramme suivant résume cette logique :

Les animations constituent le gros des données, est-il possible de s’en débarrasser ? Nous pourrions par exemple essayer de réutiliser la matrice des caractéristiques de sélection car après tout, ces caractéristiques capturent de nombreux aspects importants de l’animation. Nous entraînons donc un réseau de neurones, que nous appelons Décompresseur, à reconstruire une pose complète à partir de son vecteur de caractéristiques. La logique à chaque trame devient désormais :

Au lieu d’extraire une pose des animations sources, nous extrayons à présent le vecteur des caractéristiques correspondant qu’on passe ensuite au Décompresseur. Voici une comparaison entre l’animation d’origine (en gris) et sa reconstruction par le Décompresseur (en rouge).

Nous pouvons constater que bien que les animations soient similaires, il existe parfois des erreurs visibles (suivez par exemple les positions des mains sur le squelette affiché à gauche). Il semble donc que les caractéristiques de sélection ne contiennent pas assez d’informations pour nous permettre de reconstruire fidèlement la pose. Néanmoins, la qualité de l’animation reconstruite est étonnamment bonne. Au lieu de s’appuyer uniquement sur les caractéristiques de sélection, que se passe-t-il si nous apportons un complément d’informations au Décompresseur ?

Plutôt que de choisir manuellement ces informations, nous pouvons utiliser un réseau encodeur automatique (« auto-encoder ») pour les extraire des animations sources (consultez cet article pour plus de renseignements). Entraîner ce réseau nous permet d’obtenir un vecteur de caractéristiques complémentaires par trame, sélectionnées automatiquement pour améliorer la précision du Décompresseur. Nous devons stocker ces caractéristiques complémentaires pour toutes les trames dans une matrice, aux côtés de la matrice des caractéristiques de sélection. Voyons ce que cela signifie pour notre logique :

Le gain en précision est net. Ci-dessous, l’animation originale est affichée en gris et celle provenant du Décompresseur avec les caractéristiques complémentaires est affichée en vert :

L’animation en sortie est désormais presque identique à l’originale. Combien de mémoire avons-nous réussi à économiser ?

Notons bien que l’économie en mémoire est réalisée sans changement perceptible dans l’animation en sortie et surtout, nous n’avons pas touché au comportement d’origine de la sélection par recherche de mouvement. C’est un bon début ! Toutefois, le passage à l’échelle que nous espérons n’est pas encore possible car les matrices des caractéristiques, qui demeurent indispensables, augmentent toujours proportionnellement à la taille des animations sources. Voyons comment s’en débarrasser.

Simplifions d’abord notre diagramme en regroupant les deux matrices en une unique matrice des caractéristiques complètes. En d’autres termes, un vecteur de caractéristiques complètes pour une trame donnée représente la concaténation du vecteur de caractéristiques de sélection et du vecteur de caractéristiques complémentaires.

Le diagramme ci-haut montre qu’entre deux requêtes, nous ne faisons que lire une suite de lignes successives dans la matrice des caractéristiques complètes, sans effectuer de saut. L’idée que nous avons alors est d’entrainer un autre réseau de neurones, que nous appelons Séquenceur, pour produire le vecteur de caractéristiques d’une trame à partir de celui de la trame d’avant. Bien entendu, ce réseau ne pourra pas être précis sur de longues fenêtres de temps. Toutefois, comme nous prévoyons de « rafraichir » le vecteur de caractéristiques au moment de chaque transition de clip (environ 5 fois par seconde), le Séquenceur a simplement besoin d’apprendre à prédire sur une courte durée de temps. La nouvelle logique devient donc la suivante :

Notons que la matrice n’est maintenant requise que pour effectuer la sélection par recherche de mouvement. Pour s’en débarrasser une fois pour toutes, nous entrainons un troisième et dernier réseau de neurones, que nous appelons Projecteur. Le rôle de ce dernier est de prédire le meilleur vecteur de caractéristiques complètes étant donne un vecteur de caractéristiques requête en entrée. Ce réseau apprend en quelque sorte à imiter la recherche de la ligne la plus proche dans la matrice des caractéristiques, sans garder la matrice au moment de l’exécution !

Nous avons à présent remplacé tous les composants du système qui dépendent de données (sources ou caractéristiques) par des réseaux de neurones. Voyons le schéma de logique complet:

Si chacun des réseaux est entraîné de façon suffisamment précise, la différence entre la sélection par recherche de mouvement et sa version apprise est presque imperceptible. Voici ce que la version apprise donne sur la trajectoire d’avant :

Et voici l’économie réalisée en ressource mémoire :

Nous avons réduit la taille mémoire nécessaire par un facteur 10 ! Mais pour vraiment voir l’avantage de notre méthode, il faut viser un scenario plus ambitieux. Nous avons donc ajouté 30 nouveaux styles de mouvements à nos animations sources, et avons aussi augmenté la complexité du squelette de notre personnage en incluant les articulations des doigts (soit quelque 47 nouvelles articulations supplémentaires). Voici ce que cela donne (l’utilisateur appuie sur un bouton de manette pour changer de style) :

Et voici la comparaison de taille mémoire :

Bien que nous ayons ajouté une énorme quantité de données sources, la consommation en mémoire de notre nouvelle méthode est restée relativement inchangée (environ 17 Mo), à contraster avec l’originale (quelque 591 Mo !). En bonus, les paramètres des réseaux de neurones pouvaient être encore compressés par un facteur de deux, sans aucun impact visuel sur le résultat, en codant leurs valeurs sur 16 bits au lieu de 32. En en tenant compte, nous sommes passés de 590 Mo à 8,5 Mo de mémoire, réalisant un facteur de compression de 70 !

Cette nouvelle technique s’avère être moyen puissant, générique et systématique de compresser les systèmes d’animation basés sur la sélection par recherche de mouvement, autorisant un vrai passage à l’échelle. En l’utilisant, nous pourrions créer des contrôleurs d’animation très gourmands en données complexes tout en respectant les budgets de production. Pour illustrer ce riche potentiel, nous avons préparé une dernière vidéo qui montre des personnages marchant sur un terrain accidenté et qui interagissant de manière fluide avec d’autres personnages ou accessoires du jeu. Chacun des personnages de la scène suivante est animé à l’aide de notre technique :

Nous espérons que la sélection apprise de mouvement ouvrira de nouvelles portes aux systèmes d’animation et qu’elle offrira aux artistes, aux concepteurs et aux programmeurs la possibilité de libérer complètement leur potentiel créatif, en leur permettant de livrer des personnages capables de réagir de manière réaliste et unique face aux milliers de situations différentes qui leur seront présentées en jeu, sans jamais avoir à se soucier de contraintes de mémoire ou de performance.

Pour obtenir plus de détails et de résultats, consultez la vidéo complémentaire en cliquant ici, et lisez l’article complet en cliquant ici.

Autres recherches dans le domaine de l’animation

Certaines des autres recherches dans le domaine de l’animation effectuées par Ubisoft La Forge

Menu