Ce fichier regroupe les descriptions de certains algorithmes implémentés dans anyflo.
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;
----------------------------------
Où (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;
----------------------------------
Où 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.