Les cartes graphiques/Le rasterizeur

Illustration du principe de la rasterization. La surface correspondant à l'écran est subdivisée en pixels carrés, de coordonnées x et y. La caméra est placée au point e. Pour chaque pixel, on trace une droite qui part de la caméra et qui passe par le pixel considéré. L'intersection entre une surface et cette droite se fait en un point, appartenant à un triangle.

À ce stade du pipeline, les sommets ont été regroupés en primitives. Vient alors l'étape de rasterization, durant laquelle chaque pixel de l'écran se voit attribuer un ou plusieurs triangle(s). Cela signifie que sur le pixel en question, c'est le triangle attribué au pixel qui s'affichera. Pour mieux comprendre quels triangles sont associés à tel pixel, imaginez une ligne droite qui part de caméra et qui passe par un pixel sur le plan de l'écran. Cette ligne intersecte 0, 1 ou plusieurs objets dans la scène 3D. Les triangles situés ces intersections entre cette ligne et les objets rencontrés seront associé au pixel correspondant.

L'étape de rastérisation contient plusieurs étapes distinctes, que nous allons voir dans ce chapitre. C'est lors de cette phase que la perspective est gérée, en fonction de la position de la caméra. Diverses opérations de clipping et de culling, qui éliminent les triangles non-visibles à l'écran, se font aussi après la rasterization ou pendant.

La quasi-totalité des cartes graphiques récentes incorporent un circuit de zastérization, appelé le rasterizeur. Les seules exceptions sont les cartes graphiques très anciennes, mais aussi certaines cartes graphiques intégrées des processeurs Intel datant des années 2010. De nos jours, aucune carte graphique, même bas de gamme ou intégrée, n'est dans ce cas.

Le clipping-culling

A la suite l'assemblage des primitives, plusieurs phases de culling éliminent les triangles non-visibles depuis la caméra.

La première d'entre elle est le back-face culling, qui agit sur les primitives assemblées par l'étape précédente. Elle fait en sorte que les primitives qui tournent le dos à la caméra soient éliminées. Ces primitives appartiennent aux faces à l'arrière d'un objet opaque, qui sont cachées par l'avant. Elles ne doivent donc pas être rendues et sont donc éliminées du rendu.

Ensuite, vient le view frustum culling, dont le nom indique qu'il s'agit de l'élimination de tout ce qui est situé en-dehors du view frustum. Elle fait que ce qui est en-dehors du champ de vision de la caméra n'est pas affiché à l'écran n'est pas calculé ou rendu, dans une certaine mesure. Un soin particulier doit être pris pour les triangles dont une partie seulement est dans le champ de vision. Ils doivent être découpés en plusieurs triangles, tous présents intégralement dans le champ de vision. Les algorithmes pour ce faire sont assez nombreux et il serait compliqué d'en faire une liste exhaustive, aussi nous laissons le sujet de côté pour le moment.

Clipping/View frustum culling dans le cadre d'un écran de forme carrée (en gris).

La rastérisation

Exemple de rastérisation, où les formes géométriques sont une ligne droite, un arc de cercle et un polygone.

Une fois tous les triangles non-visibles éliminés, la carte graphique attribue les primitives restantes à des pixels : c'est l'étape de rastérisation proprement dite, aussi appelée étape de Triangle Setup. Un exemple de rastérisation est donné dans l'illustration ci-contre. On voit que la géométrie de la scène est ici en 2D et décrit : une ligne droite, un arc de cercle et un polygone. La rastérisation dit quels pixels de l'écran correspondent à la ligne, l'arc de cercle et le polygone. La même chose a lieu pour une scène 3D, sans grandes différences particulières.

Il est rare qu'on ne trouve qu'un seul triangle sur la trajectoire d'un pixel : c'est notamment le cas quand plusieurs objets sont l'un derrière l'autre. Si vous tracez une demi-droite dont l'origine est la caméra, et qui passe par le pixel, il arrive qu'elle intersecte la géométrie en plusieurs points. Et dans ce cas, n'allez pas croire que seul l'objet situé devant les autres détermine à lui seul la couleur du pixel. N'oubliez pas que certains objets sont transparents ! Avec la transparence, la couleur finale d'un pixel dépend de la couleur de tous les points d'intersection en question. Cela demande de calculer un pseudo-pixel pour chaque point d'intersection et de combiner leurs couleurs pour obtenir le résultat final. Les pseudo-pixels en question sont appelés des fragments. Les fragments attribués à un même pixel sont combinés pour obtenir la couleur finale de ce pixel. Mais cela s'effectuera assez loin dans le pipeline graphique, et nous reviendrons dessus en temps voulu.

La rastérisation de type scan-line

Rendu en Scan-line.

Si vous avez déjà eu la chance de programmer un moteur de jeu purement logiciel, il est possible que vous ayez eu à coder un rastériseur logiciel. La manière la plus simple est d'utiliser une boucle qui traite l'écran pixel par pixel. Une autre méthode effectue la rastérisation triangle par triangle, mais elle n'est pas pratique et est peu utilisée. Une autre méthode, très populaire en logiciel, traite l'écran ligne par ligne avec un algorithme de type rendu par scalines (scanline rendering).

Malheureusement, le rendu par scanline n'est pas du tout adapté pour une implémentation en matériel. Un premier défaut de cette approche est que les unités de texture ont besoin que le rendu se fasse par blocs de 4 pixels, par carrés de 2 pixels de côté. La raison à cela sera expliquée dans le prochaine chapitre sur les textures, aussi nous ne pouvons pas en parler plus en détail ici. Mais cela se marie mal avec un rendu ligne par ligne. On peut certes adapter l'algorithme de manière à ce qu'il traite deux lignes en parallèle, mais on tombe alors sur des subtilités qui nuisent à une implémentation efficiente. Un autre défaut est que cet algorithme est asymétrique sur l'axe x et sur l'axe y, vu que le rendu est ligne par ligne. Et cela empêche de le paralléliser facilement. Il est en effet très important pour le matériel de pouvoir effectuer des calculs en parallèle, plutôt que les uns après les autres. Et cet algorithme marche assez mal de ce point de vue.

Il existe néanmoins quelques consoles de jeux qui ont implémenté cet algorithme en matériel. Un bon exemple est la console Nintendo 3DS et ses dérivés, qui utilisaient ce genre de rastérisation. Mais la quasi-totalité du matériel récent utilise une autre méthode de rastérisation, plus compatible avec des circuits et plus facilement parallélisable.

La rastérisation basée sur des fonctions de contours et les équations de droite d'un triangle

Par définition, un triangle est une portion du plan délimitée par trois droites, chaque droite passant par un côté. Et chaque droite coupe le plan en deux parties : une à gauche de la droite, une autre à sa droite. Un triangle est définit par l'ensemble des points qui sont du bon côté de chaque droite. Par exemple, si je prend un triangle délimité par trois droites d1, d2 et d3, les points de ce triangle sont ceux qui sont situé à droite de d1, à gauche de d2 et à droite de d3. La rastérisation matérielle profite de cette observation pour déterminer si un pixel appartient à un triangle.

L'idée est de calculer si un pixel est du bon côté de chaque droite, et de combiner les trois résultats pour prendre une décision. Pour chaque droite, on crée une fonction de contours, qui indique de quel côté de la droite se situe le pixel. La fonction de contours va, pour chaque point sur l'image, renvoyer un nombre entier :

• zéro si le point est placé sur la droite ;
• un nombre négatif si le point est placé du mauvais côté de la droite ;
• un nombre positif si le point est placé du bon côté.

Comment calculer cette fonction ? Tout d'abord, nous allons dire que le point que nous voulons tester a pour coordonnées $(x,y)$ sur l'écran. La droite passe quant à elle par deux sommets : le premier de coordonnées $(X_{1},Y_{1})$ et l'autre de coordonnées $(X_{2},Y_{2})$. La fonction est alors égale à :

$f(x,y)=(x-X_{1})\times (Y_{2}-Y_{1})-(y-Y_{1})\times (X_{2}-X_{1})$

Pour savoir si un pixel appartient à un triangle, il suffit de tester le résultat des trois fonctions de contours, une pour chaque droite. A l'intérieur du triangle, les trois fonctions (une par côté) donneront un résultat positif. A l'extérieur, une des trois fonctions donnera un résultat négatif.

L'étape de Triangle traversal

L'usage des fonctions de contours permet de tester un couple pixel-triangle. Pour l'utiliser dans un algorithme de rastérisation, il faut choisir quels pixels tester pour quel triangle. Dans sa version la plus naïve, tous les pixels de l'écran sont testés pour chaque triangle. Mais si le triangle est assez petit, une grande quantité de pixels seront testés inutilement. Pour éviter cela, diverses optimisations ont été inventées. Leur but est de limiter le nombre de pixels à tester. Une autre source d'optimisation matérielle tient dans l'ordre de traitement des pixels. L'algorithme de rastérisation a une influence sur l'ordre dans lequel les pixels sont envoyés aux unités de texture. Et l'ordre de traitement des pixels impacte l'ordre dans lequel on traite les texels (les pixels des textures). Suivant l'ordre de traitement des pixels, les texels lus seront proches ou dispersés en mémoire, ce qui peut permettre de profiter ou non du cache de textures.

La première optimisation consiste à déterminer le plus petit rectangle possible qui contient le triangle, et à ne tester que les pixels de ce rectangle. On économise ainsi beaucoup de calculs, et améliore un peu l'ordre de traitement des pixels. Non seulement on calcule moins de pixels, mais les pixels calculés sont assez proches les uns des autres, bien que ce ne soit pas parfait. L'économie de calcul est assez large, surtout pour les petits triangles. L'amélioration de l'accès aux textures marche surtout pour les petits triangles, mais marche très mal pour les gros triangles.

Smallest rectangle traversal

De nos jours, les cartes graphiques actuelles se basent sur une amélioration de cette méthode. Le principe consiste à prendre ce plus petit rectangle, et à le découper en morceaux carrés. Tous les pixels d'un carré seront testés simultanément, dans des circuits séparés, ce qui est plus rapide que les traiter uns par uns. Ce découpage de l'écran en carrés de pixels s'appelle l'algorithme du tiled traversal. Il a pour avantage qu'il se marie très bien avec la gestion des textures. En effet, les textures sont stockées en mémoire d’une manière particulière : elles sont découpées en carrés de quelques pixels de côté, et les carrés sont répartis dans la mémoire d'une manière assez spécifique. Les carrés des textures ont la même taille que les carrés de la rastérisation. Cela garantit que la rastérisation d'un carré de pixel a de bonnes chances de tomber sur un carré de texture, ce qui permet de profiter parfaitement du cache de texture.

Tiled traversal

La coordonnée de profondeur

Chaque fragment correspond à un point d'intersection entre le regard et la géométrie de la scène. La rastérisation lui attribue une position sur l'écran, codée avec deux coordonnées x et y. Mais elle ajoute aussi une troisième coordonnée : la coordonnée de profondeur, aussi appelée coordonnée z. Le nom de cette coordonnée trahit sa signification : elle précise à quelle distance se situe le fragment de la caméra. Plus précisément, elle précise la distance par rapport au plan du view frustum qui est le plus proche de la caméra. Plus elle est petite, plus le fragment en question est associé à un triangle proche de la caméra.

L'élimination précoce des fragments cachés

La coordonnée z permet de savoir si un objet est situé devant un autre ou non : entre deux fragments de même coordonnée x et y, c'est celui avec le plus petit z qui est devant, car plus proche de la caméra. En théorie, cela peut permettre de savoir si un fragment doit être rendu ou non. Logiquement, si un objet est derrière un autre, il n'est pas visible et ses fragments n'ont pas à être calculés/rendus. Les concepteurs de cartes graphiques usuelles ont donc inventé des techniques d'élimination précoce pour éliminer certains fragments dès qu'on connait leur coordonnée de profondeur, à savoir une fois l'étape de rastérisation/interpolation terminée. Ainsi, on est certain que le fragment en question n'est pas texturé et ne passe pas dans les pixels shaders, ce qui est un gain en performance non-négligeable. Il faut certes prendre en compte la transparence des fragments qui sont devant, mais rien d'insurmontable.

Mais ces techniques peuvent causer un rendu anormal quand la coordonnée de profondeur ou de transparence d'un pixel est modifiée après l'étape de rastérisation, typiquement dans les pixels shaders. Il est rare que les shaders bidouillent la profondeur ou la transparence d'un pixel, mais cela peut arriver. C'est pour cela que l’élimination des fragments invisibles est traditionnellement réalisé à la toute fin du pipeline graphique, dans les ROPs, juste avant d’enregistrer les pixels dans le framebuffer.

Pour éliminer tout problème, on doit recourir à des solutions qui activent ou désactivent l'élimination précoce des pixels suivant les besoins. La plus simple est de laisser le choix aux drivers de la carte graphique. Ils analysent les shaders et décident si le test de profondeur précoce peut être effectué ou non. De nos jours, les APIs graphiques comme DirectX et OpenGl permettent de marquer certains shaders comme étant compatibles ou incompatibles avec l'élimination précoce. C'est possible depuis DirectX 11.

La duplication des circuits de gestion de profondeur

Il existe plusieurs techniques d'élimination précoce', qui sont présentes depuis belle lurette dans les cartes graphiques modernes. La plus simple effectue le même calcul que dans les ROP. Les circuits de gestion de la profondeur sont ainsi dupliqués : un exemplaire est dans le ROP, l'autre en sortie de l'étape de rastérisation. L'implémentation peut utiliser soit deux unités de profondeur, soit une seule unité partagée. La geforce 6800 a apparemment opté pour la seconde solution.

GeForce 6800

Rappelons que la carte graphique change régulièrement de shader à exécuter. Et il arrive qu'on passe d'un shader compatible avec l'élimination précoce à un shader incompatible ou inversement. Passer d'un shader qui est compatible avec l'élimination précoce à un qui ne l'est n'est pas un problème. Il suffit de désactiver l'unité d'élimination précoce lors du changement de shader. Mais dans le cas inverse, quelques problèmes de synchronisation peuvent apparaitre.

Il faut activer l'élimination précoce quand les pixels du nouveau shader sortent du circuit de rastérisation, ce qui n'est pas exactement le même temps que le changement de shader. En effet, le shader précédent a encore des pixels qui traversent le pipeline et qui sont en cours de calcul dans les pixels shaders ou dans les ROP. Le processeur de commande doit donc faire attendre les processeurs de shader et quelques autres circuits. Typiquement, il faut attendre que la commande précédente se termine, avant d'en relancer une autre avec le nouveau shader.

L'interpolation des coordonnées de texture

Une fois l'étape de triangle setup terminée, on sait donc quels sont les pixels situés à l'intérieur d'un triangle donné. Il faut alors texturer le triangle. Pour les pixels situés exactement sur les sommets, on peut reprendre la coordonnée de texture et la profondeur du sommet associé. Mais pour les autres pixels, nous sommes obligés d'extrapoler les coordonnées et la profondeur à partir des données situées aux sommets. C'est le rôle de l'étape d'interpolation, qui calcule les informations des pixels qui ne sont pas pile-poil sur un sommet. Par exemple, si j'ai un sommet vert, un sommet rouge, et un sommet bleu, le triangle résultant doit être colorié comme indiqué dans le schéma de droite.

Les coordonnées barycentriques

Pour calculer les couleurs et coordonnées de chaque fragment, on va utiliser les coordonnées barycentriques. Pour faire simple, ces coordonnées sont trois coordonnées notées u, v et w. Pour les déterminer, nous allons devoir relier le fragment aux trois autres sommets du triangle, ce qui découpe le triangle initial en trois triangles. Les coordonnées barycentriques sont simplement proportionnelles aux aires de ces trois triangles. Par proportionnelles, il faut comprendre que les coordonnées barycentriques ne dépendent pas de la valeur absolue de l'aire des trois triangles. A la place, ces trois aires sont divisées par l'aire totale du triangle, et c'est ce rapport qui est utilisé pour calculer les coordonnée barycentriques.

Coordonnées barycentriques.

La carte graphique calcule ces trois coordonnées en commençant par normaliser l'aire du triangle. C'est à dire qu'elle fait en sorte que l'aire totale du triangle soit d'une unité d'aire, qu'elle fasse 1. Les aires des trois triangles sont alors calculées en proportion de l'aire totale, ce qui fait que leur valeur est comprise dans l'intervalle [0, 1]. Cela signifie que la somme de ces trois coordonnées vaut 1 :

$u+v+w=1$

En conséquence, on peut se passer d'une des trois coordonnées dans nos calculs, vu que :

$w=1-(u+v)$

Les trois coordonnées permettent de faire l'interpolation directement . Il suffit de multiplier la couleur/profondeur d'un sommet par la coordonnée barycentrique associée, et de faire la somme de ces produits. Si l'on note C1, C2, et C3 les couleurs des trois sommets, la couleur d'un pixel vaut :

$(C1*u)+(C2*v)+(C3*w)$

La gestion de la perspective

Maintenant, parlons un petit peu des coordonnées de texture. Pour rappel, les coordonnées de texture permettent d'appliquer une texture à un modèle 3D. Il y a un ensemble coordonnée de texture par sommet, qui précise quelle texture appliquer, mais aussi où se situe le texel à appliquer dans la texture. Par exemple, la coordonnée de texture peut dire : je veux le pixel qui est à ligne 5, colonne 27 dans cette texture. Dans les faits, on n'utilise pas de coordonnées entières de ce type, mais deux nombres flottants compris entre 0 et 1. La coordonnée 0,0 correspond au texel en bas à gauche, celui de coordonnée 1,1 est tout en haut à droite. Les deux coordonnées de texture sont notées u,v avec DirectX, ou encore s,t dans le cas général : u est la coordonnée horizontale, v la verticale.

Lors de la rastérisation, chaque fragment se voit attribuer un triangle, et les coordonnées de texture qui vont avec. Si un pixel est situé pile sur un sommet, les coordonnées de texture de ce sommet est attribuée au pixel. Si ce n'est pas le cas, les coordonnées de texture sont interpolées à partir des coordonnées des trois sommets du triangle rastérisé.

Il existe plusieurs moyens de faire cette interpolation, mais le plus simple est l'interpolation affine, identique à celle effectuée pour les autres valeurs interpolées. Concrètement, on fait une moyenne pondérée des coordonnées de texture u et v des trois sommets pour obtenir les coordonnées de textures finales, sans prendre en compte la coordonnée de profondeur. Par contre, en faisant cela, la perspective n'est pas correctement rendue, comme illustré ci-dessous. L'interpolation affine était utilisée sur la console Playstation 1 de Sony, d'où des textures un peu bizarres sur cette console.

Correction de perspective.

D'autres consoles utilisaient l'interpolation affine, mais s'en sortaient mieux car elles utilisaient non pas des triangles, mais des quads (des rectangles). Avec des primitives rectangulaires, le résultat a l'air visuellement, meilleur, car l'interpolation donne un bon résultat pour ce qui va à l'horizontal, seule les objets à la verticale de la caméra donnant une perspective légèrement déformée. Tout cela est bien illustré ci-dessous. Cependant, l'interpolation est alors plus lourde en calculs, car elle demande d'interpoler quatre sommets au lieu de trois. Le cout en calculs n'est pas négligeable.

Affine texture mapping tri vs quad

Si on garde un rendu avec des triangles, moins gourmand en calculs, on pourrait résoudre le problème en interpolant aussi la coordonnée z, mais le rendu est alors aussi peu convainquant qu'avant. Par contre, en interpolant 1/z, et en calculant z à partir de cette valeur interpolée, les problèmes disparaissent. Plus précisément, il faut remplacer les coordonnées u,v,z (les deux coordonnées de texture u,v et la profondeur) par les coordonnées suivantes : u/z, v./z et 1/z. En faisant cela, on s'assure que la perspective est rendue à la perfection. l'explication mathématique de pourquoi cette formule fonctionne est cependant assez compliquée... De plus, cette rastérisation demande d'effectuer des divisions flottantes et est très gourmandes. Raison pour laquelle les vielles cartes vidéo n'utilisaient pas cette interpolation. Mais les cartes graphiques récentes ont des circuits dédiés capables de faire ces lourds calculs sans trop de problèmes.