Les cartes graphiques

Tout l'algorithme se base sur une fonction mathématique assez simple : la fonction de contours. Si je dispose d'une droite, la fonction de contours va, pour chaque point sur l'image, renvoyer un nombre entier. Si le point est placé d'un côté (à gauche, en haut, de la droite), alors cette fonction renverra un nombre négatif. Si le point est placé sur la droite, la fonction renvoie zéro. Et enfin, si le point est placé à droite et/ou en bas de la droite, la fonction renvoie un nombre positif.

En bleu, les zones de pixels négatives, en rouge les zones positives.

Comment calculer cette fonction ? Rien de plus simple. Tout d'abord, nous allons dire que le point que nous voulons tester a pour coordonnées x et y sur l'écran. Ensuite, nous allons prendre un des sommets du triangle, de coordonnées X et Y. L'autre sommet, placé sur cette droite, sera de coordonnées X2 et Y2. La fonction est alors égale à :

kitxmlcodelatexdvp(x - X) * (Y2 - Y) - (y - Y) * (X2 - X)finkitxmlcodelatexdvp

En somme, rien de bien compliqué à calculer en matériel : on a juste besoin de circuits additionneurs, de soustracteurs, et de multiplicateurs.

Notre triangle est composé de trois côtés, de trois segments. Si vous appliquez cette fonction à chacun des segments composant ce triangle, vous allez voir une chose assez intéressante :

• à l'intérieur du triangle, les trois fonctions (une par côté) donneront un résultat positif ;
• à l'extérieur, une des trois fonctions donnera un résultat négatif.

Mieux : cet algorithme fonctionne aussi pour les formes qui ne sont pas des triangles.

Pour savoir quels sont les pixels appartenant à un triangle, il suffit de tester pour chaque pixel possible le résultat des fonctions de contours. Si les trois résultats sont positifs, on peut envoyer le pixel au reste de la carte graphique, avec les informations correspondant au triangle. La carte graphique pourra alors placer des textures sur le pixel.

Dans sa version la plus naïve, tous les pixels de l'écran sont testés pour chaque triangle. Si le triangle est assez petit, on est face à un vrai gâchis. Une grande quantité de pixels seront testés inutilement. Pour éviter ces calculs inutiles, diverses optimisations ont été inventées.

La première consiste à déterminer le plus petit rectangle possible qui contient le triangle. Les seuls pixels testés seront alors ceux de ce rectangle. Il en existe aussi beaucoup d'autres.

Mais de nos jours, les cartes graphiques actuelles se basent sur une amélioration de l'algorithme qui détermine le plus petit rectangle contenant le triangle. L'algorithme en lui-même n'est pas vraiment amélioré : son principe est le même. Simplement, les concepteurs de cartes graphiques profitent du fait qu'une carte graphique peut contenir un grand nombre de circuits électroniques capables de travailler en parallèle.

Le principe consiste à prendre notre plus petit rectangle, et à le découper en morceaux carrés. Par exemple, on peut prendre un carré de longueur 8, contenant donc 64 pixels. Tous les pixels de ce carré seront alors testés simultanément, en parallèle, dans des circuits séparés. Le fait de pouvoir tester 64 pixels en même temps permet de gagner en rapidité, même si beaucoup de ces pixels sont testés inutilement.

Petite précision : j'ai parlé dans les phrases précédentes de pixels. Mais il faut bien se rendre compte qu'il ne s'agit pas vraiment des pixels de l'écran. Ce que l'étape de configuration de triangles va fournir, ce sont des informations qui précisent qu'elles sont la couleur, la profondeur d'un pixel calculées à partir d'un triangle. Or, il est rare qu'on ne trouve qu'un seul triangle sur la trajectoire d'un pixel. Il n'est pas rare que plusieurs objets soient l'un derrière l'autre. Dans ces conditions, un seul pixel correspondra à plusieurs triangles : un par objet (voire plus…).

Dans ces conditions, ce que va fournir l'étape d'interpolation, ce sont des informations déduites de l'influence d'un triangle sur le pixel. L'ensemble de ces informations va s'appeler un fragment. Ce fragment peut contenir :

• une position à l'écran ;
• une profondeur ;
• une couleur ;
• une valeur de stencil ;
• une transparence alpha ;
• etc.

Dans la suite, plusieurs fragments pourront être combinés pour obtenir la couleur finale d'un pixel. Mais cela s'effectuera assez loin dans le pipeline graphique : seules, les toutes dernières étapes (le ROP) s'occupent des pixels. Nous reviendrons dessus en temps voulu.

Pour calculer les couleurs et coordonnées de chaque fragment, nous allons devoir ruser. Le but est, à partir d'un point dans un triangle, de déterminer sa couleur, profondeur, etc. ; en fonction de ce qu'on trouve sur les sommets.

Pour cela, on va utiliser ce qu'on appelle les coordonnées barycentriques. Eh oui, encore des maths !

Pour faire très simple, ces coordonnées sont au nombre de trois, et sont notées u, v et w. Pour les déterminer, nous allons devoir relier le point dont on veut la valeur, aux trois autres sommets du triangle.

On obtient ainsi trois triangles :

Les coordonnées barycentriques sont simplement proportionnelles aux aires de ces trois triangles. Je dis « proportionnelles », car il faut savoir que ces trois aires sont divisées par l'aire totale du triangle, ce qui a pour effet de les ramener 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).

L'aire totale du triangle, ainsi que l'aire des trois sous-triangles sont déterminées par un petit calcul tout simple, que la carte graphique peut faire toute seule.

Ces coordonnées barycentriques sont aussi utiles pour calculer l'adresse d'une texture.

Ces trois coordonnées permettent ainsi de repérer un point. Mieux : elles permettent de faire directement l'interpolation, de manière naïve. Il suffit pour cela 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).

Le résultat obtenu est alors celui du milieu :

Le problème : la perspective n'est pas prise en compte ! Intuitivement, on pouvait le deviner : la coordonnée de profondeur (z) n'était pas prise en compte dans le calcul de l'interpolation.

Il va de soi que la carte graphique corrige toute seule la perspective, et qu'elle utilise une méthode d'interpolation un peu plus compliquée que les calculs vus au-dessus.