ALGORITHMS


This file contains descriptions of some algorithms implemented in anyflo..


Curves extension
Dynamic image
Dynamic mouse
Behavioral
Neural networks

















































Curves extension

Linear method

I had developed in assembler in the 1980s a recursive algorithm (using only additions and shifts) to generate real-time lines and curved surfaces
In principle it is from a polygonal line P0 = {Pi} i = 0, n-1 with n vertices are the control points of a curve through these points by approaching the best. It is assumed that the tangent at a point Pn is parallel to segment Pn-1Pn+1 and its lengths, left and right, are respectively proportional to the lengths of segments Pn-1Pn and PnPn+1, with conditions particular ends.



Applied once on the polygonal line LP0 we obtain a polygonal line LP1 2 times more points:
LP1 = f(LP0) = P0 P1g P1d ... Pig Pid ... Pn-1g Pn-1.
Recursively applying this method on polylines LPk = f(LPk-1) we obtaine very quickly almost smooth line.

Method by cubic

A similar algorithm is to generate cubic branches defined by two consecutive control points Pi-1 anf Pi tangent respectively to right Pi-1Pi-1d and to lef PiPig. The coefficients of these cubic branches, which are continuous in the order 1 (since having common tangents), allow to control the curvature.

Generation of curved surfaces

Polyhedral surface SP0 built on a mesh {Pi,j}0<=i<nx 0<=j<ny by nx ny points can be extended to a curved surface through these points and approaching the best in generating polyhedral approximation as follows:
Generation of polygonal approximations Qk of points {Pk,j}0<=j<ny of each column.
And generation of polygonal approximations Rm of points {Qi Rm, m} 0 <= i Then generation of polygonal approximations Rm of points {Qi,m}0<=i<nx.
The vertices Ri,j are those of the polyhedral approximation sought.

Dynamic image

Principle

A pixel is traditionally represented by a static structure:
----------------------------------
typedef struct {
unsigned char r, g, b, a;
} Pixel;

----------------------------------
Where (r, g, b) are the red, green and blue color and is the alpha channel (transparency).
Define a dynamic pixel structure by:
----------------------------------
typedef struct {
unsigned char r, g, b, a;
float m, s, v;
} Pixel;

----------------------------------
Where m is the mass, s and v are the stiffness and viscosity of a spring applied to au vector 4D (r, g, b, a).

Implementation

An image will be view as an object composed of:
1) an array of nx by ny pixels dynamic image at time t.
2) the same table, but with (r, g, b,a) in floats (to avoid rounding errors in the calculations of the dynamic).
3) a memory table of static pixels (r, g, b, a) when it was created (at time 0).
4) a memory speeds of static pixels.
The springs are stretched between the image at time 0 and the image at time t, it is sufficient to change the color (r, g, b, a)t so that it oscillates around (r, g, b, a)0.
Control commands allow to restrict their color, their velocities and their accelerations have been implemented.

A simplified version is obtained by giving all pixels the same mass, the same stiffness and the same viscosity. The tables have more then 4 components (r, g, b, a) in place of 7 (r, g, b, a, m, r, w).

A linearization method simplifies the calculations, allowing the real-time images of average size (about 300 pixels per side).

Dynamic mouse

Principle

The dynamic device mouse captures vectors (t, x, y) with:
       t = time elapsed since the last initial ini mouse or first mouse dynamic dim(n).
       x, y = coordinates of the point entered (left click).
A linear approximation is carried out of the analysis of that signal in a time window in small amplituden. Differential equations gives:
       curvilinear velocity V=ds/dt is approximated by V=(s(t)-s(t-n))/n.
       the tangent vector T=dOM/ds is approximated by T=(OM(t)-OM(t-n)/(s(t)-s(t-n)).
       whose components are: Tx=(x(t)-x(t-n)/(s(t)-s(t-n)) and Ty=(y(t)-y(t-n)/(s(t)-s(t-n)).
       Components of the unit tangent vector are: tx=Tx/m et ty=Ty/m avec m=sqrt(Tx*Tx+Ty*Ty).
       if a=angle(Ox,OM(t)) is the polar angle of the tangent, then:
              c=cos(a)=dTx/ds is approximated by tx et
              s=sin(a)=dTy/ds is approximated by ty.
              so: a=acos(c) modulo PI depending on the sign of asin(a).
       The radius of curvature R=ds/da is approximated by R=V/(a(t)-a(t-n)).
Practically just hold buffers storing the last n vectors (t,x,y), and the last n valuesde a is to calculate these approximations to each image.
mouse dynamic smooth(d) and mouse dynamic adjust(1) used to correct for variations in noise or too irregular for the mouse.

Behavioral

The structure of an object A of anyflo includes, among other things, a pointer (initially zero) front one linked list of objects of type function (called local) attached at the object A and comprising:
1) The source code of the function.
2) Compiled code for execution.
3) A pointer (initially zero) front one linked list of objects of type local variable.
Such a function is dupplication a particular function and can be found in several distinct objects but can be ordered differently (since compilations are distinct) and thus giving these objects of identical (in design) but different (in updating them). Such functions can communicate with each other (at the same object) or local functions of other objects.
This method is used (especially with neural networks) to determine which actors simply learn a certain behavior (eg walking) so that it knows to behave properly in situatiuons varied (eg walking or flat climbing stairs) without it being necessary for any remodel each of these situations. Maybe one day film producers synthesis types realize what they would realize savings by buying such an actor instead of paying armies of graphic designers to work purely repetitive ...).

Neural networks

I implemented the backpropagation error algorithm on multilayer perceptrons based on the book The neural networks Hervé Abdi (Presses Universitaires de Grenoble 1994), Kohonen networks and adaptive networks..