Newton Game Dynamics : les Arbres de Collision

Dans le tutoriel précédent, vous avez découvert comment fonctionne le moteur Newton Game Dynamics pour permettre à des formes géométriques simples (sphères ou boîtes par exemple) d'interagir entre elles de manière réaliste. Toutefois, comment faire dans le cas d'environnements complexes ? Bien sûr, on pourrait diviser un mesh complexe (un mesh est un objet 3D constitué de polygones plus ou moins nombreux suivant sa complexité) en plusieurs primitives de base (sphères, boîtes), mais cela s'avérerait extrêmement fastidieux et plutôt compliqué. Pour faire face à ce problème, le développeur de la bibliothèque (car je crois qu'il est tout seul, son travail est à saluer !) a instauré les arbres de collision, également appelés collision tree (c'est d'ailleurs ce terme que vous retrouverez dans la documentation). Les arbres de collision permettent de définir des primitives de collision bien plus complexes en passant au moteur les coordonnées des vertices du modèle.

L'un des gros inconvénients des arbres de collision est que, compte tenu de leur complexité, ils doivent rester immobiles. C'est-à-dire qu'on ne peut leur donner ni vitesse ni force… Il existe bien sûr des techniques « détournées » qui permettent de donner l'illusion de les déplacer (on peut par exemple effectuer une rotation sur le modèle 3D, et donner translations, forces… adéquates à tous les autres corps). Toutefois, pour attribuer des primitives de collision complexes à des modèles 3D, il existe un autre moyen - bien que moins précis - , que nous verrons dans un prochain tutoriel : les enveloppes convexes (convex hulls pour les intimes) et les objets composés (ou compound qui contiennent plusieurs enveloppes convexes).

Mais revenons à nos arbres de collision. Je disais donc qu'ils devront rester immobiles, tout du moins dans la version de Newton avec laquelle j'écris cet article. Toutefois, la limitation actuelle des arbres de collision n'en est pas vraiment une, puisque leur but premier est de définir des primitives de collision complexes pour des niveaux (un terrain…), des modèles 3D… et qui ne bougent donc normalement pas.

Par rapport au précédent tutoriel, j'ai revu l'organisation des classes afin que ce soit plus aisément compréhensible et plus facile à gérer. Je ne reviendrai pas sur ce que nous avons vu précédemment, ou que brièvement. Concernant la mise en application de ce concept, j'ai choisi d'utiliser un heightmap (plus de détail dans la partie III-1-A), qui représentera notre sol, et des sphères et des boîtes qui tomberont sur le sol.

Avant de rentrer dans le vif du sujet, et pour ceux ayant un peu la flemme de lire la doc, voici les fonctions pour créer des primitives de collisions pour des formes de base :

1) NewtonCollision * NewtonCreateCone (const NewtonWorld * nWorld, float rayon, float hauteur, const float * offsetMatrix);
Elle permet, comme son nom l'indique, de créer une primitive de collision pour un cône. Le premier paramètre est un pointeur vers un objet NewtonWorld valide, le deuxième élément la valeur du rayon de la base, le troisième paramètre la hauteur à partir de la base et le dernier élément un pointeur vers un tableau de 16 float contenant le volume de collision de l'objet. En laissant sur NULL (c'est plus simple !), ce volume de collision est centré sur l'origine de l'objet ;

2) NewtonCollision * NewtonCreateCapsule (const NewtonWorld * nWorld, float rayon, float hauteur, const float * offsetMatrix);
Pas besoin d'explications, je pense ;

3) NewtonCollision * NewtonCreateCylinder (const NewtonWorld * nWorld, float rayon, float hauteur, const float * offsetMatrix);
Pareil, mais pour créer un cylindre !

4) NewtonCollision * NewtonCreateChamferCylinder (const NewtonWorld * nWorld, float rayon, float hauteur, const float * offsetMatrix);
Pour créer un cylindre chanfreiné.

Comme je l'ai dit en introduction, j'ai remanié légèrement l'architecture des classes par rapport au premier tutoriel. On retrouve donc la classe CVector, qui elle n'a pas bougé d'un iota, la classe CPhysique, CPhysSphere, CPhysBox et la petite nouveauté, CPhysHeightmap.

La classe CPhysique est donc la classe de base des trois autres. Elle possède comme donnée membre un pointeur vers un objet NewtonWorld. Concernant ses fonctions membres, on retrouve un constructeur et destructeur, une fonction SetPosition qui modifie la matrice de l'objet, et une fonction Render déclarée pure, qui devra donc être définie dans chacune de ses classes de base. À noter comme pour le premier tutoriel une structure matrice simplifiée, qui comprend juste en plus une fonction LoadIdentity, afin de l'initialiser à la matrice identitée plus facilement.

La classe CPhysBox dérive de la classe CPhysique et a donc accès à ses variables et fonctions membres. Contrairement au premier tutoriel, j'ai décidé de diviser la phase d'initialisation en plusieurs phases. Ainsi, la fonction CreerBoite, qui prend en argument un pointeur vers un objet NewtonWorld et une longueur, se charge seulement de créer la primitive de collision, sans lui affecter de callback. Pour ceci, il faut appeler la fonction SetMasse en lui passant en argument une masse, afin de lui affecter un callback. De cette manière, si vous souhaitez utiliser les capacités du moteur juste pour les collisions, il vous suffit d'appeler la fonction CreerBoite. Si en plus vous voulez lui affecter des forces, vous le pouvez en appelant la fonction SetMasse. À part ça, rien de bien nouveau.

La classe CPhysSphere est l'équivalent de la classe CPhysBox, mais pour gérer les sphères. Là aussi, à part le changement d'organisation de la classe, rien de neuf.

III-A. La classe CPhysHeightmap▲

#ifndef CPHYSHEIGHTMAP_H
#define CPHYSHEIGHTMAP_H

#include <string>
#include <GL/gl.h>
#include <GL/glu.h>
#include <GL/corona.h>
#include "cphysique.h"

// Quelques données relatives au Heightmap
const GLuint TAILLE_MAP = 257; // La largeur et la longueur de la carte
const GLuint iPrecision = 5; // Précision de la carte


class CPhysHeightmap : public CPhysique
{
   public:
      // Constructeur / Destructeur
      CPhysHeightmap ();
      virtual ~CPhysHeightmap ();

      // Fonction qui va charger le Heightmap et créer l'arbre de collision
      bool CreerHeightmap (NewtonWorld * nWorld, std::string szNom);
      GLfloat LireHauteur (GLuint x, GLuint z); // Fonction pour lire la hauteur

      void Render (); // Fonction Render

   protected:
      GLubyte m_ubHeightmap [TAILLE_MAP * TAILLE_MAP]; // Tableau contenant les données du Heightmap
      GLuint m_uiTexture;
};

#endif // CPHYSHEIGHTMAP_H
};

// Création du heightmap et de l'arbre de collision
bool CPhysHeightmap::CreerHeightmap (NewtonWorld * nWorld, std::string szNom)
{
   std::ifstream fichier (szNom.c_str(), std::ios::binary);

   if (!fichier)
   {
      std::cerr << "Erreur dans l'ouverture du fichier heightmap.";
      return GL_FALSE;
   }

   fichier.read ((char*)&m_ubHeightmap, TAILLE_MAP * TAILLE_MAP);
   
   fichier.close(); // On n'a plus besoin de ce fichier, on le ferme

// On créé l'arbre de collision
   NewtonCollision * nCollision = NULL;

   nCollision = NewtonCreateTreeCollision (nWorld, NULL);

   NewtonTreeCollisionBeginBuild (nCollision);

   GLfloat fVert[9];
   GLint strideInBytes = sizeof(GLfloat) * 3;

   for (GLuint x = 0 ; x < TAILLE_MAP - 1 ; x += iPrecision)
   {
      for (GLuint z = 0 ; z < TAILLE_MAP - 1 ; z += iPrecision)
      {
         fVert [0] = x;
         fVert [1] = LireHauteur (x, z) / 10.0f;
         fVert [2] = z;

         fVert [3] = x;
         fVert [4] = LireHauteur (x, z + iPrecision) / 10.0f;
         fVert [5] = z + iPrecision;

         fVert [6] = x + iPrecision;
         fVert [7] = LireHauteur (x + iPrecision, z) / 10.0f;
         fVert [8] = z;

         NewtonTreeCollisionAddFace (nCollision, 3, &fVert [0], strideInBytes, 0);
      }
   }

   NewtonTreeCollisionEndBuild (nCollision, 1); // 1 = optimisation

   m_pBody = NewtonCreateBody (nWorld, nCollision);

   if (m_pBody == NULL)
   {
      std::cerr << "Impossible de créer l'arbre de collision.";
      return EXIT_FAILURE;
   }

   NewtonReleaseCollision (nWorld, nCollision); // On libère l'arbre de collision

Il ne nous reste plus que la fonction main, qui n'a finalement que peu changé par rapport à la dernière fois, si ce n'est les appels pour créer les sphères et les boîtes qui sont un peu différentes compte tenu du petit changement d'organisation des classes.

Quelques petites choses sont toutefois à éclaircir, comme ces quelques lignes juste après la création du monde Newton :

float min[] = {-400, -400, -400};
   float max[] = {400, 400, 400};
   NewtonSetWorldSize (nWorld, min, max);
   NewtonSetMinimumFrameRate (nWorld, 60.0f);

En effet, de base, la taille du monde Newton est limitée à une boîte dont le minimum est au point -100;-100;-100 et le maximum au point 100;100;100. Tous les objets en dehors de cette limite sont considérés par Newton comme inactif, et les callback n'agissent donc pas sur eux. Il nous faut donc augmenter cette taille, puisque le heightmap est assez grand. Attention toutefois à ne pas donner des dimensions trop extravagantes sous peine de faire ramer fortement le moteur.

Dernière chose à vous expliquer, les trois fonctions pour le moins barbares au début du fichier :

/// FONCTIONS DEBUG
CVector debugFace [1024][2];

void DebugShowGeometryCollision (const NewtonBody* body, int vertexCount, const dFloat* faceVertec, int id);
void  DebugShowBodyCollision (const NewtonBody* body);

int debugCount = 0;

// Pour montrer la géométrie des primitives de collision
void DebugShowCollision ()
{
    int i;

    glDisable(GL_TEXTURE_2D);

    glBegin(GL_LINES);
    glColor3f(1.0f, 1.0f, 0.0f);
    NewtonWorldForEachBodyDo (nWorld, DebugShowBodyCollision);

    glColor3f(0.0f, 0.0f, 1.0f);
    for (i = 0; i < debugCount; i ++) {
        glVertex3f (debugFace[i][0].x, debugFace[i][0].y, debugFace[i][0].z);
        glVertex3f (debugFace[i][1].x, debugFace[i][1].y, debugFace[i][1].z);
    }
    glEnd();
    glEnable (GL_TEXTURE_2D);
}

// Montrer la géométrie des collisions
void DebugShowGeometryCollision (const NewtonBody* body, int vertexCount, const dFloat* faceVertec, int id)
{
    int i;

    i = vertexCount - 1;
    CVector p0 (faceVertec[i * 3 + 0], faceVertec[i * 3 + 1], faceVertec[i * 3 + 2]);
    for (i = 0; i < vertexCount; i ++) {
        CVector p1 (faceVertec[i * 3 + 0], faceVertec[i * 3 + 1], faceVertec[i * 3 + 2]);
        glVertex3f (p0.x, p0.y, p0.z);
        glVertex3f (p1.x, p1.y, p1.z);
         p0 = p1;
    }
}

// Montre la géométrie de collision des corps Newton
void  DebugShowBodyCollision (const NewtonBody* body)
{
    NewtonBodyForEachPolygonDo (body, DebugShowGeometryCollision);
}
/// FIN DES FONCTIONS DEBUG

Ces fonctions, dites Debug, nous permettent de dessiner ce que Newton « voit », c'est-à-dire les lignes de collision. Elles peuvent s'avérer extrêmement utiles, notamment pour vérifier que les primitives de collision que l'on a créées sont bien en accord avec ce que l'on a souhaité faire.
Pour pouvoir les utiliser, un simple appel à la fonction DebugShowCollision () avant le dessin des objets suffit. Attention toutefois, ces fonctions ne sont là qu'à un but de debug car elles ralentissent extrêmement le framerate (vous pourrez en juger par vous-même).
J'ai ajouté dans la boucle des événements de la SDL un switch qui permet de détecter dès que la touche F1 est enfoncée, afin d'activer et de désactiver à volonté l'affichage de ces lignes de debug.

C'est tout pour ce tutoriel consacré aux arbres de collision. J'espère avoir été assez clair, et si vous rencontrez un quelconque problème, vous pouvez m'envoyer un message privé, je tâcherai d'y répondre. Pour la prochaine fois, je compte vous montrer comment utiliser les enveloppes convexes (ou convex hulls) qui, comme les arbres de collision, permettent de créer des primitives de collisions complexes (moins précises que les arbres de collision toutefois), mais qui ont l'avantage de pouvoir être soumises à diverses forces et donc bouger de manière réaliste. En attendant, voici le résultat de ce tutoriel :

Source du programme : ici (miroir)

Merci à Laurent Gomila pour sa relecture et ses avis, jc_cornic pour sa correction orthographique et fearyourself pour ses corrections dans le code !