Classe Matrix de Flash8 eronnée?

Mar 22

Je me penchais tout à l'heure sur la question suivante : "Est-ce que les classes de matrice et vecteur de Flash 8 sont réellement optimisées à fond?"

Du coup je me suis décidé à faire un test simple sur l'opération la plus lourde que peut faire la classe Matrix, l'inversion de matrice!
Les matrices de Flash sont des matrices 3x3 que l'on représente de la forme suivante :
matrice 3x3

J'implémente un algorithme un peu optimisé en considérant le fait que les valeurs de G et H sont nulles et I vaut 1. Cela simplifie pas mal les calculs tout de même

Bref voilà ma fonction d'inversion :

PLAIN TEXT

JavaScript:

function invMat (m:Object):Void
{
var a:Number = m.a;
var b:Number = m.b;
var c:Number = m.tx;
var d:Number = m.c;
var e:Number = m.d;
var f:Number = m.ty;
// --
var iDet:Number = 1/(a*e - b*d);
m.a = e * iDet;
m.b = -b * iDet;
m.c = -d * iDet;
m.d = a * iDet;
m.tx = (b * f - c * e) * iDet;
m.ty = (c * d - a * f) * iDet;
}

Ce n'est peut être même pas optimisé à fond encore, mais voilà pour mes tests de vérification et pour se donner une première idée ca suffit.

Je lance la fonction main suivante:

PLAIN TEXT

JavaScript:

var LOOP:Number = 10000;
var t:Number = getTimer ();
while (--LOOP> -1)
{
var m = {a:1, b:2, c:3, d:4, tx:5, ty:6};
invMat (m);
}
trace (getTimer () - t + ' ms');
trace (ObjectDumper.toString (m));

J'obtiens en sortie :

331 ms
{a: -2, b: 1, c: 1.5, d: -0.5, tx: 4, ty: -4.5}

hum hum, je sent que ça va être dur pour la classe "native" ^^
Je fais donc le test suivant avec cette dernière :

PLAIN TEXT

JavaScript:

var LOOP:Number = 1000;
var t:Number = getTimer();
while( --LOOP> -1 )
{
var m:Matrix = new Matrix( 1,2,3,4,5,6);
m.invert();
}
trace( getTimer() - t + ' ms' );
trace( m );

Et j'obtiens à ma grande surprise :

1355 ms
(a=-2, b=1, c=1.5, d=-0.5, tx=1, ty=-2)

Au delà de la différence de temps de calcul, c'est surtout le résultat qui me choque....!

Bon je refais plusieurs fois mon calcul (vive les formules de Cramer), je vérifie sur internet ici mais bon je vois pas mon erreur

Je me décide de lancer mon cher Matlab, je tape les commandes suivantes, qui parlent d'elles même je pense :

A = [1 2 5;3 4 6;0 0 1] A = 1 2 5 3 4 6 0 0 1

A^-1 ans = -2.0000 1.0000 4.0000 1.5000 -0.5000 -4.5000 0 0 1.0000

Aîe, c'était donc mon calcul que était bon alors... Bizarre !

Alors si je fais l'inverse d'une matrice par cette matrice elle même je récupère quoi? La matrice identité comme espéré?
Je fais le test :

PLAIN TEXT

JavaScript:

var m:Matrix = new Matrix( 1,2,3,4,5,6);
var mi:Matrix = m.clone();
mi.invert();
m.concat( mi );
trace( m );

Et j'obtiens en sortie :

(a=1, b=0, c=0, d=1, tx=0, ty=0)

C'est bien la matrice identitée... Et si je fais ça avec ma matrice récupérée par mon algo alors? encore une fois, je fais le test :

PLAIN TEXT

JavaScript:

var m = new Matrix( 1,2,3,4,5,6);
var mi = m.clone();
invMat (mi);
m.concat( mi );
trace( m );

(a=1, b=0, c=0, d=1, tx=3, ty=-2.5)

Mouarf .... C'est quoi cette histoire?

Je redemande à Matlab :
A = [1 2 5;3 4 6;0 0 1]; B = A^-1; B*A ans = 1.0000 0 -0.0000 0.0000 1.0000 0.0000 0 0 1.0000
Ouais bein lui il reste cohérent aussi....

Alors que penser? Moi je ne fais que des hypothèses, mais je dirait qu'ils se sont bien arrangés avec leur classe. Un petit "truc" sur l'inverse, un petit "truc" sur la multiplication et hop, ça tourne!

[MISE A JOUR]
Je viens de tester la méthode concat() et je retrouve bien comme je le pensais un problème par rapport à la multiplication matricielle standard. Maintenant j'aimerai bien savoir pourquoi et comment ils font pour obtenir ce résultat !
[/MISE A JOUR]

Bref moi je suis un peu deg'. Je comprends pas vraiment ce qui se passe par là, et je comprend mieux maintenant pourquoi j'ai eu des soucis avec la classe Matrix durant mes tests pour la classe DistortImage...

27 commentaires pour “Classe Matrix de Flash8 eronnée?”

Alan Shaw a dit :
23 March 2006 à 1:47 am
Bon quant aux détails je ne suis pas très sûr, mais je crois que la solution au paradoxe se trouve dans le fait que

"The translation operation... cannot be expressed in terms of a 3x3 matrix."

(Lengyel, Mathematics for 3D Game Programming & Computer Graphics)

Cela nous indiquerait que la classe Matrix n'est point la matrice mathématique ordinaire.

Et les docs MM en nulle part ne prétendent pas que l'operation Matrix.invert égale l'inversion matricielle standard:

"invert... performs the opposite transformation of the original matrix."

(AS2.0 Language Reference for Macromedia Flash

Clairement pas la même chose!
Alan Shaw a dit :
23 March 2006 à 2:07 am
Non, je me suis trompé, car Lengyel parle des transformations 3D où la matrice 3x3 ne suffit pas.
Antoine a dit :
23 March 2006 à 8:04 am
Hellow,

Dis, je voulais savoir ce qu'était ton tx et ty parce que là, je sais pas mais si c'est une matrice 2x3 ou 3x2 ça va être chaud de trouver un inverse (l'inverse à gauche étant forcément différent de l'inverse à droite.)

Attention que dans matlab, on n'inverse pas une matrice comme ça mais en faisant inv(X) si X est la matrice carrée.
ekameleon a dit :
23 March 2006 à 8:27 am
Hello
1 - pour la vitesse (bench) : tu déclares une instanciation dans la boucle pour utiliser la matrice de MM et dans ton test tu utilises un simple objet générique... forcément la fonction du constructeur est plus lourde pour mettre en place l'instance que ta déclaration d'un objet simple.

2 - La classe de macromedia n'est pas native comme on le voudrait (pas de ASNative dessus) ... c'est juste une surcouche dans le flashplayer donc elle est plus lente qu'un code vraiment natif.

3 - Quand on regarde de plus prêt comment fonctionne la méthode inverse de Macromedia on voit tout de suite ce qui ne va pas
public function invert():Void { if (b == 0 && c == 0) { a = 1 / a ; d = 1 / d ; b = 0 ; c = 0 ; tx = - a * tx ; ty = - d * ty ; } else { var a0:Number = a ; var a1:Number = b ; var a2:Number = c ; var a3:Number = d ; var det:Number = a0 * a3 - a1 * a2; if (det == 0) identity() ; else { det = 1 / det ; a = a3 * det ; b = -a1 * det ; c = -a2 * det ; d = a0 * det ; var p:Point = deltaTransformPoint( new Point(tx, ty) ) ; tx = - p.x ; ty = - p.y ; } } }
On se rend compte qu'en interne la méthode utilise d'autres méthodes, une instance de la classe Point instanciée(encore un appel d'une fonction constructeur etc....)

4 - Pour ce qui est de l'erreur ... elle doit se faire au niveau du var p:Point = ... à mon avis.. faudrait que je vois cela de plus prêt quand j'ai un peu de temps

EKA+
ekameleon a dit :
23 March 2006 à 8:30 am
J'ai oublié de mettre la méthode deltaTransPoint qui provoque à mon avis la différence avec ton code
public function deltaTransformPoint(p:Point):Point { return new Point(a * p.x + c * p.y , d * p.y + b * p.x) ; }
EKA+
Antoine a dit :
23 March 2006 à 10:24 am
Et dire qu'il existe des méthodes d'inversion de matrice bien plus rigoureuse que 1/det * (matrice transposée des cofacteurs) comme le fait MM Adobe.
Foxy a dit :
23 March 2006 à 10:51 am
je suis pas expert en la matière mais apparament l'inverse est gérée comme s'il s'agissait d'une matrice d'ordre 2. Quand à tx et ty qui sont traités de façon différente, est-ce que ce n'est pas lié à l'usage qu'on en fait pour les MovieClip du fait de leur point d'enregistrement pour compenser le décalage que peux occasioner l'inverse ? Enfin ça a certainement une utilité bien pensée par les ingénieurs mm pour faciliter (sic !) quelque chose ou un rendu ?
kiroukou a dit :
23 March 2006 à 11:18 am
@Antoine: sous Matlab ^-1 ou inv c'est strictement la même chose pour une matrice carrée

Et dire qu’il existe des méthodes d’inversion de matrice bien plus rigoureuse que 1/det * (matrice transposée des cofacteurs)

Ce n'est pas rigoureux ça? Car il existe d'autres techniques bien entendu, mais en quoi celle ci n'est pas rigoureuse?

@Eka: Oui en effet l'appel du constructeur est plus long, je le sais bien, mais reste que ca devait être prit en compte dans mon bench, car dans mon application ce sera comme ça.
Je sais aussi que la classe n'est pas vraiment native, d'où mes guillemets. Ils auraient vraiment pu faire cet effort soit dit en passant.... M'enfin
Merci beaucoup pour la fonction deltaTransPoint! En fait ils appliquent une multiplication matricielle du bloc 2x2 transposé sur les points tx et ty!
C'est bizarre. Mais je comprend mieux qd même maintenant

Je ne vois pas encore la raison de ceci, mais il est clair que comme tu le dis Foxy, ca doit être relié à l'utilisation des MovieClip et de leur système de coordonnées.
Reste que ça fait du bien de voir que ce n'est pas moi qui suis complètement fou ^^
ekameleon a dit :
23 March 2006 à 11:47 am
Normalement on devrait pas appeler cette classe Matrix mais TransformMatrix ! C'est vraiment une classe spécifique pour gérer les dégradés, les rotations de bitmap etc... mais c'est pas une vraie classe Matrix comme on l'entend.
kiroukou a dit :
23 March 2006 à 11:55 am
Ouais en effet. Mais je ne l'aurai jamais pensé avant d'avoir fait ces tests.
Comme quoi parfois juste se contenter d'utiliser est beaucoup mieux ^^
iteratif a dit :
23 March 2006 à 12:30 pm
de quoi repondre a toutes vos questions :

http://www.senocular.com/flash/tutorials/transformmatrix/
kiroukou a dit :
23 March 2006 à 12:38 pm
Moi ca ne me répond pas encore vraiment ^^
Il explique de façon très détaillé le fonctionnement des matrices c'est certain, mais à aucun moment il détaille le pourquoi de cette représentation et de ce fonctionnement.
C'est certain qu'il y a une raison logique à ça. Pour le moment je me dis que la troisème colonne, est en fait en point qui n'a rien à voir avec la matrice, mais il est contenu dedans car en interne après ils en ont besoin!
Bref c'est une matrice 2x2 avec un point 2D leur classe Matrix! et vraiment pas une vraie Matrice 3x" comme je m'y attendais initiallement. Maintenant avec un peu plus de recul je comprend beaucoup mieux leur choix. Mais ils auraient pu etre plus clair tout de même
ekameleon a dit :
23 March 2006 à 1:05 pm
faut pas trop leur en demander à mon avis Car sinon j'ai plein de truc à leur demander avant cela lol
EKA+
kiroukou a dit :
23 March 2006 à 1:09 pm
Oui je me doute bien qu'il y a des choses plus importantes dont les professionnels (dont je ne fais pas partie) ont besoin. MAis bon, je suis Français non? Alors si je râlais pas un petit peu y'aurai vraiment un problème hihi ^^

Mais bon, je suis content que le problème sois un peu plus clair maintenant, et j'espère que ce post pourra aider d'autres personnes.
iteratif a dit :
23 March 2006 à 2:56 pm
Il y a une erreur dans ton code, modification apportée en gras :

function invMat (m:Object):Void
{
var a:Number = m.a;
var b:Number = m.b;
var c:Number = m.tx;
var d:Number = m.c;
var e:Number = m.d;
var f:Number = m.ty;
// --
var iDet:Number = 1/(a*e - b*d);
m.a = e * iDet;
m.b = -b * iDet;
m.c = -d * iDet;
m.d = a * iDet;
m.tx = (b * f - c * e) * iDet;
m.ty = -(c * d - a * f) * iDet;
}
kiroukou a dit :
23 March 2006 à 4:08 pm
heu vu que matlab trouve pareil, je pense que mon calcul est bon ^^
iteratif a dit :
23 March 2006 à 4:28 pm
ah oui desolé mais ca m'as perturbe que tu ai utilisé les lettres a,b,c,d,e et f ...
Antoine a dit :
24 March 2006 à 5:15 pm
sous Matlab ^-1 ou inv c'est strictement la même chose pour une matrice carrée

Non, c'est deux fois plus lent

Ce n'est pas rigoureux ça? Car il existe d'autres techniques bien entendu, mais en quoi celle ci n'est pas rigoureuse?

J'avais souvenir mais je n'ai rien retrouvé dans mes cours... Je dois donc m'incliner
kiroukou a dit :
24 March 2006 à 5:19 pm
ah ouais au niveau des perfs oki ^^ Je ne savais pas, donc je note ça dans ma tête
Pour le côté rigueur dans l'inversion, ca doit être possible, m'enfin à la fac on m'a apprit comme ceci et ensuite j'ai vu des méthodes plus numériques, mais nulle part que ce n'était pas rigoureux. Du coup ça m'intéressait de savoir (histoire d'essayer de coller mon prof lol).

Tu bouffes beaucoup de matlab toi aussi sinon?
Antoine a dit :
24 March 2006 à 5:41 pm
Ben en ingéniorat civil (polytech en france) on fait pas mal de simulation et le prof aime pas que l'on fasse pas gaffe aux temps d'exécution et au perf. C'est comme ça que je le sais parce qu'avant noel j'ai fait quelques résolutions de systeme linéaire.

Pour l'inversion, je vais demander à mon prof... Je voudrais bien être sûr
Antoine a dit :
24 March 2006 à 5:51 pm
Voilà la réponse de mon prof (rapide hein ;))

Bonjour Antoine :

C'est effectivement parce que Cramer n'est PAS la bonne méthode pour
inverser une matrice qu'elle ne figure pas mentionnée explicitement dans
le syllabus (en fait, l'intérêt de la formule de Cramer est de pouvoir
travailler de manière formelle et de faire apparaître le déterminant de
manière explicite, ce qui est intéressant par exemple lorsque l'on
étudie d'un point de vue théorique les problèmes de valeurs propres et
que l'on doit trouver le polynôme caractéristique d'une matrice (voir
ton cours de math 2 !)).
Il y a cependant une référence à Cramer pour la résolution d'un système
d'équations linéaires (Corollaire 7.9). L'exercice 24 de la section 7.3
est aussi un exemple qui te fera comprendre qu'utiliser des formules
"théoriques" n'est pas toujours faisable. Bref, sans être le parfait
spécialiste de l'algèbre numérique (si tu veux en savoir plus, interroge
mon collègue Paul Van Dooren ou inscris toi en math app) je peux te dire
que les méthodes utilisées par les numériciens se basent sur de
l'échelonnement (comme vu au cours) ou de la factorisation.

V. Wertz
kiroukou a dit :
24 March 2006 à 6:02 pm
Ah ouais ok (rapide ton prof d'ailleurs!)
Mais il ne dit rien sur le fait que ce n'est pas rigoureux.

des méthodes d'inversion de matrice bien plus rigoureuse

.

Comme je te le disais j'ai étudié durant ma formation les méthodes numériques, et on avait vu d'autres solutions bien plus faciles à implémenter ensuite niveau algorithmique! Mais reste que la méthode de Cramer est rigoureuse, mais juste trop théorique pour être facile à utiliser.
Mais maintenant lors de mes exams, je me suis toujours servi de Cramer (car les matrices petites!).

Ouarf ca me rappelle trop peu de choses moi ça:

polynôme caractéristique d'une matrice

lol
Antoine a dit :
24 March 2006 à 6:31 pm
En effet, je m'incline

C'était ma matière de la semaine passé ça... les polynomes caractéristiques et les formes quadratiques... souvenir souvenir
Nico a dit :
6 September 2006 à 7:07 pm
Le truc, c'est que Cramer, demande bcp plus de calcul que d'autres Méthodes, comme la triangularisation et puis substitution (gauss). ou alors cholelsky (factorisation), fin bon moi aussi j'aime pas du tout ces matrices flash. Il pourrait un peu se casser le cul, quand-même pour nous pondre des petites classes qui permettent de manipuler les matrices et résoudre des systèmes, fin bon, c'est bien la preuve que malgré tous les progrès qu'ils ont faits depuis quelques années, y'a encore beaucoup à faire...
petites questions : n'existe-t-il pas une classe faites pour ca et développée par un super crack, parce que j'ai pas envie de le faire moi-même...
kiroukou a dit :
6 September 2006 à 7:27 pm
Salut,
dans la librairie Sandy je propose une classe de manipulation des matrices 4x4 avec un certain nombre d'opérations classiques
Tu peux toujours aller voir, mais il manquera certainement encore d'autres choses nécéssaires en algèbre linéaire.
Nico a dit :
6 September 2006 à 8:13 pm
est-ce que ta classe peut faire des matrices 3x3 et 2x2 ? parce que si oui, je me demande bien comment t'as pu faire. Est-ce que je me trompe ou dans flash, ils ont même pas prévu de pouvoir manipuler des tableaux doubles? Fin, y'a peut-être moyen de faire ce avec des pointeurs, qqn sait m'en dire plus ?
Philip flip Kromer a dit :
20 August 2007 à 11:29 pm
Bonjour. Mon Français est très pauvre ainsi je suis désolé pour celui.

Le problème est que (b) et (c) sont commutés dans l'aide d'actionscript.

J'ai fait un programme qui montre ceci. Veuillez le voir
http://mrflip.com/visage/demos/matrixmathdemo/MatrixMathDemo.html
ou voir à mon blog,
http://multivisage.blogspot.com/2007/08/flex-demo-matrix-math-and-error-in.html

Weblogue de Kiroukou

Classe Matrix de Flash8 eronnée?

27 commentaires pour “Classe Matrix de Flash8 eronnée?”

Répondre

Meta

Recent Posts

Recent Comments

Links