Optimisation des indices de vertices

L'une des préoccupations majeures des programmeurs de jeux vidéo, qu'ils soient amateurs ou professionnels, est d'obtenir un framerate le plus haut possible. Pour ceci, de nombreuses méthodes s'offrent à vous : diminuer le nombre de triangles des modèles 3D, simplifier les shaders, diminuer les calculs d'éclairages, ou encore réécrire les algorithmes d'intelligence artificielle afin de les rendre plus performants. Il existe pourtant une autre technique, très simple à mettre en œuvre, et qui peut sensiblement améliorer les performances, tout du moins sur les cartes graphiques les plus récentes : réorganiser les indices afin de favoriser l'utilisation du cache.

Tout comme les CPU, les GPU modernes disposent d'un cache, pouvant contenir entre 8 et 32 éléments sur les cartes graphiques récentes, ces éléments étant accessibles très rapidement. Il devient donc clair qu'il est important de réordonner les indices afin d'utiliser au maximum ce cache. Imaginons par exemple la liste d'indices suivantes : 0 - 1 - 2 et 4 - 3 - 2, avec un cache de deux éléments. Le vertex 0 sera inséré dans le cache, puis le vertex 1, puis le vertex 2 (le vertice 0 sortira quant à lui du cache), puis le vertice 4, le 3 et enfin le 2. Et bien ici, on a un exemple très simple d'indices mal organisés. Le vertex 2 est en effet utilisée deux fois, mais la seconde fois qu'on l'utilisera, il ne sera plus dans le cache et ne sera pas dessiné de la manière la plus rapide possible. C'est ce qu'on appelle un « défaut de cache » (ou « cache miss » en anglais). On peut donc réordonner les indices afin de profiter de ce concept : 0 - 1 - 2 et 2 - 3 - 4. Ainsi, le vertex 2 sera ajouté dans le cache, puis le vertex 2 sera de nouveau demandé pour créer le second triangle, mais étant déjà dans le cache, il sera dessiné plus rapidement.

Bien sûr, avec des cartes graphiques pouvant traiter des millions de triangles à la seconde, l'exemple ci-dessus sera imperceptible. Toutefois, avec des scènes de plusieurs centaines de milliers de triangles, réorganiser des modèles permettra sans aucun doute de gagner en fluidité.

Il existe deux principales méthodes afin de favoriser l'utilisation du cache. Tout d'abord l'utilisation des triangles strips ou, mieux, l'utilisation des triangles strips couplée aux indices de vertices. Toutefois, les triangles strips sont à présent moins efficaces sur les cartes graphiques récentes, où il est plutôt conseillé (notamment par les concepteurs de cartes graphiques) d'envoyer à la carte graphique des triangles normaux, couplés aux indices de vertices. La seconde méthode consiste donc à optimiser ces indices de vertices, et c'est ce que nous allons étudier dans ce tutoriel.

Cette méthode sera donc inutile sur des cartes graphiques anciennes ne disposant pas ou très peu de cache, où il est conseillé d'utiliser des triangles strips (il existe de nombreux algorithmes permettant de créer des triangles strips sur Internet).

Comme dit plus haut, nous allons donc optimiser les indices de vertices. Il existe de nombreux algorithmes, plus ou moins complexes, pour arriver à cet objectif. Tout d'abord la méthode de Hugues Hoppe (ici, voir l'article « Optimization of mesh locality for transparent vertex caching »). Son principal désavantage est qu'elle optimise les modèles à une seule taille de cache. Par exemple, si les indices sont optimisés pour une taille de cache de 16, et que finalement la machine ne dispose que d'un cache de 12, les performances ne seront finalement pas meilleures, voire pires, qu'avec les indices non optimisés. La méthode de Hoppe est cependant idéale pour les consoles, où la taille du cache est fixe.

DirectX vous propose une fonction automatique, D3DXOptimizeFaces, qui repose sur l'algorithme de H. Hoppe citée juste au-dessus, tout en apportant plusieurs améliorations. Toutefois, elle semble disposer des mêmes défauts que la méthode sur laquelle cette fonction repose, à savoir une optimisation optimale pour une seule taille de cache.

Il existe d'autres méthodes, plus complexes, expliquées dans différents papiers, que vous pouvez implémenter si le cœur vous en dit, comme celui-ci : par là (« Cache Oblivious Mesh Layouts », de Sung-Eui Yoon, Peter Lindstrom, Valerio Pascucci et Dinesh Manocha).

Toutefois, la méthode que nous allons implémenter repose sur un algorithme trouvé par Tom Forsyth , et expliqué ici : cliquez ici. Ses principaux avantages sont qu'elle est assez rapide (environ 60 ms pour optimiser un modèle de 5500 triangles, sur mon Athlon XP 3000+), très facile à implémenter et, surtout, contrairement à la méthode de Hoppe, efficace quelle que soit la taille du cache. C'est-à-dire que l'algorithme n'optimise pas les modèles de façon optimale pour une taille de cache donnée, mais l'optimise de manière à ce que ce soit suffisamment efficace pour n'importe quelle taille de cache. Je vous conseille donc dans un premier temps de bien lire le papier de la méthode, puisque cet article sera surtout un exemple d'implémentation de la méthode.

Vous avez à présent lu le papier de la méthode, et avant de foncer tête baissée dans son implémentation, voici un pseudocode de l'algorithme :

OptimizeIndicesOrder (indices, tailleDuCache, nombreDeVertices) :
Initialisation :
nombreDeTriangles : indices / 3 ;
pour chaque triangle : on ajoute, à chaque vertex qui le compose, une référence à ce triangle (en l'occurrence l'indice) ,
pour chaque vertex : on calcule son score ;
pour chaque triangle : on calcule son score (somme des trois scores de ses vertices) ;
on récupère l'indice du premier triangle ayant le plus haut score.

Corps de l'algorithme :
Tant qu'il reste des triangles à ajouter :

Si le score du triangle à ajouter est trop bas, on fait une recherche dans tous les triangles non ajoutés.


On supprime, pour chaque vertex qui compose le triangle à ajouter, la référence à ce triangle.
On met à jour les indices, et on réduit de 1 le nombre de triangles à ajouter

On ajoute dans le cache (virtuel) les trois vertices du triangle qui vient d'être ajouté.

On recalcule leur score, et on met à jour le score de tous les triangles qui utilisent ces trois vertices.

Enfin, on recherche parmi les triangles qui utilisent les vertices présents dans le cache, celui qui a le meilleur score, et on récupère son indice.

Voilà, nous avons à présent tout le nécessaire pour commencer l'implémentation de l'algorithme. La première chose que nous allons implémenter est un cache LRU. Comme vous l'avez constaté, l'algorithme utilise un cache « virtuel » de type LRU (Least Recently Used), qui fonctionne de la manière suivante : lorsqu'un élément est ajouté dans le cache, il est placé à la tête de celui-ci, et si la taille maximale est atteinte, l'élément le plus ancien sort du cache. Si l'élément à ajouter est déjà présent dans le cache (on n'autorise pas les doublons), alors on replace cet élément à la tête. J'ai décidé de l'implémenter en utilisant un container de type std::deque. Voici l'implémentation de ce cache :

// Fonction implémentant de manière efficace un cache LRU (Least Recently Used),
// implémenté en utilisant un std::vector

#ifndef LRUCACHE_HPP
#define LRUCACHE_HPP

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>

// Pour un cache en utilisant une deque
template <typename Value_Type>
class LRUCache
{
   public:
      // Constructeur
      LRUCache (const std::size_t maxSize)
         : maxSize (maxSize)
      {
      }

      // Un second constructeur qui initialise le cache avec maxSize fois l'élément
      // passé en paramètre. Utile dans certains contextes, car il est théoriquement
      // impossible d'y ajouter deux valeurs identiques
      LRUCache (const std::size_t maxSize, const Value_Type & val)
         : maxSize (maxSize), LRUList (maxSize, val)
      {
      }
        
   private:
      // Quelques typedefs pour faciliter le travail...
      typedef typename std::vector<Value_Type>::iterator vec_iterator;
      typedef typename std::vector<Value_Type>::const_iterator vec_const_iterator;
        
      // Taille maximale du cache
      std::size_t maxSize;
 
      // Les données en elles-mêmes
      std::vector<Value_Type> LRUList;
 
   public:
      // On cherche un élément
      vec_iterator find (const Value_Type & value)
      {            
         // On recherche l'élément
         vec_iterator vec_iter = std::find (LRUList.begin(), LRUList.end(),
                                            value);

         // Si aucun élément n'a été trouvé, on retourne l'itérateur vers la fin
         if (vec_iter == LRUList.end())
            return vec_iter;
 
         // Sinon, on replace l'élément au début de la liste
         Value_Type val = *vec_iter;
         LRUList.erase (vec_iter);
         LRUList.insert (LRUList.begin(), val);
 
         // On renvoie l'élément
         return (LRUList.begin());
      }
 
      // Fonction pour insérer un élément
     Value_Type insert (const Value_Type & value)
     {
        // On recherche si l'élément est déjà dans la liste
        vec_iterator vec_iterator = find (value);
                
        // Si l'élément n'est pas encore présent, on l'ajoute à la fin de la liste.
        // S'il est présent, il sera automatiquement ajouté au début (MRU)
        if (vec_iterator == LRUList.end())
           LRUList.insert (LRUList.begin(), value);
     
        // On vérifie si on ne dépasse pas la taille maximale du cache
        if (LRUList.size() > maxSize)
        {
           // On récupère la valeur de l'élément qui va être supprimé
           Value_Type val = LRUList.back();
         
           // On supprime le dernier élément
           LRUList.pop_back();
         
           // On renvoie l'élément
           return val;
        }
         
        // Sinon, on retourne l'élément qui vient d'être ajouté
        return (LRUList.front());
      }
            
      // Pour accéder à un élément
      const Value_Type & operator[] (const std::size_t idx) const
      {
         assert (idx < maxSize);
                
         return LRUList[idx];            
      }
    
      // On affiche les éléments dans l'ordre, du plus récent au plus ancien
      void Write () const
      {
         for (vec_const_iterator vec_const_iter = LRUList.begin(),
              itEnd = LRUList.end() ; vec_const_iter != itEnd ; ++vec_const_iter)
         {
            std::cout << *vec_const_iter << std::endl;
         }
      }            
};

#endif // LRUCACHE_HPP

Le code est pour le moins simplissime. On propose deux constructeurs, dont un qui permet d'initialiser le cache à une valeur donnée, alors que le cache n'autorise théoriquement pas les doublons. Cela permet juste de simplifier les choses. En effet, lors de l'implémentation de l'algorithme, on aura besoin de récupérer les indices des vertices qui seront sortis du cache. Comme les indices sont des valeurs positives, ceci permettra de manière très simple de vérifier s'il s'agit bien d'indices de vertices (valeurs positives ou nulle), ou bien des indices dus à l'initialisation du cache (valeurs négatives).

Les fonctions find et insert permettent d'imiter les containers de la STL. find se charge de trouver si un élément est présent dans le cache. S'il l'est, cet élément est replacé au début du cache, et un itérateur vers cet élément est renvoyé, sinon, find renvoie un itérateur vers LRUCache.end(). insert permet, quant à elle, d'insérer un nouvel élément.

L'utilisation d'un vector s'explique par le fait d'un accès aléatoire via l'opérateur [] très rapide. Même si utiliser un std::deque, qui propose une insertion constante aux deux extrémités du container (via push_back et push_front), mes petits tests ont montré que je gagne 10 ms sur un petit modèle de 5500 indices en utilisant un vector plutôt qu'un deque. Sur un temps d'exécution de 60 ms, les 10 ms gagnées rien qu'en utilisant un autre container sont donc les bienvenues (et plus le nombre d'indices à réorganiser sera grand, plus le gain sera important). L'utilisation d'un std::unordered_set aurait pu être intéressante, car il offre un temps d'insertion constant, mais en plus une implémentation de find en complexité log N au lieu de N, mais comme nous travaillons sur des petits caches (maximum 32 éléments), ceci n'est pas trop un problème. De plus, std::unordered_set n'est pas disponible sur toutes les implémentations de la STL et, surtout, n'offre pas d'accès direct aux éléments.

Nous allons à présent implémenter l'algorithme en lui-même. Commençons par plusieurs constantes et deux structures :

// Plusieurs constantes utilisées pour le calcul des scores
const float FindVertexScore_CacheDecayPower = 1.5f;
const float FindVertexScore_LastTriScore = 0.75f;
const float FindVertexScore_ValenceBoostScale = 2.0f;
const float FindVertexScore_ValenceBoostPower = 0.5f;

// Quelques structures pour la mise en place de l'algorithme :
struct TriData
{
   bool isAdded; // Le triangle est-il ajouté à la liste de dessin ?
   float score; // Score du triangle (somme des scores de ses trois vertices)
   std::size_t indices[3]; // Les indices vers ses vertices
};

struct VertData
{
   float score; // Score du vertex
   std::set<std::size_t> remainingTriangles; // Indices vers les triangles qui
                                                         // utilisent ces vertex non ajoutés
                                                         // à la liste des triangles à dessiner
    
   float CalculateScore (const std::size_t positionInCache, const std::size_t cacheSize)
   {
      if (remainingTriangles.empty())
      {
      score = -1.0f;
      return score;
      }        
    
      // N'est pas dans le cache
      if (positionInCache < 0)
      {
      }
      else if (positionInCache < 3)
      {
         // Ce vertex est utilisé dans le dernier triangle ajouté, il a
         // un score spécial
         score = FindVertexScore_LastTriScore;
      }
      else
      {
         assert (positionInCache < cacheSize);
         const float scaler = 1.0f / (cacheSize - 3);
         score = std::powf (1.0f - (positionInCache - 3) * scaler, FindVertexScore_CacheDecayPower);
      }
        
      float valenceBoost = std::powf (remainingTriangles.size(),
                                      -FindVertexScore_ValenceBoostPower);
      score += FindVertexScore_ValenceBoostScale * valenceBoost;
        
      return score;
   }

};

Les constantes sont directement prises du papier de Tom Forsyth, tout comme la fonction de calcul du score. Pas grand-chose à ajouter ici.

bool OptimizeIndicesOrder (std::vector<std::size_t> & triIndices,
                                    const std::size_t cacheSize,
                                    const std::size_t numberOfVertices)
{
   // On vérifie qu'il n'y a pas moins de trois indices, ou que le cache est trop
   // faible (auquel cas les cartes graphiques visées sont trop anciennes et un
   // système de triangle strips s'avère plus efficace
   if ((triIndices.size() < 3) || (triIndices.size() % 3 != 0) || (cacheSize < 4))
      return false;

   std::size_t numTriangles = triIndices.size() / 3; // 3 indices par triangle...
   std::size_t trianglesLeft = numTriangles; // Nombre de triangles restant à dessiner
   std::size_t numVertices = numberOfVertices;

   // On calcule le nombre de vertices s'il n'est pas connu (numberOfVertices == 0)
   if (numVertices == 0)
   {
      numVertices = *std::max_element (triIndices.begin(), triIndices.end());
      ++numVertices;
   }

Rentrons à présent dans le vif du sujet. La fonction prend donc en paramètre les indices du modèle 3D, la taille du cache (de base 32), ainsi que le nombre de vertices. On commence par vérifier si, notamment, le cache n'est pas inférieur à 4, puis on calcule plusieurs variables qui nous seront utiles. Si le nombre de vertices n'a pas été spécifié (non connu par exemple), on le calcule directement ici en utilisant std::max_element.

   // On crée un cache de la taille indiquée en paramètre, initialisé avec une
   // valeur négative
   LRUCache<int> cacheIdx (cacheSize, -1);

   // On crée deux vectors contenant nos données pour l'algorithme
   std::vector<TriData> triData (numTriangles);
   std::vector<VertData> vertData (numVertices);

Voici notre fameux cache LRU en action. Il est de taille cacheSize (normalement 32), et toutes les valeurs sont initialisées à -1. On crée enfin deux vector contenant nos structures précédemment définies.

   // Puis on initialise chaque triangle de la même façon, à part qu'on n’utilise pas
   // d'itérateurs (ben ouais, j'ai besoin de i dans ce cas...)
   for (std::size_t i = 0 ; i != numTriangles ; ++i)
   {
      triData.at(i).isAdded = false; // Le triangle n'est pas ajouté...
      triData.at(i).score = 0.0f;

      // On initialise les indices de chaque triangle avec le tableau passé en 
      // paramètre à la fonction
      triData.at(i).indices[0] = triIndices.at(i * 3);
      triData.at(i).indices[1] = triIndices.at(i * 3 + 1);
      triData.at(i).indices[2] = triIndices.at(i * 3 + 2);

      // Enfin, on ajoute l'indice de ce triangle à chacun des vertices qui
      // l'utilise
      vertData.at(triData.at(i).indices[0]).remainingTriangles.insert (i);
      vertData.at(triData.at(i).indices[1]).remainingTriangles.insert (i);
      vertData.at(triData.at(i).indices[2]).remainingTriangles.insert (i);
   }

Cette boucle est très simple. Elle initialise chaque structure TriData contenue dans le vector : on initialise son score à 0.0f, puis chaque indice est défini en utilisant les indices passés en paramètre de la fonction. Enfin, pour chacun des trois vertices qui composent ce triangle, on ajoute dans le std::set l'indice vers ce triangle. Plus un vertex aura de triangles qui l'utilisent, plus son score sera haut, et donc par la même occasion le score de son triangle associé.

   // On calcule le score pour chaque vertex. Étant donné qu'aucun des vertices
   // n'est actuellement dans le cache, seule la valence sera calculée
   for (std::vector<VertData>::iterator it = vertData.begin(),
        itEnd = vertData.end(); it != itEnd ; ++it)
   {
      it->score = std::powf (it->remainingTriangles.size(), -FindVertexScore_ValenceBoostPower)
                             * FindVertexScore_ValenceBoostScale;
   }

Une fois que les vertices ont correctement été initialisés en ajoutant les références vers les triangles qui les utilisaient, on calcule leur score. Les plus attentifs remarqueront que ce code n'est rien d'autre que la fin de la fonction CalculateScore contenue dans la structure VertData. En effet, à l'heure actuelle, aucun vertex n'est dans le cache, et plutôt que d'appeler la fonction CalculateScore et avoir plusieurs embranchements if/else, j'ai préféré calculer le score directement ici.

   // On calcule le score de chaque triangle et on récupère l'indice du triangle
   // ayant le score le plus haut
   float bestScore = 0.0f;
   int bestIdx = -1;

   for (std::size_t i = 0 ; i != numTriangles ; ++i)
   {
      triData.at(i).score = vertData.at(triData.at(i).indices[0]).score +
      vertData.at(triData.at(i).indices[1]).score +
      vertData.at(triData.at(i).indices[2]).score;

      if (triData.at(i).score > bestScore)
      {
         bestScore = triData.at(i).score;
         bestIdx = i;
      }
   }

On se charge ensuite de calculer le score de chaque triangle (qui est la somme des scores des trois vertices que le triangle utilise), puis on stocke le score ainsi que l'indice du meilleur triangle.

   // On arrive à présent dans le corps de l'algorithme. L'algorithme tournera tant
   // qu'il y aura des triangles à ajouter
   while (trianglesLeft != 0)
   {
      // On cherche dans tous les triangles non ajoutés si le score du triangle
      // trouvé est anormalement bas
      if (bestScore < 0.05f)
      {
         bestScore = 0.0f;
         bestIdx = -1;

         for (std::size_t i = 0 ; i < numTriangles ; ++i)
         {
            if ((!triData.at(i).isAdded) && (triData.at(i).score > bestScore))
            {
               bestScore = triData.at(i).score;
               bestIdx = i;
            }
         }
      }

On arrive à présent dans une boucle while, qui ne sera quittée que lorsque tous les triangles auront été traités et réorganisés. On vérifie tout d'abord si le meilleur score n'est pas anormalement bas. En effet, à part durant l'initialisation de l'algorithme, ensuite, seuls les triangles qui utilisent les vertices présents dans le cache seront vérifiés, dans un but de performance (pour un modèle de 8000 triangles, ça nous obligerait à vérifier 8000 triangles à chaque boucle, alors que là, on ne se contentera de vérifier que les triangles qui composent les 32 vertices du cache, donc au maximum, en assumant que chaque vertex est utilisé par 6 triangles, 32 * 6 = 192 triangles. De plus, cette approximation est plutôt efficace.

      // On récupère les trois vertices du meilleur triangle, on supprime, pour
      // chaque vertex utilisant ce triangle, l'indice vers celui-ci et, enfin,
      // on met à jour les indices
      std::size_t vertToAdd[3];

      for (std::size_t i = 0 ; i != 3 ; ++i)
      {
         vertToAdd[i] = triData.at(bestIdx).indices[i];
         vertData.at(vertToAdd[i]).remainingTriangles.erase (bestIdx);
         triIndices.at((numTriangles - trianglesLeft) * 3 + i) = vertToAdd[i];
      }
        
      // On met à jour l'état de ce triangle
      triData.at(bestIdx).isAdded = true;
      --trianglesLeft;

Pas grand-chose à dire. Les trois vertices du triangle qui vient d'être ajouté sont stockés dans un tableau, l'indice du triangle est supprimé du std::set, puis les indices des vertices sont ajoutés dans le std::vector qui contient les indices réorganisés. Enfin, on règle la variable isAdded du triangle sur true, et pour terminer, on réduit de 1 le nombre de triangles à ajouter. Facile.

      // À présent, on ajoute dans le cache les trois vertices qui composent le
      // meilleur triangle, et on cherche le prochain meilleur triangle (celui
      // ayant le plus haut score). On récupère également les indices des trois
      // vertices qui, éventuellement, sortent du cache, et on vérifie également
      // les triangles qui utilisent ces vertices
      bestScore = 0.0f;
      bestIdx = -1;
        
      for (std::size_t i = 0 ; i != 3 ; ++i)
      {
         int rejectedVertice = cacheIdx.insert (vertToAdd[i]);
            
         // On vérifie que l'indice n’est pas négatif (les indices négatifs sont
         // ceux ajoutés à l'initialisation du cache, qui ne représente pas de vrais
         // vertices)
         if ((rejectedVertice >= 0) && (rejectedVertice != vertToAdd[i]))
         {
            float oldScore = vertData.at(rejectedVertice).score;

            // Le vertex étant sorti du cache, seule sa valence est calculée
            float newScore = std::powf (vertData.at(rejectedVertice).remainingTriangles.size(), 
                                        -FindVertexScore_ValenceBoostPower)
                                        * FindVertexScore_ValenceBoostScale;
            vertData.at(rejectedVertice).score = newScore;

            float newScoreMinOldScore = newScore - oldScore;

            // On met à jour le score des triangles, et on vérifie si son score est
            // le plus élevé
            for (std::set<std::size_t>::const_iterator iter = vertData.at(rejectedVertice).remainingTriangles.begin(),
                 itEnd = vertData.at(rejectedVertice).remainingTriangles.end() ;
                 iter != itEnd ; ++iter)
            {
               triData.at(*iter).score += newScoreMinOldScore;

               if (triData.at(*iter).score > bestScore)
               {
                  bestScore = triData.at(*iter).score;
                  bestIdx = *iter;
               }
            }
         }
      }

Ça se complique un petit peu à présent. Le meilleur triangle a déjà été ajouté, il faut donc à présent trouver le meilleur triangle suivant. Comme nous l'avons dit plus haut, le meilleur triangle ne sera pas cherché à partir de TOUS les triangles du modèle 3D, mais juste à partir des triangles qui utilisent les vertices dans le cache. Cette approximation est plutôt bonne, car les scores des vertices présents dans le cache sont généralement bien supérieurs à ceux qui ne sont pas dans le cache, d'où le score de leur triangle est, la plupart du temps, largement supérieur aux autres triangles.

Ici, on récupère les trois vertices qui sont sortis du cache (oui, on ne teste donc pas 32 vertices pour une taille de cache de 32, mais de 32 + 3 éléments). Souvenez-vous que notre implémentation du cache LRU renvoie l'élément qui est sorti du cache si la taille maximale a été atteinte, ou alors l'élément qui vient d'être ajouté. On récupère donc cet indice, et on vérifie s'il n'est pas inférieur ou égal à 0 (souvenez-vous qu'on a initialisé toutes les valeurs à -1 au début), ou bien qu'il n’est pas égal au vertex qui vient d'être ajouté.

Une fois récupéré, le score de ce vertex est mise à jour, tout comme celui de chaque triangle qui l'utilise, et on vérifie si ce score est le plus haut. Si oui, on récupère l'indice et le score.

Cette opération est imbriquée dans une boucle for qui itérera trois fois (puisque trois vertices sont ajoutés dans le cache, il y a potentiellement trois anciens vertices qui sortent du cache).

      // Enfin, pour chaque vertex étant présent dans le cache, on met à jour leur
      // score ainsi que celui des triangles que chaque vertex utilise, et on recherche
      // le meilleur score
      for (std::size_t i = 0 ; i != cacheSize ; ++i)
      {
         int vertIdx = cacheIdx[i];
        
         // On vérifie que l'indice n’est pas invalide
         if (vertIdx >= 0)
         {
            float oldScore = vertData.at(vertIdx).score;

            // On calcule le nouveau score
            float newScore = vertData.at(vertIdx).CalculateScore (i, cacheSize);
            vertData.at(vertIdx).score = newScore;

            float newScoreMinOldScore = newScore - oldScore;

            // On met à jour le score des triangles, et on vérifie si son score est
            // le plus élevé                
            for (std::set<std::size_t>::const_iterator iter = vertData.at(vertIdx).remainingTriangles.begin(),
                 itEnd = vertData.at(vertIdx).remainingTriangles.end() ;
                 iter != itEnd ; ++iter)
           {
              triData.at(*iter).score += newScoreMinOldScore;

              if (triData.at(*iter).score > bestScore)
              {
                 bestScore = triData.at(*iter).score;
                 bestIdx = *iter;
              }
           }
        }
     }        
   }

   return true;

Dernière partie de l'algorithme. Nous avons mis à jour les scores des trois vertices potentiellement sortis du cache, on met à présent à jour le score des 32 vertices présents dans le cache, en appelant la fonction membre CalculateScore. Le score dépendant de la position dans le cache du vertex, on envoie donc le paramètre i, qui est la position dans le cache.

Puis on met à jour les scores des triangles, et on vérifie si le score est le meilleur. De la même façon, si oui, on récupère le score et l'indice du triangle. Et voilà, that's done !

Nos indices ont été à présent optimisés, mais il nous reste une ultime étape, qui peut apporter autant en termes de performance que l'optimisation des indices. En effet, il faut réorganiser également les vertices de manière à ce qu'ils soient en accord avec les indices, mais il ne faut surtout pas modifier l'ordre des indices que l'on a calculé auparavant. L'algorithme est plutôt simple : pour chaque indice, on vérifie si le vertex associé a déjà été ajouté. Si oui, on l'ajoute dans un nouveau tableau, et on met à jour le numéro du vertex vers lequel le tableau d'indices pointait. Une fois cette étape faite, on échange l'ancien tableau de vertices avec le nouveau :

void ReorderVertices (std::vector<std::size_t> & triIndices,
                             std::vector<float> & vertices)
{
   // Le nouvel ordre des indices, et une map pour savoir si l'indice a déjà été
   // ajoutée
   std::vector<float> newIndices;
   std::map<std::size_t, std::size_t> indices;
    
   std::size_t counter = 0;

   for (std::size_t i = 0 ; i != triIndices.size() ; ++i)
   {
      // Ce point a-t-il déjà été ajouté ?
     std::size_t idx = triIndices[i];

     if (indices.find (idx) == indices.end())
     {
        newIndices.push_back (vertices[idx * 3 + 0]);
        newIndices.push_back (vertices[idx * 3 + 1]);
        newIndices.push_back (vertices[idx * 3 + 2]);

        indices[idx] = counter;
        triIndices[i] = counter++;
     }
     else
        triIndices[i] = indices[idx];
   }
    
   // On échange les tableaux de vertices
   vertices.swap (newIndices);
}

Un mécanisme similaire doit être fait pour les normales et les indices de texture.

Nous allons à présent apprécier les résultats que l'algorithme nous apporte. Pour cela, il existe un nombre, l'ACMR : Average Cache Miss Ratio, qui permet de nous indiquer, comme son nom l'indique, une moyenne du défaut de cache. Le score maximum théorique est de 0.5 (mais ne reste que théorique. Pour l'atteindre, il faudrait en effet un cache extrêmement gros), tandis que le pire score possible est de 3.0.

Voici les résultats de l'ACMR pour un modèle de 5544 triangles (les mesures de temps ont été prises sur un AMD Athlon XP 3000+).

Merci à Tom Forsyth pour son algorithme, et à loneshock de Gamedev.net pour son implémentation de l'algorithme.