Génération de textures de terrain

Date de publication : 08/06/2006 , Date de mise à jour : 25/08/2006

Par Jean Christophe Beyler (Autres articles)
 

La génération de terrain est souvent un sujet qui intéresse et passionne. Ce tutoriel présente comment afficher un terrain en utilisant OpenGL et comment lui créer une texture au début de l'exécution du programme. En utilisant trois images de bases (l'herbe, de la roche et de la neige) et une image de niveau monochrome, on peut donc générer une texture qui sera parfaite pour le terrain.

1. Introduction
2. Présentation
3. Génération des textures
3.1. Calculer la hauteur h
3.2. Utiliser la valeur pour calculer la couleur du pixel
3.3. Calcul de la couleur
3.4. Un peu d'aléatoire
3.5. Taille de la texture
4. Le rendu
4.1. Un tableau pour les points
4.2. Dessiner des triangles ou des quads
4.3. Charger la texture avec OpenGL
4.4. L'application de la texture
5. Des ombres
5.1. Avant de continuer
5.2. Une première version
5.3. Les limitations de la 1ère méthode
5.4. Une 2ème solution : L dot N
5.5. Dernière méthode : le calcul des ombres
6. A propos du code source
7. Conclusion
8. Remerciements
9. Téléchargements
10. Poursuite de la génération de Terrain


1. Introduction

Lorsqu'on affiche un terrain en 3 dimensions, il faut arriver à colorer ou utiliser une texture pour le rendu des triangles. Pour un rendu plus réel, la texture doit être appliquée correctement. Le problème réside dans la génération de cette texture, c'est donc ce que nous allons voir ici.

Cet article ne présentera pas en détail chaque aspect du code et suppose donc une connaissance du C et de la bibliothéque SDL. Il montrera par contre les idées générales sur la génération de textures à partir d'une image de niveaux et d'images de base.


2. Présentation

Lorsqu'on veut afficher un terrain en 3 dimensions, on utilise généralement une image qui permet d'avoir la hauteur de chaque point du terrain. Cette image, généralement monochrome, ressemble à ceci :

Image de niveaux
Bien sûr, la gestion des images de niveaux est une convention entre le programme et l'image de niveaux. Généralement, une couleur sombre représente une faible altitude dans le terrain et une couleur clair représente un niveau élevé.

Voici ce que donne l'affichage du terrain en 3 dimension et en mode filaire :

Affichage de terrain 3D en filaire
Mais comment décider comment colorier les différentes zones du terrain? Une première solution serait d'utiliser des couleurs dépendant des hauteurs des sommets du terrain. C'est bien sûr possible mais, généralement, ne donne pas de très bons résultats.

Donc l'idée est de générer une texture qui sera fait parfaitement par rapport au terrain qui sera affiché. Ce que nous voulons faire est d'utiliser trois textures différentes pour afficher correctement le terrain. Voici les trois images que nous allons utiliser :

3 images de base
Donc on va calculer un mélange de ces trois images pour arriver à générer une texture qui sera à l'image de niveaux. On obtient donc ceci :

Texture générée
Et lorsqu'on applique cette texture au rendu 3D, cela donne :

Texture appliquée
La prochaine section présentera comment on crée cette texture.


3. Génération des textures

Pour générer un terrain comme celui-ci, l'algorithme que nous allons utiliser est relativement simple : 
Pour chaque pixel de la texture du terrain
    Faire
        Soit h la hauteur dans le terrain du pixel associé
        Utiliser la valeur de h pour calculer la partie des trois textures de base
        Affecter la couleur au pixel
    Fin
Il faut donc savoir calculer la hauteur h du pixel associé et calculer la couleur du pixel.


3.1. Calculer la hauteur h

Pour calculer la hauteur du pixel associé, on utilise l'image de niveaux. Si nous sommes dans le meilleur des mondes, la taille de la texture du terrain est la même que l'image de niveaux. C'est donc facile d'avoir la hauteur du pixel associé.

Comme le montre ce code, on peut facilement passer de l'échelle 0-255 de l'image de niveaux à l'intervalle [a,b].

Avant de montrer l'algorithme général pour cette transformation, remarquons qu'en utilisant uniquement une couleur d'une image bitmap de niveaux, nous avons seulement 256 niveaux. En utilisant, les trois couleurs à la fois, nous pouvons gérer plus d'un million de niveaux différents. Mais dans le cas général, un seul octet suffit pour faire un joli terrain.
Calcul de la hauteur
/* C'est monochrome, on peut prendre n'importe quelle couleur et c'est une valeur entre 0-255 */
h = la valeur du pixel (i,j); 


h /= 255.0; /* Valeur entre [0,1] */

h *= b-a;   /* Valeur entre [0,b-a] */

h += a;     /* Valeur entre [a,b] */
Nous avons donc la solution pour récupérer la hauteur du pixel associé et la transformer à n'importe quelle échelle.


3.2. Utiliser la valeur pour calculer la couleur du pixel

Pour avoir la couleur du pixel, nous utilisons directement la hauteur du pixel. Dépendant de la hauteur, nous allons utiliser un mélange entre les différentes images de niveaux.

L'image suivante montre le dégradé des images de base :

Dégradé
En effet, si la hauteur est assez basse, on utilisera uniquement la couleur de l'image qui représente de l'herbe. Ensuite, si la hauteur est très haute alors on utilise la couleur de l'image de neige. Bien sûr, cela veut dire que nous pouvons faire des mélanges entre les trois images. Voici la fonction que j'utilise pour donner la couleur du pixel :

La fonction va donc remplir un tableau à 3 éléments qui donnera la participation de la couleur de chacune des trois images de base. Si la valeur est à zéro, on n'utilise pas cet image. Si la valeur est à 1.0, on utilise entièrement cette composante.
Calcul de la composition des couleurs
/* Cette fonction remplit le pourcentage que ce pixel doit avoir dependant de l'hauteur associe
 * Si l'hauteur est faible, c'est que de l'herbe
 * Sinon c'est un melange herbe - roche
 * Plus haut, c'est que de la roche
 * Ensuite un melange roche - neige
 * Et enfin, c'est que de la neige
 */ 	
void Terrain_RemplitPerc(float *perc, unsigned char haut)
{
        /* Que de la prairie */
        if(haut<60)
                {
                perc[0] = 1.0f;
                perc[1] = 0.0f;
                perc[2] = 0.0f;
                }
        /* Melange entre prairie et roche */
        else if(haut<130)
                {
                perc[0] = 1.0f - (haut-60.0f)/70.0f;
                perc[1] = (haut-60.0f)/70.0f;
                perc[2] = 0.0f;
                }
        /* Que de la roche */
        else if(haut<180)
                {
                perc[0] = 0.0f;
                perc[1] = 1.0f;
                perc[2] = 0.0f;
                }
        /* Melange entre roche et la neige */
        else if(haut<220)
                {
                perc[0] = 0.0f;
                perc[1] = 1.0f - (haut-180.0f)/40.0f;
                perc[2] = (haut-180.0f)/40.0f;
                }
        /* Que de la neige */
        else
                {
                perc[0] = 0.0f;
                perc[1] = 0.0f;
                perc[2] = 1.0f;
                }
}
Je pense que vous pouvez comprendre facilement ce code. Les valeurs que j'utilise ont été trouvées empiriquement. Jouez avec les valeurs pour trouver de meilleurs résultats si vous le voulez.

Bien que pas obligatoire, je tente de garder la somme des trois valeurs soit égale à 1. Si on dépasse cette limite, on risque d'avoir des couleurs saturées.


3.3. Calcul de la couleur

Supposons pour l'instant que nous sommes dans le cas où la texture générée est la même taille que les trois images de base. Il est donc facile de savoir le pixel associé aux images de base.

Une fois que nous avons la participation des couleurs des trois images, nous pouvons calculer la couleur du pixel. L'algorithme général est :
Calcul de la couleur
Calcul du pixel (i,j) :
    Appel de Terrain_RemplitPerc(perc,hauteur du pixel(i,j)).
    Récupération du pixel (i,j), nommé A, de l'image prairie associé.
    Récupération du pixel (i,j), nommé B, de l'image roche associé.
    Récupération du pixel (i,j), nommé C, de l'image neige associé.

Rendre perc[0] * A + perc[1] * B + perc[2] * C.
Ce qui se traduit par :
Calcul de la couleur (en C)
/* Recuperation des participations des couleurs pour le pixel courant */
Terrain_RemplitPerc(perc,((unsigned char*) image->pixels)[tmpi*image->w*3 + tmpj*3]);

/* Recuperation des couleurs par image de base */
b = perc[0] * Terrain_GetPixelColor(prairies,tmpi,tmpj,0);
g = perc[0] * Terrain_GetPixelColor(prairies,tmpi,tmpj,1);
r = perc[0] * Terrain_GetPixelColor(prairies,tmpi,tmpj,2);

b += perc[1] * Terrain_GetPixelColor(rocheuses,tmpi,tmpj,0);
g += perc[1] * Terrain_GetPixelColor(rocheuses,tmpi,tmpj,1);
r += perc[1] * Terrain_GetPixelColor(rocheuses,tmpi,tmpj,2);

b += perc[2] * Terrain_GetPixelColor(neige,tmpi,tmpj,0);
g += perc[2] * Terrain_GetPixelColor(neige,tmpi,tmpj,1);
r += perc[2] * Terrain_GetPixelColor(neige,tmpi,tmpj,2);
On a bien une composition des trois images de base. La fonction Terrain_GetPixelColor sera montrée plus bas. Acceptez qu'elle prend en paramètre un couple (tmpi, tmpj) pour rendre une couleur (0 pour bleu, 1 pour vert et 2 pour rouge) de l'image passé en premier paramètre. Le dernier paramètre permet de spécifier si on veut le canal rouge, vert ou bleu.


3.4. Un peu d'aléatoire

Pour ajouter un peu d'aléatoire dans le calcul de la participation des images de base. On peut ajouter ou enlever un peu à la hauteur du pixel avant la distribution de la participation des couleurs. En effet, en ajoutant au début de la fonction Terrain_RemplitPerc :
Un peu d'aléatoire
        /* On utilise la fonction rand pour mettre de l'aleatoire */
        int add = haut + (rand()%30)-15;

        if(add<0)
                add = 0;

        if(add>255)
                add = 255;

        haut = add;
On permet d'ajouter un peu de différence dans le choix de la couleur indépendamment de la hauteur du pixel. En faisant un modulo 30, suivi d'une soustraction de 15, on centre le nombre add sur un intervalle [haut-15, haut+15[ pour ajouter un peu de différence de coloriation des pixels avoisinants. En choisissant des nombres plus petits, la différence se fera moins sentir (il est vrai que 30 est un peu beaucoup).

Voici une comparaison :

A gauche : sans aléatoire, à droite : avec l'aléatoire
On ne voit pas beaucoup de différences entre les deux images de loin. Mais nous voyons des petites différences dans la partie enneigée.

C'est bien sûr une question de goût et de ce que vous cherchez dans votre application. Une image plus proche permet de voir l'effet de l'aléatoire.

A gauche : sans aléatoire, à droite : avec l'aléatoire

3.5. Taille de la texture

Bien sûr, il n'est pas obligatoire que la texture soit de la même taille que les images de base. Pour résoudre le problème, on utilise en fait le modulo pour ne plus avoir de problèmes de débordement. Cette solution n'est pas parfaite mais elle permet d'avoir un meilleur résultat.

Pourquoi avoir une taille plus grande? Cela permet d'avoir plus de détail dans le terrain. C'est encore un compromis entre le temps de calcul, la consommation mémoire et les détails qui seront visibles lors du rendu.

Voici une comparaison entre une texture de taille 1024*1024 et une texture de taille 4096*4096. On voit parfaitement bien la différence de détail.

A gauche : texture de taille 4096*4096, à droite : texture de taille 1024*1024

4. Le rendu

Ce n'est pas tout de pouvoir générer la texture pour le terrain mais il faut pouvoir afficher ce terrain. Cette section expliquera donc cela.


4.1. Un tableau pour les points

Pour optimiser le rendu du programme, on mettra tous les points dans un tableau à 2 dimensions qu'on parcourera lors de l'affichage.
Calcul des points
        for(i=0;i<MAX_POINTS;i++)
        {
                for(j=0;j<MAX_POINTS;j++)
                {
                        res->hauteur[i][j] = Terrain_GetHauteur(image,i,j, MAX_POINTS, MAX_POINTS);
                }
       }
Comme le code le montre, nous débutons la boucle par un calcul de rapport entre les coordonnées (i,j) et le nombre de points sur chaque côté (défini par MAX_POINTS). Nous avons donc une valeur dans l'intervalle [0,1[ pour chaque point.

Ensuite, nous multiplions par la hauteur et la largeur de l'image de niveaux. Ce qui nous donnera le pixel correspondant de l'image.

Enfin, nous pouvons utilisons la fonction Terrain_GetHauteur pour calculer la hauteur du point. Cette fonction en appelle une autre nommée Terrain_GetPixelColor Voici le code de ces petites fonctions :
Fonction de couleur et de hauteur
unsigned char Terrain_GetPixelColor(SDL_Surface *image, int i, int j,int k)
{
        return ((unsigned char*)image->pixels)[i*image->w*3+j*3+k];
}

/* 
 * Recuperation de la hauteur d'un point
 * Puisque notre texture generee n'est pas forcement de la meme taille que l'image de niveaux,
 * nous calculons un ratio entre [0,1] ensuite on remultiplie par la hauteur et la largeur de l'image
 */
double Terrain_GetHauteur(SDL_Surface *image, int i, int j, int maxi, int maxj)
{
        double di,dj;
        double res;
        di = i;
        dj = j;

        di /= maxi;
        dj /= maxj;

        di *= image->h;
        dj *= image->w;

        i = di;
        j = dj;

        res = (Terrain_GetPixelColor(image,i,j,0)/256.0)*param.hautmax;
        return res;
}
Remarquons d'abord le changement de repére. En effet, les coordonnées (i,j) sont les coordonnées de la texture que nous voulons générer. Par contre, notre image de niveau n'a pas forcément la même taille. Donc nous passons par l'intervalle [0,1] pour avoir le point correspondant à l'image.

Dans ce code, j'utilise les surfaces de la bibliothéque SDL. Ces structures contiennent les couleurs des pixels (que nous pouvons modifier pendant l'exécution) sous forme de tableau de type void*. Vu que les pixels sont rangés sont la forme de triplets (rouge,vert,bleu) et en ligne. L'accés au pixel (i,j) se fait logiquement avec le calcul i*(largeur de l'image) + j.

Par contre, vu que nous avons un type void* le facteur 3 que vous voyez nous permet de passer d'un pixel à l'autre (vu qu'il y a trois couleurs par pixel, si on avait une image RGBA, on utiliserait un facteur 4).


4.2. Dessiner des triangles ou des quads

Le terrain est défini par un ensemble de points qui forment un maillage en forme de cases carrées. Pour le dessiner, on peut soit dessiner directement les cases avec des GL_QUADS ou alors dessiner deux triangles avec GL_TRIANGLES.

En fait, si nous voulions faire mieux, il faudrait utiliser GL_TRIANGLE_STRIP ou encore des listes précalculées. Mais cela sort du cadre de ce tutoriel et le programme tourne sur mon ordinateur avec 230 images par seconde. Donc ce n'est pas nécessaire d'optimiser le rendu pour l'instant.

Pour décider quelle technique utilisée, il suffit de décider ce dont vous avez besoin. Ici, nous utiliserons les triangles. Voici comment desssiner les triangles de chaque case sans les textures :
Afficher le terrain
glBegin(GL_TRIANGLES);
for(i=0,posi=-20 ;i<MAX_POINTS-1;i++, posi += ajout)
  {
  for(j=0, posj=-20;j<MAX_POINTS-1;j++, posj += ajout)
    {
    glVertex3d(posi,posj,terrain->hauteur[i][j]);
    glVertex3d(posi,posj+ajout,terrain->hauteur[i][j+1]);
    glVertex3d(posi+ajout,posj+ajout,terrain->hauteur[i+1][j+1]);
				
    glVertex3d(posi,posj,terrain->hauteur[i][j]);
    glVertex3d(posi+ajout,posj+ajout,terrain->hauteur[i+1][j+1]);
    glVertex3d(posi+ajout,posj,terrain->hauteur[i+1][j]);
    }
  }
glEnd();
Expliquons un peu ce code puisqu'il est le centre de l'affichage du terrain. Premièrement, nous utilisons deux couples (i,j) et (posi,posj).

Nous savons que le couple (i,j) parcourt les différents points du terrain. Les dimensions du terrain sont données par la macro MAX_POINTS. Mais nous voulons que les dimensions du terrain soient les mêmes à l'affichage.

Arbitrairement, j'ai décidé que le terrain serait un carré de largeur 40. On va donc associer le couple (posi,posj) avec le couple (i,j). Le point (-20,-20) sera associé avec (0,0) (d'où l'initialisation des variables posi et posj) et le point (20,20) sera associé avec (MAX_POINTS-1, MAX_POINTS-1).

Donc pour garder l'association, nous définissons la distance entre les points par une variable ajout qui est définie comme ceci :
Définition de la variable ajout
double ajout = 40.0 / MAX_POINTS;

4.3. Charger la texture avec OpenGL

Pour passer la texture qu'on vient de créer à OpenGL, on utilise le code suivant :
Chargement de la texture
        /*On passe la texture a OpenGL*/
        glGenTextures(1,&(res->tex));
        glBindTexture(GL_TEXTURE_2D,res->tex);
        glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER,GL_LINEAR);
        glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MIN_FILTER,GL_LINEAR_MIPMAP_NEAREST);
        gluBuild2DMipmaps(GL_TEXTURE_2D, 3, terraintxt->w, terraintxt->h, GL_RGB, GL_UNSIGNED_BYTE, terraintxt->pixels);
C'est du code classique mais je pense que c'est intéressant de le voir une fois. On commence par générer un identifiant de texture. On utilise ensuite la fonction glBindTexture pour dire qu'on va travailler sur cette texture et que c'est une texture 2D.

Ensuite, les fonctions glTexParameteri permettent de dire ce qu'on va faire avec la texture. Ici, nous demandons d'utiliser des textures Mipmaps, ce qui permet d'avoir un bon rendu de loin et de près.

Enfin, on appelle la fonction gluBuild2DMipmaps qui permet de créer les textures Mipmaps.

Une autre solution est d'utiliser à la place un filtrage de base, c'est plus rapide mais l'effet est nettement moins bon. On remplacerait les trois dernières instructions par ceci :
Chargement alternative
      glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER,GL_NEAREST);
      glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MIN_FILTER,GL_NEAREST);
      glTexImage2D(GL_TEXTURE_2D,0,GL_RGB,terraintxt->w,terraintxt->h,0,GL_RGB,
           GL_UNSIGNED_BYTE,terraintxt->pixels);
La différence entre les deux méthodes se trouve dans la façon dont OpenGL va filtrer la texture avant de l'afficher. Comme toujours, appliquer un filtre a un coût non négligeable.

Dépendant de l'ordinateur sur lequel vous tournez un programme comme celui-ci, le niveau de détail peut avoir un impact significatif sur les performances du programme. Etudiez soigneusement vos besoins en terme de performances et en terme de détail pour décider quel filtre choisir.


4.4. L'application de la texture

Il ne reste plus qu'à appliquer la texture au terrain. Pour le faire, nous allons associer un point de la texture à un point du terrain. Simplement, le point (0,0) du terrain sera le point (0,0) de la texture et le point (MAX_POINTS-1, MAX_POINTS-1) du terrain est (1,1) de la texture.

Par contre, il faut faire attention à l'échange des coordonnées. En effet, il est usuel de considérer la première coordonnée du terrain comme étant le numéro de ligne. C'est l'opposé pour les textures, la première coordonnée est la coordonnée des colonnes.
Application de la texture
	glBegin(GL_TRIANGLES);
	for(i=0,posi=-20 ;i<MAX_POINTS-1;i++, posi += ajout)
	{
		for(j=0, posj=-20;j<MAX_POINTS-1;j++, posj += ajout)
		{
			glTexCoord2f( ((float) j)/MAX_POINTS, ((float) i)/MAX_POINTS);
			glVertex3d(posi,posj,terrain->hauteur[i][j]);
				
			glTexCoord2f( ((float) j+1)/MAX_POINTS, ((float) i)/MAX_POINTS);
			glVertex3d(posi,posj+ajout,terrain->hauteur[i][j+1]);
				
			glTexCoord2f( ((float) j+1)/MAX_POINTS, ((float) i+1)/MAX_POINTS);
			glVertex3d(posi+ajout,posj+ajout,terrain->hauteur[i+1][j+1]);
				
			glTexCoord2f( ((float) j)/MAX_POINTS, ((float) i)/MAX_POINTS);
			glVertex3d(posi,posj,terrain->hauteur[i][j]);
				
			glTexCoord2f( ((float) j+1)/MAX_POINTS, ((float) i+1)/MAX_POINTS);
			glVertex3d(posi+ajout,posj+ajout,terrain->hauteur[i+1][j+1]);

			glTexCoord2f( ((float) j)/MAX_POINTS, ((float) i+1)/MAX_POINTS);
			glVertex3d(posi+ajout,posj,terrain->hauteur[i+1][j]);
		}
	}
	glEnd();
Enfin, nous présentons une image utilisant un bleu transparent pour faire un effet d'eau pour rendre le rendu plus réaliste.

Image intermédiaire avec eau

5. Des ombres

En espérant que vous êtes d'accord avec moi, réussir à afficher le terrain comme nous l'avons fait est déjà une bonne chose. Mais il manque une chose primordiale : des ombres pour bien montrer le relief. Cette partie va montrer trois techniques pour le calcul de l'éclairage.

L'ajout d'ombres dans la génération de la texture ajoute un effet de réalisme important au rendu. Regardez l'image suivante qui comprare trois rendus différents. Vous pouvez comparer cette image avec celle de la partie précédente qui n'avait pas d'ombres.

A gauche, la version la plus basique mais qui permet d'avoir un résultat quasi-identique au deuxième (celui du milieu) qui utilise un produit scalaire. Ces deux techniques sont acceptables mais elles ne font qu'un calcul localisé. Donc si nous avions une montagne, on n'aurait pas l'effet d'ombre que la montagne aurait sur la vallée d'à côté. C'est le dernier algorithme (donc l'image de droite) qui permet en plus de faire ressortir un plus grand réalisme en ce qui concerne les ombres.

Comparaison de calculs d'ombre

5.1. Avant de continuer

Avant de commencer l'explication des ombres, je vais prendre deux ou trois paragraphes pour présenter la structure globale qui contiendra toutes les informations pour la génération et la visualisation du terrain. A la place d'avoir une dizaine de variables globales, il nous reste une grande structure avec toutes les informations nécessaires.
Calcul d'ombre
typedef struct sParam
{
        double hautmax;                 /* Hauteur maximal pour le terrain */

        /* Parametres pour l'affichage */
        int filaire;                    /* Filaire ou non */

        double angle;                   /* Le premier angle */
        double angle2;                  /* Le 2eme angle */
        double trans;                   /* Le Zoom */

        int water;                      /* Ajoute-t-on de l'eau */
        double w_cur;                   /* Niveau courant de l'eau */

        int light;                      /* Type de lumière */
        double l_veci, l_vecj,l_vecz;   /* Vecteur de lumière */
        double l_min, l_max;            /* Minimum et Max de lumière de la scène */
        double l_adouc;                 /* Facteur d'adoucissant */
        double l_ldotnmultiple;         /* Facteur multiplicatif */
}SParam;
Sans trop rentrer dans les détails :

  • hautmax : permet d'avoir la taille maximale que le terrain peut prendre lors du rendu;
  • filaire : affichage en filaire ou non;
  • water et w_cur : gestion de l'affichage de l'eau;
  • light : donne le type de calcul d'éclairage. Ces types sont donnés par une série de macros dans le fichier Define.h
  • l_veci, l_vecj et l_vecz : vecteur d'un rayon du soleil
  • l_min et l_max : luminosité minimale et maximale du terrain
  • l_adouc, l_ldotnmultiple : des facteurs pour rendre le rendu plus joli
Cette structure sera déclaré en global dans le fichier Main.c. Voici sa déclaration et ses valeurs par défaut :
Déclaration de la variable param
/* Structure pour les parametres et leur valeurs par defauts */
SParam param = {10.0,1,-65.0,0.0,-6.0,0,3.0,
		L_AUCUN,-1,0,-0.02,0.2,1.0,0.01,47.0};

5.2. Une première version

La technique la plus facile dans le calcul d'ombre est d'utiliser un vecteur lumineux et de l'utiliser comme base de tous les algorithmes qui vont suivre.

Ensuite, ce qu'on fait c'est que pour chaque pixel on va calculer le coefficient de luminosité. Ce sera un nombre flottant entre 0 et 1 et on multipliera ce nombre par la couleur sans calcul d'ombre pour obtenir la couleur finale :
Calcul d'ombre
/* Calcul d'ombre */
r *= diff;
g *= diff;
b *= diff;
Tout ce qui reste à faire est le calcul de ce coefficient. Mais ce n'est pas compliqué! En effet, nous avons fixé la direction du rayon du soleil dans une structure et nous définirons ce vecteur comme étant (param.l_veci, param.l_vecj) (donc le rayon du soleil posséde une direction (param.l_veci, param.l_vecj)), donc si, pour un pixel (i,j), le pixel (i-param.l_veci,j-param.l_vecj) est plus élevé alors la luminosité du pixel (i,j) sera amoindrie (En effet, le pixel (i-param.l_veci,j-param.l_vecj) cachera un peu le pixel (i,j)).

En utilisant cette idée, on peut définir donc une première fonction Terrain_calcLightMap_Simple qui sera définie par :
Calcul d'ombre
double Terrain_calcLightMap_Simple(SDL_Surface *image, int i, int j, int maxi, int maxj)
{
        if( (i-param.l_veci>=0)&&(i-param.l_veci<maxi) && (j-param.l_vecj>=0) &&(j-param.l_vecj<maxj) )
                return 1.0 - (Terrain_GetHauteur(image, i-param.l_veci, j-param.l_vecj, maxi, maxj)
                           - Terrain_GetHauteur(image, i, j, maxi, maxj))/param.l_adouc;
        else
                return 1.0f;
}
Cette fonction commence bien sûr par une série de vérifications sur les valeurs des coefficients pour ne pas provoquer un débordement mémoire.

Comme on le remarque, on utilise la différence entre les deux hauteurs pour calculer le taux d'ombre. Si jamais cette différence est grande, alors res sera proche de 0, si jamais la différence est faible, le résultat sera proche de 1.

La valeur param.l_adouc permet de moduler la quantité d'ombre créée. Si ce nombre est petit, les zones seront très ombragées, sinon elles seront peu ombragées.


5.3. Les limitations de la 1ère méthode

La première méthode a un inconvénient : il est trop localisé, ce qui provoque des imperfections dans le calcul des ombres.

Défauts de la première méthode
Pour remédier à ce problème, à la place d'avoir un calcul si localisé, pour le calcul de l'ombre du pixel (i,j), on va utiliser la moyenne du coefficient d'ombre de chaque pixel avoisinant aussi. Ceci permettra d'éviter ce genre de défaut.

Puisque cette idée de faire une moyenne va revenir par la suite. Nous allons donc faire une fonction qui applique ce calcul de moyenne. Il faudra donc faire deux passes.

En effet, pour faire correctement les choses, on stocke dans un tableau assez grand (qu'on appellera lightmap) les coefficents d'ombre de chaque pixel. Ensuite, à l'aide d'un deuxième tableau temporaire, nous procéderons au calcul de chaque coefficient.

Pour ceux qui ne sont pas convaincus que deux passes sont nécessaires :

  1. Si vous vouliez le faire en une passe : calculer le nombre de fois que vous recalculer le coefficient du pixel (i,j);
  2. Si vous vouliez le faire directement sur le tableau lightmap sans passer par un deuxième tableau : pensez au fait que si vous changer la valeur du coefficient (i,j) alors vous allez utiliser cette moyenne dans le calcul des autres coefficients avoisinants; or, il aurait fallu utiliser l'ancienne valeur.
Voici donc le gros de la fonction qui fait le calcul des moyennes :
Calcul d'ombre Version 2
int Terrain_AppliquePatch(double **lightmap, int maxi, int maxj, int taille_patch)
{
        int i,j,k,l,cnt;
        double **tmplightmap;

        /* Allocation du tableau temporaire, fait en dynamique puisque le static peut planter :
         * taille du tableau si grand...
         */

        tmplightmap = malloc(maxi*sizeof(double*));
        if(tmplightmap==NULL)
                return 1;

        for(i=0;i<maxi;i++)
                {
                tmplightmap[i] = malloc(maxj*sizeof(double));
                if(tmplightmap[i]==NULL)
                        {
                        i--;
                        while(i>=0)
                                {
                                free(tmplightmap[i]);
                                }
                        free(tmplightmap);
                        return 1;
                        }
                }

        /* Calcul de moyenne */
        for(i=0;i<maxi;i++)
        {
                for(j=0;j<maxj;j++)
                {
                        /* Valeur par défaut */
                        tmplightmap[i][j] = 0.0;

                        /* Compteur pour savoir combien d'éléments ont été sommés */
                        cnt = 0;

                        for(k=i-taille_patch;k<=i+taille_patch;k++)
                        {
                                for(l=j-taille_patch;l<=j+taille_patch;l++)
                                {
                                        /* Si les coordonnées sont bonnes */
                                        if((k>=0)&&(l>=0)&&(k<maxi)&&(l<maxj))
                                        {
                                                tmplightmap[i][j] += lightmap[k][l];
                                                cnt++;
                                        }
                                }
                        }

                        /* Calcul de la moyenne */
                        if(cnt)
                                {
                                tmplightmap[i][j] /= cnt;
                                }
                        else
                                tmplightmap[i][j] = 1.0f;

                }
        }

    /* Recopie */
    for(i=0;i<maxi;i++)
        {
                for(j=0;j<maxj;j++)
                {
                lightmap[i][j] = tmplightmap[i][j];
                }
        }

    return 0;
}
Et voici le résultat :

Après l'application du filtre
Remarquez que c'est le dernier paramètre que nous utilisons pour définir la grandeur du filtre. Par contre, plus c'est grand, plus il y aura de calculs pour terminer la génération. De plus, d'un point de vue rendu, cela n'est pas forcément une bonne idée donc nous avons mis un filtre 4*4 (donc le dernier paramètre vaut 4).


5.4. Une 2ème solution : L dot N

L'avantage de la méthode précédente est la facilité d'utilisation de cette méthode. Mais elle demeure une approximation de la vraie solution qui est d'utiliser un produit scalaire entre la normal du point et le vecteur lumière.

En effet, le signe de ce produit scalaire nous dira si le pixel devrait être ombragé. Si le signe est positif, alors la normale et le vecteur lumière sont dans les mêmes directions. La lumière ne peut donc pas illuminer ce point.

Sinon, le produit est négatif, auquel cas, nous prendrons l'opposé de la valeur du produit scalaire comme coefficient de luminosité. Nous pouvons donc définir une nouvelle fonction Terrain_calcLightMap_LDOTN :
Prototype de la fonction Terrain_calcLightMap_LDOTN
double Terrain_calcLightMap_LDOTN(SDL_Surface *image, int i, int j, int maxi, int maxj);
Cette fonction vérifie si nous n'allons pas provoquer un débordement mémoire. Ensuite, il calcule une normale. Comment calculer la normal d'un point?

On utilise en fait les positions des points voisins. En effet, en utilisant les points (i-1,j-1), (i+1,j-1) et (i+1,j+1) on définit un triangle. Donc on pourra calculer un vecteur normal à partir de ces trois points.
Début du calcul L . N
        /* Complétons ces vecteurs
         * Premier vecteur sera le vecteur (i-1,j-1) vers (i+1,j-1)
         * Deuxième vecteur sera le vecteur (i+1,j-1) vers (i+1,j+1)
         */
        v1.x = 2; v1.y = 0;
        v1.z = Terrain_GetHauteur(image,i+1,j-1, maxi, maxj) - Terrain_GetHauteur(image,i-1,j-1, maxi, maxj);

        v2.x = 0; v2.y = 2;
        v2.z = Terrain_GetHauteur(image,i+1,j+1, maxi, maxj) - Terrain_GetHauteur(image,i+1,j-1, maxi, maxj);

        /* Normalise */
        Vecteur_Normalise(&v1);
        Vecteur_Normalise(&v2);

        /*On cherche la normale*/
        Vecteur_pVect(&v1,&v2,&n);
        /*On normalise la normale*/
        Vecteur_Normalise(&n);
En regardant le signe de z, on sait si le vecteur regarde vers le haut ou vers le bas. Vu que c'est par rapport au vecteur lumière, nous allons vérifier que ce vecteur regarde vers le haut.
Changement de sens pour le vecteur normal
        /* On vérifie que le vecteur est dans le bon sens */
        if(n.z<0)
                {
                n.x *=-1;
                n.y *=-1;
                n.z *=-1;
                }
Vous remarquez qu'on utilise toujours des vecteurs normaux. C'est conseillé de le faire et d'utiliser des facteurs d'ajustement par la suite.

Comme c'est fait ici :
Fin de la fonction
        /* On a la normale, on calcule maintenant L dot N */
        tmp =  Vecteur_ProdScal(&light, &n);

        if(tmp < 0)
                return -param.l_ldotnmultiple*tmp;
        else
                return 0.0f;
On voit bien que si tmp est négatif alors le pixel sera illuminé. Vu que nous voulons une valeur entre 0 et 1, nous multiplions la valeur par un ajustement. Cet ajustement dépendra du terrain et du vecteur lumière.

Comme pour la première méthode, il sera plus sage d'appliquer un filtre comme pour la partie précédente sur le calcul d'ombre.

Voici une image illustrant cette solution :

Deuxième méthode utilisant un filtre

5.5. Dernière méthode : le calcul des ombres

Cette dernière technique n'est qu'une extension de la dernière. En effet, nous allons utiliser le produit scalaire lorsqu'un calcul de coefficient sera nécessaire. La problématique de cette solution est donc de savoir quand est-ce qu'un tel calcul est nécessaire.

Nous partons toujours de la même hypothése : nous avons un vecteur lumière connu. Pour se simplifier la vie, mais ce n'est pas obligatoire, nous avons décidé que le soleil, étant tellement loin, posséde le même vecteur rayon lumineux pour tous les points du terrain.

Remarquons ici que je vais utiliser dans le vocabulaire le vecteur lumière, cela veut dire le vecteur se dirigeant vers la lumière donc c'est le vecteur opposé à celui donné dans la structure globale.

  • S'il existe une intersection entre le vecteur lumière partant du point qui nous intéresse et le reste du terrain, alors il ne peut pas avoir de rayon arrivant ici. On mettra donc ce point à 0;
  • S'il n'y a pas d'intersection, alors nous allons devoir utiliser la technique du produit scalaire.
Finalement, cette solution, bien que gourmande en ressources (vu le nombre de calculs à faire) n'est pas très difficile à mettre en place. Voici son implémentation :
Lanceur de rayon pour le coefficient de luminosité
double Terrain_calcLightMap_Ray(SDL_Surface *image, int i, int j, int maxi, int maxj, SVecteur *light)
{
        SPoint cur;
        float tmp;

        /*
         * Verification s'il y a une intersection avec le terrain, si
         * c'est le cas, il n'y aura pas de lumiere ici
         */

        /*
         * Point de depart, le point(i,j) avec son hauteur
         */
        tmp = i;
        tmp /= maxi;
        tmp *= image->h;

        cur.x = tmp;

        tmp = j;
        tmp /= maxj;
        tmp *= image->w;

        cur.y = tmp;
        cur.z = Terrain_GetHauteur(image,i,j,maxi,maxj);
Jusque là, rien de bien particulier, nous avons le point de départ avec son hauteur. Remarquez que nous avons de nouveau fait un changement de repére entre la position dans la texture à générer et l'image de niveaux. Ensuite vient le calcul de savoir s'il y a une intersection ou non.
Recherche d'intersection
        /* Tant qu'on est dans le terrain */
        while( (cur.x>=0) && (cur.y>=0) && (cur.x<image->h) && (cur.y<image->w) )
                {
                /* On recupere la hauteur courante */
                tmp = Terrain_GetHauteur(image,(int) cur.x, (int) cur.y, image->h, image->w);

                /* Si c'est au-dessus du maximum possible du terrain */
                if(cur.z>param.hautmax)
                        {
                        /* On sort, pas d'intersection possible */
                        break;
                        }

                /* Si le terrain est au-dessus du vecteur de lumiere, le terrain cache la lumiere */
                if(tmp > cur.z)
                        {
                        return 0.0;
                        }

                /* Sinon, on continue avec le vecteur de lumiere */
                cur.x += light->x;
                cur.y += light->y;
                cur.z += light->z;
                }

        /* Sinon pas d'intersection, on calcule la luminosite avec le calcul L dot N */
        return Terrain_calcLightMap_LDOTN(image,i,j,maxi,maxj);
}
Rien de bien particulier. Si le niveau du terrain est au-dessus du vecteur allant vers la lumière alors il y a une intersection. Sinon on peut calculer le coefficient de luminosité utilisant le produit scalaire de la deuxième méthode.

Voici une image montrant ce calcul d'ombre :

Dernière méthode

6. A propos du code source

Voici quelques remarques sur le code source présenté :

  • La souris permet de faire tourner et zoomer dans le monde;
  • La touche 'f' : passer du mode filaire au mode texture;
  • La touche 'l' : cycler dans les différents modes d'ombres (l'ordre étant : pas de lumière, avec le simple calcul naif, avec le simple calcul naif + filtre, le produit scalaire, produit scalaire + filtre, le calcul de rayon et le calcul de rayon + filtre)
  • La touche 'w' : permet de mettre ou enlever l'eau;
  • Les fléches droite et gauche : faire une rotation sur un autre angle...
Il a été porté à mon attention que ce bout de code n'est pas tout à fait portable. En effet, les touches présentées ici fonctionne avec certains claviers et sous certains systèmes d'exploitation. Avec un petit peu de chance, la prochaine version de SDL corrigera ce détail. Il est donc possible que la touche 'w' ne fonctionne pas pour vous mais que c'est la touche 'z' qui se chargera pour l'eau. Pour le rendre portable, il faudrait passer par les codes unicode. Mais cela sort du cadre de ce tutoriel.

La génération de ces textures peut prendre un certain temps, il faudra être patient. En principe, lorsque la création est faite, on pourrait créer un fichier image (bmp, png, ...) et l'utiliser directement. C'est donc un procédé de prétraitement.

Enfin, la texture d'herbe utilisée ici a été créée à l'aide de l'outil graphique Gimp et la texture de roches a été trouvée sur http://www.games-creator.com/. La texture de l'eau a été trouvée sur http://www.noctua-graphics.de/english/fraset_e.htm.

L'idée de l'algorithme pour le lancé de rayon pour le calcul des ombres a été tiré de cet article : Fast Computation of Terrain Shadow Maps par Mircea Marghidanu .


7. Conclusion

J'ai tenté de montrer comment générer une texture en utilisant des images de base et une image de niveaux. On peut calculer des coefficients de luminosité et même les ombres des objets.

L'avantage de cette solution permet d'avoir une seule texture et un rendu beaucoup plus rapide que de faire les mélanges entre les images de base à chaque rendu. Ensuite, des extensions existent encore pour faire encore mieux. Le choix des extensions dépendra de ce que vous cherchez dans votre générateur de terrain.


8. Remerciements

J'aimerais remercier Laurent Gomila pour son aide dans la rédaction de cet article et Miles pour son soutien et sa relecture!


9. Téléchargements

Voici le code source : TexTerrainGen.zip (1.21 Mo)

Le pdf : TexTerrainGen.pdf (720 Ko)


10. Poursuite de la génération de Terrain

khayyam90 a fait un très bon article sur la génération de terrain utilisant l'algorithme de Perlin. Nous avons mis ensemble un code source utilisant le même visualisateur mais utilisant son algorithme. Je vous conseille de lire cet article, il vous permettra de générer aléatoirement des terrains avec cet algorithme.


Valid XHTML 1.1!Valid CSS!

Les sources présentées sur cette page sont libres de droits, et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une oeuvre intellectuelle protégée par les droits d'auteurs. Copyright © 2006 Jean Christophe Beyler. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E de dommages et intérêts. Cette page est déposée à la SACD.

Vos questions techniques : forum d'entraide 2D - 3D - Jeux - Publiez vos articles, tutoriels et cours
et rejoignez-nous dans l'équipe de rédaction du club d'entraide des développeurs francophones
Nous contacter - Hébergement - Participez - Copyright © 2000-2009 www.developpez.com - Legal informations.