Théorie des collisions : Sols d'un monde 3D

Considérons une généralisation de la collision sur sol 2D courbe, que nous avons vu au-dessus, mais en 3D. Rappelez-vous, l'idée était de savoir, pour tout x, quel était le y associé avec une fonction y = f(x). À partir de là, on pouvait marcher sur une courbe.

L'idée est la même ici, savoir pour un x,y donné, quel est le z du sol.
Autrement dit de connaitre z = f(x,y).

Le problème, comme plus haut, est de définir cette fonction f(x,y). Afin d'avoir un contrôle des reliefs, nous allons définir cette fonction à partir d'une simple image. Et c'est cette image que nous appellerons Heigtmap.

Voici une Heightmap, à gauche, et le terrain qu'elle permettra de générer, à droite :

Source : http://en.wikipedia.org/wiki/Heightmap

La heightmap est une image (un BMP par exemple) en noir et blanc, avec des nuances de gris.
À partir de cette image, on reconstruit le sol 3D de droite.
Le concept est simple, pour un x,y donné, on regarde la couleur du pixel sur le BMP. Plus le pixel est blanc, plus l'altitude à cette position est élevée.

Regardez, on voit bien que les zones noires à gauche sont représentées par des creux à droite, et les zones blanches par des pics de montagne.

La couleur du pixel à un x,y donné est finalement le z attendu. Nous avons donc notre fonction z = f(x,y). C'est le BMP.

Beaucoup de jeux où vous pouvez marcher en extérieur dans un monde fait de relief. Beaucoup de jeux de voitures actuels sont faits avec un Heightmap.

Notez qu'on peut définir une altitude minimale (qui correspondra au pixel noir) et une altitude maximale (qui correspondra au pixel blanc) de notre choix.
Cela permet de faire des dénivelés plus ou moins importants, en fonction de nos besoins. Par exemple, à gauche, le sol est peu vallonné, alors qu'il l'est énormément dans le jeu de voiture (Monster Truck).

La fonction « simple » de collision sur une HeightMap n'est pas si compliquée. Nous ne définirons pas de structure Image, nous partirons juste du principe qu'on peut demander la valeur Z (la blancheur) d'un pixel x,y.

Nous calculerons donc d'abord, pour une AABB3D, le point en bas au centre, de la même façon que nous l'avions fait pour le chapitre sur le sol courbe. Nous considèrerons, pour notre AABB3D, l'axe z de bas en haut.

bool Collision(AABB3D box,Image Im) 
{ 
   float x = box.x + box.w/2; 
   float y = box.y + box.h/2; 
   float z = box.z + box.d; 
   int ix = round(x); 
   int iy = round(y); 
   int hauteursol = GetPixel(Image,ix,iy); 
   if (hauteursol>z) 
      return true; 
   else 
      return false; 
}

Cette fonction va prendre, pour un x (ou un y) donné, la valeur entière la plus proche (la fonction round) pour trouver l'altitude.

Cette partie requiert certaines connaissances mathématiques universitaires (ou fin de lycée).

III-D-1. Problème de discontinuité▲

La fonction que nous avons vu juste au-dessus présente un inconvénient majeur, elle nous génère un « escalier ». Cela ne se voit pas trop si le terrain est « serré », c'est-à-dire s'il y a peu de distance entre f(x,y) et f(x+1,y) (et de même pour y). Mais cela va faire de grandes cassures dans le cas contraire.
Voyons le schéma ci-dessous :

Ce que nous avons vu, c'est le cas A. Imaginez qu'on regarde une seule ligne de notre terrain, et de profil. Les points verts sont les points d'altitude, de coordonnées x= 0, 1, 2 et 3.
Les traits rouges sont les valeurs de la fonction entre 0 et 1, entre 1 et 2, et entre 2 et 3.

La fonction round() arrondit au nombre entier le plus proche, donc typiquement, la limite est au milieu, à 0.5, 1.5, 2.5
Et c'est la que nous avons une belle cassure. Et si nous faisons ainsi avancer notre personnage, quand il atteindra la limite, il va monter ou descendre d'un coup, ce qui pourra être bien moche.

III-D-2. Interpolation linéaire▲

III-D-3. Interpolation bilinéaire▲

bool Collision(AABB3D box,Image Im) 
{ 
   float x = box.x + box.w/2; 
   float y = box.y + box.h/2; 
   float z = box.z + box.d; 
   int ix = (int)(x); 
   int iy = (int)(y); 
   float dx = x - ix; 
   float dy = y - iy; 
   float hauteursol = ((1-dx)*GetPixel(Image,ix,iy) + dx*GetPixel(Image,ix+1,iy)) * (1-dy) 
                     +((1-dx)*GetPixel(Image,ix,iy+1) + dx*GetPixel(Image,ix+1,iy+1)) * dy; 
   if (hauteursol>z) 
      return true; 
   else 
      return false; 
}

III-D-4. Interpolation cubique et bicubique▲