Quelques définitions

Illumination globale

Les techniques d’illuminations globales (GI) visent à améliorer le rendu d’une scène 3D, en prenant en compte aussi bien la lumière directe (les sources de lumières qui éclairent les objets) que la lumière indirecte (réflexion de la lumière sur les objets, qui éclaire d’autres objets). Ces techniques permettent d’obtenir des rendus réalistes, au prix d’un temps de calcul relativement long (parfois trop pour être compatible avec du rendu en temps réel). Un domaine de la recherche actuelle vise à développer de nouveaux algorithmes d’illumination globale compatible avec le temps réel (jeux 3D).

(source : Wikipédia – Illumination globale)

Illumination indirecte

Dans l’illumination directe (à gauche sur l’illustration suivante), la lumière provenant d’une source est directement réfléchie sur une surface, puis renvoyé vers la caméra. C’est le modèle classique de calcul de la lumière en 3D, que l’on retrouve par exemple dans le modèle de Phong. La lumière est alors décomposée en plusieurs composantes : la lumière ambiante (qui représente une illumination globale constante), la lumière diffuse (qui représente une diffusion de la lumière sur la surface) et la lumière spéculaire (qui représente une réflexion sur la surface).

(Source : Real-Time Global Illumination for Point Cloud Scenes)

Dans l’illumination indirecte, on considère que chaque surface qui reçoit de la lumière va à son tour en renvoyer. Il n’y a donc plus qu’une seule source de lumière, mais une infinité, correspondant à chaque surface qui renvoie de la lumière. Pour réaliser le rendu d’une scène, il faut donc procéder de la façon suivante :

1. pour chaque surface S1 visible par la caméra ;
2. pour chaque surface S2 visible depuis la surface S1 ;
3. calculer la lumière reçue par la surface S2 provenant de la source ;
4. calculer la lumière renvoyée par la surface S2 vers la surface S1 ;
5. calculer la lumière reçue par la surface S1 provenant de la surface S2 ;
6. calculer la lumière totale renvoyée par la surface S1 vers la caméra.

Chaque étape doit prendre en compte plusieurs paramètres. Pour (3), il faut par exemple prendre en compte la distance entre la source et la surface S2 et l’atténuation de la lumière en fonction de la distance. Pour (4), il faut prendre en compte les caractéristiques de la surface et sa capacité à réfléchir la lumière. Pour (5), il faut prendre en compte la distance entre les surfaces S1 et S2 et l’angle d’incidence. Pour (6), les capacités de réflexion de la surface S1 et la distance entre la surface S1 et la caméra.

Cette première approche simple peut largement être améliorée (et complexifiée), en prenant en compte par exemple que la lumière peut se réfléchir plusieurs fois sur des surfaces avant d’atteindre la caméra (particulièrement important lorsque les surfaces sont très réfléchissantes, comme du verre ou du métal poli), de la diffusion de la lumière dans le brouillard ou la poussière (lumière volumétrique, éclat lumineux), la présence de plusieurs sources lumineuses (voir des milliers de sources lumineuses dans le cas de particules incandescentes).

Lancé de rayons

Il existe plusieurs techniques de « lancés ». Elles reposent sur l’idée que la lumière est constituée de rayons qui vont partir de des sources lumineuses, se réfléchir, diffuser et réfracter sur les différentes surfaces (chaque surface pouvant renvoyer plusieurs rayons), puis atteindre la caméra. Dans les techniques de photon mapping, on part des sources lumineuses, on émet des rayons et on les suit jusqu’à la caméra (cette technique est décrite dans un autre article du blog de Simon et fera l’objet d’une traduction). Dans les techniques de lancé de rayons, on part de la caméra, on lance un rayon pour chaque pixel de l’image finale et l’on remonte jusqu’aux sources de lumière (illustration suivante).

(Source : Wikipédia – Raytracing)

Dans la technique du lancé de cônes (Cone Tracing), présentée dans l’article traduit, on remplace simplement les rayons par des cônes pour le calcul de l’illumination.

Occlusion ambiante

Cette technique fera également l’objet de plusieurs traductions du blog de Simon, je la détaillerai à ce moment là.

Simplement pour comprendre l’idée générale : lorsque deux surfaces sont proches (dans une fissure, un trou), la lumière indirecte diminue fortement et l’on observe des ombres douces. Plus les surfaces sont proches et fermées, plus l’ombrage sera important. L’illustration suivante représente la même scène sans (en haut) et avec l’occlusion ambiante (en bas). Remarquez en particulier l’ombre dans l’angle du mur et du sol et entre la sphère dans l’image du bas.

Cette technique améliore fortement la qualité du rendu et commence à être très utilisée dans les jeux. Un de ses points forts est que pour un objet statique (ou peu dynamique), l’occlusion ambiante ne varie pas (ou peu) et il est possible de la pré-calculer, le résultat étant mis dans une texture. Il suffit ensuite d’appliquer la texture sur l’objet lors du rendu, comme n’importe quelle autre texture.

Il existe plusieurs algorithmes de calcul de l’occlusion ambiante, mais pour comprendre le principe, voyons un exemple simple représenté dans l’illustration suivante. Pour chaque point d’une surface, on va lancer un nombre fixé de rayons qui vont parcourir une distance fixée aussi dans toutes les directions. On compte ensuite le nombre de rayons qui ne rencontrent pas une autre surface et on calcul le rapport entre le nombre de rayons ayant rencontrés une surface et le nombre de rayons lancés. Ainsi, dans l’illustration suivante, pour le point A, sur les six rayons lancés, aucun ne rencontre de surfaces, le rapport est de 0/6 = 0 %. Pour le point B, seul quatre rayons ne rencontrent pas de surfaces sur les six lancés, le rapport est de 4/6 = 66 %. Pour le point C, deux rayons ne rencontrent pas de surfaces, le rapport est de 2/6 = 33 %.

Il suffit ensuite d’atténuer la lumière pour chaque point en fonction du rapport calculé. Plus le rapport est proche de 0 %, plus la surface sera sombre et plus le rapport est proche de 100 %, plus la surface est claire.

Pour obtenir un bon rendu, on pourra augmenter le nombre de point et le nombre de rayons lancés, mais l’impact sur les performances sera important.

Partitionnement de l’espace

Voxel

Le principe des voxels est relativement simple : ils sont l’équivalent en 3D des pixels pour la 2D. Un exemple bien connu d’utilisation des voxels est le jeu Minecraft, dans lequel chaque élément (terrain, objets) sont représentés par des cubes.

(Source : Wikiépdia – Minecraft)

Les voxels sont particulièrement gourmand en termes de performances et sont encore peu utilisés pour les jeux vidéos. Ils sont particulièrement adaptés pour le rendu de volumes transparents (verre, liquide, fumée, nuage) ou de géométries très complexes (pour le rendu d’un mesh complexe, une approche utilisant une version low poly du mesh et une texture des Displacement/Normal/Bump mapping).

Octree

Un octree est une structure permettant de partitionner l’espace dans un arbre, permettant par exemple de faciliter la recherche d’un élément par rapport à sa position 3D. La construction d’un tel arbre est simple : à chaque itération, le cube représentant une partie de l’espace est divisé en 8 cubes.

(Source : GPU Gems 2 – Octree Textures on the GPU)

L’intérêt des octrees avec les voxels est que l’on va pouvoir utiliser une structure « creuse » : les zones qui sont vides ne seront pas divisées en cubes plus petits, simplifiant ainsi les algorithmes de recherche et la mémoire.

• utiliser deux boucles for imbriquées pour parcourir chaque pixel du widget et calculer la couleur correspondante, en faisant varier les paramètres S et V dans l’espace colorimétrique HSV ;
• utiliser deux gradient (à l’aide de la classe QLinearGradient), le premier, horizontal, allant du blanc à gauche à la teinte choisie à droite, et le second, vertical, allant du transparent en haut au noir en bas.

Je vais présenter ici comment implémenter un benchmark avec Qt pour tester la rapidité de ces différentes méthodes et présenter deux autres méthodes pour accélérer le rendu : l’accès direct au tampon mémoire contenant l’image finale et l’accélération matériel sur carte graphique.

Création du programme Benchmark

Qt offre différents outils facilitant la création de tests unitaires et de benchmarks, rassemblés dans le module QtTest. Différents tutoriels permettent de se familiariser progressivement avec ce module.

Benchmark.pro

Pour créer notre programme Benchmark, commençons par créer un fichier de projet Benchmark.pro. Ce fichier de projet contient les déclarations de base suivantes : la liste des modules utilisés (core, gui puisse que l’on teste les fonctions de dessin et testlib) et le nom et le type de binaire généré (une application Benchmark dans notre cas) :

On ajoute ensuite la liste des fichiers à inclure dans notre projet. On va simplement créer une classe Benchmark : on ajoute donc les fichiers d’en-tête et d’implémentation :

benchmark.h

La classe Benchmark hérite de QObject (pour pourvoir utiliser le système de signaux et slots) et contient deux slots privés, un pour chaque méthode que l’on souhaite tester. Ces slots seront automatiquement appelés à l’exécution du programme. A part cela, le contenu de la classe est minimaliste :

benchmark.cpp

Dans le fichier d’implémentation, on ajoute chaque méthode dans les slots correspondants :

Il faut également ajouter la macro QTEST_MAIN, qui crée une fonction main, qui aura pour fonction de créer une instance de la classe Benchmark et d’exécuter les slots privés :

Méthode des deux boucles for

Pour mesurer le temps d’exécution d’une méthode, on utilise la macro BENCHMARK. Le temps du reste du code contenu dans le slot mais en dehors du bloc précédent la macro n’est pas évalué. Pour vérifier que le code généré correctement les nuances de gris, on enregistre les images produites :

Méthode des deux gradients linéaires

Le code étant expliqué dans la solution de l’exercice, je n’entre pas dans le détail ici.

Résultat du benchmark

Lorsque le programme est exécuté, des messages sont générés automatiquement à chaque étape du processus. L’en-tête décrit simplement le nom du programme et les versions de QtTest et de Qt utilisées :

Le premier slot que lance le programme est un slot spécifique, initTestCase, généré par défaut et ne faisant rien. Ce slot permet, si on le souhaite, d’initialiser des objets pour l’ensemble du programme :

Vient ensuite les différents slots que l’on a créé. Le premier est hsvGradient. Lorsque le temps d’exécution du slots est trop petit, la mesure risque de ne pas être précise. Pour palier à cet inconvénient, le code contenu dans le bloc de code suivant la macro BENCHMARK peut être exécuté plusieurs fois, le temps indiqué correspondant au temps moyen mesuré. Ici, le slot hsvGradient a été exécuté deux fois et le temps moyen est de 47 millisecondes :

Pour le slot doubleLinearGradient, le code a été exécuté une seule fois et le temps mesuré est de 57 millisecondes. On voit donc ici que cette méthode est plus lente que la première version (sur le système testé ! C’est à dire Linux dans mon cas. Sous Windows ou Max OS X, il est possible que les résultats soient différents). Cette différence peut s’expliquer par le fait que la génération de deux gradients et la gestion de la transparence est plus lente que l’accès directe aux pixels, sur le système de rendu par défaut (le système Raster) :

Le programme exécute ensuite un slot pour libérer les ressources initialisées dans la fonction initTestCase :

Pour terminer, le programme indique le nombre de slot exécutés sans incident (passed), ceux qui ont échoué (failed) et ceux qui n’ont pas été exécutés (skipped) :

Rendu dans un tampon mémoire

Dans la première méthode, on utilise la fonction Qimage::setPixel pour modifier chaque pixel un par un. Cette méthode permet d’utiliser une interface sécurisée et simple. Malheureusement, les calculs (calcul de l’adresse mémoire correspondant au pixel, conversion de l’espace colorimétrique HSV en RGB) et tests effectués en interne (la position du pixel est bien dans l’image ? Les valeurs de la couleurs sont-elles correctes ?) peuvent ralentir fortement l’exécution.
Il est alors possible d’optimiser le rendu en accédant directement à la mémoire à l’aide de pointeurs : on créer un bloc mémoire de taille suffisante que l’on alloue à une image puis on accède à chaque octet un par un.

ATTENTION : ce type d’approche peut comporter certains risques : en cas d’erreur dans le code, il est possible que l’on écrive dans une zone mémoire qui ne correspond pas à l’image. Aucun test n’est effectué pour vérifier que le pointeur pointe vers une zone valide. L’application peut devenir instable. De plus, il est possible que le code ne soit pas portable et donne des résultats différents en fonction des systèmes d’exploitation utilisés (je l’ai testé uniquement sur Linux, pensez à bien enregistrer tous vos documents avant de lancer le programme sur un autre système:) ).

La première chose a faire est de créer une zone mémoire de taille suffisante : un pixel étant codé sur 32 bits (un octet par composante de la couleur et quatre composantes : rouge, vert, bleu et alpha), il faudra donc réserver un bloc mémoire de width * height * 4 pour contenir toute l’image :

Il n’est pas nécessaire d’initialiser chaque octet du bloc mémoire (avec memset par exemple) puisque l’algorithme utilisé garanti que chaque octet sera initialisé durant l’exécution de celui-ci.

Pour commencer, on crée un pointeur pointant vers le premier octet du bloc mémoire :

On utilise deux boucle for, comme dans la première méthode, pour parcourir chaque pixel (en fait, on parcourt le bloc mémoire linéairement, en « déplaçant » le pointeur octet par octet et non en accédant aux coordonnées (x, y) comme dans le cas d’une image) :

Les valeurs de composantes RGB sont calculés par la méthode présentée dans la version QML de la solution de l'exercice :

Ensuite, pour chaque composante, on affecte la valeur calculée (sous forme de uchar pour être sur qu'elle occupe bien à un octet en mémoire) à l'octet pointé par le pointeur (en dé-référençant celui-ci) puis on « avance » le pointeur d’un octet :

On fait de même pour les autres composantes :

Pour terminer, on enregistre l’image générée :

Résultat du benchmark

Les messages de sortie d’application générés par le slot drawInBuffer indique que cette méthode est plus rapide d’un facteur 10 que les deux autres méthodes, avec un temps d’exécution moyen de 3,9 millisecondes :

Optimisation de l’algorithme

Jusqu’à présent, nous avons simplement travailler sur l’implémentation pour optimiser le rendu des nuances de gris. Une autre approche consiste à travailler sur l’algorithme utilisé et d’essayer de diminuer les calculs effectués.
Quelque soit l’approche utilisée, il sera nécessaire de parcourir l’ensemble des pixels du widget, soit explicitement, comme dans le cas de la première méthode présentée, soit implicitement, comme dans le cas des deux QLinearGradient. On ne pourra donc pas optimiser cette partie (on peut au mieux éviter de parcourir plusieurs fois chaque pixel, comme on fait avec la méthode avec les deux QLinearGradient).
On peut remarquer que, dans chaque méthode présentée jusqu’ici, on travaille avec des nombres réels, ce qui n’est pas optimal. L’idéal serait de travailler qu’avec des nombres entiers, mieux gérés par les processeurs, et d’effectuer que des opérations élémentaires : addition, soustraction et multiplication.

Regardons en détail ce que l’on souhaite faire lorsque l’on parcourt un ligne pour une composante en particulier. La composante est une valeur entière allant de 0 à 255 (ou de 255 à 0) pour les pixels allant de 0 à N (avec N > 256 pour être sur d’afficher toutes les nuances). Il faut donc parcourir chaque pixel et incrémenter, quand c’est nécessaire, la composante. Si on représente cela avec un graphique 2D, on obtient :

avec x, l’index des pixels, et y, la composante de la couleur (source : Wikipédia).

Le lecteur averti aura compris l’idée sous-jacente : calculer la composante de la couleur revient à dessiner une ligne dans un espace (x, y) discret. Or, il existe un algorithme très performant pour réaliser cela : l’algorithme de Bresenham. Il suffit juste de remplacer y par la composante de la couleur. Le lecteur se reportera à l’article de Wikipédia pour l’explication du principe de cet algorithme.

L’implémentation de l’algorithme est assez triviale à partir du pseudo-code. On fera attention aux notations utilisées, qui correspondent au pseudo-code, c’est à dire que y1 correspondent à la composante de la couleur et non à la position verticale du pixel. La variable i est utilisée pour parcourir verticalement l’image dans une boucle for :

L'image générée est un gradient allant du noir au blanc :

Pour générer toutes les nuances, il va falloir imbriquer deux fois algorithme, le premier allant du blanc à la teinte choisie (première ligne de pixels) et le second allant de la teinte (pixel de la première ligne) au noir (pixel de la dernière ligne). Il faut également gérer chaque composante indépendamment.

Pour terminer, il est possible de combiner cette méthode avec la méthode utilisant un tampon mémoire. Le code est très proche du précédent.

Résultat du benchmark

La méthode utilisant l’algorithme amélioré permet de gagner un facteur 3 à 4 par rapport aux premières méthodes :

La version combinant les deux approches permet un gain de performance d’un facteur 4 par rapport à la méthode utilisant un tampon mémoire et un facteur 50 par rapport au premières méthodes :

Accélération matériel sur carte graphique

Pour réaliser le rendu des nuances de gris sur carte graphique, on utilise une classe dérivée de QGLWidget. Il suffit de dessiner un rectangle s’adaptant à la taille du widget, le reste du travail de rendu est réalisé dans le fragment shader : on calcule le rapport entre la position du pixel et la largeur du widget (passé en paramètre) pour calculer la nuance de gris correspondante :

Pour que le fragment shader soit appliqué sur chaque pixel du widget, il suffit de dessiner un quadrilatère sur la totalité de la surface :

Les différents paramètres utilisés dans le fragment shader sont définis à l’aide des fonctions uniformLocation et setUniformValue. Par exemple, pour mettre à jour la taille du widget :

Par contre, je n’ai pas réussit à utiliser les fonctions de benchmarks de Qt Test pour tester la rapidité du rendu par cette méthode. Pour pouvoir mesurer le temps, j’ai ajouté un calcul du nombre de FPS (frame par seconde) avec un simple compteur, incrémenté à chaque cycle et remis à zéro toutes les secondes :

Pour mettre à jour la widget, j’utilise un QTimer avec un délai de 0.

ATTENTION : Il en faut pas laisser le programme tourner trop longtemps avec cette méthode. Le programme tourne en boucle et utilise la carte graphique au maximum de ses capacités, ce qui augmente progressivement sa température. Personnellement, je n’ai pas pris le risque de tester si cela pouvait endommager la carte graphique.

Performances

J’ai réalisé le test sur un ordinateur portable équipé d’une carte Nvidia 8600M GT avec 512 Mo et un widget de 256 x 256 pixels. Avec cette configuration, les mesures donnent un FPS moyen de 5000 fps avec de pointes à 5200 fps, c’est à dire des temps de rendu de l’ordre de 0,2 millisecondes (soit 250 fois plus rapide que les premières versions).

Les sources

Télécharger les sources des benchmarks.

Télécharger les sources de la version OpenGL.