Le classique algorithme du traceur de Mandelbrot est connu depuis des décades, et pour la plupart, les passionnés de graphisme en ont déjà écrit un. Mais aujourd'hui l'ère du Graphics Processing Unit (GPU) est venue.  Au lieu de rendre la fractale avec le CPU, nous pouvons exploiter la grande puissance et parallélisme des GPU afin que le rendu de la fractale soit beaucoup plus rapide. Regardons de quelle manière nous pouvons adapter l'algorithme précédent au GPU.

4.1 - Une première tentative

Heureusement pour nous, l'algorithme de rendu de Mandelbrot se fait par pixel.  Chaque pixel est traité indépendemment des autres. Cela signifie que nous pouvons simplement rendre un quad qui couvre tout l'écran, et écrire un fragment shader qui effectue le processus d'itération:

uniform vec4 insideColor;
uniform sampler1D outsideColorTable;
uniform float maxIterations;
void main ()
{
	vec2 c = gl_TexCoord[0].xy;
	vec2 z = c;
	gl_FragColor = insideColor;
	for (float i = 0; i < maxIterations; i += 1.0)
	{
		z = vec2(z.x*z.x - z.y*z.y, 2.0*z.x*z.y) + c;
		if (dot(z, z) > 4.0)
		{
			gl_FragColor = texture1D(outsideColorTable, 
			i / maxIterations);
			break;
		}
	}
}

Ceci est précisément le même algorithme que celui vu précédemment; il a été re-écrit en GLSL (OpenGL Shading Language).

Il suppose que vous ayez initialisé une table de couleurs sous la forme d'une texture 1D dans outsideColorTable et que les coordonnées de textures passées au fragment shader correspondent aux nombres complexes. Le shader calcule la suite en employant la multiplication complexe et teste chaque valeur pour voir si elle sort du cercle de rayon 2.

Malheureusement, ce shader sera très lent, et vous ne serez pas capables de rendre la fractale en temps réel, à moins que maxIterations soit très petit. De plus, la boucle et le branchement dans le shader impliquent le support du SM 3.0 (Shader Model) au niveau de la carte graphique.  Au moment où cet article est écrit (ndt: et traduit...), il faut au moins une 6600 ou mieux pour exécuter le shader ci-dessus, et il sera également lent sur une GeForce 7800 (ndt: je confirme: 15 fps sur ma 7800gt), actuellement la plus puissante carte disponible.

4.2 - Stream Processing

Au lieu d'effectuer l'itération de Mandelbrot dans un unique et complexe pixel shader, une approche meilleure serait d'utiliser un algorithme multipasses. Pour implémenter cela, nous pouvons utiliser le modèle stream processing issu des calculs généraux avec GPU (GPGPU). Un shader se chargera de la génération des données, lesquelles sont ensuite utilisées comme entrées d'un autre shader; la sortie du second shader est l'entrée d'un troisième et ainsi de suite.  Puisque les shaders ne peuvent pas lire et écrire dans le même framebuffer, nous devons utiliser un minimum de deux buffers.  Nous allons alors ping-ponguer entre ces deux buffers, d'abord en utilisant l'un comme entrée et l'autre comme sortie, puis en inversant les rôles pour la passe suivante.

Pour rendre la fractale de Mandelbrot dans un algorithme multipasses, nous utiliserons des framebuffers en virgule flottante pour stocker les valeurs de z_n de chaque pixel. Trois shaders au total sont utilisés; le premier initialise les données en stockant simplement les coordonnées de texture (qui représentent les valeurs de c égale à z₁) dans les composantes rouge et verte de chaque pixel:

void main ()
{
	vec2 c = gl_TexCoord[0].xy;
	gl_FragColor = vec4(c, 0, 0);
}

Le second shader sera exécuté continuellement.  Ce shader effectue l'itération proprement dite, calculant la valeur suivante de z_n pour chaque pixel. Dans ce shader, nous récupérons la valeur précédente z_n-1 par un accès à une texture qui est la sortie de la passe précédente; la valeur de c est fournie par les coordonnées de texture comme avant.

uniform sampler2D input;
uniform float curIteration;
void main ()
{
	// Lookup value from last iteration
	vec4 inputValue = texture2D(input, gl_TexCoord[0].xy);
	vec2 z = inputValue.xy;
	vec2 c = gl_TexCoord[0].xy;
	
	// Only process if still within radius-2 boundary
	if (dot(z, z) > 4.0)
		// Leave pixel unchanged (but copy 
		//through to destination buffer)
		gl_FragColor = inputValue;
	else
	{
		gl_FragColor.xy = vec2(z.x*z.x - z.y*z.y, 2.0*z.x*z.y) + c;
		gl_FragColor.z = curIteration;
		gl_FragColor.w = 0.0;
	}
}

Comme vous pouvez le voir, nous stockons également la valeur n (le nombre courant d'itérations passé comme une variable uniform) dans la composante bleue du pixel. Elle sera utilisée dans le troisième shader dont le but est d'afficher la fractale.  Son entrée est le buffer en virgule flottante contenant les valeurs z_n finales, mais à la différence des deux premiers shaders, sa sortie est le buffer de couleurs classique.

uniform sampler2D input;
uniform vec4 insideColor;
uniform sampler1D outsideColorTable;
uniform float maxIterations;
void main ()
{
	// Lookup value from last iteration
	vec4 inputValue = texture2D(input, gl_TexCoord[0].xy);
	vec2 z = inputValue.xy;
	
	// If Z has escaped radius-2 boundary, shade by outer color
	if (dot(z, z) > 4.0)
		gl_FragColor = texture1D(outsideColorTable, 
		inputValue.z / maxIterations);
	else
		gl_FragColor = insideColor;
}

Cet algorithme multipasses à trois shaders dessine la même image que le shader original, mais pourra être exécuté sur n'importe quel carte supportant les textures en virgule flottante.  Dans le monde d'ATI, cela inclut la Radeon 9500 et mieux, et dans celui de nVidia, les GeForce 5200 et mieux. (Remarque: bien que deux des shaders utilisent une instruction if, les cartes pré-SM 3.0 produiront une instruction CMP à la place d'un branchement.)

Les shaders présentés ci-dessous peuvent être assemblés de différentes façons. La plus évidente est d'utiliser le shader d'itération un certain temps en rendu offscreen et d'afficher ensuite le résultat.  Un effet sympathique peut être obtenu en exécutant le shader de visualisation tout de suite après chaque itération. La fractale prend vie et s'anime, faisant apparaître progressivement les détails de sa complexité. Une autre possibilté est de plaquer la fractale sur une surface 3D, ce qui peut être fait assez facilement avec du placage de texture classique, simplement en utilisant le shader de visualisation pour dessiner les triangles de la surface.

Deux problèmes restent cependant non résolus dans notre traceur de Mandelbrot avec GPU. D'abord, il n'y a pas d'antialiasing dans la fractale, puisqu'elle est essentiellement échantillonnée au niveau du point.  Cela crée des images plutôt moches, à moins que les images ne soient rendues en haute résolution et ensuite sous-échantillonées. Le second problème est la précision. Actuellement les cartes ATI utilisent un format de virgule flottante codé sur 24 bits et nVidia un format codé sur 32 bits pour les registres dans les unités de shading et les buffers en virgule flottante stockent les données aussi sur 32 bits. Cela implique que l'on ne peut pas zoomer très loin dans la fractale avant que le manque de précision ne se fasse ressentir. On peut obtenir une précision d'environ 10^-7 avec des flottants sur 32 bits et seulement de 10^-5 avec 24 bits. C'est une inévitable limitation des GPU. Les traceurs de Mandelbrot basés sur le CPU utilisent une précision de 64 bits ou utilisent leurs propres implémentations des nombres flottants à précision arbitraire (ndt: j'ai pas trouvé mieux...).