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.

Raycasting, rayon simple.

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.

Simple raycasting with fisheye correction

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.

Principe du lancer de rayons.

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

Image rendue avec le lancer de rayons 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".

Lancer de rayon récursif.

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

L'avantage principal du lancer de rayons est son rendu de l'éclairage, qui est plus réaliste. Les ombres se calculent naturellement avec cette méthode de rendu, là où elles demandent des ruses comme des lightmaps, des textures pré-éclairées, divers algorithmes d'éclairage géométriques, etc. 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.

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

Pour ce qui est des performances théoriques, le lancer de rayons se débrouille mieux sur un point : l'élimination des pixels/surfaces cachés. La rastérisation a tendance à calculer inutilement des portions non-rendues de la scène 3D, et doit utiliser des techniques de culling ou de clipping pour éviter trop de calculs inutiles. Ces techniques sont très puissantes, mais imparfaites. De nombreux fragments/pixels calculés 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 se passe totalement de ces techniques d'élimination des pixels cachés, car elle ne calcule pas les portions invisibles de l'image par construction : pas besoin de culling, de clipping, ni même de z-buffer.

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, de nombreuses optimisations présentes en rastérisation ne sont pas possibles. Notamment, le lancer de rayon utilise assez mal la mémoire, dans le sens où les accès en mémoire vidéo sont 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.

Les optimisations du lancer de rayons liées aux volumes englobants

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.

Les hiérarchies de volumes englobants

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...

Hiérarchie de volumes englobants.

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.

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

Le lancer de rayons a toujours besoin de calculer la géométrie, d'appliquer des textures et de faire des calculs d'éclairage. Sachant cela, beaucoup de chercheurs se sont dit qu'il n'était pas nécessaire d'utiliser du matériel spécialisé pour le lancer de rayons, et qu'utiliser les GPU actuels était suffisant. 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.

Une carte graphique spécialement dédiée au lancer de rayons est donc quasiment identique à une carte graphique normale. Les deux contiennent des unités de texture et des processeurs de shaders, des unités géométriques, un input assembler, et tout ce qui va avec. Seuls les circuits de rasterisation et le z-buffer sont remplacés par des circuits dédiés au lancer de rayon, à savoir des unités de génération des rayons et des unités pour les calculs d'intersection. D'ailleurs, il est aussi possible d'ajouter des circuits de génération/intersection de rayons à une carte graphique existante.

Au niveau matériel, la gestion de la mémoire est un peu plus simple. Le lancer de rayon n'écrit que dans le framebuffer et n'a pas besoin de z-buffer, ce qui a beaucoup d'avantages. Notamment, les caches sont en lecture seule, leurs circuits sont donc assez simples et performants, les problèmes de cohérence des caches disparaissent. L'absence de z-buffer fait que de nombreuses écritures/lectures dans le framebuffer sont économisées. Les lectures et écritures de textures sont tout aussi fréquentes qu'avec la rasterisation, et sont même plus faible en principe car de nombreux effets de lumières complexes sont calculés avec le lancer de rayons, alors qu'ils doivent être précalculés dans des textures et lus par les shaders.

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

Toute la subtilité du lancer de rayons est de déterminer si un rayon intersecte un triangle. Pour cela, il existe des algorithmes basés sur du calcul vectoriel pour déterminer si intersection il y a, et quelles sont ses coordonnées. 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. 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.

La génération et le tri des rayons primaire/secondaire/d'ombrage

La génération des rayons n'est pas une étape qui demande beaucoup de puissance de calcul, et elle peut être faite par un processeur de shaders sans problèmes. Pour du rendu en raycasting, il y a juste à générer les rayons primaires, rien de plus. Et la génération des rayons primaires peut être faite par une unité spécialisée, même si ce n'est pas le cas sur les cartes 3D modernes. La génération des rayons d'ombrage et des rayons secondaires est par contre plus complexe.

Les rayons d'ombrage et secondaires sont générés à partir du résultat des intersections des rayons précédents. Et dans les faits, ce sont les shaders qui s'occupent de générer les rayons secondaires. 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 génère ce rayon s'il le faut. Le rayon est alors envoyé aux unités de traversée et d'intersection.

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 traversée des structures d'accélérations et des BVH

Les cartes graphiques modernes incorporent des circuits pour accélérer les accès mémoire aux BVH. Ces circuits se trouvent vraisemblablement dans les unités de texture, si on en croit quelques brevets déposés par les fabricants de carte graphiques, ce qui est logique vu qu'il s'agit d'un des seuls endroits où la carte graphique gère des accès mémoire une fois la géométrie rendue. Et ces unités effectuent un travail essentiel. Car si le calcul des intersections est une chose facile pour la carte graphique, la gestion des structures d'accélération ne l'est pas du tout. Et ce pour plusieurs raisons.

Déjà, les BVH se marient assez mal avec les mémoires caches et la hiérarchie mémoire. Ce sont des structures de données qui dispersent les données en mémoire, dans le sens où chaque volume englobant est située dans sa propre portion de mémoire et celles-ci ne sont pas collées les unes aux autres en mémoire RAM. A l'inverse, les autres structures de données utilisées par la carte graphique, comme les tampons de sommets ou d'indice, les textures, sont des tableaux, des structures de données compactes qui forment un seul bloc en RAM. Traverser un BVH demande de faire des sauts en mémoire RAM, et ce sont des accès mémoire imprévisibles que l'on ne peut pas optimiser, pour lesquels les caches sont inopérants.

L'autre raison, très liée à la précédente, est que traverser un BVH pour trouver le triangle intersectant demande d'effectuer beaucoup de branchements. On doit tester l'intersection avec un volume englobant, puis décider s'il faut passer au suivant, et si oui lequel, et rebelotte. Et dans du code informatique, cela demande beaucoup de IF...ELSE, de branchements, de tests de conditions, etc. Et les cartes graphiques sont assez mauvaises à ça. Les shaders peuvent en faire, mais sont très lents pour ces opérations.

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.

Les 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 :

• The VolumePro Real-Time Ray-Casting System.
• VIZARD II: A reconfigurable interactive volume rendering system

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].