Accueil › Articles

Depuis longtemps, les infographistes s’efforcent de modéliser le réel, l’objectif étant de concevoir des univers aussi saisissants que la réalité. On peut faire remonter ces premières tentatives aux réflexions de spécialistes de la physique et de l’informatique appliquées. Cet article étudie ainsi la modélisation de vagues océaniques au rendu réaliste. Pour améliorer les performances de notre solution, nous partirons d’une charge applicative multifile (multi-threaded) traitée sur ordinateur biprocesseur. Nous en fournirons une implémentation capable d’un traitement en temps réel sur une solution graphique intégrée telle que les jeux de composants de la famille des chipsets Intel® 965 Express.

En premier lieu, nous listerons les travaux existants. Ensuite, nous poserons les bases mathématiques de l’approche par la somme des ondes sinusoïdales qu’exploite notre implémentation. Enfin, nous expliciterons notre implémentation, notamment quant aux mécanismes employés pour la parallélisation (threading). Nous fournirons par ailleurs le code source à utiliser dans les extensions et l’implémentation de rendu océanique multifile que le lecteur souhaiterait lui-même réaliser.

Un certain nombre de chercheurs se sont déjà penchés sur la modélisation de l’eau. Parmi les travaux les plus probants, notons ceux de Jerry Tassendorf, dont les modélisations ont été utilisées pour les effets spéciaux de films de cinéma tels que Titanic et Waterworld  [5] [6] Depuis, d’autres chercheurs et développeurs ont étudié la question, sous l’angle de la simulation en temps réel. Dans son ouvrage Interactive Simulation of Water Surfaces, Miguel Gomez [2] décrit ainsi une solution implicite pour les champs de hauteur d’eau, que l’on pourra adopter dans certains cas, mais dont le désavantage majeur est qu’elle impose la gestion d’au moins deux maillages (le maillage en cours et le précédent) pour le calcul du suivant. Son autre inconvénient est qu’elle contraint à obtenir des informations de voisinage pour le calcul de la position suivante de chaque sommet (vertex). A l’inverse, dans son ouvrage Effective Water Simulation from Physical Models, [3] Mark Finch propose une solution, explicite elle aussi, qui se dispense de ces informations et qui s’assortit de toute une série d’avantages 

Dans son ouvrage Rendering Ocean Water, [4] John Isidoro emploie une approche par somme des sinus, très comparable à la méthode décrite en [3]. Ces deux auteurs présentent, pour implémentation, le code du nuanceur de pixels et de sommets correspondant, au niveau de l’assemblage, et passent en revue la technique de leur assemblage DirectX* en bas niveau. Nous proposons quant à nous un algorithme sur CPU, inspiré de [3] et mappable en HLSL (High-Level Shader Language) ou à laisser sur CPU.

Nous allons d’abord passer en revue certaines définitions de base en physique des ondes. [Giancoli85] [3]
Amplitude: Hauteur maximale d’une crête ou d’un creux de vague par rapport au niveau normal. L’ampleur de l’oscillation est l’amplitude multipliée par 2.
Longueur d’onde (L). Distance entre deux crêtes successives.
Vitesse de déplacement. Vitesse à laquelle la vague se déplace par unité de temps. Cette vitesse est représentée par la constante de phase φ, avec φ = vitesse × 2π/L.

3.1 Génération de vagues par la somme des sinus

Figure 3-1.Physique des ondes.

Sur la figure 3-1. La longueur d’ondes L est la distance entre deux crêtes, la vitesse de déplacement est la distance que parcourt une vague pendant une unité de temps et l’amplitude est la distance de l’origine au sommet d’une crête.

3.2 Modélisation statique

Commençons par les bases. De cette manière, si certains paramètres sont inutiles dans le cas particulier d’une application, on pourra les éliminer et suivre la procédure ci-dessous pour obtenir la géométrie ondulatoire procédurale qui convient. Tout d’abord, comme nous souhaitons que nos vagues bénéficient d’un paramétrage périodique et modifiable, nous optons pour une onde sinusoïdale.

Nous souhaitons par ailleurs rester, pour nos modélisations, dans un espace normé où toutes les valeurs obtenues pour la hauteur de chaque onde sinusoïdale sont comprises entre 0 et 1. Il nous paraît plus facile, de cette manière, de réfléchir à ce qu’il nous faut faire pour tenir compte de la réalité. En l’occurrence, notre onde sinusoïdale ne doit donner aucune valeur négative :

En revanche, après cette opération, certaines valeurs sont susceptibles d’être strictement supérieures à 1. Nous allons donc modifier l’échelle des résultats pour qu’ils soient strictement compris dans l’intervalle [0,1] :

Souvent, et tout particulièrement pour la modélisation de vagues océaniques, ces grandes oscillations sinusoïdales sont préférables. Néanmoins, il arrive fréquemment que l’on souhaite obtenir des vagues plus pentues (à inclinaisons plus forte), par exemple pour signaler l’approche d’une tempête. Pour reproduire cet effet, on ajoute une puissance (inclinaison) à la formule de notre modélisation :

Ensuite, nous souhaitons pouvoir paramétrer la hauteur de la vague (amplitude). Nous introduisons donc dans notre formule un facteur de démultiplication :

3.3 Modélisation dynamique

Nous disposons à présent d’une onde sinusoïdale dont nous pouvons régler l’inclinaison et l’amplitude. En revanche, nous souhaiterions également pouvoir en maîtriser la surface. Ainsi, nous voudrions par exemple pouvoir prendre en compte la vitesse et la direction de la vague ainsi que sa longueur d’onde.

Dans la mesure où la modélisation porte sur un champ de hauteur d’eau bidimensionnel, il nous faut envisager le mouvement dans chacune des deux directions. Pour ce faire, nous projetons la position (Pos) en abscisses et en ordonnées (x,y) sur un vecteur de direction d’onde (Dir) à l’aide d’un produit scalaire (•). Pour des raisons de simplification, nous partons du principe que le vecteur directionnel est parallèle à la surface plane et qu’il n’a donc pas de cote (z). Le produit scalaire de deux vecteurs est une valeur scalaire, que nous nommons S.

Ensuite, nous souhaitons prendre en compte la fréquence de l’onde. Or les lois de la physique nous rappellent que la longueur d’onde (L) est fonction de la fréquence, avec fréquence = 2π/L. Nous pouvons donc utiliser la longueur d’onde en entrée et en déduire la fréquence à l’aide de cette formule. Comme nous souhaitons que la périodicité des valeurs produites par notre fonction sinusoïdale soit fonction de cette fréquence, nous intégrons cette variable à la formule :

Nous disposons à présent d’une onde dont la position est déterminée par sa direction et sa longueur d’onde, mais qui ne se déplace pas encore en surface. La dernière variable à introduire est donc celle qui permet de faire varier la vitesse de déplacement de la vague. Là encore, la physique nous apprend que la constante de phase φ est fonction de cette vitesse de déplacement. Elle est donnée par la formule suivante :

Nous transformons donc notre formule de la manière suivante, où t représente le temps :

En résumé, nous disposons à présent d’une fonction qui fait intervenir à la fois la longueur d’onde, l’amplitude, la vitesse de déplacement, la direction, la position et l’inclinaison d’une vague :

où
et

3.4 Composition de l’onde

Une seule fonction sinusoïdale suffirait si notre modélisation était simple, mais, pour reproduire au mieux une surface océanique, il nous faut un plus fort niveau de variabilité. En observant la surface d’un océan, on s’aperçoit en effet que le mouvement de l’eau procède de la rencontre de vagues venant de plusieurs directions et dont l’interférence crée des pics, des creux, etc. Pour modéliser ce phénomène, nous allons faire entrer en jeu plusieurs vagues en effectuant la somme de leurs positions en n’importe quel point de notre modélisation. Nous avons choisi de limiter le nombre de nos ondes sinusoïdales à quatre, après avoir constaté que ce chiffre fournissait un niveau de variabilité acceptable. Pour simuler la hauteur d’une position (x,y), nous avons la formule suivante :

3.5 Normales de surface

Pour nuancer la surface, il est important de connaître le vecteur normal de celle-ci (normale). Si nous faisions appel à une surface texelisée, nous pourrions actualiser la position de chaque sommet grâce à la formule n° 3 ci-dessus, pour ensuite recalculer les normales de surface et en calculer la moyenne pour chaque sommet. Il existe cependant une autre solution qui mérite qu’on l’envisage : c’est la solution explicite présentée en [3]. On peut prendre les dérivées dans les directions x et y pour déterminer le taux de modification de la normale de surface, quels sont respectivement les vecteurs binormal et tangent (binormale et tangente). Or nous avons montré plus haut qu’une position (x,y) donnée a une hauteur de surface correspondant à la formule Position(x,y,t) = [x,y,f(x,y,t)]. La binormale et la tangente d’un champ de hauteur d’eau (en supposant, pour des raisons de simplicité, que cette hauteur est orientée par rapport à une grille x-y) sont :

, ce qui se simplifie en
et

[il manque une formule ici], ce qui se simplifie en

Le produit vectoriel est donc :

, soit

A présent, il nous reste à calculer la dérivée de chaque fonction f(x,y,t) et à en faire la somme pour chaque onde sinusoïdale que nous composons afin d’obtenir la position finale. Pour ce faire, nous calculons la différentielle de f(x,y,t) sur x et y pour chaque onde qui compose notre modélisation géométrique :

où

De même, la différentielle sur x est :

Pour la normale de surface finale, nous calculons chaque composant comme suit et nous normons le résultat :

3.6 Parallélisation

De nombreux concepteurs de moteurs de jeu ont déjà fait appel à la parallélisation, en général pour des fonctions qui se prêtent à un threading au niveau des tâches. En revanche, s’ils l’ont fait, ce n’est pas tant pour stimuler les performances que pour simplifier la programmation. Or notre propos dans cet article est précisément de faire appel à la parallélisation pour renforcer les performances. Nous allons cependant nous limiter à une parallélisation dans sa plus simple expression, sur deux files uniquement, la première qui se chargera de l’initialisation, du rendu et d’autres fonctions d’un moteur de jeu, et l’autre de la modélisation des vagues.

Schématiquement parlant, un jeu se décompose en effet en trois tâches : initialisation, actualisation de l’univers virtuel et rendu. Puisque l’actualisation de la scène doit intervenir à chaque image et que c’est de la parallélisation de cette opération que nous tirerons le plus grand profit, c’est donc la partie correspondante de la charge logicielle que nous allons paralléliser. La figure 3-2 montre ainsi la répartition de cette charge : la file A gère l’initialisation du jeu et le rendu, tandis que la file  B se charge de la position des sommets et de la génération du vecteur normal de la modélisation.

Il convient ensuite de réfléchir aux conséquences de la parallélisation d’une application graphique. Sachant que la parallélisation de DirectX risque de faire considérablement baisser les performances applicatives, nous préférons éviter cette situation. La raison de cette baisse est que, dans sa version « threadsafe », DirectX n’autorise l’entrée dans l’API que d’un fil à la fois. Or, si cela ne présente pas d’inconvénients dans certains cas, nous décidons, pour notre modélisation, de ne confier l’ensemble du rendu qu’à une seule file.

Figure 3-2. Modélisation sur deux files.

Schéma d’une simulation sur deux files qui indique l’équilibrage des charges de modélisation à chaque itération de la bouche de rendu. Tn représente la durée de l’opération sur chaque file.

La file A est la file principale. Elle pilote l’initialisation, le moteur d’intelligence artificielle (AI), les interactions avec l’utilisateur, le rendu et la séquence d’arrêt. La file B est celle qui effectue la modélisation. Dans le cas présent, la file A restera inemployée puisque la modélisation ne porte que sur les vagues. L’objectif de la répartition équitable du travail entre les files A et B est qu’aucune des deux files ne soit inoccupée en attendant que l’autre termine sa tâche ou, du moins, que la durée d’inoccupation soit la plus courte possible. Cette technique d’équilibrage est d’ailleurs à généraliser au fur et à mesure que l’on fait augmenter le nombre de files. Pour bénéficier au maximum de la parallélisation, il faut en effet répartir la charge logicielle aussi équitablement que possible entre les files disponibles.

Notre première implémentation s’inspirait de [2]. However, the need for neighbor information does not make it amenable to a parallel implementation(¹). De plus, le fait de ne pas disposer de paramètres pour piloter la surface était rédhibitoire. Modéliser la surface océanique comme s’il s’agissait d’une membrane élastique nous contraindrait en effet à une approche de type « lancer, puis laisser faire », alors que nous souhaitons au contraire obtenir une simulation reproductible d’une vague qui monte et qui descend. C’est pourquoi nous avons préféré l’implémentation décrite en [3], dont les divers avantages sont abordés au chapitre 2 de l’ouvrage en question.

Figure 4-1. Modélisation de vagues océaniques.

Les commandes de paramétrage pour chaque onde sinusoïdale se situent en haut à gauche. Elles déterminent les propriétés de surface. A droite, un bouton permet de basculer entre une implémentation parallèle et séquentielle, de régler le mode de calcul des normales et d’enregistrer le paramétrage pour pouvoir s’en resservir plus tard. Cette modélisation est adaptée de la démo BasicHLSL issue de [11].

4.1 Interface utilisateur

L’une des caractéristiques des travaux exposés en [3] est la possibilité qu’ils offrent d’un pilotage complet de l’ensemble des paramètres surfaciques, ce qui est également le cas de notre implémentation : amplitude, velocity, direction, and the exponent from Equation 2. Additionally, these parameters can be saved and recalled for later simulations. Un bouton situé sur la droite de l’interface permet par ailleurs de comparer les versions parallélisée et séquentielle de la démo. Enfin, il est possible de faire disparaître les commandes afin qu’elles ne masquent pas la modélisation.

4.2 Implémentation C++ de la somme des sinus avec exposant

Nous allons présenter à présent la méthode employée pour paralléliser la somme des sinus sur CPU. Il s’agit d’une adaptation directe de la formule n° 2.

void CSinWaterMesh::TakeStepSumOfWavesWithExp( float t, 
                                               int numOfWavesToSum )
{
   for( int i=0; i
   {
      for( int j=0; j
      {
         for( int k=0; k
         {
            CVector3 posVect;
            float dotresult = 0.0f;
            float phase_constant = 0.0f;
            float final = 0.0f;
            posVect.Init( m_pVB[i*m_iNumCols+j].x,         
                          m_pVB[i*m_iNumCols+j].y, 
                          0.0f );
            if( m_bSumWave[k] )
            {
               dotresult = m_direction[k].Dot( &posVect );
               dotresult *= ( 2*(float)MYPI ) / m_wavelength[k];
               phase_constant = t*
                  ( (m_speed[k]*2*(float)MYPI) / m_wavelength[k] );
               final = ( dotresult + phase_constant );
               final = ( sin(final) + 1.0f ) / 2.0f;
  &



nbsp;            final = m_amplitude[k] * pow( final, m_kexp[k] );
            }
            else
            {
                final = 0.0f;
            }
           
            if( k!=0 ) 
            {
               m_pVB[i*m_iNumCols+j].z += final;
            }
            else
            {
               // The first wave calculated will overwrite the 
               // summation from the last frame.
               m_pVB[i*m_iNumCols+j].z = final;
            }
         }
      }
   }
}

4.3 Calcul des normales

L’équation n° 4 représente le calcul explicite des normales et c’est aussi l’approche dont nous pensions qu’elle serait la meilleure. Pourtant, il nous a finalement semblé largement plus rapide de calculer les normales des sommets en effectuant la moyenne des normales des faces. Le secret de l’accélération de cette implémentation réside dans le fait de savoir quels sont les voisins de chaque sommet sans avoir à rechercher cette information à chaque image. Pour ce faire, nous pré-calculons la liste de leurs voisins à chacun. A noter que cette opération n’est pas possible pour une implémentation DirectX 9 sur GPU puisque l’on n’a pas accès aux données de voisinage ; sur le CPU, en revanche, elle est beaucoup plus rapide que le calcul à partir de la dérivée. Donc, même si le recours à l’équation n° 4 reste la meilleure méthode pour calculer les normales sur GPU, sur CPU en revanche, l’établissement classique de la moyenne des normales des faces est plus rapide, y compris si l’on tient compte, bien entendu, du calcul des nouvelles normales des faces.

4.4 Parallélisation

Dans le cadre de la première implémentation, l’objectif était d’obtenir une version parallélisée de la démo pour actualiser les normales surfaciques et la position. La méthode la plus simple pour y parvenir a été de créer une fonction qui encapsule la fonction d’actualisation du maillage sur une file et qui crée une nouvelle file à chaque fois qu’une actualisation de ce maillage est nécessaire. Ainsi donc, une nouvelle file doit se lancer à chaque nouvelle image et calcule les nouvelles valeurs de hauteur du maillage. Au bilan, cette méthode fonctionne, certes, mais les performances se sont révélées mauvaises.

Pour la seconde implémentation, le modèle des files à la demande a été remplacé par un système de pool de files. Or, comme nous n’avons besoin pour notre implémentation que d’une seconde file pour suppléer la file principale de rendu, le pool n’en comporte donc qu’une seule. Le principe d’un pool est la création des files au démarrage pour qu’elles soient à la disposition de la file principale le moment venu. Cette démarche a l’avantage de supprimer la pénalisation que représente le fait de fermer les files à chaque fois que l’une d’elles est requise ; l’inconvénient, en revanche, est que des ressources sont affectées aux files même lorsqu’elles sont inoccupées. De plus, selon que l’on mette en œuvre un pool ou non, il se peut que certaines files consomment inutilement des cycles CPU durant les boucles d’attente. Pour y palier, on peut recourir à une stratégie de scrutation (polling) périodique ou faire appel à un objet de synchronisation du système d’exploitation. Le principe consiste à ne pas se retrouver coincé dans un « spin loop », mais de n’effectuer une scrutation que périodiquement pour voir si les données nécessaires sont présentes. L’idée était de réduire les temps système induits par la seconde file, en n’en créant qu’une seule et en supprimant cette charge de la boucle de rendu. Pour simuler un vrai moteur de jeu, nous ajoutons une charge logicielle à traiter en file A pendant que la file B calcule le maillage et les normales. La durée du traitement de cette charge est variable. Elle est là pour reproduire les autres aspects de la modélisation qui interviennent indépendamment du résultat du solveur de vagues. Il s’agit par exemple des interactions avec l’utilisateur, d’autres calculs physiques (détection des collisions, etc.), les calculs d’AI, etc. S’il s’agissait d’effectuer une modélisation de l’eau, le travail pourrait se répartir au niveau des tâches, en affectant le travail des calculs de surface à une file et la génération des normales à une autre, mais il existe aussi une autre solution, qui consiste à effectuer une décomposition au niveau des boucles et à traiter une partie de la grille sur une file et une autre partie sur une autre file, avec un certain temps système quand les grilles sont assemblées si des informations de voisinage sont requises.

Création d’une file

Pour créer une file, nous employons la fonction __beginthreadex(…). Si nous choisissons cette implémentation, c’est comme compromis entre les fonctions Win32 et les implémentations C en exécution (runtime) de la parallélisation abordée en [1]. En fait, la fonction __beginthreadex(…) pose moins de problème est elle est plus fiable que CreateThread(..), tout en possédant les mêmes fonctionnalités, et c’est d’ailleurs ce que notre expérimentation a confirmé. La documentation de Microsoft Visual Studio .Net* 2005 indique d’ailleurs que le recours à CreateThread(..) en exécution C risque de provoquer de légères fuites de mémoire lorsque la file appelle ExitThread(…).

#include 
HANDLE hThreadHandle;  //unsigned long
DWORD dwThreadid;
.
.
hThreadHandle = (HANDLE) _beginthreadex(void *security, 
                                   unsigned stack_size, 
                                   unsigned (_stdcall *)(void *), 
                                   void *arg, 
                          

;         unsigned initflag, 
                                   unsigned *threadaddr, 
);

Les paramètres de l’appel __beginthreadex(…) sont, pour le premier, des attributs de sécurité hiérarchiques. Si on lui affecte la valeur NULL, le niveau de sécurité de la file sera défini par défaut. Le deuxième est la taille de la pile : si ce paramètre est défini sur zéro, cette taille sera la même que celle de la file en cours. Le paramètre suivant est l’adresse de la fonction utilisateur que la nouvelle file appellera lorsqu’elle entamera son exécution. Les trois paramètres restants sont : arg, qui est une valeur transmise à la nouvelle file, initflag, qui est une marque (flag) de pilotage de l’état de la file à la création de celle-ci, et, enfin, une adresse où écrire l’identifiant de la file. Voici le code correspondant à cet appel dans notre application :

hThreadHandle = (HANDLE) _beginthreadex( NULL, 
                                   0, 
                                   LaunchTakeStepThread,
                                    (void*)&g_time, 
                                   0,
                                    (unsigned int*)&dwThreadId );

Exécution des files

A présent que la file a été créée, elle attend, via la fonction sleep(), qu’il lui soit demandé d’intervenir. Il est transmis à cette fonction la durée d’attente, exprimée en millisecondes. Si elle reçoit une valeur nulle, elle abandonne sa tranche de temps en cours et attend d’être rappelée. Lorsque nous sommes prêts pour l’exécution des files, la file maîtresse l’indique à la file auxiliaire par l’incrémentation d’une variable partagée, qui est un emplacement dans la mémoire que les deux files partagent. Si la file maîtresse incrémente cette valeur, c’est pour indiquer à son auxiliaire qu’elle a consommé les valeurs et qu’elle est prête pour le maillage suivant. La file auxiliaire calcule l’ensemble de données suivant, fixe cette valeur et passe en veille jusqu’à ce qu’elle soit réactivée par la file maîtresse. C’est ce que l’on appelle une relation « producteur-consommateur ».

Le corps de la file auxiliaire (producteur) est le suivant :

while(we are not exiting the thread)
{
      TakeStep();
      Time += Time_Increment;
      bStepComplete = true;
      while(bStepComplete && !bExitThread)
      {
            Sleep(0);
      }
}

La file maîtresse « consomme » le maillage produit par son auxiliaire et lui indique de poursuivre et de calculer le maillage suivant.

while(1)
{
while(!bStepComplete)
{
      // Wait for the grid update to finish
Sleep(0);
}
 
//Copy the vertex info to the “real” VB.
g_pGrid->CopyVBToRenderVB();
 
//Allow the other thread to compute a new set of vertices
g_pGrid->ResetStepComplete();  //resets bStepComplete
}

La fonction ResetStepDone() dépend de la méthode d’exclusion mutuelle. Pour le code de la section critique, il faut saisir celui-ci, fixer une valeur, puis laisser cette section ; pour l’interblocage, nous allons employer un décrément interbloqué. Les deux sont abordés en partie 4.5 de cet article.

Suppression des files

Dans le cadre de l’implémentation décrite ci-dessus, la file auxiliaire se supprime automatiquement lorsque la fonction lancée par _beginthreadex(…) arrive au bout. Dans certains cas, cette suppression pourrait nécessiter _endthreadex(..), mais cela n’a pas été le cas dans notre implémentation.

4.5 Mutual Exclusion

Comme nous l’avons mentionné dans la partie « Exécution des files », notre modélisation peut se résumer à une relation producteur-consommateur, où la file auxiliaire est le producteur de maillages de vagues, et la file principale le client. Dans le cadre d’une telle relation, le producteur place en général les éléments de données terminés dans un espace de stockage d’où le consommateur les retire pour les consommer. La taille de cette file d’attente limite ainsi l’« avance » que peut prendre le producteur sur le consommateur. Nous avons décidé d’assumer à chaque image la charge correspondant à la synchronisation ainsi que de ne pas permettre au producteur de passer aux données de l’image suivante avant que celles de l’image en cours n’aient été consommées. La raison en est que, dans de nombreux jeux, l’image suivante est fonction de données de l’image en cours (calculs d’AI ou de physique, commandes du joueur, etc.)

Dans notre implémentation, la synchronisation s’effectue au moyen d’une scrutation d’une variable d’état m_bStepDone, lancée par les deux files, qui indique si le maillage a été actualisé depuis la consommation du précédent. Pour protéger cette variable, nous avons expérimenté deux des méthodes d’accès synchronisé abordées dans l’ouvrage d’Aaron Cohen, Win32 Multithreaded Programming: interlocked accesses and critical sections [1] : les accès interbloqués et les sections critiques. Le choix entre les deux est fonction de l’application concernée. L’interblocage est en général plus simple, et à privilégier dans le cas du recours à une variable partagée. Les sections critiques sont quant à elle plus générales et peuvent s’employer n’importe où dans le code pour encapsuler des parties de celui-ci ou des données à un niveau de granularité plus grossier. L’exemple qui accompagne cet article autorise la compilation des deux implémentations. On les considère comme les primitives de synchronisation les plus rapides sous Windows*.

L’interblocage des accès se réalise grâce à une série de fonctions qui établissent une correspondance directe avec des instructions CPU atomiques pour les scénarios lecture-mofification-écriture. Ces opérations empêchent que les variables ne passent en état incorrect à cause de problèmes d’ordre de lecture-écriture entre les files.

Les fonctions d’interblocage ne sont qu’au nombre de trois : InterlockedIncrement(), InterlockedDecrement() et InterlockedExchange().Les deux premières autorisent respectivement l’incrémentation ou la décrémentation d’une longue valeur ; la troisième permet le remplacement d’une valeur par une autre en une seule et même opération atomique.

Les sections critiques sont des primitives de synchronisation qui peuvent servir à protéger du code ou des données grâce au principe d’exclusion mutuelle. Avant d’exécuter le code protégé ou d’accéder à la mémoire protégée, une file doit d’abord acquérir la section critique. Si cette dernière n’est pas disponible, ce qui se produit lorsqu’une autre file se l’est déjà appropriée, la première file est bloquée jusqu’à ce que cette section soit disponible. A noter qu’en fonction de l’application, la même instance d’une section critique peut protéger plusieurs types de ressources, de code, de données ou les trois.

Propriétés Visual Studio

Vérifiez que les propriétés de Virtual Studio sont correctement paramétrées et, en particulier, les marquages (flags) pour VC++ : Project > Properties > Configuration Properties C/C++ > Code Generation > Runtime Library > sélection de la bibliothèque parallélisée qui convient. La figure 4-2 montre où cette sélection s’effectue dans la fenêtre Property Pages de la rubrique « Runtime Library ».

Figure 4-2. Emplacement des pages de propriétés à la rubrique « Runtime Library ».

5.1 Optimisation du code

Après avoir constitué la charge applicative, nous nous sommes servi de l’analyseur de performances VTune™. Or cet outil nous a montré que la file auxiliaire passait la majeure partie de son temps à exécuter la fonction LookupTriIndex() pour consulter six fois les indices des triangles des sommets, afin de déterminer de quelles normales de triangles il faut effectuer la moyenne pour calculer celle du sommet. La fonction LookupTriIndex() est elle-même linéaire, aussi l’ensemble de la procédure de calcul de la normale est O(n²). Il fallait donc recommencer cette procédure. L’alternative était d’accélérer le processus de consultation des normales ou bien de calculer celles-ci directement à l’aide des dérivées partielles des formules de vagues. De manière à permettre une comparaison, nous avons réalisé les deux, sans toucher non plus à l’algorithme d’origine.

Figure 5-1. Comparaison des performances monoprocesseur (UP) et biprocesseur (DP).

La figure 5-1 représente la fréquence image pour trois tailles de maillage. On a comparé deux implémentations, l’une sur configuration monoprocesseur (« UP »), l’autre sur système biprocesseur (« DP »). Au fur et à mesure de leur traitement, les charges applicatives augmentent et représentent la modélisation d’autres fonctions du moteur de jeu (AI, détection des collisions, etc.)

5.2 Analyse des performances

Il convient d’envisager plusieurs vecteurs de performances. Pour valider notre implémentation, nous avons ainsi mis en place trois charges applicatives pour modéliser trois scénarios distincts, chacun allongeant la durée de traitement par le processeur n° 1 et celle de demande des résultats à la file n° 2. Dans le cas d’un processeur unique, les performances décroissent au fur et à mesure que la charge applicative modélisée augmente, ce qui est logique : l’ampleur des tâches est plus importante alors que seul un processeur y est affecté. A noter que, sur configuration biprocesseur, il n’y a que très peu de différences de performances (en fréquence image, exprimée en images par seconde [IPS, FPS en anglais]) en valeur absolue entre les trois cas : aucune charge (« No workload » sur le diagramme), charge n° 1 (« Workload 1 ») et charge n° 2 (« Workload 2 »). Pour dire les choses autrement, à condition que la charge soit correctement équilibrée, la charge n° 2 est nulle ou quasiment. En revanche, pour l’ensemble des trois maillages (Mesh 1, 2 et 3 ), la charge n° 3 fait effectivement chuter la fréquence image sur un système biprocesseur, ce qui montre que la charge modélisée sur la file principale est à présent plus longue à s’exécuter que la génération du maillage et des normales sur la file auxiliaire. Les performances sont donc maintenant bridées par la charge simulée et non pas par les calculs géométriques.

5.3 Equilibrage de la char

Sous l’angle des performances relatives, on constate que, sans charge modélisée pour la file principale, l’avantage d’un traitement sur deux processeurs s’amoindrit au fur et à mesure que la taille du maillage augmente. Avec les charges n° 1 et 2, et pour les deux maillages les plus grands, nous savons que les performances absolues restent inchangées, donc les performances relatives sont meilleures avec une charge plus importante. On peut se demander comment il est possible que ces performances absolues puissent décroître alors qu’en termes relatifs, elles augmentent, comme en atteste le comportement de la charge n° 3 pour les deux maillages les plus grands. Cette situation indique en fait que la charge n° 3 est « plus proche » de l’équilibre idéal que la charge n° 2 à cette taille de maillage. Sans doute pourrait-on situer l’équilibre idéal à mi-chemin entre les charges n° 2 et 3. Le résultat essentiel est logique : on parvient à des performances parallèles optimales lorsque chaque file traite une charge relativement importante par rapport aux temps système induits par la parallélisation et que les charges sont bien équilibrées entre elles.

Alors même que nous avons atteint l’objectif que nous nous étions fixé pour la géométrie des vagues océaniques, il n’en reste pas moins diverses questions à aborder pour parvenir à une modélisation réellement convaincante. En premier lieu, nous souhaiterions à présent calculer les mappes des normales avec la même base que pour nos vagues océaniques, ce qui améliorera notre modélisation et rendra plus fidèlement compte des composantes ondulatoires à plus haute fréquence que produit le vent à la surface de l’eau. (Il ne s’agira pas d’une vraie géométrie, mais cette modélisation aura tous les inconvénients et les avantages de mappes de normales dans d’autres situations.) Il existe également un certain nombre de techniques qui nous permettraient d’améliorer l’éclairage et le nuancement de la surface et, surtout, le calcul de l’éclairage en prenant en compte les vecteurs de réflexion et de réfraction. Nous souhaiterions également associer à notre implémentation certaines des techniques présentées en [8], afin d’améliorer cet éclairage par des techniques d’imagerie à grande gamme dynamique (High Dynamic Range Imaging, HDRI). Nous voudrions également étudier la modélisation de l’écume à la surface de l’eau.

En ce qui concerne la parallélisation, il nous reste là aussi quelques questions à étudier. Nous souhaiterions ainsi comparer cette implémentation à une autre avec décomposition au niveau des boucles. En outre, nous aimerions étudier dans quelle mesure cette implémentation se redimensionne avec des files supplémentaires, l’expérimenter en répartissant les files entre le CPU et le GPU ainsi que faire appel à un objet au niveau du système d’exploitation pour la synchronisation des files.

Adam Lak est ingénieur logiciel senior au groupe Sotware Solutions d’Intel. Spécialisé dans les algorithmes et architectures d’infographie, il dirige le projet Modern Game Technologies.

David Reagin est ingénieur logiciel chez Intel. Avant de se consacrer au développement graphique et à sa promotion, il a validé des études de microprocesseurs pendant sept ans. Il est titulaire d’une licence (B.S.) d’informatique du Georgia Institute of Technology (Atlanta).

1. [Cohen98] Aaron Cohen et Mike Woodring, Win32 Multithreaded Programming, O’Reilly & Associates, 1998.

2. [Gomez00] Miguel Gomez, « Interactive Simulation of Water Surfaces », Game Programming Gems 1, publié sous la direction de Mark Deloura, pages 187-194.

3. [Finch04] Mark Finch, « Effective Water Simulation from Physical Models », GPU Gems: Programming Techniques, Tips, and Tricks for Real-Time Graphics, publié sous la direction de Randima Fernando, pages 5-29, 2004.

4. [Isidoro02] John Isidoro, Alex Vlachos et Chris Brennan, « Rendering Ocean Water », Direct3D ShaderX: Vertex and Pixel Shader Tips and Tricks, pages 347-356, 2002.

5. [Tessendorf01] « Simulating Ocean Water », polycopié SIGGRAPH2001, 2001.

6. [IMDB04] Fiche du film Titanic (http://us.imdb.com/title/tt0120338/).

7. [Vterrain04] « Water Rendering Simulation », site Internet Virtual Terrain Project (VTP), 2004 (http://www.vterrain.org/Water/).

8. [Lake04] Adam Lake et Cody Northrop, « Real-Time High Dynamic Range Environment Mapping », Intel Software Network.

9. [QuickMath04] QuickMath, 4 novembre 2004(http://www.quickmath.com/).

10. [Giancoli85] Douglas Giancoli, Physics, Principles with Application, deuxième édition, Prentice Hall, Inc., 1985.

11. [MSSDK04] SDK Microsoft DirectX 9.0, mise à jour de l’été 2004, août 2004 (http://www.microsoft.com/downloads/search.aspx?displaylang=en&categoryid=2).

(¹) Nous ne prétendons pas la chose impossible, mais simplement qu’elle est plus compliquée que la solution explicite que nous avons choisi de mettre en œuvre.

Reportez-vous à notre Notice d'optimisation pour plus d'informations sur les choix et l'optimisation des performances dans les produits logiciels Intel.

Commentaires (5)

Trackbacks (0)

Réagir  

Nom (obligatoire)*

Email (obligatoire, mais pas d'affichage ici)*

Votre URL (facultatif)


Commentaire*