Support mathématique
Matrices et opérations matricielles
Introduction
Il doit être facile de trouver sur le net des tas et des tas de textes traitant de ces sujets, mais ils sont tous en anglais et puis bon, autant partir du bon pied et commencer par le début. Hé oui, mauvaise nouvelle, la 3D c'est avant tout un problème mathématique.
Nous allons commencer en 2D, car c'est quelque chose qui est en général beaucoup plus instinctif car on peut le dessiner facilement, Paint ayant encore de beaux jours devant lui.
Mais avant tout cela, je vais vous dire ce que c'est qu'une matrice et une opération matricielle, d'un point de vue totalement abstrait. La seule chose dont vous devez toujours vous souvenir, c'est que, comme pour tout, on peut toujours s'en passer, même dans la 3D, il ne s'agit juste que d'une manière plus simple pour représenter les choses.
Car, après tout, le jour où le mec qui a inventé les maths (Monsieur Mathématique?) s'est dit que l'opération << + >> serait une bonne idée, il n'a peut-être pas songé tout de suite à l'opération << * >>. Pour faire 4*3, il s'est dit qu'il était tout aussi simple de faire 4+4+4, ce dont tout le monde en conviendra.
Bon, pour faire 4*48 ça commence à devenir un peu chiant, mais c'est toujours faisable, non ? Par contre pour faire 3.14159*78.9, c'est plus compliqué. Bien sûr, on peut s'en sortir, en multipliant tout par un facteur un million pour éviter les virgules, et puis tout diviser après. Après tout, n'est-ce pas là justement le principe dit de << la virgule fixe >> ? Mais je m'égare...
Vous aurez compris, il semblait utile de définir un nouveau concept, la multiplication, avec des propriétés à elle, des opérateurs à elles, des inversions, des trucs et des machins qui n'existaient pas avec l'addition, même si la multiplication n'est jamais basée que sur l'addition. Vous devez avoir à l'esprit que la multiplication est inutile, on peut toujours s'en passer, comme on peut toujours se passer des calculs matriciels, c'est juste que c'est diablement plus simple.
Matrice
Une matrice, c'est un tableau de réels, on parlera de la taille d'une matrice comme on parle de la taille d'un tableau. C'est un tableau bi-dimensionnel, il est donc constitué de lignes et de colonnes. Une matrice 4x3, c'est un tableau contenant 4 lignes et 3 colonnes.
On dit d'une matrice qu'elle est carrée quand son nombre de lignes est égal à son nombre de colonnes. Une matrice dite identité est une matrice carrée, dont tous les éléments sont nuls sauf les éléments de la première diagonale qui valent tous un.
En général, la notation préférée pour les matrices ce sont les lettres majuscules. C'est ainsi que l'on parlera de la matrice A, ou B, etc. Quand on dit l'élément A(i,j) il s'agit de l'élément du tableau se trouvant à la ligne i et à la colonne j. Les lignes et les colonnes sont numérotées à partir de 1.
Bon, jusque là, rien d'infaisable.
On peut additionner deux matrices, à condition qu'elles soient de mêmes tailles (même nombre de lignes et même nombre de colonnes), le résultat étant une troisième matrice où chaque élément est la somme des éléments qui se trouvaient à la même position dans les matrices de départ.
n peut surtout multiplier deux matrices. Malgré ce que l'on pourrait supposer, ça n'est pas du tout la même chose que l'addition (c'était trop simple, non ?). On peut multiplier une matrice de taille (i,j) avec une matrice de taille (j,k), et ainsi former une matrice de taille (i,k) selon la règle suivante :
Si C=A*B, alors C(i,k)=Somme(Pour m allant de 1 à j)A(i,m)*B(m,k)
Oula.
Bon, un petit exemple :
ca nous donne
Attention ! Contrairement à l'addition et contrairement à la multiplication << classique >>, la multiplication matricielle n'est pas commutative. En d'autres termes :
A*B <> B*A
On parle de la transposée d'une matrice lorsque l'on a inversé les lignes et les colonnes. On parle alors de A' ou At
La transposée de
On dit d'une matrice qu'elle est une matrice ligne si elle n'a qu'une seule ligne. De même, on dira qu'une matrice est une matrice colonne si elle n'a qu'une seule colonne. La transposée d'une matrice ligne donne une matrice colonne et vice-versa.
L'inverse d'une matrice A, notée A-1, est telle que A*A-1=I, où I est la matrice identité. En général on ne parle de matrice inverse que pour les matrices carrées. Une propriété dit que si A est une matrice carrée, alors A*A-1= A-1*A=I, ce qui n'était pas évident, je vous rappelle que le produit matriciel n'est pas commutatif.
Bon, normalement ici vous devez commencer à en avoir marre de ces cochonneries de matrices. On va donc passer à légèrement autre chose.
Matrices et transformations géométriques
Peut-être savez-vous que pour faire tourner un point (x,y) autour de l'origine, dans un plan, la formule à utiliser est :
x'=x*Cos(a)-y*Sin(a) y'=x*Sin(a)+y*Cos(a)
Mais si vous regardez cette forume avec ce que l'on vient de voir un peu au dessus, vous vous rendrez compte qu'il s'agit de la multiplication matricielle suivante :
Ainsi donc, une rotation peut se représenter par une multiplication matricielle, pour autant que les points soient eux-mêmes représentés par des matrice colonnes.
A présent, si vous voulez faire deux rotations successives, vous allez devoir utiliser deux fois cette formule. Et si vous voulez faire deux rotations à 2000 points, vous allez devoir, finalement, vous taper 4000 opérations matricielles.
Et bien non (et c'est là qu'on va piger à quoi vont nous servir les matrices), car la multiplication de deux matrices de transformation (comme la matrice de multiplication vue plus haut) est une nouvelle matrice de transformation, qui correspond à la composition des deux transformations. Si vous ne comprenez pas ce que je viens de raconter, ça se résume par :
Si A est une matrice de rotation d'un angle a, et B est une matrice de rotation d'un angle b, alors A*B est une matrice de rotation d'angle a+b.
Bref, pour vos 2000 points, vous faites d'abord le calcul du produit matriciel et ensuite vous faites uniquement 2000 opérations matricielles sur vos points. En pratique ici, c'est totalement inutile car tout le monde sait bien qu'il aurait suffit de créer une autre matrice de rotation dont l'angle est la somme des deux angles, mais ça n'est pas toujours aussi simple que ça.
Figurez-vous qu'il existe des matrices de translation, de rotation, de scaling, de projection, etc, etc. Si vous devez faire une suite d'opérations de ce genre à un certain nombre de points, vous commencer par calculer la matrice de transformation qui est la composition des opérations élémentaires et vous appliquez cette matrice à vos points. Le gain est énorme.
Les coordonnées normalisées
Si vous vous demander à quoi peut bien correspondre une matrice de translation en 2D, et que vous chercher une matrice 2x2 comme pour la matrice de rotation, vous allez chercher pour rien, elle n'existe pas. Pour la trouver, il va falloir introduire un nouveau concept : les coordonées normalisées.
Vous savez que dans un plan, un point se représente par deux valeurs, un x et un y. Voici donc un nouveau concept : moi je dis qu'à présent, un point se représentera par trois valeurs : un x, un y et un t.
Là vous vous dites, ça y est, le Plouf a perdu les pédales, dans un plan il n'y a que deux dimensions et là il nous tape trois variables, comme dans l'espace, c'est complètement louf.
Et vous aurez raisons, sauf si je vous dit que le point (1,2,1) correspond au point (2,4,2). En fait, la formule pour passer d'une représentation à une autre est :
old_x=x/t old_y=y/t
Bref, si on multiplie tout par 2, on est toujours au même endroit. Jusque là, cette nouvelle invention semble donc totalement inutile. Sauf si je vous demande (pour rigoler) où se trouve le point (1,4,0).
Heu, en (infini,infini) ? Wais, mais c'est pas très précis, ça, non ? Parce que (4,1,0) et (1,4,0) ça doit sûrement être deux choses différentes alors que dans le « vieux » système c'est tout les deux le « point » (infini,infini). Me voilà capable de distinguer des choses qui étaient indistinguables avant. Bien joué mais ça sert à quoi ? C'est quoi finalement, ce point (1,4,0) ?
Vous allez comprendre, imaginez le point (1,4,1), bon c'est facile, non ? Ensuite prenez le point (1,4,0.1). Ha, il est un peu plus loin (en 10,40). Ensuite le point (1,4,0.001), il est loin, lui, en (1000,4000), etc... Et bien tous ces points sont alignés sur une droite de pente 4. Le point (1,4,0), c'est juste le « dernier » point de la droite. Un point qui est à l'infini, certes, mais pas n'importe où à l'infini : à l'infini sur une droite donnée. Bref, ce point, c'est une direction, une direction qui est la direction de la droite de pente 4. De même que le point (4,1,0) c'est le point qui représente la direction de la droite de pente un quart.
L'avantage du système ? On ne fait plus de différence entre un point et une direction, c'est devenu deux concepts identiques, qui s'expriment exactement de la même façon. Mais à quoi ça sert ? Vous ne voyez pas ?
Si je suis en un point et que je regarde dans la direction de pente 4 (wé, en fait je regarde le point 1,4,0), quelle direction je regarde si je tourne mon regarde d'un angle a ?
Il suffit de faire subir une rotation d'angle -a au point (1,4,0), grâce à quoi ? A une matrice de rotation, bingo ! Voilà comment on peut faire tourner des lumières qui sont à l'infini dans les moteurs 3D...
La matrice de rotation dans ces nouvelles coordonées s'exprime comme ceci :
Ben wé, c'est une matrice 3x3, puisque nos points sont à présent des matrices colonnes de trois lignes. (3x1)
Et, je vous le donne dans le mille, la matrice de translation, c'est
Essayez, vous verrez que ça marche. A présent savoir pourquoi ça se met à fonctionner en 3x3 alors que ça ne marchait pas en 2x2, j'ai pas envie ici de faire des tats de calculs existentiels, je vous demande d'admettre que c'est comme ça et pas autrement.
A présent, comment on fait pour faire tourner un point autour d'un autre point quelconque ? Et bien on commence par translater le centre de rotation à l'origine, ensuite on applique la rotation, et puis on translate le résultat pour replacer le centre au bon endroit. Il s'agit de trois opérations consécutives, qui peuvent s'exprimer en une seule, grâce à la combinaison des opérations avec le produit matriciel. C'est-y pas beau ? Sans compter qu'on peut même translater un point « à l'infini » d'une distance infinie pour le ramener à l'origine, et vice-versa, il suffit de mettre dt=0. (ce qui arrive rarement, j'en conviens, en général on laisse dt à 1).
Dans toutes ces matrices, il y en a une qui est amusante, c'est justement la matrice Identité, c'est la matrice qui ne fait rien :
Si vous transformez un point avec cette matrice, vous allez obtenir le point lui-même.
La notion d'inverse de matrice prend tout son sens, vu que la composition d'une matrice avec son inverse donne l'identité, on comprend que si une matrice fait une transformation, la matrice inverse fait l'opération inverse. Finalement, l'inverse d'une matrice de rotation d'angle a, c'est une matrice de rotation d'angle -a. De même pour la translation vous pouvez vérifier vous-même que
Le fait que le produit matriciel n'est pas commutatif prend également tout son sens, il n'est en effet pas du tout équivalent de faire la rotation avant la translation ou la translation avant la rotation. Faites un dessin, vous comprendrez tout de suite pourquoi. Il faut donc toujours bien se méfier et vérifier que l'on compose les matrices dans le bon ordre.
On peut donc construire la matrice qui tourne un point x (x,y,t) autour d'un centre (cx,cy,ct) d'un angle a :
Avec x'=R*x
Remarquez que le produit se fait en sens inverse, on commence par les dernières opérations.
Tout ce que je viens de raconter est immédiatement adaptable en 3D. Au lieu de jouer avec des (x,y,z), on joue avec des (x,y,z,t), les matrices de transformation sont des matrices (4x4) et vous pouvez facilement trouver dans la littérature spécialisée (la doc d'opengl par exemple) quelles sont les matrices de transformation intéressantes.
Bien, à présent que je vous ai convaincu de l'utilité des matrices, il ne vous reste plus qu'à trouver un tutoriel sérieux là dessus, qui ira surement beaucoup plus en profondeur que moi. Les matrices, c'est un sujet presque inépuisable, et qui ne sert pas qu'en géométrie (en fait ça sert partout).
Finalement, la première chose à faire quand on se met à programmer un moteur 3D, c'est de programmer une classe Matrix...
Notion de base
Pas à prendre dans le sens « notions basiques » mais bien dans le sens « qu'est-ce qu'une base ? »
Commençons comme toujours en 2D avec un petit problème assez simple. Nous définissons un rectangle comme ceci :
Si je vous demande à quel endroit se trouve le coin supérieur gauche, vous pouvez tout de suite me répondre, il se trouve en (-a,-b). Maintenant plaçons ce rectangle comme ceci :
Même si je vous donne la position du nouveau centre et de l'angle de rotation, vous ne pouvez pas immédiatement me donner la position du coin supérieur gauche du rectangle. Il faut faire un calcul.
En fait qu'allez-vous faire ? Une méthode classique, c'est de prendre ce point (-a,-b), de lui appliquer la même rotation suivie de la même translation que celles appliquées au rectangle. Vous obtiendrez en effet la position du point.
Mais il existe une autre manière de voir les choses (qui revient, bien sûr, au même), c'est de dire que la position du point (-a,-b) original se trouve au point... (-a,-b), après tout, c'est toujous le coin supérieur gauche et il n'y a pas de raison que le coin supérieur gauche se trouve ailleurs qu'en (-a,-b). Et vous aurez parfaitement raison, de la même manière que quand l'on vous demande à quelle hauteur vous vous trouvez, vous donnerez sûrement la hauteur de la chaise sur laquelle vous êtes assis(e), sans prendre en compte la hauteur du bâtiment, ni la hauteur de la colline sur laquelle se trouve ce bâtiment, etc...
L'important, c'est de savoir qu'il s'agit de la hauteur par rapport au plancher. Si on est capable de donner la hauteur du plancher par rapport au sol, et la hauteur du sol par rapport au niveau de la mer, on saura bien donner votre hauteur par rapport au niveau de la mer. Et bien ici c'est la même chose, le point se trouve en (-a,-b) par rapport... au premier schéma, pas du tout par rapport au second. La seule question à se poser, c'est : « comment passer du premier schémas au second ? ».
La réponse est évidente, il faut faire une translation, suivie d'une rotation, ça revient au même. En réalité, la bonne manière de représenter la seconde figure est celle-ci :
Et donc, si on vous demande la position du coin supérieur gauche, vous répondrez deux choses : (-a,-b), et surtout comment passer du premier repère d'axe au second. Et comme pour passer de l'un à l'autre, il s'agit d'une combinaison d'opération, devinez ce qu'on va donner pour décrire le passage d'un repère (appelé base) à une autre ? Une matrice, bien entendu...
Finalement, une coordonée ne représente rien si elle n'est pas accompagnée d'un renseignement qui dit de quelle base on parle.
A quoi ça sert me direz-vous ? C'est de toutes façons évident, tout ça... Oui ?
Voyons si vous avez compris alors : moi je vous donne un point quelconque, (x,y), se trouvant dans la « grande » base, pas celle de travers qui est celle du rectangle. Ce que je vous demande, c'est de me dire si ce point (x,y) se trouve dans le rectangle ou pas. Facile ?
Ce problème n'est à prioris pas facile, il faut regarder les équations des droites des côtés du rectangle, etc, etc, etc, bonne chance...
Alors qu'il suffirait de se demander : « quelles sont les coordonées de ce point dans la base du rectangle ? » Si on connaît ça, le problème devient très bête, car ça revient à savoir si un point se trouve dans un rectangle qui est parrallelle aux axes. Ce qui se code facilement par « si x est compris entre -a et a et y compris entre -b et b ».
Et comment connaître la coordonée de (x,y) dans la base du rectangle ? Ben pardis, vous pouvez faire l'autre opération inverse grâce à cette fameuse matrice qui représente la position du rectangle dans la grande base, faites donc l'opération inverse ! Et hop, un petit calcul d'inversion de matrice, un petit produit matriciel, et quelques petits tests idiots, et le tour est joué !
Moralité : quand un problème se pose, demandez-vous toujours si il n'est pas plus simple de le résoudre dans une base appropriée. Vous verrez un peu plus tard qu'il s'agit d'une des bases (c'est le cas de le dire, hihi) de tout moteur 3D. Vous verrez que tout objet possède une base « locale », dont la position est exprimée par rapport à une base « globale », commune à tous les objets. Mais je m'avance...
Notion d'espace
Un espace, ça n'est jamais qu'une base, en gros c'est équivalant. Quand on parle d'un point, on doit préciser sa base, et donc finalement dans quel espace il se situe. Votre hauteur, celle finalement de la chaise, se trouve dans l'espace « pièce », tandis que la hauteur du plancher se trouve dans l'espace « maison », et ainsi de suite.
Dans un moteur 3D, on peut dire qu'il y a 4 espaces, ou plutôt 4 types d'espace. J'y arrive.
Depuis le chapitre précédent, vous pouvez imaginer que chaque objet (3D ou pas) est défini dans sa base propre. Un rectangle (cube, ...) est défini par une paire (a,b), un cercle par un rayon, etc... On suppose donc que le rectangle est centré dans sa base, de même que le cercle. On peut même tout normaliser, en disant qu'un cercle est finalemement toujours de rayon 1. Il s'agit en fait de l'objet abstrait, qu'il faudra « placer » dans un espace commun, là où se trouvent rassemblés tous les objets, la scène où se déroule l'action.
Il faudra donc, pour chaque objet, connaître une matrice (une base, un repère, etc...) qui permette de passer de la base de l'objet (« l'espace objet ») à la base globale (« l'espace global ». Mais cela suffit-il ? Pour décrire la position de chaque objet dans l'espace, certainement, mais pas pour les afficher à l'écran. Il faut connaître un renseignement en plus.
Car où se trouve la caméra ? En général dans les moteurs simples, la caméra se trouve à l'origine et regarde dans la direction des Z, alors que l'axe des X est horizontal et l'axe Y vertical. Evidement, ça n'est pas très souple...
Le problème, c'est que les formules qui permettent de projeter un point à l'écran sont des formules qui supposent que la caméra se trouve à l'origine, regarde l'axe des Z etc...
Alors que faire ? Le plus simplement du monde, il faut déplacer tous les objets de sorte que ceux qui sont devant la caméra et dans l'axe de regard de cette caméra se retrouvent placés sur l'axe des Z, et ainsi de suite. Finalement, il faut faire un nouveau changement de base, pour se déplacer dans « l'espace caméra ». Quelle est la matrice qui correspond à ce changement de base ? Tout simplement la matrice qui explique comment la caméra est située par rapport à sa position « de base », et donc quelle est la position relative de la caméra par rapport à l'origine de l'espace global, quelle est son orientation, etc... Vous voulez faire tourner la caméra? Multipliez sa matrice par une matrice de rotation...
Le dernier espace est finalement l'écran lui-même, espace en deux dimensions, c'est l'étape ultime, ce que le joueur ou l'utilisateur verra. C'est également une base, et il existe une matrice de transformation qui permet de passer de l'espace caméra à l'espace écran. Il s'agit en fait de la représentation matricielle des formules classiques :
u=x/z v=y/z
Finalement, si j'ai un point d'un objet, dans l'espace objet, mettons ce fichu coin supérieur gauche, et que je veux connaître sa position à l'écran, je dois faire les opérations suivantes :
- transformer ce point avec la matrice de base de l'objet, pour connaître sa position dans l'espace « global »
- transformer cette position globale avec la matrice de base de la caméra, de manière à connaître sa position dans l'espace « caméra »
- transformer cette position caméra avec la matrice de projection, de manière à connaître sa position dans l'espace « écran »
Trois transformations à la suite ? Non ! Une seule ! Je vous rappelle que l'on peut une bonne fois pour toute combiner toutes ces transformations au moyen du produit matriciel. Cette combinaison doit être faite à chaque image (car d'une image à une autre, la position de l'objet ou de la caméra aura sûrement changé), mais pas à chaque point. Pour chaque point, on fera UN et UN SEUL produit matriciel. Le bonheur, ça trace...
Enfin, tout ça c'est la théorie...
Mais ça vous permet à présent de comprendre l'origine des trois matrices que l'on peut modifier dans OpenGl, la matrice de l'objet « model matrix », la matrice caméra « camera matrix » et la matrice de projection « projection matrix ». La théorie n'est donc pas si éloignée que cela de la pratique...