L'animation temps réel dans les jeux vidéo

(Redirigé depuis Documentv3 106)

Un article de David Lanier.

© Copyright 2002 par (http://dlanier.free.fr) Toute reproduction même partielle de ce document est formellement interdite sans l'autorisation de son auteur.

Sommaire

[modifier] 1. Généralités

Depuis les débuts du jeu vidéo sur micro-ordinateur 8 bits dans les années 80, l'animation a été prépondérante. Elle a permit aux joueurs de s'immerger dans l'univers proposé et de rendre les actions du joueur identifiables dans cet univers. Tout d'abord réalisée en 2 dimensions (2D) par diverses techniques telles que les scrollings et les sprites, elle a acquis aujourd'hui un réalisme qu'il n'aurait pas été possible d'imaginer il y a 20 ans ! Nous allons voir les différentes techniques utilisées pour animer les jeux d'aujourd'hui.

[modifier] 1.1. Prérequis

Il est nécessaire pour comprendre ce qui suit d'avoir des notions minimums en 3D telles que translation, rotation, scale, changement de repère, quaternions. Il faut avoir aussi des notions de mathématiques. Il faut connaître la dynamique pour comprendre le paragraphe sur ce sujet car les notions de bases ne seront pas expliquées.

[modifier] 1.2. A qui s'adresse ce cours ?

Ce cours s'adresse aussi bien aux débutants dans le domaine de l'animation qu'aux gens désireux de se perfectionner. Il est plutôt orienté pour les programmeurs mais peut-être lu en grande partie par des artistes. Ce cours n'abordera pas les notions présentées avec un formalisme mathématique. Ce cours se veut accessible au plus grand nombre et ne devrait pas nécessiter d'avoir un niveau élevé en mathématiques.

[modifier] 2. Les différentes méthodes de création d'une animation

La plupart du temps on utilise un package 3D pour créer les animations. Voyons ces méthodes :

[modifier] 2.1. Procédurale

Il s'agit ici d'une animation qui se définit par rapport à une action, par exemple nous pouvons rajouter un comportement sur un objet qui le ferait tourner sur lui-même. Nous pouvons aussi lui affecter une trajectoire géométrique tel qu'un cercle et lui demander de suivre ce cercle à une certaine vitesse. Ce type d'animation n'est, en général, pas éditable directement sous un package 3D car ces comportements sont des éléments du moteur de jeu et donc rarement disponible dans le package 3D lui-même. Il est cependant possible de programmer ces comportements et de les rajouter au package 3D.

[modifier] 2.2. Dynamique

On anime ici les objets par de la dynamique. Il s'agit de mécanique du point et du solide plus rarement des fluides. C'est à dire, les objets sont animés par un comportement basé sur des lois physiques. Exemple : Un personnage tenant une épée, la lâche. La gravité s'appliquant sur cette épée fait qu'elle tombe sur le sol puisqu'aucune contrainte ne la retient. Précédemment, la gravité s'appliquait aussi mais la main du personnage empêchait l'épée de tomber. On utilise des lois similaires à celle-ci bien qu'en réalité dans les jeux vidéo, nous n'ayons pas forcément besoin d'un réel comportement dynamique mais uniquement de faire croire à ce comportement, de le rendre plausible... Nous n'allons que brièvement parler de la dynamique du point dans ce document. Pour cela on introduit l'équation fondamentale de la dynamique :

F1+ F2 +...+ Fn = m*Aoù les Fi sont des vecteurs forces appliqués sur le centre de gravité de l'objet, mest la masse de l'objet, et A son vecteur accélération.

On considère ici un objet où seul son centre de gravité reçoit l'application de forces. Cela est suffisant pour simuler des lancés d'objets par exemple. Dans ce cas, on néglige toute rotation, seul un point (qui n'a donc pas d'orientation) est considéré comme représentant de l'objet sur lequel s'applique les forces.

animation_jv_1.gifFigure 1 : cube avec une force de gravité

Cette méthode permet de gèrer des particules. C'est un effet très couramment utilisé dans les jeux. On l'utilise en autres pour :

  • simuler de la poussière lors de dérapage de voitures.
  • simuler un feu avec de la fumée qui monte au-dessus
  • Etc.


Voyons sur un exemple comment on apllique cette formule :

Considérons que seule une force s'applique sur un objet lancé : son poids noté P = m*g où m est la masse de l'objet, et g la constante gravitationnelle sur terre dont la valeur numérique est 9.81. Avec l'équation fondamentale de la dynamique précédente, on obtient dans ce cas que la somme des forces vaut P le poids, et donc : 

P = m*A

Ceci nous permet de calculer l'accélération qui est constante par rapport au temps et vaut A = P/m = g. Or ce qui nous intéresse pour faire bouger un objet c'est sa position à un instant donné.

Pour calculer la position à partir de l'accélération, on est obligé de passer par la calcul de sa vitesse. Pour la calculer, il suffit d'intégrer par rapport au temps l'équation donnant l'accélération, puis pour retrouver la position à un instant donné, il nous faudra encore intégrer la vitesse. Ce qui fait : 

A(t) = g  (constant par rapport au temps t)

V(t) = g*t + V0où V0 est la vitesse au temps 0 (vitesse initiale de l'objet)

Et enfin, on calcule : 

P(t) = 1 / 2*g* t2 + V0 * t + P0  Où est P0 est la position au temps 0 (position initiale)

Ces formules s'appliquent pour des vecteurs 3D, voir la figure précédente pour l'orientation des axes. L'accélération s'applique sur l'axe y dans le sens inverse. On a donc les vecteurs suivants :

A(t) = ( 0 , -g , 0 ) V( t ) = ( Vx( t ), Vy( t ), Vz( t ) ) et V0 = (V0x , V0y , V0z ) P( t ) = ( Px( t ), Py( t ), Pz( t ) ) et P0 = (P0x , P0y , P0z )

Ceci est la résolution théorique d'une équation différentielle linéaire du second ordre par rapport à t avec second membre constant qui est :

P( t ) = ( 0, -g , 0 )

En pratique comment résout-on ces équations ? Nous allons procéder numériquement de manière itérative en considérant ces équations sur des intervalles de temps petits et en calculant une solution approchée sur chaque extrémité de l'intervalle. Chaque nouvelle position 3D calculée avec sa vitesse nous permettra de calculer la position et vitesse approchée sur l'intervalle suivant...

Cela s'appelle les méthodes numérique de résolution des équations différentielles linéaires du premier ordre. Les méthodes d'Euler et celles de Runge-Kunta en font partie. Nous n'allons pas nous étendre sur les différentes méthodes et leurs avantages / inconvénients, cela dépasserait la cadre de ce document. Nous allons nous intéresser uniquement à la méthode d'Euler explicite qui est la plus simple et la plus rapide (et qu'il faut éviter en pratique si on veut un résultat précis :) ) Cette méthode permet à un temps donné, connaissant la position et la dérivée (dans notre cas c'est vitesse) en ce temps de calculer la position et vitesse suivante. La formule est la suivante :

NewPos = CurPos + h * CurSpeedOù h est la longeur de l'intervalle de temps ( 1/30 dans notre cas ), CurPos est la position courante et CurSpeed la vitesse courante au temps t.

On démarre à t0 = 0 : V( t0 ) = V0 connu. P( t0 ) = P0 connu.

On va considérer par exemple des intervalles de 1 / 30 secondes (ce qui représente une frame sur deux pour un jeu tournant à 60 FPS).

Donc au temps suivant t1 = 1/30, on aura V( t1 ) = V( t0 ) + (1/30) * A( t0 ) avec A( t0 ) = A( t ) = g constant par rapport à t. P( t1 ) = P( t0 ) + (1/30) * V( t0 ) Puis au temps t2 = 2 / 30, on aura : V( t2 ) = V( t1 ) + (1/30) * A( t1 ) P( t2 ) = P( t1 ) + (1/30) * V( t1 )

Etc...

[modifier] 2.3. Keyframes

C'est le moyen le plus commun de création d'une animation. Prenons un exemple concret : Nous avons une caméra qui doit présenter deux combattants dans une arène, et nous souhaitons que la caméra fasse le tour de des 2 personnages en un temps de 5 secondes.

Remarque : On parle plus fréquemment en nombres de frames plutôt qu'en unité de temps. Pour passer d'un nombre de frames à un nombre de secondes on se sert de la vitesse d'affichage. Si on définit qu'une animation se jouera à 30 FPS sous le package 3D, on sait que 30 frames représenteront donc 1 seconde. Donc en faisant durer une animation 150 frames cela représentera 150 / 30 = 5 secondes d'animation. Mais en général le nombre de frames d'un jeu n'est pas constant...

On peut placer des clés d'animation sur la translation de la caméra, sa rotation ou son scale. Il y a d'autres possibilités que ces 3 cas mais nous n'en parleront pas ici. Prenons par exemple la translation. Une clé d'animation contiendra au minimum un temps (ou une frame) et une translation qui est un vecteur 3D.

Les animateurs plaçent ces clés sous un package 3D. Le programmeur les récupère par une phase d'export du package 3D puis il créé l'animation dans le moteur du jeu. Dans notre exemple, nous voulons que notre caméra passe d'une clé à une autre avec les informations que nous avons fixé dans chaque clé. La manière de passer d'une clé à une autre est appelé l'interpolation. L'interpolation permet, à partir de 2 clés existantes, de calculer une valeur intermédiaire à un temps donné permettant de relier les 2 clés.

[modifier] 2.3.1. Algorithme général d'animation par keyframe

Il nous faut un tableau contenant toutes les clés d'animation. Chacune de ces clés contient un temps, celui auquel s'applique cette clé et une valeur pour la clé. Dans ce tableau les clés sont triées en fonction du temps par ordre croissant.

L'algorithme est le suivant :

  • On prend en entrée le temps courant. Notons le t.
  • On recherche entre quelles clés on se trouve dans le tableau de clés, pour cela on cherche à vérifier que t soit inférieur au temps d'une clé. On connaît maintenant la clé de départ et d'arrivée notons les respectivement Keyn et Keyn + 1. Appelons tnet tn + 1 respectivement les temps des clés de départ et d'arrivée. Ces clés vérifient : tn <= t <= tn + 1.
  • Avec ces 2 clés nous pouvons utiliser une fonction d'interpolation pour nous renvoyer au temps courant la valeur de ce que nous interpolons (translation, rotation etc..)


Remarque : la fonction d'interpolation peut utiliser d'autres informations que ces 2 clés, elle peut utiliser d'autres clés pour lisser l'animation comme dans le cas du TCB.

Voyons quelques fonctions d'interpolation utilisées dans les jeux.

[modifier] 2.3.2. Interpolation de type linéaire

C'est le cas le plus simple. Nous allons traiter les clés 2 par 2 en considérant que nous avons une clé de départ et une clé d'arrivée qui sont des translations. Pour passer de l'une à l'autre nous allons faire comme s'il existait une droite 3D entre ces 2 clés et suivre cette droite à vitesse constante. Introduisons quelques notations afin de définir la formule d'interpolation linéaire. Soient Pn la translation de notre clé de départ, Pn + 1 la translation de la clé d'arrivée, tn le temps de la clé de départ et tn + 1 le temps de la clé d'arrivée. Pn et Pn + 1 représentent donc 2 points 3D.

Le segment de droite noté S entre nos 2 points 3D est donné par sa formule paramétrique S( t ) qui est la suivante :

S( t ) = Pn + t * (Pn + 1 - Pn) avec t dans [0,1]Pour t = 0, nous obtenons S ( 0 ) = Pn et pour t = 1, S ( 1 ) = Pn + 1. Et pour t dans ]0,1[ nous sommes sur le segment de droite dont les extrémités sont Pn et Pn + 1. Voici un exemple de fonction en C++ qui prend en entrée un temps t et en sortie donne la nouvelle position en fonction des clés. Ce fragment de programme sera expliqué juste après. 


struct Key
 {
 Vec3f Pos; //Vecteur 3D
 float Time; //Temps de la clé
 };
 void SolveLinear(float t, Vec3f&  NewPos)
 {
 Key* CurKey, *NextKey;
 int i = -1 ;
 const int NumKeys = TabKey.Count();
 const int NumKeysMinusOne = NumKeys-1;
 for ( i = 0 ; i <  NumKeys ; i++ )
 {
 //Get current key
 NextKey = TabKey[i];
 if ( t <  NextKey-> Time )
 {
 //Get Cur Key
 if ( i == 0 ) //We're on first key
 CurKey = TabKey[NumKeysMinusOne]; //Prev key = Last key
 else
 CurKey = TabKey[i-1]; //Prev Key
 //Translate time that is part of the interval [CurKey-> Time , NextKey-> Time]
 //to be part of the interval [0,1] to use our formula
 const float Coeff = ( t - CurKey-> Time) / ( NextKey-> Time - CurKey-> Time );
 assert(Coeff < =1.0f &&  Coeff > =0);
 //Interpolate
 NewPos = CurKey-> Pos + Coeff * ( NextKey-> Pos - CurKey-> Pos );
 break;
 }
 }
 assert(i <  NumKeys);//Have we found the good time ? We should...
 }


Exemple de programme 1 : interpolation linéaire pour des translations

Explication de cet exemple de code : Nous commençons par définir une structure appelé Keyqui contiendra les informations d'une clé d'animation. Cette structure contient 2 attributs : Time qui est le temps de la clé et Posqui est la valeur du vecteur 3D représentant la translation de la clé. Dans notre cas Vec3f représente un vecteur composé de 3 floats. Pour plus de précision on pourra utiliser le type double suivant la machine cible sur laquelle vous désirez jouer votre animation.

Voyons en détail la fonction SolveLinear : elle prend en paramètre un float t qui représente le temps courant et une référence sur un Vec3f qui sera la translation résultante de notre interpolation. C'est-à-dire pour notre exemple, la translation qu'il faudra mettre dans notre caméra. Nous allons dans cette fonction utiliser un tableau qui contient des pointeurs sur les clés d'animation de notre caméra. Ce tableau est appeléTabKey, il comporte une méthode Count qui renvoit le nombre d'éléments du tableau. Il contient aussi l'opérateur [ ]. TabKey[ i ] est le ième élément du tableau, soit la ième clé d'animation. Les clés d'animation contenues dans le tableau sont triées par ordre croissant en fonction du temps de la clé.

Pour chaque appel de SolveLinear, nous recherchons à partir du temps courant noté t les clés de départ et d'arrivée, pour cela nous cherchons à vérifier la condition :

t < NextKey->Time

Lorsque celle-ci est vérifiée, nous savons que NextKeyreprésente la clé d'arrivée et nous pouvons à partir de celle-ci retrouver la clé de départ. Pour cela on évite le cas particulier où NextKey se trouve être la première clé du tableau, dans ce cas on prend la dernière clé comme clé précédente. Si NextKeyn'est pas la première clé, il suffit de prendre la clé précédente dans le tableau, c'est notre clé de départ. C'est ce qu'effectue le test : 


if ( i == 0 ) //We're on first key
 CurKey = TabKey[NumKeysMinusOne]; //Prev key = Last key
 else
 CurKey = TabKey[i-1]; //Prev Key


A ce stade, nous connaissons les 2 clés de départ et d'arrivée, elles sont respectivement CurKey et NextKey. Ensuite nous avons vu que pour utiliser notre formule d'interpolation sur un segment il nous faut un temps compris entre 0 et 1. Comme le temps courant est compris entre CurKey->Time et NextKey->Time, nous allons faire un changement de variable du temps courant pour le placer entre 0 et 1. En 0, le temps courant vaudra CurKey->Time, et en 1 notre temps vaudra NextKey->Time. Ce changement est effectué dans le formule : 


const float Coeff = ( t - CurKey-> Time) / ( NextKey-> Time - CurKey-> Time );
 assert(Coeff < =1.0f &&  Coeff > =0);


Après avoir vérifié que le temps courant était bien entre 0 et 1, il ne nous reste plus qu'à utiliser la formule d'interpolation pour calculer la nouvelle position :

NewPos = CurKey->Pos + Coeff * ( NextKey->Pos - CurKey->Pos );

Ensuite, il est inutile de parcourir les autres clés, c'est pourquoi on sort de la boucle avec l'instruction du language C : break;

Exemple d'interpolation linéaire avec 6 clés :

animation_jv_2.gifFigure 2 : interpolation de type linéaire

Pour rentrer une vitesse de déplacement entre chaque segment, on se sert du temps de chaque clé. Si la différence de temps entre 2 clés est petite, la transition sera rapide, et au contraire, s'il elle est grande, la transition sera lente.

La trajectoire globale de notre caméra sera un ensemble de segments de droite ce qui n'est pas du plus bel effet... Nous souhaiterions avoir une trajectoire d'animation plus lisse...

Pour remédier à cela, on introduit la notion de tangente à l'intérieur d'une clé d'animation. On rajoute donc 1 ou 2 tangentes à chaque clé. Ces tangentes vont donner des informations complémentaires sur la manière dont on arrive ou dont on part d'une clé. Ces informations seront la vitesse et la "direction".

Dans le cas ou l'on place 2 tangentes par clé, l'une servira à définir une manière d'arriver sur la clé l'autre servira à définir la manière dont on partira de cette dernière. On les appelle respectivement tangente in et tangente out. In pour "entrée sur une clé" et out pour "sortie de la clé". Dans le cas où il n'y a qu'une tangente, elle sert à définir à la fois comment on arrive sur et comment on part de la clé.

Remarque : pour passer d'une rotation à une autre, on ne peut interpoler de la même manière que pour une translation. Il existe cependant des moyens de faire ces interpolations, par exemple, quand les rotations sont sous forme de quaternions, on peut utiliser la fonction SLERP(spherical linear interpolation) qui fait une interpolation de type linéaire entre 2 quaternions à un temps donné entre 0 et 1. Pour information la formule du SLERP est :

form_slerp.pngOù p est le quaternion de départ, q celui d'arrivée,t le temps compris entre 0 et 1 et Apq est l'angle entre p et q. Pour plus de détail sur les quaternions et les différents types d'interpolation, nous invitons le lecteur à regarder [ 5 ] et [ 8 ].

[modifier] 2.3.3. Tangentes et courbes d'animation

De manière pratique, ces tangentes peuvent être édités sous le package 3D utilisé pour créer les clés. Cette tangente est de même nature que la valeur de la clé.

Par exemple :

  • Dans une clé sur la translation de notre caméra, la valeur de la clé sera une translation représentée par un vecteur 3D. De ce fait, les tangentes seront elles aussi des vecteurs 3D.
  • Dans une clé sur la rotation de notre caméra, la valeur de la clé sera une rotation (par exemple représentée par un quaternion). Donc les tangentes seront elles aussi des rotations !


Remarque : Ceci paraît sans doute assez compliqué. Il est assez intuitif de se représenter une tangente pour une translation, c'est un vecteur 3D, on peut le visualiser dans l'espace. Mais il est peu intuitif de se représenter une tangente pour une rotation... On peut voir cette tangente comme la manière d'arriver sur la clé ou de repartir de cette dernière, c'est donc une rotation qui représente ici cette manière dans le cas d'animation sur la rotation.

En pratique : Est-ce que les animateurs rentrent une valeur de vecteur ou de quaternion pour les tangentes d'une clé ? Non. Les animateurs règlent leurs tangentes sur ce que l'on appelle une courbe d'animation.

Exemple : Lorsque l'on anime la translation d'un objet, on peut voir une courbe d'animation sur chaque composante de cette translation soit x, y et z. la figure suivante montre une courbe d'animation sur la composante z d'une translation :

animation_jv_3.gifFigure 3 : Une Courbe d'animation

Cette courbe d'animation comporte 3 clés qui sont représentées par les carrés noirs aux extrémités et le blanc au milieu. La courbe joignant les 3 clés est ce que l'on appelle la courbe d'animation. Sur la 2e clé, on peut visualiser, 2 tangentes In et Out. Les animateurs savent interpréter ces courbes et règler les tangentes pour obtenir l'effet qu'ils désirent obtenir entre 2 clés.

Dans certains cas, plutôt que d'éditer directement les tangentes sur la courbe, il est possible de rentrer certains paramètres qui seront utilisés pour reconstruire les tangentes avec l'aide des clés voisines.

Par exemple : une clé avec un type d'interpolation en TCB contiendra au lieu de tangentes, les paramètres : tension , continuity, bias. Nous allons étudier par la suite ce type d'interpolation.

L'interpolation de type Hermite est une interpolation qui fait intervenir des valeurs de clés, et des tangentes. Dans le cas le plus général d'Hermite, on ne prend en compte qu'une tangente par clé.

animation_jv_4.gifFigure 4: Une courbe d'Hermite

Explication de la figure précédente : Sur cette courbe d'Hermite, on a 5 points notés de P0 à P4, en chacun de ces points part une tangente avec en son extrémité une flèche, les tangentes dont notées de T0 à T4. On voit que la courbe résultante passe par tous les points.

[modifier] 2.3.4. Interpolation de type Hermite

L'interpolation de type Hermite cubique se fait à l'aide de 4 polynômes de degré 3 notés H0, H1, H2, H3. Nous interpolons toujours entre 2 clés, appelons Pnla valeur de la clé de départ, et Pn+1 celle de la clé d'arrivée. Tn et Tn+1 représentent respectivement la tangente à la clé Pn et celle sur la clé Pn+1.

La formule d'interpolation d'Hermite est la suivante :

P( t ) = H0( t )Pn + H1( t )Pn+1 + H2( t )Tn + H3( t )Tn+1 avec t dans [0,1]Avec les polynômes (appelés " Blending Hermite functions ") : H0 = 2t3 - 3t2 + 1 H1 = -2t3 + 3t2H2 = t3 - 2t2 +t H3 = t3 - t2Pour trouver pourquoi les polynômes ont ces valeurs, il suffit de prendre la forme générale d'un polynôme de degré 3 : Hi(t) = ai t3 + bi t2 + ci t +di, de remplacer dans la formule précédente les Hi(t) i = 0 à 3 par cette forme générale. Puis de poser que P(0) = Pn, P(1) = Pn+1 et P'(0) = Tn et enfin P'(1) = Tn+1 puis de résoudre le système linéaire résultant. Nous n'aborderons pas le détail ici.

Le cas qui nous intéresse est un cas particulier des courbes d'Hermite, ce sont les splines de Kochanek-Bartels appelées aussi plus couramment splines TCB.

Pour ces splines, les tangentes sont calculées à partir des paramètres T, C et B et de 4 clés ! Ces paramètres T, C et B doivent tous être compris entre -1 et 1 pour la formule suivante.

Nous avons déjà Pn et Pn+1 clés de départ et d'arrivée, notons la clé précédant celle de départ Pn - 1 et la clé suivant celle d'arrivée Pn + 2. Avec les notations précédentes, nous pouvons calculer les tangentes :

form_tangentes.png

Ce qui nous permet de calculer P( t ).

Explication de l'influence des paramètres TCB :

  • T : tension, sert comme son nom l'indique à règler la tension de la courbe, plus T sera proche de 1 plus on se rapprochera d'une ligne droite entre les 2 clés, plus T sera proche de -1 plus la courbe sera lâche. On peut voir cela comme quelqu'un qui tire sur une corde (valeur 1) ou la relâche (valeur -1).
  • C : continuity, sert pour définir comment le changement de vitesse et de direction interviendra entre le moment ou l'on entre sur une clé et le moment ou l'on part de cette clé.
  • B : bias, définit la direction de la courbe dès qu'elle passe la clé.


Il y a des cas particuliers des splines TCB lorsque :

  • T = C = B = 0, on appelle cette interpolation spline de Catmull-Rom.
  • B = C = 0, on l'appelle spline Cardinal.
  • T = C = 0, on l'appelle "Bias controlled spline"
  • T = B = 0, on l'appelle "Continuity controlled spline"


Voyons un exemple de code qui concrétise cela. Dans cet exemple nous avons appelé Pn-1 PrevKey, Pn CurKey, Pn+1 NextKey et Pn+2 NextNextKey. 


void SolveTCB ( float t, Vec3f&  NewPos)
 {
 Key *NextKey, *NextNextKey, *CurKey, *PrevKey;
 const int NumKeys = TabKey.Count();
 const int NumKeysMinusOne	= NumKeys-1;
 for ( int i = 0 ; i <  NumKeys ; i++ )
 {
 //Get next key
 NextKey = TabKey[i];
 if ( t <  NextKey-> Time
 {
 //Get Current Key
 if ( i  ==  0 )	//We're on first key
 //First key = Last key, so the prev is the one before the last
 CurKey = TabKey[NumKeysMinusOne-1];
 else
 CurKey = TabKey[i-1]; //Prev Key
 //Get Previous Key
 if (i == 0)
 PrevKey = TabKey[NumKeysMinusOne-2];
 else
 if (i == 1)
 PrevKey = TabKey[NumKeysMinusOne-1];
 else
 PrevKey = TabKey[i-2];
 //Get NextNextKey
 if (i == NumKeysMinusOne)
 NextNextKey = TabKey[0];
 else
 NextNextKey = TabKey[i+1];
 //Interpolate
 const float Coeff = ((t-CurKey-> Time) / (NextKey-> Time - CurKey-> Time));
 //Update values from TCB
 const float OneMinusTension = (1.f - CurKey-> tension);
 const float OneMinusContinuity = (1.f - CurKey-> continuity );
 const float OnePlusContinuity = (1.f + CurKey-> continuity );
 const float OneMinusBias = (1.f - CurKey-> bias);
 const float OnePlusBias = (1.f + CurKey-> bias);
 //Compute tangents
 Vec3f TanCurKey = 0.5f*((OneMinusTension*OneMinusContinuity*  OneMinusBias*(NextKey-> Pos - CurKey-> Pos )) +
 (OneMinusTension*OnePlusContinuity*OnePlusBias* ( CurKey-> Pos - PrevKey-> Pos )));
 Vec3f TanNextKey = 0.5f*((OneMinusTension*OnePlusContinuity*OneMinusBias* (NextKey-> Pos - CurKey-> Pos )) +
 (OneMinusTension*OneMinusContinuity*OnePlusBias*( NextNextKey-> Pos - NextKey-> Pos ))):
 //Compute new position
 NewPos = H0(Coeff) * CurKey -> Pos;
 NewPos += H1(Coeff) * NextKey-> Pos;
 NewPos += H2(Coeff) * TanCurKey;
 NewPos += H3(Coeff) * TanNextKey;
 break;
 }
 }
 }


Exemple de programme 2 : interpolation TCB pour des translations

Ce fragment de code est assez similaire au précédent dans le cas de l'interpolation linéaire. L'algorithme global reste le même, seuls les cas particuliers sont plus denses car il nous faut prendre une clé avant la clé courante et une clé après la prochaine. Il y a donc des cas particuliers quand nous sommes au début ou à la fin des clés dans le tableau.

Remarque : dans le cas des rotations sous forme de quaternions, pour l'interpolation linéaire de 2 rotations, nous avons vu que nous pouvions utiliser la fonction SLERP. Dans le cas de l'interpolation de type TCB entre 2 rotations, nous pouvons utiliser la fonction SQUAD(spherical cubic interpolation qui représente une interpolation de type bilinéaire sur un quadrilatère). Cette fonction prend en entrée 2 quaternions, un de départ et un d'arrivée, 1 tangente pour chaque clé sous forme de quaternions et un temps compris entre 0 et 1. Elle réalise l'interpolation de type TCB. Pour information, la formule du squad est :

Squad ( t; p, a, b, q ) = Slerp( 2t (1 - t); Slerp(t; p, q), Slerp(t; a, b) )Où t est le temps entre 0 et 1, p est le quaternion de départ, q celui d'arrivée, a le quaternion tangente de départ et b celui d'arrivée.

[modifier] 2.4. Notion de Motion capture pour les jeux vidéo

Dans la motion capture, on utilise un acteur pour récupérer ses mouvements. Pour ceci, on va disposer sur lui des capteurs. Puis on va utiliser une méthode pour récupérer les mouvements de ces capteurs et les transcrire dans notre format d'animation les keyframes.Remarque : Les capteurs ne sont pas forcément disposés sur des articulations.

Il nous faut pour cela disposer d'un modèle 3D réalisé sous un package 3D avec un mesh et un squelette. C'est sur le squelette que nous allons localiser les points auxquels correspondent les capteurs de l'acteur de manière à répercuter les mouvements de celui-ci sur le squelette du modèle 3D. Dans le cas du jeu vidéo, les mouvements des capteurs sont retranscrits sous forme de keyframes. On utilise aussi un logiciel qui " nettoie " l'animation en enlevant ce qui est superflu.

Voyons précisemment comment l'animation par squelette fonctionne.

[modifier] 3. L'animation par squelette

Nous allons ici étudier les différentes techniques utilisées dans les moteurs de jeux pour animer des personnages, monstres etc.

[modifier] 3.1. Squelette

On parle d'animation par squelette lorsque l'on a un mesh qui est déformé par un squelette. On peut voir ce squelette comme un squelette humain. on va y retrouver des bones tels que : le torse, les bras, avant bras, les cuisses (fémur), les tibias etc. Dans le corps humain, ce sont les muscles qui donnent le mouvement, dans l'animation par squelette, ce sont les bones qui inculquent le mouvement au mesh.

Bien sûr on ne créé un bone que pour les parties que l'on désire animer, c'est-à-dire où l'on veut placer une articulation. Si les doigts d'un mesh n'ont pas besoin d'être animés, on ne placera pas de bones les représentants.

Remarque : Il faut savoir que plus le nombre de bones est grand dans un squelette plus le personnage sera lent à animer. Idem avec le nombre de vertices du mesh, plus il y en aura plus l'animation par squelette sera lente. Nous allons voir pourquoi.

Ce squelette est une représentation hiérarchique de bones. Il y a un parent à toute cette hiérarchie, que nous appelerons lebone root. Quand un bone est attaché à un autre, on parle de parent pour désigner le bone au dessus de lui dans la hiérarchie, de filspour désigner le ou les bones en dessous de lui dans la hiérarchie et de frères pour désigner tous les bones qui ont le même parent.

Voyons ceci sur exemple de hiérarchie de bones :

animation_jv_5.gifFigure 5 : hiérarchie de bones

Chaque nom commençant par " Bip "est un nom de bone dans la hiérarchie. Le bone root est ici Bip01. Chaque décalage indique un nouveau niveau de hiérarchie, les noms au même niveau comme " Bip01 Spine1 " et " Bip01 L Thigh" sont fils du même bone nommé "Bip01 Spine". Le bone "Bip01 Head" a comme parent "Bip01 Neck" et comme fils " Dummy21 ".

Notion de pose : Une pose c'est l'ensemble des matrices de transofrmation des bones à un instant donné. Elles permettent de définir l'état du squelette de manière unique. On parle souvent de pose initiale, c'est celle dont on s'est servi pour associer le mesh au squelette. Dans cette pose spéciale, le mesh n'est pas déformé par le squelette.

La cinématique directe et inverse : on parle de cinématique directe lorsque l'on répercute le mouvement d'un bone sur tous ses fils. Dans le cas ou l'on bouge un bone et que l'on répercute le mouvement sur tous ses parents, on parle de cinématique inverse. On l'utilise par exemple lorsque une main se trouve sur un tiroir, au lieu de faire en sorte que la main tire le tiroir, c'est le tiroir qui pousse la main et on utilise de la cinématique inverse...

La répercution des mouvements du squelette sur les vertices du mesh est appelé skinning.

Remarque : On ne récupère que les clés de rotations sur les bones car entre 2 bones, seul une rotation peut intervenir.

[modifier] 3.2. Skinning

On appelle ce processus skinning car il est utilisé pour déformer un mesh représentant la peau du personnage par l'animation d'un squelette.

Comment fait-on le lien entre le squelette et le mesh ? Il faut que si le bone représentant un bras bouge, les vertices du mesh " proches "du bras bougent en même temps pour représenter sur le mesh la déformation.

Pour cela, on différencie 2 types de skinning le rigidet le smooth (appelé aussi blended). Voyons d'abord le cas le plus simple, le rigid skinning.

[modifier] 3.2.1. Rigid

On parle de rigid skinning lorsque chaque vertex du mesh n'est déformé (on dit aussi influencé) que par un et un seul bone à la fois. Voyons un pseudo-algorithme (non optimisé) Lorsque un bone est animé :

  • on récupère le delta de rotation du bone.
  • on transforme ce delta dans le repère du mesh.
  • on récupère les vertices influencés par ce bone dans le mesh.
  • on applique le delta sur chaque vertex et sur chaque normale au vertex.


Ceci nécessite d'avoir précalculé par quel bone est influencé chaque vertex du mesh. En général, cette opération est faite dans le package 3D, on récupère directement la correspondance vertex --> bone dans le moteur du jeu. Le rigid skinning est peu coûteux mais il a un défaut visible sur les figures suivantes.

Voici un cylindre avec 2 bones à l'intérieur. Les 2 bones déforment le cylindre quand ils bougent.

animation_jv_6.gifFigure 6 : Cylindre avec 2 bones à l'intérieur - bones à l'état initial

animation_jv_7.gifFigure 7 : Cylindre avec 2 bones déformé par rigid skinning

Le rigid skinning ne produit pas des belles déformations aux jointures entre bones, c'est-à-dire aux articulations. On voit sur l'image les bones à l'intérieur du cylindre, le 2e bone a été plié de 90° et les vertices suivant la déformation produisent un effet d'étirement au dessus et un recouvrement en dessous de la pliure.

Pour remédier à cela, on introduit le smooth skinning. C'est le mode de skinning le plus couramment utilisé. Voyons d'abord le résultat que l'on obtient avec cette méthode sur le même cylindre :

animation_jv_8.gifFigure 8 : Cylindre avec 2 bones déformé par du smooth skinning

[modifier] 3.2.2. Smooth

On utilise non plus un seul bone pour influencer un vertex mais plusieurs. Chacun de ces bones a une influence appelée "un poids" sur un vertex. La somme des poids des bones déformant un vertex fait toujours 1. Si on veut qu'un vertex noté V soit influencé à 70% par un bone et à 30% par un autre, ces bones auront respectivement un poids de 0,7 et 0,3 par rapport à V. Remarque : Un poids de 1 indiquerait que seul ce bone influencerait le vertex (rigid skinning). Un poids de 0 indique que le bone n'influencerait pas du tout le vertex.

Dans le rigid skinning, nous avions une correspondance 1 vertex --> 1 bone.

Dans le moothskinning, nous avons 1 vertex --> n bones avec n poids Wi tels que W0+ W1+... Wn = 1.

Le pseudo-algorithme pour le smooth skinning est le suivant :

  • on accède aux matrices des bones par un tableau contenant toutes les matrices. Si on a bien fait les choses, la matrice dans ce tableau est une matrice représentant le delta de rotation des bones exprimé dans le repère local du mesh, de manière à pouvoir l'appliquer directement sur les vertices.
  • Pour chaque vertex :* on récupère les matrices des n bones qui l'influencent ainsi que les poids correspondant à chaque matrice, les poids Wi sont normalisés (la somme vaut 1)
  • On modifie les vertices et les normales au vertex avec la formule suivante : V = M0*V*W0 + M1*V*W1 + ... + Mn*V*WnDans cette formule, Mi est la matrice 4x4 du bone numéro i et Wiest un réel compris entre 0 et 1 représentant l'influence du bone sur le vertex. Et n est le nombre de bones influençant ce vertex.




En pratique : on limite le nombre de bones influençant un vertex à 4 de manière à ce que ce ne soit pas trop lent.

Dans l'animation de presonnages, on se sert aussi d'une autre technique appelée" morphing ". voyons en quoi elle consiste.

[modifier] 4. Le morphing de meshes

Cette technique est assez connue du grand public. Elle consiste à transformer un mesh en un autre de manière progressive. Pour cela, on agit sur les vertices du premier mesh pour qu'ils atteignent les vertices de l'autre mesh progressivement.

Il faut avoir un mesh de référence et des meshes qui seront des cibles de morphing (morph targets). Ces derniers contiendront le même nombre de vertices que le mesh de référence mais avec des coordonnées de vertices différentes du mesh de référence. Il est possible de faire du morphing avec des cibles ne contenant pas le même nombre de vertices mais cela dépasse notre cadre.

Exemple : Voyons un mesh qui va être déformé et ses 2 cibles de morphing.

animation_jv_9.gifFigure 9 : Morphing avec 2 cibles

Nous voyons sur la figure précédente :

  • le mesh de référence le plus à gauche, c'est un cube classique.
  • Deux cibles de morphing : le cube du milieu, appelé ici cible 1 et celui de droite appelé ici cible 2 avec chacun un vertex déplacé par rapport au cube original de gauche. (Il serait possible de mettre plus de différences qu'un seul vertex)
  • Sur cette figure, le mesh de référence n'est pas encore morphé, il est dans sa forme originale.


Le mesh final ( une fois le morphing effectué ) est une combinaison de ces meshes cibles. Pour spécifier comment on doit combiner les meshes cibles pour obtenir le mesh final, on donne un pourcentage à chaque cible.

Par exemple, si nous voulons que le mesh final contienne la forme de la cible 1, on va mettre le pourcentage de celle-ci à 100. Nous obtiendrons le résultat suivant :

animation_jv_10.gifFigure 10 : morphing avec cible 1 à 100%

On voit que notre mesh de référence à gauche s'est transformé en notre cible 1 ( le mesh du mileu) Autre exemple : On souhaite avoir la moitié de la déformation de la cible 1, pour ceci, on met son pourcentage à 50 et on obtient ceci :

animation_jv_11.gifFigure 11 : morphing avec cible 1 à 50%

Ou encore, avec 50% de la cible 1 et 50% de la cible 2, nous obtenons le mesh final suivant :

animation_jv_12.gifFigure 12 : morphing avec 50% de chaque cible Ici le mesh référence, à gauche, est transformé à 50% par chaque cible.

animation_jv_13.gifFigure 13 : le même morphing que précédemment mais vu sous un autre angle

Sur cette dernière figure, le mesh de référence se trouve le plus à droite. Et au final pour le morphing, on spécifie le temps que doit durer le morphing pour que ce changement soit progressif.

Voyons l'algorithme utilisé pour faire ce morphing. Pour cela, introduisons quelques structures : 


struct VertDiff
 {
 Vec3f Diff ;
 int VertIndex ;
 } ;


Ceci va nous permettre de mémoriser les différences de vertices entre le mesh de référence et les cibles de morphing.

Nous avons un mesh de référence. Chaque cible doit avoir le même nombre de vertices que le mesh de référence.

  • On commence par précalculer les différences entre les cibles et le mesh de référence. Pour cela :* On parcourt chaque mesh cible. On compare les coordonnées de chaque vertex avec celui possédant le même index dans le mesh de référence. S'il y a une différence, on mémorise l'index et la différence sous forme de vecteur 3D entre les 2 vertices dans une structure VertDiff décrite précédemment.



  • Nous possédons maintenant pour chaque cible un ensemble de différences avec le mesh de référence entre vertices (VertDiff)
  • Quand l'utilisateur spécifie un pourcentage pour une cible, par exemple il veut 50% de la cible i, on applique ce qui suit :* Pour chaque VertDiff noté vd de la cible i, on prend le vertex correspondant à l'index vd->VertIndex dans le mesh de référence auquel on rajoute 50% de la différence mémorisée dans vd (vd->Diff).




Pour animer ceci au cours du temps, on fait une interpolation de type linéaire entre chaque différence de vertex de la même manière qu'au paragraphe sur les keyframes.

Pour faire le parallèle avec l'animation par keyframe, nous sommes dans un cas où nous pouvons considérer que nos clés d'animation sont : pour celle de départ, la position du vertex de référence et pour celle d'arrivée : la position du vertex de référence à laquelle on a ajouté la différence de vertex de ses cibles pondérées par le pourcentage rentré par l'utilisateur.

En pratique : On réalise par exemple l'animation faciale avec du morphing. C'est-à-dire que chaque phonème est représenté par une cible de morphing.

[modifier] 5. Glossaire

Ce glossaire comprend les divers termes que l'on retrouve dans ce document, il n'a pas pour prétention de détenir la définition mais juste de proposer une des définitions possibles. La plupart de ces termes comprennent des mots en Anglais car le language du jeu vidéo est basé sur des termes Anglais.

  • L'animation dans un jeu vidéo : L'animation sert à donner vie aux différents éléments du jeu (personnages, décors, etc.) pour servir son immersion et son esthétique.
  • Clés d'animation (Keyframes) : ce sont des informations retenues à un temps donné pour un objet, elles peuvent contenir par exemple une translation, une rotation ou un scale. On parle aussi du temps d'une clé qui est le temps auquel s'applique les informations retenues dans cette clé. En plus ce cela, on peut avoir des tangentes d'entrée et/ou de sortie d'une clé ou encore des paramètres pour reconstruire les tangentes.
  • Tangentes d'une clé d'animation, on différencie 2 tangentes pour une même clé, il y a la tangentein et out, In pour"arriver sur la clé" et out pour "quitter la clé". Ces tangentes représentent un moyen de spécifier une vitesse et une direction pour arriver ou repartir d'une clé.
  • Interpolation : L'interpolation permet, à partir de 2 clés existantes, de calculer une valeur intermédiaire à un temps donné permettant de relier les 2 clés. On parle d'interpolation linéaire, de Bézier, d'Hermite, en TCB, en spline etc. Ces types d'interpolation permettent tous de passer d'une clé à une autre mais par des chemins différents.
  • Vertex : dans notre cas, c'est un point faisant partie d'une géométrie qui a une représentation 3D. Au pluriel, on parle de vertices.
  • Faces : les vertices d'un objet 3D sont regroupés en général par 3 pour former un triangle appelé face.
  • Mesh : c'est un objet géométrique 3D composé entre autres de vertices et de faces. On dit meshes au pluriel.
  • Bones(os) : c'est un des composants du squelette en animation de personnages de la même manière qu'un os est un composant du squelette humain. Il y a analogie entre les deux.
  • Squelette : ensemble des bones. Le squelette permet de déformer les meshes comme nous allons le voir dans l'animation des personnages. Entre 2 bones se trouve implicitement une articulation.
  • Boucle de jeu : C'est l'ensemble des fonctions du jeu qui sont appelées continuellement. On y retrouve l'affichage de la scène, la gestion du clavier ou de la manette, la gestion des sons etc. Il est cependant possible de n'appeler certains des composants de la boucle qu'une fois sur deux comme par exemple la gestion des entrées. Ceci afin de ne pas surcharger la boucle quand ce n'est pas nécessaire.
  • Frame : on dit par exemple qu'un jeu tourne à 60 FPS (frame per seconds), soit 60 images par secondes. On appelle ceci la vitesse d'affichage. Une frame correspond à un appel de la boucle du jeu.
  • Transformation : c'est ce qui contient la translation, la rotation et le scale d'un objet. On utilise souvent des matrices 4 x 4 comme dans Direct X. Cette transformation permet lorsque l'on a un vertex dans le repère du mesh de le passer dans le repère du monde en prémultipliant ce vertex par la transformation du mesh.
  • Courbe d'animation : lorsque l'on a une animation, par exemple sur une translation, il est possible de voir l'animation sur chaque composante x, y et z de cette translation. On obtient donc une courbe avec en abscisse le temps et en ordonnée la valeur de la composante à ce temps. C'est cette courbe qui est appelée la courbe d'animation.
  • Package 3D : on désigne sous ces termes un logiciel de 3D permettant la modélisation et l'animation d'objets 3D. On peut citer ici les logiciels les plus connus : 3D Studio MaxTM de Discreet, MayaTM d'Alias Wavefront ou encore XSITM/SoftimageTM d'Avid.
  • Moteur de jeu : programme éxécutable regroupant les fonctionnalités basiques nécessaires à un jeu telles que l'affichage 3D, le son, la gestion des entrées (clavier, joystick), le gestionnaires de fichiers etc.
  • Phase d'export : pour récupérer les données graphiques provenant d'un package 3D, comme les meshes, textures, animations etc. On passe par une phase d'export. On exporte ces données du package 3D dans un format de fichier spécifique au moteur de jeu que nous développons.
  • Animation faciale : c'est une animation qui tend à faire correspondre ce que dit un personnage avec les mouvements de son visage et particulièrement sa bouche.
  • Phonème : c'est la plus petite unité du language parlé. On lui associe une forme de bouche particulière qui correspond à cette sonorité. On l'utilise en animation faciale.


[modifier] 6. Références

Certains de ces liens peuvent ne plus exister au moment où vous lisez ceci.

Programmation des jeux vidéo

[ 1 ] http://www.gamasutra.com: site web référence en matière de développement de jeux vidéo.

[ 2 ] http://www.darwin3d.com : site avec du code source récupérable.

[ 3 ] http://www.gamedev.net: articles.

[ 4 ] http://www.flipcode.com: articles avec code source.

[ 5 ] http://www.magic-software.com: théorie et code source récupérable, programmation graphique.

L'animation par ordinateur

[ 6 ] http://www.cs.virginia.edu/~dbrogan/CS551.851.animation.sp.2000/ : site contenant des références telles qu'articles, autres sites webs et livres.

[ 7 ] http://www.cis.ohio-state.edu/~parent/book/outline.html : algorithmes et techniques de l'animation par ordinateur.

[ 8 ] http://www.theory.org/software/qfa/writeup/writeup.html : algos de caméras, keyframes, slerp, squad quaternions.

[ 9 ] http://cs1.cs.nyu.edu/phd_students/sudo/toy/graphics/hw5.html : applet pour visualiser des courbes, splines etc.

Physique

[10] http://www.batesville.k12.in.us/physics/PhyNet/default.html

[modifier] 7. Remerciements

Merci à tous ceux qui m'ont aidé à rédiger ce cours. Particulièrement Jean-Paul Digeon, Bruno Plantier, Fabrice Carré, Thierry Puginier, Gabriel Grasso, Stéphane Bura et Patrick Chen de Kalisto Entertainment.

(aucun commentaire actuellement)

ajouter un commentaire
Récupérée de « http://www.games-creators.org/wiki/L%27animation_temps_r%C3%A9el_dans_les_jeux_vid%C3%A9o »