Les cartes graphiques/Le pipeline géométrique : évolution

Le pipeline graphique a beaucoup changé dans le temps et est devenu de plus en plus programmable. Et cela s'est beaucoup ressentit dans la partie du pipeline graphique dédiée au traitement de la géométrie. De circuits fixes de T&L, il a intégré des vertex shaders, puis des geometry shaders, hull shaders, domain shaders, primitive shaders, mesh shaders et bien d'autres. Dans ce chapitre, nous allons décrire l'évolution de ce pipeline et décrire comment elle s'est déroulée.

L'évolution du pipeline géométrique s'est faite en plusieurs grandes périodes, qu'on peut distinguer très nettement. Et pour distinguer ces périodes, nous devons faire quelques rappels sur comment est calculée la géométrie d'une scène 3D. Pour rappel, le pipeline géométrique regroupe les étapes suivantes :

• L'étape de transformation effectue des 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 dit si le sommet est fortement éclairé ou dans l'ombre.
• La phase d'assemblage des primitives regroupe les sommets en triangles.

Chaque étape peut être prise en charge par un processeur de shader, ou par un circuit fixe spécialisé. Les étapes peuvent être regroupées. L'évolution dans le temps se traduit par des changements sur ce qui était programmables et ne l'était pas. Ceci étant dit, voyons comment ces 4 étapes ont variées dans le temps.

Dans ce chapitre, nous allons voir l'ancien pipeline géométrique. Il ne traitait que des sommets, les triangles n'existaient qu'une fois l'assemblage de primitive effectué. Le pipeline géométrique après Direct X 10 fonctionne sur un principe totalement différent, mais ce sera le sujet du prochain chapitre.

La période des mainframes et workstations : les années 70-90

La toute première période est celle des années 70 à 90, où le rendu 3D n'était possible que sur des ordinateurs très puissants, comme des mainframes et stations de travail. L'informatique grand public n'existait pas encore, et le rendu 3D était utilisé pour des simulateurs de vol pour l'armée, de l'imagerie médicale, des applications industrielles, l'architecture, etc. Les jeux vidéos n'existaient pas vraiment, sauf sur consoles et il n'y avait que du rendu 2D sur celles-ci.

Les cartes graphiques étaient alors faites sur mesure pour un ordinateur bien précis, qui n'était vendu qu'à moins d'une centaine d'exemplaires. Les API graphiques n'existaient pas encore, ce qui fait que chaque modèle d'ordinateur faisait un peu à sa sauce. Les cartes graphiques étant réalisées presque sur mesure, il y avait une grand diversité d'implémentations, toutes différentes. Et n'oublions pas que tout était à concevoir, le rendu 3D n'en était qu'à ses débuts. Les toutes premières ne géraient pas le placage de textures, les fonctionnalités étaient limitées, la rastérisation utilisait des polygones, etc.

Les processeurs à virgule flottante pour la géométrie

Durant cette époque, le traitement de la géométrie était réalisé avec des processeurs à virgule flottante. Le chargement des sommets/triangles était le fait du processeur de commandes, le reste était le fait d'un ou de plusieurs processeurs.

Il faut noter que les shaders n'existaient pas encore. Les processeurs étaient programmés avec un "microcode", qui est un terme trompeur pour ceux qui ont déjà lu des cours d'architecture des ordinateurs. En réalité, il s'agissait plus d'un firmware. Les processeurs étaient connectés à une mémoire ROM, qui contenait un programme à exécuter. Le programme faisait tous les calculs nécessaires pour rendre un triangle/polygone.

Parmi les processeurs utilisés dans cette période, on trouve le geometry engine de SGI, l'Intel i860, des processeurs Weitek, etc. Les processeurs en question avaient souvent des fonctionnalités utiles pour le rendu 3D. Au minimum, ils géraient quelques instructions utiles pour le rendu 3D, comme des opérations MAD (Multiply And Accumulate), des opérations trigonométriques, une opération pour calculer 1/x, des opérations transcendantales, etc.

Le processeur Intel i860 était un processeur un peu particulier dans cette liste. Il gérait à la fois des calculs sur des entiers et à virgule flottante. Il disposait de deux modes : un mode normal où il fonctionnait comme un processeur classique, et un mode "VLIW" où il exécutait en même temps une opération flottante et une opération entière. Les instructions n'étaient pas encodées de la même manière dans les deux modes.

Le geometry engine de SGI

Le geometry engine de SGI était lui bien différent des autres processeurs. Il était conçu sur mesure pour les calculs géométriques. Le processeur était un processeur de type SIMD, c’est-à-dire qu'il faisait plusieurs opérations identiques, sur des opérandes différents. Il pouvait donc faire 4 additions/soustraction en même temps, chacune étant réalisée dans une unité de calcul séparée. Pour cela, il contenait 4 unités séparées, contenant chacune :

• une unité de calcul capable de réaliser les 4 opérations ;
• un registre flottant de 29 bits : un bit de signe, un exposant de 8 bits et une mantisse de 20 bits ;
• une pile d'opérande de 8 niveaux, dont on reparlera dans la suite.

L'unité de calcul gère naturellement les additions et soustraction. Elle dispose aussi d'un support limité des multiplications et divisions. Ces deux opérations sont réalisées en enchainant des additions/soustractions, avec l'aide du microcode. Pour simplifier l'implémentation, chaque unité de calcul contient trois registres entiers pour simplifier l'implémentation des multiplications et divisions. Ils sont appelés l'accumulateur, le shift up et le shift down. Voyons à quoi ils servent.

Pour rappel, une multiplication multiplie un multiplicande par un multiplieur. Le registre accumulateur mémorise les résultats intermédiaires de la multiplication/division, les fameux produits partiels. Les deux autres registres mémorisent le multiplieur ou le diviseur. Ils étaient décalés d'un rang par cycle d'horloge, ce qui facilitait l'implémentation des multiplications et divisions. Le registre shift up était décalé d'un rang vers la gauche, le registre shift down l'était d'un rang vers la droite.

Les registres flottants sont en réalité chacun composés de deux registres séparés : un pour l'exposant, un autre pour les mantisses. Et l'unité de calcul était elle aussi découpée en deux : une portion gérait les exposants, l'autre les calculs sur les mantisses. Entre les deux, se trouvait toute la logique de contrôle du processeur, avec le décodeur, le program counter, le microcode, etc.

Exemple d'une pile/file d'opérandes, chaque opérande étant codée sur 4 Bytes.

La pile d'opérande est une petite mémoire qui mémorise plusieurs opérandes. Les opérandes sont organisés en pile (LIFO), à savoir que les opérandes sont ajoutés les unes après l'autre dans cette pile, et que la mémoire mémorise leur ordre d'ajout. De plus, on ne peut accéder qu'à l'opérande la plus récemment ajouté. Il est possible de faire une analogie avec une pile d'assiette : les opérandes sont empilés comme des assiettes, seul l'opérande au sommet de cette pile est accessible.

Le processeur gère plusieurs opérations. Premièrement, il peut ajouter un opérande au sommet de la pile, ou au contraire la retirer. Il s'agit des opérations PUSH et POP. Le processeur peut aussi faire une opération entre l’opérande dans les registres, et celle au sommet de la pile. L'opération retire l'opérande de la pile, et la remplace par le résultat de l’opération.

La pile d'opérande permet de mémoriser une pile de matrice directement dans les 4 geometry engine. Une matrice 4 par 4 est éclatée sur les différents geometry engine : ses 4 lignes sont réparties sur 4 processeurs, les 4 nombres par ligne sont dans les registres pour la pile. Il était initialement prévu de mettre cette pile de matrice en dehors du geometry engine, dans une mémoire séparée. Mais

Le pipeline géométrique était implémenté en utilisant 10/12 processeurs de ce type, enchainés l'un à la suite de l'autre. Les 4 premiers faisaient une multiplication par une matrice 4*4, les 6 suivants faisaient les opérations de clipping/culling, les deux derniers faisaient la rastérisation proprement dite.

Les quatre premiers processeurs prenaient en charge la multiplication d'un sommet par une matrice de 4 par 4. La matrice était découpée en 4 lignes ou colonnes, chacune étant mémorisée dans un processeur : 4 processeurs pour 4 lignes/colonnes, 4 nombres par ligne pour 4 registres flottants par processeur. La mise à jour de la matrice se faisait avec l'aide du processeur de commande. Il était responsable de la mise à jour simultanée des registres de tous les processeurs. Il disposait pour cela de plusieurs commandes, qui étaient toutes à destination des 4 premiers processeurs, sauf la dernière :

• LoadMM pour charger une matrice dans les 16 registres des 4 processeurs géométriques ;
• StoreMM pour sauvegarder cette matrice dans la RAM ;
• MultMM pour multiplier la matrice avec une matrice au sommet de la pile ;
• PushMM pour sauvegarder la matrice dans la pile ;
• PopMM pour charger la matrice de la pile vers les 4 processeurs géométriques ;
• LoadVP pour configurer les registres de viewport pour le clipping et la rastérisation.

La multiplication demande de faire des additions et des multiplications. Le processeur avait bien une instruction de multiplication, mais celle-ci était réalisée en enchainant des additions et décalages à l'intérieur du processeur (l'instruction était microcodée).

Il y avait le même problème pour les deux processeurs dédiés à la rastérisation. L'un était en charge de la coordonnée de profondeur, l'autre des coordonnées x et y à l'écran. Et les deux avaient besoin de faire des divisions, pour des histoires de correction de perspective détaillées dans un prochain chapitre sur la rastérisation. Les divisions étaient microcodées elles aussi, à savoir que le processeur les émulait avec des soustractions successives en interne.

Les processeurs pour le clipping prenaient en charge le frustrum clipping, à savoir qu'ils éliminaient ce qui était en-dehors du champ de vision. Pour rappel, le champ de vision est délimité par 6 plans : gauche, droite, haut, bas, near plane, far plane. Il y avait 6 processeurs pour 6 plans : chaque processeur clippait les triangles pour un plan bien précis. Il était possible de se passer du clipping pour le near et le far plane, ce qui réduisait le nombre de processeur à 5 ou 4.

Le fait de clipper un plan à la fois peut paraitre étonnant, mais ce choix est justifié dans le document "Structuring a VLSI architecture", qui décrit le geometry engine en détail. La conception du chip s'est inspiré du circuit Clipping Divider, utilisé dans le Line Drawing System-1 de l'entreprise Evans & Sutherland. Le circuit en question ne faisait que du clipping et rien d'autre. Il faisait les calculs de clipping pour 4 plans en même temps et combinait les 4 résultats. Mais une implémentation similaire avec un circuit intégré aurait posé des problèmes de câblage, les interconnexions auraient pris trop de place. Une implémentation série/pipeline, qui clippe un plan à la fois, n'avait pas de problème. Elle permettait aussi de gérer à la fois des polygones et des lignes, si programmée correctement.

Une description complète du Geometry Engine et de la carte géométrique des IRIS est disponible ici : The Geometry Engine : A VLSI Geometry System for Graphics.

La station de travail Appollo DN 10000 VS

Les processeur de l'époque incorporaient diverses optimisations pour accélérer les calculs géométriques. Par exemple, la station de travail Appollo DN 10000 VS faisait les calculs géométriques et de clipping sur le processeur, pas sur la carte graphique. C'était un choix pas très courant pour l'époque, il n'est pas représentatif. La station de travail incorporait 4 processeurs principaux et une carte graphique qui s'occupait uniquement de la rastérisation et des textures. Les calculs géométriques étaient distribués sur les 4 processeurs, s'ils étaient libres. Toute la difficulté tenait à éviter que les 4 processeurs se marchent dessus. Il fallait synchroniser les processeur et la carte graphique ensemble.

Une première synchronisation tient dans l'entrée des triangles dans les processeurs. Les processeurs traitent chaque triangle un par un. L'ordinateur a, dans sa RAM, un pointeur vers le prochain triangle. Les processeurs peuvent lire ce pointeur pour charger le prochain triangle à traiter, et l'incrémentent pour passer au triangle suivant. Mais il ne doit être modifié que par un seul processeur à la fois. Les programmes exécutés sur les 4 processeurs utilisent des mécanismes de synchronisation (des mutex/spinlock) pour éviter que deux processeurs tentent de modifier ce pointeur en même temps.

Une autre synchronisation a lieu pour l'accès à la carte graphique. Quand un processeur a finit son travail, il envoie le triangle finalisé à la carte graphique. Mais elle ne peut recevoir qu'un triangle à la fois. Si deux processeurs finissent leur travail presque en même temps, ils vont vouloir envoyer leur résultat en même temps. Il y a alors un conflit d’accès à la carte graphique : plusieurs processeurs veulent communiquer avec en même temps. Là encore, un mécanisme de synchronisation est prévu, lui aussi logiciel et basé sur des mutex/spinlock/autres.

Le processeur ajoutait des instructions spéciales pour accélérer le clipping. Les opérations de clipping en question élimine les pixels situés en-dehors du champ de vision de la caméra, en-dehors du view frustrum. Une implémentation naïve demande d'enchainer 6 paires de calculs, avec chacune une comparaison et un branchement. L'optimisation mémorise les résultats des comparaisons dans un registre de 6 bits (un bit par comparaison). Les 6 bits de résultats sont ensuite analysés par un unique branchement. Ainsi, on passe de 6 comparaisons + 6 branchements à 6 comparaisons + 1 branchement.

Les cartes accélératrices des PC grand publics : les années 90-2000

La seconde période est celle de l'arrivée des accélérateurs 3D sur les PC grand public et les consoles. Au début de cette période, les cartes graphiques se débrouillaient sans circuits géométriques. Le calcul de la géométrie était réalisé sur le processeur, la carte graphique s'occupait de la rastérisation et de ce qui arrive après.

Sur PC, la Geforce 256 a été la première à intégrer une unité non-programmable pour gérer transformation et éclairage, appelée l'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. En plus de l'unité de T&L, il y avait deux circuits supplémentaires : un input assembler et un circuit d'assemblage des primitives. 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.

Dans les tableaux qui vont suivre, les circuits non-programmables sont indiqués en rouge.

Cartes accélératrices PC, avant l'arrivée des shaders
Input assembly	Transform & Lighting	Primitive assembly

Les autres cartes graphiques de l'époque avaient une implémentation similaire, sur PC et console. Soit elles ne faisaient pas de calculs géométriques, soit elles avaient une unité de T&L. Précisons cependant une exception notable : la Nintendo 64, qui avait un processeur de shader pour la géométrie.

La Geforce 3 a remplacé l'unité de T&L par un processeur de vertex shader programmable. Il s'occupait donc des phases de transformation et d'éclairage, comme les circuits de T&L qu'ils remplaçaient. Les autres GPU de l'époque ont suivi le mouvement. Les processeurs de shaders étaient toujours accompagnés de l''input assembler et de l'assembleur de primitive.

Après la Geforce 3, avant DirectX 10
Input assembly	Vertex shader	Primitive assembly

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. Mais DirectX 10 a changé la donne, avec l'introduction des geometry shader. Nous détaillerons ces shaders dans le prochain chapitre. Tout ce que nous dirons est que ces shaders ne travaillent pas sur des sommets isolés, mais travaillent sur des primitives, des triangles. Ils peuvent ajouter, retirer ou modifier des triangles. Mais le résultat était assez désastreux. Les geometry shaders étaient trop limitées et les programmeurs avaient beaucoup de mal à les utiliser, ce qui fait que ces technologies ont été peu utilisées.

DirectX 10
Input assembly	Vertex shader	Geometry shader				Primitive assembly

Par la suite, des shaders dédiés aux techniques de tesselations ont été introduits. Nous verrons cela dans quelques chapitres, mais les techniques de tesselations visent à augmenter les détails géométriques d'un modèle 3D, en ajoutant des sommets à la volée. Des shaders dédiés ajoutent des sommets à un modèle, en suivant un certain algorithme.

DirectX 11
Input assembly	Vertex shader	Hull shader	Tesselation	Domain shader	Geometry shader	Primitive assembly

L'arrivée des primitive shaders d'AMD et des mesh shaders de NVIDIA a modifié en profondeur le pipeline géométrique, qui est devenu plus simple, plus puissant et plus flexible. Ces shaders sont des geometry shaders améliorés, à savoir qu'ils peuvent travailler sur des primitives directement, voire sur des paquets de primitives. Concrètement, ils reçoivent des paquets de 32 sommets et exécutent des calculs dessus. Les calculs ne traitent pas chaque sommet isolément, ce qui permet de travailler sur des plusieurs triangles à la fois. Avec de tels shaders, les étapes d'assemblage de primitives et d'input assembly sont inutiles, et ont disparues.

Avec les primitive shaders, l'implémentation exacte dépend de si la tesselation est activée ou non. Si la tesselation n'est pas activée, le vertex shader et le geométry shader sont fusionnés en un seul primitive shader.

Comparaison entre les pipelines géométriques de DirectX 11 et 12, sans tesselation

DirectX 11	Input assembly	Vertex shader	Geometry shader	Primitive assembly
DirectX 12	Primitive shader (AMD)

Avec la tesselation activée, les geometry shaders et les domain shaders en un seul shader. De même, les vertex shaders et les hull shaders sont fusionnés en un seul shader, nommé l'amplification shader. Ainsi, le pipeline graphique est grandement simplifié, avec seulement deux shaders et un étage fixe, au lieu de quatre shaders différents.

Comparaison entre les pipelines géométriques de DirectX 11 et 12, avec tesselation

DirectX 11	Input assembly	Vertex shader	Hull shader	Tesselation	Domain shader	Geometry shader	Primitive assembly
DirectX 12	Amplification shader (AMD)			Tesselation	Primitive shader (AMD)

La tessellation

La tessellation est une technique qui permet d'ajouter des triangles à une surface à la volée. Les techniques de tesselation décomposent chaque triangle en sous-triangles plus petits, et modifient les coordonnées des sommets créés lors de ce processus. L'algorithme de découpage des triangles et la modification des coordonnées varie beaucoup selon la carte graphique ou le logiciel utilisé. Typiquement, les cartes graphiques actuelles ont un algorithme matériel pour le découpage des triangles qui est juste configurable, mais la modification des coordonnées des nouveaux sommets est programmable depuis DirectX 11.

Tessellation.

Elle permet d'obtenir un bon niveau de détail géométrique, sans pour autant remplir la mémoire vidéo de sommets pré-calculés. Lire des sommets depuis la mémoire vidéo est une opération couteuse, même si les caches de sommets limitent la casse. La tesselation permet de lire un nombre limité de sommets depuis la mémoire vidéo, mais ajoute des sommets supplémentaires dans les unités de gestion de la géométrie. Les détails géométriques ajoutés par la tesselation demandent donc de la puissance de calcul, mais réduisent les accès mémoire.

L'historique de la tesselation sur les cartes 3D

Les premières tentatives utilisaient des algorithmes matériels de tesselation, et non des shaders. Par exemple, la première carte graphique commerciale avec de la tesselation matérielle était la Radeon 8500, de l'entreprise ATI (aujourd'hui rachetée par AMD), avec la technologie de tesselation TrueForm. Elle utilisait un circuit non-programmable, qui tessellait certaines surfaces et interpolait la forme de la surface entre les sommets.

ATI améliora ensuite le TrueForm pour que des informations de tesselation soient lues depuis une texture, ce qui permet une implémentation de la technologie dite du displacement mapping. En même temps, Matrox ajouta un algorithme de tesselation basé sur la technique de N-patch dans ses cartes graphiques. Mais ces techniques se basaient sur des algorithmes matériels non-programmables, ce qui rendait ces technologies insuffisamment flexibles et impraticables. De plus, c'était des technologies propriétaires, que les autres fabricants de cartes graphiques n'ont pas adopté. Elles sont donc tombées en désuétude.

La tesselation a eu un regain d'intérêt à l'arrivée des geometry shaders dans DirectX 10 et OpenGL 3.2. Et il y avait de quoi, de tels shaders pouvant en théorie implémenter une forme limitée de tesselation. Mais le cout en performance est trop important, sans compter que les limitations de ces shaders n'a pas permis leur usage pour de la tesselation généraliste.

Dans les tableaux qui vont suivre, les circuits non-programmables sont indiqués en rouge.

DirectX 9
Input assembly	Vertex shader		Primitive assembly
DirectX 10
Input assembly	Vertex shader	Geometry shader	Primitive assembly

Une nouvelle étape a été franchie avec l'AMD Radeon HD2000 et le GPU de la Xbox 360, qui permettaient une tesselation partiellement programmable. La tesselation se faisait en deux étapes : une étape de découpage des triangles et une étape de modification des sommets créés. La première étape était un algorithme matériel configurable mais non-programmable, alors que la seconde était programmable. Mais le manque de support logiciel, le fait qu'on ne pouvait pas utiliser la tesselation en même temps que les geometry shader, ainsi que la non-utilisation de cette technique par NVIDIA, a fait que cette technique n'a pas été reprise dans les GPU suivants.

Il fallut attendre l'arrivée des tesselation shaders dans OpenGL 4.0 et DirectX 11 pour que des shaders adéquats arrivent sur le marché commercial. La tesselation sur ces cartes graphiques se fait en trois étapes : deux shaders et un algorithme matériel fixe entre les deux. Dans le détail, un hull shader est suivi par un étage fixe de tesselation, lui-même suivi par un domain shader. L'étage fixe est là où se situe le découpage des triangles par l'unité matérielle configurable. La tesselation est suivie par la modification de la place des vertices créées, mais il y a aussi un shader avant la génération des nouveaux triangles.

Avant DirectX 11
Input assembly	Vertex shader				Geometry shader	Primitive assembly
DirectX 11
Input assembly	Vertex shader	Hull shader	Tesselation	Domain shader	Geometry shader	Primitive assembly

Les geometry shaders et les tesselation shaders étaient très limités, ce qui fait qu'ils ont été peu utilisés. Les programmeurs avaient beaucoup de mal à les utiliser de manière performante, sans compter que ces shaders s'intégraient très mal au pipeline graphique existant. Les cartes graphiques avaient du mal à les intégrer au hardware, sauf à recourir à des méthodes quelque peu tordues, comme on le verra dans ce qui suit.

Pour résumer, le pipeline géométrique des PC est donc assez différent de ce qu'on avait sur les mainframes. Le pipeline géométrique a beaucoup évolué dans le temps. Les étapes d'input assembler et d'assemblage des primitives sont restées des circuits fixes, pour quasiment disparaitre sur les GPU modernes. Par contre, les étapes de transformation et d'éclairage ont elles beaucoup évoluées. Elles sont passées de circuits fixes à des circuits programmables. Et de nombreuses étapes ont été rajoutées.