ALGORITHMES


Ce fichier regroupe les descriptions de certains algorithmes implémentés dans anyflo.


Les extensions courbes
Image dynamique
Souris dynamique
Le comportemental
Réseaux neuronaux

















































Les extensions courbes

Méthode linéaire

J´avais développé en assembleur dans les années 1980 un algorithme récursif (n´utilisant que des décallages et des additions) pour générer en temps réel des lignes et des surfaces courbes:
Dans son principe il consiste à partir d´une ligne polygonale P0 = {Pi}i=0,n-1 dont les n sommets sont les points de contrôle d´une courbe passant par ces points en l´approchant au mieux.
On fait l´hypothàse que la tangente en un point Pn est parallè au segment Pn-1Pn+1 et que ses longueurs, à left et à right, sont respectivement proportionnelles aux longueurs des segments Pn-1Pn et PnPn+1, avec des conditions particulières aux extrémités.



Appliqué une première fois sur la ligne polygonale LP0 on obtient une ligne polygonele LP1 de 2 fois plus de points:
LP1 = f(LP0) = P0 P1g P1d ... Pig Pid ... Pn-1g Pn-1.
En appliquant récursivement cette méthode sur les lignes polygonales LPk = f(LPk-1) on obtient très rapidement une ligne pratiquement lisse.

Méthode par les cubiques

Un algorithme analogue consiste à générer des branches de cubiques définies par 2 point de contrôle consécutifs Pi-1 et Pi et leurs tangentes respectivement à right Pi-1Pi-1d et à left PiPig. Les coefficients de ces branches de cubiques, qui sont continues à l´ordre 1 (puisque ayant des tangentes communes), permettent d´en contrôler la courbure.

Génération de surfaces courbes

Une surface polyhédrique SP0 construite sur un maillage {Pi,j}0<=i<nx 0<=j<ny de nx par ny points peut être étendue en une surface courbe passant par ces points et s´en approchant au mieux en générant une approximation polyhédrique de la façon suivante:
Génération des approximations polygonales Qk des points {Pk,j}0<=j<ny de chaque colonne.
Puis génération des approximations polygonales Rm des points {Qi,m}0<=i<nx.
Les sommets Ri,j sont ceux de l´approximation polyhédrique cherchée.

Image dynamique

Principe

Un pixel est traditionnellement représenté par une structure statique:
----------------------------------
typedef struct {
unsigned char r, g, b, a;
} Pixel;

----------------------------------
(r, g, b) sont les composantes rouge, vert et bleu de la couleur et a est la couche alpha (transparence).
Définissons une structure de pixel dynamique par:
----------------------------------
typedef struct {
unsigned char r, g, b, a;
float m, s, v;
} Pixel;

----------------------------------
m est la mass, s et v sont la raideur et la viscosité d'un spring appliqué au vecteur 4D (r, g, b, a).

Implémentation

Une image sera vue comme un objet composé de:
1) un tableau de nx par ny pixels dynamiques, image à l´instant t.
2) le même tableau, mais avec r, g, b et a en floats (pour éviter les erreurs d´arrondi par les calculs de la dynamique).
3) une mémoire du tableau des pixels statiques (r, g, b, a) à sa création (au temps 0).
4) une mémoire des vitesses des pixels statiques.
Les ressorts sont tendus entre l´image au temps 0 et l´image au temps t, il suffit alors de modifier la couleur (r, g, b, a)t pour que celle-ci oscille autour de (r, g, b, a)0.
Des commandes de contrôle des couleurs, de leurs vitesses et de leurs accélérations ont été implémentées.

Une version simplifiée est obtenue en donnant à tous les pixels la même mass, la même raideur et la même viscosité. Les tableaux n'ont plus alors que 4 composantes (r, g, b, a) au lieu de 7 (r, g, b, a, m, r, v).

Une méthode de linéarisation permet de simplifier les calculs, ce qui autorise le temps réel sur des images de taille average (de l´ordre de 300 pixels de côté).

Souris dynamique

Principe

Le périphérique souris en mode dynamic capte des vecteurs (t,x,y) avec:
       t = temps écoulé depuis le dernier ini mouse ou le premier mouse dynamic dim(n).
       x,y: coordonnées du point saisi (clic left).
On réalise une approximation linéaire de l´analyse de ce signal dans dans une fenêtre temporelle de petite amplitude n. Les équations différentielles donnant:
       la speed curviligne V=ds/dt est confondue avec V=(s(t)-s(t-n))/n.
       le vecteur tangent T=dOM/ds est confondu avec T=(OM(t)-OM(t-n)/(s(t)-s(t-n)).
       dont les composantes sont: Tx=(x(t)-x(t-n)/(s(t)-s(t-n)) et Ty=(y(t)-y(t-n)/(s(t)-s(t-n)).
       Les composantes du vecteur unitaire tangent sont: tx=Tx/m et ty=Ty/m avec m=sqrt(Tx*Tx+Ty*Ty).
       Si a=angle(Ox,OM(t)) est l´angle polaire de la tangente, on a:
              c=cos(a)=dTx/ds est confondu avec tx et
              s=sin(a)=dTy/ds est confondu avec ty.
              d´où: a=acos(c) a&grav;e PI près selon le signe de asin(a).
       Le rayon de courbure R=ds/da est confondu avec R=V/(a(t)-a(t-n)).
Pratiquement il suffit de maintenir des buffers stockant les n derniers vecteurs (t,x,y) et les n dernières valeurs de a pour calculer ces approximations à chaque image.
Un mouse dynamic smooth(d) et un mouse dynamic adjust(1) permettent de corriger les variations parasites ou trop irrégulières de la souris.

Le comportemental

La structure d´un objet A d´anyflo comporte, entre autre, un pointeur (initialement nul) front une liste chainée d´objets de type fonction: (dites locales) attachées a` l´objet A et comportant:
1) Le code source de la fonction.
2) Le code compilé pour son exécution.
3) Un pointeur (initialement nul) devant une liste chainée d´objets de type variable local.
Une telle fonction est la dupplication d´une fonction particulière et peut donc se trouver dans plusieurs objets distincts mais pouvant se dérouler différemment (puisque les compilations sont distinctes) et donc conférant à ces objets des comportements identiques (dans leur conception) mais différents (dans leur actualisation). De telles fonctions peuvent communiquer entre elles (au niveau d´un même objet) ou avec les fonctions locales d´autres objets.
Cette méthode est utilisée (notamment avec des réseaux neuronaux) pour définir des acteurs auxquels il suffit d´apprendre un certain comportement (par exemple de marcher) pour qu´il sache se comporter correctement dans des situatiuons variées (par exemple de marcher à plat ou de monter un escalier) sans qu´il ne soit nécessaire de tout remodeliser pour chacune de ces situations. Peut-être qu´un jour les producteurs de films de synthèse s´appercevront quelle économie ils réaliseraient en achetant un tel acteur au lieu de payer des armées d´infographistes à faire un travail purement répétitif ...).

Réseaux neuronaux

J´ai implémenté l´algorithme de la rétropropagation de l´erreur sur les perceptrons multicouches d´après l´ouvrage Les réseaux neuronaux d´Hervé Abdi (Presses Universitaires de Grenoble 1994), ainsi que les réseaux de Kohonen et les réseaux adaptatifs.