True Decals

(Les décals)

 

Par Mathieu Guillame-Bert

http://www.achoum.fr.st

mathieu.guillame-bert@wanadoo.fr

 

Introduction

 

Dans les jeux vidéos 3D vous pouvez voir ce qu’on appelle des décals (ou décalcomanies). Ce sont le plus souvent les impactes de balles, les traces d’explosions, les taches de sang ou même pour certaines projections d’éclairage. Elles sont très importantes car elles ajoutent beaucoup de réalisme aux jeux. Dans ce tutorial, je vais donc vous expliquer comment créer des décals.

 

J’ai fait cet article avec mes connaissances actuelles (Premières années de Prépa), il y aura donc sûrement des améliorations à apporter aussi bien au niveau de l’algorithme que de la théorie. Don si vous voyer une quelconque améliorations n’hésité pas à m’écrire.

 

 

Exemples :

 

Half Life

 

Doom 3

 

 

 

Mise en place

 

Dans la suite de cet article, vous serez appelez a faire appelle a des notions de géométrie dans l’espace. Je vous conseil donc, si vous ne vous rappelez plus de la définition d’un produit vectoriel ou d’une normale de retourner jeter un œil sur vos cours de mathsJ.

 

Il existe deux moyens de faire des décals.

 

Un premier très simple mais très limité. Il consiste simplement à « collé » un polygone sur un mur. En donnant au polygone la même normal que le mur. Cependant si le décals est appliquer sur un bords du mur, celui ci va « dépasser » et donc créé un bug graphique. Cette méthode n’est donc utilisable que pour de petits décals comme de petites impactes.

 

Fig 1

Fig 2

 

 

La seconde méthode consiste a créé une enveloppe du murs. Donc si le décals est appliquer sur un bords du mur, celui ci va épouser la forme du murs et donc créer un effet parfait.

 

Voici donc ce que nous obtiendrons à la fin de cet article :

 

 

Le décal

Le résultat (projection sur une sphère)

 

 

Pour information, j’ai utilisé sur l’exemple une image TGA 256x256x32.

 

Tous au long de ce tutorial j’utiliserai la structure CVector3. C’est une classe de vecteur toute simple avec le produit scalaire, le produit vectoriel, addition, multiplication et magnitude.

Tout autre structure de vecteur peut faire l’affaire. Cependant si vous n’en avez pas encore, vous pouvez télécharger CVector3 ici (Télécharger).

Vous airez aussi besoin de la structure suivante :

 

struct CVector2

      {

      float x, y;

      };

 

 

Vous remarquez que je ne compare jamais une float à un nombre entier. Je préfère rajouter 0.05 pour prendre en compte l’erreur de précision des float.

 

J’utiliserai aussi les fonctions suivantes :

-         Signe: donne le signe d’un nombre à virgule flottant

-         NormalizeVector : Normalise un vecteur (lui donne une magnitude de 1)

-         Normalise : donne la normale d’une face.

 

 

Voici leur code :

 

int Signe(float a)

      {

      if(a>0)return 1;

      if(a<0)return -1;

      return 0;

      }

 

void NormalizeVector(CVector3 *v)

      {

      float norm = v->Magnitude();

      v->x /= norm;

      v->y /= norm;

      v->z /= norm;

      }

 

CVector3 Normalise(CVector3 *Pt1,CVector3 *Pt2,CVector3 *Pt3)

      {

      CVector3 Normal;

      float Ax = Pt3->x - Pt2->x;

      float Ay = Pt3->y - Pt2->y;

      float Az = Pt3->z - Pt2->z;

 

      float Bx = Pt1->x - Pt2->x;

      float By = Pt1->y - Pt2->y;

      float Bz = Pt1->z - Pt2->z;

 

      float x = Ay * Bz - By * Az;

      float y = Az * Bx - Bz * Ax;

      float z = Ax * By - Bx * Ay;

 

      float norm = (float)sqrt(x*x+y*y+z*z);

 

      Normal.x = x / norm;

      Normal.y = y / norm;

      Normal.z = z / norm;

      return Normal;

      }

 

 

Théorie et Code

 

Avant de nous lancer dans le code pure, je vais vous présenter le principe utiliser.

Celui ci ce décompose en cinq étapes :

         - La détermination le point de collision directe

- La création d’un volume de projection

- La recherche des points de coupures

- L’organisation des points de coupures

- Le calcule des coordonnées de texture.

 

Ces opérations sera répéter sur toutes les faces de notre monde.

 

 

La première chose à faire est donc de déterminer le point de collision direct. Le décal que nous allons créer est calculé à partir d’un point (Vecteur), d’une direction (Vecteur)(et éventuellement d’une échelle).

Le point de collision direct sera le point d’intersection de la direction avec le monde. Il faut donc fait un test de collision entre la direction et chaque face du monde (collision de type Rayon/Face). Voici la fonction en question :

 

 

float Collision(CVector3 Pt1,CVector3 Pt2,CVector3 Pt3,CVector3 Pto,CVector3 V,CVector3 pNormal)

      {

      CVector3 R;

      CVector3 R2;

      float p1;

      CVector3 d;

 

      d = (Pt1) - (Pto);

 

      float Scal2 = (V) * (pNormal);

 

      float t = d*(pNormal)/Scal2;

 

      if(t<=0)

      return -1;

      if(t>=1)

      return -1;

 

      R2 = (V) * t + (Pto);

 

      R = R2 - (Pt1);

 

      p1 = R*((Pt2-Pt1)^(pNormal));

 

      if(p1<0)

            {

            R = R2 - (Pt2);

            p1 = R*(((Pt3)-(Pt2))^(pNormal));

            if(p1<0)

                  {

                  R = R2 - (Pt3);

                  p1 = R*(((Pt1)-(Pt3))^(pNormal));

                  if(p1<0) return t;

                  }

            }

      return -1;

         }

 

float CollisionAutoNorm(CVector3 Pt1,CVector3 Pt2,CVector3 Pt3,CVector3 Pto,CVector3 V)

     {

     Return Collision(Pt1, Pt2, Pt3, Pto, V, Normalise(Pt1, Pt2, Pt3));

     }

 

 

Les arguments sont les trois sommets d’une face, le point de départ, la direction et la normal de la face. Cette fonction renvois un nombre à virgule flottant. Si celui-ci est compris entre 0 et 1, il y a collision, si non rien…

 

Au final vous devrez garder la face qui retourne le nombre le plus petit (compris entre 0 et 1). Voici un exemple :

 

float DistMin = 2;

CVector3 Normal;

float a;

unsigned int Bonneface;

for(unsigned int j=0; j < pMonde->NDFace; j++)

{

 

a = Collision(pMonde->pVector[pMonde->pFace[j].vertIndex[0]],

              pMonde->pVector[pMonde->pFace[j].vertIndex[1]],

              pMonde->pVector[pMonde->pFace[j].vertIndex[2]],

              Position,Direction);

 

if(a>=0)

if(a<=1)

if(a<DistMin)

     {

     DistMin = a;

     Bonneface = j;

     }

}

Normal = Normalise(pMonde->pVector[pMonde->pFace[Bonneface].vertIndex[0]],

                   pMonde->pVector[pMonde->pFace[Bonneface].vertIndex[1]],

                   pMonde->pVector[pMonde->pFace[Bonneface].vertIndex[2]]) ;

 

if(DistMin==2) return; //pas de collisions

 

CVector3 PointDirect = Position + Direction * DistMin; //Point direct

//la normale de la face de collision est Normal

 

 

Fig 3

 

Nous avons maintenant le point direct.

Nous allons chercher le volume de projection. Celui-ci est un pavé orienté selon la normale de la face de collision. Sa base est carré de coté « Size * 2» et de hauteur « Size * SizeLong * 2 ». Son centre est le point direct Il nous faut définir un vecteur de référence indiquant la direction d’un des coté (Le « haut » du décal (Top)).   

 

Voici l’équation de ces 8 sommets :

 

 

float SizeLong = 2; //ces deux valeurs sont arbitraire

float Size = 1;

 

 

CVector3 Top;

Top.Set(0,-1,0.5); // La valeur de Top est aussi arbitraire

 

CVector3 D1,D2,D3,D4,F1,F2,F3,F4; // les 8 sommets

 

float SizeLong = 2;

float Size = 1;

 

CVector3 Cote = Top^Normal;

 

if(Cote.IsNull())

      {

      Top.x = Normal.y;

      Top.y = Normal.z;

      Top.z = Normal.x;

      Cote = Top^Normal;

      }

 

NormalizeVector(&Cote);

Top = (Normal^Cote)*Size;

Cote *= Size;

 

D1 = point - Cote - Top + Size*Normal*SizeLong;

D2 = point + Cote + Top + Size*Normal*SizeLong;

D3 = point - Cote + Top + Size*Normal*SizeLong;

D4 = point + Cote - Top + Size*Normal*SizeLong;

 

     

F1 = D1 - SizeLong*Size*2*Normal;

F2 = D2 - SizeLong*Size*2*Normal;

F3 = D3 - SizeLong*Size*2*Normal;

F4 = D4 - SizeLong*Size*2*Normal;

 

Voici un schéma pour clarifier les idées :

 

Fig 4

 

 

Il nous faut maintenant chercher les points de coupures. J’entends par point de coupure :

-         Tous points d’intersections entre les faces du monde et les arrêtes du volume de projection

-         Tous points d’intersection entre les faces du volume de projection et les arrêtes du monde

-         Tous sommets du monde contenu dans le volume de projection

 

Ces points seront rangés dans un tableau. Nous allons pour ça utiliser la fonction Collision. Pour trouver les points du monde appartenants au volume, ont effectue un test de collision partant de chaque sommet du monde avec pour direction la normale de la face multiplier par SizeLong*2.

 

La valeur MAX_DECALS_PART est le nombre maximum de point de coupure sur une face donnée. Si vous utiliser un monde très complexe ou des décals très grands vous serez sûrement amené à l’augmenter.

 

Voici le code :

 

#define MAX_DECALS_PART 30

 

CVector3 ptColl[MAX_DECALS_PART];

CVector3 p1,p2;

CVector3 ps[3];

float a;         

            Int CurPoint = 0;

 

            for(k=0;k<3;k++)

                  ps[k] = pMonde ->pVector[pMonde ->pFace[j].vertIndex[k]];

 

            CVector3 Normal2 = Normalise(&ps[0],&ps[1],&ps[2]);

 

            for(k=0;k<3;k++)

                  {

                  p1 = ps[k];

                  p2 = ps[(k+1)%3];

     

                  a = CollisionAutoNorm(D1,F1,F4,p1,p2-p1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = p1 + (p2-p1)*a;

 

                  a = CollisionAutoNorm(D1,F4,D4,p1,p2-p1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = p1 + (p2-p1)*a;

 

                  a = CollisionAutoNorm(D4,F4,F2,p1,p2-p1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = p1 + (p2-p1)*a;

 

                  a = CollisionAutoNorm(D4,F2,D2,p1,p2-p1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = p1 + (p2-p1)*a;

 

                  a = CollisionAutoNorm(D2,F2,F3,p1,p2-p1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = p1 + (p2-p1)*a;

 

                  a = CollisionAutoNorm(D2,F3,D3,p1,p2-p1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = p1 + (p2-p1)*a;

                 

                  a = CollisionAutoNorm(D3,F3,F1,p1,p2-p1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = p1 + (p2-p1)*a;

 

                  a = CollisionAutoNorm(D3,F1,D1,p1,p2-p1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = p1 + (p2-p1)*a;

 

 

 

                  a = CollisionAutoNorm(D1,D2,D3,p1,p2-p1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = p1 + (p2-p1)*a;

                  a = CollisionAutoNorm(D1,D4,D2,p1,p2-p1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = p1 + (p2-p1)*a;

 

                  a = CollisionAutoNorm(F1,F3,F2,p1,p2-p1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = p1 + (p2-p1)*a;

                  a = CollisionAutoNorm(F1,F2,F4,p1,p2-p1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = p1 + (p2-p1)*a;

                  }

 

 

            for(k=0;k<3;k++)

                  {

                  a = CollisionAutoNorm(D1,D2,D3,ps[k],Normal*SizeLong*2);

                        if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = ps[k];

                        else

                        {

                        a = CollisionAutoNorm(D1,D4,D2,ps[k],Normal*SizeLong*2);

                        if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = ps[k];

                        }

                  }

 

 

                  a = CollisionAutoNorm(ps[0],ps[1],ps[2],D1,D4-D1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = D1 + (D4-D1)*a;

 

                  a = CollisionAutoNorm(ps[0],ps[1],ps[2],D4,D2-D4);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = D4 + (D2-D4)*a;

 

                  a = CollisionAutoNorm(ps[0],ps[1],ps[2],D2,D3-D2);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = D2 + (D3-D2)*a;

 

                  a = CollisionAutoNorm(ps[0],ps[1],ps[2],D3,D1-D3);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = D3 + (D1-D3)*a;

 

                 

                  a = CollisionAutoNorm(ps[0],ps[1],ps[2],F1,F4-F1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = F1 + (F4-F1)*a;

 

                  a = CollisionAutoNorm(ps[0],ps[1],ps[2],F4,F2-F4);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = F4 + (F2-F4)*a;

 

                  a = CollisionAutoNorm(ps[0],ps[1],ps[2],F2,F3-F2);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = F2 + (F3-F2)*a;

 

                  a = CollisionAutoNorm(ps[0],ps[1],ps[2],F3,F1-F3);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = F3 + (F1-F3)*a;

 

 

                  a = CollisionAutoNorm(ps[0],ps[1],ps[2],D1,F1-D1);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = D1 + (F1-D1)*a;

                 

                  a = CollisionAutoNorm(ps[0],ps[1],ps[2],D2,F2-D2);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = D2 + (F2-D2)*a;

 

                  a = CollisionAutoNorm(ps[0],ps[1],ps[2],D3,F3-D3);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = D3 + (F3-D3)*a;

 

                  a = CollisionAutoNorm(ps[0],ps[1],ps[2],D4,F4-D4);

                  if((a>-0.05)&&(a<1.05))

                        ptColl[CurPoint++] = D4 + (F4-D4)*a;

 

 

 

Voici donc les points de coupures obtenus pour la première face:

Fig 5

 

Les points de coupures, au nombre de CurPoint, sont rangés dans ptColl.

Si le nombre de point (CurPoint) est de zéro c’est qu’il n’y à pas de décal sur cette face. Dans ce cas là ont passe directement à la face suivante. Si non, on continue.

 

Notre but maintenant est de créer une face entre ces points. Il nous faut donc les ordonne. En effet nous utiliserons le paramètre GL_TRIANGLE_FAN pour l’affichage en OpenGL. Voici ça répartition :

 

Fig 6

 

Il faut donc organiser les points pour que l’affichage ce face correctement. Par exemple si, sur la figure 6 vous inversez les point 3 et 5, le dessin va devenir :

 

Fig 7

 

Nous allons pour ça créer une fonction qui permettra de comparer deux points 2 à deux et de retourner celui qui doit être afficher en premier :

bool AngleClass(CVector3 p1,CVector3 p2,CVector3 Normal,CVector3 Cote,CVector3 Top);

Le tri ce fera de cette façon :

 

int l;

int l2;

CVector3 Swap;

for(l=0;l<CurPoint;l++)

for(l2=l+1;l2<CurPoint;l2++)

     {

     if(AngleClass(ptColl[l2]-ptColl[0],ptColl[l]-ptColl[0],Normal2,Cote2/Size,Top2/Size))

          {

          Swap = ptColl[l2];

          ptColl[l2] = ptColl[l];

          ptColl[l] = Swap;

          }

     }

 

Maintenant attaquons nous à la fonction AngleClass :

Celle ci calcule la classe de chaque vecteur par rapport au plan de la face en cour d’analyse grâce à la fonction  ClassVect (que nous définirons plus tard):

 

Fig 8 : Classe d’un vecteur

 

 

Si la classe du premier vecteur est plus grande ce celle du second, nous retournons false. Si elle est plus petite, nous retournons true. Si elle est égale, nous effectuons un test de direction :

 

bool AngleClass(CVector3 p1,CVector3 p2,CVector3 Normal,CVector3 Ref,CVector3 Top)

      {

      NormalizeVector(&p1);

      NormalizeVector(&p2);

      int Classe1 = ClassVect(p1,Ref,Top);

      int Classe2 = ClassVect(p1,Ref,Top);

      if(Classe1<Classe2)

            return true;

     

      else if(Classe1>Classe2)

            return false;

 

      else //if(Classe1==Classe2)

            {

            if(((p1^p2)*Normal)>0)

                  return true;

            else

                  return false;

            }

      }

 

La fonction ClassVect est très simple :

int ClassVect(CVector3 p,CVector3 Ref,CVector3 Top)

      {

      int SigneX = Signe(p*Ref);

      int SigneY = Signe(p*Top);

      if (SigneX<-0.05)

            {

            if(SigneY>0.05)

                  return 3;

            else if(SigneY<-0.05)

                  return 5;

            else //(SigneY==0)

                  return 4;

            }

      else if(SigneX>0.05)

            {

            if(SigneY>0.05)

                  return 1;

            else if(SigneY<-0.05)

                  return 7;

            else //(SigneY==0)

                  return 0;

            }

      else

            {

            if(SigneY>0.05)

                  return 2;

            else if(SigneY<-0.05)

                  return 6;

            else //(SigneY==0)

                  return -1;

            }

      }

 

Maintenant que nous avons notre face ordonnée, nous devons décaler vers l’avant pour éviter les erreurs de chevauchement (+= Normal*0.05), puis calculer les coordonnées des textures, ceci par deux simple projection sur Top et Cote normés.

 

CVector2 ptText[MAX_DECALS_PART];

 

for(l=0;l<CurPoint;l++)

      {

      ptColl [l] += Normal*0.05;

      ptText [l].x = ((ptColl[l]-D1) * Cote)/(Size*Size*2);

      ptText [l].y = -((ptColl[l]-D1) * Top)/(Size*Size*2);

      }

 

 

Vous devez maintenant sauver votre partie de décal et recommencer avec les autres faces du monde.

 

struct _Decal

      {

      CVector3 p[MAX_DECALS_PART];

      CVector2 t[MAX_DECALS_PART];

      int NumPart;

      CVector3 normal;

      };

 

Vector<_Decal> AllDecal;

 

 

_Decal NewDecal;

for(l=0;l<CurPoint;l++)

    {

    NewDecal.p[l] = ptColl[l];

    NewDecal.t[l] = ptText[l];

    }

NewDecal.NumPart = CurPoint;

NewDecal.normal = Normal2;

AllDecal.push_back(NewDecal);

 

L’affichage

 

Pour l’affichage, voici la procédure :

 

 

glBindTexture(GL_TEXTURE_2D,TextureDecals);

vector<_Decal >::iterator it;

Int l;

for(it=AllDecal.begin();it!=AllDecal.end();it++)

{

glNormal3fv((float *)(&it->normal));

glBegin(GL_TRIANGLE_FAN);

for(l=0;l<it->NumPart;l++)

      {

      glTexCoord2fv((float *)(&it ->t[l]));

      glVertex3fv((float *)(&it->p[l]));

      }

      glEnd();

}

 

 

L’utilisation de Vector est juste un exemple, vous pouvez trouvez votre propre système de gestion.

 

Améliorations

 

Comme vous aller le constater, la projection de la texture sur les faces octogonales à la face principale est un peu « étirer », cela est dû au fait que nous utilisons un système de projection planaire. Vous pouvez donc utiliser à la place une projection cylindrique, sphérique, en boite, … (Pour adeptes de 3DSMax, cela ressemblerai à le fonction « texture automatique »). Vous obtiendrez ainsi des résultats différents mais pas forcement moins intéressant.

 

Conclusion

 

Vous pouvez télécharger les fichiers Decals.cpp et Decals.h contenant les sources de cet algorithme. Le code est légèrement différent car j’ai du l’adapter à un moteur de jeu que je développe actuellement.

(Télécharger)

 

Cet article touche à ça fin. Et vous devriez maintenant être capable de faire des décals les doigts dans le nez J.

Si, cependant, vous rencontrés des problèmes, n’hésitez pas à me contacter. Je serais aussi très contant  que vous m’envoyer une E-mail, quand votre jeu, aussi simple soit t’il, sortira J.

Je redonne mon E-mail : mathieu.guillame-bert@wanadoo.fr

 

Si vous souhaitez voir un jeu utilisant ce principe je vous conseil l’adresse suivante :

http://cronosbattle.free.fr

Ce jeu est en cour de développement (29/04/05), mais il y à déjà des choses intéressantes.