Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.

com

Support de formation sur les mathmatiques lis la 3D

David Lanier

Page 1

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com Support de formation sur les mathmatiques lis la 3D........................................................... 1 1.Introduction et notation........................................................................................................ 3 2.Vecteurs en dimension 3...................................................................................................... 3 2.1.Addition de vecteurs..................................................................................................... 3 2.2.Multiplication de vecteurs.............................................................................................3 2.3.Norme dun vecteur.......................................................................................................3 2.4.Produit scalaire..............................................................................................................4 2.5.Produit vectoriel............................................................................................................ 5 3.Les matrices......................................................................................................................... 5 4.Les reprsentations dans IR 3...............................................................................................6 4.1.Reprsentation dun plan...............................................................................................6 4.2.Reprsentation paramtrique dun segment de droite et dune droite...........................7 5.Reprsentation des rotations................................................................................................ 8 5.1.Matrices 3x3..................................................................................................................8 5.2.Angles dEuler............................................................................................................ 10 5.3.Axe et angle.................................................................................................................11 5.4.Quaternions................................................................................................................. 11 5.4.1.Interpolation des quaternions : SLERP.................................................................... 12 5.4.2.Interpolation des quaternions : SQUAD.................................................................. 12 5.5.Vecteur angulaire........................................................................................................ 13 6.Changement de repre........................................................................................................14 6.1.Repre local dun objet............................................................................................... 14 7.Exercices pratiques rsolus / tips....................................................................................... 16 7.1.Projection dun point sur plan..................................................................................... 16 7.2.Intersection segment / plan..........................................................................................16 7.3.Un exemple 2D : Changement de repre.................................................................... 18 7.4.Un exemple 2D : Intersection segment / segment......................................................19 7.5.Construire une matrice de rotation partir dun vecteur ........................................... 20 7.6.Faire un Billboard....................................................................................................... 21 7.7.Collisions Rayons / Faces........................................................................................... 22 7.8.Quelques notions de balistique (dynamique du point) - Particules.............................22 8.Remerciements...................................................................................................................23 9.Rfrences.......................................................................................................................... 23

Page 2

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com

1. Introduction et notation
Le but de ce cours dinitiation aux maths 3D est de donner les bases de la 3D. Comme il serait possible dcrire des dizaines de livres sur ce sujet, nous nous concentrerons ici sur les connaissances ncessaires la rsolution des problmes pratiques que lon rencontre le plus souvent dans les jeux vido. Donc nous allons passer en revue beaucoup de domaines de la 3D sans rellement en approfondir un particulirement, mais nous aurons de ce fait une vision de ce qui existe et quoi cela sert. Si le lecteur veut approfondir certains de ces domaines, des rfrences de sites web sont donnes la fin de ce support. Dans tout ce qui suit, on notera SQRT la fonction racine carr.

2. Vecteurs en dimension 3
On apelle vecteur v lensemble {x,y,z} avec x,y,z IR. On notera {0,0,0}le vecteur nul origine du repre. Les axes X, Y et Z reprsentant une base canonique de IR3 et sont X = {1,0,0}, Y = {0,1,0}, Z = {0,0,1}. Pour accder lun des composants de ce vecteur on utilisera la notation . exemple, la premire composante de v sera v.x. Un vecteur est en fait toujours un point de lespace auquel on soustrait lorigine (le vecteur nul). On fait donc souvent lamalgame entre un point dans lespace 3D et un vecteur dans ce mme espace. En fait, le point 3D v peut tre vu comme le vecteur v reprsent par v = v {0,0,0}

2.1.Addition de vecteurs
On dfinit laddition de 2 vecteurs, note + par lapplication qui a 2 vecteurs associe un vecteur ( IR3 x IR3 IR3). Donc le rsultat de laddition de vecteurs est un vecteur. Soit u et v IR3 u + v = w avec w = {u.x + v.x , u.y + v.y , u.z + v.z }

2.2.Multiplication de vecteurs
On dfinit la multiplication de 2 vecteurs, note * par lapplication qui a 2 vecteurs associe un vecteur ( IR3 x IR3 IR3). Donc le rsultat de laddition de vecteurs est un vecteur. Soit u et v IR3 u * v = w avec w = {u.x * v.x , u.y * v.y , u.z * v.z } Remarque : on peut aussi multiplier le vecteur par un rel (le scaler ) ce qui nous donne pour a IR : a*u = { a * u.x , a * u.y , a * u.z }

2.3.Norme dun vecteur

On dfinit la norme dun vecteur, note || || par lapplication qui a une vecteur associe un rel || || : IR3 IR Soit v IR3 ||v || = SQRT ( v.x 2 + v.y 2 + v.z 2 )

Page 3

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com Remarque : Cette forumule vient de la forumule de Pythagore en dcomposant le vecteur sur chaque axe. Normaliser un vecteur consiste calculer sa norme puis diviser tous les composants par la norme du vecteur. Dans la pratique : on utilise souvent la norme au carr dun vecteur pour viter le calcul de la racine carr.

2.4.Produit scalaire
On dfinit le produit scalaire de 2 vecteurs, not . par lapplication qui a 2 vecteurs associe un rel ( IR3 x IR3 IR ). Donc le rsultat du produit scalaire de 2 vecteurs est un rel. Soit u et v IR3 u .v = u.x * v.x + u.y * v.y + u.z * v.z u v

Remarque : le produit scalaire est symtrique : u . v = v . u, et u .u = || u || 2. De manire trigonomtrique, en appelant langle form par u et v, on a aussi la formule suivante : u.v = ||u|| * ||v|| * cos Remarque : Grce cette formule, on peut dterminer langle modulo 2 PI entre 2 vecteurs. On peut aussi dterminer si les vecteurs pointent dans le mme sens o sils sont orthogonaux etc.. Sils pointent dans le mme sens, langle sera compris entre [/2 , + /2] (soit [90, + 90]) donc le cosinus sera positif. En rsum : Si u.v > 0 les vecteurs pointent dans la mme direction 90 prs. Si u.v = 0 les vecteurs sont orthogonaux (cos = 0 = /2 + k , k Z (entiers) ) Si u.v < 0 les vecteurs ne regardent pas dans la mme direction. De manire analytique, le produit scalaire reprsente la projection dun vecteur sur un autre orthogonalement, condition que lun des 2 vecteurs soit normalis. exemple avec ||v|| = 1, si on dfinit h IR par h = u . v. On a la reprsentation suivante : u v h>0 Dans le cas prcdent h > 0, dans le suivant h < 0. u v h<0 Remarque : Autre vision du vecteur v = {x,y,z} on peut en fait dcomposer v dans la base de IR3 (X,Y,Z) de la manire suivante (X, Y et Z sont les axes classiques de IR3) : v={v.X,v.Y,v.Z}

Page 4

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com

2.5.Produit vectoriel
On dfinit le produit vectoriel de 2 vecteurs, not ^ par lapplication qui a 2 vecteurs associe un vecteur orthogonal ( IR3 x IR3 IR3 ). Donc le rsultat dun produit vectoriel est un vecteur orthogonal aux 2 vecteurs dont on a fait le produit. u ^ v = w avec w = { u.y * v.z - u.z * v.y , u.z * v.x - u.x * v.z , u.x * v.y - u.y * v.x } Remarque : le produit vectoriel nest pas symtrique. On a u ^ v = - v ^ u De manire trigonomtrique, en appelant langle form par u et v, on a aussi la formule suivante en posant w = u ^ v : ||w|| = ||u|| * ||v|| * |sin | Attention, comme w est un vecteur, cest ici sa norme qui permet de retrouver le sin en valeur absolue. Donc cela nest jamais suffisant pour dterminer langle , contrairement au produit scalaire. Comme rsultat, on a un vecteur w qui est orthogonal la fois u et v (mme si u et v ne sont pas orthogonaux entre eux).

3. Les matrices
On ne va pas tudier ici toutes les gnralits sur les matrices, mais se concentrer sur ce qui nous servira le plus souvent. On appelle matrice un tableau constitu de m lignes et n colonnes

o les aij sont des rels est appel matrice

On peut additionner des matrices les multiplier etc On ne dtaillera pas ce genre de choses ici. Voici la matrice identit, elle na que des 0 sauf sur la diagonale ou se trouvent des 1 :

Transpos de matrices : Pour transposer une matrice on fait aij = aji pour tout i et j. Donc seule la diagonale reste inchange, cest une sorte de symtrie par rapport la diagonale. Quelques proprits de la multiplication de matrices : i) Le produit de matrice n'est pas commutatif. En gnral AB BA ii) Loi associative: (AB)C = A(BC) iii) Loi distributive: A(B+C) = AB + BC iv) AE = EA =A avec E matrice identit. Page 5

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com v) (AB)T = BT AT

Matrice Inverse : La matrice carre nxn A est dite inversible, s'il existe une matrice B avec la proprit A B = B A = E. Une telle matrice B est unique. On appelle B l'inverse de A et on la note A-1. La matrice A-1 est appele l'inverse de A.

4. Les reprsentations dans IR 3

Pour reprsenter un point on considre son vecteur.

4.1.Reprsentation dun plan

Un plan dans IR3 est un espace de dimension 2 infini, il est donc engendr par 2 vecteurs non colinaires partir dun point prcis (cela permet de le fixer). - On peut donc le reprsenter par 1 point 3D dit origine M et 2 vecteurs dit gnrateurs U et V. Soient 3 vecteurs 3D en tout. - Mais de manire plus simple, on utilise souvent la reprsentation faisant uniquement intervenir 2 vecteurs 3D, soient un point 3D origine M et un vecteur qui reprsente la normale au plan N. N U vplan M y x 0 z On a alors : v = {x,y,z} IR3 v est un point 3D appartenant au plan : On note vplan le vecteur du plan v M. On a alors : vplan . N = 0 et aussi vplan = a * U + b * V avec a et b IR Ce qui veut dire que vplan sexprime en fonction des 2 vecteurs gnrateurs du plan. Plus prcisemment, il est une combinaison linaire de U et V. Lquation dun plan dans IR3 se traduisant de manire analytique par : Tout vecteur v = {x,y,z} IR3 tant dans dans le plan doit vrifier ax+by+cz=d a,b,c et d sont des coefficents rels non uniques. Or on a vplan = v M = { x M.x , y M.y , z M.z } V

Page 6

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com Et en utilisant la formule vplan . N = 0 On a lquivalence suivante : vplan . N = 0 (x M.x) * N.x + (y M.y) * N.y + (z M.z) * N.z = 0 Cette quation nous permet de dterminer a, b, c et d avec : a = N.x, b = N.y, c = N.z et d = (M . N) Donc de manire gnrale lquation du plan partir de sa normale et dun point scrit anlytiquement : N.x * x + N.y * y + N.z * z = -(M . N) avec {x,y,z} formant un vecteur dans le plan

4.2.Reprsentation paramtrique dun segment de droite et dune droite

On reprsente un segment de droite not v par 2 points qui sont ses extrmits: B v A On utilise une reprsentation paramtrique du segment sous cette forme : v ( x ) = A + x * (B A) avec x variant de 0 1. Pour x = 0, v(0) = A, pour x = 1 v(1) = B. Pour reprsenter une droite, il faut 1 point 3D not A et un vecteur qui donne la direction not v: v A

De la mme manire que le segment de droite, la droite de manire paramtre scrit : V ( x ) = A + x * v avec x IR. Lintrt de ces reprsentations est quelles sont valables aussi bien pour des points 3D que 2D.

Page 7

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com

5. Reprsentation des rotations

Les rotations peuvent tre reprsentes par diffrents moyens dans IR3, une matrice 3x3, un quaternion, un axe et un angle, des angles dEuler, un vecteur angulaire. Nous allons tudier chacun de ces moyens avec leur dfaut et leurs avantages. On peut passer de lun lautre, le dtail de ces transformations ne sera pas donn, voir les rfrences pour le dtail. On reconnat une rotation au fait que lorsque lon lapplique sur un vecteur, la norme du vecteur reste inchang. En gnral, on utilise dans une interface utilisateur les angles dEuler car ils sont les plus intuitifs puis on passe une reprsentation diffrente en interne.

5.1.Matrices 3x3
Cest le moyen le plus connu de reprsenter une rotation. On a survol les matrices prcdemment, ici on va se concentrer sur les matrices 3x3. Une matrice 3x3 cest un tableau A = (aij) avec 0 i,j 2 On note les vecteurs colonnes v0 = { a00, a10, a20 } v1 = { a01, a11, a21 } et v2 = { a02, a12, a22 }. Ce sont les colonnes de cette matrice de haut en bas. v0 v1 v2 A= a 00 a 10 a 20 a 01 a 11 a 21 a 02 a 12 a 22

Est-ce toujours une rotation ? Non. Les matrices 3x3 ne reprsentent des rotations que si elles sont orthonornales, cest-dire que lon a la proprit suivante : A A T = Id avec Id matrice identit.

On apelle cela aussi une matrice homogne. Cest dire que linverse de cette matrice est la transpose de celle-ci. Ceci se traduit sur les vecteurs colonnes v0, v1 et v2 de la matrice par la proprit suivante : Tous ces vecteurs sont normaliss (ont une norme de 1) et sont tous orthogonaux entre eux, cd : v0 . v1 = v0 . v2 = v1 . v2 = 0 Pour effectuer ceci, en pratique on fait par exemple :
void OrthonormalizeOrientation( matrix_3x3 &Orientation ) { vector_3 X(Orientation(0,0),Orientation(1,0),Orientation(2,0)); vector_3 Y(Orientation(0,1),Orientation(1,1),Orientation(2,1)); vector_3 Z; X.Normalize(); Z = CrossProduct(X,Y).Normalize(); Y = CrossProduct(Z,X).Normalize(); Orientation(0,0) = X(0); Orientation(0,1) = Y(0); Orientation(0,2) = Z(0); Orientation(1,0) = X(1); Orientation(1,1) = Y(1); Orientation(1,2) = Z(1); Orientation(2,0) = X(2); Orientation(2,1) = Y(2); Orientation(2,2) = Z(2);

Page 8

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com
}

Proprits : - Pour inverser une rotation, il suffira de transposer la matrice de rotation de lobjet. - Pour combiner 2 rotations reprsentes par des matrices 3x3 A et B, il suffit de les multiplier, la multiplication conserve lorthonormalisation. Remarque sur les matrices, avec les notations prcdentes : v0 v1 v2 A= a 00 a 10 a 20 a 01 a 11 a 21 a 02 a 12 a 22

En fait le vecteur v0 reprsente la transformation du vecteur X = {1,0,0} par cette matrice, en effectuant le calcul : A X = v0 De la mme manire on a v1 = AY et v2 = AZ. Ceci sert en pratique pour la construction de matrices spcifiques. Par exemple : Je veux construire une matrice de rotation qui mon axe X fait correspondre Y et Y fait correspondre X tout en laissant Z inchang (rotation autour de laxe Z de 90). Cela me donne : v0 = AX et je veux que cela me donne Y donc v0 = Y, de mme v1 = -Xet v2 = Z (inchang) ce qui me donnera la matrice suivante : A= 0 1 0 -1 0 0 0 0 1

Attention dans certains cas les matrices sont transposes par rapport celles-ci (Direct X par exemple). Avantages : - Pas de problmes de gimbal lock (bloqu dans une orientation sans pouvoir en bouger, voir les angles dEuler). - Les matrices de rotation simples comme lexemple prcdent sont facilement reconnaissables. (Je sais a fait maigre comme avantage ) Inconvnients par rapport aux autres reprsentations : - Plus coteux en mmoire. - Othonormalisation plus coteuse en temps CPU. - Erreurs darrondis peuvent engendrer une matrice non orthonormale lors de combinaisons de matrices et donc translater ou scaler lobjet au lieu de seulement le tourner. - Linterpolation de 2 rotations de manire smooth est coteuse (calcul de vecteurs propres) et napparat pas aussi smooth quavec un quaternion.

Page 9

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com

5.2.Angles dEuler
Les angles dEuler sont des angles qui reprsentent des rotations autour des axes X, Y et Z dans unordre prcis. Soit un angle dEuler E = {60,89,120}, cest une rotation qui veut dire que lon a tourn dun angle de 60 autour de X puis 89 autour de Y puis 120 autour de Z. Ces angles peuvent aussi tre exprims en radians.

Attention, lordre de rotation autour des axes est important, car quand on tourne autour dun axe, tous les autres axes tournent avec ! On doit dfinir si lon tourne en premier sur X puis ensuite sur Y et enfin sur Z si on change cet ordre cela ne donnera pas la mme orientation finale dans le cas gnral. Il y a 12 cas dordre possibles de rotation. Dans Maya par exemple, on peut dfinir lordre dans lequel appliquer les rotations. Il nexiste pas une manire unique de reprsenter une rotation donne avec les angles dEuler. Les angles dEuler peuvent tre convertis en matrices 3x3 laide des matrices de rotation autour des axes X, Y et Z. Les 3 matrices suivantes reprsentent de gauche droite : Rotation dun angle autour de X idem autour de Y idem autour de Z.

Avantages : - 3 variables seulement sont utilises pour reprsenter les 3 degrs de libert. - Il ny a pas appliquer une quelconque transformation pour en faire une rotation, cest toujours une rotation. - Reprsentation assez intuitive de la rotation. Inconvnients : - Pas de combinaison des rotations sous cette forme. - On peut tomber dans un cas o on perd un degr de libert ( appel le Gimbal Lock problem ). - Linterpolation smooth fait intervenir de lintgration numrique ce qui peut tre coteux en CPU.

Page 10

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com

5.3.Axe et angle
Cest une reprsentation assez intuitive aussi.

On dfinit la rotation applique sur le vecteur R par une rotation dun certain angle autour dun axe arbitraire. Avantages : - Il ny a pas appliquer une quelconque transformation pour en faire une rotation, cest toujours une rotation. - Reprsentation assez intuitive de la rotation. Inconvnients : - Pas de combinaison de rotation sous cette forme. - Linterpolation smooth fait intervenir de lintgration numrique ce qui peut tre coteux en CPU. - Gimbal lock problem.

5.4.Quaternions
Cest une des reprsentations les plus utilises. Un quaternion cest un vecteur de IR 4. Il est donc compos de 4 rels : q = { x, y ,z, w } avec x,y,z,w rels. q scrit aussi : q = { v, w} avec v vecteur tel que v = {x,y,z} et w rel. Les quaternions sont lorigine une extension des nombres complexes. Nous naborderons pas les dtails de cela dans ce support de cours. Est-ce quun quaternion est toujours une rotation ? Non. De la mme manire que les matrices doivent tre orthonormales pour reprsenter une rotation, les quaternions doivent tre unitaires. On dfinit la norme dun quaternion par la norme dun vecteur de IR 4 : ||q|| = SQRT ( x 2 + y 2 + z 2 + w 2 )

Page 11

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com Et on apelle quaternion unitaire un quaternion q tel que ||q|| = 1. Cest la reprsentation dune rotation. On ne va pas dtailler ici toutes les oprations que lon peut faire sur les quaternions et comment elles se font, la littrature ce sujet est dj dense. Le quaternion peut aussi tre vu partir dun axe et dun angle de cette manire : Si on une rotation reprsente par un axe v et un angle , le quaternion correspondant scrit : q = { sin (/2) * v, cos (/2) } soit q = { x*sin (/2) , y*sin (/2) , z*sin (/2) , cos (/2) } Pour composer des rotations sous forme de quaternion, on les multiplie par loprateur de multiplication des quaternions (non dtaille ici). Attention de manire gnrale la multiplication des quaternions nest pas symtrique : q1 * q2 q2 * q1. Pour inverser une rotation, on inverse le quaternion en multipliant par 1 chaque composante de laxe.

5.4.1.Interpolation des quaternions : SLERP

La mthode la plus connue est le SLERP (Spherical Linear intERPolation).

Cette mthode permet de passer du quaternion p au quaternion q de manire linaire (sur une sphre). En gros on trace une droite que lon projette sur la sphre.

5.4.2.Interpolation des quaternions : SQUAD

Lautre mthode qui est la plus utilise est le SQUAD (Spherical Cubic Interpolation). Elle est mathmatiquement identique une interpolation de Bezier ou dHermite cubique (spline). On lutilise par exemple dans les courbes danimation avec une interpolation de type TCB pour les rotations.

Page 12

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com Pour a quaternion de dpart et b quaternion darrive, on utilise les tangentes en a note p et en b note q (dans le cas des rotations, les tangentes dune cl danimation sont des rotations aussi la tangente reprsentant une direction suivre ) : squad(t, a, p, q, b) = slerp(2t(1-t), slerp(t, a, b), slerp(t, p, q)) avec t [0,1] On a la possibilit de contrler la vitesse de dpart et darrive du quaternion grce aux tangentes. Comme on le voit le squad est coteux en temps CPU et aussi en mmoire si lon veut stocker les tangentes. En rsum, pour les quaternions : Avantages : - Linterpolation donne un trs bel effet. - Pas de Gimbal lock problem. - On peut combiner les rotations en multipliant les quats. Inconvnients : - Pas de reprsentation intuitive.

5.5.Vecteur angulaire
La reprsentation dune rotation se fait sous la forme dun vecteur de IR3, v = {x,y,z} x,y et z rels. Cette reprsentation est similaire celle avec un axe et un angle. - v reprsente laxe autour duquel seffectue la rotation. - langle autour de laxe v est pla dans la norme du vecteur v. Pour combiner les rotations, il suffit dajouter les vecteurs angulaires. Avantages : - Cette reprsentation est utile pour contraindre des rotations suivants un axe et un angle, il suffit dans ce cas, de minorer/majorer les composantes du vecteur. - Ca sert aussi dans certains cas diffrencier une matrice de rotation pour avoir la vitesse angulaire (cest le vecteur angulaire). (Voir http://www.martinb.com et la partie Rotation) Inconvnients : ?

Page 13

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com

6. Changement de repre
6.1.Repre local dun objet
Lorsquun objet not OBJ est plac dans un monde 3D. Il existe au moins 2 repres. Un repre de rfrence appel le repre du monde et le repre local de lobjet OBJ. On notera Mlocal un point exprim par un vecteur en local dans lobjet. Quand on dit que ce vecteur est exprim en local cela veut dire que Mlocal est exprim en fonction des vecteurs Xlocal, Ylocal et Zlocal : Mlocal = xl * Xlocal + yl * Ylocal + zl * ZLocal ou xl, yl et zl sont des rels. Ce vecteur ne connat pas le repre du monde. Zmonde Zlocal Ylocal 0Local Mlocal Xlocal 0monde Xmonde Il existe entre les 2 repres une translation, un scale et une rotation. Cet ensemble not transformation permet de changer de repre. Chaque objet possde une transformation, cela permet de passer du repre de lobjet dans le monde. Par exemple le point Mlocal dans le repre du monde scrit : Mlocal exprim dans le monde = TransfodeOBJ * Mlocal On notera SOBJ le vecteur scale de lobjet OBJ, TOBJ le vecteur translation ( = 0Local exprim dans le monde 0monde) de OBJ et ROBJ sa rotation. Soit : Mlocal exprim dans le monde = ROBJ * (Mlocal * SOBJ) + TOBJ On applique dabord le scale puis la rotation et on ajoute ensuite la translation. Comme on la vu prcdemment, ROBJ peuttre une matrice, un quaternion etc Dans ce cas lopration * entre ROBJ et le vecteur Mlocal*SOBJ utilise loprateur * des matrices ou des quaternions Inversement, si on a un point Mmonde exprim dans le repre du monde, pour lexprimer en fonction du repre local de OBJ, il suffit dinverser la transformation OBJ et de lappliquer sur Mmonde, le vecteur rsultant sera Mmonde exprim dans le repre OBJ. Pour inverser une transfo on fait : Si Scale = {sx,sy,sz} et que sx, sy et sz sont non nuls, on a ScaleInverse = {1/sx, 1/sy, 1/sz} Linverse de la translation T est T. Et pour inverser la rotation, utiliser loprateur inverse de la reprsentation choisie, dans le case des matrices 3x3 il suffit de transposer la matrice. Remarque : Pour passer une normale dfinie dans un repre quelconque dans un autre repre, on ne fait quappliquer des rotations, il ne faut pas appliquer de translation ou de scale, sinon ce nest plus une normale. Exemple : Nlocal est la normale dune face exprime dans le repre local de lobjet, je veux lexprimer en fonction du monde, je dois faire Ymonde

Page 14

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com Nlocalexprime dans le monde = Rlocal*Nlocal Tips (En pratique) : Quand on a des algorithmes du genre :
for (int i=0 ;i<NumNormalsMesh1 ;i++) { const Vec3f& localnormalMesh1 = mesh1.GetNormal(i) ; for (int j=0 ;j<NumNormalsMesh2 ;j++) { const Vec3f& localnormalMesh2 = mesh2.GetNormal(j) ; CompareNormals(localnormalMesh1, localnormalMesh2) ; } }

Bien sr ceci est faux, car il faudrait passer les normales dans le mme repre pour les comparer. Pour ceci on a le choix de passer chaque normale dans le monde ce qui revient faire :
Transfo Transfomesh1 = mesh1.GetTransfo() ; Transfo Transfomesh2 = mesh2.GetTransfo() ; Rotation Rmesh1 = Transfomesh1.GetRotation(); Rotation Rmesh2 = Transfomesh2.GetRotation(); for (int i=0 ;i<NumNormalsMesh1 ;i++) { Vec3f localnormalMesh1 = mesh1.GetNormal(i); //Passage dans le monde de la normale du mesh 1 localnormalMesh1= Rmesh1 * localnormalMesh1; for (int j=0 ;j<NumNormalsMesh2 ;j++) { Vec3f localnormalMesh2 = mesh2.GetNormal(j) ; //Passage dans le monde de la normale du mesh 2 localnormalMesh2 = Rmesh2 * localnormalMesh2; CompareNormals(localnormalMesh1, localnormalMesh2) ; } }

On remarque qu chaque passage dans la boucle sur le mesh 2 on est oblig de passer la normale par la rotation du mesh 2 pour lexprimer dans le monde. Et a va consommer du temps CPU ! Alors que la solution idale consiste exprimer les normales du mesh 1 dans le repre du mesh 2 comme suit :
Transfo Transfomesh1 = mesh1.GetTransfo() ; Transfo Transfomesh2 = mesh2.GetTransfo() ; Rotation Rmesh1 = Transfomesh1.GetRotation(); Rotation Rmesh2 = Transfomesh2.GetRotation(); Rotation FromMesh1ToMesh2 = Rmesh1 * ( Rmesh2.Inverse() ) for (int i=0 ;i<NumNormalsMesh1 ;i++) { Vec3f normalMesh1InMesh2Coords = mesh1.GetNormal(i);

Page 15

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com
//Passage de la normale du mesh 1 dans le repre du mesh 2 normalMesh1InMesh2Coords = Rotation FromMesh1ToMesh2 * localnormalMesh1; for (int j=0 ;j<NumNormalsMesh2 ;j++) { Vec3f localnormalMesh2 = mesh2.GetNormal(j) ; //Plus besoin de transformer localnormalMesh2 car tout est dans le repre de //Mesh 2 CompareNormals(normalMesh1InMesh2Coords, localnormalMesh2) ; } }

Ceci est videmment similaire sil sagissait de vertices, on ne prendrait pas que la rotation mais toute la transfo que lon appliquerait de la mme manire pour passer dun repre lautre.

7. Exercices pratiques rsolus / tips

7.1.Projection dun point sur plan
Soit un plan, on a vu prcdemment que ce plan peut sexprimer sous forme dun vecteur 3D not O origine du plan et dun vecteur normal au plan not N : On note M un point 3D quelconque, on cherche le point P projection orthogonale de M sur le plan. Exprimer P en fonction de M, N et O. M h P O N

Une solution : On a vu prcdemment que le produit scalaire dun vecteur v et dun vecteur unitaire not N nous donne la projection de ce vecteur sur N. En prenant v = M O et N la normale du plan comme vecteur unitaire, on obtient h = v . N avec h rel. h = (M-O) . N h reprsente la distance orthogonale entre le point M et le plan, grce cette distance, on peut projeter le point M sur le plan : P=Mh*N Soit exprim en fonction de M, N et O uniquement : P = M - ((M - O) . N) * N

7.2.Intersection segment / plan

On a un plan dfini comme prcdemment par les 2 vecteurs O = {x0,y0,z0}et N. Soient les 2 points A = { x A , y A , z A }et B = { x B , y B , z B }. Ils forment un segment not [AB] qui coupe le plan au point I = {x i , y i , z i }.

Page 16

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com Trouver les coordonnes de I en fonction de O,N,A et B. B N hB PA I hA A Une solution : Exprimons lquation du plan : Si un vecteur M = {x,y,z}est dans le plan, il vrifie lquation du plan vue prcdemment qui est : N.x ( x x 0) + N.y ( y y 0) + N.z ( z z 0) = 0 Donc I doit vrifier cette quation. Soit : N.x ( x i x 0) + N.y ( y i y 0) + N.z ( zi z 0) = 0 Or I est un point du segment [AB], on peut donc lexprimer sous forme paramtrique comme on la vu prcdemment : I = A + t ( B A ) avec un t fix compris entre 0 et 1, en fait trouv les coordonnes de I revient trouver le paramtre t. Soit sous forme dcompose sur chaque variable, I scrit : x i= x A + t ( xB x A ) y i= y A + t ( yB y A ) z i= x A + t ( zB z A ) On pose le vecteur = ( B A) pour simplifier. On a donc : x i = x A + t .x y i = y A + t .y z i = x A + t .z En remplaant maintenant xi, yi et zi dans lquation du plan on a : N.x ( x A + t .x x 0) + N.y (y A + t .y y 0) + N.z (z A + t .z z 0) = 0 En extrayant t de lquation, cela nous donne : t (.x . N.x + .z . N.z + .z . N.z ) = - ( N.x (x A - x 0) + N.y (y A - y 0) + N.z (z A - z 0) ) Do : t = (N.x (x 0 - x A) + N.y (y 0 - y A) + N.z (z 0 - z A) ) / ( .x . N.x + .z . N.z + .z . N.z) En remarquant que le numrateur est le produit scalaire de N par le vecteur (O-A), cest loppos de la distance orthogonale du plan au point A note hA. Et en remarquant que le dnominateur est le produit scalaire de B-A et de N, en notant la distance de B au plan hB On a au final, on obtient un rsultat trs simple : t = hA / hA hB PB O

Page 17

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com Comme vrification, on doit avoir t [0,1] et hA et hB de signe contraires. Remarque : si hA et hB sont de mme signe, il ny a pas dintersection avec le plan, ils sont tous les 2 au-dessus ou en dessous.

7.3.Un exemple 2D : Changement de repre

Avec un repre 2D ( O, i , j ), on cherche passer dans le repre ( O, u , v ) , cest dire changer de base. Ceci est utilis pour la mapping. Trouver les coordonnes du point M (x,y) x, y rels, du repre (O,i,j) dans le repre (O,u,v) j u O v Une solution : On a dans le repre (O,i,j) : OM = x*i + y*j. On a aussi u = ui *i + uj * j et v = vi *i + vj * j Il nous reste trouver i et j en fonction de u et v, donc rsoudre le systme dquations linaires dordre 2 : u = ui *i + uj * j v = vi *i + vj * j Une fois trouv i et j en fonction de u et de v, on remplace les valeurs de i et j dans lquation OM = x * i + y * j. M(x,y) i

Page 18

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com

7.4.Un exemple 2D : Intersection segment / segment

Ce nest pas un problme 3D, mais il est intressant car assez similaire aux problmes 3D que vous pouvez rencontrer. Soient 2 segments 2D [A1A2] et [B1B2]. B1 I B2 A1 Trouver lintersection I de ces 2 segments en fonction de A1,A2,B1,B2. Une solution : Toujours sous forme paramtrique : I est sur [B1B2] il sexprime donc en paramtrique par : I = B1 + t B (B2 B1) I est aussi sur [A1A2] donc: I = A1 + t A (A2 A1) Notez que le paramtre t est diffrent sur chaque segment. Dans le cas gnral, t A t B . On pose les vecteurs VA = A2 A1 et VB = B2 B1 En remplaant ceci dans les 2 quations prcdentes, on obtient : I = A1 + t A VA = B1 + t B VB On a donc une quation 2 inconnues tA et tB . En projetant cette quation sur laxe X et sur laxe Y, on obtient un systme linaires de 2 quations 2 inconnues : A1.x + tA VA.x = B1.x + tB VB.x A1.y + tA VA.y = B1.y + tB VB.y Soit : tA VA.x - tB VB.x = B1.x - A1.x tA VA.y - tB VB.y = B1.y - A1.y Ou sous forme matricielle, en posant le vecteur T = { tA,tB }le vecteur R = B1-A1 Et la matrice 2x2 M= | VA.x | | VA.y - VB.x | | - VB.y | A2

On obtient le systme linaire matriciel suivant : MT = R Si le dterminant 2x2 de M est non nul, lquation a une unique solution qui se trouve en inversant la matrice M, linverse de M tant not M-1 On a T = M-1 R Remarque, seule la connaissance dune des 2 valeurs TA ou TB nous suffit pour trouver lintersection I. En notant det le determinant de 2 vecteurs 2D. Nous obtenons donc pour tA pa exemple :

Page 19

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com tA = det( ( B1 A1) , vB) / det (vA,vB)

7.5.Construire une matrice de rotation partir dun vecteur

Soit un vecteur V exprim dans le repre du monde. On cherche orienter un objet dans la mme direction que ce vecteur pour que lobjet regarde dans cette direction. Lobjet a pour repre les 3 vecteurs orthonorms X,Y,Z. Z V Y X Construire une matrice 3x3 de rotation note R pour orienter XYZ partir de V. On note X Y et Z les vecteurs X Yet Z aprs leur avoir appliquer la rotation cherche. Soient X = R*X Y = R*Y Z = R*Z On doit avoir au final : Y V Z X

Une solution : On cherche donc la matrice 3x3 R. En premier si V nest pas normalis, on le normalise. On doit avoir laxe X = {1,0,0} de lobjet orient dans la mme direction que V, on a vu que cela revient crire que : X= V = R * X Ce qui est quivalent dire que la premire colonne de R est le vecteur V (voir remarque sur les matrices de rotation) Pour trouver Y, on sait que Y est un vecteur orthogonal X, on prend donc arbitrairement Y = {-X.y, X.x, 0} ( attention si X.x = X.y = 0, on pose X.x = 1) . Puis on fait Y = Y / ||Y|| pour avoir un vecteur normalis. On peut vrifier que le produit scalaire de X et Y est nul. Puis pour dterminer Z on utilise le produit vectoriel entre X et Y. Soit Z = X ^ Y Par consquent notre matrice de rotation se dduit de X, Y et Z qui sont respectivement la premire colonne, la deuxime et la troisime de R. Soit R= V.x V.y V.z Y.x Y.y 0 (X ^ Y).x (X ^ Y).y (X ^ Y).z = X = Y = Z

Page 20

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com

7.6.Faire un Billboard
Il sagit ici dorienter un objet 3D en fonction de lorientation dune camra. Lobjet doit toujours face la camra dans toutes les situations. Lobjet gauche est un mesh form de 2 triangles. Celui de droite est une camra avec le vecteur indiquant la direction de la vue.

Ceci peut se reprsenter sous forme de repres avec la Transfo du mesh et celle de la camra : Zmesh Zmonde Ymonde Xmesh Xmonde Orienter le mesh en fonction de lorientation de la camra. Une solution : Il sagit ici de ne modifier que lorientation du mesh, par consquent trouver une matrice de rotation en fonction de la vue de la camra sera suffisant. Il nous faut dterminer le vecteur direction de la camra dans le monde (Zcam sur le schma), il indique dans quelle direction regarde la camra. Le scale et la translation de la camra nous importent peu, seule sa rotation sous forme de matrice note Rcam nous intresse. Calculons le vecteur Zcam dans le monde. Dans ce cas, il est utile davoir reprsent Rcam sous forme dune matrice 3x3. Il est facile de vrifier quavec Zcam = {0,0,1}dans le repre de la camra, si on calcule le vecteur : Zcam dans le repre du monde = Rcam * {0,0,1} on trouve la dernire colonne de la matrice (ou ligne dans la notation Amricaine des matrices) Comme on veut que lobjet soit orient vers la camra et non dans le mme sens, il nous faut prendre comme vecteur dorientation du mesh loppos de Zcam dans le monde : soit -Zcam dans le repre du monde. Grce ce vecteur, il ne nous reste plus qu construire une matrice de rotation pour orienter notre mesh. Et en utilisant lexemple prcdent, on calcule cette matrice. Ymesh Zcam Xcam Ycam

Page 21

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com

7.7.Collisions Rayons / Faces

Dcrire lalgorithme utilis pour faire des collisions rayon / face. Une solution : Le rayon est reprsent par un segment de droite en paramtrique. Il suffit avec ce qui prcde de faire lintersection entre le segment et le plan dans lequel se trouve la face. Pour dfinir la plan partir dune face, on prend la normale de la face comme normale du plan et un des vertex de cette face comme origine du plan. Si le rayon intersecte le plan, il reste dterminer si lintersection se trouve lintrieur de la face, pour cela il y a plusieurs mthodes possibles. Par exemple : - Calculer dans le plan, les vecteurs normaux aux edges de la face : le produit scalaire entre lorigine du edge et la normale ledge doit tre ngatif si le point est lintrieur. (lintrt de cette mthode est que lon peut stocker les normales aux edges) - On peut aussi utiliser le produit vectoriel entre un edge et le vecteur form par le point moins lorigine du edge, le vecteur rsultant devrait se trouver du mme ct de la normale pour tous les edges sil est lintrieur.

7.8.Quelques notions de balistique (dynamique du point) - Particules

V Z M F Y X On considre un objet de masse m dans un le repre du monde, il peut tre dcrit comme un point 3D not M si lon ne considre pas son orientation. On cherche lancer cet objet dans une direction V0 (cest sa vitesse initiale). Cet objet est soumis une force F (gnralement la gravit). Trouver en fonction du temps comment faire voluer la position de cet objet, en fait il sagit ici de dcrire lalgorithme utilis en pratique pour faire bouger lobjet. Une solution : Avec le principe fondamental de la dynamique, on a F=ma ou F reprsente les forces appliques sur M, m est la masse de lobjet et a est son acclration. Ceci nous permet de dterminer a, par intgration, on a la vitesse v : v (t) = a(t) dt Et enfin la position en intgrant la vitesse : p(t) = v(t) dt Comment se traduit ceci en pratique :

Page 22

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com Comme on ne peut intgrer ces quations sur tout lintervalle de temps la fois pour avoir une formule gnrale, on casse le temps en petits intervalles et on considre que : Si les forces reprsentes par F, ne varient pas au cours du temps, avec la formule F = m a on a une acclration constante au cours du temps : a=F/m Pour trouver la vitesse en fonction du temps, on utilise la formule dintgration dEuler : v( t + t ) = v( t ) + t * ( dv( t + t ) / dt) Or dv( t + t ) / dt = a( t + t ) = a (constant par rapport t) Donc la vitesse scrit : v( t + t ) = v( t ) + t * a En pratique, on peut prendre t = 1 / 30 secondes. Ensuite le mme manire, pour la position on a : p( t + t ) = p( t ) + t * ( dp( t + t ) / dt) Or dp( t + t ) / dt = v( t + t ) que lon a dj calcul, do : p( t + t ) = p( t ) + t * v( t + t ) Remarque : On est toujours oblig de stocker ltat prcdent de lobjet (car pour calculer la nouvelle vitesse et position il nous faut la vitesse et la position prcdente). Cette mthode dEuler est peu prcise mais elle est rapide et convient parfaitement dans ce cas tant que lon ne veut pas calculer de manire plus exacte la trajectoire. Sinon il faudra utiliser une autre mthode dintgration comme Runge Kutta dordre 4 (RK4) par exemple. On ne rentrera pas dans les dtails de ces autres mthodes.

8. Remerciements
Merci Andr Bertrand, Jean-Franois Lopez et Nicolas Dalstein de Kalisto pour leurs remarques et corrections.

9. Rfrences
Approfondir vos connaissances les quaternions (oprations, interpolation etc) : http://www.gamasutra.com/features/19980703/quaternions_01.htm ou http://freefall.freehosting.net/articles/quaternions_1.html ou http://www.gamedev.net/reference/programming/features/whyquats/ La physique selon Chris Hecker (avec exemples de code fournis dont celui sur lorthonormalisation des matrices 3x3) : http://www.d6.com/users/checker/ Approfondir les angles dEuler : http://vered.rose.utoronto.ca/people/david_dir/GEMS/GEMS.html Quickmaths permet de calculer sur le web par exemple des dterminants de matrices 3x3, son but est de rsoudre des problmes simples de maths sur le web : http://www.quickmath.com aussi sur http://www.calc101.com/ Des tas de formules, de leons sur lalgbre : http://www.algebrahelp.com/ Leons de maths : http://www.sosmath.com/index.html Archives de maths : http://archives.math.utk.edu/calculus/crol.html Distance entre ligne et point http://geometryalgorithms.com/Archive/algorithm_0102/algorithm_0102.htm

Page 23

Formation sur les mathmatiques lis la 3D 2001 2004 David Lanier www.dl3d.com Du code pour tout ce qui est gomtrique dont certains sont applicables aux jeux : http://www.magic-software.com Initiation aux maths 3D : http://www.geocities.com/pcgpe/graphics.html ou ici avec des petits tests de questions : http://chortle.ccsu.ctstateu.edu/vectorLessons/tutorialIndex.html Tout le process dun jeu du point de vue programmeur :
http://www.nihilistic.com/GDC2000/GDC2000Tutorial/index.htm

3D, physique, cinmatique etc http://www.martinb.com A propos des splines (TCB, Hermite, Bezier) http://www.cubic.org/~submissive/sourcerer/hermite.htm Interpolation de matrices polynmiales (article dur) http://www.nd.edu/~pantsakl/elecpubs/IJC_whole.pdf Matrices et quaternions faq : http://skal.planet-d.net/demo/matrixfaq.htm (Faites gaffe y a des conneries dedans, sur le dterminant au moins) Numerical recipes in C : http://lib-www.lanl.gov/numerical/bookcpdf.html Mthodes de calcul numrique avec programmes en C : http://www.univ-lille1.fr/eudil/jbeuneu/index.html

Page 24