Developpez.com - 2D - 3D - Jeux
X

Choisissez d'abord la catégorieensuite la rubrique :


Initiation à la génération de lightmaps statiques en Java (LWJGL)

Publié le 1 octobre 2012

Par Nicolas Devère

 

Cet article présente une technique de calcul et d'affichage simple de textures de lightmap sur des objets (meshes) statiques composant une map de jeu typique.

       Version PDF   Version hors-ligne   Version eBooks
Viadeo Twitter Facebook Share on Google+        



I. Introduction
II. Définitions
III. Principe général
IV. Implémentation
IV-A. Les classes Triangle, Mesh et Map
IV-B. La classe Pixel
IV-C. La classe Grid
IV-D. Les lumières : l'interface Light et quelques implémentations
IV-E. La classe LightMap
IV-F. Retour à la classe Grid
IV-G. Utilisation du système
IV-H. Bonus : un algorithme d'intersection
V. Conclusion


I. Introduction

Qu'est-ce que les lightmaps ? Il s'agit d'une technique de rendu des lumières et ombres sous la forme de simples textures appliquées aux objets 3D.

Pourquoi les lightmaps ? Et bien d'une part les développeurs sont en recherche constante de principes d'illumination palliant aux limites des API d'affichage (comme les 8 lumières d'OpenGL), et d'autre part les plate-formes mobiles (comme Android), en plein essor, ne permettent pas (encore) les techniques les plus avancées. A la croisée de ces deux tendances les lightmaps semblent être actuellement un bon compromis entre réalisme et performance.

Le principal : à quoi cela ressemble-t-il ? Voici une scène basique, que nous utiliserons pour cet article, avec un éclairage simple :




Et la même scène « lightmappée » :




On peut constater que la technique des lightmaps calcule l'éclairage et les ombres, mais elle permet également d'émuler de nombreux types de lumières (couleur, mode de propagation, etc…), sans limite de complexité, ni perte de performance.


II. Définitions

Lightmap : Une lightmap telle que nous l'entendrons dans cet article est une texture associée à un mesh unique et comportant les informations d'éclairage et d'ombres portées sur celui-ci selon des lumières placées dans la map.

Mesh : Il s'agit d'une forme 3D composée de triangles et décrivant une portion de décor dans une map de jeu. Un mesh est associé à une unique texture de lightmap.

Map : Structure de données composée d'une liste de meshes de décor et disposant IMPERATIVEMENT d'une méthode de test d'intersection entre deux points, c'est-à-dire retournant vrai si le segment traverse le décor.

warning Remarque : les implémentations des structures de données 3D utilisées dans la suite de l'article (map, mesh, triangle) sont de simples exemples et peuvent être modifiées ou remplacées selon les besoins.

III. Principe général

Le mécanisme est simple : on prend chaque triangle d'un mesh, on l'inscrit dans une grille de pixels, et pour chacun d'eux on teste l'intersection avec une lumière. Si pas d'intersection on ajoute l'illumination au pixel. Ces pixels sont importants car ils représentent la structure de passage entre le monde 3D et la texture 2D. Ainsi, ils sont définis par une position 3D sur la map et une couleur RGB (modifiée par les lumières) qui sera ajoutée à la lightmap finale.

Exemple :


( Le triangle vert est circonscrit dans la grille rouge, dont chaque carreau est un futur pixel de la texture. )

Puis, lorsque nous avons toutes nos grilles on les " écrit " dans un grand buffer qui deviendra notre texture OpenGL.




Enfin, on calcule les UV de chaque triangle pour cette texture, et nous pouvons afficher notre beau mesh !


IV. Implémentation


IV-A. Les classes Triangle, Mesh et Map

Comme mentionné précédemment, ces classes sont hypothétiques et seront de simples supports à l'explication de notre technique. Ainsi, nous n'y mettrons que les fonctionnalités utiles pour cet article.

Triangle :

public class Triangle {

	/** Premier point */
	public Vec3 p1;

	/** Second point */
	public Vec3 p2;

	/** Troisième point */
	public Vec3 p3;

	/** UV du premier point */
	public float u1, v1;

	/** UV du second point */
	public float u2, v2;

	/** UV du troisième point */
	public float u3, v3;
}
Cette classe contient 3 points et leurs coordonnées de texture sur la future lightmap.

Mesh :

public class Mesh {

	// ID de la lightmap du mesh
	private int idTexture;

	// Triangles constituant le mesh
	private Triangle[] triangles;


	/** Assigne une texture de lightmap au mesh */
	public void setTexture(int arg) {
		idTexture = arg;
	}

	/** Retourne les triangles du mesh */
	public Triangle[] getTriangles() {
		return triangles;
	}

	/** Affiche le mesh */
	public void display() {

		GL11.glEnable(GL11.GL_TEXTURE_2D);
		GL11.glBindTexture(GL11.GL_TEXTURE_2D, idTexture);
		GL11.glBegin(GL11.GL_TRIANGLES);
		for (int i=0; i<triangles.length; i++) {
			GL11.glTexCoord2f(triangles[i].u1, triangles[i].v1;
			GL11.glVertex3f(triangles[i].p1.x, triangles[i].p1.y, triangles[i].p1.z);

			GL11.glTexCoord2f(triangles[i].u2, triangles[i].v2;
			GL11.glVertex3f(triangles[i].p2.x, triangles[i].p2.y, triangles[i].p2.z);

			GL11.glTexCoord2f(triangles[i].u3, triangles[i].v3;
			GL11.glVertex3f(triangles[i].p3.x, triangles[i].p3.y, triangles[i].p3.z);
		}
		GL11.glEnd();
		GL11.glDisable(GL11.GL_TEXTURE_2D);
	}

	/** Retourne si le segment spécifié traverse ce mesh */
	public boolean intersects(Vec3 point1, Vec3 point2) {
		// Implémentation à la charge du développeur
	}
}
Un mesh contient un tableau de triangles ainsi que l'identifiant de sa future texture de lightmap. Nous y avons adjoint une méthode d'affichage simple avec LWJGL (remplaçable par une implémentation plus performante : display lists ou autres VBO) et un test d'intersection dont l'implémentation est à la discretion du développeur.

Map :

public class Map {
	
	// Meshes présents dans la map
	private Mesh[] meshes;


	/** Retourne les meshes présents dans la map */
	public Mesh[] getMeshes() {
		return meshes;
	}

	/** Affiche la map */
	public void display() {

		for (int i=0; i<meshes.length; i++)
			meshes[i].display();
	}

	/** Retourne si le segment spécifié traverse un mesh de la map */
	public boolean intersects(Vec3 point1, Vec3 point2) {

		for (int i=0; i<meshes.length; i++)
			if (meshes[i].intersects(point1, point2))
				return true;

		return false;
	}
}
Cette classe, regroupant seulement un tableau de meshes, possède la fameuse méthode d'intersection ainsi qu'une méthode d'affichage.

Voilà, maintenant que nous avons nos structures de base, nous pouvons attaquer le vif du sujet !


IV-B. La classe Pixel

Commençons doucement avec cette classe très simple mais néanmoins indispensable car, comme expliqué précédemment, elle représente à la fois un pixel de notre texture et sa position correspondante dans le décor 3D. Elle contient donc à la fois une couleur et une position :

public class Pixel {

	/** Couleur rouge (entre 0 et 1) */
	public float r;

	/** Couleur verte (entre 0 et 1) */
	public float g;

	/** Couleur bleue (entre 0 et 1) */
	public float b;


	/** Coordonnée sur l'axe X */
	public float x;

	/** Coordonnée sur l'axe Y */
	public float y;

	/** Coordonnée sur l'axe Z */
	public float z;


	/** Indique si le pixel fait partie d'un triangle */
	public boolean valid;


	/** Constructeur */
	public Pixel() {

		r = g = b = 0f;
		x = y = z = 0f;
		valid = false;
	}
}
On notera la présence du paramètre "valid", il indiquera simplement si le pixel est dans un triangle ou non. En effet, comme nos triangles seront inscrit dans des grilles rectangulaires, certaines cases (représentant les pixels) seront forcément à l'extérieur (ce qui nous dispensera de les traiter), comme l'indique ce schéma :

On notera également que la position (x, y, z) du pixel représentera exactement le centre de sa case.


IV-C. La classe Grid

Attention, les choses vont un peu se corser car c'est ici que vont s'effectuer une bonne partie des traitements de notre système. Si vous n'êtes pas familier avec les changements de repère et autres coordonnées relatives, vous allez le devenir ! En effet, cette classe va représenter notre fameuse grille incluant un triangle. A ce titre, elle sera chargée de prendre un triangle 3D quelconque et d'en extraire un tableau (à 2 dimensions) de pixels ainsi que les coordonnées 2D des points du triangle dans cette grille (qui serviront plus tard à calculer les UV).

La première étape de ces traitements est d'extraire un repère orthonormé coplanaire au triangle. Pour ce faire, quelques conventions s'imposent : nous considérerons comme origine du repère le premier point du triangle (p1) et la direction Ox (horizontale) suivra le segment [p1, p2]. D'autre part, nous aurons besoin de la normale au triangle : celle-ci sera le produit vectoriel [p1, p2] x [p1, p3] normalisé, c'est à dire qu'elle fera face à l'observateur lorsque le triangle sera counter-clockwise. Ceci posé, notre repère est simple : le vecteur Ox est donc simplement [p1, p2] normalisé, et le vecteur Oy (vertical) est le produit vectoriel (normale x Ox). Ainsi, en clair, Oy "partira" toujours de p1 vers p3, les coordonnées verticales du triangle dans ce repère ne seront jamais négatives. Cela donnera typiquement :

Nous pouvons calculer ceci directement dans le constructeur de la classe, ce qui donne notre code de départ :

public class Grid {

	// Le triangle inclus dans la grille
	private Triangle t;

	// La normale au triangle
	private Vec3 n;


	// Origine du repère orthonormé 2D
	private Vec3 o;

	// Vecteur horizontal du repère 2D
	private Vec3 ox;

	// Vecteur vertical du repère 2D
	private Vec3 oy;


	// Coordonnées du premier point du triangle dans le repère 2D
	private float xp1, yp1;

	// Coordonnées du deuxième point du triangle dans le repère 2D
	private float xp2, yp2;

	// Coordonnées du troisième point du triangle dans le repère 2D
	private float xp3, yp3;


	// Taille du côté d'un pixel de la grille
	private float pixRes;

	// Tableau de pixels constituant la grille
	private Pixel[][] pix;

	// Hauteur du tableau de pixels (taille de la 1ere dimension)
	private int pixH;

	// Largeur du tableau de pixels (taille de la 2e dimension)
	private int pixW;

	// indice minimal du tableau en hauteur
	private pixHMin;

	// indice minimal du tableau en largeur
	private pixWMin;


	/**
	 * Constructeur.
	 * 
	 * @param triangle : Le triangle à inclure dans la grille
	 * @param pixelResolution : la taille d'un côté d'une case de la grille
	 */
	public Grid(Triangle triangle, float pixelResolution) {

		t = triangle;
		pixRes = pixelResolution;

		// On assigne le premier point du triangle à l'origine du repère
		o = t.p1.clone();

		// On calcule le vecteur (o, p2)
		Vec3 op2 = new Vec3(t.p2.x - o.x, t.p2.y - o.y, t.p2.z - o.z);

		// On calcule le vecteur (o, p3)
		Vec3 op3 = new Vec3(t.p3.x - o.x, t.p3.y - o.y, t.p3.z - o.z);

		// On calcule la normale au triangle
		n = MyMath.crossProduct(op2, op3);
		n.normalize();

		// On calcule le vecteur horizontal du repère (op2 normalisé)
		ox = op2.clone();
		ox.normalize();

		// On calcule le vecteur vertical du repère (produit vectoriel (n x ox))
		oy = MyMath.crossProduct(n, ox);
	}

}
Voilà, notre classe calcule strictement le repère 2D du triangle mais contient d'ors et déjà plusieurs attributs supplémentaires, dont le mystérieux paramètre pixelResolution. Celui-ci permet en fait de choisir la précision de notre lightmap : plus il est petit, plus nos grilles contiendront de cases, donc notre texture de pixels (nous le verrons par la suite).

De plus, nous avons inclus notre tableau de pixels (attribut pix) dont nous posons par convention que la première dimension représente les lignes et la deuxième les colonnes. De même, le poste pix[0][0] sera géométriquement le coin inférieur-gauche de notre grille. Les entiers pixH et pixW indiqueront respectivement le nombre de lignes et de colonnes de la grille. Quand à pixHMin et pixWMin, ils augurent encore quelques complications !

Nous reviendrons sur ces attributs ultérieurement, pour l'heure avec notre repère tout neuf nous pouvons calculer les coordonnées 2D du triangle par simples produits scalaires des points 3D sur les bons vecteurs du repère, ce qui donne :

xp1 = 0
yp1 = 0
(normal, p1 est l'origine du repère)

xp2 = op2 * ox (ce qui donne simplement la norme de op2)
yp2 = 0 (normal, op2 est confondue avec notre direction horizontale)

xp3 = op3 * ox
yp3 = op3 * oy

En schéma :

Et dans le code de notre constructeur :

public Grid(Triangle triangle, float pixelResolution) {

	...

	// On calcule le vecteur vertical du repère (produit vectoriel (n x ox))
	oy = MyMath.crossProduct(n, ox);

	// On calcule les coordonnées des points du triangle dans notre repère
	xp1 = 0f;
	yp1 = 0f;
	xp2 = MyMath.dotProduct(op2, ox);
	yp2 = 0f;
	xp3 = MyMath.dotProduct(op3, ox);
	yp3 = MyMath.dotProduct(op3, oy);
		
}
Maintenant que nous avons le repère 2D et les coordonnées du triangle dans celui-ci, nous pouvons nous attaquer à la construction de la grille de pixels proprement dite. Comme celle-ci doit inclure le triangle, il nous faut déterminer les coordonnées min et max de celui-ci. Ceci se fait facilement dans notre système : sur l'axe Oy, forcément yMin = yp1 (ou yp2) et yMax = yp3. Sur l'axe Ox, seuls 3 cas de figure peuvent se présenter :

Dans notre constructeur, nous aurons donc ceci :

public Grid(Triangle triangle, float pixelResolution) {

	...

	xp3 = MyMath.dotProduct(op3, ox);
	yp3 = MyMath.dotProduct(op3, oy);

	// On calcule les coordonnées xMin et xMax du triangle
	float xMin;
	if (xp1<xp3) xMin = xp1; else xMin = xp3;

	float xMax;
	if (xp2>xp3) xMax = xp2; else xMax = xp3;

	// On détermine les coordonnées yMin et yMax du triangle
	yMin = yp1;
	yMax = yp3;
		
}
Et c'est maintenant que nous devons parler de pixelResolution ainsi que du couple pixHMin / pixWMin. Ces variables vont nous permettre de déterminer et manipuler les indices du tableau de pixels selon la position du triangle. En effet ces indices (i, j) vont aller de 0 à n alors que, par exemple, dans le 2e cas du dernier schéma certaines cases sont "négatives" en x par rapport au repère. pixHMin et pixWMin vont donc indiquer la plus négative des cases sur les 2 axes afin de passer facilement de ces indices "géométriques" (ic, jc) aux indices "informatiques" (i, j) positifs ou nuls.

Quand à pixelResolution, il divisera bien sûr les coordonnées min et max du triangle pour, par un habile jeu d'arrondis, déterminer la taille du tableau :

pixHMin = arrondi_inférieur(yMin / pixelResolution)
pixWMin = arrondi_inférieur(xMin / pixelResolution)

pixH = arrondi_supérieur(yMin / pixelResolution) - pixHMin
pixW = arrondi_supérieur(xMin / pixelResolution) - pixWMin
(la taille totale du tableau est la taille des valeurs max moins la taille des valeurs min)

Ce qui donne dans le code :

public Grid(Triangle triangle, float pixelResolution) {

	...

	yMin = yp1;
	yMax = yp3;

	// On calcule les indices les plus petits de la grille réelle
	pixHMin = (int)Math.floor(yMin / pixRes);
	pixWMin = (int)Math.floor(xMin / pixRes);

	// On calcule la taille totale du tableau
	pixH = (int)Math.ceil(yMax / pixRes) - pixHMin;
	pixW = (int)Math.ceil(xMax / pixRes) - pixWMin;

}
Cette fois, nous avons tout ce qu'il faut pour déclarer notre tableau et calculer nos positions de pixel dans le monde 3D absolu. Ces positions seront espacés de pixelResolution et ordonnés suivant notre repère 2D, ce qui donne ce code :

public Grid(Triangle triangle, float pixelResolution) {

	...

	// On calcule la taille totale du tableau
	pixH = (int)Math.ceil(yMax / pixRes) - pixHMin;
	pixW = (int)Math.ceil(xMax / pixRes) - pixWMin;

	// Enfin, on déclare notre tableau de pixels !
	pix = new Pixel[pixH][pixW];

	// Boucles de remplissage du tableau

	int ic;  // Indice de ligne réelle de la case (peut être négatif)
	int jc;  // Indice de colonne réelle de la case (peut être négatif)

	int ip;  // Coordonnée Y de la case dans le repère 2D
	int jp;  // Coordonnée X de la case dans le repère 2D

	// On balaye les lignes en second
	for (int i=0; i<pixH; i++) {

		// On balaye les colonnes en premier
		for (int j=0; j<pixW; j++) {

			// Instantiation du pixel
			pix[i][j] = new Pixel();

			// On détermine les indices réels du pixel dans le repère 2D
			ic = i + pixHMin;
			jc = j + pixWMin;

			// On en déduit les coordonnées du pixel dans le repère 2D
			ip = (float)ic * pixRes;
			jp = (float)jc * pixRes;

			// Enfin, on calcule la position finale du pixel dans le monde 3D par projection sur notre repère 2D
			pix[i][j].x = (ox.x * jp) + (oy.x * ip) + o.x;
			pix[i][j].y = (ox.y * jp) + (oy.y * ip) + o.y;
			pix[i][j].z = (ox.z * jp) + (oy.z * ip) + o.z;
		}
	}
		
}
Ouf, nous avons l'ossature de notre constructeur ! C'est fini ? Hélas non... Actuellement nous avons ceci :

Alors que nous voudrions cela :

(subtile mais essentielle différence : l'origine du triangle est au milieu d'un pixel, pas dans un coin, ce qui est important pour avoir un calcul exact des UV par la suite)

Comment obtenir ça dans notre code ? Vous avez dix secondes...
En fait, c'est très simple : il suffit de corriger nos coordonnées 2D du triangle par la moitié de la taille d'un pixel.
Donc la portion de code concernée devient :

public Grid(Triangle triangle, float pixelResolution) {

	...

	// On calcule le vecteur vertical du repère (produit vectoriel (n x ox))
	oy = MyMath.crossProduct(n, ox);

	// On calcule les coordonnées des points du triangle dans notre repère (en les replaçant en milieu de pixel)
	float halfRes = pixRes * 0.5f;
	xp1 = 0f + halfRes;
	yp1 = 0f + halfRes;
	xp2 = MyMath.dotProduct(op2, ox) + halfRes;
	yp2 = 0f + halfRes;
	xp3 = MyMath.dotProduct(op3, ox) + halfRes;
	yp3 = MyMath.dotProduct(op3, oy) + halfRes;

	...
}
Ainsi la "discrétisation" de la grille par les pixels (par le jeu des arrondis) placera forcément le point p1 au milieu de l'un d'eux.
C'est fini ? Toujours pas ! Maintenant nous voulons obtenir ceci :

C'est à dire avoir une bordure d'un pixel tout autour du triangle. La raison en est que dans notre texture finale les grilles de pixels seront collées les unes aux autres, et si l'affichage est interpolé (ou utilise un filtrage bilinéaire) on pourrait "voir" le début d'une autre grille dans les coins ou les arêtes suivant les bords. Avec cette bordure, pour peu que l'on choisisse judicieusement les couleurs de ses pixels, on évite ces artefacts disgracieux. Pour ajouter ce bord, on joue tout simplement avec les min et max des indices du tableau, ce qui donne dans le code concerné :

public Grid(Triangle triangle, float pixelResolution) {

	...

	yMin = yp1;
	yMax = yp3;

	// On calcule les indices les plus petits de la grille réelle (en rajoutant une bordure de 1 pixel derrière)
	pixHMin = (int)Math.floor(yMin / pixRes) - 1;
	pixWMin = (int)Math.floor(xMin / pixRes) - 1;

	// On calcule la taille totale du tableau (en rajoutant une bordure de 1 pixel devant)
	pixH = (int)Math.ceil(yMax / pixRes) - pixHMin + 1;
	pixW = (int)Math.ceil(xMax / pixRes) - pixWMin + 1;

	...
}
Allez, une dernière modification : Elle concerne les coordonnées 3D finales des pixels. En l'état actuel ils sont "collés" au triangle qui les a généré, or on se rappelle que nous devrons tester l'intersection entre le monde et le segment (lumière-pixel), qui risque de toujours retourner vrai si on ne "décolle" pas légèrement les pixels du décor. Pour ce faire, nous allons utiliser astucieusement la normale au triangle. Le code de calcul de position 3D des pixels devient donc :

pix[i][j].x = (ox.x * jp) + (oy.x * ip) + (n.x * MyMath.EPSILON) + o.x;
pix[i][j].y = (ox.y * jp) + (oy.y * ip) + (n.y * MyMath.EPSILON) + o.y;
pix[i][j].z = (ox.z * jp) + (oy.z * ip) + (n.z * MyMath.EPSILON) + o.z;
Avec EPSILON de l'ordre, par exemple, de 0.001.

Maintenant la dernière ligne droite pour notre constructeur ! Il reste un dernier paramètre à déterminer pour chaque pixel : le fameux booléen valid qui indique si le pixel fait partie du triangle (donc s'il sera traité par les lumières). Nous devons obtenir ceci :

C'est à dire que chaque pixel dans la zone orange doit être marqué comme valid. Heureusement, notre configuration de grille permet d'obtenir cette information par quelques rapides calculs 2D. D'abord, nous pouvons constater, sur nos triangles, que le côté (p1, p3) est toujours "à gauche" du côté (p2, p3). Ainsi, en considérant la place des coins du pixel par rapport à ces segments on a notre booléen. En effet :

SI (bas-droite à droite de (p1, p3) OU haut-droite à droite de (p1, p3)) ET (bas-gauche à gauche de (p2, p3) OU haut-gauche à gauche de (p2, p3))
ALORS le pixel est valid

D'autre part, ce calcul serait faussé pour les pixels en-dessous de (p1, p2), mais cela ne concerne obligatoirement que la première ligne de notre grille, il suffit donc de ne pas la tester (ni la dernière ligne d'ailleurs, c'est toujours ça de gagné !).

Pour avoir la place d'un coin de pixel par rapport à un segment, on va procéder par produit scalaire : on extrait d'abord un vecteur orthogonal au segment par simple permutation de ses coordonnées x et y (et oui, on est en 2D) puis on teste le signe du produit scalaire de ce vecteur par le coin concerné.

Plaçons ce code dans une méthode à part pour plus de clarté :

private boolean isValid(float ip, float jp) {

	// On calcule la perpendiculaire à (p1, p3) par permutation des coordonnées
	float xn = -(yp3 - yp1);
	float yn =  (xp3 - xp1);

	// On calcule le vecteur (p1, origine_du_pixel)
	float io = ip - yp1;
	float jo = jp - xp1;

	// Produit scalaire avec coin bas-droite
	float dot1 = ((jo + pixRes) * xn) + (io * yn);

	// Produit scalaire avec coin haut-droite
	float dot2 = ((jo + pixRes) * xn) + ((io + pixRes) * yn);

	// On calcule la perpendiculaire à (p2, p3) par permutation des coordonnées
	xn =  (yp3 - yp2);
	yn = -(xp3 - xp2);

	// On calcule le vecteur (p2, origine_du_pixel)
	io = ip - yp2;
	jo = jp - xp2;

	// Produit scalaire avec coin bas-gauche (origine du pixel)
	float dot3 = (jo * xn) + (io * yn);

	// Produit scalaire avec coin haut-gauche
	float dot4 = (jo * xn) + ((io + pixRes) * yn);

	// Retour de la condition test
	return (dot1<=0f || dot2<=0f) && (dot3<=0f || dot4<=0f);
}
Cette méthode permet une première économie de traitements dans notre constructeur, en effet seuls les pixels valides auront besoin de coordonnées 3D. Notre boucle d'instantiation des pixels devient donc :

// On balaye les lignes en second
for (int i=0; i<pixH; i++) {

	// On balaye les colonnes en premier
	for (int j=0; j<pixW; j++) {

		// Instantiation du pixel
		pix[i][j] = new Pixel();

		// On détermine les indices réels du pixel dans le repère 2D
		ic = i + pixHMin;
		jc = j + pixWMin;

		// On en déduit les coordonnées du pixel dans le repère 2D
		ip = (float)ic * pixRes;
		jp = (float)jc * pixRes;

		// On teste si le pixel fait partie du triangle
		if (i!=0 && i!=pixH-1 && isValid(ip, jp) {

			// Enfin, on calcule la position finale du pixel dans le monde 3D par projection sur notre repère 2D
			pix[i][j].x = (ox.x * jp) + (oy.x * ip) + (n.x * MyMath.EPSILON) + o.x;
			pix[i][j].y = (ox.y * jp) + (oy.y * ip) + (n.y * MyMath.EPSILON) + o.y;
			pix[i][j].z = (ox.z * jp) + (oy.z * ip) + (n.z * MyMath.EPSILON) + o.z;

			// On marque le pixel comme valide
			pix[i][j].valid = true;
		}
	}
}
Cette fois ça y est ! On en a fini de la construction d'une grille de pixels. Ajoutons quelque getters et notre classe sera (momentanément) complète.

/** Retourne le triangle inclus dans la grille */
public Triangle getTriangle() {return t;}

/** Retourne la normale à la grille */
public Vec3 getNormal() {return n;}

/** Retourne le nombre de lignes de la grille */
public int getHeight() {return pixH;}

/** Retourne le nombre de colonnes de la grille */
public int getWidth() {return pixW;}

/** Retourne le tableau de pixels */
public Pixel[][] getPixels() {return pix;}

IV-D. Les lumières : l'interface Light et quelques implémentations

A présent que nous avons nos pixels, il est temps de les éclairer ! Rappelons le principe : au départ tous nos pixels sont noirs, et le rôle des lumières sera de rajouter certaines valeurs aux composantes RGB. Une tâche, une méthode : l'interface représentant nos lumières sera simplissime :

public interface Light {

	public void applyTo(Grid grid, Map map);
}
Cette méthode signifierait : la lumière s'applique à une grille de pixels selon une map. Ce code est volontairement minimal pour laisser au lecteur le loisir de programmer tous les types de lumières qu'il souhaite. Cependant, ne nous le cachons pas, le principal intérêt du système est de calculer les ombres portées, et cette fonctionnalité impliquera forcément des tests d'intersection sur la map entière (un peu à la manière d'un raytracing), c'est ce qui explique ce paramètre dans notre méthode.

A titre d'exemple, nous allons proposer deux implémentations. La première, très simple, simulera une lumière d'ambiance en ajoutant simplement une couleur aux pixels valides. Elle nous permettra de définir la structure minimale du code d'une lumière, ce sera la classe LightAmbient :

public class LightAmbient implements Light {

	// Couleur rouge (entre 0 et 1)
	private float r;

	// Couleur verte (entre 0 et 1)
	private float g;

	// Couleur bleue (entre 0 et 1)
	private float b;


	/** Constructeur */
	public LightAmbient(float red, float green, float blue) {

		r = red;
		g = green;
		b = blue;
	}


	/** Implémentation de l'interface Light */
	public void applyTo(Grid grid, Map map) {

		// On récupère les informations de la grille
		Pixel[]][] pix = grid.getPixels();
		int h = grid.getHeight();
		int w = grid.getWidth();

		// On balaye les pixels et on modifie les valides
		for (int i=0; i<h; i++) {
			for (int j=0; j<w; j++) {
				if (pix[i][j].valid) {
					pix[i][j].r += r; if (pix[i][j].r>1f) pix[i][j].r = 1f;
					pix[i][j].g += g; if (pix[i][j].g>1f) pix[i][j].g = 1f;
					pix[i][j].b += b; if (pix[i][j].b>1f) pix[i][j].b = 1f;
				}
			}
		}
	}
}
Pour éviter des effets indésirables sur la lightmap en cas de forte lumière, on note qu'on plafonne les composantes de couleur des pixels à 1. On pourrait objecter que cette opération peut se faire directement dans la classe Pixel, mais ce serait enlever de la liberté dans l'implémentation des lumières. Conceptuellement, ce sont bien à elles de manipuler les pixels, sans restriction, même s'il en coûte une éventuelle redondance de code entre les différentes implémentations.

On remarque également que le paramètre map est inutilisé, ce qui ne sera pas le dans notre deuxième exemple : la classe LightPoint. Celle-ci simulera une lumière diffuse ponctelle positionnée dans l'espace et irradiant unformément autour d'elle. Lumière diffuse signifie que l'éclairage des pixels sera conditionné par l'angle d'attaque avec la surface, et positionnée dans l'espace signifie qu'un faisceau pourra être stoppé par des obstacles, générant nos fameuses ombres. En voici le code :

public class LightPoint implements Light {

	// Couleur rouge (entre 0 et 1)
	private float r;

	// Couleur verte (entre 0 et 1)
	private float g;

	// Couleur bleue (entre 0 et 1)
	private float b;

	// Position de la lumière
	private Vec3 pos;


	/** Constructeur */
	public LightPoint(float red, float green, float blue, Vec3 position) {

		r = red;
		g = green;
		b = blue;

		pos = position;
	}


	/** Implémentation de l'interface Light */
	public void applyTo(Grid grid, Map map) {

		// Vecteur servant à manipuler la position des pixels
		Vec3 pixPos = new Vec3();

		// Vecteur représentant la direction d'un rayon de lumière
		Vec3 ray = new Vec3();

		// Force d'attaque d'un rayon sur un pixel
		float dot;

		// On récupère les informations de la grille
		Pixel[]][] pix = grid.getPixels();
		Vec3 normal = grid.getNormal();
		int h = grid.getHeight();
		int w = grid.getWidth();

		// On balaye les pixels et on modifie les valides
		for (int i=0; i<h; i++) {
			for (int j=0; j<w; j++) {
				if (pix[i][j].valid) {

					// On assigne la position du pixel au vecteur
					pixPos.set(pix[i][j].x, pix[i][j].y, pix[i][j].z);

					// On calcule la direction (normalisée) du rayon allant de la lumière au pixel
					ray.set(pixPos.x - pos.x, pixPos.y - pos.y, pixPos.z - pos.z);
					ray.normalize();

					// On calcule la force d'attaque sur le pixel
					dot = -MyMath.dotProduct(ray, normal);

					// Si négatif, la lumière est derrière la grille : on stoppe net
					if (dot<=0f) return;

					// On modifie la couleur (selon la force d'attaque) si pas d'obstacle entre la lumière et le pixel
					if (!map.intersects(pos, pixPos)) {
						pix[i][j].r += r * dot; if (pix[i][j].r>1f) pix[i][j].r = 1f;
						pix[i][j].g += g * dot; if (pix[i][j].g>1f) pix[i][j].g = 1f;
						pix[i][j].b += b * dot; if (pix[i][j].b>1f) pix[i][j].b = 1f;
					}
				}
			}
		}
	}
}
Voilà pour le principe de nos lumières. Suivant cette trame, le développeur pourra implémenter et sophistiquer ses lumières selon ses besoins. On peut imaginer par exemple des distances d'éclairage min et max produisant de jolis dégradés, mais aussi des lumiéres mono-directionnelles (pour simuler le soleil), des spots éclairant dans un cône défini, etc...


IV-E. La classe LightMap

Cette classe, la dernière de notre système, représente les textures de lightmaps elles-mêmes. Son rôle est de prendre un mesh, un ensemble de lumières et une map, et de fabriquer une matrice de composantes RGB qu'on transformera ensuite en texture OpenGL applicable au mesh. Mais attaquons directement le code avec les attributs et le constructeur :

public class LightMap {

	// Largeur initiale des textures
	private static final int DEFAULT_WIDTH = 1024;

	// Hauteur initiale des textures
	private static final int DEFAULT_HEIGHT = 256;

	// Liste de tableaux de composantes RGB composant la texture
	private List tex;

	// Largeur de la texture
	private int width;

	// Hauteur de la texture
	private int height;


	/** Constructeur */
	public LightMap() {

		tex = new Vector();
		width = 0;
		height = 0;
	}
}
Attardons-nous sur la liste tex : nous poserons par convention que ses éléments représenteront les lignes de la texture. D'autre part, la première ligne sera le bas de la texture. Ces lignes seront des tableaux de Vec3 (RGB) de taille fixe (donnée au départ par DEFAULT_WIDTH). La raison de cette disposition est que nous "écrirons" nos grilles de pixels de gauche à droite puis de bas en haut. On ne connait donc pas par avance la hauteur de la texture, nous devons pouvoir lui rajouter des lignes au besoin.

Revenons à notre code, avec l'ajout de sa méthode principale : la génération de la texture selon un mesh, des lumières, une map, et une taille de pixel. Cette méthode va commencer par fabriquer les objets Grid de tous les triangles du mesh puis leur appliquer les lumières, comme exposé ci-dessous :

public void generate(Mesh mesh, Light[] lights, Map map, float pixelResolution) {

	int i, j;

	// On commence par réinitialiser la texture
	tex.clear();

	// On initialise la largeur par défaut
	width = DEFAULT_WIDTH;

	// On déclare un tableau de grilles avec les triangles du mesh
	Triangle[] tris = mesh.getTriangles();
	int maxTris = tris.length;
	Grid[] grids = new Grid[maxTris];

	// On construit et traite les grilles pour chaque triangle
	for (i=0; i<maxTris; i++) {

		grids[i] = new Grid(tris[i], pixelResolution);

		// On agrandit au besoin la largeur de la texture selon celle des grilles
		while (grids[i].getWidth()>width)
			width *= 2;

		// On applique les lumières à la grille
		for (j=0; j<lights.length, j++)
			lights[j].applyTo(grids[i], map);

		// On post-traite les pixels
		grids[i].finalizePixels();
	}

}
Nous pouvons noter la présence de la mystérieuse méthode finalizePixels(). Nous détaillerons son rôle dans le prochain chapitre. En attendant, maintenant que nous avons nos grilles, nous pouvons les placer dans la texture. Pour cela, nous devons disposer de deux méthodes supplémentaires : une pour agrandir la texture vers le haut si elle est remplie et une pour placer une grille à une place spécifiée. Les voici :

/** Ajoute le nombre de lignes spécifié à la texture */
private void increase(int size) {

	for (int i=0; i<size; i++) {
		Vec3[] line = new Vec3[width];
		for (int j=0; j<width; j++) {
			line[j] = new Vec3();
		}
		tex.add(line);
	}

	height = tex.size();

}

/** Place la grille (coin bas-gauche) dans la texture aux coordonnées spécifiées */
private void fill(Grid grid, int x, int y) {

	Vec3[] line;
	Pixel[][] pixels = grid.getPixels();

	for (int i=0; i<grid.getHeight(); i++) {
		line = (Vec3[])tex.get(i + y);
		for (int j=0; j<grid.getWidth(); j++) {
			line[j + x].set(pixels[i][j].r, pixels[i][j].g, pixels[i][j].b);
		}
	}

}
Avec ces deux petites méthodes, nous pouvons attaquer l'algorithme de remplissage proprement dit. Sans plus de suspens, en voici le code dans la suite de la méthode generate :

public void generate(Mesh mesh, Light[] lights, Map map, float pixelResolution) {

	...

	// Position actuelle du curseur de remplissage
	int curX;
	int curY;

	// Position suivante du curseur de remplissage
	int nextX;
	int nextY;

	// On commence par construire une texture minimale
	increase(DEFAULT_HEIGHT);

	// On itère sur toutes les grilles du mesh
	for (i=0; i<grids.length; i++) {

		// On détermine l'épaisseur max de la ligne courante
		if (nextY<grids[i].getHeight()) {
			nextY = grids[i].getHeight();
			// Si le haut de la ligne dépasse la texture, on l'agrandit
			while (curY + nextY>=height)
				increase(height);
		}

		// On détermine la position de la grille suivante sur la ligne courante
		nextX = curX + grids[i].getWidth();

		// Si elle dépasse la texture, on revient à la ligne
		if (nextX>=width) {
			curX = 0;
			nextX = grids[i].getWidth();
			curY += nextY;
			nextY = grids[i].getHeight();
			// Si le haut de la ligne dépasse la texture, on l'agrandit
			while (curY + nextY>=height)
				increase(height);
		}

		// On place la grille courante à la place courante
		fill(grids[i], curX, curY);

		// On stocke dans la grille sa position sur la texture
		grids[i].applyMapCoord(curX, curY);

		// On avance dans la ligne courante
		curX = nextX;
	}

}
Cet algorithme fonctionne un peu à la manière d'une machine à écrire : on place les grilles de gauche à droite dans notre texture et, arrivé au bout, on revient à la ligne (plus haut) et on recommence. Il est à noter qu'il optimise peu la place dans la texture en pouvant laisser de grosses zones inutilisées (oui, il s'agit d'une initiation, d'ailleurs votre serviteur continue à chercher actuellement des solutions optimales en terme de placement et de performance !).

Notons également la présence de la méthode applyMapCoord(...) sur la classe Grid. Celle-ci informe simplement la grille courante de sa position sur la texture car c'est une information essentielle pour le calcul des UV du triangle associé (nous détaillerons ceci au prochain chapitre). D'ailleurs, maintenant que nous avons notre textures finale et sa taille globale, nous pouvons calculer ces UV pour chaque triangle. C'est ce que nous allons faire comme dernière opération de notre méthode generate :

public void generate(Mesh mesh, Light[] lights, Map map, float pixelResolution) {

	...

	// On calcule les UV de chaque triangle du mesh pour cette texture
	for (i=0; i<grids.length; i++)
		grids[i].applyUV(width, height);

}
Voilà, notre méthode de génération de la texture est complète ! Pour finir la classe, il ne nous manque plus que quelques getters :

/** Retourne la hauteur de la texture */
public int getHeight() {return height;}


/** Retourne la largeur de la texture */
public int getWidth() {return width;}


/** Retourne la texture sous forme d'un buffer lisible par LWJGL */
public ByteBuffer getAsByteBuffer() {

	Vec3[] line;
	ByteBuffer buffer = ByteBuffer.allocateDirect(width * height * 3).order(ByteOrder.nativeOrder());
	buffer.clear();

	for (int i=0; i<height; i++) {
		line = (Vec3[])tex.get(i);
		for (int j=0; j<width; j++) {
			buffer.put((byte)(line[j].x * 127f));
			buffer.put((byte)(line[j].y * 127f));
			buffer.put((byte)(line[j].z * 127f));
		}
	}

	buffer.rewind();
	return buffer;
}
Cette fois ça y est, nous avons tout le code de notre classe LightMap, notre système est presque complet à l'exception des 3 nouvelles méthodes de la classe Grid qui feront l'objet du prochain chapitre.


IV-F. Retour à la classe Grid

Attaquons sans détour par la méthode finalizePixels() : rappellez-vous, celle-ci est appellée après le traitement d'une grille par toutes les lumières dans la classe LightMap. Son rôle est similaire à la bordure d'un pixel autour de la grille : éviter les effets de bavement dus à l'interpolation de l'affichage, tels que ceux-ci :

pour cela il suffit finalement de colorier chaque pixel touchant un pixel valide avec la couleur de celui-ci, ce qui créera une bordure de "bons" pixels autour du triangle. Voici le code de cette méthode :

public void finalizePixels() {

	int i, j;

	for (i=1; i<pixH - 1; i++) {
		for (j=1; j<pixW - 1; j++) {

			if (pix[i][j].valid) {

				// On colorie les pixels à gauche du triangle
				if (!pix[i][j-1].valid) {
					pix[i][j-1].r = pix[i][j].r;
					pix[i][j-1].g = pix[i][j].g;
					pix[i][j-1].b = pix[i][j].b;
				}

				// On colorie les pixels à droite du triangle
				if (!pix[i][j+1].valid) {
					pix[i][j+1].r = pix[i][j].r;
					pix[i][j+1].g = pix[i][j].g;
					pix[i][j+1].b = pix[i][j].b;
				}

				// On colorie les pixels en bas du triangle
				if (!pix[i-1][j].valid) {
					pix[i-1][j].r = pix[i][j].r;
					pix[i-1][j].g = pix[i][j].g;
					pix[i-1][j].b = pix[i][j].b;
				}

				// On colorie les pixels en haut du triangle
				if (!pix[i+1][j].valid) {
					pix[i+1][j].r = pix[i][j].r;
					pix[i+1][j].g = pix[i][j].g;
					pix[i+1][j].b = pix[i][j].b;
				}

			}
		}
	}

}
Autre fonction, autre sujet : attaquons le calcul des UV des points du triangle avec la méthode applyMapCoord(...). Celle-ci, se souvient-on, sert à stocker dans la grille sa place dans la lightmap. A priori rien de compliqué mais nous allons en profiter pour calculer en fait la place du pixel origine du triangle. Pour ce faire nous procédons simplement comme ceci :

Ajoutons deux attributs à notre classe :

public class Grid {

	// Coordonnées de l'origine 2D dans la lightmap
	private int mapX;
	private int mapY;

	...

}
Puis notre méthode :

/** Applique la place de la grille dans la lightmap */
public void applyMapCoord(int x, int y) {

	mapX = x - pixWMin;
	mapY = y - pixHMin;

}
En effet, ce pixel origine dans la lightmap est simplement le pixel le plus "négatif" de la grille (coin bas-gauche) moins les coordonnées min des pixels. Maintenant que nous avons la place du triangle dans la lightmap, il nous suffit, pour en calculer les UV, de faire le rapport entre les coordonnées 2D de ce triangle et la taille totale de la texture. C'est le rôle de notre dernière méthode : applyUV(...).

/** Calcule les UV du triangle selon la taille totale de la lightmap (en pixels) */
public void applyUV(int totalWidth, int totalHeight) {

	// On calcule les coordonnées 2D réelles du pixel origine dans la lightmap
	float xo = mapX * pixRes;
	float yo = mapY * pixRes;

	// On calcule la taille 2D réelle de la lightmap
	float wt = totalWidth * pixRes;
	float ht = totalHeight * pixRes;

	// On fait le rapport entre la position des points du triangle et la taille de la lightmap
	t.u1 = (xo + xp1) / wt;
	t.v1 = (yo + yp1) / ht;

	t.u2 = (xo + xp2) / wt;
	t.v2 = (yo + yp2) / ht;

	t.u3 = (xo + xp3) / wt;
	t.v3 = (yo + yp3) / ht;
}

IV-G. Utilisation du système

Bonne nouvelle, notre système est enfin complet ! A présent pour lightmapper par exemple une map entière, il suffit d'itérer sur tous ses mesh et pour chacun d'eux calculer sa lightmap, envoyer celle-ci à LWJGL et enregistrer dans le mesh l'ID de cette texture. C'est ce que nous allons faire dans une méthode hypothétique applyLightMap(...) prenant en argument une map, des lumières et une résolution de pixel :

/** Applique des lightmaps à toute une map */
public void applyLightMap(Map map, Light[] lights, float pixelResolution) {

	int idTex;
	IntBuffer idBuf;
	LightMap lightmap;
	Mesh[] meshes = map.getMeshes();

	// On itère sur tous les meshes de la map
	for (int i=0; i<meshes.length; i++) {

		// On génère la lightmap pour le mesh
		lightmap = new LightMap();
		lightmap.generate(meshes[i], lights, map, pixelResolution);

		// On envoie la lightmap dans la carte graphique avec LWJGL
		idBuf = ByteBuffer.allocateDirect(4).order(ByteOrder.nativeOrder()).asIntBuffer();
		idBuf.clear();
		GL11.glGenTextures(idBuf);
		idTex = idBuf.get(0);

		GL11.glBindTexture(GL11.GL_TEXTURE_2D, idTex);
		GL11.glTexParameteri(GL11.GL_TEXTURE_2D, GL11.GL_TEXTURE_MIN_FILTER, GL11.GL_LINEAR);
		GL11.glTexParameteri(GL11.GL_TEXTURE_2D, GL11.GL_TEXTURE_MAG_FILTER, GL11.GL_LINEAR);
		GL11.glTexImage2D(GL11.GL_TEXTURE_2D, 0, GL11.GL_RGB8, lightmap.getWidth(), lightmap.getHeight(), 
						0, GL11.GL_RGB, GL11.GL_UNSIGNED_BYTE, lightmap.getAsByteBuffer());

		// On stocke l'ID de la lightmap dans le mesh pour affichage
		meshes[i].setTexture(idTex);
	}

}
Et nous n'avons plus qu'à afficher notre map avec sa méthode display().


IV-H. Bonus : un algorithme d'intersection

Comme nous ne sommes pas des sauvages, afin de proposer une implémentation entièrement testable, voici enfin un algorithme d'intersection d'un segment 3D sur un mesh. Attention, cet algorithme utilise la force brute en testant tous les triangles du mesh et est donc lent et non-optimisé. Son fonctionnement est le suivant : pour chaque triangle on calcule son plan, puis le point d'intersection entre celui-ci et le segment, si ce point existe et est dans le triangle on retourne vrai. En voici l'implémentation dans la classe Mesh :

/** Retourne si le segment spécifié traverse ce mesh */
public boolean intersects(Vec3 point1, Vec3 point2) {
	// Implémentation à la charge du développeur (mais voici un exemple)

	float segx = point2.x - point1.x;
	float segy = point2.y - point1.y;
	float segz = point2.z - point1.z;
	float d1, d2, dDiff, frac1, frac2;

	Vec3 norm;
	float d;

	Vec3 p1p2 = new Vec3();
	Vec3 p1p3 = new Vec3();
	Vec3 intersection = new Vec3();

	float uv, uu, vv;
	float wx, wy, wz;
	float wu, wv;
	float s, t;

	for (int i=0; i<triangles.length; i++) {

		// On calcule le plan du triangle
		p1p2.set(triangles[i].p2.x - triangles[i].p1.x, triangles[i].p2.y - triangles[i].p1.y, triangles[i].p2.z - triangles[i].p1.z);
		p1p3.set(triangles[i].p3.x - triangles[i].p1.x, triangles[i].p3.y - triangles[i].p1.y, triangles[i].p3.z - triangles[i].p1.z);
		norm = MyMath.crossProduct(p1p2, p1p3);
		norm.normalize();
		d = -( (norm.x * triangles[i].p1.x) + (norm.y * triangles[i].p1.y) + (norm.z * triangles[i].p1.z) );

		// On calcule les distances au plan des deux points du segment
		d1 = (point1.x * norm.x) + (point1.y * norm.y) + (point1.z * norm.z) + d;
		d2 = (point2.x * norm.x) + (point2.y * norm.y) + (point2.z * norm.z) + d;

		// Si points devant ou derrière le plan, triangle suivant
		if ((d1>0f && d2>0f) || (d1<0f && d2<0f))
			continue;

		dDiff = d1 - d2;

		// Si segment collé au plan, triangle suivant
		if (Math.abs(dDiff) < MyMath.EPSILON)
			continue;

		// On calcule le point d'intersection segment-plan
		frac = d1 / dDiff;
		intersection.set(point1.x + (segx * frac), point1.y + (segy * frac), point1.z + (segz * frac));

		// On calcule les variables paramétriques du point selon le triangle
		uv = (p1p2.x * p1p3.x) + (p1p2.y * p1p3.y) + (p1p2.z * p1p3.z);
		uu = (p1p2.x * p1p2.x) + (p1p2.y * p1p2.y) + (p1p2.z * p1p2.z);
		vv = (p1p3.x * p1p3.x) + (p1p3.y * p1p3.y) + (p1p3.z * p1p3.z);
		frac2 = 1f / ((uv * uv) - (uu * vv));

		wx = intersection.x - triangles[i].p1.x;
		wy = intersection.y - triangles[i].p1.y;
		wz = intersection.z - triangles[i].p1.z;
		wu = (wx * p1p2.x) + (wy * p1p2.y) + (wz * p1p2.z);
		wv = (wx * p1p3.x) + (wy * p1p3.y) + (wz * p1p3.z);

		s = ((uv * wv) - (vv * wu)) * frac2;
		t = ((uv * wu) - (uu * wv)) * frac2;

		// Si l'intersection est dans le triangle, on retourne vrai
		if (s>=0f && t>=0f && (s+t)<=1f)
			return true;
	}

	return false;
}

V. Conclusion

Cette initiation met en lumière (jeu de mot...), pour le développeur souhaitant générer des lightmaps, deux points critiques principaux dont la qualité de l'implémentation dépendent : d'une part une méthode d'intersection 3D dont la rapidité conditionnera directement les performances du système, et d'autre part un algorithme de placement des pixels dans la texture, le plus optimisé possible, sera le gage d'une utilisation mémoire minimale.



               Version PDF   Version hors-ligne   Version eBooks

Valid XHTML 1.0 TransitionalValid CSS!

Copyright © 2012 Nicolas Devère. 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'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts. Droits de diffusion permanents accordés à Developpez LLC.

Responsable bénévole de la rubrique 2D - 3D - Jeux : LittleWhite -