L´ANIMATION

Introduction
Méthodes traditionnelles
Animation procédurale
Cinématique inverse
Méthodes dynamiques
Méthodes comportementales
Méthodes connexionnistes
Méthodes évolutionnistes
Application à l´animation de personnage
Le temps réel
Bibliographie

















































Introduction

         La simulation des méthodes de l´animation traditionnelle a été, et reste encore, prépondérante, surtout dans le monde de la production: Probablement pour des raisons de rentabilité immédiate, il est en effet plus facile de faire comme avant plutôt que d´innover:


Interpolations (simulation de la méthode des dessins clés).



Utilisation de la 3D pour résoudre les problèmes de l´interpolation 2D.

Mouvements relatifs d´objet rigides avec variations des caracteristiques de la caméra virtuelle (simulation d´animation de marionnettes).
        
Applications de la robotique pour des objets rigides articulés animés de mouvements de rotations et de translations. La cinématique inverse règle les problèmes d´animation à buts.

Depuis les années 80, la recherche s´oriente vers l´utilisation de modèles dynamiques:
         Simulation de mouvements réalistes d´objets pesants soumis à des champs de force.
         Simulation d´animation d´objets souples caratérisés par des propriétés mécaniques (raideur, élasticité, ...)
         Résolution des problèmes de détection de collisions et de réponses aux chocs.
         Simulation de mouvements turbulents de fluides et de gaz (thermodynamique).

Depuis les années 80-90, avec Reynolds [Reynolds 82], est apparue l´animation comportementale:
         Créationd d´acteurs munis de comportements quasi vivants permettant de résoudre des situations impliquant un grand nombre d´individus ayant des interactions complexes.
Depuis les années 90, des modèles connexionnistes, évolutionnistes [Goldberg 91] [Dessalles 96] et de la vie artificielle [Heudin 94], s´inspirant de la biologie, ouvrent la voie à la simulation de la vie.

Renouvelant l´ancienne conception de la représentation comme "mimésis", ces nouvelles approches visent à simuler le fonctionnement plutôt qu´à vouloir rendre l´apparence: La dynamique simule le monde des choses, le connexionisme et l´évolutionnisme simulent celui des êtres.
         Dans les prochaines années, les techniques d´animation vont intégrer les nouvelles connaissances issues de la "Vie Artificielle" [Ray 1994] [Sims 1994], [Heudin 1994].

Méthodes traditionnelles

Interpolations
Morphings
Méthodes cinématiques
Interpolation basée sur un modèle physique
Boites déformantes

Interpolations

         Nous évoquerons, pour mémoire, l´interpolation linéaire, qui n´est qu´une modélisation très simplifiée de la méthode dite des dessins clés (key framing) inventée par Walt Disney dans la première moitié du siècle dernier:
         Une représentation paramétrique de la droite passant par deux points distincts M1 et M2 est donnée par:
         M(t) = M1 + (1-t)*(M2-M1) avec t variant de - l´infini a + l´infini.
         Pour t variant de - l´infini à 0 le point M(t) dàcrit la demi droite à gauche de M1.
         Pour t variant de 0 à 1 le point M(t) décrit le segment [M1M2].
         Pour t variant de 1 à + l´infini le point M(t) décrit la demi droite à droite de M2.



         Pour animer une entité géométrique G par la méthode des dessins clés on définit un ensemble de positions clées G1, G2, ..., Gn devant être atteintes aux instants t1, t2, ..., tn puis, pour chaque couple [Gi,Gi+1] on applique la formule précédente en mappant l´intervalle des temps [ti,ti+1] sur le segment [0,1].
         Les inconvenients de cette méthode sont évidents:
         1) Déplacements linéaires à l´exclusion de tout mouvement courbe ce qui peut provoquer des positions intermédiaires arbitraires.



         Une meilleure animation est obtenue en déplacant et en tournant progressivement l´objet.



         2) Vitesses constantes sur chaque intervalle, alors que les mouvements réels (en particulier ceux du vivant) sont variés. On n´insistera jamais assez sur l´importance des accélérations dans la perception du mouvement (le système perceptif est en effet sensible aux variations et l´accélération est une variation de la vitesse).
         t = t1 + k * (t2 - t1) fournit un mouvement uniforme par morceaux (à vitesse constante sur chaque intervalle).
         Pour remédier à cet inconvenient on peut remplacer la variation uniforme k par une fonction f(k):
         t = t1 + f(k) * (t2 - t1)
Par exemple:
         f(k) = 1 - cos(0.5 * k * PI) fournit un mouvement accéléré.
         f(k) = sin(0.5 * k * PI) fournit un mouvement décéléré.
         f(k) = 0.5 * (1 - cos(k * PI)) fournit un mouvement pendulaire
         3) Discontinuités du premier ordre (des vitesses) aux passages par les positions clées, ce qui provoque des sautes d´animation (dues à une accélération infinie). Soient en effet M1, M2 et M3 trois poistions clées non alignées, à l´instant t2-e/2 la vitesse V1 est portée par le segment M1M2, et à l´instant t2+e/2 la vitesse V2 est portée par le segment M2M1. V1 et V2 sont donc très différentes et le rapport (V2-V1)/e tend vers l´infini lorsque e tend vers 0.


Morphings

         Soient deux images pixel I1 et I2, on cherche une transformation de I1 en I2:
        f: I1 -> I2
        En général f n´est pas une surjection, alors que la transformation inverse f-1 l´est.


C´est la raison pour laquelle on définira un morphing de I2 dans I1, le problème étant: Pour chaque pixel de I2, quel pixel de I1 faut-il échantillonner ?
        Transformations géometriques
        Convolutions
        Méthode par paires de segments
        Transformation de Fourier

Méthodes cinématiques

         Les interpolations, les trajectoires et les lois de mouvements permettent de contrôler les objets dans l´espace et dans le temps:
        Géométrie: Formes, positions et orientations de volumes, de caméras, de lumières, etc...
        D´une façon plus générale tout paramètre:
                Sommet particulier d´un objet
                Couleurs
                Modèles d´éclairement,
                Coefficients d´extension courbe
                etc...
        Des objets rigides (c´est a dire dont la géométrie varie à distances constantes) sont animés par des transformations linéaires. Rappelons qu´en coordonnées homogènes les translations, les dilatations et les rotations de l´espace à 3 dimensions s´expriment par des matrices 4X4. Il suffit donc d´associer à chaque objet rigide un repère local dont la position et l´orientation sont définies par une matrice le transformant par rapport à son père (dans une structure hiérarchisée par exemple).
        Notons qu´il est préférable de définir l´orientation d´un objet rigide, non pas par ses 3 angles d´Euler, mais par un
        quaternion q = (c,x,y,z)
avec teta = angle de rotation autour du vecteur (x,y,z) de module sin(teta) et avec c = cos(teta/2).
En effet le mouvement le plus général d´un solide est, à chaque instant, tangent à un mouvement hélicoidal.
        Pratiquement un algorithme d´animation se présente comme suit:

Pour numéro d´image variant de 1 à ni, faire:
        Pour chaque objet faire:
                Si l´objet est rigide, calculer sa matrice et l´appliquer à tous ses sommets (en programmation OpenGL il suffit d´appeler les fonctions correspondant aux transformations successives avec les paramètres adéquates).
                Sinon, pour chaque sommet de l´objet:
                        le placer sur sa trajectoire à l´image courante
        Afficher les volumes.
        Stocker éventuellement l´image sur le disque


        Classiquement on utilise des représentations paramétriques de trajectoires. (cubique), (Bezier), (Spline), (Beta Spline), (Nurbs), P(t) dépendant d´un paramètre t (usuellement le temps)
        Le vecteur vitesse à l´instant t est donné par la dérivée P´(t) de la position OM= P(t), il est porté par la tangente à la trajectoire en P(t). Si s(t) est l´abscisse curviligne on a:
        V(t) = s´(t) u, avec u = dOM/ds vecteur unitaire de la tangente
        Le point P défini par OP = u décrit une courbe de la sphère (O,1) (hodographe du mouvement) d´abscisse curviligne z, le vecteur n = dz / ds est le vecteur unitaire tangent à la sphère, qui est appelé vecteur normal en M à la trajectoire P.
        Le vecteur accélération A = dV / dt se décompose en:
        At = accélération tangente portée par u
        An = accélération normale portée par n
        Le vecteur b = u ^ n complête le trièdre de Serret-Frénet. Ce trièdre constitue un repère local tangent à la trajectoire commode pour déplacer l´objet tangentiellement à sa trajectoire.




        Si le paramètre de la trajectoire n´est pas le temps, il est possible de graduer cette courbe en fonction du temps par une loi de mouvement. Celle-ci est en général une Spline donnant l´abscisse curviligne s sur la trajectoire du point M en fonction du temps:


Interpolation basée sur un modèle physique

         On remplace deux courbes à interpoler par deux corps physiques affectés de propriétés dynamiques (masse, raideur, élasticité, ...), et on cherche la transformation de l´un en l´autre qui minimise le travail des forces (d´élongation, de courbure, ...) [Sederberg 92].

Interpolations 3D

         Si l´interpolation 2D pose quelques problèmes, l´interpolation 3D soulève de vraies questions, en particulier quant aux topologies des volumes à transformer l´un dans l´autre. En effet on attend d´une telle transformation des propriétés de régularités et de continuités qui ne sont pas nécessairement remplies pour des topologies différentes. Comment par exemple transformer une sphère en un tore ?



         Le premier problème est celui de la correspondance entre les points des 2 volumes. On se limitera à des surfaces polyédriques dont on interpolera les sommets (et non pas tous les points des 2 surfaces).
         Le deuxième problème est celui de l´interpolation elle-même (linéaire, par trajectoires, modèle physique, ...) qui dépend du premier.
Kent [Kent 92] décrit un algorithme pour des polyèdres sans "trou":
         Soient A et B deux tels polyèdres de topologies T(A) et T(B).
         On projète T(A) et T(B) sur la sphère unité.
         Om "mélange" les deux topologies par clipping d´une surface sur l´autre et réciproquement, pour obtenir une topologie T(AB) contenant les deux précédentes.
         On mappe la topologie résultante T(AB), ce qui fournit deux nouveaux polyèdres ayant la même topologie T(AB). Il est alors possible d´établir une bijection entre leurs sommets respectifs.





Modèles de base --> Projection --> Clipping --> Mélange --> Nouveaux modèles

Cette méthode ne fonctionne bien qu´à condition que la projection sur la sphère soit:
         1) Une bijection (pas de points confondus);
         2) Continue, c´est à dire que:
         proj(voisinage) inclu voisinage(proj)
C´est le cas pour un polyèdre à topologie radiale (ou stare shaped), c´est à dire un volume pour lequel il existe au moins un point intérieur depuis lequel on voit tous les sommets de la surface. Ce point appartient à l´intersection de tous les demi espaces limités aux facettes et ne contenant pas la normale (noyau du polyèdre). Il suffit de prendre le centre de gravité du noyau pour centre de projection.


Boites déformantes


              Déformation d´une surface paramétrique

              FFD

              EFFD

              Expression faciale

Déformation d´une surface paramétrique

       Un ensemble de points de contrôle Pi,j et une représentation paramétrique polynomiale permet d´engendrer une surface courbe a partir d´un petit nombre de parametres (les coordonnees des points de contrôle et les coefficients de la representation). La propriete d´ enveloppe convexe de ces surfaces garantit que la surface reste dans l´enveloppe convexe du polyèdre ayant pour sommets ses points de contrôle, il suffit donc d´animer ces points pour animer la surface.
         Au cours d´une telle animation la courbure en un point de la surface peut diminuer et il peut être utile de subdiviser localement la surface (en ajoutant des points de contrôle).

FFD (Free-Form Deformation)

         Cette méthode, due à Sedeberg [Sedeberg 86], consiste à déformer, non pas un volume, mais un espace l´englobabant. Une image du procédé serait un volume pris dans un cube de plastique que l´on déformerait, entraînant la déformation de ce volume (une méthode alalogue est utilisée dans un mapping d´une image 2D sur une surface paramétrique de l´espace).
         De même que l´on a défini une courbe deBézier ou une surface de Bézier on peut définir un hyper patch de Bezier:
         P(u,v,w) = somme(i=0,3;j=0,3;k=0,3) Pi,j,kBi(u)Bj(v)Bk(w)
qui génère un volume paramétrique. Il suffit de déplacer les points de contrôle Pi,j,k pour animer la boîte englobante, puis de mapper le volume dans la boîte déformée.


Boîte de base --> Ajustée sur le volume --> Déformer la boîte --> FFD

EFFD (Extended Free-Form Deformation)

         Sabine Coquillard [Coquillard 90] remblace la boîte parallélépipédique des FFD par une grille 3D ajustée au volume à déformer. Par exemple un volume convexe proche d´un cube sera bien approché par une grille cubique, un volume très long et étroit sera mieux approché par une grille parallélépipédique allongée, un volume proche d´un tore sera mieux approché par une grille 3D en forme de tore, etc...


Expression faciale

         Keith Waters [Waters 87] définit un modèle paramétrique de muscles contrôlant les déformations d´une surface polyédrique représentant un visage humain (saisi par exemple au Cyber_Ware) à partir du système de notation FACS (Facial Action Coding System) [Ekman 77] repris par Badler [Badler 81]. Les points de contrôle de différents visages sont activés par des muscles paramétriques attachés à ces points, alors que les mouvements dynamiques produisant des expressions sont activés par un modèle abstrait de muscles.
        Les muscles linéaires tirent la peau, tandis que les muscles sphincters ouvrent la bouche ou les yeux.
        Bien qu´encore couramment employé, ce modèle est dépassé et on lui préfère aujourd´hui une modélisation anatomique. voir aussi /art/1998/une_methode_comportementale une méthode comportemental de modélisation et d´animation du corps humain.

Animation procédurale

        Les méthodes précédentes simulent en particulier les techniques classiques d´animation, elles en ont les avantages (contrôle exhaustif) mais aussi les inconvenients (impossibilité de gérer des événements complexes ou imprévisibles). L´animation ´procédurale´ consiste à générer une séquence animée non pas par des descriptions géométriques mais par des procédures. Alors que les méthodes traditionnelles priviligient l´intervention manuelle de l´animateur (dessins clés), l´animation procédurale lance des processus automatiques (modèles mathématiques ou physiques) dépendant du temps.
        Par exemple un système de particules implique une telle démarche [Reeves 83]. Un système de particules est un objet flou constitué d´un très grand nombre de petits éléments caracterisés par:
        Position initiale
        Vitesse initiale
        Paramètres de taille, de couleur, de transparence, de forme, ...
        Date de naissance et durée de vie
        Leurs mouvements sont gérés par des méthodes dynamiques en 4 passes pour chaque image:
        1) Création de nouvelles particules.
        2) Suppression des particules ayant excédées leur durée de vie.
        3) Les particules sont mues par la dynamique.
        4) Le système est affiché.
        Afin de simuler le comportement stochastique des particules formant par exemple un nuage, la création de nouvelles particules peut suivre une loi du genre:
        N(t) = M(t) + rand(r) * V(t)
        N(t) = Nombre de particules générées à l´instant t
        M(t) = Nombre moyen de particules
        rand(r) = Variable aléatoire
        V(t) = Variance, ou mesure de la dispersion.
        Un script peut contrôler la géometrie de sources (générations) ou de puits (disparitions) de particules dans le temps.
        Pratiquement il suffit d´exécuter, à chaque image, une certaine fonction.
        Un algorithme d´animation procedurale se présente comme suit:

Pour numéro d´image variant de 1 à ni, faire:
        exécuter la fonction pour l´image courante.
        Afficher les volumes.
        Stocker éventuellement l´image sur le disque


        Une telle fonction analysera par exemple la scène à un instant donné, détectera des collisions et décidera de modifier certains mouvements en conséquence.
        Un des avantages d´une telle méthode est qu´elle peut gérer des événements extérieurs (interaction) imprévisibles. Un autre avantage est que la fonction peut être spécifique à une animation particulière.
        C´est une méthode très employée en production.

Cinématique inverse


       Structure articulée

       Cinématique directe

       Cinématique inverse

       Résolution par la méthode du Jacobien

Structure articulée

        Ensemble de liens rigides connectant des joints.
        Arbre représentant une structure articulée d´objets rigides.
        Degré de liberté: Nombre de variables indépendantes nécessaires pour spécifier l´état d´un joint:
                1: Déplacemnet le long d´un axe.
                2: Rotation autour d´un axe et déplacemnet sur cet axe (mouvement helicoidale).
                3: Rotation de type rotule.
        Les feuilles de l´arbre sont appelées effecteurs terminaux (end effector).
        L´état d´une structure articulée peut être représentée par un vecteur:
        T = (T1, T2, ..., Tn)
dont les composantes sont toutes les variables Ti définissant la configuration de cette structure. Leur ensemble forme l´espace des états, qui est un espace vectoriel dont la dimension est le nombre de degrés de liberté de la structure.
        Par exemple tout objet rigide non contraint a 6 degrés de liberté (3 composantes de translation et 3 angles de rotation), son vecteur d´état s´écrit:
        (x, y, z, rx, ry, rz)
        Animer une structure articulée dont l´espace des états est de dimension N revient à trouver une trajectoire dans cet espace.

Cinématique directe

Voir [Watt 1992].         Les mouvements de chaque joint Ti sont donnés explicitement par l´animateur, le mouvement X d´un effecteur terminal est obtenu en cumulant (par produit de matrices) les mouvements de ses parents:
        X = f(T1, T2, ..., Tn) = f(T)
        Une telle méthode devient rapidement inextricable lorsque la compléxité de la structure augmente.

Cinématique inverse

        Dans cette méthode, encore appelée animation dirigée vers un but, l´animateur ne donne que le mouvement X de l´effecteur terminal, les mouvements T des joints sont alors donnés par:
        T = f-1(X)
        Le problème est que, pour une structure complexe (dans le cas de nombreuses liaisons), l´inverse de la fonction f peut être difficile à trouver (il peut y avoir plusieurs solutions, ou même ne pas y en avoir).

Résolution par la méthode du Jacobien

        Soit X = f(T) n = dimension(X), m = dimension(T)
        En différentiant:
        dX = J(T) dT
        avec J = Jacobien de la fonction f, qui est la matrice de n lignes et m colonnes dont chaque élément est:
        Ji,j = d fi / d Xj
        différentielle partielle de fi par rapport à Xj.
        En notations dérivées (en divisant par la différentielle du temps):
        dX / dt = J(T) dT / dt, soit: X´ = J(T) T´
        X´ = vitesse de l´effecteur terminal qui est généralement un vecteur à 6 dimensions constitué de la vitesse linéaire V et de la vitesse angulaire A.
        Le jacobien J permet de passer de la vitesse T´ de l´espace des états à la vitesse X´ dans l´espace cartésien des positions de l´effecteur terminal.
        Reprenant l´équation X´ = J T´ on obtient:
        T´ = J-1
        Si on sait inverser la matrice J (ce qui est plus facile que d´inverser une fonction f), la connaissance de X´ conduit à celle de T´.
        Pour des intervalles de temps dt petits on peut confondre la dérivée X´ avec (X(t+dt) - X(t)) / dt (méthode de linéarisation), de même on peut confondre la dérivée T´ avec (T(t+dt) - T(t)) / dt.

A l´instant t=0 on suppose que l´on connait la fonction f, T(0) et T´(0) (conditions initiales), on en déduit le jacobien J de f puis:
        X(0) = f(T(0))
        X´(0) = J T´(0), puis X(dt) = X(0) + dt*X´(0):

A l´instant dt on aura:
        T´(dt) = J-1 X´(dt) soit:
        (T(dt) - T(0)) = J-1 (X(dt) - X(0))
        Comme on connait X(dt), X(0) et T(0) on en déduit T(dt), puis.
        X´(dt) = J T(dt)
        X(2*dt) = X(dt) + dt*X´(dt)

Et ainsi de suite itérativement. Mais, à chaque pas, l´approximation d´une dérivée par un quotient introduit une erreur qui est cumulée lors des calculs ("tracking error"), on la minimise en réduisant dt.

Méthodes dynamiques


       Principe

       Exemple

       Linéarisation

       Dynamique des surfaces souples

Principe

       La technique précédente autorise un contrôle plus systématique et permet de simuler une infinité d´effets, parmi ceux-ci figurent les lois naturelles (par exemple la mécanique) dont il suffit d´écrire les équations dans les fonctions appellées à chaque image. Pour simplifier ce travail certains algorithmes classiques sont écrits ´en dur´, c´est le cas par exemple des lois de la dynamique des corps pesants, des ressorts, des structures articulées, des chocs, etc...
        Pratiquement celà revient à ecrire les équations de la Mécanique Newtonienne et à les résoudre par rapport au temps:
        f(F, P, V, A) = 0 avec:
        F(t) = Forces
        P(t) = position
        V(t) = dP / dt = Vitesse
        A(t) = dV / dt = Accélération

Exemple

        Soit un point matériel de masse m et soumis à une force verticale F=(0,-g,0) supposée constante. A l´instant 0 on suppose que P(0)=(x(0),y(0),z(0)) et que V(0)=x´(0),y´(0),z´(0). A chaque instant t L´équation vectorielle:
        F = m * A(t) se décompose en 3 équations algébriques:
        x" = 0, soit x´ = x´(0), soit x = x´(0)*t + x0
        y" = -g, soit y´ = -g*t + y´(0), soit y = -g*t*t/2 + y´(0)*t + y(0)
        z" = 0, soit z´ = z´(0), soit z = z´(0)*t + z0
        Ces 3 équations x(t), y(t) et z(t) constituent une représentation paramétrique d´une parabole, qui est effectivement la trajectoire d´un corps pesant lancé avec une vitesse initiale v0 dans le champ de la pesanteur.


Linéarisation

        Mais, dans le cas général (champ de forces non constant, masses variables, corps déformables, chocs, ...) on arrive rapidement à des systèmes d´équations différentielles qu´on ne sait pas résoudre.
        La méthode de linéarisation consiste à confondre, sur un intervalle dt petit du temps, une dérivée avec l´accroissement relatif de la fonction, c´est à dire:
        df / dt ~ (f(t+dt) - f(t)) / dt
        L´erreur commise diminue avec dt.
       






        De F = m * A(t) on déduit M(t) connaissant M(t-dt) et M(t-2*dt).
A l´instant 0 on suppose connus M(0), V(0) et A(0), on en déduit:
        M(dt) = M(0) + dt*V(0), V(dt)=V(0)+dt*A(0) et donc M(t+2*dt)=M(t+dt)+V(dt)
A l´instant dt+2*dt, on a:
        F = (M(t+2*dt)-2*M(t+dt)+M(t))/(dt*dt)
        Comme M(t) et M(t+dt) sont connus, on en déduit M(t+2*dt)
        Et ainsi de suite de façon itérative. Il suffit donc de conserver en mémoire deux positions antérieures pour pouvoir développer, de proche en proche, l´animation dynamique.
        L´erreur commise en remplaçant une dérivée par un quotient s´accumule au cours des calculs, pour la minimiser on diminue dt. Pour une animation de par exemple 25 images par seconde on partage l´intervalle de temps entre deux images en, par exemple, 5, ce qui revient à prendre dt = 1/(5*25) soit dt = 0.008 seconde. De toutes les itérations effectuées, seule une sur 5 sera effectivement affichée.
        Cette méthode, bien qu´entachée d´une erreur non négligeable, permet cependant de générer une animation dynamique de complexité arbitraire, très rapidement (temps réel), sans avoir à résoudre de systèmes d´équations différentielles. En outre elle peut être utilisée pour résoudre les problèmes d´aliasings temporels.

Dynamique des surfaces souples

         Weil [Weil 86] propose une méthode pour animer des tissus suspendus dans l´espace 3D. Une pièce de tissus (supposée inextensible) est assimilée à une grille suspendue par certains points et placée dans un champ de pesanteur vertical, et le problème consiste à trouver sa position d´équilibre. Une solution purement mathématique est pratiquement impossible, Wein a retenu une solution itérative à partir d´une position initiale.
        Dans un premier temps la surface est approximée dans l´enveloppe convexe de ses points fixes. Pour celà une chainette
        y = acosh(x/a) = 0.5 * a (exp(x/a) + exp(-x/a))
modélise le comportement physique d´un fil réel de longueur fixe suspendu en deux points.
        Dans un deuxième temps les contraintes sont prises en compte lors de petits déplacements jusqu´à ce que ceux-ci tombent en dessous d´un seuil minimal préfixée. Un algorithme de relaxation déforme peu à peu la surface en s´assurant que les distances d´un point de la grille à ses voisins ne varie pas.


Méthodes comportementales

        Les techniques précédentes s´appliquent bien à l´animation d´objets physiques mais échouent avec les êtres vivants qui obéissent, en plus, à d´autres lois dites ´comportementales´ (par référence au comportement d´un être face à une situation donnée)
        Les langages procéduraux traditionnels ne suffisent pas pour gérer des acteurs munis de comportements, et il faut faire appel aux langages dits ´orientés objets´ dans lesquels les structures de données intégrent non seulement des ´datas´ (physique) mais aussi du ´code´ (intelligence)
        Reynolds [Reynolds 82] introduit l´animation d´acteurs, en particulier pour gérer un grand nombre d´objets en interaction (des bancs de poissons, des vols d´oiseaux, ...). Il ne s´agit plus de déterminer de façon exhaustive les mouvements de chaque individu, mais de donner des règles de comportement, des protocoles d´échanges de messages entre individus; les mouvements résultent alors d´un équilibre atteint par une telle structure dynamique. Le bien fondé de la méthode trouve sa justification dans l´excellence des résultats obtenus.
        Il s´agit d´un système de particules [Reeves 83] particulier pour lequel les particules:
        1) Ne sont pas indépendantes mais interagissent les unes avec les autres pour simuler le comportement d´une colonie.
        2) Sont des objets pouvant être eux-mêmes animés.
        3) Obéissent à plusieures règles:
                regle 1: Eviter les collisions avec les voisins les plus proches.
                regle 2: Ajuster sa vitesse avec celle des voisins.
                regle 3: Rester proche de ses voisins.
        Un tel système simule très bien un vol reel d´oiseaux suivant globalement leur leader, pouvant éviter des obstacles (pouvant même se séparer en plusieurs vols pour se rejoindre après) et montrant un comportement proche du vivant.

Méthodes connexionnistes

        Au lieu de construire des mouvements dépendant d´un contexte donné, ce qui oblige à tout refaire lorsque le contexte change, il est préférable de munir les acteurs de comportements. Mais, quelle que soit la complexité de ces comportements, ils sont programmés et ne s´appliquent qu´à des situations prédéfinies.
        Une méthode, inspirée du connexionnisme, (Les réseaux de capteurs actuateurs) consiste à définir des acteurs munis de comportements neutres susceptibles d´apprentissage. Une technique efficace est de construire des systèmes adaptatifs munis:
        1) De capteurs
        2) D´un réseau neuronal
        3) De moteurs
        Les capteurs sont connectés à la couche d´entrée du réseau et les moteurs sont connectés à la couche de sortie. Une ou plusieurs couches cachées complexifient le réseau. Puis l´acteur subit un apprentissage supervisé au cours duquel il apprend à répondre à un ensemble de situations testes. À l´issue de cet apprentissage l´acteur non seulement répond correctement aux situations qu´il a appris, mais, de par la propriété de généralisation des réseaux neuronaux, il répond de façon cohérente à des situations nouvelles. (voir les réseaux neuronaux dans anyflo).

Méthodes évolutionnistes

        La recherche de stratégies par des méthodes analytiques et l´écriture d´algorithmes pour résoudre les problèmes ont montré leurs limites qui sont en fait celles de notre cerveau. Mais celui-ci possède, comme d´ailleurs les ordinateurs, la facultè très remarquable de pouvoir tout simuler et même ce qui le dépasse. C´est ainsi qu´en s´inspirant de la théorie de l´évolution de Darwin, John Holland [Holland 75], dans les années soixantes dix, inventa les algorithmes génétiques (algorithmes génétiques). Nous les utilisons en animation de synthèse pour résoudre des problèmes trop complexes (comme la construction des comportements d´un être artificiel) ou mal posés (comme des réponses à une interaction avec un humain ne connaissant pas nécessairement le système avec lequel il interagit). (Voir les algorithmes génétiques dans anyflo).
(application à la synthèse). ("danse avec moi").
(Évolution de créatures virtuelles).

Application à l´animation de personnage

Modélisation dynamique du corps
Modélisation anatomique du corps
Modélisation des cheveux et des vêtements
Animation comportementale
Application des modèles connexionnistes et évolutionnistes

Modélisation dynamique du corps

         David Zetlzer [Zetlzer 1982] utilise, dès 1982, la notion de "moteur de contrôle" pour gérer l´animation de structures articulées, à laquelle il adjoint celle de processeur de mouvement préfiguration de ce que seront les comportements.
         Les travaux de Demetri Terzopoulos, bien que ne traitant pas spécifiquement des corps vivants, sont à la base de l´animation dynamiques de surfaces souples [Terzopoulos 1987], utilisée pour modéliser les muscles et la peau.
         Gavin Miller [Miller 1988] a introduit l´usage des ressorts dans la simulation de muscles moteurs pour animer des serpents et des vers.
         Armin Bruderlin [Bruderlin 1989] décrit la locomotion humaine par un modèle dynamique du mouvement des jambes qu´il associe avec une direction "à but", anticipant par là les travaux sur l´intentionnalité.
         Michael McKenna [McKenna 1990] anime des figures articulées en appliquant la mécanique Newtonienne, il introduit également les notions de "contrôleur de marche" et de "programme moteur".
         Marc Raibert [Raibert 1991] applique la robotique au contrôle dynamique de la locomotion d´êtres artificiels bipèdes.
         Jessica Hodgins [Hodgins 1995] simule des comportements athlétiques (courir, faire du vélo, sauter, ...) par des modèles dynamiques compatibles avec des données biomécaniques. Elle adapte aussi ces comportements à des acteurs quelconques [Hodgins 1997].

Modélisation anatomique du corps

         Keith Waters [Waters 1987] introduisait une méthode de paramétrisation d´un modèle facial simulant l´action superficielle des muscles du visage pour synthétiser des expressions. Yuencheng Lee [Lee 1995] reprend cette méthode en l´automatisant et en lui associant un modèle dynamique.
         Zajac [Zajac 1986] [Zajac 1989] a développé le 1er modèle de muscles appliqué à la synthèse du corps humain.
         John Chadwick [Chadwick 1989] a developpé un système d´aide à l´animation traditionnelle de personnages basé sur une structure en "couches" fournissant divers niveaux de contrôle.
         Les Thalmanns [Magnenat-Thalmann 1991] decrivent des procédures attachées aux noeuds d´une structure articulée ("joint-local deformations") pour simuler des changements naturels de la forme des membres.
         David Chen et Zetlzer [Chen 1992] avaient proposés en 1992 de produire les déformations d´un corps mobile en simulant l´action des muscles et les forces qu´ils exercent sur le squelette. Pour cela ils avaient développé un modèle basé sur la biomécanique et la méthode des éléments finis destiné aux animateurs et aux specialistes de l´étude fonctionnelle des muscles.
         Victor Ng Thow Hing [Hing 1994] donne un modèle dynamique de tendons et de muscles pour contrôler les mouvements d´un corps articulé.
         Ferdi Scheepers [Scheepers 1997] et ses collaborateurs décrivent un système de modélisation du corps basé sur la déformation des muscles induite par les mouvements du squelette.
         Jane Wilhelms [Wilhelms 1997] modélise automatiquement la peau en voxélisant la masse du corps, dont est extraite une isosurface polygonale ancrée ensuite aux muscles par des ressorts.
         Michel Bret Méthode domportementale de modélisation et d´animation du corps humain modélise:
Le squelette comme une structure articulée.
Les muscles comme des attaches dynamiques (ressorts) entre les os.
Des organes et des tissus graisseux.
La peau comme une surface souple enveloppant les structures précédentes au moyen d´un laser virtuel.
Les mouvements comme sorties de réseaux neuronaux préalablement entraînés par apprentissages supervisé
Ces réseaux pouvant être générés par des algorithmes génétiques.

Modélisation des cheveux et des vêtements

         Ken-ichi Anjyo [Anjyo 1992] présente une méthode simple pour traiter le comportement dynamique des cheveux.
         Michel Carignan [Carignan 1992] développe des algorithmes de modélisation et d´animation de vêtements ajustés à des acteurs de synthèse en mouvement: Definis comme des pièces planes cousues ensembles, les vêtements sont ensuite ajustés à un corps mobile au moyen de modèles physiques tenant compte de l´élasticité, de l´adhérence et des collisions.
         Jessica Hodgins [Hodgins 1997] définit les "mouvements secondaires" comme le comportement passif d´éléments dépendant des corps contrôlés: C´est le cas des cheveux et des vêtements.

Animation comportementale

         Craig Reynolds introduisit les notions d´"acteur" [Reynolds 1982] et de "comportement" [Reynolds 1987] qui furent reprises et ameliorées par de nombreux auteurs.
         Xiaoyuan Tu [Tu 1994] synthétise un monde marin virtuel basé sur des modèles physiques et habités par des poissons artificiels, définis comme des agents autonomes, dont les comportements répondent à des intentions en activant des moteurs de contrôle.
         De même Radek Grzeszczuk [Grzeszczuk 1995] construit des animaux artificiels apprenant, par essais successifs, à se mouvoir dans un environnement virtuel.
         Bruce Blumberg [Blumberg 1995] synthétise des créatures virtuelles autonomes capables de se comporter dans un environnement donné, mais acceptant aussi un contrôle extérieur au niveau de l´intention, au niveau de l´exécution d´une tâche et au niveau moteur.

Application des modèles connexionnistes et évolutionnistes

         Michiel Van de Panne et Eugène Fiume [Van de Panne 1993] [Van de Panne 1994] utilisent des réseaux neuronaux [Bourret 91] [Abdi 94] dont les entrées sont des valeurs de capteurs et dont les sorties actionnent des moteurs de mouvement pour construire des créatures decouvrant des stratégies de marche.
         Karl Sims [Sims 1991] utilise des techniques de sélection, de variation et de mutation sur des expressions LISP (inspirées de la programmation génétique) pour créer des structures complexes (plantes, textures, mouvements, ...).
         Karl Sims [Sims 1994] utilise des réseaux neuronaux (générés par des algorithmes génétiques) pour contrôler les muscles de créatures artificielles dont le comportement est dirigé vers un but (nager, marcher, sauter, ...).
         Michel Bret (1998):
("une méthode comportementale de modélisation et d´animation du corps humain")
("corps vivants virtuels")
("experimentation dans les arts du connexionnisme") a employ1é des modèles biomécaniques (avec un squelette, des muscles, des graisses, des organes et une peau) pour construire des corps de synthèse et il a employé des réseaux neuronaux pour les animer.

Le temps réel


       Position du problème


       Acteurs interactifs

Position du problème

       L´animation en temps réel se caractérise par des contraintes de temps de calculs. Elles sont résolues d´une part par l´évolution du matériel (ordinateurs de plus en plus puissants, cartes graphiques cablées) et, d´autre part, par des innovations logiciels (librairies graphiques comme OpenGL ou DirectX, optimisation des algorithmes). Dans tous les cas la sophistication et la compléxité des images calculées en temps réel sont inférieures à celles des images calculées en temps différé, lesquelles sont pratiquement hors contraintes.
         Historiquement née avec les simulateurs (de vol, de conduite, scientifiques et militaires), le temps réel est aujourd´hui au coeur de l´interactivité et de tout un nouveau courant artistique contemporain (les installations artistiques interactives) qui rejoint l´univers des jeux, du spectacle (danse, cirque) et de la musique.

Acteurs interactifs

         Michel Bret et Marie-Hélène Tramus ("la funambule virtuelle") et ("danse avec moi") ont construits des installations intéractives artistiques mettant en scène des acteurs percevant leur environnement et réagissant de façon "intelligente". Le système ("modèle") permet de construire rapidement des installations interactives comportant des capteurs variés, un ou plusieurs personnages virtuels et différents modes d´animation (en réaction directe aves les capteurs ou passant par des réseaux neuronaux).

Bibliographie

Hervé Abdi Les réseaux de neurones Presses Universitaires de Grenoble 1994
Ken-ichi Anjyo, Yoshiaki Usami, Tsuneya Kurihar A Simple Method for Extracting the Natural Beauty of Hair in COMPUTER GRAPHICS 26(2), 111-120, 1992
Badler Animating Facial Expression in COMPUTER GRAPHICS 1981
Bruce M. Blumberg, Tinsley A. Galyean Multi-Level Direction of Autonomous Creatures for Real-Time Virtual Environments in COMPUTER GRAPHICS, 47-54, 1995
P. Bourret, J. Reggia, M. Samulides Réseaux Neuronaux TEKNEA 1991
Armin Bruderlin, Thomas W. CALVERT Goal-Directed, Dynamic Animation of Human Walking in COMPUTER GRAPHICS 23(3), 233-242, 1989
Michel Carignan, Ying Yang, Nadia Magnenat Thalmann, Daniel Thalmann Dressing Animated Synthetic Actors with Complex Deformable Clothes in COMPUTER GRAPHICS 26(2), 99-104, 1992
John E. Chadwick, David R. Haumann, Richard E. Parent Layered Construction for Deformable Animated Characters in COMPUTER GRAPHICS 23(3), 243-252, 1989
David T. Chen, David Zetlzer Pump It Up: Computer Animation of Biomechanically Based Model of Muscle in COMPUTER GRAPHICS 26(4), 89-98, 1992
Sabine Coquillard Extended Free-Form Deformation:A Sculpturing Tool for 3D Geometric Modelling in COMPUTER GRAPHICS 24(4), 187,196, juillet 1990
Jean-Louis Dessalles L´ordinateur génétique HERMES 1996
P> Ekman, W. Friesman Manual for the Facial Action Coding System Consulting Psychologist, 1977
David E. Goldberg Algorithmes Génétiques Addison-Wesley 1991
Francis GOUBEL, Ghislaine LENSEL-CORBEIL Biomécanique, éléments de mécanique musculaire MASSON 1998
Radek Grzeszczuk, Demetri Terzopoulos Automated Learning of Muscle-Actuated Locomotion Through Control Abstraction in COMPUTER GRAPHICS, 63-70, 1995
Jean-Claude Heudin La Vie Artificielle
HERMES, 1994

Victor Ng Thow Hing A Biomechanical Musculotendon Model For Animating Articulated Objects Thesis, Departement of Computer Science University of TORONTO, 1994
John Holland Adaptation in natural and artificial systems Ann Arbor; The University of Michigan Press, 1975
Jessica K. Hodgins, Wayne L. WOOTEN, David C. BROGAN, James F. O´BRIEN Animating Human Athletics in COMPUTER GRAPHICS, 71-78, 1995
Jessica K. Hodgins, Nancy S. POLLARD Adaptating Simulated Behaviors For New Characters in COMPUTER GRAPHICS, 153-162, 1997
Yuencheng Lee, Demetri Terzopoulos, Keith Waters Realistic Modeling for Facial Animation in COMPUTER GRAPHICS, 55-62, 1995
Michael McKenna, David Zetlzer Dynamic Simulation of Autonomous Legged Locomotion in COMPUTER GRAPHICS 24(4), 29-38, 1990
James R. Kent, Wayne E. Carlson, Richard E. Parent Shape Transformation for Polyhedral Objects in COMPUTER GRAPHICS 26(2), 47-54, juillet 1992
Gavin S.P. Miller The Motion Dynamics of Snakes and Worms in COMPUTER GRAPHICS 22(4), 168-178, 1988
Marc H. Raibert, Jessica K. Hodgins Animation of Dynamic Legged Locomotion in COMPUTER GRAPHICS 25(4), 349-358, 1991
Thomas S. Ray Evolution, complexity, entropy, and artificial reality. in Physica, 239-263, 1994
W.T. Reeves Particle Systems - A technique for Modelling a Class of Fuzzy Objects in COMPUTER GRAPHICS 17(3), juillet 1983
Craig W. Reynolds Computer Animation with Scripts and Actors in COMPUTER GRAPHICS 16(3), 289-296, 1982
Craig W. Reynolds Flocks, herds, and schools: A distributed behavioral model. in COMPUTER GRAPHICS 21(4), 25-34, 1987
Ferdi Scheepers, Richard E.Parent, Wayne E.Carlsom, Stephen F.May Anatomy-Based Modeling of the Human Musculature in COMPUTER GRAPHICS Graphics, 163-172, 1997
Thomas Sederberg Free-Form Deformation of Solid Geometric Models in COMPUTER GRAPHICS 20(4), 151,160, juillet 1986
Thomas Sederberg, Eugene Greenwood A physically Based Approach to 2D Shape Blending in COMPUTER GRAPHICS 26(2), 25-34, juillet 1992
Karl Sims Artificial Evolution for Computer Graphics in COMPUTER GRAPHICS 25(4), 319-328, 1991
Karl Sims Evolving Virtual Creatures in COMPUTER GRAPHICS, 15-22, 1994
Karl Sims Evolving 3D Morphology and Behavior by Competition in Artificial Life IV Proceedings, MIT Press, 28-39, 1994
Demetri Terzopoulos, John PLATT, Alan BARR, Kurt FLEISCHER Elastically Deformable Models COMPUTER GRAPHICS 21(4), 205-214, 1987
Xiaoyuan Tu, Demetri Terzopoulos Artificial Fishes: Physics, Locomotion, Perception, Behavior in COMPUTER GRAPHICS, 43-50, 1994
Michiel Van de Panne, Eugène Fiume Sensor-Actuator Networks in COMPUTER GRAPHICS , 335-342, 1993
Michiel Van de Panne Control Techniques for Physically-Based Animation These, Universite de TORONTO, 1994
Keith Waters A Muscle Model for Animating Three-Dimensionam Facial Expression COMPUTER GRAPHICS 21(4), 17-24, 1987
Alan Watt, Mark Watt Advanced Animation and Rendering Techniques Addison-Weslwy, ACM Press 1992
J. Weil The Synthesis of Cloth Objects in COMPUTER GRAPHICS 20(4), 49-54, juillet 1986
Jane Wilhelms, Allen Van Gelder Anatomically Based Modeling in COMPUTER GRAPHICS, 181-188, 1997
Andrew WITKIN, Michael KASS Spacetime Constraints in COMPUTER GRAPHICS 22(4), 159-168, 1998
David Zetlzer Motor Control Techniques for Figure Animation in IEEE Computer Graphics and Applications 2,9, 53-59, 1982
F.E. Zajac, E. L. Topp, P. J. STEVENSON A dimensionless musculotendon model in Proceedings IEEE Engineering in Medecine and Biology, 1986
F.E. Zajac Muscle and tendon: Properties, models, scaling, and application to biomechanics and motor control in Critical Reviews in Biomedical Engineering, 17, 359-411, 1989