Les formats MD5Mesh et MD5Anim (modèles de Doom 3)

Puisque nous n'avons affaire qu'à des quaternions unitaires (leur magnitude vaut 1,0), on peut facilement obtenir le dernier composant à l'aide de cette formule :

float t = 1.0f - (q.x * q.x) - (q.y * q.y) - (q.z * q.z);

if (t < 0.0f)
  {
    q.w = 0.0f;
  }
else
  {
    q.w = -sqrt (t);
  }

Voici une brève présentation des opérations et formules que l'on aura besoin d'effectuer sur les quaternions avec les modèles MD5. Pour plus d'information au sujet des quaternions, reportez-vous à un livre sur les mathématiques liées à la 3D, ou a une FAQ en ligne, ou même Wikipédia.

La multiplication de quaternions permet de concaténer deux orientations. La multiplication de deux quaternions Q_a et Q_b est donnée par la formule :

Qa.Qb = (wa, va)(wb, vb) = (wawb - va·vb, wavb + wbva + wa×wb)

Après développement et simplification, on arrive à la formule suivante :

r.w = (qa.w * qb.w) - (qa.x * qb.x) - (qa.y * qb.y) - (qa.z * qb.z);
r.x = (qa.x * qb.w) + (qa.w * qb.x) + (qa.y * qb.z) - (qa.z * qb.y);
r.y = (qa.y * qb.w) + (qa.w * qb.y) + (qa.z * qb.x) - (qa.x * qb.z);
r.z = (qa.z * qb.w) + (qa.w * qb.z) + (qa.x * qb.y) - (qa.y * qb.x);

Attention : la multiplication de deux quaternions n'est pas commutative, c'est-à-dire que Qa × Qb  ? Qb × Qa.

La rotation d'un point par un quaternion est donnée par la formule suivante :

R = Q.P.Q*

où R est le quaternion résultant, Q le quaternion par lequel on veut appliquer une rotation, Q^* son conjugué et P le point « converti » en quaternion. Pour convertir un vecteur 3D en un quaternion, il suffit de copier les trois composants x, y et z du vecteur et de mettre le composant w à 0. La conversion inverse, du quaternion au vecteur, est similaire : on garde les composants x, y et z et on abandonne w.

Remarque : ici le « . » est l'opérateur de multiplication.

L'inverse d'un quaternion peut être obtenu, pour un quaternion unitaire, en prenant l'opposé des composants x, y et z (ceci équivaut à prendre le conjugué du quaternion) :

inverse(<w, x, y, z>) = conjugué(<w, x, y, z>) = <w, -x, -y, -z>

La normalisation d'un quaternion est exactement la même chose que pour les vecteurs, mais avec quatre composants.

Je ne vais pas traiter ici l'interpolation sphérique (appelée « SLERP ») de deux quaternions, car c'est un peu plus long et compliqué, mais vous pouvez toujours regarder le code source (donné à la fin de ce document), dans des livres ou sur Internet pour la formule. L'interpolation sphérique sert à interpoler deux orientations (ou rotations). Elle est utilisée pour l'animation squelettique.

Lors du traitement d'un fichier MD5 Mesh, vous pourrez tomber sur des commentaires. Les commentaires commencent par la chaîne « // » et sont valides jusqu'à la fin de la ligne courante. Ils sont là juste pour les humains qui veulent jeter un œil au fichier à l'aide d'un éditeur de texte ; ils n'affectent en rien les données du modèle. Vous pouvez simplement les ignorer lors du traitement du fichier.

Avant de lire les données géométriques, vous trouverez quelques paramètres importants nécessaires pour la vérification de la validité du fichier md5mesh et pour diverses allocations mémoire.

MD5Version 10
commandline "<string>"

numJoints <int>
numMeshes <int>

La première ligne indique la version du format (un nombre entier). La version du format MD5 utilisé dans Doom 3 est la 10. Ce document ne traite que de la version 10 du format. Les versions anciennes (ou plus récentes) peuvent différer en certains points dans la structure du format.

Ensuite vient la chaîne commmandline utilisée par Doom 3 avec la commande console exportmodels. Je n'ai rien à dire à son sujet, cette commande est propre à Doom 3 et pas vraiment au format de modèle MD5.

numJoints est le nombre de joints du squelette du modèle. numMeshes est le nombre de meshs du modèle contenus dans le fichier md5mesh.

Après ça vous trouverez la liste des joints du squelette de base :

joints {
    "name" parent ( pos.x pos.y pos.z ) ( orient.x orient.y orient.z )
    ...
}

name (string) est le nom du joint. parent (int) est l'index du joint parent. S'il est égal à -1, alors le joint n'a pas de parent et c'est ce que l'on appelle un joint racine. pos.x, pos.y et pos.z (float) représentent la position du joint dans l'espace (coordonnées 3D). orient.x, orient.y et orient.z (float) sont les composants x, y et z du quaternion d'orientation du joint. Après la lecture d'un joint, vous devez calculer son composant w.

Après le squelette, viennent les meshs. Chaque mesh est de la forme :

mesh {
    shader "<string>"

    numverts <int>
    vert vertIndex ( s t ) startWeight countWeight
    vert ...

    numtris <int>
    tri triIndex vertIndex[0] vertIndex[1] vertIndex[2]
    tri ...

    numweights <int>
    weight weightIndex joint bias ( pos.x pos.y pos.z )
    weight ...
}

La chaîne shader est définie dans les fichiers MTR (répertoire /materials) de Doom 3 et indiquent quelles sont les textures à appliquer au mesh et comment les combiner entre elles.

numverts (int) est le nombre de sommets du mesh. Après cette variable vient la liste des sommets. vertIndex (int) est l'index du sommet. s et t (float) sont les coordonnées de texture (également appelées coordonnées UV). Dans le format MD5 Mesh, un sommet ne possède pas de position propre. À la place, sa position est calculée à partir des vertex weights (expliqué plus loin dans ce document). countWeight (int) est le nombre de vertex weights, en commençant à l'index startWeight (int), qui sont utilisées pour obtenir la position finale d'un sommet.

numtris est le nombre de triangles du mesh. triIndex (int) est l'index du triangle. Chaque triangle est défini par trois index des sommets le compodant : vertIndex[0], vertIndex[1] et vertIndex[2] (int).

numweights (int) est le nombre de vertex weights du mesh. weightIndex (int) est l'index du vertex weight. joint (int) est l'index du joint dont il dépend. bias (float) est un facteur compris dans l'intervalle ]0,0 ; 1,0] et qui définit la contribution (ou le poids) de ce vertex weight lors du calcul de la position finale du sommet. pos.x, pos.y et pos.z (float) sont les coordonnées 3D de la position du vertex weight dans l'espace local au joint dont il dépend.

Le squelette du modèle stocké dans les fichiers MD5 Mesh est ce que l'on appelle en anglais « the bind-pose skeleton ». C'est généralement un squelette dans la position dans laquelle le modèle a été créé par l'artiste.

Les joints de ce squelette sont déjà dans leur position finale (ou locale au modèle), vous n'avez pas à faire de calculs dessus afin d'obtenir leur position correcte par rapport au modèle, tels que l'addition de la position du joint parent ou la rotation par le joint parent ou autre. Leur position est en espace objet et est indépendante de celle des autres joints.

Comme dit plus haut, la position des sommets doit être calculée à partir des vertex weights. Chaque sommet possède un ou plusieurs vertex weights, chacun d'entre eux ayant une position dépendant d'un joint (la position est exprimée dans l'espace local au joint), et un facteur indiquant combien cette position pèse dans le calcul de la position finale du sommet. La somme des facteurs de tous les vertex weights d'un sommet doit valoir 1,0. Cette technique est appelée « Vertex Skinning » et permet à un sommet de dépendre de plusieurs joints du squelette, afin d'obtenir de meilleures animations.

D'abord, chaque position des vertex weights doit être convertie de l'espace local au joint à l'espace objet (coordonnées exprimées en fonction de l'origine du modèle). Ensuite, on fait la somme de tous ces vertex weights multipliés par leur facteur bias :

finalPos = (weight[0].pos * weight[0].bias) + ... + (weight[N].pos * weight[N].bias)

Les données des sommets provenant des fichiers MD5 Mesh ont un index start et une variable count. start est l'index du premier vertex weight utilisé pour le sommet. Les autres vertex weights utilisés par le sommet suivent le premier. La variable count indique combien sont utilisés au total pour calculer la position du sommet. Voici le code qui permet de calculer les positions des sommets dans l'espace objet du modèle à partir de leurs vertex weights :

/* setup vertices */
for (i = 0; i < mesh->num_verts; ++i)
  {
    vec3_t finalVertex = { 0.0f, 0.0f, 0.0f };

    /* calculate final vertex to draw with weights */
    for (j = 0; j < mesh->vertices[i].count; ++j)
      {
        const md5_weight_t *weight = &mesh->weights[mesh->vertices[i].start + j];
        const md5_joint_t *joint = &joints[weight->joint];

        /* calculate transformed vertex for this weight */
        vec3_t wv;
        Quat_rotatePoint (joint->orient, weight->pos, wv);

        /* the sum of all weight->bias should be 1.0 */
        finalVertex[0] += (joint->pos[0] + wv[0]) * weight->bias;
        finalVertex[1] += (joint->pos[1] + wv[1]) * weight->bias;
        finalVertex[2] += (joint->pos[2] + wv[2]) * weight->bias;
      }

    ...
  }

Chaque sommet possède ses propres coordonnées de texture. Les coordonnées ST (ou UV) pour le coin supérieur gauche de la texture sont (0,0 ; 0,0). Les coordonnées ST pour le coin inférieur droit sont (1,0 ; 1,0).

Le sens vertical (coordonnée T) est l'inverse du sens standard d'OpenGL. C'est le même repère que celui utilisé par les surfaces DirectDraw. Au chargement d'une texture (autre qu'une texture provenant d'un fichier DDS), vous devrez soit inverser verticalement l'image, soit prendre l'opposé de la coordonnée de texture T pour les sommets des modèles MD5.

Vous aurez certainement besoin de calculer les vecteurs normaux du modèle, par exemple pour l'éclairage. Voici la méthode pour calculer les « normal weights », à l'instar des vertex weights (cette méthode fonctionne également pour les tangentes et bitangentes).

D'abord, calculez tous les sommets des triangles du modèle dans la position du squelette initial.

Calculez les normales des sommets. Vous avez maintenant les normales en espace objet pour le squelette dans sa position initiale.

Pour chaque vertex weight d'un sommet, transformez la normale du sommet par l'inverse du quaternion d'orientation du joint dont dépend le vertex weight. Vous avez à présent le vecteur normal exprimé en espace local au joint. C'est le normal weight que l'on cherchait à obtenir.

Plus tard, au moment de calculer la position des sommets des triangles, vous pourrez opérer de même pour les normales, excepté que vous n'aurez pas à effectuer de translation par rapport aux positions des joints dont dépend le sommet lorsque vous effectuerez la conversion espace local au joint vers espace objet.

Les fichiers MD5 Anim ont la même syntaxe que les fichiers MD5 Mesh. Les commentaires commencent par « // » et sont valables jusqu'en fin de ligne. Un en-tête de fichier est également présent avec un numéro de version, une ligne de commande et des variables nécessaires pour les allocations mémoire :

MD5Version 10
commandline "<string>"

numFrames <int>
numJoints <int>
frameRate <int>
numAnimatedComponents <int>

Le numéro de version est le même pour tous les fichiers MD5, donc il doit être égal à 10. La variable commandline est interne à Doom 3.

numFrames (int) est le nombre de séquences de l'animation. Une animation est composée de plusieurs séquences, chacune étant une copie du squelette à une position particulière. En parcourant chacune des séquences les unes à la suite des autres on obtient une animation.

numJoints (int) est le nombre de joints des squelettes de chaque séquence de l'animation. Il doit être le même que celui du squelette lu dans le fichier MD5 Mesh pour que l'animation puisse être jouable par le modèle.

frameRate (int) est le nombre de séquences par seconde à dessiner pour l'animation. La durée d'une séquence peut être obtenue en inversant simplement frameRate.

numAnimatedComponents (int) est le nombre de paramètres par séquence utilisés pour calculer le squelette de la séquence. Ces paramètres, combinés avec le squelette de base donné par le fichier MD5 Anim, permettent de construire un squelette pour chaque séquence.

Après la lecture de l'en-tête, vient la hiérarchie du squelette utilisé pour l'animation. Elle apporte des indications sur les joints pour construire les squelettes des séquences à partir du squelette de base :

hierarchy {
    "name"   parent flags startIndex
    ...
}

name (string) est le nom du joint. parent (int) est l'index du joint parent. Si parent vaut -1, alors le joint n'a pas de parent. À partir de ces deux informations, et du nombre de joints, il est conseillé de comparer ces données avec le squelette du fichier MD5 Mesh afin de s'assurer que l'animation est compatible avec ce modèle. flags (int) est un champ de bits indiquant comment l'on doit calculer ce joint pour le squelette d'une séquence. startIndex (int) est un index sur le début des paramètres utilisés pour calculer le squelette d'un séquence.

Après la hiérarchie viennent les bounding box. Ce sont des boîtes englobant le modèle tout entier, utilisées pour la détection de collision. Il y a une bounding box pour chaque séquence :

bounds {
    ( min.x min.y min.z ) ( max.x max.y max.z )
    ...
}

min.x, min.y et min.z (float) représentent les coordonnées 3D minimum de la boîte ; max.x, max.y et max.z (float) représentent les coordonnées maximum. Ces coordonnées sont exprimées en espace objet. Ces boîtes sont utiles pour calculer les AABB(2) ou OBB(3) pour le frustum culling et la collision de détection.

Viennent ensuite les données du squelette de base qui servira à calculer les squelettes des séquences de l'animation. Ces données regroupent la position et l'orientation de chaque joint du squelette. Il y a une ligne pour chaque joint :

baseframe {
    ( pos.x pos.y pos.z ) ( orient.x orient.y orient.z )
    ...
}

pos.x, pos.y et pos.z (float) représentent la position du joint. orient.x, orient.y et orient.z (float) sont les composants x, y et z du quaternion d'orientation.

Après les données du squelette de base, viennent les données des séquences de l'animation. Il y a un bloc de données pour chaque frame. Ces données sont les paramètres utilisés pour calculer les squelettes propres à chaque frame :

frame frameIndex {
    <float> <float> <float> ...
}

frameIndex (int) est l'index de la séquence. Entre les accolades, vous avez un champ de nombres à virgule flottante. La variable numAnimatedComponents précise leur nombre (invariable pour toutes les séquences d'une même animation). Une fois tous ces paramètres lus, vous pouvez calculer le squelette de la séquence.

À partir des données du squelette de base, des infos sur la hiérarchie et des données d'une séquence particulière, vous pouvez calculer un squelette pour cette séquence. Voici comment ça fonctionne pour chaque joint : on commence avec les données du squelette de base (position et orientation) puis on remplace certains composants de la position et de l'orientation par les données de la séquence. Les drapeaux apportés par la hiérarchie du squelette indiquent quels sont les composants à remplacer.

Description de la variable flags (fourni avec la hiérarchie) : en partant de droite, les trois premiers bits sont pour les composants du vecteur position, et les trois suivants pour les composants du quaternion orientation. Si un bit est positionné à 1, alors vous devez remplacer le composant correspondant par une valeur du champ de données de la séquence. Quelle valeur ? Celle donnée par la variable startIndex. Vous commencez à la position startIndex dans le champ de données de la séquence, puis vous incrémentez la position chaque fois que vous avez à remplacer un composant de la position ou de l'orientation.

Une fois que vous avez calculé la position et l'orientation du joint « animé », vous devez les transformer en espace objet. Avant cela, n'oubliez pas de calculer le composant w du quaternion du joint !

Pour la position, si le joint possède un parent, vous devez transformer le joint par le quaternion orientation du parent, puis ajouter la position du parent à la position résultante de la première transformation. Si le joint n'a pas de parent, alors il est déjà en espace objet.

Pour l'orientation, si le joint possède un parent, vous devez concaténer les deux orientations ; d'abord celle du parent puis celle du joint. Une fois concaténée, renormalisez le résultat (les quaternions représentant une orientation doivent être unitaires). Si le joint n'a pas de parent, alors son orientation est déjà en espace objet.

Voici le code pour construire le squelette d'une séquence :

for (i = 0; i < num_joints; ++i)
  {
    const baseframe_joint_t *baseJoint = &baseFrame[i];
    vec3_t animatedPos;
    quat4_t animatedOrient;
    int j = 0;

    memcpy (animatedPos, baseJoint->pos, sizeof (vec3_t));
    memcpy (animatedOrient, baseJoint->orient, sizeof (quat4_t));

    if (jointInfos[i].flags & 1) /* Tx */
      {
        animatedPos[0] = animFrameData[jointInfos[i].startIndex + j];
        ++j;
      }

    if (jointInfos[i].flags & 2) /* Ty */
      {
        animatedPos[1] = animFrameData[jointInfos[i].startIndex + j];
        ++j;
      }

    if (jointInfos[i].flags & 4) /* Tz */
      {
        animatedPos[2] = animFrameData[jointInfos[i].startIndex + j];
        ++j;
      }

    if (jointInfos[i].flags & 8) /* Qx */
      {
        animatedOrient[0] = animFrameData[jointInfos[i].startIndex + j];
        ++j;
      }

    if (jointInfos[i].flags & 16) /* Qy */
      {
        animatedOrient[1] = animFrameData[jointInfos[i].startIndex + j];
        ++j;
      }

    if (jointInfos[i].flags & 32) /* Qz */
      {
        animatedOrient[2] = animFrameData[jointInfos[i].startIndex + j];
        ++j;
      }

    /* compute orient quaternion's w value */
    Quat_computeW (animatedOrient);

    /* NOTE: we assume that this joint's parent has
       already been calculated, i.e. joint's ID should
       never be smaller than its parent ID. */
    md5_joint_t *thisJoint = &skelFrame[i];

    int parent = jointInfos[i].parent;
    thisJoint->parent = parent;
    strcpy (thisJoint->name, jointInfos[i].name);

    /* has parent? */
    if (thisJoint->parent < 0)
      {
        memcpy (thisJoint->pos, animatedPos, sizeof (vec3_t));
        memcpy (thisJoint->orient, animatedOrient, sizeof (quat4_t));
      }
    else
      {
        md5_joint_t *parentJoint = &skelFrame[parent];
        vec3_t rpos; /* rotated position */

        /* add positions */
        Quat_rotatePoint (parentJoint->orient, animatedPos, rpos);
        thisJoint->pos[0] = rpos[0] + parentJoint->pos[0];
        thisJoint->pos[1] = rpos[1] + parentJoint->pos[1];
        thisJoint->pos[2] = rpos[2] + parentJoint->pos[2];

        /* concatenate rotations */
        Quat_multQuat(parentJoint->orient, animatedOrient, thisJoint->orient);
        Quat_normalize (thisJoint->orient);
      }
  }

jointInfos contient les infos relatives à la hiérarchie du squelette. animFrameData est un tableau contenant les données de la séquence. Aussi n'oubliez pas de copier l'index du parent depuis les infos de la hiérarchie vers votre nouveau joint. Le nom du joint peut également être utile parfois.

Vous devez effectuer cette opération pour chaque séquence. Du moins, celles dont vous avez besoin.

Animer le modèle consiste à calculer la séquence courante à dessiner, la suivante et à mettre à jour le temps écoulé depuis le début de la séquence courante.

L'index de la séquence courante est incrémenté lorsque la durée maximale de la séquence a été atteinte. Pour rappel, cette durée maximale est l'inverse de la variable frameRate.

Vous pouvez ensuite procéder à l'interpolation des squelettes des séquences courante et suivante. Le pourcentage d'interpolation peut être obtenu en multipliant le temps écoulé depuis la dernière fois que la séquence courante a été incrémentée par la variable frameRate propre à l'animation.

Pour interpoler deux squelettes, il suffit d'interpoler chacun de leurs joints. Et pour interpoler deux joints, il suffit d'interpoler la position et l'orientation.

Pour la position, procédez à une simple interpolation linéaire :

finalJoint->pos.x = jointA->pos.x + interp * (jointB->pos.x - jointA->pos.x);
finalJoint->pos.y = jointA->pos.y + interp * (jointB->pos.y - jointA->pos.y);
finalJoint->pos.z = jointA->pos.z + interp * (jointB->pos.z - jointA->pos.z);

Pour l'orientation, il est préférable de procéder à une interpolation sphérique plutôt qu'à une simple interpolation linéaire, à moins que les rotations ne soient très petites. Pour la formule de l'interpolation sphérique, reportez-vous à un livre de maths ou à quelques recherches sur le web :

Quat_slerp( jointA->orient, jointB->orient, interp, finalJoint->orient );

Code source d'exemple 1 : md5.c (13,5 Ko). Uniquement MD5 Mesh. Pas d'application de texture, pas d'éclairage, pas d'animation. Cette démo « light » tient sur moins de 650 lignes de code.

Code source d'exemple 2 : md5mesh.c (14,2 Ko), md5anim.c (12,2 Ko), md5model.h (3,7 Ko). MD5 Mesh et Anim. Pas d'application de texture, pas d'éclairage. Moins de 1300 lignes.

Version PDF : télécharger (54.5 Ko)