Les moteurs 3D actuels utilisent de nombreux outils mathématiques pour augmenter leurs puissances et leurs performances. Il y a les vecteurs, les matrices (cf. mini-articles sur le sujet : A quoi servent les matrices dans un moteur 3D ? ) aujourd'hui découvrons un autre de ces composants essentiels : les quaternions.

Qu'est-ce qu'un quaternion ?
Tout d'abord, sachez qu'il n'est pas nécessaire de bien comprendre les quaternions eux-mêmes pour comprendre leurs utilisations en 3D. Mais nous allons quand même nous intéresser à leur nature pour avoir une vue d'ensemble assez complète.

La théorie des quaternions fut découverte en 1843 par William Rowan Hamilton (1805-1865), qui avait déjà développé celle des nombres complexes. Si vous connaissez les nombres complexes, vous comprendrez facilement ce qu'est un quaternion. En effet ...

Un nombre complexe s'écrit :

C = a + i.b

Q = a + i.b + j.c + k.d

i*i = j*j = k*k = -1

i*j = -j*i = k

j*k = -k*j = i

k*i = -i*k = j

Tout comme pour les nombres complexes, on peut définir un certain nombre d'opérations sur les quaternions dont :

L'addition :

Q0 + Q1 = (a0+a1) + (b0+b1)i + (c0+c1)j + (d0+d1)k

Q0.Q1 =

(a0 + i.b0 + j.c0 + k.d0).( a1 + i.b1 + j.c1 + k.d1)

= (a0.a1 - b0.b1 - c0.c1 - d0.d1)

+ (a0.b1 + b0.a1 + c0.d1 - d0.c1 ).i

+ (a0.c1 - b0.d1 + c0.a1 + d0.b1 ).j

+ (a0.d1 + b0.c1 - c0.b1 + d0.a1 ).k

Bien que l'étude des quaternions soit particulièrement passionnante, l'énoncé de l'ensemble de leurs propriétés dépasse le cadre de ce mini-article. Retenons simplement celles-ci :

• Le conjugué d'un quaternion Q( a, b, c, d ) est : Q = a - i.b - j.c - k.d
• La norme d'un quaternion Q(a, b, c, d) vaut:
  
  
  

Lorsque la norme d'un quaternion vaut 1 on dit que le quaternion est normalisé. C'est cette catégorie de quaternions qui va nous intéresser pour la 3D.

Interprétation des quaternions en 3D
Après cette introduction un peu formelle, voyons comment les quaternions sont perçus en 3D. C'est donc les quaternions normalisés qui nous intéressent. Tout quaternion normalisé peut être associé à une rotation vectorielle 3D : Une rotation vectorielle est une rotation autour d'une droite qui passe par l'origine. En effet, il faut 3 valeurs pour la direction de l'axe et 1 pour l'angle de la rotation. Soit 4 valeurs, ça tombe plutôt bien ;).

Si la rotation est autour d'un axe orienté selon le vecteur V de coordonnées (x,y,z) (le vecteur étant normalisé) et d'angle a, le quaternion associé vaut :

Q = cos(a/2) + i.x.sin(a/2) + j.y.sin(a/2) + k.z.sin(a/2).

La démonstration de cette formule est trop longue pour être décrite ici et dépasse le cadre de ce mini-article. Il est à noter que la rotation d'axe orienté selon -V et d'angle -a possède la même représentation :

Q’ = cos(-a/2) + i.(-x).sin(-a/2) + j.(-y).sin(-a/2) + k.(-z).sin(-a/2)

= cos(a/2) + i.(-x).(-sin(a/2)) + j.(-y).(-sin(a/2)) + k.(-z).(-sin(a/2))

= cos(a/2) + i.x.sin(a/2) + j.y.sin(a/2) + k.z.sin(a/2)

= Q

Ce qui est normal puisque les rotations sont équivalentes, mais on constate quand même que cette transformation n'est pas bijective.

Utilisation en 3D
Considérons un objet 3D : modifier son orientation revient à faire pivoter l'objet autour d'un ou plusieurs axes. Or la composée de 2 rotations passant par le même point (dans notre cas l'origine) est une rotation passant par ce point. Donc, quelque soit l'orientation d'un objet dans l'espace, on peut décrire cette orientation par une rotation (celle qui résulte de la composition des rotations précédemment appliquées). On peut donc utiliser les quaternions pour représenter les orientations des objets dans l'espace.

Si l'on souhaite modifier l'orientation de cet objet, il suffit de construire le quaternion associé à la rotation souhaitée puis de l'appliquer :

• L'orientation de l'objet est représentée par : Q
• La rotation est représentée par : Qr
• L'orientation de l'objet après rotation est : Q’ = Qr.Q

Généralement, les orientations et les rotations dans l'espace sont représentées par des matrices 3x3. Comparons donc les quaternions et les matrices pour une opération de rotation. Pour multiplier 2 matrices, il faut 27 multiplications et 18 additions scalaires. Pour multiplier deux quaternions, il faut 16 multiplications et 12 additions scalaires.

Le gain n'est pas négligeable, si en plus on considère que pour mémoriser un quaternion il faut seulement 4 valeurs contre les 9 de la matrice.

Quaternion et matrice
Certains dirons : « Ok, tout cela est très bien mais les API 3D ne veulent que des matrices !». Heureusement, tout quaternion (normalisé) peut être converti en matrice et réciproquement.

Voici la formule pour convertir un quaternion en matrice : (Attention si vous travaillez en repère indirect, vous devrez transposer cette matrice)

Q = W + i.X + j.Y + k.Z

Exemple : Rotation d'un angle A autour de l'axe Z. Le quaternion vaut :

Q =

cos(A/2) + i.sin(A/2).0 + j.sin(A/2).0 + k.sin(a/2).1 =

cos(A/2) + k.sin(A/2)

En appliquant les formules de trigonométrie suivantes :

1 - 2sin²(A/2)   =   cos(A)

2*sin(A/2)*cos(A/2)   =   sin(A)

on obtient la matrice de rotation autour de Z telle qu'elle est décrite dans le mini-article : A quoi servent les matrices dans un moteur 3D ? )

Evidemment, cela contrebalance un peu l'enthousiasme que peuvent soulever les quaternions. En effet, si dans votre moteur 3D vous avez des objets plutôt statiques, il vaut mieux, pour les représenter, mémoriser les matrices afin de ne pas faire la conversion à chaque génération d'image. Si par contre les objets sont très animés, le gain dans les calculs de composition peut largement compenser la perte due à la conversion.

Principale application
Dans le cas des objets animés, l'utilisation des quaternions est encore plus intéressante que ce que nous venons de voir. En effet, très souvent quand on souhaite animer des objets on a besoin d'interpolation. Pour les positions, les méthodes sont bien connues, mais pour les orientations ? Eh bien pour les orientations, les quaternions nous offrent une méthode très élégante, il s'agit de l'interpolation linéaire sphérique, connue sous le nom de SLERP (pour Spherical Linear intERPolation).

Les quaternions permettent d'interpoler les orientations
Considérons un objet d'orientation Q, devant passer d'une orientation Q0 (à T=0) à une orientation Q1 (à T=1). Pour obtenir les positions intermédiaires, il suffit d'utiliser la formule suivante :

Pour T variant de 0 à 1 :

Slerp( Q0, Q1, T ) = Q0*sin( (1-T).Omega )/sin(Omega) + Q1*sin( T.Omega ) /sin(Omega)

Avec Cos( Omega ) = Q0.Q1 donc Omega = cos-1( Q0.Q1 )

Cette méthode est particulièrement utilisée par les moteurs pour l'interpolation de positions clefs (notamment pour les personnages) et pour la cinématique inverse. Il existe d'autres façons d'interpoler mais elles sont beaucoup moins utilisées.

Conclusion
En 3D, on utilise essentiellement les matrices homogènes (c'est-à-dire 4x4) car elles permettent de représenter de manière homogène (c'est-à-dire en une seule notation mathématique) les transformations de l'espace. Ces transformations sont généralement des changements d'orientation et de position. Or, quand on travaille essentiellement sur les positions on préfère utiliser des vecteurs, plus faciles à manipuler et plus rapides à calculer. Les quaternions permettent de faire la même chose avec les orientations.

J'espère que ce mini-article aura permis de démystifier ces objets encore un peu exotiques que sont les quaternions et qu'il aura aider à mieux comprendre leur utilisation par les moteurs 3D.

Les différences entre ces deux types de processeurs sont nombreuses et il serait trop long de vouloir les détailler toutes. Par contre, on peut se pencher sur les différences qui permettent de répondre à une question que beaucoup d'utilisateurs se sont posés à savoir : pourquoi un processeur graphique n'a-t-il pas des fréquences de fonctionnement aussi élevées qu'un microprocesseur principal d'ordinateur ? Prenons par exemple le NV35, dernier processeur graphique de NVidia. Il plafonne commercialement à 450 MHz alors qu'un microprocesseur comme le POWER G4 d'Apple, destiné pour les ordinateurs de bureau et réputé pour être un microprocesseur ayant une des plus faibles fréquences, plafonne à 1,45 GHz, soit 3 fois plus. Si on fait la comparaison avec un Pentium 4, on atteint des sommets avec un facteur de différence de fréquence de fonctionnement avec le NV35 frolant les x7 !

La réponse n'est pas simple, et va nous entraîner dans les méandres de la conception des processeurs et des choix parfois douloureux que doivent faire les ingénieurs. Pour éviter que vous vous y perdiez, voici un résumé de la réponse finale : Un processeur graphique contient environ 4 fois plus de transistors destinés aux opérations logiques qu'un microprocesseur et cela génère des problèmes de maîtrise de dégagement de chaleur et de consommation d'énergie, de plus il a des difficultés à utiliser des optimisations d'architecture permettant de monter en fréquence, comme la décomposition des unités d'exécution (à ne pas confondre avec les unités de calcul comme nous le verrons). Cela est du à des particularités dans l'architecture des processeurs graphiques avec en particulier l'existence de plusieurs unités de calculs en série. A présent, voyons ça en détail.

Deux catégories de transistors
On peut classer l'utilisation des transistors dans un processeur en deux groupes. Le premier correspond aux transistors destinés à effectuer des opérations logiques, le second est destiné à stocker des informations : buffer, registre, ... mais le gros de ces transistors est constitué par la mémoire cache. Pourquoi je vous raconte cela ? Parce que les transistors servant au calcul logique sont les plus utilisés, et ce sont eux qui produisent la part la plus importante du dégagement de chaleur. Plus il y a ce type de transistors, plus le microprocesseur chauffe, et cette montée en température est aussi proportionnelle à la montée en fréquence. Le nombre de ce type de transistors dépend essentiellement du nombre d'opérations différentes qu'un microprocesseur peut effectuer, et à ce petit jeu, les processeurs graphiques peuvent faire beaucoup plus de choses que les microprocesseurs classiques.

Limitation de la taille du pipeline d'exécution
Le raisonnement qui suit est assez complexe, puisqu'il est le résultat de plusieurs raisonnements qui s'enchevêtrent, mais ça vaut le coup d'essayer de le comprendre. En premier, voici une explication sur l'expression 'pipeline d'exécution '. Cette expression correspond au fait que toute unité ou groupe d'unités de calculs est précédée de plusieurs unités d'exécution qui ont pour vocation de préparer les instructions et les données pour le calcul. J'ai inventé cette expression parce que généralement le terme de pipeline tout court dans un microprocesseur et un processeur graphique ne représente pas la même chose. Un microprocesseur contient un pipeline d'exécution, alors qu'un processeur graphique dispose d'une part de pipelines servant à assembler texel par texel les textures finales et d'autre part des pipelines d'exécution. On ne parle jamais de ces derniers, mais c'est un fait qu'il y en a car un processeur graphique reste un processeur de calcul aussi complexe soit-il. La seule véritable différence, c'est qu'un processeur graphique effectue des calculs spécialisés alors qu'un microprocesseur est conçu pour permettre tous types de calculs, ce qui fait qu'on le nomme parfois processeur généraliste.

Vous remarquerez que j'ai parlé de plusieurs pipelines d'exécution, ce qui suppose, en suivant la définition que j'en ai donné, qu'il existe plusieurs unités de calculs. Vous allez me dire qu'un microprocesseur aussi ! Oui, mais il y a une différence essentielle. Sur un microprocesseur, toutes les unités de calculs sont en parallèle, alors que sur un processeur graphique il en existe plusieurs en série. Autrement dit, les données passent nécessairement par plusieurs unités de calculs. Nous verrons que le fait qu'il y a des unités de calculs en série est une donnée clef pour comprendre pourquoi un processeur graphique ne monte pas aussi haut en fréquence qu'un microprocesseur, mais avant il me faut vous expliquer la différence entre une unité d'exécution et de calculs.

Différence entre unité d'exécution et de calculs
La différence fondamentale entre une unité d'exécution et de calculs est qu'une unité d'exécution ne modifie pas les données qu'elle traite ! C'est l'unité de calculs qui a cette fonction. Elle peut modifier une information : schématiquement A = A+B, ou en produire une nouvelle C = A+B. De là découle quelque chose de plus important du point de vue ingénieurie à savoir que si les unités d'exécution sont décomposables en de plus petites unités et que cela sert pour augmenter la fréquence de fonctionnement, il n'en va pas du tout de même pour les unités de calculs. La raison est que bon nombre de calculs ne peuvent pas être décomposés sans ajouter des étapes intermédiaires de sauvegarde et récupération des résultats intermédiaires, qu'il faudra ensuite assembler d'une manière particulière qui est dans bon nombre de cas différente si le calcul est exécuter d'un bloc. C'est un problème qui n'a pas encore trouvé de solution, sauf celle de créer des unités de calculs (lorsque celles-ci sont de même type) destinées à des calculs simples et d'autres à des calculs complexes. Ainsi le Pentium 4 est composé de deux unités ALU destinées à des calculs rapides en 1 cycle généralement et cette partie est nommée 'rapid engine'.

Il existe une autre différence, mais plus spécifique au processeur graphique. Dans la mesure où il y a des unités de calculs en série, il est nécessaire d'associer à chaque sortie d'unité de calculs une mémoire cache, dans laquelle viendra puiser l'unité de calculs suivante. Si ce n'était pas le cas, il faudrait pouvoir faire des écritures et lectures en mémoire à chaque passage d'une unité de calculs, ce qui pourrait représenter un temps d'exécution considérable et vraisemblablement incompatible avec les impératifs de fonctionnement temps réel des jeux ou autrement dit pour permettre une vitesse d'affichage suffisante des images calculées. D'un point de vue pratique, les ingénieurs peuvent centraliser la mémoire cache d'un microprocesseur, alors qu'un processeur graphique doit au moins en avoir une partie disséminée entre les différentes unités d'exécution. Bref, une contrainte de plus pour la conception des processeurs graphiques d'autant plus que les mémoires cache de chaque unité ne peuvent pas être trop éloignées. On ne peut donc pas non plus les mettre où l'on veut.

Décomposition des unités d'exécution
Le principe de décomposer les unités d'exécution pour pouvoir monter plus haut en fréquence est à présent un vieux truc. Le principe réside dans le fait de faire en sorte que chaque unité d'exécution ne mette pas plus de 1 cycle pour exécuter son travail. Ce temps est déterminé par le nombre de transistors qui la composent, car ils agissent un peu comme des retardateurs de signaux. Plus un signal doit passer par un grand nombre de transistors, plus son temps de parcours dans l'unité d'exécution sera long. Si on souhaite doubler la fréquence d'un processeur, il faut en gros diviser par deux le nombre de transistors.

La décomposition des unités d'exécution entraine leur multiplication. Cela pose deux problèmes. Le premier, il faut savoir où les mettre. A priori ça parait simple, mais ça ne l'est pas s'il y en a beaucoup. Ainsi un Pentium 4 dont le pipeline d'exécution est composé d'une vingtaine d'unités d'exécution possède des unités d'exécution qui ne font rien. Leur rôle est de permettre l'acheminement des données d'une unité à une autre tellement l'organisation d'un grand nombre d'unités d'exécution est complexe. Une autre conséquence est l'augmentation de taille que le processeur subit en augmentant le nombre d'unités d'exécution.

Dans le cas des processeurs graphiques, si on devait décomposer chaque pipeline d'exécution en 15 unités, on aurait avec 3 pipelines d'exécution un processeur graphique composé de plus de 45 unités ! C'est du pure délire au niveau de l'organisation, d'autant plus si on ajoute les différentes contraintes déjà mentionnées plus haut. Bref cette technique de décomposition des unités d'exécution n'est pas le Graal qui anime les ingénieurs travaillant sur des microprocesseurs comme les Athlon ou Pentium. Evidemment la décomposition d'unités d'exécution est utilisée dans les processeurs graphiques mais dans des proportions bien moindres et les améliorations qui pourraient être faites à ce niveau n'apportent que des gains modestes. en montée en fréquence.

La contrainte fonctionnelle
Nous avons vu de nombreuses contraintes techniques liées aux particularités des processeurs graphiques, mais la première contrainte, la contrainte maîtresse n'est pas une contrainte d'ingénierie ou d'architecture, c'est la contrainte fonctionnelle. Les processeurs graphiques ne sont pas arrivés à maturité et rien n'indique s'ils y arriveront un jour et quand. Ainsi le maître mot pour les processeurs graphiques n'est pas optimisation de l'architecture, mais ajout de nouvelles fonctionnalités. Voici une liste non -exhaustive de fonctions qui ont été ajoutées aux processeurs graphiques ces dernières années : Compression des textures, z-buffer, stencil buffer, filtrage anisotropique, FSAA, Bump mapping, gestion de la géométrie (T&L et Vertex), implémentation de la programmabilité des processeurs graphiques par les shader (vertex et pixel). Et il ne s'agit là que des fonctions 3D, car les processeurs graphiques se sont vus aussi adjoindre des algorithmes de décompression de type Mpeg, et même l'intégration des RAMDAC. Bref les ingénieurs des processeurs graphiques se cassent avant tout la tête pour savoir quelles fonctionnalités devront être ajoutées et comment. Tout cela pose des problèmes très complexes à résoudre comme en témoigne le récent échec de NVidia avec son processeur NV30 sur lequel sont basées les cartes graphiques GeForce FX 5800.

Raisonnement final

• Les ingénieurs ont pour priorité d'ajouter de nouvelles fonctions ou d'aumgenter les possibilités de celles déjà existantes. Cela est du à l'importance de contraintes fonctionnelles puisqu'il existe encore de nombreuses opérations qu'un processeur graphique ne sait pas faire, et que vu la complexité intrinsèque des processeurs graphiques, l'optimisation d'architecture est un casse-tête qui consomme énormément de temps, temps qu'il est plus judicieux d'utiliser pour concevoir de nouvelles fonctions. Cela est d'autant plus vrai que, comme nous l'avons vu, l'optimisation d'architecture (pour la montée en fréquence) ne pourra jamais atteindre les sommets qu'atteignent les microprocesseurs comme l'Athlon ou le Pentium 4.
  
  

• Au final, l'ajout constant et primordial de transistors pour de nouvelles fonctions fait que la part des transistors dédiés à la logique est considérable, ensuite que l'architecture particulière des processeurs graphiques n'est pas conçue pour monter en fréquence.
  
  

• Au final, on a une architecture qui n'est pas conçue pour atteindre des fréquences équivalentes à celles des microprocesseurs, et même si cette architecture permettait de monter plus haut en fréquence (ce qui est en fait le cas dans des proportions que j'estime à x2), le nombre considérable de transistors, ainsi que la part importante dédiée aux transistors logiques fait que tant la consommation que le dégagement de chaleur sont des freins incontournables, sauf à utiliser des procédés de fabrication plus performants. Pour vous donner un ordre de grandeur, un Pentium 4 Northwood avec 512 Ko de mémoire cache L2 utilise au total 55 millions de transistors dont la moitié dédiée à la mémoire cache et un processeur graphique comme le R350 équipant les cartes graphiques 9800 Pro de 110 millions de transistors dont les 3/4 (estimation) sont dédiés aux transistors logiques. Dans tous les cas, la proportion de transistors logiques utilisés est environ 3 fois supérieure.

En résumé, on a d'abord la contrainte fonctionnelle, puis les contraintes d'architecture qui renforcent la contrainte fonctionnelle et au final un nombre impressionnant de transistors dédiés aux calculs logiques et pour conséquence des difficultés à monter en fréquence d'une part à cause des contraintes d'architecture, et d'autre part par le nombre de transistors dédiés à la logique générant un dégagement de chaleur très important.

Conclusion
Le seul domaine qui puisse apporter un véritable gain en termes de montée en fréquence est l'utilisation de procédés de fabrication plus fins. Diminution de la taille des interconnexions et surtout des transistors vu le nombre impressionnant qu'un processeur graphique intégre. Toutefois si le procédé de fabrication est l'élément clef de la montée en fréquence, il faut rappeler que celui-ci doit être bien maîtrisé pour fournir les résultats attendus. Ainsi NVidia qui a sauté sur la technologie 0,13 micron en 2002 s'en est mordue les doigts alors que ATI qui a fait preuve d'un certain conservatisme en continuant sur un procédé 0,15 micron mais bien maîtrisé continue à faire progresser son processeur R300 devenu le R350 puis bientôt le R360 (nom à confirmer). Ce qu'il est intéressant de noter dans les choix de ces deux constructeurs de processeurs graphiques, c'est que si le procédé de fabrication est primordial pour un premier processeur, ses évolutions doivent compter avant tout sur les optimisations du procédé de fabrication et sur les optimisations de l'architecture du processeur. D'ailleurs, les constructeurs ont eux-même anoncé qu'à l'avenir, la durée de vie d'une architecture sera d'au moins 24 contre 12 à 18 auparavant.

A quand les processeurs graphiques de 1 GHz ? Pas demain la veille. Le prochain grand rendez-vous pour NVidia et ATI est le procédé de fabrication 0,09 micron et il ne faudra pas compter dessus avant le deuxième semestre 2004. En tenant compte des ajouts de transistors qui seront faits pour intégrer de nouvelles fonctionnalités ou amaliorer d'anciennes, on peut penser que la fréquence de départ tournera autour de 600 MHz, et que les évolutions du procédé de même que des architectures permettront d'atteindre les 800 MHz voire les 900 MHz, mais pas le 1 GHz. Pour cela, il faudra attendre 2006 avec un procédé de fabrication en 0,065 micron.

Pour terminer, je souhaiterais attirer votre attention sur le fait que si on peut penser que les fréquences des processeurs graphique ont plus faiblement augmenté que celles des microprocesseurs, c'est un phénomène qui touche à sa fin. Deux raisons à cela, d'abord les processeurs graphiques intègrent un tel nombre de fonctionnalités aujourd'hui qu'il est raisonnable de penser que la contrainte fonctionnelle faiblisse au profit de la contrainte d'ingénierie et donc que les fabricants passent plus de temps à optimiser l'architecture de leur processeur. Ensuite et surtout, de plus en plus de fonctions, en particulier celles des vertex shader, ont des performances proportionnelles à la fréquence du processeur. Donc plus qu'avant, les processeurs graphiques, pour être performants, se doivent d'avoir une fréquence la plus élevée possible.

Les matrices, ces êtres étranges venus d'ailleurs, et que l'on rencontre les soirs de brume ... Bref nous allons voir dans ce mini-article l'utilité des matrices pour le développement des applications 3D. Ce long mini-article est en deux parties. Dans la première, je donnerais des informations de base sur les repères, les points et objets dans l'espace, les vecteurs, puis dans la seconde partie les différentes représentations mathématiques d'une action comme la rotation dans l'espace dont les matrices font partie, puis des matrices elles-mêmes et de quelques unes de leurs particularités.

Point et objet dans un espace à 3 dimensions :
Pour décrire un point dans l'espace 3D, il nous faut un repère 3D, c'est-à-dire 3 axes qu'on nomme généralement X,Y et Z, et une origine qui est le point d'intersection de ces trois axes et qu'on nomme O. Pour positionner un point P dans cet espace, il nous faut ses coordonnées x, y et z et on écrit P(x,y,z). Le point O a pour coordonnées O(x=0,y=0,z=0) ou O(0,0,0). Donc pour 'repérer' un point, on utilise un repère. Il existe plusieurs type de repère, mais celui dont nous parlerons est dit orthonormé, c'est a dire que les axes forment entre eux des angles de 90°.

Pour les objets, c'est un peu plus compliqué puisqu'il nous faut, en plus de ses coordonnées qui correspondent généralement au centre de l'objet, son orientation. Effectivement, si un personnage a une position P dans un espace, il a aussi une orientation : il est de face, de dos, de côté, ... Pour décrire cela, on utilise les vecteurs. Pour travailler avec les vecteurs il nous faut ajouter une base au repère. Une base est un ensemble de vecteur linéairement indépendant. En gros cela signifie qu'a partir de ces vecteurs de 'base' ont peut construire tout autre vecteurs. On ajoute au repère O,X,Y,Z une base, donc 3 vecteurs qu'on nomme généralement i,j,k.

Trois représentations mathématiques différentes d'une rotation dans l'espace :
Nous allons prendre un exemple concret d'une opération mathématique dans l'espace ou plus exactement d'une transformation. Il s'agit de la rotation selon l'axe Z. Il existe d'autres transformations, comme la translation, l'homotéthie, ... Toutefois, pour ne pas alourdir les explications de ce mini-article, je ne démontrerais pas les formules présentées ci-dessous, mais cela fait appel essentiellement à la trigonométrie. Une autre particularité est que je ne précise pas l'axe Z dans les équations qui suivent dans la mesure où Z ne joue aucun rôle direct, ce ne sera pas le cas dans la seconde partie de ce mini-article.

Rotation par un système d'équation :
Voici le système d'équation qui permet de faire une rotation autour de l'axe Z. z₁ = z représente le fait que la coordonnée z n'est pas modifiée et que c'est autour de cet axe que se fait la rotation. Si on faisait une rotation autour de Y, on aurait un autre système d'équation et Y = Y, même chose pour X.

Dans ce système x₁, y₁ sont les coordonnées du point P(x,y) après rotation.

Rotation par les matrices
Voici la matrice de rotation. Certains auront remarqué qu'on ne fait qu'exprimer les coefficients du système d'équation dans un tableau. C'est exact car avant tout une matrice est un tableau carré (même nombre de lignes et de colonnes) ou rectangulaire (nombre de lignes et de colonnes différent) dans lequel on met des valeurs numériques. Vous me direz que cos() n'est pas un nombre. En pratique, on réalise souvent les calculs intermédiaires en conservant les coefficients sous forme de fonction, mais comme une fonction : f(x) = y et que y est un nombre. Donc une matrice est bien constituée de nombres et au final il faudra les calculer.

Ce qu'il faut bien comprendre, c'est que les matrices ne sont qu'une représentation de quelque chose, ce peut être un système d'équation linéaire, d'application linéaire liée au calcul vectoriel, ... Les matrices ne sont qu'une notation, la représentation de quelque chose qui a un sens mathématique, mais c'est une notation qui simplifie considérablement l'approche qu'on peut avoir de certains problèmes qui peuvent devenir complexes. Ainsi le système d'équation vu plus haut, peut se résumer à :

il est évident que cette forme (Y = A.X) est extrêmement simple, mais il ne faut pas oublier que derrière cela il existe un arsenal mathématique conséquent que je déconseille à toute personne n'ayant pas un niveau bac+1 de se lancer dans l'apprentissage approfondi des matrices. Un dernier point sur les matrices. Si la notation matricielle n'est finalement qu'une notation, celle-ci n'est vraiment utile que quand on effectue des modifications sur des groupes de valeurs numériques, vectorielles, ... qui représentent des objets dans l'espace. On nomme ces modifications des transformations. La rotation, la translation, l'homotéthie ... sont des transformations. Autrement dit, la notation matricielle et les calculs qui peuvent lui être associés n'ont d'utilité que si on change de place un objet, la position du regard sur un objet, etc ...

Rotation par les nombres complexes :
Si vous avez fait une terminale scientifique ou équivalent, vous avez étudier les nombres complexes. Pour les autres, les nombres complexes sont en premier une réponse à la question : quelle est la solution à l'équation x² = -1. Les nombres complexes sont de la forme z = a + bi (i pour imaginaire). Même si c'est avant tout un artifice de calcul, les nombres complexes permettent souvent d'arriver à une solution concrète et il existe même une représentation géométrique des nombres complexes où 'a' représente l'axe des X et 'b' l'axe des Y. A partir de là, on peut utiliser le cercle trigonométrique, et définir une trigonométrie des complexes. Les formules vues précédemment étant issues de la trigonométrie classique et comme il existe des liens entre trigonométrie classique et complexe, on trouve donc une représentation par les nombres complexes de la rotation.

Nous ne parlerons plus des nombres complexes dans la suite de ce mini-article mais avant d'en avoir terminé avec eux, je souhaiterais vous donner une information complémentaire. Dans la seconde partie de cet article, nous allons voir que la forme la plus utile de représentation matricielle s'effectue dans un espace en 4 dimensions. Or nous avons vu que les complexes permettent de travailler dans un espace à deux dimensions. La question est : existe-t-il une formulation des nombres complexes pour une dimension 4, comme les complexes le sont pour une dimension 2 ? La réponse est oui et se nomme les quaternions. Conçus par le mathématicien Hamilton, ils se représentent sous la forme z = a + bi + cj + dk. De plus, les quaternions, s'ils n'ont pas pour vocation de remplacer la représentation matricielle, jouent un rôle de plus en plus important en infographie 3D, dans la mesure où leurs propriétés particulières permettent d'effectuer des combinaisons de transformation (rotations) qui nécessitent moins d'opérations mathématiques que la représentation matricielle.

Nous allons voir dans la suite comment les matrices peuvent être utilisées pour effectuer les différentes opérations mathématiques, et quelles sont les plus importantes.

Pour la seconde partie de ce mini-article, nous allons voir à quoi ressemblent les différentes matrices utilisées en développement 3D et dans quelles situations elles le sont. Mais avant tout cela, il me faut vous parler des coordonnées homogènes.

Représentation en coordonnées homogènes : Introduction
Les coordonnées homogènes sont issues du domaine des mathématiques nommé géométrie projective qui est aujourd'hui une partie de l'important domaine mathématique nommé algèbre linéaire. D'un point de vue pratique, les coordonnées homogènes impliquent d'ajouter une dimension. Ainsi dans un espace 2D, la matrice d'une transformation est composée de deux lignes et deux colonnes, ou matrice 2x2. En coordonnées homogènes, les matrices de transformation dans un espace 2D, seront de type 3x3 (trois lignes, trois colonnes). Dans un espace 3D, les matrices de transformation sont de type 3x3 et en coordonnées homogènes en format 4x4, puisqu'on ajoute une dimension. Bref les développeurs 3D travaillent dans la quatrième dimension ;).

Représentation en coordonnées homogènes : Pourquoi ?
Je vais répondre ici à deux questions essentielles. La première est pouquoi a-t-on besoin des coordonnées homogènes pour faire des transformations ? Toutes les transformations matricielles comme les rotations, l'homothétie, la symétrie, ... sont des transformations linéaires et respectent ce qu'on nomme les axiomes de linéarité. D'où leur nom de transformation linéaire. Toutes ? Toutes, sauf une ! La translation. Or on nepeut envisager de faire des transformations sans avoir besoin à un moment ou à un autre de la translation. L'utilisation des coordonnées homogènes permet une représentation de la translation qui est 'compatible' avec les autres transformations, c'est-à-dire qu'on rend homogènes toutes les transformations dans leur mode de fonctionnement.

Vu sous un autre angle, il faut savoir que les transformations linéaires, doivent se conformer aux axiomes de linéarité, si elles ne le faisaient, le résultat d'une transformation pourrait tout simplement être indéterminé. En particulier, la composition de transformation linéaire, c'est-à-dire le fait d'associer plusieurs transformations doit produire une transformation linéaire. Ainsi si l'on fait la transformation A.B = C, C est une transformation linéaire qui pourra être utilisée par la suite pour faire d'autres combinaisons telles que C.D = E. D'un point de vue mathématique, le fait que A,B C D soient des transformations linéaires assure qu'il en sera de même pour E. La translation en tant que transformation n'est pas linéaire et donc associée a des transformations linéaires n'assure pas que le résultat sera une transformation linéaire. C'est par l'utilisation des coordonnées homogènes qu'on donne à la translation les propriétés de transformation linéaire.

La deuxième question est : pourquoi le fait d'ajouter une dimension supplémentaire rend-il la translation homogène avec les autres transformations et donc en fait une transformation linéaire ? Je ne vous cacherais pas que la réponse précise à dépasse largement le niveau de cet article, mais ce que je peux vous dire c'est qu'il existe dans l'arsenal mathématique de l'algèbre linéaire des outils qui montrent qu'il est possible de donner les propriétés de linéarité à une transformation, si on l'exprime dans un espace de dimension N+1 (au lieu de N).

Matrices de transformation linéaire
Voici les matrices de transformation linéaire les plus couramment utilisées pour des opérations dans un espace 3D, et leur représentation utilise les coordonnées homogènes c'est-à-dire qu'on travaille avec des matrices 4x4.

Multiplication matricielle et composition de transformation
Quand on découvre la multiplication matricielle, ça a l'air un peu compliqué mais en fait il s'agit d'une règle de composition qu'on répète à chaque ligne et chaque colonne. Une fois cette règle maîtrisée, la multiplication matricielle ne nécessite qu'une seule chose, de l'attention. Mais bon comme c'est l'ordinateur qui s'en charge, vous ne risquez pas grand chose, mais savoir le faire manuellement vous évitera d'avoir l'air bête si un jour vous en avez besoin ;). Le principe de la multiplication matricielle est de multiplier chaque élément d'une ligne d'une matrice A, à chaque élément d'une colonne d'une matrice B et d'additionner ces résultats pour produire le résultat d'un coefficient de la matrice C. Voici un graphique qui résume cela :

En ce qui concerne la composition de transformation, le problème est le suivant. Soit Y = A.X, et Y' = B.Y alors Y' = B.(A.X) = (B.A).X. Prenons un exemple. Si l'on souhaite faire une rotation, puis une translation à un objet, on ne va pas calculer les coordonnées (Y) résultat de la rotation puis calculer Y' à partir de Y. On va d'abord combiner les matrices de rotation et de translation tel C = A.B, puis on fera directement le calcul Y' = C.X. Attention la multiplicaiton matricielle n'est pas commutative !, c'est à dire que B.A n'est pas égale à A.B, donc respectez toujours l'ordre d'exécution des opérations.

On trouve dans la composition de transformation, la principale réponse à la question que pose ce long mini-article à savoir, que les matrices sont un outil facile à utiliser et parfaitement adapté pour effectuer des combinaisons de transformation.

Comment utiliser les matrices ?
Deux voies sont possibles. La première consiste à utiliser les fonctions que l'API met à votre disposition. Dans le cas d'OpenGL, vous disposez de fonctions comme glTranslate(), glrotate(), glScale(). Vous disposez aussi du contrôle de la perspective qui contrôle essentiellement le champ de vision ou FOV en anglais pour Field Of View. Il existe aussi des fonctions de calcul matriciel pour les textures qui permettent de contrôler l'orientation, la position et l'échelle.

En fonction de la carte, l'API va utiliser ou non les instructions mathématiques du processeur graphique ou du processeur principal.

Vous pouvez aussi faire vos propres calculs matriciels, cela peut être utile quand on souhaite un contrôle plus important (plus précis) sur les transformations ou pour des effets spéciaux sur les textures que ne pourraient pas gérer les fonctions de l'API. Vous trouvez dans le lien ci-dessous, entre autre, des exemples de programmation directe du processeur graphique pour des opérations mathématiques.

Voilà j'espère que cette petite introduction aux calculs matriciels en infographie 3D aura éclairci votre lanterne et peut-être même éveillé votre intérêt pour vous lancer dans la programmation d'applications 3D. Une remarque toutefois, les américains utilisent de préférence les repères indirects, donc ne soyez pas étonné que les API et les articles anglais sur le sujet présentent les choses sous un autre angle (ah, sacrés américains).

Bien entendu, il ne s'agit que d'un survol d'un domaine en évolution constante et rapide, mais si vous voulez être bon vous devrez passer par l'algèbre linéaire, et un niveau de premier cycle universitaire en mathématique est un minimum. Je souhaite remercier Tanguy Fautré et Patrice Arrighi pour leur relecture. Ce dernier devrait d'ailleurs vous proposer d'ici peu un mini-article sur l'utilisation des quaternions en développement 3D :).