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.
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.
|
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 {
public Vec3 p1;
public Vec3 p2;
public Vec3 p3;
public float u1, v1;
public float u2, v2;
public float u3, v3;
}
|
Cette classe contient 3 points et leurs coordonnées de texture sur la future lightmap.
Mesh :
public class Mesh {
private int idTexture;
private Triangle[] triangles;
public void setTexture (int arg) {
idTexture = arg;
}
public Triangle[] getTriangles () {
return triangles;
}
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);
}
public boolean intersects (Vec3 point1, Vec3 point2) {
}
}
|
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 {
private Mesh[] meshes;
public Mesh[] getMeshes () {
return meshes;
}
public void display () {
for (int i= 0 ; i< meshes.length; i+ + )
meshes[i].display ();
}
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 {
public float r;
public float g;
public float b;
public float x;
public float y;
public float z;
public boolean valid;
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 {
private Triangle t;
private Vec3 n;
private Vec3 o;
private Vec3 ox;
private Vec3 oy;
private float xp1, yp1;
private float xp2, yp2;
private float xp3, yp3;
private float pixRes;
private Pixel[][] pix;
private int pixH;
private int pixW;
private pixHMin;
private pixWMin;
@param
@param
public Grid (Triangle triangle, float pixelResolution) {
t = triangle;
pixRes = pixelResolution;
o = t.p1.clone ();
Vec3 op2 = new Vec3 (t.p2.x - o.x, t.p2.y - o.y, t.p2.z - o.z);
Vec3 op3 = new Vec3 (t.p3.x - o.x, t.p3.y - o.y, t.p3.z - o.z);
n = MyMath.crossProduct (op2, op3);
n.normalize ();
ox = op2.clone ();
ox.normalize ();
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) {
...
oy = MyMath.crossProduct (n, ox);
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);
float xMin;
if (xp1< xp3) xMin = xp1; else xMin = xp3;
float xMax;
if (xp2> xp3) xMax = xp2; else xMax = xp3;
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;
pixHMin = (int )Math.floor (yMin / pixRes);
pixWMin = (int )Math.floor (xMin / pixRes);
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) {
...
pixH = (int )Math.ceil (yMax / pixRes) - pixHMin;
pixW = (int )Math.ceil (xMax / pixRes) - pixWMin;
pix = new Pixel[pixH][pixW];
int ic;
int jc;
int ip;
int jp;
for (int i= 0 ; i< pixH; i+ + ) {
for (int j= 0 ; j< pixW; j+ + ) {
pix[i][j] = new Pixel ();
ic = i + pixHMin;
jc = j + pixWMin;
ip = (float )ic * pixRes;
jp = (float )jc * pixRes;
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) {
...
oy = MyMath.crossProduct (n, ox);
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;
pixHMin = (int )Math.floor (yMin / pixRes) - 1 ;
pixWMin = (int )Math.floor (xMin / pixRes) - 1 ;
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) {
float xn = - (yp3 - yp1);
float yn = (xp3 - xp1);
float io = ip - yp1;
float jo = jp - xp1;
float dot1 = ((jo + pixRes) * xn) + (io * yn);
float dot2 = ((jo + pixRes) * xn) + ((io + pixRes) * yn);
xn = (yp3 - yp2);
yn = - (xp3 - xp2);
io = ip - yp2;
jo = jp - xp2;
float dot3 = (jo * xn) + (io * yn);
float dot4 = (jo * xn) + ((io + pixRes) * yn);
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 :
for (int i= 0 ; i< pixH; i+ + ) {
for (int j= 0 ; j< pixW; j+ + ) {
pix[i][j] = new Pixel ();
ic = i + pixHMin;
jc = j + pixWMin;
ip = (float )ic * pixRes;
jp = (float )jc * pixRes;
if (i! = 0 & & i! = pixH- 1 & & isValid (ip, jp) {
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;
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.
public Triangle getTriangle () { return t;}
public Vec3 getNormal () { return n;}
public int getHeight () { return pixH;}
public int getWidth () { return pixW;}
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 {
private float r;
private float g;
private float b;
public LightAmbient (float red, float green, float blue) {
r = red;
g = green;
b = blue;
}
public void applyTo (Grid grid, Map map) {
Pixel[]][] pix = grid.getPixels ();
int h = grid.getHeight ();
int w = grid.getWidth ();
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 {
private float r;
private float g;
private float b;
private Vec3 pos;
public LightPoint (float red, float green, float blue, Vec3 position) {
r = red;
g = green;
b = blue;
pos = position;
}
public void applyTo (Grid grid, Map map) {
Vec3 pixPos = new Vec3 ();
Vec3 ray = new Vec3 ();
float dot;
Pixel[]][] pix = grid.getPixels ();
Vec3 normal = grid.getNormal ();
int h = grid.getHeight ();
int w = grid.getWidth ();
for (int i= 0 ; i< h; i+ + ) {
for (int j= 0 ; j< w; j+ + ) {
if (pix[i][j].valid) {
pixPos.set (pix[i][j].x, pix[i][j].y, pix[i][j].z);
ray.set (pixPos.x - pos.x, pixPos.y - pos.y, pixPos.z - pos.z);
ray.normalize ();
dot = - MyMath.dotProduct (ray, normal);
if (dot<= 0f ) return ;
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 {
private static final int DEFAULT_WIDTH = 1024 ;
private static final int DEFAULT_HEIGHT = 256 ;
private List tex;
private int width;
private int height;
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;
tex.clear ();
width = DEFAULT_WIDTH;
Triangle[] tris = mesh.getTriangles ();
int maxTris = tris.length;
Grid[] grids = new Grid[maxTris];
for (i= 0 ; i< maxTris; i+ + ) {
grids[i] = new Grid (tris[i], pixelResolution);
while (grids[i].getWidth ()> width)
width * = 2 ;
for (j= 0 ; j< lights.length, j+ + )
lights[j].applyTo (grids[i], map);
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 :
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 ();
}
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) {
...
int curX;
int curY;
int nextX;
int nextY;
increase (DEFAULT_HEIGHT);
for (i= 0 ; i< grids.length; i+ + ) {
if (nextY< grids[i].getHeight ()) {
nextY = grids[i].getHeight ();
while (curY + nextY>= height)
increase (height);
}
nextX = curX + grids[i].getWidth ();
if (nextX>= width) {
curX = 0 ;
nextX = grids[i].getWidth ();
curY + = nextY;
nextY = grids[i].getHeight ();
while (curY + nextY>= height)
increase (height);
}
fill (grids[i], curX, curY);
grids[i].applyMapCoord (curX, curY);
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) {
...
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 :
public int getHeight () { return height;}
public int getWidth () { return width;}
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) {
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;
}
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;
}
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;
}
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 {
private int mapX;
private int mapY;
...
}
|
Puis notre méthode :
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(...).
public void applyUV (int totalWidth, int totalHeight) {
float xo = mapX * pixRes;
float yo = mapY * pixRes;
float wt = totalWidth * pixRes;
float ht = totalHeight * pixRes;
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 :
public void applyLightMap (Map map, Light[] lights, float pixelResolution) {
int idTex;
IntBuffer idBuf;
LightMap lightmap;
Mesh[] meshes = map.getMeshes ();
for (int i= 0 ; i< meshes.length; i+ + ) {
lightmap = new LightMap ();
lightmap.generate (meshes[i], lights, map, pixelResolution);
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 ());
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 :
public boolean intersects (Vec3 point1, Vec3 point2) {
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+ + ) {
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) );
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;
if ((d1> 0f & & d2> 0f ) | | (d1< 0f & & d2< 0f ))
continue ;
dDiff = d1 - d2;
if (Math.abs (dDiff) < MyMath.EPSILON)
continue ;
frac = d1 / dDiff;
intersection.set (point1.x + (segx * frac), point1.y + (segy * frac), point1.z + (segz * frac));
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;
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.
Copyright © 2012 Nicolas Devère.
Aucune reproduction, même partielle, ne peut être faite de ce site ni 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.