Espace vectoriel et informatique

[invite8fabde6c]

Bonjour,

Loin de moi l'idée de remettre en cause l'utilité de cette magnifique partie des maths (qui à vrai dire sauvent un peu ma moyenne, et me change un peu de la monotonie de l'analyse ou encore pire : la géométrie )

Sur plusieurs discussion, j'ai vu que l'algèbre pouvait servir en informatique. Mais voilà, je bidouille un peu en programmation (deux, trois petites lignes de codes par-ci par-là) et je me demandais dans quel contexte l'utilisation de l'algèbre pouvait être grandement utile.

C'est sûr qu'un endomorphisme est un peu inutile pour faire un pendu, alors est-ce que c'est utile pour un type d'algorithme particulier ?
-----

[invitefa064e43]

évidemment comme tout en maths, on peut trouver des applications là où s'y attend le moins.

mais déjà, les premières choses qui me passent à l'esprit :

* la 3D et tout ce qui est graphique en général : énorme utilisation des vecteurs, et donc de l'algèbre linéaire (rotations = matrice, affichage d'une projection = ce qu'on voit depuis une certaine caméra, un certain point de vue = matrice, ombres = matrice , etc ....)

* les méthodes de calcul numérique (résolution de problème par approximation ou par calcul exact), qui utilisent très souvent des matrices / vecteurs propres, etc...

[invitec3143530]

L'algèbre linéaire sert je crois dans les algorithmes de compression d'images.

[invite8fabde6c]

Pour les résolutions numériques il faudrait plus se pencher sur le problème. Je pense que certains se sont penchés sur le problème pour optimiser tout ça, et ça doit être intéressant de voir comment ils arrivent à rendre plus rapide tout ce qui est calcul numérique.
En ce qui concerne la 3D, c'est sûr que ça doit grandement aider, mais je serai curieux de voir des lignes de codes utilisant des matrices de rotation et de projection.

Merci en tout cas pour vos réponse

[A voir en vidéo sur Futura]

[invitefa064e43]

par exemple, trouvé au hasard sur google en tapant "source code 3d rotation" :
http://www.fastgraph.com/makegames/3...on/3dsrce.html

The Mathematics of the 3D Rotation Matrix: Source Code
Diana Gruber
Note: This is NOT THE SOURCE CODE TO FASTGRAPH. This is just some C++ code I wrote over the weekend to illustrate the ideas in my paper The Mathematics of the 3D Rotation Matrix. You may use this code however you see fit.

Recently I have been benchmarking this code against Fastgraph. Fastgraph is written in assembly language, and takes advantage of the speed boost available using concurrent floating point operations. Vectors consist of 3 floats. A floating point operation takes 3 cycles. You can start two more operations before the first one finishes. So you can do 3 floating point operations at the same time. Get it?

So far, Fastgraph beats this code by 200%-500%, depending on such things as what compiler switches you apply. There are further optimizations that can be applied to this C++ code. In many cases you don't need to do a complete matrix multiply, for example. Since the first 3 columns of the transform matrix are identical to the rotation matrix, you can take a shortcut and just calculate the 4th column.

Source code here is presented "as is". Use it at your own risk. Please report any errors to dgruber@fastgraph.com. Don't flame me, just report the errors.

//---------------------------------------------------------------------------
/* 3D.h: declarations for 3D rotation/translation class 3D.cpp */

#ifndef _3DH
#define _3DH

//---------------------------------------------------------------------------
class _3D
{
private:

   // internal vectors and matrices
   double WorldUp[3];
   double ViewMoveMatrix[12];
   double ViewRotationMatrix[12];
   double WorldTransform[12];
   double ObjectMoveMatrix[12];
   double ObjectRotationMatrix[12];
   double ObjectTransform[12];
   double CombinedTransform[12];

   // helper functions
   void MatrixMultiply(double *A, double *B, double *C);
   void MoveFill(double *A, double Cx, double Cy, double Cz);
   void RotateFill(double *A, double Cx, double Cy, double Cz);

public:
 
   double pi;

   _3D(void); // constructor

   // 3D functions
   void _3DAxisAngle (double x, double y, double z, double theta);
   void _3DAxisAngleObject (double x, double y, double z, double theta);
   void _3DGetView (double *x1, double *y1, double *z1, double *x2, double *y2, double *z2);
   int  _3DLookAt (double x1, double y1, double z1, double x2, double y2, double z2);
   void _3DPOV(double Cx, double Cy, double Cz, double xAngle, double yAngle, double zAngle);
   void _3DRoll(double theta);
   void _3DRollObject(double theta);
   void _3DRotateRight(double theta);
   void _3DRotateRightObject(double theta);
   void _3DRotateUp(double theta);
   void _3DRotateUpObject(double theta);
   void _3DMove(double x, double y, double z);
   void _3DMoveObject(double x, double y, double z);
   void _3DMoveForward(double n);
   void _3DMoveForwardObject(double n);
   void _3DMoveRight(double n);
   void _3DMoveRightObject(double n);
   void _3DMoveUp(double n);
   void _3DMoveUpObject(double n);
   void _3DSetObject(double Ox, double Oy, double Oz, int xAngle, int yAngle, int zAngle);
   void _3DUpVector(double x, double y, double z);
};
#endif

/*

            Absolute Moves
            --------------
View                             Object
----                             ------
_3DMove()                        _3DMoveObject


            Relative Moves
            --------------
View                             Object
----                             ------
 _3DMoveForward()                _3DMoveForwardObject()
 _3DMoveRight()                  _3DMoveRightObject()
 _3DMoveUp()                     _3DMoveUpObject()


            Absolute Rotations
            ------------------
View                             Object
----                             ------
_3DAxis/Angle()                  _3DAxis/AngleObject()


            Relative Rotations (roll, pitch, yaw)
            -------------------------------------
View                             Object
----                             ------
_3DRoll()                        _3DRollObject()
_3DRotateRight()                 _3DRotateRightObject()
_3DRotateUp()                    _3DRotateUpObject


            Absolute Move + Absolute Rotation using Euler Angles
            -----------------------------------------
View                             Object
----                             ------
_3DPOV()                         _3DSetObject()


            Absolute Move + Absolute Rotation using Look At vector
            -----------------------------------------
View                             Object
----                             ------
_3DLookAt()                       ?

*/


/* --------------------------------------------------------------------------
3D.CPP by Diana Gruber

This is the code I wrote to illustrate some of the ideas I had about
3D rotation. This is NOT THE SOURCE CODE TO FASTGRAPH. Fastgraph is
written in assembly language. It is much faster than this C++ code.

This code illustrates the concepts in my paper "The Mathematics of the 
3D Rotation Matrix" presented at XGDC on October 1, 2000. Hopefully
you will find it easy to follow and mildly interesting. If you are
looking at this in hard copy and you want to download it, try
http://www.makegames.com/3Drotation or email me at dgruber@fastgraph.com.

-------------------------------------------------------------------------- */
#include "3D.h"
#include 
#include 

//---------------------------------------------------------------------------
_3D::_3D(void)
{
   /* Constructor -- initialize */

   // initialize WorldUp
   WorldUp[0] = 0;
   WorldUp[1] = 1.0;
   WorldUp[2] = 0;

   // initialize the World Transform
   _3DPOV(0,0,0,0,0,0);

   // initialize the Object Transform
   _3DSetObject(0,0,0,0,0,0);

   // calculate a value for pi
   pi = 4.0*atan(1.0);
}

//---------------------------------------------------------------------------
void _3D::_3DAxisAngle (double x, double y, double z, double theta)
{
   /* This function performs an axis/angle rotation. (x,y,z) is any 
      vector on the axis. For greater speed, always use a unit vector 
      (length = 1). In this version, we will assume an arbitrary 
      length and normalize. */

   double length;
   double c,s,t;

   // normalize
   length = sqrt(x*x + y*y + z*z);

   // too close to 0, can't make a normalized vector
   if (length < .000001)
      return;

   x /= length;
   y /= length;
   z /= length;

   // do the trig
   c = cos(theta);
   s = sin(theta);
   t = 1-c;   

   // build the rotation matrix
   ViewRotationMatrix[0] = t*x*x + c;
   ViewRotationMatrix[1] = t*x*y - s*z;
   ViewRotationMatrix[2] = t*x*z + s*y;
   ViewRotationMatrix[3] = 0;

   ViewRotationMatrix[4] = t*x*y + s*z;
   ViewRotationMatrix[5] = t*y*y + c;
   ViewRotationMatrix[6] = t*y*z - s*x;
   ViewRotationMatrix[7] = 0;

   ViewRotationMatrix[8] = t*x*z - s*y;
   ViewRotationMatrix[9] = t*y*z + s*x;
   ViewRotationMatrix[10] = t*z*z + c;
   ViewRotationMatrix[11] = 0;

   // build the transform
   MatrixMultiply(ViewRotationMatrix,ViewMoveMatrix,WorldTransform);
}

//---------------------------------------------------------------------------
void _3D::_3DAxisAngleObject (double x, double y, double z, double theta)
{
   /* This function performs an axis/angle rotation. (x,y,z) is any 
      vector on the axis. For greater speed, always use a unit vector 
      (length = 1). In this version, we will assume an arbitrary 
      length and normalize. */

   double length;
   double c,s,t;

   // normalize
   length = sqrt(x*x + y*y + z*z);

   // too close to 0, can't make a normalized vector
   if (length < .000001)
      return;

   x /= length;
   y /= length;
   z /= length;

   // do the trig
   c = cos(theta);
   s = sin(theta);
   t = 1-c;   

   // build the rotation matrix
   ObjectRotationMatrix[0] = t*x*x + c;
   ObjectRotationMatrix[1] = t*x*y - s*z;
   ObjectRotationMatrix[2] = t*x*z + s*y;
   ObjectRotationMatrix[3] = 0;

   ObjectRotationMatrix[4] = t*x*y + s*z;
   ObjectRotationMatrix[5] = t*y*y + c;
   ObjectRotationMatrix[6] = t*y*z - s*x;
   ObjectRotationMatrix[7] = 0;

   ObjectRotationMatrix[8] = t*x*z - s*y;
   ObjectRotationMatrix[9] = t*y*z + s*x;
   ObjectRotationMatrix[10] = t*z*z + c;
   ObjectRotationMatrix[11] = 0;

   // build the transform
   MatrixMultiply(ObjectMoveMatrix,ObjectRotationMatrix,ObjectTransform);
   MatrixMultiply(WorldTransform,ObjectTransform,CombinedTransform);
}

//---------------------------------------------------------------------------
void _3D::_3DGetView (double *x1, double *y1, double *z1, double *x2, double *y2, double *z2)
{
   /* Returns the current position and a unit vector representing
      the direction of the rotation */

   // the current position is the 4th column of the translation matrix
   *x1 = -ViewMoveMatrix[3];
   *y1 = -ViewMoveMatrix[7];
   *z1 = -ViewMoveMatrix[11];

   // the "out" unit vector is the 3rd row of the rotation matrix
   *x2 = ViewRotationMatrix[8];
   *y2 = ViewRotationMatrix[9];
   *z2 = ViewRotationMatrix[10];
}

//---------------------------------------------------------------------------
int _3D::_3DLookAt (double x1, double y1, double z1, double x2, double y2, double z2)
{
   /* Build a transform as if you were at a point (x1,y1,z1), and
      looking at a point (x2,y2,z2) */

   double ViewOut[3];      // the View or "new Z" vector
   double ViewUp[3];       // the Up or "new Y" vector
   double ViewRight[3];    // the Right or "new X" vector

   double ViewMagnitude;   // for normalizing the View vector
   double UpMagnitude;     // for normalizing the Up vector
   double UpProjection;    // magnitude of projection of View Vector on World UP

   // first, calculate and normalize the view vector
   ViewOut[0] = x2-x1;
   ViewOut[1] = y2-y1;
   ViewOut[2] = z2-z1;
   ViewMagnitude = sqrt(ViewOut[0]*ViewOut[0] + ViewOut[1]*ViewOut[1]+
      ViewOut[2]*ViewOut[2]);

   // invalid points (not far enough apart)
   if (ViewMagnitude < .000001)
      return (-1);

   // normalize. This is the unit vector in the "new Z" direction
   ViewOut[0] = ViewOut[0]/ViewMagnitude;
   ViewOut[1] = ViewOut[1]/ViewMagnitude;
   ViewOut[2] = ViewOut[2]/ViewMagnitude;

   // Now the hard part: The ViewUp or "new Y" vector

   // dot product of ViewOut vector and World Up vector gives projection of
   // of ViewOut on WorldUp
   UpProjection = ViewOut[0]*WorldUp[0] + ViewOut[1]*WorldUp[1]+
   ViewOut[2]*WorldUp[2];

   // first try at making a View Up vector: use World Up
   ViewUp[0] = WorldUp[0] - UpProjection*ViewOut[0];
   ViewUp[1] = WorldUp[1] - UpProjection*ViewOut[1];
   ViewUp[2] = WorldUp[2] - UpProjection*ViewOut[2];

   // Check for validity:
   UpMagnitude = ViewUp[0]*ViewUp[0] + ViewUp[1]*ViewUp[1] + ViewUp[2]*ViewUp[2];

   if (UpMagnitude < .0000001)
   {
      //Second try at making a View Up vector: Use Y axis default  (0,1,0)
      ViewUp[0] = -ViewOut[1]*ViewOut[0];
      ViewUp[1] = 1-ViewOut[1]*ViewOut[1];
      ViewUp[2] = -ViewOut[1]*ViewOut[2];

      // Check for validity:
      UpMagnitude = ViewUp[0]*ViewUp[0] + ViewUp[1]*ViewUp[1] + ViewUp[2]*ViewUp[2];

      if (UpMagnitude < .0000001)
      {
          //Final try at making a View Up vector: Use Z axis default  (0,0,1)
          ViewUp[0] = -ViewOut[2]*ViewOut[0];
          ViewUp[1] = -ViewOut[2]*ViewOut[1];
          ViewUp[2] = 1-ViewOut[2]*ViewOut[2];

          // Check for validity:
          UpMagnitude = ViewUp[0]*ViewUp[0] + ViewUp[1]*ViewUp[1] + ViewUp[2]*ViewUp[2];

          if (UpMagnitude < .0000001)
              return(-1);
      }
   }

   // normalize the Up Vector
   UpMagnitude = sqrt(UpMagnitude);
   ViewUp[0] = ViewUp[0]/UpMagnitude;
   ViewUp[1] = ViewUp[1]/UpMagnitude;
   ViewUp[2] = ViewUp[2]/UpMagnitude;

   // Calculate the Right Vector. Use cross product of Out and Up.
   ViewRight[0] = -ViewOut[1]*ViewUp[2] + ViewOut[2]*ViewUp[1];
   ViewRight[1] = -ViewOut[2]*ViewUp[0] + ViewOut[0]*ViewUp[2];
   ViewRight[2] = -ViewOut[0]*ViewUp[1] + ViewOut[1]*ViewUp[0];

   // Plug values into rotation matrix R
   ViewRotationMatrix[0]=ViewRight[0];
   ViewRotationMatrix[1]=ViewRight[1];
   ViewRotationMatrix[2]=ViewRight[2];
   ViewRotationMatrix[3]=0;

   ViewRotationMatrix[4]=ViewUp[0];
   ViewRotationMatrix[5]=ViewUp[1];
   ViewRotationMatrix[6]=ViewUp[2];
   ViewRotationMatrix[7]=0;

   ViewRotationMatrix[8]=ViewOut[0];
   ViewRotationMatrix[9]=ViewOut[1];
   ViewRotationMatrix[10]=ViewOut[2];
   ViewRotationMatrix[11]=0;

   // Plug values into translation matrix T
   MoveFill(ViewMoveMatrix,-x1,-y1,-z1);

   // build the World Transform
   MatrixMultiply(ViewRotationMatrix,ViewMoveMatrix,WorldTransform);

   return(0);
}

//---------------------------------------------------------------------------
void _3D::_3DMove(double x, double y, double z)
{
   /* Absolute move, without changing the rotation */

   ViewMoveMatrix[3] = -x;
   ViewMoveMatrix[7] = -y;
   ViewMoveMatrix[11]= -z;

   // build the transform
   MatrixMultiply(ViewRotationMatrix,ViewMoveMatrix,WorldTransform);
}

//---------------------------------------------------------------------------
void _3D::_3DMoveObject(double x, double y, double z)
{
   /* Absolute move, without changing the rotation */

   ObjectMoveMatrix[3] = x;
   ObjectMoveMatrix[7] = y;
   ObjectMoveMatrix[11]= z;

   // build the transform
   ....

(coupé par manque de place)

[invitefa064e43]

et concernant le calcul numérique, pour se pencher sur la question rien ne vaut un cours d'analyse numérique (avec ses prérequis en maths ...)

et puis, ça me fait penser que la "théorie" derrière les espaces vectoriels est liées aussi prfondément avec l'analyse de fonctions en ce qui concerne la "transformée de Fourier" et autres "transformées intégrales", qui sont elles-mêmes à la base de nombreux algorithmes de compression / encodage de son / musique / image / vidéo (mp3, jpeg, mpg...)

[inviteda3670f6]

Les matrices, et espaces vectioriels sont très utilisées en 3D, dans toutes les cartes graphiques, d'ailleurs les processeurs s'appellent justement processeurs vectoriels. Ils permettent entre autre de localiser des "mobiles" par rapport à d'autres mobiles, dans les jeux 3D qui fleurissent un peu partout, ou dans les simulateurs, et autres shoot them up en 3D.
Ensuite les transformées conformes, non conforme, la TCD, la FFT, les ondelettes, etc sont très utilisées en traitement numérique du signal, vidéo, mais aussi le filtrage(audio), modulation(transimmssion de données), etc... Tous les outils de CAO, ou de simulation utilisent les transformées de fourier/bilinéaire/Z/laplace, la convolution, etc etc...
A plus

[invite8fabde6c]

Merci pour vos réponses, ça rend mon cours de math un peu plus concret
Pour les lignes de code, je les regarderai d'un peu plus prêt une fois les concours passés, mais ça doit être intéressant de chercher à comprendre comment ça marche ^^