# Les cartes graphiques/Le pipeline géométrique d'avant DirectX 10

Une partie importante du pipeline graphique est dédiée au traitement de la géométrie. Le pipeline graphique a beaucoup changé dans le temps et est devenu de plus en plus programmable. De circuits fixes de T&L, il a intégré des vertex shaders, puis d'autres formes de shaders : geometry shaders, hull shaders, domain shaders, primitive shaders, mesh shaders et bien d'autres.L'évolution s'est faite en trois grandes périodes de temps, éventuellement quatre, qu'on peut distinguer très nettement.
La toute première période est celle où les circuits géométriques n'étaient pas programmables du tout. C’était l'époque ancienne des circuits de T&L, introduit sur la première carte graphique Geforce de NVIDIA, la Geforce 256. Le pipeline géométrique se résumait alors aux quatre étapes suivantes :
* L'étape de chargement des sommets/triangles, qui sont lus depuis la mémoire vidéo et injectés dans le pipeline graphique.
* L'étape de transformation effectue deux changements de coordonnées pour chaque sommet. Premièrement, elle place les objets au bon endroit dans la scène 3D, ce qui demande de mettre à jour les coordonnées de chaque sommet de chaque modèle. C'est la première étape de calcul : l'étape de transformation des modèles 3D. Ensuite, elle effectue un changement de coordonnées pour centrer l'univers sur la caméra, dans la direction du regard. C'est l'étape de transformation de la caméra.
* La phase d'éclairage (en anglais lighting) attribue une couleur à chaque sommet, qui définit son niveau de luminosité : est-ce que le sommet est fortement éclairé ou est-il dans l'ombre ?
* La phase d'assemblage des primitives regroupe les sommets en triangles.
Les deux étapes du milieu étaient le fait d'un circuit de T&L unique. Il n'était pas un circuit programmable, mais un circuit fixe. Dans les tableaux qui vont suivre, les circuits non-programmables sont indiqués en rouge. Il était accompagné de deux circuits fixes pour les deux étapes restantes. L''input assembler charge les vertices depuis la mémoire vidéo, l'assembleur de primitive regroupe les sommets en triangles avant la rastérisation.
Avant l'arrivée des shaders :
| Input assembly | Transform & Lighting | Primitive assembly |
La première période a été très courtes : à peine deux générations de cartes graphiques. Rapidement, dès la Geforce 3, les unités géométriques sont devenues programmables, avec l'introduction des vertex shaders. Les vertex shaders s'occupaient des phases de transformation et d'éclairage, qui étaient devenues programmables. Les processeurs de shaders étaient toujours accompagnés de l''input assembler charge les vertices depuis la mémoire vidéo, l'assembleur de primitive regroupe les sommets en triangles avant la rastérisation. S'en est suivi une longue période où le traitement de la géométrie se résumait aux vertex shaders. Durant cette période, le pipeline graphique ne manipulait que des sommets, les triangles n'existaient qu'en sortie du pipeline géométrique.
Après la Geforce 3, avant DirectX 10 :
| Input assembly | Vertex shader | Primitive assembly |
L'introduction des techniques de tesselation, qui agissent directement sur des primitives, a changé la donne. Nous détaillerons ces techniques de tesselation dans le prochain chapitre. Mais leur introduction ne s'est pas faite sans heurts. Initialement, les concepteurs de cartes graphiques ont tenté d'ajouter des nouveaux shaders pour gérer la tesselation. Sont d'abord apparus les geometry shaders, puis le hull/domain shaders. Il s'agit là de la troisième période, qui visait à améliorer le pipeline graphique précédent. Mais le résultat était assez désastreux. Les programmeurs avaient beaucoup de mal à utiliser la tesselation ou les nouveaux shaders, ce qui fait que ces technologies ont été peu utilisées.
DirectX 10 :
| Input assembly | Vertex shader | Geometry shader | Geometry shader | Geometry shader | Geometry shader | Primitive assembly |
| DirectX 11 |||||||
| Input assembly | Vertex shader | Hull shader | Tesselation | Domain shader | Geometry shader | Primitive assembly |
Depuis les années 2018-2020, le pipeline géométrique a fortement évolué et a été revu de fond en comble. L'arrivée des primitive shaders d'AMD et des mesh shaders de NVIDIA a modifié en profondeur le pipeline géométrique. Il est devenu plus simple, mais paradoxalement plus puissant et plus flexible. De nombreuses étapes ont disparues ou sont devenus programmables. A vrai dire, les étapes d'assemblage de primitives et d'input assembly ont disparues.
Dans ce chapitre, nous allons voir l'ancien pipeline géométrique, celui de la première et de la seconde période.

## L'input assembler

L'input assembler charge les informations géométriques, présentes dans en mémoire vidéo, dans les unités de traitement des sommets. C'est une unité d'accès mémoire un peu particulière, mais qui contient des circuits assez classiques pour ce genre de circuits : des circuits de calcul d'adresse, des circuits pour commander la mémoire VRAM, un contrôleur mémoire, diverses mémoires tampons, etc. Pour faire son travail, il a besoin d'informations mémorisées dans des registres, à savoir l'adresse des données géométriques en mémoire, leur taille et éventuellement du type des données qu'on lui envoie (sommets codées sur 32 bits, 64, 128, etc).
Avant leur traitement, les objets géométriques présents dans la scène 3D sont mémorisés dans la mémoire vidéo, sous une forme plus ou moins structurée. Rappelons que les objets 3D sont représentés comme un assemblage de triangles collés les uns aux autres, l'ensemble formant un maillage. La position d'un triangle est déterminée par la position de chacun de ses sommets. Avec trois coordonnées x, y et z pour un sommet, un triangle demande donc 9 cordonnées. De plus, il faut ajouter des informations sur la manière dont les sommets sont reliés entre eux, quel sommet est relié à quel autre, comment les arêtes sont connectées, etc. Toutes ces informations sont stockées dans un tableau en mémoire vidéo : le tampon de sommets.
Le contenu du tampon de sommet dépend de la représentation utilisée. Il y a plusieurs manières de structure les informations dans le tampon de sommet, qui ont des avantages et inconvénients divers. Toutes ces représentations cherchent à résoudre un problème bien précis : comment indiquer comment les sommets doivent être reliés entre triangles. Le point crucial est qu'un sommet est très souvent partagé par plusieurs triangles. Par exemple, prenez le cube de l'image ci-contre. Le sommet rouge du cube appartient aux 3 faces grise, jaune et bleue, et sera présent en trois exemplaires dans le tampon de sommets : un pour la face bleue, un pour la jaune, et un pour la grise. Pour éviter ce gâchis, les concepteurs d'API et de cartes graphiques ont inventé des représentations pour les maillages, qui visent à limiter la consommation de mémoire ou faciliter la traversée du tampon de sommet.

### Les techniques anciennes : Triangle strip et Triangle fan

Pour gérer le partage des sommets entre triangles, la représentation la plus simple est appelée le maillage sommet-sommet (Vertex-Vertex Meshes). L'idée est que chaque sommet précise, en plus de ses trois coordonnées, quels sont les autres sommets auxquels il est relié. Les sommets sont regroupés dans un tableau, et les autres sommets sont identifiés par leur position dans le tableau, leur indice. Les informations sur les triangles sont implicites et doivent être reconstruites à partir des informations présentes dans le tampon de sommets. Autant dire que niveau praticité et utilisation de la puissance de calcul, cette technique est peu efficace. Par contre, le tampon de sommet a l'avantage, avec cette technique, d'utiliser peu de mémoire. Les informations sur les arêtes et triangles étant implicites, elles ne sont pas mémorisées, ce qui économise de la place.
Dans la représentation précédente, les arêtes sont présentes plus ou moins directement dans le tampon de sommets. Mais il existe des méthodes pour que les informations sur les arêtes soient codées de manière implicite. L'idée est que deux sommets consécutifs dans le tampon de sommet soient reliés par une arête. Ainsi, les informations sur les arêtes n'ont plus à être codées dans le tampon de sommet, mais sont implicitement contenues dans l'ordre des sommets. Ces représentations sont appelées des Corner-tables. Dans le domaine du rendu 3D, deux techniques de ce genre ont été utilisées : la technique du triangle fans et celle des triangle strips.
La technique des triangles strip permet d'optimiser le rendu de triangles placés en série, qui ont une arête et deux sommets en commun. L'optimisation consiste à ne stocker complètement que le premier triangle le plus à gauche, les autres triangles étant codés avec un seul sommet. Ce sommet est combiné avec les deux derniers sommets chargés par l'input assembler pour former un triangle. Pour gérer ces triangles strips, l'input assembler doit mémoriser dans un registre les deux derniers sommets utilisées. En mémoire, le gain est énorme : au lieu de trois sommets pour chaque triangle, on se retrouve avec un sommet pour chaque triangle, sauf le premier de la surface.
La technique des triangles fan fonctionne comme pour le triangle strip, sauf que le sommet n'est pas combiné avec les deux sommets précédents. Supposons que je crée un premier triangle avec les sommets v1, v2, v3. Avec la technique des triangles strips, les deux sommets réutilisés auraient été les sommets v2 et v3. Avec les triangles fans, les sommets réutilisés sont les sommets v1 et v3. Les triangles fans sont utiles pour créer des figures comme des cercles, des halos de lumière, etc.

### Le tampon d'indices

Enfin, nous arrivons à la dernière technique, qui permet de limiter l'empreinte mémoire tout en facilitant la manipulation de la géométrie. Cette technique est appelée la représentation face-sommet. Elle consiste à stocker les informations sur les triangles et sur les sommets séparément. Le tampon de sommet contient juste les coordonnées des sommets, mais ne dit rien sur la manière dont ils sont reliés. Les informations sur les triangles sont quant à elles mémorisées dans un tableau séparé appelé le tampon d'indices. Ce dernier n'est rien de plus qu'une liste de triangles.
Dit comme cela, on ne voit pas vraiment où se trouve le gain en mémoire. On se retrouve avec deux tableaux : un pour les indices, un pour les vertices. Mais l'astuce tient au codage des données dans le tampon d'indices. Dans le tampon d'indices, un sommet n'est pas codé par ses trois coordonnées. Les sommets étant partagés entre plusieurs triangles, il y aurait beaucoup de redondance avec cette méthode. Pour un sommet partagé entre N triangles, on aurait N copies du sommet, une par triangle. Pour éviter cela, chaque sommet est codé par un indice, un numéro qui indique la position du sommet dans le tampon de sommet. Avec la technique du tampon d'indice, les coordonnées sont codées en un seul exemplaire, mais le tampon d'indice contiendra N exemplaires de l'indice. L'astuce est qu'un indice prend moins de place qu'un sommet : entre un indice et trois coordonnées, le choix est vite fait. Et entre 7 exemplaires d'un sommet, et 7 exemplaires d'un indice et un sommet associé, le gain en mémoire est du côté de la solution à base d'index.
    On pourrait remplacer les indices par des pointeurs, ce qui donnerait un cas particulier d'une structure de données connue sous le nom de vecteur de Liffe. Mais ce n'est pas très pratique et n'est pas utilisé dans le domaine du rendu 3D.
Avec un tampon d'indices, un sommet peut être chargé plusieurs fois depuis la mémoire vidéo. Pour exploiter cette propriété, les cartes graphiques intercalent une mémoire cache pour mémoriser les sommets déjà chargés : le cache de sommets. Chaque sommet est stocké dans ce cache avec son indice en guise de Tag. Pour profiter le plus possible de ce cache, les concepteurs de jeux vidéo peuvent changer l'ordre des sommets en mémoire. Sur les cartes graphiques assez anciennes, ce cache est souvent très petit, à peine 30 à 50 sommets. Et c'était de plus un cache très simple, allant d'une simple mémoire FIFO à des caches basiques (pas de politique de remplacement complexe, caches directement adressé, ...). Notons que ce cache a cependant été fortement modifié depuis que les unités de vertex shader ont été fusionnées avec les unités de pixel shaders. Un tel cache se mariait bien avec des unités géométriques séparées des circuits de gestion des pixels, en raison de sa spécialisation.

## L'étape de T&L et les vertex shaders

L'étape de transformation-projection regroupe plusieurs manipulations différentes, mais qui ont pour point commun de demander des changements de repères. Par changement de repères, on veut dire que l'on passe d'un système de coordonnées à un autre. En tout, il existe trois changements de repères distincts qui sont regroupés dans l'étape de transformation : un premier qui place chaque objet 3D dans la scène 3D, un autre qui centre la scène 3D du point de vue de la caméra, et un autre qui corrige la perspective.
Un changement de coordonnée s'effectue assez simplement en multipliant le vecteur (X, Y, Z) des coordonnées d'un sommet par une matrice adéquate. Il existe des matrices pour la translation, la mise à l'échelle, d'autres pour la rotation, une autre pour la transformation de la caméra, une autre pour l'étape de projection, etc. Un petit problème est que les matrices qui le permettent sont des matrices avec 4 lignes et 4 colonnes, et que la multiplication demande que le nombre de coordonnées du vecteur soit égal au nombre de colonnes. Pour résoudre ce petit problème, on ajoute une 4éme coordonnée aux sommets, la coordonnée homogène, qui ne sert à rien, et est souvent mise à 1, par défaut. Mais oublions de détail.
L'étape de transformation est souvent fusionnée avec l'étape d'éclairage par sommet, les deux demandant de faire des calculs assez similaires. Sur PC, la geforce 256 a été la première à intégrer une unité non-programmable pour gérer transformation et éclairage, appelée unité de T&L (Transform & Lighting). L'unité de T&L incorporait un ou plusieurs circuits de multiplication de matrices spécialisés pour l'étape de transformation. Ils sont composés d'un gros paquet de multiplieurs et d'additionneurs flottants. Elles prennent en entrée les données provenant de l'input assembler, ainsi que les matrices nécessaires, et fournissent en sortie les coordonnées des sommets transformés.
L'unité de T&L est devenue programmable dès la Geforce 3, première carte graphique à supporter les vertex shaders. Il y a peu de généralités spécifiques pour les processeurs de vertex shaders, tout a déjà été dit dans le chapitre sur les processeurs de shaders. Tout au plus peut on dire que les cartes graphiques avaient autrefois des processeurs spécialisés dans l’exécution des vertex shaders, distincts des processeurs pour les pixel shaders. Mais cette époque est révolue avec les cartes graphiques actuelles. Par contre, on peut étudier un exemple de processeur de vertex shader d’antan.

## L'assemblage de primitives

En sortie de l'étage précédent, on n'a que des sommets éclairés et colorisés, pas des triangles. Et les sommets ne sont pas dans l'ordre : deux sommets qui en sortent à la suite ne sont pas forcément dans le même triangle. Pour recréer des triangles, on doit lire les sommets dans l'ordre adéquat, par paquets de trois pour obtenir des triangles. C'est le rôle de l'étape d'assemblage de primitives (primitive assembly), qui regroupe les sommets appartenant au même triangle, à la même primitive. L'assemblage des primitives est réalisée par un circuit fixe, non-programmable, qui utilise le tampon d'indice pour regrouper les sommets en primitives.
L'étape d'assemblage de primitives est suivie par un tampon de primitives, dans lequel les triangles sont accumulés avant d'entrer dans le rastériseur. Le contenu du tampon de primitive varie suivant la carte graphique, mais il y a deux possibilités principales. La première est simplement un paquet de sommets avec un petit tampon d'indices associé. L'autre est simplement un paquet de sommets, avec des sommets dupliqués s'ils sont partagés par plusieurs triangles. La première solution fait un meilleur usage de la mémoire du tampon de primitive, l'autre est plus simple et plus rapide, plus simple d'utilisation pour le rastériseur.