Les cartes graphiques/Le support matériel du lancer de rayons

Les cartes graphiques actuelles utilisent la technique de la rastérisation, qui a été décrite en détail dans le chapitre sur les cartes accélératrices 3D. Mais nous avions dit qu'il existe une seconde technique générale pour le rendu 3D, totalement opposée à la rastérisation, appelée le lancer de rayons. Cette technique a cependant été peu utilisée dans les jeux vidéo, jusqu'à récemment. La raison est que le lancer de rayons demande beaucoup de puissance de calcul, sans compter que créer des cartes accélératrices pour le lancer de rayons n'est pas simple.

Mais les choses commencent à changer. Quelques jeux vidéos récents intègrent des techniques de lancer rayons, pour compléter un rendu effectué principalement en rastérisation. De plus, les cartes graphiques modernes incorporent quelques circuits pour accélérer le lancer de rayons, même s'ils restent marginaux des compléments au rendu par rastérisation. S'il a existé des cartes accélératrices totalement dédiées au rendu en lancer de rayons, elles sont restées confidentielles. Aussi, nous allons nous concentrer sur les cartes graphiques récentes, et allons peu parler des cartes accélératrices dédiées au lancer de rayons.

Le lancer de rayons

Le lancer de rayons et la rastérisation. commencent par générer la géométrie de la scène 3D, en plaçant les objets dans la scène 3D, et en effectuant l'étape de transformation des modèles 3D, et les étapes de transformation suivante. Mais les ressemblances s'arrêtent là. Le lancer de rayons effectue l'étape d'éclairage différemment, sans compter qu'il n'a pas besoin de rastérisation.

Le ray-casting : des rayons tirés depuis la caméra

La forme la plus simple de lancer de rayon s'appelle le ray-casting. Elle émet des lignes droites, des rayons qui partent de la caméra et qui passent chacun par un pixel de l'écran. Les rayons font alors intersecter les différents objets présents dans la scène 3D, en un point d'intersection. Le moteur du jeu détermine alors quel est le point d'intersection le plus proche, ou plus précisément, le sommet le plus proche de ce point d'intersection. Ce sommet est associé à une coordonnée de textures, ce qui permet d'associer directement un texel au pixel associé au rayon.

En somme, l'étape de lancer de rayon et le calcul des intersections remplacent l'étape de rasterisation, mais les étapes de traitement de la géométrie et des textures existent encore. Après tout, il faut bien placer les objets dans la scène 3D/2D, faire diverses transformations, les éclairer. On peut gérer la transparence des textures assez simplement, si on connait la transparence sur chaque point d'intersection d'un rayon, information présente dans les textures.

Exemple de rendu en ray-casting 2D dans un jeu vidéo.

En soi, cet algorithme est simple, mais il a déjà été utilisé dans pas mal de jeux vidéos. Mais sous une forme simple, en deux dimensions ! Les premiers jeux IdSoftware, dont Wolfenstein 3D et Catacomb, utilisaient cette méthode de rendu, mais dans un univers en deux dimensions. Cet article explique bien cela : Le moteur de rendu de Wolfenstein 3D. Au passage, si vous faites des recherches sur le raycasting, vous verrez que le terme est souvent utilisé pour désigner la méthode de rendu de ces vieux FPS, alors que ce n'en est qu'un cas particulier.

Le raytracing proprement dit

Le lancer de rayon proprement dit est une forme améliorée de raycasting dans la gestion de l'éclairage et des ombres est modifiée. Le lancer de rayon calcule les ombres assez simplement, sans recourir à des algorithmes compliqués. L'idée est qu'un point d'intersection est dans l'ombre si un objet se trouve entre lui et une source de lumière. Pour déterminer cela, il suffit de tirer un trait entre les deux et de vérifier s'il y a un obstacle/objet sur le trajet. Si c'est le cas, le point d'intersection n'est pas éclairé par la source de lumière et est donc dans l'ombre. Si ce n'est pas le cas, il est éclairé avec un algorithme d'éclairage.

Le trait tiré entre la source de lumière et le point d'intersection est en soi facile : c'est rayon, identique aux rayons envoyés depuis la caméra. La différence est que ces rayons servent à calculer les ombres, ils sont utilisés pour une raison différente. Il faut donc faire la différence entre les rayons primaires qui partent de la caméra et passent par un pixel de l'écran, et les rayon d'ombrage qui servent pour le calcul des ombres.

Les calculs d'éclairage utilisés pour éclairer/ombrer les points d'intersection vous sont déjà connus : la luminosité est calculée à partir de l'algorithme d'éclairage de Phong, vu dans le chapitre "L'éclairage d'une scène 3D : shaders et T&L". Pour cela, il faut juste récupérer la normale du sommet associé au point d'intersection et l'intensité de la source de lumière, et de calculer les informations manquantes (l'angle normale-rayons de lumière, autres). Il détermine alors la couleur de chaque point d'intersection à partir de tout un tas d'informations.

Le raytracing récursif

La technique de lancer de rayons précédente ne gère pas les réflexions, les reflets, des miroirs, les effets de spécularité, et quelques autres effets graphiques de ce style. Pourtant, ils peuvent être implémentés facilement en modifiant le raycasting d'une manière très simple.

Il suffit de relancer des rayons à partir du point d'intersection. La direction de ces rayons secondaires est calculée en utilisant les lois de la réfraction/réflexion vues en physique. De plus, les rayons secondaires peuvent eux-aussi créer des rayons secondaires quand ils sont reflétés/réfractés, etc. La technique est alors appelée du lancer de rayons récursif, qui est souvent simplement appelée "lancer de rayons".

Les optimisations du lancer de rayons

Les calculs d'intersections sont très gourmands en puissance de calcul. Sans optimisation, on doit tester l'intersection de chaque rayon avec chaque triangle. Mais diverses optimisations permettent d'économiser des calculs. Elles consistent à regrouper plusieurs triangles ensemble pour rejeter des paquets de triangles en une fois. Pour cela, la carte graphique utilise des structures d'accélération, qui mémorisent les regroupements de triangles, et parfois les triangles eux-mêmes.

Les volumes englobants

Objet englobant : la statue est englobée dans un pavé.

L'idée est d'englober chaque objet par un pavé appelé un volume englobant. Le tout est illustré ci-contre, avec une statue représentée en 3D. La statue est un objet très complexe, contenant plusieurs centaines ou milliers de triangles, ce qui fait que tester l'intersection d'un rayon avec chaque triangle serait très long. Par contre, on peut tester si le rayon intersecte le volume englobant facilement : il suffit de tester les 6 faces du pavé, soit 12 triangles, pas plus. S'il n'y a pas d'intersection, alors on économise plusieurs centaines ou milliers de tests d'intersection. Par contre, s'il y a intersection, on doit vérifier chaque triangle. Vu que les rayons intersectent souvent peu d'objets, le gain est énorme !

L'usage seul de volumes englobant est une optimisation très performante. Au lieu de tester l'intersection avec chaque triangle, on teste l'intersection avec chaque objet, puis l'intersection avec chaque triangle quand on intersecte chaque volume englobant. On divise le nombre de tests par un facteur quasi-constant, mais de très grande valeur. Il faut noter que les calculs d'intersection sont légèrement différents entre un triangle et un volume englobant. Il faut dire que les volumes englobant sont généralement des pavées, ils utilisent des rectangles, etc. Les différences sont cependant minimales.

Mais on peut faire encore mieux. L'idée est de regrouper plusieurs volumes englobants en un seul. Si une dizaine d'objets sont proches, leurs volumes englobants seront proches. Il est alors utile d'englober leurs volumes englobants dans un super-volume englobant. L'idée est que l'on teste d'abord le super-volume englobant, au lieu de tester la dizaine de volumes englobants de base. S'il n'y a pas d'intersection, alors on a économisé une dizaine de tests. Mais si intersection, il y a, alors on doit vérifier chaque sous-volume englobant de base, jusqu'à tomber sur une intersection. Vu que les intersections sont rares, on y gagne plus qu'on y perd.

Et on peut faire la même chose avec les super-volumes englobants, en les englobant dans des volumes englobants encore plus grands, et ainsi de suite, récursivement. On obtient alors une hiérarchie de volumes englobants, qui part d'un volume englobant qui contient toute la géométrie, hors skybox, qui lui-même regroupe plusieurs volumes englobants, qui eux-mêmes...

Le nombre de tests d'intersection est alors grandement réduit. On passe d'un nombre de tests proportionnel aux nombres d'objets à un nombre proportionnel à son logarithme. Plus la scène contient d'objets, plus l'économie est importante. La seule difficulté est de générer la hiérarchie de volumes englobants à partir d'une scène 3D. Divers algorithmes assez rapides existent pour cela, ils créent des volumes englobants différents. Les volumes englobants les plus utilisés dans les cartes 3D sont les axis-aligned bounding boxes (AABB).

La hiérarchie est mémorisée en mémoire RAM, dans une structure de données que les programmeurs connaissent sous le nom d'arbre, et précisément un arbre binaire ou du moins d'un arbre similaire (k-tree). Traverser cet arbre pour passer d'un objet englobant à un autre plus petit est très simple, mais a un défaut : on saute d'on objet à un autre en mémoire, les deux sont souvent éloignés en mémoire. La traversée de la mémoire est erratique, sautant d'un point à un autre. On n'est donc dans un cas où les caches fonctionnent mal, ou les techniques de préchargement échouent, où la mémoire devient un point bloquant car trop lente.

La cohérence des rayons

Les rayons primaires, émis depuis la caméra, sont proches les uns des autres, et vont tous dans le même sens. Mais ce n'est pas le cas pour des rayons secondaires. Les objets d'une scène 3D ont rarement des surfaces planes, mais sont composés d'un tas de triangles qui font un angle entre eux. La conséquence est que deux rayons secondaires émis depuis deux triangles voisins peuvent aller dans des directions très différentes. Ils vont donc intersecter des objets très différents, atterrir sur des sources de lumières différentes, etc. De tels rayons sont dits incohérents, en opposition aux rayons cohérents qui sont des rayons proches qui vont dans la même direction.

Les rayons incohérents sont peu fréquents avec le rayctracing récursif basique, mais deviennent plus courants avec des techniques avancées comme le path tracing ou les techniques d'illumination globale. En soi, la présende de rayons incohérents n'est pas un problème et est parfaitement normale. Le problème est que le traitement des rayons incohérent est plus lent que pour les rayons cohérents. Le traitement de deux rayons secondaires voisins demande d'accéder à des données différentes, ce qui donne des accès mémoire très différents et très éloignés. On ne peut pas profiter des mémoires caches ou des optimisations de la hiérarchie mémoire, si on les traite consécutivement. Un autre défaut est qu'une même instance de pixels shaders va traiter plusieurs rayons en même temps, grâce au SIMD. Mais les branchements n'auront pas les mêmes résultats d'un rayon à l'autre, et cette divergence entrainera des opérations de masquage et de branchement très couteuses.

Pour éviter cela, les GPU modernes permettent de trier les rayons en fonction de leur direction et de leur origine. Ils traitent les rayons non dans l'ordre usuel, mais essayent de regrouper des rayons proches qui vont dans la même direction, et de les traiter ensemble, en parallèle, ou l'un après l'autre. Cela ne change rien au rendu final, qui traite les rayons en parallèle. Ainsi, les données chargées dans le cache par le premier rayon seront celles utilisées pour les rayons suivants, ce qui donne un gain de performance appréciable. De plus, cela évite d'utiliser des branchements dans les pixels shaders. Les méthodes de tri de rayons sont nombreuses, aussi en faire une liste exhaustive serait assez long, sans compter qu'on ne sait pas quelles sont celles implémentées en hardware, ni commetn elles le sont.

Les avantages et désavantages comparé à la rastérisation

Volume délimité par la caméra (*view frustum*).

L'avantage principal du lancer de rayons est la détermination des surfaces visibles. La rastérisation a tendance à calculer inutilement des portions non-rendues de la scène 3D, malgré l'usage de techniques de culling ou de clipping aussi puissantes qu'imparfaites. De nombreux fragments/pixels sont éliminés à la toute fin du pipeline, grâce au z-buffer, après avoir été calculés et texturés. Le lancer de rayons ne calcule pas les portions invisibles de l'image par construction : pas besoin de culling, de clipping, ni même de z-buffer. D'ailleurs, l'absence de z-buffer réduit grandement le nombre d'accès mémoire.

Les réflexions et la réfraction sont gérées naturellement par le lancer de rayon récursif, alors qu'elles demandent des ruses de sioux pour obtenir un résultat correct avec la rastérisation. L'éclairage et les ombres se rendent difficilement avec la rastérisation, cela demande de précalculer des textures comme des shadowmaps ou des lightmaps. Avec le lancer de rayon, pas besoin de précalculer ces textures, tout est calculé avec le lancer de rayons, ce qui réduit les accès aux textures. Mieux : les processeurs de shaders n'ont plus besoin d'écrire dans des textures. Grâce à cela, les caches de texture sont en lecture seule, leurs circuits sont donc assez simples et performants, les problèmes de cohérence des caches disparaissent.

Mais tous ces avantages sont compensés par le fait que le lancer de rayons est plus lent sur un paquet d'autres points. Déjà, les calculs d'intersection sont très lourds, ils demandent beaucoup de calculs et d'opérations arithmétiques, plus que pour l'équivalent en rastérisation. Ensuite, le lancer de rayon n'est pas économe niveau accès mémoire. Ce qu'on économise avec l’absence de tampon de profondeur et l'absence de textures d'éclairage précalculées, on le perd au niveau de la BVH et des accès aux textures.

Par contre, la BVH est un énorme problème. Les BVH étant ce que les programmeurs connaissent sous le nom d'arbre binaire, elles dispersent les données en mémoire. Et les GPU et CPU modernes préfèrent des données consécutives en RAM. Leur hiérarchie mémoire est beaucoup plus efficace pour accéder à des données proches en mémoire qu'à des données dispersées et il n'y a pas grand chose à faire pour changer la donne. La traversée d'une BVH se fait avec des accès en mémoire vidéo complétement désorganisés, là où le rendu 3D a des accès plus linéaires qui permettent d'utiliser des mémoires caches.

Le matériel pour accélérer le lancer de rayons

En théorie, il est possible d'utiliser des shaders pour effectuer du lancer de rayons, mais la technique n'est pas très performante. Il vaut mieux utiliser du hardware dédié. Heureusement, cela ne demande pas beaucoup de changements à un GPU usuel.

Le lancer de rayons ne se différencie de la rastérisation que sur deux points dont le plus important est : l'étape de rastérisation est remplacée par une étape de lancer de rayons. Les deux types de rendu ont besoin de calculer la géométrie, d'appliquer des textures et de faire des calculs d'éclairage. Sachant cela, les GPU actuels ont juste eu besoin d'ajouter quelques circuits dédiés pour gérer le lancer de rayons, à savoir des unités de génération des rayons et des unités pour les calculs d'intersection.

Les circuits spécialisés pour les calculs liés aux rayons

Toute la subtilité du lancer de rayons est de générer les rayons et de déterminer quels triangles ils intersectent. La seule difficulté est de gérer la transparence, mais aussi et surtout la traversée de la BVH. En soit, générer les rayons et déterminer leurs intersections n'est pas compliqué. Il existe des algorithmes basés sur du calcul vectoriel pour déterminer si intersection il y a et quelles sont ses coordonnées. C'est toute la partie de parcours de la BVH qui est plus compliquée à implémenter : faire du pointer chasing en hardware n'est pas facile.

Et cela se ressent quand on étudie comment les GPU récents gèrent le lancer de rayons. Ils utilisent des shaders dédiés, qui communiquent avec une unité de lancer de rayon dédiée à la traversée de la BVH. Le terme anglais est Ray-tracing Unit, ce qui fait que nous utiliseront l'abréviation RTU pour la désigner. Les shaders spécialisés sont des shaders de lancer de rayon et il y en a deux types.

Les shaders de génération de rayon s'occupent de générer les rayons
Les shaders de Hit/miss s'occupent de faire tous les calculs une fois qu'une intersection est détectée.

Le processus de rendu en lancer de rayon sur ces GPU est le suivant. Les shaders de génération de rayon génèrent les rayons lancés, qu'ils envoient à la RTU. La RTU parcours la BVH et effectue les calculs d'intersection. Si la RTU détecte une intersection, elle lance l'exécution d'un shader de Hit/miss sur les processeurs de shaders. Ce dernier finit le travail, mais il peut aussi commander la génération de rayons secondaires ou d'ombrage. Suivant la nature de la surface (opaque, transparente, réfléchissante, mate, autre), ils décident s'il faut ou non émettre un rayon secondaire, et commandent les shaders de génération de rayon si besoin.

La RTU : la traversée des structures d'accélérations et des BVH

Lorsqu'un processeur de shader fait appel à la RTU, il lui envoie un rayon encodé d'une manière ou d'une autre, potentiellement différente d'un GPU à l'autre. Toujours est-il que les informations sur ce rayon sont mémorisées dans des registres à l'intérieur de la RTU. Ce n'est que quand le rayon quitte la RTU que ces registres sont réinitialisés pour laisser la place à un autre rayon. Il y a donc un ou plusieurs registres de rayon intégrés à la RTU.

La RTU contient beaucoup d'unités de calculs d'intersections, des circuits de calcul qui font les calculs d'intersection. Il est possible de tester un grand nombre d'intersections de triangles en parallèles, chacun dans une unité de calcul séparée. L'algorithme de lancer de rayons se parallélise donc très bien et la RTU en profite. En soi, les circuits de détection des intersections sont très simples et se résument à un paquet de circuits de calcul (addition, multiplications, division, autres), connectés les uns aux autres. Il y a assez peu à dire dessus. Mais les autres circuits sont très intéressants à étudier.

Il y a deux types d'intersections à calculer : les intersections avec les volumes englobants, les intersections avec les triangles. Volumes englobants et triangles ne sont pas encodés de la même manière en mémoire vidéo, ce qui fait que les calculs à faire ne sont pas exactement les mêmes. Et c'est normal : il y a une différence entre un pavé pour le volume englobant et trois sommets/vecteurs pour un triangle. La RTU des GPU Intel, et vraisemblablement celle des autres GPU, utilise des circuits de calcul différents pour les deux. Elle incorpore plus de circuits pour les intersections avec les volumes englobants, que de circuits pour les intersections avec un triangle. Il faut dire que lors de la traversée d'une BVH, il y a une intersection avec un triangle par rayon, mais plusieurs pour les volumes englobants.

L'intérieur de la RTU contient aussi de quoi séquencer les accès mémoire nécessaires pour parcourir la BVH. Traverser un BVH demande de tester l'intersection avec un volume englobant, puis de décider s'il faut passer au suivant, et rebelotte. Une fois que la RTU tombe sur un triangle, elle l'envoie aux unités de calcul d'intersection dédiées aux triangles.

Les RTU intègrent des caches de BVH, qui mémorisent des portions de la BVH au cas où celles-ci seraient retraversées plusieurs fois de suite par des rayons consécutifs. La taille de ce cache est de l'ordre du kilo-octet ou plus. Pour donner des exemples, les GPU Intel d'architecture Battlemage ont un cache de BVH de 16 Kilo-octets, soit le double comparé aux GPU antérieurs. Le cache de BVH est très fortement lié à la RTU et n'est pas accesible par l'unité de texture, les processeurs de shader ou autres.

Pour diminuer l’impact sur les performances, les cartes graphiques modernes incorporent des circuits de tri pour regrouper les rayons cohérents, ceux qui vont dans la même direction et proviennent de triangles proches. Ce afin d'implémenter les optimisations vues plus haut.

La génération des structures d'accélération et BVH

La plupart des cartes graphiques ne peuvent pas générer les BVH d'elles-mêmes. Pareil pour les autres structures d'accélération. Elles sont calculées par le processeur, stockées en mémoire RAM, puis copiées dans la mémoire vidéo avant le démarrage du rendu 3D. Cependant, quelques rares cartes spécialement dédiées au lancer de rayons incorporent des circuits pour générer les BVH/AS. Elles lisent le tampon de sommet envoyé par le processeur, puis génèrent les BVH complémentaires. L'unité de génération des structures d'accélération est complétement séparée des autres unités. Un exemple d'architecture de ce type est l'architecture Raycore, dont nous parlerons dans les sections suivantes.

Cette unité peut aussi modifier les BVH à la volée, si jamais la scène 3D change. Par exemple, si un objet change de place, comme un NPC qui se déplace, il faut reconstruire le BVH. Les cartes graphiques récentes évitent de reconstruire le BVH de zéro, mais se contentent de modifier ce qui a changé dans le BVH. Les performances en sont nettement meilleures.

Un historique rapide des cartes graphiques dédiées au lancer de rayon

Les premières cartes accélératrices de lancer de rayons sont assez anciennes et datent des années 80-90. Leur évolution a plus ou moins suivi la même évolution que celle des cartes graphiques usuelles, sauf que très peu de cartes pour le lancer de rayons ont été produites. Par même évolution, on veut dire que les cartes graphiques pour le lancer de rayon ont commencé par tester deux solutions évidentes et extrêmes : les cartes basées sur des circuits programmables d'un côté, non programmables de l'autre.

La première carte pour le lancer de rayons était la TigerShark, et elle était tout simplement composée de plusieurs processeurs et de la mémoire sur une carte PCI. Elle ne faisait qu'accélérer le calcul des intersections, rien de plus.

Les autres cartes effectuaient du rendu 3D par voxel, un type de rendu 3D assez spécial que nous n'avons pas abordé jusqu'à présent, dont l'algorithme de lancer de rayons n'était qu'une petite partie du rendu. Elles étaient destinées au marché scientifique, industriel et médical. On peut notamment citer la VolumePro et la VIZARD et II. Les deux étaient des cartes pour bus PCI qui ne faisaient que du raycasting et n'utilisaient pas de rayons d'ombrage. Le raycasting était exécuté sur un processeur dédié sur la VIZARD II, sur un circuit fixe implémenté par un FPGA sur la Volume Pro Voici différents papiers académiques qui décrivent l'architecture de ces cartes accélératrices :

La puce SaarCOR (Saarbrücken's Coherence Optimized Ray Tracer) et bien plus tard par la carte Raycore, étaient deux cartes réelement dédiées au raycasting pur, sans usage de voxels, et étaient basées sur des FPGA. Elles contenaient uniquement des circuits pour accélérer le lancer de rayon proprement dit, à savoir la génération des rayons, les calculs d'intersection, pas plus. Tout le reste, à savoir le rendu de la géométrie, le placage de textures, les shaders et autres, étaient effectués par le processeur. Voici des papiers académiques sur leur architecture :

RayCore: A ray-tracing hardware architecture for mobile devices.

Le successeur de la SaarCOR, le Ray Processing Unit (RPU), était une carte hybride : c'était une SaarCOR basée sur des circuits fixes, qui gagna quelques possibilités de programmation. Elle ajoutait des processeurs de shaders aux circuits fixes spécialisés pour le lancer de rayons. Les autres cartes du genre faisaient pareil, et on peut citer les cartes ART, les cartes CausticOne, Caustic Professional's R2500 et R2100.

Les cartes 3D modernes permettent de faire à la fois de la rasterisation et du lancer de rayons. Pour cela, les GPU récents incorporent des unités pour effectuer des calculs d'intersection, qui sont réalisés dans des circuits spécialisés. Elles sont appelées des RT Cores sur les cartes NVIDIA, mais les cartes AMD et Intel ont leur équivalent, idem chez leurs concurrents de chez Imagination technologies, ainsi que sur certains GPU destinés au marché mobile. Peu de choses sont certaines sur ces unités, mais il semblerait qu'il s'agisse d'unités de textures modifiées.

De ce qu'on en sait, certains GPU utilisent des unités pour calculer les intersections avec les triangles, et d'autres unités séparées pour calculer les intersections avec les volumes englobants. La raison est que, comme dit plus haut, les algorithmes de calcul d'intersection sont différents dans les deux cas. Les algorithmes utilisés ne sont pas connus pour toutes les cartes graphiques. On sait que les GPU Wizard de Imagination technology utilisaient des tests AABB de Plücker. Ils utilisaient 15 circuits de multiplication, 9 additionneurs-soustracteurs, quelques circuits pour tester la présence dans un intervalle, des circuits de normalisation et arrondi. L'algorithme pour leurs GPU d'architecture Photon est disponible ici, pour les curieux : [1].

◄ Retour vers « Les Render Output Target »

Sommaire du livre

Continuer vers « L'antialiasing » ►