PROGRAMMATION DE JEU

v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}

st1\:*{behavior:url(#ieooui) }
<!– /* Font Definitions */ @font-face {font-family:Wingdings; panose-1:5 0 0 0 0 0 0 0 0 0; mso-font-charset:2; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:0 268435456 0 0 -2147483648 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-parent:”"; margin:0cm; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:”Times New Roman”; mso-fareast-font-family:”Times New Roman”;} a:link, span.MsoHyperlink {color:blue; text-decoration:underline; text-underline:single;} a:visited, span.MsoHyperlinkFollowed {color:purple; text-decoration:underline; text-underline:single;} p {mso-margin-top-alt:auto; margin-right:0cm; mso-margin-bottom-alt:auto; margin-left:0cm; mso-pagination:widow-orphan; font-size:12.0pt; font-family:”Times New Roman”; mso-fareast-font-family:”Times New Roman”;} @page Section1 {size:595.3pt 841.9pt; margin:70.85pt 70.85pt 70.85pt 70.85pt; mso-header-margin:35.4pt; mso-footer-margin:35.4pt; mso-paper-source:0;} div.Section1 {page:Section1;} /* List Definitions */ @list l0 {mso-list-id:200746148; mso-list-template-ids:-606031390;} @list l0:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:36.0pt; mso-level-number-position:left; text-indent:-18.0pt; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l1 {mso-list-id:651833834; mso-list-template-ids:1372109452;} @list l1:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:36.0pt; mso-level-number-position:left; text-indent:-18.0pt; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l2 {mso-list-id:1141770978; mso-list-template-ids:1381380188;} @list l2:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:36.0pt; mso-level-number-position:left; text-indent:-18.0pt; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l3 {mso-list-id:1146774339; mso-list-template-ids:-1137016094;} @list l3:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:36.0pt; mso-level-number-position:left; text-indent:-18.0pt; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l4 {mso-list-id:1182738366; mso-list-template-ids:-545735430;} @list l4:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:36.0pt; mso-level-number-position:left; text-indent:-18.0pt; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l5 {mso-list-id:1271159658; mso-list-template-ids:2075552206;} @list l5:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:36.0pt; mso-level-number-position:left; text-indent:-18.0pt; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l6 {mso-list-id:1424492582; mso-list-template-ids:-1805844792;} @list l6:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:36.0pt; mso-level-number-position:left; text-indent:-18.0pt; mso-ansi-font-size:10.0pt; font-family:Symbol;} @list l7 {mso-list-id:1563055269; mso-list-template-ids:50987456;} @list l7:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:36.0pt; mso-level-number-position:left; text-indent:-18.0pt; mso-ansi-font-size:10.0pt; font-family:Symbol;} ol {margin-bottom:0cm;} ul {margin-bottom:0cm;} –>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:”Tableau Normal”;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:”";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:”Times New Roman”;
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}

Programmation de jeux

La programmation d’un jeu ou d’un logiciel doit suivre des étapes bien précises pour être réalisée proprement et avec qualité. Ce cours va donc nous instroduire dans les arcane de la conception. Il est donc important de l’assimiler correctement.

Savoir où poser les pieds

Développer un logiciel ou un jeu ne se résume pas à quelques nuits de programmation intenses passée devant son pc. Il faut toujours avoir à l’idée plusieurs points très essentiels pour le succès de votre soft. Un programme doit tout d’avoir une certaine utilité pour avoir une chance de se faire connaître. Il est ainsi clair que programmer un utilitaire qui fait clignoter la lumière du caps lock lorsqu’on double clique sur le menu démarrer n’aura qu’un succès….disons limité……

dessinner les écrans du soft donne une bonne idée du travail a éffectuer

Il est important avant de commencer à coder de bien mettre au point la finalité et le but de son travail. Un papier et un crayon sont pour cela les meilleurs outils. Il vous faudra alors à partir d’une idée initiale noter tout ce qui peut vous venir à la tête. Puis dans un second temps ordonner le tout et chercher à garder le meilleur. Ces “brouillons ” servirons de référence lors de l’étape de codage mais aussi à inscrire de nouvelles idées à chaque fois qu’il en vient ! Cela vous évitera d’avoir à créer de nouvelles versions à chaque nouvelle idée. Il est à noter que lorsqu’on parle de ” garder le meilleur de ses idées, ce la revient aussi à garder ce qui est réalisable dans le laps de temps que l’on se donne pour créer notre programme.

Une seconde étape consiste à créer sur papier encore, les écrans du programme, c’est à dire dessiner l’allure du logiciel. Cette étape est très importante dans la mesure où elle permet de déterminer l’allure générale du logiciel et d’éviter des erreurs de conceptions qui pourraient survenir sans avoir tout pensé avant. Il peut arriver en effet si on saute cette étape d’avoir à refaire la moitié du logiciel parce qu’on se rend compte d’une erreur monumentale de conception (Visual Basic est tellement graphique que la création des interfaces peut se faire directement avec).

L’étape du codage arrive alors. On peut ici programmer de plusieurs manières : soit en faisant les algorithmes sur papier des différents codes du programme puis en les traduisant dans le langage utilisé au moment venu. ou alors en codant directement puis dans un second temps refaire tout les codes en les optimisants.
La première technique qui permet de partir sur de bonnes bases est idéale pour de gros projets et pour générer un code de qualité, on préféra le second moyen pour de petites réalisations.

certains soft ont un très grand succès parcequ’une grande utilité (ici NAPSTER)

La partie la plus fastidieuse de la création d’un programme est sans nulle doute le déboguage de votre travail. Même en étant sur de son code, il y aura toujours un risque d’erreur qui va croissant avec la taille de votre réalisation. Plus un programme fait de choses plus il y a de chance qu’une erreur survienne. Pour parer, un seul moyen : passer de longs jours à tester, en se mettant à la place d’un utilisateur, votre logiciel dans tout les contextes et sous toutes les coutures possibles.

Des IDE comme Visual C++ ou Visual Basic possèdent un système de déboguage propre qui permet de localiser les bugs beaucoup plus facilement.

testeur…bientôt un metier ?

Viens ensuite le moment de la compilation. C’est à dire transformer les listings de source que vous avez écrit dans votre langage de prédilection en langage Machine afin de créer votre exécutable. Il vous faudra aussi créer un installateur, mettre votre programme dans la barre des tâches…(la plus part de ces actions vous étant expliquée dans le chapitre trucs et astuces de ce Hors Serie).

Enfin pour finir il faudra bien évidemment faire connaître et distribuer l’application ainsi créée (un site web est toujours une bonne chose).

Créer un jeu

Créer un jeu commence toujours par la réalisation d’un scénario. Un scénario n’est pas uniquement l’histoire du jeu (sauver la princesse Brume, sortir des geôles maléfiques de PROGRAMMATIONWORLD…), mais aussi tout les rouages de l’univers de ce jeu.

Il devra donc contenir plusieurs points essentiels :

• Un résumé très clair de la trame principale du jeu

• Une présentation des acteurs principaux du jeu, des différent lieux géographiques, et le déroulement générale de l’action.

• Une présentation beaucoup plus précise du jeu dans un second temps. Soit une description de la gestion des point de vie, les types d’ennemis rencontrés, les différents bonus que l’on trouvera dans le jeu, les différentes armes, les moyens de déplacements…. en clair tout ce qui n’appartient pas aux trois première partie de votre scénario.

dessiner l’univers de jeu voilà de quoi booster son imagination (ici HALF-LIFE)

Vous devrez alors relier le tout dans un seul et unique document qui constituera votre scénario.

Il est très important de le faire relire par quelqu’un qui n’a pas participé à son élaboration afin de trouver les failles. Vous serez ainsi sur d’avoir un scénario ” béton ” avant de démarrer la programmation du jeu ou de l’envoyer à un éventuel éditeur.

Revenons maintenant sur ces différentes parties.

• L’histoire du jeu est la principale partie du scénario. Elle correspond à la première étape de la création d’un programme vue précédemment.

• Il est toujours important d’avoir une idée qui tient la route. Si ce n’est pas le seul facteur qui fait acheter un jeu à un joueur c’est tout de même celui qui le tient en haleine et qui le pousse à continuer à jouer.

Evitons donc les idées sans réels innovations. Pour cela il y’a autour de nous plusieurs facteurs qui peuvent nous aider.

Les deux principaux sont notre imagination et les médias.

Notre imagination tout d’abord au travers de nos rêves et nos cauchemars offre un puit inépuisable d’idées. Il suffit pour cela uniquement de fermer les yeux et de laisser courir son imagination et tout vient tout seul ! C’est un moyen sur de rêver à l’univers de votre jeu, de ses monstres, son ambiance, de ses musiques. Essayez alors d’avoir toujours à porté de votre de lui de quoi noter vos idées car celles-ci peuvent partir aussi vite qu’elles sont venues..

Les médias ensuite au travers des fictions vues à la télés, au travers des événements sportifs, au travers des films, des informations … sont aussi de bonnes sources. Il faut alors s’assurer d’avoir la permission de prendre ces idées et de prendre les bonnes idées :un jeu sur ” bouillon de culture ” ou sur ” the Full Monty ” n’aura pas ou peu de succès, mais il nous suffit de penser à des films comme ” la guerre des étoiles ” et une multitude d’idées nous viennent à la tête. A nous alors de savoir nous en inspirer plus ou moins fortement. Les sports sont aussi de bonnes mines d’idées. Il est possible de faire des jeux suivant à la précision les règles du sport copié (FIFA 2000), essayer de garder les grandes lignes (ce qu’on appelle le mode arcade), ou bien inventer des règles totalement aberrantes (comme super Mario Kart ou bien Micro-machines).

Un autre moyen consiste à copier un autre jeu. Bien sur il est préférable d’essayer de reprendre les grandes idées et de ne pas se lancer dans un copiage honteux du jeu lui même, il existe 10000 clones de Tétris, il ne servira à rien d’en créer un de plus…

• Vient ensuite la présentation plus précise du jeu. Cette étape comprend des schémas représentant les différents écrans de jeu permettant d’avoir une première idée du projet (ceci dans les différents modes ou mondes possible). Mais aussi des points importants comme le nombre de joueurs, les mondes rencontrés, le déroulement du jeu.. Tout ce qui peut en fait donner une idée précise du jeu sans entrer dans les détails.

programmer trop nuit à la santé (ici Richard Stallman, fondateur de GNU)

Les détails sont abordés dans une dernière partie. Sans doute la plus importante en taille de votre scénario. Tout les détails doivent être répertoriés. Soit les possibilités du personnage contrôlé par le joueur, les ennemis rencontrés, les héros du jeu, les PNJ (personnages non joueurs), les armes que l’on peut trouver et leur description, le mode de vue du jeu (3D ? 2D ?, 3D iso ?..), l’univers musical rencontré, le moyen de gestion de vie du joueur. Cette partie doit pouvoir répondre à toute les questions que l’ont peut se poser..

Le code source d’un jeu

Les éléments techniques expliqués ici se rapportent plus à un jeu programmé en C ou C++ qu’en Visual Basic. Tout les jeux vidéo fonctionnent de la même manière : sur le principe de la boucle infinie. Ce principe permet à un jeu de donner l’impression au joueur que le jeu réagit à chacune de ses actions en voyant à l’écran une explosion, son vaisseau avancer, le score augmenter, le scrolling du monde s’effectuer.. Tout ceci au même moment. Pourtant le programme ne gère pas toutes les données en même temps : cette prouesse est obtenue grâce au principe du ” multitasking ” ou multitâche (à ne pas confondre avec le multithreading ” : nous verrons la différence un peu plus loin).

Un jeu est donc une application multitâche divisée en plusieurs parties dont la plus importante est la boucle infinie. Un jeu peut faire de 700 lignes (tétris ou pac-man) à plus de 500 000 pour les grosses productions, mais 95% de la taille de votre source sera toujours gérée par une boucle infinie.. Le schéma ci-contre montre ces différentes parties.

Schéma d’une boucle de jeu type

Explicons les plus en détails : Le programme commence par initialiser toutes les variables globales. Il alloue les emplacements mémoire et charge les images et aux fichiers Le code peut contenir deux boucles, celle dont nous avons parlé un peu plus haut sur laquelle repose le jeu et une boucle de menu. Cette dernière permet au joueur d’avoir le choix entre plusieurs options avant de débuter le jeu (quitter, options graphiques, crédits, etc.). troisième partie : On entre alors dans la boucle principale du jeu : Celle-ci se décompose en plusieurs autres sections, mais sachant qu’une boucle tourne a peut près a 30fps, leur ordre est laissé à l’appréciation du programmeur. Première section: on analyse ici les entrées effectuées par le joueur (clavier, joystick, volant..) Seconde section : la partie la plus importante de la boucle infinie. Celle ci a pour tache de définir ce que sera la prochaine frame (écran) qui sera affichée. Elle mets a jour l’intelligence artificielle, elle détecte les collisions entre le joueur et les autres entités a l’écran, et les collisions entre les entités elles-mêmes, elle met a jour les nouvelles coordonnées de tout les sprites. Troisième section: ici le programme mets en place les animations et les sons du jeu. Quatrième section: maintenant que tout a été définis, l’écran va donc être dessiné et chargé en mémoire vidéo (elle sera appelée image vidéo off-screen). Cinquième section: l’image off-screen va remplacer l’image affichée a l’écran et vice et versa évitant ainsi les scintillements. Sixième section: on essaye ici de donner une cadence constante à la boucle infinie afin que le jeu ai le même fps sur un p3 800 et sur un p233. De même on gère ici s’il y a lieu les ralentissements et les échanges réseau en cas de jeu multijoueurs. Une dernière partie du code géra le fait qu’un joueur quitte le jeu. Elle aura pour but principaux de libérer les ressources et de redonner la main correctement à L’OS.

La maintenance

La maintenance d’un programme commence d’abord par les commentaires et la présentation de votre code source

Comparons par exemple deux codes, l’un avec une mauvaise présentation et aucun commentaire, l’autre bien présenté et abondamment commenté

if (kbhit()){
key = toupper(getch());
if (key==’Q' || key==27)
game_running = 0;
if (key==’B') positionJoueur–;
if (key==’N') positionJoueur++;}
if (++positionJoueur> P_MAX)
positionJoueur=P_MAX;
if (–positoinJoueur < NULL)
positionJoueur=NULL;

A première vue on ne comprend pas trop ce que fait le code ; aucun commentaire n’a été inséré entre les lignes de code et aucun espace n’est visible…. Nous avons a faire à un source très brouillon et difficile à maintenir et à comprendre de surcroît.

Regardons maintenant ce même code avec des commentaires et une bonne présentation :

//si le joueur à appuyé sur une touche
//du clavier alors….
if (kbhit())
{
//…déterminer la touch pressée….
key = toupper(getch());

// si cette touche est ’Q' alors ….
if (key==’Q' || key==27)
//…indiquer que le jeu est fini
finDuJeu = true;

//sinon si la touche est ’B' alors….
else if (key==’B')
///translater le sprite vers la gauche
positionJoueur–;

//sinon si la touche est ’N' alors….
else if (key==’N')
//translater le sprite vers la droite
positionJoueur++;
}
//si en augmentant de 1 la position du
//joueur on est superieur
//à la position maximale alors….
if (++positionJoueur> POSITION_MAXIMALE)
//…repositionner le spirte dans l’ecran
positionJoueur=POSITION_MAXIMALE;

//si en augmentant de 1 la position
//du joueur on est superieur
// à la position maximale alors….
if (–positoinJoueur < NULL)
//…repositionner le spirte dans l’ecran
positionJoueur=NULL;

Le code est maintenant tout à fait compréhensible et agréable à lire….

Les avantages sont donc multiples :

–> D’autres programmeurs pourrons comprendre votre code et un travail en équipe est maintenant possible.

–> Il vous sera plus facile de faire de nouvelles versions car avec un code documenté, se remémorer l’utilité de chaque parcelle de source n’est plus un problème.

–>Enfin c’est un moyen sûr d’éviter la plus part des bugs.

pas de commentaires…très difficile à comprendre

Gestion des données

Votre jeu commence à prendre de l’ampleur, et vous ne savez plus quoi faire des dizaines de méga octets de données qui lui sont nécessaires? Une solution s’impose: les réunir en un seul fichier!

Problématique

Les données d’un jeu peuvent s’organiser de bien des manières. Colonize, par exemple, stocke ses 300 fichiers à la vue de tous, dans le répertoire racine de son chemin d’installation. A l’opposé, les jeux “modernes” ont en général tendance à rassembler leurs données en un seul et même fichier. Il y a évidemment des raisons pratiques à cela. En effet, laisser les fichiers tels quels est une méthode qui présente de nombreux inconvénients. Tout d’abord, si le jeu comporte un grand nombre de fichiers, la probabilité d’en perdre un lors d’une copie ou d’un déplacement, et donc de rendre le jeu inutilisable, n’en sera que plus forte. D’autre part, à moins d’utiliser votre propre format pour les images et les sons, vos données ne sont pas à l’abri du “rip” et sont donc facilement réutilisables par tout un chacun, ce qui n’est pas forcément souhaitable. Pour finir, un argument non négligeable: ça ne fait pas très “pro”. Nous allons donc dans cet article apprendre à rassembler toutes nos données en un seul et même fichier.

On trouve dans le répertoire de Colonization un grand nombre de fichiers txt permettant de configurer le jeu dans les moindres détails

Objectifs

Le format de fichier que nous allons définir devra nous permettre de réunir plusieurs fichiers en une seule archive. Ce format devra donc comporter, outre les données elles-mêmes, des informations nous octroyant la possibilité d’ajouter, supprimer et extraire des fichiers de cette archive. Bien sûr, nos fichiers doivent être accessibles rapidement, afin de permettre leur extraction lors du déroulement du jeu. Ces informations concerneront d’une part l’archive dans son ensemble, et d’autre part chaque fichier. Les informations sur l’archive seront stockées dans un en-tête que nous définirons, et les informations sur les fichiers feront l’objet de la définition d’un descripteur. Un archive comprendra donc un unique en-tête, et autant de descripteurs qu’elle contient de fichiers.

Les formats Zip et Rar utilisent les mêmes principes que Team Packer pour rassembler les fichiers qu’ils compressent.

L’en-tête

Comme nous l’avons dit nous allons, dans notre en-tête, stocker les informations relatives à l’archive dans son ensemble. En premier lieu, nous allons devoir nous souvenir du nombre de fichiers que contient l’archive, ce qui peut être utile, par exemple, pour ne pas boucler indéfiniment lors de la recherche d’un fichier. C’est l’unique donnée à retenir impérativement. On peut cependant se permettre de rajouter quelques informations utiles. Par exemple, il est élégant, à des fins d’indentification, de stocker une petite chaine ASCII qui caractérisera notre format. (cette pratique est utilisée entre autres dans les fichiers Bitmap, qui incluent la chaine “BM8″ au début de leur en-tête.) Ici, nous avons choisi “TPK” comme “Team PacKer”. Cette technique d’identification nous permettra de savoir très vite, lors de l’ouverture d’une archive, si celle-ci correspond à notre format ou non, plutôt que de ne pas effectuer de vérification et voir notre programme planter ou fonctionner anormalement. Enfin, on peut stocker un numéro de version, qui nous sera utile pour identifier les différents types d’archive si nous décidons dans le futur de faire évoluer notre format, en ajoutant, par exemple, la possibilité de compresser les fichiers.
Voici l’en-tête correspondant à cette description:

struct header
{
char ID[4];
unsigned char version;
unsigned char sousVersion;
WORD nbFichiers;
};

Les fichiers

Afin de pouvoir extraire un fichier, nous aurons besoin de deux choses: son nom, et sa taille. Le nom de fichier a deux emplois: il sert d’une part à l’identification, car c’est le seul moyen qu’on a de le distinguer d’un autre fichier, (mis à par la taille, qui est tout de même beaucoup moins parlante) et d’autre part à l’extraction sur disque. (il faut bien donner un nom au fichier qu’on extrait) Stocker la taille du fichier est également primordial, au vu de la façon dont on a structuré l’archive. En effet, une archive qui contient, par exemple, trois fichiers, va se découper comme suit:

• En-tête de l’archive
• En-tête du fichier
• Données
• En-tête du fichier
• Données
• En-tête du fichier
• Données

Si nous ne stockons pas la taille des fichiers, nous serons incapables de savoir quand nous arrêter lors de la lecture d’un bloc de données. Nous devons donc connaitre la taille d’un bloc de données, d’une part pour pouvoir extraire les fichiers correctement, et d’autre part afin de pouvoir lire le descripteur qui le suit.
Voici donc notre descripteur:

struct descripteur
{
char nom[256];
unsigned long taille;
};

Structure d’une archive contenant deux fichiers.

Le nom de fichier a été limité à 256 caractères: on pourrait penser que c’est là une perte d’espace, puisqu’on aurait pu adapter la taille de la chaine de caractères en fonction de la longueur de chaque nom de fichier. Le problème avec cette manière de procéder est qu’elle rend le descripteur illisible, puisque nous n’avons alors aucun moyen de connaitre sa taille. Notre descripteur doit donc avoir une taille fixe, de sorte que l’on sache combien d’octets lire dans le fichier lorsqu’on doit en extraire un descripteur.

Remarque

Petit rappel sur la gestion des fichiers en C/C++
Que l’on utilise les routines de haut niveau (fopen, fread, fclose…) ou bien celles de bas-niveau, ( open, read, close…) la gestion des fichiers reste, dans la manière de programmer, la même. A chaque fichier que votre programme va ouvrir sera associée une sorte de pointeur qui va indiquer à quel endroit du fichier va s’effectuer la prochaine opération de lecture/écriture. Lors de l’ouverture d’un fichier, celui-ci se trouve, à moins qu’on ait spécifié l’ouverture du fichier en ajout, au tout début. Le pointeur se déplace ensuite en fonction des lectures et écritures que le programme effectue. Mais il est également possible de déplacer ce pointeur “manuellement” via les fonctions fseek (haut niveau) et lseek (bas niveau). Ces deux fonctions permettent de spécifier la longueur du déplacement (en octets) ainsi que le point de référence du déplacement. (depuis le début du fichier, sa fin, ou bien depuis la position courante du curseur.) C’est la fonction lseek qui est utilisée dans Team Packer pour “sauter” de descripteur en descripteur afin de rechercher des fichiers dans l’archive.

Si on veut atteindre le dernier fichier, on doit “sauter” de descripteur en descripteur jusqu’à ce qu’on y arrive.

Programme d’exemple

Vous trouverez dans l’archive à télécharger le packer lui-même, ainsi qu’un programme d’exemple montrant comment l’utiliser dans vos jeux. Ce programme reprend une application qui a été développée pour les cours de DirectX. Celle-ci utilisait des fichiers bitmap et texte, tout bêtement stockés dans un répertoire avec le programme. Nous l’avons donc légèrement modifiée afin qu’elle prenne en charge les archives.
Le source du programme est disponible ici.

Génération de mondes aléatoires

Qui n’a jamais joué à un jeu dans lequel chaque partie se fait sur des mondes différents? C’est la technique que nous allons étudier dans ce cours.

Principe

La génération aléatoire de monde est une technique qui permet de créer des scènes de jeu différentes à chaque partie. Un bon exemple est Age of empire 2 : à chaque partie multijoueurs, vous êtes sûrs, si vous prenez l’option “monde aléatoire”, de tomber sur une carte que vous n’aviez jamais vu. Généralement, le jeu offre au joueur la possibilité de pouvoir orienter le monde créé (végétation, pourcentage d’eau, type de continents etc). D’autres jeux peuvent, à partir d’un nombre entier, générer un monde qui sera toujours le même. Le principe du nombre entier est puissant car on peut à partir de celui-ci sauvegarder un monde complet. Chaque case de ce monde peut elle-même être associée à un autre nombre entier qui définira ce qu’il faut afficher en cas de zoom sur cette case. En clair : au lieu d’avoir à sauvegarder pour chaque case un contenu géographique à afficher en cas de zoom, il suffira juste de lui associer un entier à partir duquel on générera un nouveau monde zoomé.

Comment générer un monde ?

Il existe un grand nombre de techniques pour générer un monde. Celle que nous allons voir maintenant est très puissante et simple à mettre en place.
Nous partons du principe que nos cartes de jeu sont à la base un quadrillage de L cases en largeur et H cases en hauteurs (figure (a)).

figure a : au départ une carte vide

La première étape consiste à générer pour chaque case un nombre aléatoire compris dans un certain intervalle. Dans notre exemple nous avons pris 4 nombres : -1, 0, 1, 2 pour distinguer 4 altitudes différentes à l’intérieur des cartes. Ces altitudes ont été représentées sur nos schémas respectivement par les couleurs bleu, vert, marron et blanc. La figure (b) montre le passage de notre carte vierge à la carte générée grâce à ces nombres aléatoires. Comme on le voit, celle-ci est complètement chaotique, inutilisable et surtout injouable. Notons que les figures b, c et d montrent notre carte avec une vue de près (colonne de gauche) et une vue éloignée (colonne de droite) pour mieux comprendre le principe de génération.

figure b n donne aléatoirement à chaque case de notre carte une valeur indiquant son altitude

figure c : on divise la carte en carrés, on prend la couleur moyenne de chaque carré et on leur assigne cette valeur

figure d : même étape avec des carrés plus grands (etc . etc.)

Si le terrain semble tellement chaotique c’est parce que nous ne l’avons pas aplani. C’est ce que nous allons faire dans notre seconde étape.
Pour cela, il nous faut faire une moyenne carrée plusieurs fois de suite sur l’ensemble de la carte. Une moyenne carrée consiste à sectionner la carte en une série de petits carrés, (au minimum deux cases de cotés) puis de faire la somme des valeurs de toutes les cases de ces derniers. On calcule alors pour chaque carré la moyenne des valeurs, moyenne qui sera la valeur à donner à toutes les cases du carré. La figure (e) illustre ce principe. Comme on le voit, la moyenne des quatre cases du carré est calculée et le résultat est attribué a chaque case de ce carré. On obtient alors une nouvelle carte comme celle de l’étape C de la figure (c). La carte est un peu plus réaliste. Nous dirons qu’il s’agit là d’une carte avec un très grand nombre de petites îles.

figure e : principe de la moyenne des carrés

A partir de là, on relance le même calcul, mais avec des carrés un peu plus grands. Nous prenons pour notre exemple des carrés de 4 cases de coté. La moyenne se fait comme montré sur la figure e (partie 2). On abouti alors à la carte de la figure d, (étape d) soit une carte pouvant être assimilée à un relief de plaine proche du niveau 0 avec un grand nombre de lacs. Si nous avions utilisé une moyenne sur des carrés de 3 cases de cotés nous aurions eu de grandes îles.
Cette technique peut se continuer jusqu’à obtention du relief voulu.

Où peuvent intervenir les paramètres ?

Comme nous l’avons vu, générer un monde est une opération triviale à base d’additions et de divisions. Il est possible, au cours de ce traitement, de faire intervenir divers paramètres de jeu. Le premier est bien entendu de faire influencer le nombre aléatoire : si l’on veut plus d’eau autant essayer de faire sortir l’altitude -1 le plus souvent possible et générer une première grille avec beaucoup plus de bleu que les autres couleurs.

Améliorer le rendu

Bien entendu un moteur de génération de monde ne fait pas tout. A vous ensuite d’améliorer le rendu des bords d’eau, des chaînes de montagnes, en créant un grand nombre de tiles permettant un design de carte irréprochable. Il vous faudra détecter les cases se situant au bord de l’eau pour leur assigner un design de bord d’eau, détecter les cases se situant à un endroit élevé de la carte pour leur assigner le design de montagne etc.

figure f : il faut toujours veiller à créer toutes les tiles possible pour les différentes cases du terrain

Nombres aléatoires et pseudo-aléatoires

Si pour la génération de notre carte nous utilisons une suite de nombre totalement aléatoire, nous sommes sûrs et certains de ne jamais retomber sur la même carte a chaque démarrage du jeu. Il faudra alors après la génération de la carte la sauvegarder totalement sur fichier afin de pouvoir la retrouver plus tard. Il est pourtant possible par l’intermédiaire du principe du pseudo-aléatoire de sauvegarder tout une carte par l’intermédiaire d’un simple nombre.
Le principe est simple : on créé une suite de nombre à partir d’une valeur “départ”. Cette suite sera toujours identique a chaque fois que cette valeur départ sera rencontrée. De même on ne retrouvera jamais cette suite pour n’importe quelle valeur départ différente.
Nous sommes donc sur qu’en donnant à notre moteur de génération de nombres pseudo-aléatoires une valeur connue par avance nous aurons toujours la même suite.
Si nous couplons alors ce moteur de génération de nombres avec le moteur de génération de carte en donnant aux cases de notre carte les valeurs de la liste pseudo aléatoire, nous pouvons par l’intermédiaire d’un nombre sauvegarder tout une carte.

Génération terminée…

Pour illustrer ce cours, nous avons repris un programme des cours de DirectX et l’avons allégé. Nous y avons rajouté les classes de génération de nombre pseudos aléatoire, le tout grandement commenté. Il ne reste donc plus qu’à les consulter.
Ces sources sont disponibles ici.

Programmation d’un moteur de particules

Les moteurs de particules sont très souvent utilisés dans les jeux. Ils permettent de reproduire des phénomènes physiques complexes avec un temps de calcul amoindri, tout en offrant une excellente qualité visuelle. On les rencontre dans des simulations d’explosions/étincelles, pluie et fluides,… L’approche se fait dans l’optique d’une programmation en C/C++ mais il est tout à fait possible d’adapter les techniques utilisées dans d’autres langages.

Une particule

Un système de particules est composé d’un nombre donné de corps, les particules. Chacune possède des propriétés physiques. L’exemple le plus simple d’un système de particules est celui d’une molécule. Elle est composée de plusieurs atomes qui interagissent avec leur environnement. Les atomes ne sont pas statiques mais se déplacent selon des forces qui dépendent de leurs caractéristiques.

Intéressons-nous à une particule dans un espace en 3D. Chaque particule possède une position dans cet espace, par rapport à un référentiel qu’on supposera fixe pour commencer. Le plus simple est d’utiliser l’origine en (0,0,0) comme référence. Une particule possède aussi une masse et une vitesse qui se présente sous la forme d’un vecteur à 3 composantes. La position est représentée par la lettre r et la vitesse par v

Une particule dans son référentiel avec l’origine en (0,0,0).

Nous pouvons faire une structure en C ou une classe en C++ pour représenter notre particule de base. La structure du vecteur à 3 dimensions V3D est ici à titre d’exemple. En C++, il convient d’utiliser une vraie classe gérant les opérations sur les vecteurs.

typedef struct{
float x,y,z;
} V3D;

typedef struct{
V3D position;
V3D vitesse;
float masse;
} Particule;

Les forces

Il est important d’introduire la notion de forces, elles modifient la trajectoire des particules et permettent d’obtenir des résultats réalistes. On pourrait faire un système sans forces mais les particules suivraient une trajectoire droite à vitesse constante. En effet, une force implique nécessairement une accélération. L’accélération d’une particule correspond à la variation de sa vitesse. Newton a démontré en son temps que

Cette formule permet de dire que sans accélération, il n’y a pas de force et vis-versa. Les forces et les accélérations dans notre système de particules sont représentées par des vecteurs à 3 composantes. Chaque particule peut être soumise à une ou plusieurs forces. Dans ce cas, il suffit d’additionner les vecteurs des forces pour trouver ce qu’on appelle la résultante. C’est elle que l’on conserve dans notre structure. Nous n’avons pas besoin de l’accélération dans la structure car elle se déduit naturellement grâce à l’équation (2). La structure devient :

typedef struct{
V3D position;
V3D vitesse;
V3D force;     // résultante des forces
float masse;
} Particule;

Un peu de cinématique : mise à jour des particules

Le système doit évoluer dans le temps et nous devons modifier les positions des particules en fonction des forces présentes et de la vitesse des particules. On sait qu’une accélération indique un changement de vitesse. On sait aussi que la présence d’une vitesse traduit un changement de position dans le temps. Il est commode de les écrire grâce à des dérivées :

Petit rappel et pas de panique : Pour un intervalle de temps donné dt, la vitesse va changer avec une valeur dv, il s’agit d’un rapport indiquant une accélération, ou en d’autres termes, un changement de vitesse. De même pour la vitesse, elle correspond à la distance parcourue pendant un temps dt divisée par ce même temps. La dérivée de la trajectoire est la vitesse. Et la dérivée de la vitesse est l’accélération. Comment trouver une trajectoire à partir d’une accélération ? Et bien en intégrant ! C’est l’étape inverse de la dérivée et nous n’allons pas le faire analytiquement mais numériquement.

Le seul problème, c’est que les variables dv,dr,dt sont infinitésimales (tendent vers 0) mais un ordinateur ne peut pas travailler facilement avec cette notion d’infini. Nous allons devoir faire une approximation lors des calculs. A chaque fois que nous affichons le résultat à l’écran, nous pouvons obtenir le temps écoulé depuis la dernière frame jusqu’à l’actuelle, il est très important d’avoir un timer de la plus haute précision pour cette étape (sous Windows, les fonctions QueryPerformance). Ce temps écoulé, nous allons l’appeler delta_temps. Plus ce laps de temps se rapproche de 0, meilleure sera l’approximation de la trajectoire. Nous allons l’utiliser de la même manière que le dt des équations (3) et (4).

Des relations (3) et (4), nous trouvons immédiatement les relations ci-dessus. Pour mettre à jour la position et la vitesse de la particule, nous devons premièrement trouver l’accélération qui a été produite par les forces durant l’intervalle de temps delta_temps. Pour cela, nous nous référons à l’équation (2) et l’on trouve tout de suite notre vecteur accélération. En regardant la formule (5), on se rend compte qu’on peut trouver le vecteur de changement de vitesse, car le dt, c’est le delta_temps que nous possédons déjà.

Maintenant nous pouvons procéder de la même manière avec la vitesse. En ajoutant ce changement de vitesse à la vitesse actuelle de la particule, nous obtenons la nouvelle vitesse de la particule (au temps t+dt). Il est préférable de rajouter le changement de vitesse à ce moment plutôt qu’à la fin du processus (après l’intégration qui conduit à la position), ceci pour des raisons de stabilité numérique. Cette nouvelle vitesse, nous allons l’employer de suite dans l’équation (6) et nous accédons ainsi au changement de position. La dernière étape consiste à rajouter ce changement de position à la position de la particule (position au temps t). Nous obtenons ainsi la nouvelle position (au temps t+dt).

Cette méthode d’intégration est celle d’Euler. Elle n’est pas toujours très fiable à cause des imprécisions numériques mais elle donne de bons résultats pour la plupart des applications. C’est surtout la méthode la plus rapide pour évaluer les équations différentielles.

// position, vitesse, force sont des membres de la classe (type V3D)

void Particule::Euler(double dt)
{
V3D a, dv, dr;

a.x = force.x / masse;
a.y = force.y / masse;
a.z = force.z / masse;

// dv/dt = a  ==> dv = a*dt;
dv.x = a.x * dt;
dv.y = a.y * dt;
dv.z = a.z * dt;

// mise à jour de la vitesse (on obtient la vitesse au temps t+dt)
vitesse.x += dv.x;
vitesse.y += dv.y;
vitesse.z += dv.z;

// dr/dt = v  ==> dr = v*dt;
dr.x = vitesse.x * dt;
dr.y = vitesse.y * dt;
dr.z = vitesse.z * dt;

// mise à jour de la position
position.x += dr.x;
position.y += dr.y;
position.z += dr.z;
}

Liens sur la résolution numérique d’équations différentielles

Paul Bourke – plusieurs méthodes avec un exemple en C
Numerical Recipes – Euler
Numerical Recipes – Runge-Kutta
Numerical Recipes – Richardson et Burlirsch-Stoer

Les attracteurs

Orbite : la force est toujours dirigée vers le centre de l’attracteur et son intensité augmente à son approche.

Maintenant que nous avons un calcul de position qui fonctionne, il nous reste à rajouter un calcul de force. On peut se contenter de simuler la gravité telle qu’on la perçoit sur terre avec un vecteur constant dirigé vers le bas. Une force constante peut être intéressante aussi pour simuler du vent. Nous n’allons pas créer des interactions entre particules car cela demande beaucoup trop de ressources (il est possible de le faire en définissant des groupes de particules) Nous allons nous intéresser plus particulièrement à la force de gravitation qui est celle apparaissant entre 2 corps distants. Il sera ainsi possible de simuler des orbites. Avec un attracteur de grande masse par rapport aux particules, on pourra modéliser, de manière simplifiée, des trous noirs. La formule (7) correspond à la vraie loi. La formule (8) est celle que nous utiliserons :

G est la constante de gravitation. M est la masse du premier corps et m la masse du 2ème corps. R est la distance entre les 2 corps. Afin d’éviter une multiplication inutile et pour empêcher une division par un nombre très petit lorsque R tend vers 0, nous enlevons G et rajoutons une valeur de limitation k, normalement égale à 1. Nous obtenons la formule (8). Ainsi la force ne pourra excéder la valeur de M*m. Cette astuce a quelques désavantages, elle tronque la réalité mais c’est la vitesse qui compte ici. Pour corriger le problème, il suffit de multiplier chaque masse par la racine de G. Chose intéressante, si une des masses est négative, le phénomène s’inverse et les particules sont repoussées au lieu d’être attirées.

De quoi avons-nous besoin pour définir l’attracteur ? Sa position et sa masse sont suffisantes. Le reste des informations pour le calcul de la force provient de la particule concernée.

Exemple 1 : Un trou noir est placé en (0,0,0) et une étoile de rayon 30, composée de 20000 particules se trouve en (0,-70,0). Chaque particule de l’étoile a une vitesse initiale de (-10,0,0). Ce déplacement provoque la mise en rotation des particules autour du trou noir et l’attraction engendre cette forme spiralée. La masse du trou noir est 10000 fois supérieure à celle d’une particule. L’intensité des particules correspond à leur vitesse.

Exemple 2 : Le même trou noir et la même étoile mais avec des particules ayant une vitesse initiale en direction de (0,0,0). Le trou noir aspire l’étoile et propulse concentriquement de la matière. Au bout d’un certain temps, on voit apparaître un “wormhole”, une sorte d’entonnoir. Les 3 images du bas sont des vues en coupe du phénomène.

void MoteurParticules::Ajoute_Force_Trou_Noir(Particule* p,
V3D centre, float masse_trou_noir)
{
V3D axe;

// on crée un vecteur qui passe par le centre
//de l’attracteur et par la particule
axe.x = centre.x - p->position.x;
axe.y = centre.y - p->position.y;
axe.z = centre.z - p->position.z;

float longueur_carre = axe.x * axe.x + axe.y *
axe.y + axe.z * axe.z;

// combien de newtons ?
float intensite = (p->masse * masse_trou_noir) /
(1.0f + longueur_carre);

// on normalise le vecteur,  évitons des problèmes
//avec des divisions par 0…
float longueur = sqrtf(longueur_carre);

if (longueur<0.00001) longueur=0.00001;
axe.x /= longueur;
axe.y /= longueur;
axe.z /= longueur;

// on retrouve un vecteur dont la longueur
//correspond à l’intensité de la force
gravitation_direction.x *= intensite;
gravitation_direction.y *= intensite;
gravitation_direction.z *= intensite;

// on le rajoute à la résultante
p->force.x += gravitation_direction.x;
p->force.y += gravitation_direction.y;
p->force.z += gravitation_direction.z;
}

Liens sur la gravitation

Applet Java avec des orbites en 2D
Excellente explication historique et technique en français
Page en anglais avec une explication complète sur les trous noirs

Les émetteurs

Les émetteurs servent à générer et positionner des particules. Il en existe plusieurs catégories. Certains donnent une vitesse initiale à chaque particule. D’autres n’en donnent pas et laissent les forces agir sur la vitesse des particules. Certains émetteurs régénèrent des particules si une condition est remplie. Par exemple, si une particule est trop éloignée, elle est éliminée et remplacée par une nouvelle particule plus proche. Un critère d’âge peut être fixé, si une particule est trop vieille, elle est éliminée (étincelles dans des collisions)

Emetteur de type ‘explosion’ ou ‘radial’

Emetteur de type ’spray’

Ces 2 émetteurs sont les plus courants et ils donnent tous une vitesse initiale à chaque particule. Le radial excelle dans les simulations d’explosion. L’émetteur “spray” se destine à la simulation de réacteurs ou d’étincelles. Nous allons créer un émetteur radial qui attribue des vitesses aléatoires à chaque particule mais qui partent toutes du même centre. Pour un vrai feu d’artifice, il faudrait ajouter une force de gravité orientée verticalement. Une variante est un émetteur de type directionnel qui est plutôt utilisé pour de la pluie ou de la neige. (avec une force latérale provoquée par du vent), les particules dans ce cas ne partent pas du même endroit mais sont distribuées sur un plan, une sphère,…

Le code ci-dessous gère un tableau de particules et l’initialise au départ avec une explosion. La vitesse maximale sur chaque axe est comprise entre -0.5 et 0.5, le générateur de nombres aléatoires standard RAND() est employé dans une routine inline (pour des questions de vitesse) afin de produire des floats compris entre 0 et 1. Un émetteur de type “spray” est facile à réaliser à partir de cette routine pour autant que le spray soit dirigé dans l’axe X,Y ou Z. Il suffit de mettre une des composantes de la vitesse à 0 et de diminuer la vitesse sur les axes restants. Une meilleure approche serait de prendre un angle aléatoire avec un maximum fixé et de passer par des sinus/cosinus. Un spray dirigé de manière quelconque et optimisé nécessite des manipulations géométriques que nous ne décrirons pas ici. Une (mauvaise) méthode est celle d’une génération de vecteurs aléatoires avec un contrôle de l’angle par rapport au vecteur direction du spray et ceci jusqu’à ce que l’on obtienne le nombre de particules voulu. Une meilleure méthode utilise la distribution des vecteurs dans un cône.

// retourne un nombre aléatoire entre 0 et 1
inline float frnd(){ return (float(rand())/RAND_MAX);}

Particule *Liste_Particules=NULL;

void Creation_Emetteur_Radial(int Nombre_Particules)
{
Liste_Particules=new Particules[Nombres_Particules];
V3D origine={0,0,0};

for (int n=0;n<Nombres_Particules;n++){
Liste_Particules[n].Position=Origine;
Liste_Particules[n].Vitesse.x=-0.5+frnd();
Liste_Particules[n].Vitesse.y=-0.5+frnd();
Liste_Particules[n].Vitesse.z=-0.5+frnd();
}
}

void Destruction_Emetteur_Radial()
{
if (Liste_Particules) {
delete[] Liste_Particules;
Liste_Particules = NULL;
}
}

La texture de la particule

L’affichage se fait via openGL. Chaque particule est stockée dans une texture de 32 x 32 pixels en RGB, même si une texture en gris suffit ici. Nous avons le choix entre charger une texture depuis le disque ou alors la générer. C’est la 2ème solution que nous allons adopter car il est très simple de créer une texture de ce type.
Nous déterminons la distance entre le centre de la texture et le pixel, nous l’utilisons pour trouver l’intensité. La fonction exponentielle permet d’avoir une particule plus intense au centre avec une luminosité qui diminue rapidement en s’écartant du centre. L’argument de la fonction expf est multiplié par un facteur, il permet de modifier les caractéristiques de luminosité.

bool GenereTextureParticule()
{
unsigned char *pixels = new unsigned char[32*32*3];

// pour générer une particule, nous allons utiliser la
// distance entre le pixel et le centre
// de la texture couplé à une fonction exponentielle.
// Cette fonction déterminera l’intensité
// du pixel.

int i = 0;

for (int y = 0; y < 32; y++) {
for (int x = 0; x < 32; x++) {
float dx = (float)x - 16.0f;
float dy = (float)y - 16.0f;

// on trouve la distance, normalisée entre 0 et 1
// et on l’inverse pour avoir
// le maximum d’intensité au centre
float distance = sqrtf(dx * dx + dy * dy) /
sqrtf(16*16 + 16*16);

int intensite = expf(-distance*8)*512.0f;
if (intensite>=255) intensite=255;

// pixel en RGB
pixels[i] = intensite;
pixels[i + 1] = intensite;
pixels[i + 2] = intensite;

i += 3;
}
}

// crée la texture openGL
glGenTextures(1, &texture[0]);
glBindTexture(GL_TEXTURE_2D, texture[0]);
glTexParameteri(GL_TEXTURE_2D,
GL_TEXTURE_MAG_FILTER,GL_LINEAR);
glTexParameteri(GL_TEXTURE_2D,
GL_TEXTURE_MIN_FILTER,GL_LINEAR);
glTexImage2D(GL_TEXTURE_2D, 0, 3, 32, 32, 0,
GL_RGB, GL_UNSIGNED_BYTE, pixels);

delete[] pixels;

return true;
}

Implémentation et affichage

Nous avons opté pour l’utilisation du C++ et les STL (Standard Template Library). Les STL regroupent un ensemble de structures particulièrement utiles pour gérer des tableaux dynamiques de manière optimisée. Nous utilisons le template vector qui est un tableau de taille variable, il fonctionne un peu à la manière d’une pile. On peut facilement rajouter des éléments dans ce tableau grâce à la fonction push_back(), mais aussi enlever le dernier élément de la liste avec pop_back(). La taille du tableau peut à tout moment être trouvée avec size(). Il est utile de disposer d’une telle structure (une liste chaînée peut aussi faire l’affaire) dans un moteur de particules, on peut ainsi aisément rajouter des particules et y accéder comme un tableau normal. Les STL disposent d’autres fonctions intéressantes mais nous ne les utiliserons pas pour le moteur. Il faut éviter de “pusher” trop souvent car ces opérations sont relativement lentes mais il est possible de substituer “vector” par “list” sans avoir à retoucher le code, il faut essayer les 2 pour voir ce qui est le plus rapide avec votre application. Voici un exemple d’utilisation de ce template vector :

#include <vector>

// la déclaration du namespace est facultative, dans le cas contraire,
//il faut ajouter un ”std::” devant la déclaration du template
using namespace std;

// on déclare le tableau dynamique, composé de ’int’
vector <int> tableau;

void Fonction()
{
// on ajoute 2 éléments à notre tableau
int a = 10;
tableau.push_back(a);
int b = 20;
tableau.push_back(b);

// on attribue à c la valeur du premier élément du tableau donc c = 10
int c = tableau[0];

// on enlève le dernier élément de la pile donc d = 20
int d = tableau.pop_back();

// e = 1, il reste un élément dans le tableau
int e = tableau.size();
}

Une classe “Particule” contient une fonction qui gère le calcul de la trajectoire (Euler). Une autre classe “MoteurParticules” maintient une liste d’objet “Particule”, liste qui est sous la forme d’un vector STL. Il ne nous reste plus qu’à afficher les particules.

Nous devons en premier lieu activer la gestion de la transparence d’openGL, c’est glEnable(GL_BLEND) qui nous permet de faire cela. Le type de blend utilisé ajoute l’intensité de la particule à l’intensité de l’arrière-plan, ceci avec une saturation pour donner un bel effet lorsque les particules se superposent. Nous travaillons avec des glVertex3f mais ceci pose un petit problème. En effet, on pourrait être tenté d’afficher chaque particule comme un plan à une distance fixe de la caméra (axe Z) mais dès que la caméra tourne, chaque particule subit les effets de la perspective :

Pour corriger le problème rencontré par les 2 premiers utilisateurs, nous allons devoir introduire la technique dite du billboarding. Celle-ci remet des surfaces en 2D dans l’axe de la caméra. Elle est souvent utilisée dans les jeux 3D pour afficher des arbres ou des personnages, Doom utilisait cette méthode. Dans la figure ci-dessus, l’utilisateur ou la caméra se déplace vers la droite, dans l’axe des X. S’il fait une rotation de 10°, alors il faudra tourner notre objet de -10° pour annuler l’effet de la rotation de caméra. Nate Miller propose une solution simple à mettre en oeuvre avec openGL :

1. Récupérer la matrice “ModelView” avec glGetFloatv(GL_MODELVIEW_MATRIX, mat) dans un tableau 1D de 16 floats
2. La transposer, c’est à dire inverser la transformation (faire la rotation inverse)
3. On trouve 2 vecteurs : (mat[0], mat[1], mat[2]) et (mat[4], mat[5], mat[6])
4. Le premier vecteur pointe vers la droite de la caméra et le 2ème vers le haut de la caméra.
5. A partir de ces 2 vecteurs, on peut créer un polygone qui est parallèle au plan formé par la caméra

Il faut faire ces calculs après avoir effectué une rotation de la caméra. Voici le code qui effectue cela, on peut se passer de la 2ème étape car il s’agit d’une permutation des éléments de la matrice selon sa diagonale. Nous avons simplifié le code en évitant de faire cela composante par composante (grâce à une classe vectorielle qui surcharge les opérateurs). On en profite pour afficher la particule. Cette routine est ici à titre d’exemple, le code du projet est quelque peu différent.

GLfloat mat[16];
glGetFloatv(GL_MODELVIEW_MATRIX, (float*) &mat);

// on trouve les vecteurs parallèles au plan formé par la caméra.
V3D v_gauche (-mat[0], -mat[4], -mat[8]);
V3D v_droite (mat[0], mat[4], mat[8]);
V3D v_haut (mat[1], mat[5], mat[9]);
V3D v_bas (-mat[1], -mat[5], -mat[9]);

float taille = 1.0f;

// on trouve les 4 coins du carré
a = position + ((v_gauche + v_bas)*taille);
b = position + ((v_droite + v_bas)*taille);
c = position + ((v_droite + v_haut)*taille);
d = position + ((v_gauche + v_haut)*taille);

// affichage de la particule
glBegin(GL_QUADS);
glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
glTexCoord2f(0,0);
glVertex3f(a.x, a.y, a.z);
glTexCoord2f(1,0);
glVertex3f(b.x, b.y, b.z);
glTexCoord2f(1,1);
glVertex3f(c.x, c.y, c.z);
glTexCoord2f(0,1);
glVertex3f(d.x, d.y, d.z);
glEnd();

Conclusion

Nous avons préparé un projet (Visual C++ 6.0) avec un moteur de particules complet tout en évitant de compliquer le code avec des fonctions avancées. L’application tourne en mode fenêtré openGL, la souris permet de modifier la position de la caméra et les touches “haut” et “bas” modifient le zoom. Deux trous noirs ont une masse qui devient parfois négative et repoussent les particules, celles qui sont trop éloignées sont replacées au centre de l’univers.

Avec les différentes techniques expliquées ici, vous ne devriez pas avoir de problèmes à créer votre propre moteur de particules et y rajouter des fonctions plus avancées (rendu de pluie, autres forces,…). La méthode numérique pour calculer la position de chaque particule peut être appliquée à des objets 3D habituels comme un vaisseau, tout est fonction des forces en présence.

Moteur de particules – Projet pour Visual C++

Programmation de labyrinthes

La programmation de labyrinthe est un sujet très utile pour tout programmeur de jeu puisque “d’architecture” revient très souvent à l’intérieur de jeu.
Programmer de telles structure passe malheureusement pour être relativement difficile. Nous allons voir qu’il s’agit en fait, d’un jeu d’enfant.

Labyrinthe ?

Un labyrinthe standard est une matrice de case possédant deux états : l’état plein (assimilable à un mur), et l’état vide (assimilable à un couloir).

La génération d’un labyrinthe consiste à étendre les murs déjà existants en définissant des cases constructibles qui vont être détectées et remplacées par des murs tant que cela sera possible.

Une case est constructible si elle se trouve dans une des situations suivantes:

Les quatres situations où une case peut être remplacée par un mur

Générer un labyrinthe est donc aussi simple que cela. Voyons maintenant les différentes étapes que nous allons suivre dans notre programme.

Etapes de génération

La génération va se faire en 5 étapes :

• Créer une grille initialisée avec des murs aux bords
• Placer des morceaux de murs aléatoirement à l’intérieur de la grille
• Référencer les différentes cases constructibles
• Pour chacune de ces cases, prises aléatoirement, la transformer en mur et analyser les 8 cases autour pour déterminer si leur état a changé (les constructibles peuvent perdre leur état, et les non constructibles peuvent le devenir).
• Afficher le labyrinthe ainsi créé

La vue d’ensemble du programme étant faite, nous pouvons passer directement à l’état fondamentale : la programmation. Nous utiliserons deux langages : le C pour disposer d’un code source en langage structuré et le C# pour le langage objet.

Code source en C

Le code source en C se présente ainsi :

#include <stdlib.h>
#include <time.h>

//définition ici du nombre de ligne et du nombre de colonnes
#define N 40
#define M 79

//définition ici des abscisses et ordonnées de l’entrée i
//et de la sortie j
#define Ei 0
#define Ej 40

#define Si (39)
#define Sj (40)

/**
* Enumération qui contient les trois états possibles
* de chaque case du labyrinthe
*/
enum e_case
{
//la case est un mur
mur,
//la case est un couloir
couloir,
//la case est construtible
constructible
};

//définition d’un nouveau type
typedef enum e_case grille[N][M];

//variable globale représentant le labyrinthe
grille laby;

//définition des fonctions
int choisir_nombre(int min, int max);
int estConstructible(grille l, int i, int j);
void InitializeLabyrinthe(void);
void SetMursAleatoires(void);
int GetCasesConstrutibles(void);
void SetCasesConstrutibles(int nombreDeCasesConstructibles);
void AfficherLabyrinthe();

/**
* fonction qui renvoie un nombre compris entre
* min et max
*/
int choisir_nombre(int min, int max)
{
static int first = 1;
if (first) {
srand(time(NULL));
first = 0;
}
return min + (int )((1.0+max-min) * rand() / (RAND_MAX+1.0));
}

/**
* Indique si une case en coordonnées i, j du tableau grille
* est constructible auquel cas le fonction renvoie 1, 0 sinon
*/
int estConstructible(grille l, int i, int j)
{

if (l[i][j] == mur)
return 0;

if ( ( l[i][j+1] == mur && l[i-1][j] != mur &&
l[i-1][j-1] != mur && l[i][j-1] != mur &&
l[i+1][j-1] != mur && l[i+1][j] != mur ) ||
( l[i-1][j] == mur && l[i][j-1] != mur &&
l[i+1][j-1] != mur && l[i+1][j] != mur &&
l[i+1][j+1] != mur && l[i][j+1] != mur ) ||
( l[i][j-1] == mur && l[i+1][j] != mur &&
l[i+1][j+1] != mur && l[i][j+1] != mur &&
l[i-1][j+1] != mur && l[i-1][j] != mur ) ||
( l[i+1][j] == mur && l[i][j+1] != mur &&
l[i-1][j+1] != mur && l[i-1][j] != mur &&
l[i-1][j-1] != mur && l[i][j-1] != mur ) )
return 1;
else
return 0;
}

/**
* fonction principale
*/
int main(void)
{
//nombre de cases constructibles
int nombreDeCasesConstructibles;

//initialiser avec murs aux bords et vide au centre
InitializeLabyrinthe();

//placer des murs aléatoirement
SetMursAleatoires();

//déterminer le nb de cases constructibles
nombreDeCasesConstructibles = GetCasesConstrutibles();

//remplacer ces cases constructibles par des murs
SetCasesConstrutibles(nombreDeCasesConstructibles);

//afficher
AfficherLabyrinthe();
}

/**
* fonction qui place sur les bords du labyrinthe
* des murs de façon à l’entourer et rempli le centre de vide
*/
void InitializeLabyrinthe(void)
{
int i, j;

//pour toutes les lignes…
for (i = 0; i < N; i++)
{
//pour chaque colonnes…
for (j = 0; j < M; j++)
{
//est-ce un bord du labyrinthe ?
if ( (i == 0 || i == N-1 || j == 0 || j == M-1) &&
(i != Ei || j != Ej) && (i != Si || j != Sj) )
//si oui, mettre un mur
laby[i][j] = mur;
else
//sinon spécifier en couloir
laby[i][j] = couloir;
}
}
}

/**
* fonction qui place dans le labyrinthe une série de murs aléatoires
* dont le nombre est spécifié par l’utilisateur
*/
void SetMursAleatoires(void)
{
int i, j;
//nombre de morceaux de murs aléatoires
int nombreDeMursAleatoires;

printf(”Nombre de mur places aleatoirement dans le labyrinthe ? ”);
scanf(”%d”, &nombreDeMursAleatoires);

//tant qu’il y’a des murs a placer
while (nombreDeMursAleatoires– > 0)
{
//faire…
do
{
//prendre au hazard une coordonnée X
i = choisir_nombre(1, N-2);
//prendre au hazard une coordonnée Y
j = choisir_nombre(1, M-2);
}
//tant que la case en ce point n’est pas un couloir…
while (laby[i][j] != couloir);

//…sinon la transformer en mur
laby[i][j] = mur;

}
}

/**
* fonction qui recherche et répertorie les différentes
* case constructibles du labyrinthe
*/
int GetCasesConstrutibles(void)
{
int i, j;
int nombreDeCasesConstructibles = 0;

//pour toutes les lignes…
for (i = 1; i < N-1; i++)
{
//pour toutes les colonnes…
for (j = 1; j < M-1; j++)
{
//si la case est constructible…
if (estConstructible(laby, i, j))
{
//sauvegarder leur nombre
nombreDeCasesConstructibles ++;

//référencer
laby[i][j] = constructible;
}
}
}

return nombreDeCasesConstructibles;
}

/**
* fonction qui remplace chaque case constructible
* par un mur et met à jour les 8 cases autour
*/
void SetCasesConstrutibles(int nombreDeCasesConstructibles)
{
int i, ii, j, jj;
int r;

//tant qu’il y’a des cases constructibles
while (nombreDeCasesConstructibles > 0)
{

//prendre une case au hazard
r = choisir_nombre(1, nombreDeCasesConstructibles);
for (i = 1; i < N-1 && r > 0; i++)
{
for (j = 1; j < M-1 && r > 0; j++)
{
if (laby[i][j] == constructible && –r == 0)
break;
}

if (r == 0)
break;
}

//remplacer par un mur
laby[i][j] = mur;

//diminuer le nombre de cases constructibles
nombreDeCasesConstructibles –;

//pour toutes les lignes…
for (ii = i-1; ii <= i+1; ii++)
{
//pour toutes les colonnes….
for (jj = j-1; jj <= j+1; jj++)
{
//mettre les 8 cases autour à jour

//si la case est marqué constructible mais
//ne peut plus l’etre…
if ( laby[ii][jj] == constructible &&
! estConstructible(laby, ii, jj) )
{
//la spécifier en couloir
laby[ii][jj] = couloir;
//diminuer le nombre de cases constructibles
nombreDeCasesConstructibles –;
}
//sinon si la case est marqué en couloir mais
//peut être constructible
else if ( laby[ii][jj] == couloir &&
estConstructible(laby, ii, jj) )
{
//la spécifier en constructible
laby[ii][jj] = constructible;
//augmenter le nombre de cases constructibles
nombreDeCasesConstructibles ++;
}
}
}
}
}

/**
* Fonction qui affiche le labyrinthe
*/
void AfficherLabyrinthe()
{
int i, j;
for (i = 0; i < N; i++)
{
for (j = 0; j < M; j++)
{
switch (laby[i][j])
{
case mur:
putchar(’#');
break;
case couloir:
putchar(’ ’);
break;
case constructible:
putchar(’x');
break;
}
}
putchar(’\n’);
}
}

Celui-ci est compatible avec le C norme ANSI vous pouvez donc à priori le compiler sous n’importe quel système. Nous ne reviendrons pas sur ce code source qui s’avère relativement simple et largement commenté. N’hesitez pas à nous contacter pour toute questions.

Code source en C#

Voyons maintenant le même code source mais dans une version objet. Nous utiliserons le langage C# pour sa portabilité, sa simplicité d’utilisation et sa lisibilité. Nous couplerons notre programme à une application Direct X qui affichera le labyrinthe sous une forme plus agréable que sur un mode console classique.
Le code source de la classe Labyrinthe se présente ainsi :

using System;
using System.Drawing;
using System.ComponentModel;
using System.Windows.Forms;

namespace Labyrinthe
{

/// <summary>
/// Enumération qui contient les trois états possibles
/// de chaque cases du labyrinthe
/// </summary>
public enum TypeDeCase
{
//la case est un TypeDeCase.Mur
Mur,
//la case est un TypeDeCase.Couloir
Couloir,
//la case est construtible
Constructible
};

/// <summary>
/// Description résumée de Labyrinthe.
/// </summary>
public class Labyrinthe
{

/// <summary>
/// définition ici du nombre de ligne et du nombre de colonnes
/// </summary>
public int Hauteur;
public int Largeur;

/// <summary>
/// définition ici des abscisses et ordonnées de l’entrée i
/// et de la sortie j
/// </summary>
public int Ei;
public int Ej;

public int Si;
public int Sj;

/// <summary>
/// le labyrinthe
/// </summary>
public TypeDeCase[,] grille;

/// <summary>
/// nombre de murs aléatoires
/// </summary>
public int NombreDeMursAleatoires;

/// <summary>
/// nombre de murs aléatoires
/// </summary>
public int NombreDeCasesConstructibles;

/// <summary>
/// Pour la génération des nombres aléatoires
/// </summary>
Random rand = new Random(DateTime.Now.Millisecond) ;

public Labyrinthe()
{

}

/// <summary>
/// fonction qui renvoie un nombre compris entre min et max
/// </summary>
int choisir_nombre(int min, int max)
{
return rand.Next(min, max ) ;
}

/// <summary>
/// Indique si une case en coordonnées i, j du tableau grille
/// est TypeDeCase.Constructible auquel cas le fonction renvoie 1, 0 sinon
/// </summary>
bool estConstructible(int i, int j)
{

if (grille[i,j] == TypeDeCase.Mur)
return false;

if ( ( grille[i,j+1] == TypeDeCase.Mur && grille[i-1,j] != TypeDeCase.Mur &&
grille[i-1,j-1] != TypeDeCase.Mur && grille[i,j-1] != TypeDeCase.Mur &&
grille[i+1,j-1] != TypeDeCase.Mur && grille[i+1,j] != TypeDeCase.Mur ) ||
( grille[i-1,j] == TypeDeCase.Mur && grille[i,j-1] != TypeDeCase.Mur &&
grille[i+1,j-1] != TypeDeCase.Mur && grille[i+1,j] != TypeDeCase.Mur &&
grille[i+1,j+1] != TypeDeCase.Mur && grille[i,j+1] != TypeDeCase.Mur ) ||
( grille[i,j-1] == TypeDeCase.Mur && grille[i+1,j] != TypeDeCase.Mur &&
grille[i+1,j+1] != TypeDeCase.Mur && grille[i,j+1] != TypeDeCase.Mur &&
grille[i-1,j+1] != TypeDeCase.Mur && grille[i-1,j] != TypeDeCase.Mur ) ||
( grille[i+1,j] == TypeDeCase.Mur && grille[i,j+1] != TypeDeCase.Mur &&
grille[i-1,j+1] != TypeDeCase.Mur && grille[i-1,j] != TypeDeCase.Mur &&
grille[i-1,j-1] != TypeDeCase.Mur && grille[i,j-1] != TypeDeCase.Mur ) )
return true;
else
return false;
}

/// <summary>
/// Genere le labyrinthe
/// </summary>
/// <param name=”h”>hauteur</param>
/// <param name=”l”>largeur</param>
/// <param name=”murs”>murs aléatoires</param>
/// <param name=”ei”>entrée x</param>
/// <param name=”ej”>entrée y</param>
/// <param name=”si”>sortie x</param>
/// <param name=”sj”>sortie y</param>
public void Generer(int h, int l, int murs, int ei, int ej, int si, int sj)
{
this.Ei = ei;
this.Ej = ej;
this.Si = si;
this.Sj = sj;
Hauteur = h;
Largeur = l;
grille = new TypeDeCase[Hauteur, Largeur];
this.NombreDeCasesConstructibles = 0;
this.NombreDeMursAleatoires = murs;

//initialiser avec Case.Murs aux bords et vide au centre
InitializeLabyrinthe();

//placer des Case.Murs aléatoirement
SetMursAleatoires();

//déterminer le nb de cases Case.Constructibles
GetCasesConstrutibles();

//remplacer ces cases TypeDeCase.Constructibles par des TypeDeCase.Murs
SetCasesConstrutibles();
}

/// <summary>
/// fonction qui place sur les bords du labyrinthe
/// des TypeDeCase.Murs de façon à l’entourer et rempli le centre de vide
/// </summary>
void InitializeLabyrinthe()
{
int i = 0, j = 0;

//pour toutes les lignes…
for (i = 0; i < Hauteur; i++)
{
//pour chaque colonnes…
for (j = 0; j < Largeur; j++)
{
//MessageBox.Show(i.ToString() + ” ” + j .ToString());
//est-ce un bord du labyrinthe ?
if ( (i == 0 || i == Hauteur-1 || j == 0 || j == Largeur-1) &&
(i != Ej || j != Ei) && (i != Sj || j != Si) )
{
//si oui, mettre un TypeDeCase.Mur
grille[i,j] = TypeDeCase.Mur;
}
else
//sinon spécifier en TypeDeCase.Couloir
grille[i,j] = TypeDeCase.Couloir;
}
}
}

/// <summary>
/// fonction qui place dans le labyrinthe une série de
///TypeDeCase.Murs aléatoires
/// dont le nombre est spécifié par l’utilisateur
/// </summary>
void SetMursAleatoires()
{
int i, j;

//tant qu’il y’a des TypeDeCase.Murs a placer
while (NombreDeMursAleatoires– > 0)
{
//faire…
do
{
//prendre au hazard une coordonnée X
i = choisir_nombre(1, Hauteur-2);
//prendre au hazard une coordonnée Y
j = choisir_nombre(1, Largeur-2);
}
//tant que la case en ce point n’est pas
//un TypeDeCase.Couloir…
while (grille[i,j] != TypeDeCase.Couloir);

//…sinon la transformer en TypeDeCase.Mur
grille[i,j] = TypeDeCase.Mur;

}
}

/// <summary>
/// fonction qui recherche et répertorie les différentes
/// case TypeDeCase.Constructibles du labyrinthe
/// </summary>
void GetCasesConstrutibles()
{
int i, j;

//pour toutes les lignes…
for (i = 1; i < Hauteur-1; i++)
{
//pour toutes les colonnes…
for (j = 1; j < Largeur-1; j++)
{
//si la case est TypeDeCase.Constructible…
if (estConstructible(i, j))
{
//sauvegarder leur nombre
NombreDeCasesConstructibles ++;

//référencer
grille[i,j] = TypeDeCase.Constructible;
}
}
}
}

/// <summary>
/// fonction qui remplace chaque case TypeDeCase.Constructible
/// par un TypeDeCase.Mur et met à jour les 8 cases autour
/// </summary>
void SetCasesConstrutibles()
{
int i = 0, ii = 0, j = 0, jj = 0;
int r;
//tant qu’il y’a des cases TypeDeCase.Constructibles
while (NombreDeCasesConstructibles > 0)
{
//prendre une case au hazard
r = choisir_nombre(1, NombreDeCasesConstructibles);
for (i = 1; i < Hauteur-1 && r > 0; i++)
{
for (j = 1; j < Largeur-1 && r > 0; j++)
{
if (grille[i,j] == TypeDeCase.Constructible && –r == 0)
break;
}
if (r == 0)
break;
}

//remplacer par un TypeDeCase.Mur
grille[i,j] = TypeDeCase.Mur;

//diminuer le nombre de cases TypeDeCase.Constructibles
NombreDeCasesConstructibles –;

//pour toutes les lignes…
for (ii = i-1; ii <= i+1; ii++)
{
//pour toutes les colonnes….
for (jj = j-1; jj <= j+1; jj++)
{
//mettre les 8 cases autour à jour
if ( (jj == Ei && Ej==ii) || (jj == Si && Sj==ii))
continue;
//si la case est marqué TypeDeCase.Constructible mais
//ne peut plus l’etre…
if ( grille[ii,jj] == TypeDeCase.Constructible &&
! estConstructible( ii, jj) )
{
//la spécifier en TypeDeCase.Couloir
grille[ii,jj] = TypeDeCase.Couloir;
//diminuer le nombre de cases TypeDeCase.Constructibles
NombreDeCasesConstructibles –;
}
//sinon si la case est marqué en TypeDeCase.Couloir mais
//peut être TypeDeCase.Constructible
else if ( grille[ii,jj] == TypeDeCase.Couloir &&
estConstructible( ii, jj) )
{
//la spécifier en TypeDeCase.Constructible
grille[ii,jj] = TypeDeCase.Constructible;
//augmenter le nombre de cases TypeDeCase.Constructibles
NombreDeCasesConstructibles ++;
}

}
}

}

}

}

}

Couplé à une classe Direct X qui affiche une fenêtre et différents bitmap à la place des murs, entrée, sortie, et couloirs nous obtenons l’application suivante :

On s’y croirait !

Remarque

La code source lié à Direct X devrait vous paraître obscur, reportez vous à notre rubrique Direct X si vous voulez en savoir plus.
Si vous n’avez pas de quoi faire fonctionner le C# lisez le cours ici pour palier à ce manque.

Des dalles

N’hesitez pas à nous envoyer vos propres algorythme de génération de labyrinthe, afin que nous les fassions figurer ici.

Annexes

En annexe nos deux programmes (lun en C et l’autre en C#) :

Programme C ici.
Programme projet C# ici;

Effet spéciaux en 2D

Ce tutorial a pour but de faire connaître les principes utilisés pour faire des effets spéciaux rencontrés dans divers jeux en 2D. Il s’agit de montrer comment réaliser simplement des effets qui feront tout le charme d’un jeu. Il n’a pas pour prétention de faire le tour des effets spéciaux professionnels mais seulement de vous faire découvrir quelques fonctions sympathiques que vous pourrez intégrer dans vos jeux.
Vous trouverez la plupart des effets spéciaux rencontrés dans le jeu et ils seront abordés par ordre de complexité croissante. Pour tout renseignement, aide ou avis complémentaire, vous pouvez écrire à JpegLauden@free.fr.
Dans une première partie, nous aborderons les principes généraux. Leur compréhension est nécessaire pour comprendre comment fonctionne le code de chaque effet.

Principes généraux

Types d’effets spéciaux

Il faut distinguer les effets temps réels des effets précalculés. Dans les effets présentés dans ce tutorial, il n’y a qu’un seul effet précalculé, il s’agit de l’effet de nuit. Les calculs engendrés pour réaliser cet effet sont trop volumineux pour être réalisés à chaque rafraîchissement de l’écran. Nous y reviendrons lorsque nous aborderons cet effet. Mais nous allons plutôt nous consacrer aux effets temps réels dont la durée est limitée dans le temps.

Activation d’un effet

La plupart des effets décrits si dessous ont une durée définie dans une variable de type int qui donne la durée de l’effet en millisecondes. Cette variable doit être déclarée en global puisqu’elle devra être accessible dans deux fonctions différentes. Ce choix n’est pas anodin puisque nous utiliserons une comparaison de temps avec la fonction timeGetTime() qui retourne la durée écoulée depuis la mise en route du système d’exploitation en ms.

Il faut dès lors associer à l’effet un compteur de temps permettant justement de faire la comparaison avec la fonction timeGetTime(). Ce compteur doit être défini en global. Enfin pour éviter que les calculs engendrés par l’effet soient effectués tout le temps même lorsque l’effet n’est pas demandé, il faut créer un booléen indiquant si l’effet est actif ou non. Ce booléen doit être déclaré en global, puisqu’il devra être accessible partout dans le code.

Pour lancer un effet spécial, il faut donc une phase d’initialisation, qui initialise le compteur de temps et qui met le booléen à true. On crée donc une fonction d’initialisation qui réalise cela et qui prend comme paramètre la durée en ms pendant lequel l’effet doit être actif.

Pratiquement, voici l’architecture type d’un effet géré en temps réel :

void Nom_Effet(int Duree)
{
Etat_Effet=true ;              //activation de l’effet
Compteur_Temps=timeGetTime() ; //initialisation du compteur de temps
Duree_Effet=Duree ;            //indication de la durée de l’effet
}

void Gestion_Effet(void)
{
//si l’effet est actif, on traîte les calculs associés
if (Etat_Effet)
{
//calculs
.
//si la durée de l’effet est écoulée, on l’arrête
if (timeGetTime()-Compteur_Temps>Duree_Effet)
Etat_Effet=false ;
}
}

Ainsi, lorsque vous voudrez lancer l’effet, il suffira d’appeler la fonction Nom_Effet(.) avec la durée voulue. Il faut ensuite que la fonction Gestion_Effet() soit appelée à chaque passage dans la boucle principale (c’est à dire à chaque rafraîchissement).

Amplitudes des effets spéciaux

Un aspect important souvent retrouvé dans les effets spéciaux concerne l’amplitude des effets, comme l’amplitude d’un tremblement, d’une distorsion ou d’un zoom. Cette amplitude peut varier dans le temps, de façon à réaliser une transition avec l’action normale dans le jeu (il faut que l’amplitude de l’effet parte de 0 pour arriver à un maximum puis diminue pour arriver de nouveau à 0). La meilleure façon de le réaliser est de faire en sorte que cette amplitude suive la courbe d’un cosinus (ou d’un sinus, c’est pareil).

La fonction sinus ou cosinus permet de donner à un effet
une progression et une régression “fluide”

L’amplitude sera généralement représentée par une variable de type int, et son calcul dépendera donc d’un sinus :

Amplitude = Amplitude_Max * sin(Angle) ;

La variable Angle quant à elle doit varier dans le temps puisque l’on doit parcourir l’ensemble des valeurs du sinus sur une période. Cette variable doit donc aller de 0 à p et son calcul dépend de la durée de l’effet (0 à début de l’effet, p à fin de l’effet) ainsi que du compteur de temps :

Angle = (timeGetTime() - Compteur_Temps) * 3.14159 / Duree_Effet) ;

C’est tout ce qui est nécessaire de savoir sur les principes généraux appliqués aux effets spéciaux temps réels. Néanmoins quelques uns des effets qui vont être abordés n’utiliseront pas tous ces principes, car cela ne sera pas utile.

Passons maintenant en revue les différents effets que nous allons traiter.

Tremblement de terre

Description

Cet effet est des plus simple à réaliser, mais il apporte néanmoins une certaine dynamique dans le jeu et peu servir à accentuer une ambiance dans une action. Vous pouvez vous en servir pour amplifier les dégâts visuellement en secouant l’image quelque dizièmes de seconde, afin de donner au joueur l’impression que le choc a été violent.

Principe

Le principe est tout simple : une fois votre affichage réalisé, juste avant de faire le flipping final avec la surface primaire, il vous suffit de prendre le contenu du backbuffer (à l’aide d’une structure RECT, comme pour les sprites) et d’afficher ce contenu dans le backbuffer en décalant l’origine de l’image, de façon aléatoire.

Le tremblement de terre est l’effet le plus simple à réaliser

Vous n’avez donc qu’à créer deux variables int x_pos et int y_pos désignant le décalage horizontal et vertical à ajouter à l’origine de l’image. Attention, ces décalages peuvent être négatifs (on tourne autour du point (0,0) correspondant à l’origine de l’écran).

A chaque passage dans la boucle d’affichage, vous aller modifier ces variables de décalage, de façon aléatoire. Pour avoir accès aux nombres aléatoires, il faut initialiser le générateur de nombre au début du programme par la fonction suivante :

srand(GetTickCount());

Puis dans la boucle d’affichage, caculez un nouveau décalage de la façon suivante :

x_pos= (rand()-rand()) % 5 ;
y_pos= (rand()-rand()) % 5 ;

Ici, x_pos et y_pos prennent des valeurs entières entre -4 et 4. Ce qui fera une amplitude du tremblement de 8 pixels maximum. La valeur 5 est empirique et dépend de l’effet que vous voulez donner ainsi que de la résolution puisqu’il s’agit de pixels.

Code correspondant à l’effet

void Tremblement_De_Terre(int Duree)
{
//fonction initialisant l’effet de tremblement de terre

//activation de l’effet (var. à définir en global)
TREMBLEMENT=true;
//durée de l’effet      (var. à définir en global)
DUREE_TREMBLEMENT=Duree;
//début du chronomètre  (var. à définir en global)
Temps_Tremblement=timeGetTime();
}

void Gestion_Tremblement_De_Terre(void)
{
//fonction de traîtement de l’effet
//(à appeler dans la boucle principale)

//si l’effet est actif
if (TREMBLEMENT)
{
//durée de l’effet écoulée
if (timeGetTime()-Temps_Tremblement>DUREE_TREMBLEMENT)
TREMBLEMENT=false;
//offset aléatoire pour l’origine de l’écran
x_pos+=(rand()-rand()) % 5;
y_pos+=(rand()-rand()) % 5;
}
}

Il reste ensuite à modifier votre affichage : juste avant l’appel à la fonction Flip(.), il faut décaler l’image dans le backbuffer :

RECT Rectangle ;
Rectangle.left=0;
Rectangle.right=Width;      //largeur de la résolution
Rectangle.top=0 ;
Rectangle.bottom=Height ;   //hauteur de la résolution
lpDDSBack->BltFast(x_pos,y_pos,lpDDSBack,&Rectangle,DDBLTFAST_WAIT);

Danger

Attention toutefois à une chose : si vous copiez ces dernières lignes et que vous lanciez l’effet de tremblement, cela ne fonctionnera pas, vous aurez un écran noir : en effet vous décalez le contenu du backbuffer, du coup l’image dépasse les bordures de l’écran, donc l’image ne s’affiche pas. Pour remédier à cela, il faut sélectionner dans le rectangle seulement la partie à déplacer et qui ne dépassera pas l’écran.

Vaguelettes

Description

Cet effet spécial permet d’effectuer une distorsion de l’image en donnant l’impression que l’image « fait des vagues ». Cela permet dans le jeu par exemple de faire une transition avec un fait passé, comme si le héros se remémorait quelque chose. L’effet peut aussi être utilisé comme transition entre deux endroits.

Principe

Le principe est encore une fois très simple : une fois l’affichage fini, juste avant de réaliser le flipping du backbuffer avec la surface primaire, on découpe l’image en bandes horizontales (d’une hauteur de un pixel) et on décale ces bandes horizontalement selon un cosinus dont l’angle évolue dans le temps.

Mal au coeur ?

Sur ce schéma, la hauteur des bandes est exagérée, mais le principe reste le même. Lors du traîtement de l’effet, on parcours toutes les lignes du backbuffer (dépend de la hauteur de la résolution) et pour chaque ligne, on sélectionne la ligne dans un rectangle dont les coordonnées sont définies par les deux coins (0,i) et (Width,i+1). Puis on réaffiche sur le backbuffer la même ligne mais décalée horizontalement.

Le décalage varie selon un cosinus. L’amplitude de ce cosinus varie selon un sinus, de façon à faire une transition (principe détaillé dans la section « principes généraux »). L’angle du cosinus varie dans le temps pendant la durée de l’effet de façon à faire « bouger les vagues ». De plus l’angle dépend aussi du numéro i de la ligne.

Dernière précision : avant de réafficher les lignes, il ne faut pas oublier d’effacer la partie d’origine en affichant par-dessus une partie d’une ligne noire. Il est préférable de passer par une surface temporaire dans laquelle nous stoquerons le backbuffer. Puis après avoir effacé le backbuffer en étalant un sprite noir dessus, nous copierons ligne par ligne l’image de la surface temporaire dans le backbuffer, chaque ligne étant décalée.

Code correspondant à l’effet

void Vaguelettes(unsigned int Duree)
{
//fonction initialisant l’effet de vaguelettes à l’écran

//activation de l’effet de vague            (var. à définir en global)
VAGUELETTES=true;
//durée de l’effet                          (var. à définir en global)
DUREE_VAGUELETTES=Duree;
//activation du chronomètre                 (var. à définir en global)
Temps_Vaguelettes=timeGetTime();
//initialisation de l’angle des vagues      (var. à définir en global)
ANGLE_VAGUELETTES=0;
}

void Gestion_Vaguelettes(void)
{
//fonction gérant l’affichage des vaguelettes à l’écran
//(à appeler dans la boucle principale)

int Amplitude, //amplitude des vagues
i,         //n° de la ligne traîtée
x;         //abscisse des lignes pour l’effet de vaguelettes

//si l’effet est actif
if (VAGUELETTES)
{
Amplitude=(int)(60*sin((timeGetTime()-Temps_Vaguelettes)
*PI/DUREE_VAGUELETTES));
//copie du backbuffer vers la surface temporaire
//la fonction Rectangle() est décrite dans Moteur2D.h
Rectangle(BORD_GAUCHE,BORD_HAUT,BORD_DROIT,BORD_BAS,0,0,0,0);
lpDDSSurface_Temporaire->BltFast(0,0,lpDDSBack,
&Rectangle_Source,DDBLTFAST_WAIT);
//on remplit en noir le backbuffer (à adapter avec vos fonctions)
Rectangle(1,1,33,33,0,0,0,0);
Zoom(lpDDSSprites_Objets,0,0,32,32,0,0,WIDTH,HEIGHT,1,1);
//on affiche les vagues lignes par lignes
for (i=0;i<HEIGHT;i++)
{
//sélection d’une ligne
Rectangle(0,i,WIDTH,i+1,0,0,0,0);
//calcul du décalage horizontal
x=(int)(Amplitude*cos((ANGLE_VAGUELETTES+2*i)*PI/180));
//affichage de la ligne (à adapter avec vos fonctions)
Affiche_Sprite(lpDDSSurface_Temporaire,BORD_GAUCHE+x,
BORD_HAUT+i,BORD_GAUCHE,BORD_HAUT,
BORD_DROIT,BORD_BAS);
}
ANGLE_VAGUELETTES+=5;
//fin de l’effet
if (timeGetTime()-Temps_Vaguelettes>DUREE_VAGUELETTES)
VAGUELETTES=false;
}
}

Zoom

Description

Cet effet permet de réaliser un zoom avant pendant une scène (donc les personnages peuvent continuer à bouger pendant le zoom) puis un zoom arrière. Cela peut être utilisé lors d’un changement de lieu par exemple.

Effet efficace pour changer d’écran dans un jeu…

Principe

Nous ne verrons ici que le principe permettant de réaliser cet effet. Celui-ci n’intervient que lors d’un changement de lieu (lorsque le personnage rentre ou sort d’une maison par exemple) et cela fait intervenir d’autres fonctionnalités du jeu (lancement de commandes, téléportation, centrage de la caméra sur le personnage, .).

Le principe reste néanmoins très simple à mettre en ouvre. Nous avons besoin d’un facteur de zoom qui peut être déclaré en tant qu’entier int. Ce facteur doit permettre de faire un zoom avant et un zoom arrière. On peut donc le faire varier à l’aide d’un sinus :

Là encore, le sinus nous aide à faire l’effet spécial

L’angle du sinus variera de la façon qui est décrite dans la section « Principes généraux ». Dès lors, comment faire un zoom ? C’est très simple, il suffit d’utiliser la fonction Blt(.) offerte par DirectX. Cette fonction permet en effet d’afficher un sprite délimité par un rectangle à l’écran. Comme la fonction BltFast(.) me direz-vous ! Oui, sauf qu’ici vous devez utiliser un deuxième rectangle, celui de la destination de votre sprite sur le backbuffer. Dès lors, rien ne vous empêche de donner une taille différente à votre sprite. On dilate alors le sprite pour l’étirer sur tout l’écran : c’est le principe du zoom : étirer une petite partie de l’image sur tout l’écran.

Pour ce faire, admettons que l’on zoome sur le centre de l’écran (c’est plus simple). Le rectangle source lorsqu’il n’y a pas de zoom sélectionne toute l’image. Par contre, lorsque le zoom est au maximum (à vous de définir ce maximum, défini normalement par le facteur de zoom (dans ce cas le facteur varie de 0 à Max selon un sinus)), le rectangle source est bien plus petit et est centré par rapport à l’écran :

RECT Source ;
Source.left = 0 + Facteur_Zoom * 4/3 ;
Source.right = Width - Facteur_Zoom * 4/3 ;
Source.top = 0 + Facteur_Zoom ;
Source.bottom = Height - Facteur_Zoom ;

Remarquez la présence du coefficient 4/3 : il est là pour préserver le rapport hauteur/largeur de votre image. En effet les résolutions acceptées par nos cartes graphiques sont en accord avec les tubes cathodiques au format 4/3. C’est à dire que le rapport Width/Height de la résolution est égal à 4/3.

Dès lors, vous n’avez plus qu’à faire varier le facteur de zoom et l’affaire est dans le sac. Lors de l’affichage avec la fonction Blt(), il vous faudra spécifier un rectangle de destination. Ici, on veut étaler notre sprite sur tout l’écran, donc il suffit de donner au rectangle de destination les dimensions de l’écran ( (0,0) –> (Width,Height) ) A vous de mettre également au point une fonction d’initialisation et de gestion de l’effet, comme cela à été vu pour les deux effets précédents.

Distorsion de l’image

Description

Cet effet reprend le même principe que l’effet de zoom précédent. Il utilise la fonction Blt(.) pour distordre l’affichage de façon à éviter de garder le même rapport hauteur/largeur de l’image. Il s’ensuit une distorsion horizontale ou verticale de l’image qui peut faire un effet assez sympathique, en donnant l’impression que l’image n’est pas dure mais flexible et maléable. Intéressant !

Principe

Comme nous l’avons dis, le principe est le même que celui utilisé avec l’effet de zoom précédent, dans le sens où on va utiliser là aussi un rectangle source, un rectangle destination, et la fonction Blt(.).

L’intérêt, ici, est de faire varier le rapport hauteur/largeur de l’image. On réalisera donc une dilatation verticale de l’image et une dilatation horizontale. Ces deux dilatations se feront suivant un sinus et un cosinus, de façon à ce qu’elles soient en opposition de phase (pendant que la hauteur augmente, la largeur diminue et inversement), sans quoi on se ramène à un effet de zoom.

De plus, pour faire une transition avec l’affichage normal du jeu, nous ferons varier l’amplitude de ces dilatations selon un sinus (principe détaillé dans la section « Principes généraux »).

De même qu’avec l’effet de vagues, il faut effacer le backbuffer avant de réafficher son contenu distordu. On passe pour cela par une surface temporaire sur laquelle on copie le backbuffer avant de l’effacer.

Code correspondant à l’effet

void Distorsion(unsigned int Duree)
{
//fonction initialisant l’effet de distorsion de l’image

//activation de la distorsion               (var. à définir en global)
DISTORSION=true ;
//début de la distorsion                    (var. à définir en global)
ANGLE_DISTORSION=0;
//durée de la distorsion                    (var. à définir en global)
DUREE_DISTORSION=Duree;
//activation du chronomètre                 (var. à définir en global)
Temps_Distorsion=timeGetTime();
}

void Gestion_Distorsion(void)
{
//fonction distordant l’écran selon 1 amplitude variable dans le temps

//amplitude de la distorsion (transition avec l’affichage normal)
unsigned int Amplitude;

//si l’effet est actif
if (DISTORSION)
{
Amplitude=(int)(60*sin((timeGetTime()-Temps_Distorsion)
*PI/DUREE_DISTORSION));
//copie du backbuffer vers la surface temporaire
Rectangle(0,0,WIDTH,HEIGHT,0,0,0,0);      //dépend de la résolution
lpDDSSurface_Temporaire->BltFast(0,0,lpDDSBack,
&Rectangle_Source,DDBLTFAST_WAIT);
//sélection de la partie du backbuffer à distordre
Rectangle(abs((int)(4*Amplitude*cos(ANGLE_DISTORSION*PI/180)/3)),
abs((int)(Amplitude*sin(ANGLE_DISTORSION*PI/180))),
400-abs((int)(4*Amplitude*cos(ANGLE_DISTORSION*PI/180)/3)),
300-abs((int)(Amplitude*sin(ANGLE_DISTORSION*PI/180))),
0,0,0,0);
//on étale ensuite le sprite sélectionné sur tout l’écran
//le facteur de zoom est appelé ici ANGLE_DISTORSION et est compris
//entre 0 et 360. cf la fonction Zoom() dans Moteur2D.h pour info.
Zoom(lpDDSSurface_Temporaire,0,0,WIDTH,HEIGHT,
0,0,WIDTH,HEIGHT,ANGLE_DISTORSION,360);
//on fait varier le facteur de zoom
ANGLE_DISTORSION+=5;
//fin de l’effet
if (timeGetTime()-Temps_Distorsion>DUREE_DISTORSION)
DISTORSION=false;
}
}

Pluie et orage

Description

Cet effet permet de faire tomber la pluie sur votre jeu. Nous avons rajouté également une fonctionnalité permettant de faire un orage. Cet effet vous permet ainsi de donner une autre dimension à une même scène et de donner l’impression au joueur que le temps n’est pas figé dans le jeu. Il est de plus très simple à coder.

Principe

Pour activer l’effet, il n’y a pas besoin de créer de fonction d’initialisation, puisqu’il suffira de mettre un booléen PLUIE à true ou false pour activer ou désactiver l’effet.

Nous utilisons un sprite de pluie qui va être affiché plusieurs fois de façon à recouvrir l’écran. On forme ainsi une mosaïque qui devra être plus grande que l’écran, puisque la surface créée par cette mosaïque devra défiler de façon à simuler la pluie qui tombe.

La pluie s’obtient par un effet de translation

Une fois que la mosaïque aura bougée de la taille d’un sprite de pluie, on repositionne la mosaïque à sa position d’origine, et ainsi de suite. Cela forme une boucle de défilement et si tout se passe bien, on a l’illusion que la pluie tombe de façon continue. Nous utiliserons pour cela une variable permettant de décaler l’origine de la mosaïque. Ce décalage se fera par rapport au coin supérieur droit de la mosaïque, car notre sprite de pluie montre une pluie tombant avec un angle de 45° environ. A vous d’adapter par la suite votre fonction si vous voulez que la pluie tombe selon une autre orientation.

Notre sprite fait une taille de 64×32 pixels. Nous décalerons donc la mosaïque de 2 pixels horizontalement et un seul verticalement à chaque passage dans la fonction.

En réalité, on ajoute un deuxième sprite de pluie, qui ne tombe pas dans la même direction que le premier (le décalage de la mosaïque se fait cette fois de un seul pixel horizontalement), ce qui donne un effet de relief et de profondeur à la scène.

Code correspondant à l’effet

void Gestion_Pluie(void)
{
//fonction affichant la pluie à l’écran

unsigned int i,j; //compteurs

//si l’effet est actif
if (PLUIE)
{
//augmentation du compteur pour l’affichage de la pluie
//ce compteur est à définir en global
SCROLL_PLUIE++;
//si on a fait défiler la hauteur d’un sprite, on recommence
if (SCROLL_PLUIE>31) SCROLL_PLUIE=0;

//on affiche autant de sprite qu’il faut pour couvrir l’écran
for (i=0;i<=WIDTH/63+1;i++)     //un sprite fait 64 pxls de large
{
for (j=0;j<=HEIGHT/31+3;j++) //un sprite fait 32 pxls de haut
{
//affichage du premier sprite de pluie
Rectangle(355,82,419,114,0,0,0,0);
Affiche_Sprite(lpDDSSprites_Menus,
64*i-4*SCROLL_PLUIE,32*j+4*(SCROLL_PLUIE-32),
0,0,WIDTH,HEIGHT);
//affichage du deuxième sprite de pluie
Rectangle(420,82,484,114,0,0,0,0);
Affiche_Sprite(lpDDSSprites_Menus,
64*i-2*SCROLL_PLUIE,32*j+2*(SCROLL_PLUIE-32),
0,0,WIDTH,HEIGHT);
}
}
//clignotement de l’écran pour l’orage, toute les 3s max
if (rand()%150<=1 && timeGetTime()-Temps_Eclair>3000)
{
Temps_Eclair=timeGetTime();
Clignotement(255,255,255,200); //éclair
}
}
}

Un rendu efficace

L’orage

Pour ce qui est de l’orage, il suffit de donner l’impression qu’un éclair est tombé. De façon aléatoire dans le temps, nous affichons un écran blanc pendant une fraction de seconde. Ce qui donne un flash à l’écran et donne une très bonne impression. Pour améliorer ce rendu, on fait en fait clignoter l’écran normal avec un écran blanc pendant quelque dizièmes de seconde. Pour plus d’information, reportez-vous à la fonction Clignotement() ci-dessous. Elle est très simple à comprendre.

void Clignotement(int r, int v, int b, unsigned int Duree)
{
//fonction initialisant l’effet de clignotement

//activation de l’effet de clignotement
CLIGNOTEMENT=true;
//mise à zéro du clignoteur
CLIGNOTEUR=0;
ROUGE_CLIGNOTEMENT=r;
VERT_CLIGNOTEMENT=v;
BLEU_CLIGNOTEMENT=b;
//activation du chronomètre
Temps_Clignotement=timeGetTime();
//durée de l’effet
DUREE_CLIGNOTEMENT=Duree;
}

void Gestion_Clignotement(void)
{
//fonction gérant l’effet de clignotement de l’écran

//on élargit un pixel coloré à la taille de l’écran
if (CLIGNOTEMENT)
{
//une image sur deux est clignotante
if (CLIGNOTEUR)
{
//on élargit un pixel coloré à la taille de l’écran
Rectangle(200,90,202,92,0,0,WIDTH,HEIGHT);
}
if (timeGetTime()-Temps_Clignotement<DUREE_CLIGNOTEMENT)
CLIGNOTEUR=1-CLIGNOTEUR;
else
CLIGNOTEMENT=false;
}
}

Neige

Description

Cet effet s’inscrit dans la suite de l’effet précédent. On a vu comment faire défiler des sprites regroupés en une mosaïque à l’écran, de façon linéaire (la pluie tombe de façon oblique tout le temps). Pour réaliser un effet de neige, il en va un peu autrement, puisque les flocons flottent dans l’air et sont portés dans le vent. De plus ils tombent de façon plus lente que la pluie.

Principe

Le code de cet effet ressemble beaucoup à celui de l’effet de pluie. La seule chose qui change, c’est dans le décalage horizontal de la mosaïque. Pour simuler le vent dans les flocons, on va faire défiler la mosaïque de façon oblique, comme la pluie, mais on va ajouter un décalage horizontal suivant un cosinus, de façon à faire légèrement onduler la neige.

L’effet d’odulation est caractéristique à la neige

L’activation de l’effet se fait comme la pluie, c’est à dire en mettant un booléen NEIGE à true. Il n’est donc pas nécessaire de faire une fonction d’initialisation.

Code correspondant à l’effet

void Gestion_Neige(void)
{
//fonction affichant la neige à l’écran

int i,j;   //compteurs

//si l’effet est actif
if (NEIGE)
{
//augmentation du compteur pour l’affichage de la neige
//ce compteur est à définir en global
SCROLL_NEIGE++;
//on boucle le défilement
if (SCROLL_NEIGE>63) SCROLL_NEIGE=0;

//on affiche autant de sprites qu’il faut pour couvrir l’écran
for (i=-1;i<=(int)WIDTH/63+1;i++)     //64 pxls de large par sprite
{
for (j=-1;j<=(int)HEIGHT/31+3;j++) //32 pxls de haut par sprite
{
//affichage du premier sprite, tombant en oblique
Rectangle(485,82,549,114,0,0,0,0);
Affiche_Sprite(lpDDSSprites_Menus,
64*i-SCROLL_NEIGE,32*j+2*(SCROLL_NEIGE-64),
0,0,WIDTH,HEIGHT);
//affichage du deuzième sprite,tombant en oblique sinusoïdale
Rectangle(550,82,614,114,0,0,0,0);
Affiche_Sprite(lpDDSSprites_Menus,
64*i-SCROLL_NEIGE+
(int)(8*sin((SCROLL_NEIGE*360./63.)*PI/180)),
32*j+(SCROLL_NEIGE-64),
0,0,WIDTH,HEIGHT);
}
}
}
}

Brrr ! ‘ fait pas chaud !

Nuit

Description

Contrairement à tous les effets qui viennent d’être abordés, il s’agit d’un effet précalculé car les calculs effectués pour cet effet sont trop lourds pour être réalisés à chaque rafraîchissement de l’écran. Il n’y aura donc pas d’activation de l’effet à proprement parler, mais plutôt l’appel d’une fonction modifiant tous les sprites d’extérieurs du jeu.

Principe

Le principe est simple à comprendre, mais peut être un peu complexe à mettre en ouvre. Comme vous le savez surement (sinon cf tutorial DDraw sur le système de couleurs), chaque pixel est défini par trois composantes, Rouge, Verte et Bleue. Pour réaliser un effet de nuit, il suffit donc simplement de diminuer pour chaque pixel de chaque sprite du jeu les composantes Rouge et Verte. Les sprites sont ainsi assombris et une teinte bleutée permet de donner cet aspect recherché pour la nuit.

Vous vous rendez donc compte que les calculs sont énormes : generalement les sprites font 32×32 pixels, soit 1024 pixels. Sachant qu’il y a plus de 500 sprites extérieurs à modifier, cela représente la modification des composantes RVB de plus de 500 000 pixels ! Néanmoins, avec les machines actuelles, cette opération peut être réalisée en moins d’une seconde, mais cela n’est toutefois pas assez rapide pour être réalisé à chaque rafraîchissement de l’écran. Ces modifications se feront donc non pas sur le backbuffer, mais sur les surfaces des sprites même. Ainsi les modifications restent à jour une fois les calculs effectués, puisque ces surfaces ne sont pas effacées.

En pratique, chaque composante RVB est codée sur un entier entre 0 et 31, sauf pour le vert qui est entre 0 et 63 (nous rappellelons que les couleurs du jeu fonctionnent en 16 bits par pixels). On assombris alors la composante R de 12 unités, la V de 24 (deux fois plus) et la B de 6 (afin de garder quand même une teinte bleutée).

Maintenant, il suffit juste de savoir comment modifier les composantes RVB d’un pixel. Et c’est là que les choses se gâtent. Ce n’est pas si difficile en soit, mais il faut réaliser pas mal de calcul pour avoir accès à ces composantes. En effet, la couleur d’un pixel est codé sur 16 bits, et il faut décortiquer ces 16 bits de façon à en sortir les 5 bits de la composante R, les 6 de la composante V et les 5 derniers pour la B. Nous utiliserons pour cela une fonction que nous avons appelé Fade(.) qui permet de diminuer ou d’augmenter les composantes de chaque pixel situés dans un rectangle dont les dimensions sont passés en paramètres de la fonction. Cette fonction permet par exemple d’éclaircir ou d’assombrir une zone d’une surface. Mais on peut aussi l’utiliser pour réaliser l’assombrissement bleuté qui nous intéresse.

A vous ensuite dans votre programme de créer un fichier comprenant la liste des zones de sprites à assombrir pour la nuit (certains sprites doivent rester tel quel, comme les sprites d’intérieurs). Réalisez ensuite une fonction qui va appeler la fonction Fade() pour chaque zone à assombrir.

Nous donnons ici la fonction permettant d’assombrir ou d’éclaircir une zone de surface.

Code correspondant à l’effet

void Fade(LPDIRECTDRAWSURFACE7 Surface, int Seuil_Rouge,
int Seuil_Vert, int Seuil_Bleu,
int xhg, int yhg, int xbd, int ybd)
{
//fonction permettant d’ombrer ou d’éclaircir un
//rectangle d’une surface quelconque selon des seuils
//définis (entre 0 et 31 chacun)

DDSURFACEDESC2 desc;   //description de la surface
WORD Couleur;          //couleur du pixel
WORD * Add;            //adresse de la surface (tableau des pixels)
unsigned int i,j;      //compteurs
int r,v,b;             //composantes du pixel à modifier

//récupération de la description de la surface
memset(&desc,0,sizeof(desc));
desc.dwSize = sizeof(desc);

if (SUCCEEDED(Surface->Lock(NULL,&desc, DDLOCK_NOSYSLOCK|
DDLOCK_WAIT,NULL))) //vérouillage de la surface
{
//récupération de l’adresse de la surface
WORD * address = (WORD *)desc.lpSurface;
//on parcourt la zone pour modifier les pixels
for (j=yhg;j<ybd;j++)
{
for (i=xhg;i<xbd;i++)
{
Add = address + (desc.lPitch/2) * j + i;  //décalage en (i,j)
Couleur=*((WORD *)Add); //récupération de la couleur du pixel
//récupération des composantes r,v,b (format 16 bits)
//par l’application de masques binaires
r=(Couleur>>11) & 0×1f;  //0×1f = 0b11111
v=(Couleur>>5) & 0×3f;   //0×3f = 0b111111
b=(Couleur) & 0×1f;      //0×1f = 0b11111

if (Seuil_Rouge>=0)   //décrémentation de la composante rouge
{
if (r>Seuil_Rouge)   r-=Seuil_Rouge;
else if (r!=0)       r=1;
}
else                  //incrémentation de la composante rouge
{
if (r<31+Seuil_Rouge)   r-=Seuil_Rouge;
else                    r=31;
}
if (Seuil_Vert>=0)    //décrémentation de la composante verte
{
if (v>2*Seuil_Vert)   v-=2*Seuil_Vert;
else if (v!=0)        v=1;
}
else                  //incrémentation de la composante verte
{
if (v<63+2*Seuil_Vert)   v-=2*Seuil_Vert;
else                     v=63;
}
if (Seuil_Bleu>=0)    //décrémentation de la composante bleue
{
if (b>Seuil_Bleu)   b-=Seuil_Bleu;
else if (b!=0)      b=1;
}
else                  //incrémentation de la composante bleue
{
if (b<31+Seuil_Bleu)   b-=Seuil_Bleu;
else                   b=31;
}
//recoloration du pixel d’origine
*((WORD *)Add)=(r<<11)+(v<<5)+b;
}
}
Surface->Unlock(NULL); //dévérouillage de la surface
}
}

Astuce

Pour ceux qui voudraient bénéficier de cet effet dans leur jeu sans souffrir du temps de calcul, il leur faudrait réécrire cette fonction en assembleur (de façon à l’optimiser à fond, vu qu’elle peut être appelée un bon millier de fois voire plus), ou bien passer à la 3D en appliquant un sprite transparent bleu sur tout l’écran.

Création de fractales

Vous connaissez sûrement ces images que l’on appelle “fractales”. Ce sont des formes extrêmement irrégulières et complexes avec une infinité de détails qui apparaissent lorsqu’on zoome sur une portion de l’image.
Les fractales sont un sujet vaste mais il suffira de connaître quelques notions mathématiques sur les nombres complexes pour générer des images intéressantes.

Les nombres complexes

Il s’agit d’une extension des nombres réels. Les nombres réels sont d’habitude représentés sur un axe (1 dimension). Les nombres complexes sont quant à eux présents sur un système à 2 axes (un plan en 2 dimensions). Pour donner une idée plus précise, le nombre complexe s’apparente à un vecteur à 2 dimensions.

La notion de nombre complexe implique celle du nombre imaginaire i (les physiciens utilisent la lettre j).

De quoi s’agit-il ? Ce nombre imaginaire est en fait égal à la racine de -1.
Cela peut sembler impossible à priori mais c’est justement pour cela qu’il a fallu créer un nouvel ensemble de nombres aux propriétés différentes de celles des réels.

La notation usuelle d’un nombre complexe z et de son conjugué (un z avec une barre) :

Remarque

D’où provient ce i*i=-1 ?

On prend un nombre complexe j = 0 + 1*i. D’après la propriété de la multiplication d’un nombre complexe, on a j*j = (0 + 1*i) * (0 + 1*i).
Ce qui donne : j*j = -1 + 0*i = -1.

On trouve aussi une autre notation sous forme de couple : z=(a,b). Le nombre a est la partie réelle et le nombre b est la partie imaginaire du nombre complexe. On utilisera des floats ou des doubles pour les représenter lors de la programmation. Avec une préférence pour les doubles et leur précision supplémentaire. On peut effectuer les calculs avec des entiers mais il faut le faire en fixed point et le manque de précision se fera ressentir

Pour calculer des fractales, il faut encore considérer quelques opérations élémentaires sur les complexes. Mis à part le nombre imaginaire, dont il ne faut pas se préoccuper, il n’y a que des additions/soustractions et des multiplications.
Ces propriétés se font sur les deux nombres complexes z1 et z2 définis ci-dessous :

En représentant les nombres complexes dans le plan complexe, on se rend compte immédiatement de la similarité avec un vecteur en 2 dimensions. Le conjugué de chaque nombre complexe correspond à son symétrique selon l’axe des réels.

Le plan complexe Z

En continuant avec cette idée de vecteur, on peut définir deux valeurs associées à chaque nombre complexe : le module et l’argument.

Le module d’un nombre complexe est la longueur entre l’origine et le point correspondant au nombre complexe sur le plan.
Il s’agit de la norme du vecteur formé par la partie réelle et imaginaire du nombre. Le module est représenté par la lettre r sur la figure ci-dessous.

L’argument d’un nombre complexe est l’angle (lettre alpha sur le graphique) formé par ce même vecteur avec l’axe des réels (axe X).

Mathématiquement, pour un nombre z = a+b*i, on trouve facilement le module grâce au théorème de pythagore et l’argument avec un peu de trigonométrie, il s’agit de l’inverse de la tangente de b/a (arc tangente, arctan).
Les formules correspondantes sont données ci-dessous.

Le Mandelbrot

Le fractale de Mandelbrot est une figure très connue que l’on doit au mathématicien français du même nom. Il a découvert les étranges propriétés de cet objet et depuis le début des années 80, on utilise l’ordinateur pour afficher ces ensembles intriguants.

Pour le dessiner, on doit calculer pour chaque pixel de l’image une certaine valeur. Chaque pixel correspond en fait à un nombre dans le plan complexe et c’est grâce à cette position dans le plan que nous pourrons effectuer les calculs nécessaires. Ces calculs sont itératifs, c’est à dire qu’il va falloir faire une boucle pour chaque pixel. C’est sous la forme d’une suite que va se matérialiser ce calcul itératif. Pour le Mandelbrot, elle est définie comme ceci :

Cela veut dire que pour calculer la valeur suivante en (n+1), nous allons réutiliser le résultat obtenu juste avant en (n). Ce résultat est multiplié par lui-même et on lui ajoute une constante (un nombre complexe). Au niveau de la programmation, nous aurons donc une boucle avec une variable temporaire qui stocke le nombre complexe z(n), effectue le calcul et écrase la valeur précédente.

Maintenant, il faut déterminer combien de fois nous allons effectuer les opérations contenues dans la boucle, c’est ce nombre d’itérations qui déterminera la qualité et la précision du fractale. Pour le Mandelbrot, une valeur comprise entre 20 et 50 donne de bons résultats. On voit que cela fait beaucoup de calculs pour tous les pixels d’une image ! Il y a des optimisations possibles mais nous n’en parerons pas ici.

Maintenant, vous vous demandez à quoi va nous servir le résultat de la suite (sous forme de nombre complexe) que nous obtenons à chaque passage dans la boucle. Pour calculer l’intensité du pixel, il faut savoir si cette suite converge ou diverge (si elle s’écarte ou s’approche d’une certaine valeur). On fixe pour cela une valeur “limite”, si la suite (c’est à dire notre variable qui stocke le résultat dans la boucle) atteint la valeur désirée avant la fin de toutes les itérations (on verra plus loin que le module du nombre est employé lors de ce test), on s’arrête et on utilise le nombre d’itérations déjà effectuées pour calculer la couleur du pixel.

Par exemple, si l’on fixe un maximum de 50 itérations pour notre boucle et que la suite arrive au résultat voulu en seulement 25 itérations, on utilisera le nombre 25 pour calculer la couleur. Si la suite ne converge pas, on arrivera au terme des 50 itérations et on utilisera le nombre 50 pour calculer la couleur. Sans entrer dans des détails (cette notion de convergence est liée à ce que l’on appelle des attracteurs), on peut dire que la convergence de la suite indique si notre pixel se trouve dans le fractale, plus ou moins au bord ou à l’extérieur.

Il manque encore quelques éléments pour calculer complètement la suite. On ne connait pas la valeur de la constante c que l’on additionne à chaque étape, nous allons y revenir. Que vaut aussi z(0), c’est à dire la variable qui stocke le résultat au tout début de la boucle ? On va simplement l’initialiser avec le nombre complexe z=0 + 0*i et ceci pour tous les pixels de l’image. En la faisant varier, on obtient un autre type de fractale, le Julia que nous traitons plus loin dans ce cours.

Pour trouver c, nous allons définir une zone rectangulaire dans le plan complexe. A chaque point du rectangle dans le plan complexe correspond un pixel sur notre image. Les coordonnées de ce point dans le plan vont nous donner directement c. Ce nombre complexe ne varie pas lorsque nous faisons la boucle sur le même pixel mais varie lorsqu’on change de pixel, car nous nous déplaçons dans la fenêtre. En faisant varier la position et la taille de cette zone délimitée dans le plan, on peut zoomer et se déplacer dans le fractale.

Cette figure montre la correspondance entre les points du plan (fenêtre) complexe et ceux de l’image. Par exemple, lorsque nous calculerons la couleur du pixel p1, nous utiliserons z1 pour remplacer c dans la suite de Mandelbrot.
Pour p2, nous changerons le c et le remplacerons par z2.

Pour calculer facilement c à partir de la position d’un pixel, nous disposons des coordonnées de la fenêtre dans le plan complexe, les coordonnées des 2 coins opposés du rectangle sont nécessaires, nous avons le complexe (a1,b1) pour le coin supérieur gauche et (a2,b2) pour le coin inférieur droit. Il suffit d’en interpoler les parties réelles et imaginaires, c’est une affaire de proportions entre les dimensions des 2 rectangles et par interpolation linéaire, on trouve la valeur intermédiaire.

// calcul des deltas
double delta_reel = (a2-a1) / largeur_image;
double delta_imag = (b2-b1) / hauteur_image;

// pour trouver c d’après un pixel en (X,Y)
c_reel = a1 + X * delta_reel;
c_imag = b1 + Y * delta_imag;

Pour le Mandelbrot, on utilise pour le coin supérieur gauche, le complexe (-2, 2) et pour le coin inférieur droit, le complexe (2,-2). Ces valeurs permettent d’encadrer la globalité de la figure. Nous allons revenir sur le principe de convergence évoqué plus haut. Dans la boucle, nous n’allons pas tester la partie réelle et imaginaire du nombre calculé mais son module. C’est le module qui va nous indiquer si la suite converge ou pas. Voici en pseudo-code les diverses opérations. Bien entendu les opérations mathématiques s’effectuent selon les règles des complexes. Les programmeurs C++ profiteront de la
surcharge des opérateurs :

// pour chaque pixel (x,y) de l’image

c = trouver_c(x,y);
z = (0,0);

for (n=0;n<iterations;n++)
{
z = z*z + c;
if (module(z)>2) break;
}

// afficher le pixel selon la valeur de n - ici en niveaux de gris.
couleur = (n*255)/iterations;
putPixel(x,y,couleur);

On voit que la convergence selon le module est testée avec la valeur 2. Elle est déterminée expérimentalement mais une valeur trop petite va tronquer le fractale. En ce qui concerne l’utilisation du nombre d’itérations pour la valeur du pixel, il y a une grande variété de formules que l’on peut employer. Avec un peu d’imagination on arrive à de bons résultats. Si vous travaillez avec une palette, vous pouvez faire du “color-cycling” en effectuant une rotation cyclique de palette, à la manière des vieux clips technos. Voici 2 formules différentes pour du truecolor et les images correspondantes.

// version 1
couleur = (n*255)/iterations;
rouge = couleur * fabs(sin(zn.imaginary);
vert = couleur * fabs(cos(zn.real);
bleu = couleur;

// version 2
couleur = (n*255)/iterations;
rouge = couleur * fabs(sin(zn.imaginary*0.1);
vert = couleur * fabs(cos(zn.real*10.0);
bleu = couleur;

Le Julia

Le Julia dérive directement du Mandelbrot. Il faut uniquement modifier la boucle qui effectue le calcul de la suite pour chaque pixel. Au lieu de mettre la valeur initiale de z à (0,0), en début de boucle, on lui attribue la valeur correspondant à c. Par contre à chaque itération, nous n’allons pas additionner c mais un autre nombre complexe qui est constant pour tous les pixels, c’est très important. Ce nombre nous l’appellerons d et on trouve de bonnes valeurs en expérimentant (mais plutôt avec la partie réelle et imaginaire comprise entre -1 et 1).

const d = (0.2, 0.3);            // ligne ajoutée !

// pour chaque pixel (x,y) de l’image

c = trouver_c(x,y);
z = c;                           // ligne modifiée !

for (n=0;n<iterations;n++)
{
z = z*z + d;                    // ligne modifiée !
if (module(z)>2) break;
}

// afficher le pixel selon la valeur de n - ici en niveaux de gris.
couleur = (n*255)/iterations;
putPixel(x,y,couleur);

En modifiant le paramètre d, le Julia se transforme et des spirales se forment. Voici 2 exemples de Julia. Le premier a pour valeur d = (0.4, 0.2), le second
a un d = (0.4, 0.1) et une méthode de remplissage différente.

Conclusion

Nous espèrons que cet article vous aura permis de comprendre le fonctionnement des fractales.
Les possibilités sont infinies et c’est en expérimentant ou en reprennant des formules déjà disponibles (le net en fourmille) que vous arriverez à obtenir de belles images. Il existe aussi de nombreux logiciels qui permettent d’en générer, nous vous conseillons le programme Fractint, il est assez vieux et fonctionne sous DOS et Linux mais possède un nombre incroyable de paramètres à modifier, pour ceux qui veulent tester différents types de fractales.

Afin de vous aider à mieux comprendre comment les programmer, nous avons préparé un projet en C++ avec une classe de nombres complexes (Visual C++ 6). Il affiche un Mandelbrot et un #define permet d’afficher un Julia. Le code est légérement plus optimisé que le pseudo-code présenté ici, on peut profiter de quelques propriétés mathématiques qui sont expliquées dans le source. Pour compiler, vous aurez besoin de PTC, une librairie graphique qui n’est pas incluse mais des instructions dans le zip vous indiquent comment procéder.

Et pour finir, quelques liens sur le sujet..

Fractint

Fractals FAQ

Introduction

Autre introduction

Filtrage sur des images : les effets de flou.

Introduction

Nous allons présenter dans ce cours quelques effets de flou à appliquer sur des images. Ces filtres sont notamment employés dans tous les éditeurs d’images dignes de ce nom (Photoshop, Paint Shop Pro, Gimp,…). On les désigne parfois par le terme anglais d’effets “postprocessing” car ils ont effectivement besoin d’une image source. Ils reposent tous sur le principe de la moyenne de plusieurs pixels, ce qui a pour conséquence d’enlever les hautes fréquences d’une image (le bruit par exemple) et de lisser l’image originale.

Effet de flou – “blur”

Très répandu, l’effet de “smooth” consiste à calculer la moyenne d’un groupe de pixels dans un certain voisinage. Il en existe différents types, on commence avec la méthode la plus simple. Pour chaque pixel de notre image, on additionne les valeurs des pixels voisins et on divise la somme par le nombre de voisins. On remplace ensuite le pixel original par cette nouvelle valeur et on passe au pixel suivant. En général, on travaille dans la même zone mémoire, c’est à dire que la source et la destination sont les mêmes. On peut cependant utiliser les voisins de notre pixel provenant d’un buffer A et copier le résultat (à l’emplacement de notre pixel) dans un autre buffer B, l’effet sera moins accentué mais donne quand même un effet de flou. Certains filtres nécessitent l’une ou l’autre des approches, on le verra plus loin.

Dans la figure ci-dessus, un bloc de 3×3 pixels a été isolé. Le pixel du centre est celui qui va être remplacé après calcul. On peut utiliser quatre voisins ou huit voisins. Plus le nombre de voisins est important, plus le flou sera prononcé. Calculons le pixel du bloc de gauche, il suffit d’additionner les quatre voisins et de diviser le résultat par 4 : (5+9+2+1)/4 = 4. Il s’agit simplement d’une moyenne sur des nombres entiers et on remarque la présence d’une division, c’est pourquoi il est intéressant de travailler avec un nombre de voisins qui est une puissance de 2. Cela permet d’utiliser des shifts (décalages) au lieu d’une opération de division qui reste lente. Voici un bout de code pour illustrer cela (blur sur 4 voisins) :

int calculePixel(int x, int y)
{
int total = 0;

total += image[x][y-1];
total += image[x][y+1];
total += image[x-1][y];
total += image[x+1][y];

// décalage vers la droite -> division par 2^2 = 4
total >>= 2;

// on écrit le pixel (source = destination)
image[x][y] = total;
}

int filtreFlou()
{
for (int y=1;y<image_hauteur-1;y++)
{
for (int x=1;x<image_largeur-1;x++)
{
calculePixel(x,y);
}
}
}

Il faut faire attention à une chose, on ne doit pas sortir de notre image lorsqu’on prend un voisin de gauche par exemple. C’est pourquoi il ne faut pas commencer en (0,0) mais en (1,1) et aller jusqu’à (largeur-1, hauteur-1). La routine précédente ne tient pas compte de la couleur (RGB) mais travaille avec une seule composante (niveau de gris). Pour faire un filtrage en truecolor, il faut faire 3x plus d’opération, on doit calculer la moyenne de la composante rouge, verte et bleue de chaque pixel. Pour simplifier, le reste du cours porte sur des calculs avec une composante.

Pour augmenter l’intensité du flou, on peut effectuer plusieurs passes. C’est à dire que l’on va appeler la routine de flou plusieurs fois sur la même image (source=destination). Ce n’est pas la meilleure méthode en terme de souplesse et de rapidité mais elle est très simple à implémenter. On remarque aussi que les voisins de notre pixel ont tous la même importance dans le calcul (même pondération), les filtres plus évolués n’accordent pas la même importance à tous les pixels qui entourent celui qu’on veut calculer. C’est ce que nous allons voir avec le flou gaussien.

Effet de flou gaussien – “Gaussian Blur”

Nous allons parler ici d’une autre méthode de flou. Elle est plus compliquée que la précédente et nous allons travailler avec un “bloc” de pixels plus grand, il fera 5×5 pixels pour cet exemple. De plus, chaque pixel du bloc est plus ou moins important dans le calcul selon son emplacement. On peut facilement se convaincre qu’un pixel éloigné devrait avoir moins d’impact sur le résultat final qu’un pixel proche du centre du bloc. On représente le “poids” de chaque pixel par un tableau de 5×5 éléments (c’est la matrice du filtre ou “kernel” en anglais). A chaque pixel contenu dans le bloc considéré, on attribue une valeur de pondération.

La figure ci-dessous montre que le pixel du centre a un “poids” de 41, c’est le pixel qui est le plus important, la pondération diminue lorsqu’on s’éloigne du centre.

Matrice d’un blur gaussien de 5×5 – déviation de 1.0

L’algorithme de base fonctionne de la même manière que celui de l’autre section sauf que lors de l’addition des pixels, nous allons les multiplier par leur poids respectif, poids qui provient de la matrice. A la fin, nous divisons la valeur obtenue par la somme des valeurs présentes dans la matrice de pondération (dans le filtre ci-dessus, le total fait 273). On écrit le résultat dans un autre buffer que l’original. Il faut de nouveau faire attention à ne pas sortir du tableau alloué pour l’image. Une solution est de créer une routine spéciale pour les bords de l’image, cette fonction n’utilisera qu’une partie de la matrice. Par exemple, pour calculer le premier pixel dans le coin gauche en haut de l’image, on utilisera que le coin inférieur droit de la matrice et on effectuera moins d’opérations. Avec cette technique, on doit aussi calculer le total de la sous-matrice.

int calculePixel(int x, int y) // n’est pas prévue pour fonctionner sur les bords !
{
int total = 0;

for (int i=0;i<5;i++)
{
for (int j=0;j<5;j++)
{
total += matrice_ponderation[i][j]*image[x+i-2][y+j-2];
}
}

total /= 273;

// on écrit le pixel (source != destination)
image_dest[x][y] = total;
}

3 matrices pour le flou gaussien – la déviation est la plus grande à droite

D’où proviennent ces valeurs de pondération ? Comme son nom l’indique, le filtre utilise une distribution de Gauss. Cette courbe a la forme d’une cloche et en 3D, elle ressemble à une bosse plus ou moins large et aplatie selon un paramètre, la déviation, c’est la hauteur de la bosse prise à intervalle régulier qui donne les valeurs pour un filtre. Plus on s’éloigne du centre de la bosse, plus on s’approche de 0, c’est pourquoi on se contente habituellement de travailler avec des matrices de dimension limitée et de mettre à 0 les éléments qui en sont très proches (voir remarque plus loin). Dans la figure, la matrice de droite fait la moyenne des pixels avec plus ou moins la même importance (la bosse est relativement plate et diffuse), la puissance du flou sera élevée. La matrice de gauche a une bosse localisée principalement sur le centre, on utilisera donc surtout les pixels présents au milieu et l’effet de flou sera moins important.

En regardant le code, on se rend bien compte que ce filtrage est très lent même avec une matrice 5×5, il y a 25 multiplications, 25 additions et une division par pixel. Si on était en RGB, il y aurait 3 fois plus d’opérations ! L’optimisation de ce filtre a donné lieu à de multiples articles. Nous donnons maintenant des explications supplémentaires sur ces techniques. Si vous avez horreur des maths, ne tenez pas compte de la formule mais essayez quand même de comprendre le principe des deux passes.

On peut en effet décomposer ce filtre gaussien en une passe horizontale et une verticale avec une matrice de pondération qui est identique pour les 2 passes. Cette optimisation permet de diminuer le nombre de calculs de manière importante, en particulier lors d’un filtrage avec de grands blocs. Dans notre cas, cela fait un total de 10 multiplications et 2 divisions par pixel au lieu de 25 multiplications et 1 division.

Remarque

Le calcul de la matrice du flou nécessite que l’on indique la déviation. Si la taille du filtre est trop petite par rapport à la valeur de la déviation, le filtre sera “saturé” et atteindra un effet de flou maximale pour une certaine valeur (la matrice contient quasiment les mêmes valeurs). Plus la déviation est élevée, plus la courbe s’étale, il faut donc une matrice plus grande pour la contenir.

La fonction de distribution et sa décomposition en un produit de 2 filtres (axes X et Y de -8 à

Nous allons donc parcourir notre image en deux fois. La figure qui suit montre ce principe. Nous effectuons par exemple un filtrage sur 4 pixels (cela signifie que nous voulions calculer un flou avec une matrice originale de 4×4). On précalcule une matrice de pondération à 1 dimension qui contient 4 éléments, grâce à la formule d’en haut. A ce sujet, il est préférable de multiplier les valeurs par une constante afin d’avoir une matrice qui contient des entiers assez grands, cela évitera les calculs en floating point qui sont toujours lents.

Cette matrice est représentée par la ligne et la colonne en vert, elle vaut disons {1,6,6,1} et son total : 14. Le pixel rouge est celui dont nous voulons connaître la valeur. La passe horizontale va de ligne en ligne, on prend les voisins qui sont à gauche et à droite de notre pixel et on les multiplie avec le poids provenant de la matrice. Ici on multiplie le pixel en bleu avec la valeur 1, le pixel jaune avec la valeur 6, le rouge avec 6 et le cyan avec 1. On additionne le tout et on divise par 14. Ensuite, quand notre passe horizontale a parcouru toute l’image, on commence la passe verticale qui fonctionne de la même manière sauf que l’on récupère les pixels en colonne au lieu de scanner en ligne. Quand notre pixel est calculé, on l’écrit dans un buffer différent de l’original.

Passe horizontale et passe verticale

Flou directionnel – “Motion blur”

Le flou directionnel consiste en une passe de flou horizontale ou verticale. Nous n’allons pas traiter ici d’un flou directionnel selon n’importe quel angle mais le principe est le même. Afin de simplifier les choses, le flou directionnel donnera la même importance à tous les pixels donc nous n’aurons pas à effectuer des multiplications pour chaque pixel.

L’algorithme est très simple. Si l’on veut faire un flou horizontal d’intensité 10 (l’intensité doit être supérieur ou égale à 1) et que l’on se trouve en (x,y) alors nous allons additionner les valeurs de tous les pixels qui se trouvent sur le bout de ligne commençant en (x-5,y) et se terminant en (x+4,y), le pixel que l’on cherche est “centré”, on prend 5 pixels à gauche de lui et 4 pixels à sa droite. Il suffira de diviser la somme finale par 10 et d’écrire le nouveau pixel. Voici une première version de ce filtre.

int calculePixelMotionBlur(int x, int y, int intensite)
{
int total = 0;

for (int i=-(intensite>>1);i<intensite>>1;i++)
{
total += image_source[x+i][y];
}

total /= intensite;

// on écrit le pixel (source != destination)
image_dest[x][y] = total;
}

Bien entendu, cette version ne tient pas compte des problèmes que l’on peut rencontrer sur les bords de l’image. Il convient comme pour le flou gaussien d’écrire une autre routine qui se charge de gérer ces cas. Maintenant on peut passer à l’optimisation de ce filtre. Le problème est que plus l’intensité du flou est grande, plus on va effectuer d’additions. Il est possible d’améliorer cela en observant ce qui se passe lors d’un passage d’un pixel à celui qui le suit.

Dans le dessin ci-dessous, on considère une ligne de l’image (en jaune). Le flou a une intensité de 6 et j’ai représenté le calcul de 2 pixels de l’image (ceux dont les emplacements sont rouges, “centrés” dans le bloc). Le premier pixel est calculé comme suit : (1+9+3+5+2+3)/6, le second (9+3+5+2+3+8)/6. En comparant les sommes calculées pour les 2 pixels, on voit qu’elles diffèrent seulement de 2 éléments. Quand on passe au 2ème pixel, on enlève le premier élément du bloc précédent (ici, le ‘1′ en vert) et on rajoute un nouveau pixel (le ‘8′ en vert). Il suffit donc de stocker cette somme (sans jamais la diviser) quelque part et lors du passage au pixel suivant, de soustraire le pixel qui disparaît et d’additionner le nouveau pixel, on ne divise la somme que lors du stockage à l’emplacement final. On passe donc à un nombre d’additions qui est constant, soit 2 pour (presque) tous les pixels présents sur la même ligne et ceci pour n’importe quelle intensité de flou ! Seule l’initialisation de la somme au début de chaque ligne nécessite un calcul complet. C’est un gain de temps très appréciable. L’autre optimisation porte sur la division et selon le langage ou la machine utilisée, il peut être intéressant de la remplacer par un indexage dans une table en fonction de la somme.

Flou radial – “Radial blur”

Il existe plusieurs techniques pour simuler cet effet. La première donne une meilleure qualité de rendu mais s’avère plutôt lente, la seconde est utilisable en temps réel au détriment de la qualité même si cela reste tout à fait acceptable, une troisième méthode utilise une simple modification du flou que je décris dans la section suivante.

Il faut en premier lieu donner à la routine une position (cx,cy) qui va servir de centre pour l’effet de flou, cette position doit être dans les limites de l’image et normalement définie avec des entiers. Pour chaque pixel de l’image, on crée un vecteur qui va de ce pixel au centre du flou et on divise ce vecteur en N parties (si possible une puissance de 2 pour profiter de la rapiditié des décalages). On effectue ensuite une boucle de N itérations qui part du pixel et va en direction du centre. On récupère à intervalles réguliers les pixels et on en fait la moyenne.

Dans la figure suivante, j’ai représenté 2 pixels et le centre du flou. On voit aussi les 2 vecteurs qui ont été divisés en parties de même longueur. Les points violets représentent les pixels que l’on récupère et qui sont utilisés pour calculer la valeur finale du pixel. Le vecteur qui va du pixel (bx,by) au centre a été subdivisé en un nouveau vecteur qui s’appelle (vx,vy).

Je conseille vivement d’éviter les floatings points pour calculer le vecteur, il vaut mieux employer des fixed points, cela consiste en l’utilisation d’entiers avec de grandes valeurs pour avoir un maximum de précision. Voici un exemple de code qui calcule le flou. Dans le calcul du vecteur (vx,vy), j’utilise 16 bits pour la partie entière et 16 bits pour la partie décimale, c’est largement suffisant pour cette application. Ensuite pour chaque pixel, on commence en (px,py) et on avance pas à pas selon le vecteur, on récupère le pixel qui se trouve dessous la position en cours (startx, starty) et on l’ajoute à la somme. A la fin on divise pour obtenir la moyenne. L’image source et l’image de destination ne sont pas les mêmes, c’est important.

void radialBlur(int px, int py, int cx, int cy, int nombre_subdiv)
{
// il faudrait avoir une puissance de 2 ici pour éviter la
//division.. et faire un décalage.
int vx = ((cx-px)<<16)/nombre_subdiv;
int vy = ((cy-py)<<16)/nombre_subdiv;

// on doit travailler en fixed point ! donc avec une précision de 16:16
int startx = px<<16;
int starty = py<<16;
int somme = 0;

for (int n=0;n<nombre_subdiv;n++)
{
somme += image_source[startx>>16][starty>>16];
startx += vx;
starty += vy;
}

somme /= nombre_subdiv;
image_destination[px][py]=somme;

Cette version du code n’est pas optimale. On se rend compte de plusieurs choses en examinant l’algorithme. La division est à éviter, surtout si l’on compte en faire une utilisation en temps réel. Une autre chose, on voit que ‘vy’ ne varie pas pour tous les pixels qui se trouvent sur une même ligne (cy et py restent constants), il n’est donc pas nécessaire de le calculer à chaque fois. Finalement, notre boucle effectue 2 décalages de trop. En effet, le premier pixel se trouve en (px,py), on peut directement initialiser la somme avec ce pixel et faire une boucle de 1 à nombre_subdiv.

Je vais maintenant montrer une autre méthode qui permet d’arriver quasiment au même effet mais en temps réel. L’idée est de diviser l’image en 4 zones A,B,C,D comme dans l’image ci-dessous.

Ensuite pour chaque zone, nous allons calculer les pixels en s’écartant toujours du centre (on effectue cela ligne par ligne). Par exemple, pour la zone A, on fera une boucle pour les X, de cx vers 0 et une boucle pour les Y de cy vers 0. Les flèches indiquent le sens de déplacement pour chaque zone.

Maintenant pour chaque pixel (px,py), peu importe la zone, on crée un vecteur qui va de (px,py) au centre (cx,cy). Comme pour la méthode précédente, on le divise par une certaine valeur (ou grâce à un décalage), on obtient un vecteur (vx,vy). La différence est que nous allons simplement faire la moyenne entre le pixel (px,py) et celui qui se trouve en (px+vx, py+vy). Le gain en vitesse est évident mais il faut faire attention à une chose, l’image source et destination doivent être les mêmes ! C’est impératif car nous récupérons des pixels qui ont deja été mélangés et qui sont toujours plus proches du centre que celui que l’on traite. En gros, on “étire” des pixels depuis le centre vers l’extérieur de l’image. Avec quelques optimisations, on arrive à avoir un effet graphique qui tourne parfaitement bien. Pour améliorer la qualité de l’image, on peut employer la technique du bilinear filtering, je ne vais pas la décrire ici mais il existe sur le web de la documentation à ce sujet. Elle consiste à ne pas tronquer les positions vers des entiers mais à récupérer 4 pixels au lieu d’un seul et d’effectuer une moyenne selon la position exacte.

Flou circulaire – “Spin blur”

Il y a plusieurs approches possibles. On peut essayer de reprendre le principe du flou radial en récupérant à intervalle régulier des pixels qui se trouvent sur le même cercle que le pixel à calculer (au lieu d’avoir une droite comme le radial), il y a cependant un problème si le cercle devient plus grand que l’image, le plus simple est de dire que tout pixel en dehors de l’image est noir mais il est préférable de prendre par exemple le pixel qui se trouve sur le bord. Une autre méthode consiste à faire une série de rotations de l’image et de faire la moyenne des résultats. C’est ce qui est employé pour obtenir une approximation de cet effet avec des cartes 3D. La solution que je vais expliquer ici est basée sur l’idée des cercles mais permet d’aller encore plus vite grâce à une conversion astucieuse.

Une image est habituellement représentée selon l’axe X et Y, donc la position de chaque pixel est caractérisée par un couple (x,y), il s’agit des coordonnées cartésiennes (rectangulaires). Une autre représentation est possible, on peut dire que le centre de l’image est notre origine et chaque pixel dépend de la distance entre l’origine et le pixel. On obtient une première valeur que l’on appelle ‘r’ pour ‘rayon’. Mais ce n’est pas suffisant, plusieurs pixels peuvent se trouver à la même distance, il faut une 2ème valeur et nous l’obtenons en calculant l’angle formé entre l’axe des X et une droite qui passe par la position du pixel et l’origine. Certains d’entre vous auront reconnu qu’il s’agit d’une représentation en coordonnées polaires.

La figure suivante montre ce principe. Le cercle rouge couvre tous les angles possibles à la même distance du centre. Dans l’image en coordonnées polaires, il sera donc représenté par une droite horizontale. L’arc de cercle orange décrit des angles entre 90° et -90° mais il est toujours à la même distance du centre, c’est un segment qui ne parcourt que la moitié des angles disponibles (l’origine du segment dépend encore de l’angle que l’on considère comme initial). Et grâce à une conversion adéquate, on peut retrouver les cercles originaux depuis ces horizontales.

Nous allons créer une fonction qui transforme l’image depuis des coordonnées cartésiennes/rectangulaires vers une image en coordonnées polaires ainsi que la transformation inverse. Deux tables permettront d’accélerer les calculs. Pour simplifier le code, la taille de ces tableaux sera la même que l’image et nous convenons que l’axe horizontal représente l’angle et l’axe vertical la distance. Il s’agit d’une approximation car il y a un grand nombre d’angles et de distances possibles (ce sont des nombres à virgule contrairement aux coordonnées cartésiennes qui sont entières) et il faudrait des tableaux de taille supérieure pour tout stocker, nous utiliserons ainsi des valeurs arrondies.

Représentation d’un pixel (x,y) en coordonnées polaires

Les angles sont compris entre 0 et 360 degrés et si notre image fait 256×256 pixels, seulement 256 valeurs d’angle différentes sont disponibles, je rappelle que nous sommes dans l’hypothèse de tables de même taille que l’image. Il en va de même pour le rayon compris entre 0 et la moitié de la longueur de la diagonale (c’est la distance maximale d’un pixel par rapport au centre, elle correspond aux pixels dans les coins).

Grâce aux formules ci-dessus, on peut calculer une première table ‘table_r_p’. Pour chaque (rayon,angle) disponible, nous allons chercher quel est la position du pixel (x,y) correspondant (dans l’image source). Il faut refléchir dans l’autre sens pour cette conversion car si l’on prend tous les (x,y) et qu’on calcule le (rayon,angle) correspondant, certains pixels seront écrits au même endroit alors que d’autres emplacements ne seront pas remplis. C’est pour éviter ces problèmes et des “trous” que l’on effectue la conversion inverse avec en contrepartie une diminution de la qualité de l’image à cause de l’approximation.

IL faut maintenant calculer une seconde table ‘table_p_r’ qui va permettre, pour chaque (x,y), de retrouver la position correspondante dans le tableau polaire (rayon,angle). A noter que ces tables restent constantes tant que l’on ne déplace pas le centre de l’effet de flou, inutile de les calculer à chaque frame. Les tables stockent directement un index de la forme “x+y*largeur” afin d’éviter l’utilisation d’une structure.

int table_r_p[XSIZE*YSIZE];
int table_p_r[XSIZE*YSIZE];

void precalcTables()
{
int i=0;

// il s’agit du centre du flou
int centre_x = XSIZE>>1;
int centre_y = YSIZE>>1;

// la distance maximale entre un pixel et le centre
float max_dist = sqrtf((XSIZE-centre_x)*(XSIZE-centre_x) +
(YSIZE-centre_y)*(YSIZE-centre_y));

// première table, elle permet de transformer l’image vers du polaire
// (r,angle)->(x,y)

for (int r=0;r<YSIZE;r++)
{
for (int angle=0;angle<XSIZE;angle++)
{
// on trouve à quel rayon dans l’image
//originale correspond cette valeur
float real_r = (r*max_dist)/YSIZE;

// on fait la même chose pour l’angle
float real_angle = (angle*2.0f*3.1415f)/XSIZE;

// on trouve le couple (x,y) qui correspond à ce (r,angle)
int x = centre_x+real_r*sin(real_angle);
int y = centre_y+real_r*cos(real_angle);

// si les valeurs excèdent les limites de l’image, on met à (0,0)
if (x<0 || x>XSIZE || y<0 || y>=YSIZE) { x=0; y=0;}

// on stocke l’index final
table_r_p[i++]=x+y*XSIZE;
}
}

i=0;

// deuxième table, elle permet de transformer
//l’image polaire vers du cartésien
// (x,y)->(r,angle)
for (int y=0;y<YSIZE;y++)
{
for (int x=0;x<XSIZE;x++)
{
// on trouve la distance entre le centre et notre pixel
float r = sqrt((x-centre_x)*(x-centre_x) +
(y-centre_y)*(y-centre_y));

// on trouve l’angle par rapport à l’axe des X
float angle = atan2(x-centre_x,y-centre_y);

// on change l’intervalle des valeurs pour rester
//dans les limites du tableau
r*=YSIZE/max_dist;
angle*=XSIZE/(2*3.1415f);

// on arrondit les valeurs, c’est important
int real_angle = angle;
int real_r = r;

// on contrôle qd même pour être certain des intervalles.
if (real_r<0 || real_r>YSIZE || real_angle<0 ||
real_angle>=XSIZE) {r=0; }

// on stocke l’index
table_p_r[i++]=real_angle+real_r*XSIZE;
}
}
}

Une fois l’image convertie en coordonnées polaires grâce à notre première table, on peut appliquer un effet de flou horizontal. En effet, chaque ligne de cette image représente en fait un cercle dans l’image originale comme montré dans la figure plus haut. En appliquant un effet de flou horizontal sur la représentation polaire, on l’effectue en réalité sur des cercles. Une fois terminé, on transforme notre image vers sa représentation cartésienne grâce à la seconde table et on obtient un effet de flou circulaire.

Voici un exemple de ces transformations, l’image de gauche est l’originale, on la transforme en coordonnées polaires et on obtient cette image déformée du milieu. On revient ensuite aux coordonnées originales. On remarque que la qualité de l’image s’est dégradée à cause des approximations polaires, en particulier vers l’épaule à droite. Pour y remédier dans une application qui demande une meilleure précision, il suffit d’augmenter la taille des tables qui stockent les positions ou alors d’utiliser du bilinear filtering.

Une remarque au sujet de l’effet de flou horizontal, il est important de faire un flou qui “boucle” horizontalement, c’est à dire que si on arrive par exemple au dernier pixel sur une ligne, on effectue la moyenne des quelques pixels qui précèdent mais on incorpore aussi dans le calcul les pixels qui sont au début de la ligne. Par exemple pour un blur sur 10 pixels, on va de (x-5,y) à (x,y) et ensuite de (0,y) à (5,y). Cela évite des effets de coupure disgracieux dans l’image. En appliquant un flou vertical, on peut même obtenir un radial blur. L’utilisation des coordonnées polaires est aussi à l’origine d’autres effets comme le kaléidoscope mais ceci est une autre histoire

Conclusion

Vous devriez maintenant avoir une idée plus précise du fonctionnement de ces filtres. Afin d’illustrer au mieux les principes décrits ici, nous vous avons préparé un projet sous Visual C++ 6.0 qui comporte un blur gaussien, un blur circulaire et deux méthodes de radial blur. Le code est plus ou moins optimisé (cela reste du C) mais ne tient pas compte de certains effets de bords, nous avons essayé de le faire le plus simple possible. Vous avez besoin de la libraire PTC pour le compiler : http://www.gaffer.org

DOWNLOAD : BLUR.ZIP (175k)

I – Interpolations avec des splines

Je vais parler ici de courbes qui sont très souvent utilisées dans divers domaines et en particulier en infographie. La majeur partie des programmes de dessins comportent un outil “courbe” qui est en général une courbe de Bézier avec des points de contrôle. Les splines sont particulièrement intéressantes dans les applications 3D, on peut par exemple interpoler et calculer une position de caméra avec seulement quelques points dans l’espace. Les splines peuvent aussi servir à lisser des objets et les “nurbs” ainsi que les surfaces courbées de Quake III sont la conséquence directe de la puissance qui se cache derrière ces entités mathématiques. Les nurbs et les surfaces courbées ne seront pas introduits dans ce cours.

Il est nécessaire d’avoir quelques notions de base en analyse et de géométrie pour bien l’assimiler, si vous ne savez pas ce que sont des polynômes, des tangentes et des vecteurs, vous ne pourrez pas comprendre le contenu du cours.

Présentation du problème

Avant d’introduire les courbes, je vais présenter quelques notions qui seront utiles pour la suite du cours. Pour simplifier, les schémas et les formules s’appliquent à de la 2D, c’est donc avec des coordonnées (x,y) que nous allons travailler. Il est très facile de passer à d’autres dimensions en rajoutant les composantes nécessaires aux différents vecteurs.

Le mieux est de commencer directement avec un exemple pratique d’infographie qui va être amélioré pas à pas. On veut utiliser une caméra dans une scène en 3D mais on ne connait que quelques points par lesquels notre caméra doit absolument passer à tel instant. On dit qu’il s’agit d’un problème “d’interpolation”. Si la trajectoire de la caméra n’était plus obligée de passer sur les points, on parlerait d’un problème “d’approximation”. Ces points qui servent à définir la trajectoire en certains endroits, on les appelle des “noeuds” mais aussi des “clés” (key qui a donné keyframing). Très souvent, une clé contient une information sur le temps en plus de la position, c’est la définition la plus courante dans les applications 3D. On va le voir plus loin.

Le problème est de “deviner” un chemin qui relie les différentes noeuds, c’est à dire des positions intermédiaires qu’il va falloir calculer. La méthode la plus simple est de relier chaque noeud par des segments de droite et il est facile d’en tirer une formule d’interpolation.

La figure ci-dessous représente le problème en 2D. J’ai placé 7 noeuds dans le plan, chaque noeud a une coordonnée (x,y) qui permet de le situer.

Pour interpoler, on a besoin de deux noeuds et aussi d’un paramètre entre 0 et 1, celui-ci permet de dire où l’on se trouve sur le segment qui relie les noeuds, ce paramètre s’appelle ‘t’. Si t est égal à 0, alors on se trouve sur le premier noeud, si t = 1 alors notre position sera sur le noeud terminal. La formule d’interpolation linéaire est simplement :

(Xi,Yi) est la position du premier noeud, (Xj,Yj) est la position du deuxième noeud. Par exemple, pour calculer le point intermédiaire qui se trouve au milieu du segment entre (x4,y4) et (x5,y5), on fait x = x4 + (x5-x4)*0.5, la même chose pour y. En faisant varier t entre 0 et 1, on peut trouver tous les points interpolés sur ce segment.

Admettons que chaque noeud de la figure représente une position de la caméra à un intervalle régulier de 10 secondes. P1 correspond au temps 0 et P7 est la position à la 60ème seconde. Comment connaître la position de la caméra à la 36ème seconde par exemple ?

Pour résoudre cela, il faut stocker le temps pour chaque noeud/clé. On compare ensuite le temps de chaque clé avec celui désiré (il faut aussi contrôler si le temps que l’on cherche est bien valide). On peut ainsi savoir entre quelles clés l’interpolation sera calculée, en l’occurence entre p4 (30 sec) et p5 (40 sec). Maintenant, il faut trouver le paramètre ‘t’. On calcule la différence de temps entre les 2 clés, c’est à dire 40-30 = 10. On soustrait le temps de la première clé à celui du temps désiré : 36-30 = 6. On obtient t grâce à un simple rapport : 6/10 = 0.6. Il reste à calculer x et y selon la formule et l’emplacement de la caméra est déterminé.

Cette méthode peut être utilisé pour la plupart des interpolations. Cependant, on verra plus loin dans le cours qu’il existe un problème avec les splines de Kochanek et Bartels.

Les courbes d’Hermite

Ceux qui ont déjà fait un peu de géométrie analytique auront remarqué que la formule précédente est celle d’une droite paramétrique et que l’interpolation est linéaire. On pourrait imaginer une interpolation, pour chaque coordonnée, qui n’est pas linéaire et qui dépend d’une fonction sous la forme d’un polynôme. C’est exactement ce que permettent les courbes d’Hermite. Pour définir une courbe d’Hermite, il faut disposer de 2 points, comme avant, mais aussi de 2 tangentes qui font varier la forme de la courbe. P1, P2, T1 et T2 sont des vecteurs.

Une courbe d’Hermite

Les courbes d’Hermite ont besoin de 4 “bases”. Ces bases sont en fait des fonctions qui vont pondérer les paramètres de la courbe lors de l’interpolation et leur donner plus ou moins d’importance selon la valeur de t. Une base est associée à chacun des 4 paramètres de la courbe : (P1,P2,T1,T2). Je donne ici directement ces 4 bases sans faire tous les calculs pour y parvenir.

Maintenant, une explication sur la signification de ces fonctions (affichées entre 0 et 1 car le paramètre t est toujours compris dans cet intervalle). H1 et H2 vont être multipliés respectivement avec P1 et P2 et H3 et H4 avec T1 et T2 (on multiplie les composantes du vecteur avec une valeur provenant de la base correspondante). On additionne ces valeurs pondérées et on obtient la position sur la courbe selon le paramètre t, c’est la formule du vecteur r(t) ci-dessus. Quand t=0, on voit que la seule valeur non nulle dans les bases est celle qui provient de h1 car h1(0)=1. Cela signifie que r(0) = p1. Quand t=1, on a r(1)=p2, toutes les autres valeurs de pondération sont à 0. Ce comportement est celui qui est voulu dans une interpolation : se trouver aux extrémités de la courbe quand t vaut 0 ou 1.

Que se passe-t-il maintenant entre 0 et 1 ? On voit que les fonctions varient par paire avec une certaine symétrie. Toute la magie de cette formule tient au fait que nous avons aussi les pondérations sur les tangentes, ces pondérations changent selon t. Quand on part du premier point, la première tangente prend de plus en plus d’importance alors la courbe va se diriger plutôt dans la direction de T1. Cependant, l’importance de T2 augmente et celle de T1 diminue lorsqu’on dépasse une certaine valeur de t. La courbe prend alors la direction de -T2 (h4 est négatif). Il faut encore modifier la pondération sur P2 pour obtenir l’effet escompté.

Peut-être comprendrez-vous mieux avec cette analogie : une voiture est attachée à un (très gros) élastique. L’élastique est lui-même attaché à un point mobile qui avance sur une route droite, celle-ci va de P1 à P2. On ne se préoccupe pas des tangentes pour l’instant. L’avancée de l’élastique (et donc de la voiture) correspond à h1*p1 + h2*p2. C’est la position sur la droite qui relie le départ et l’arrivée.

Maintenant on fait intervenir les tangentes, leurs actions peuvent être comparées à la rotation du volant vers la gauche ou la droite. Notre voiture va s’écarter de la ligne droite et partir d’un côté ou de l’autre mais l’élastique aura tendance à la faire revenir vers le ligne droite. Cependant, si on tourne notre volant pour aller dans la direction de T1, l’élastique n’arrivera pas à maintenir la voiture au centre de la route. Après un certain moment, l’élastique reprend le dessus et la voiture ne peut plus aller aussi facilement dans la direction T1 (c’est le résultat direct de h3 qui diminue). Il devient alors plus facile de se diriger selon t2 : on tourne le volant pour aller dans la direction opposée à t2 (h4 négatif). L’élastique continue son action de traction en ligne droite et pendant ce temps, il devient de plus en plus difficile de maintenir le cap vers -T2, on arrive ainsi sur P2. Ces variations étant continues, la trajectoire de la voiture est lisse.

Spline cardinale et calcul des tangentes

Reprenons l’exemple de la trajectoire de la caméra. On dispose d’une série de clés mais il nous manque encore des informations pour interpoler avec les courbes d’Hermite. Nous ne disposons par des tangentes en chaque point et il faut trouver un moyen efficace pour les calculer. Il existe plusieurs méthodes selon le type de courbe désiré.

Le terme de “spline” désigne en fait une méthode d’interpolation par segments. Chaque segment est interpolé avec une courbe dont les bases sont la plupart du temps des fonctions cubiques. On évite d’employer des bases avec des polynômes de degré supérieur à 3 pour diverses raisons (stabilité numérique, oscillations,..). Les polynômes cubiques sont rapides à évaluer et donnent des résultats tout à fait satisfaisants pour la plupart des applications.

On a ici 5 points et une approximation de la trajectoire avec des segments en bleus. Pour trouver des tangentes convenables pour un noeud donné, on calcule un vecteur qui va du noeud précédent au noeud suivant (sécantes en vert clair). Dans la figure, on veut calculer la tangente de P2, on crée ainsi un vecteur de P1 à P3 et la tangente parallèle à ce vecteur est placée en P2. Intuitivement, on sent qu’il s’agit d’une approximation intéressante et adaptée pour tracer la courbe. Plus la distance entre 2 noeuds qui servent à calculer la tangente est grande, plus celle-ci sera allongée. (la figure ne respecte pas tout à fait cela)

Il reste un problème avec les clés initiale et finale car on ne dispose par d’une clé précédente ou suivante dans ce cas. Pour la clé initial, la tangente peut être calculée en prenant le vecteur entre la clé initial et la deuxième clé. Pour la clé final, on prend un vecteur de l’avant-dernière clé à la clé finale. Cela fonctionne bien si la courbe finale n’est pas fermée. Si le noeud initial et le noeud final sont les mêmes, on a affaire à une boucle. Cette situation demande une approche différente, il faut que les tangentes pour ces deux noeuds soient les mêmes sinon une discontinuité dans la courbure apparaîtra. Pour calculer la tangente de ces noeuds un peu spéciaux, on prend le premier et l’avant-dernier noeud.

Voici le résultat de l’interpolation et les tangentes dans le cas d’une courbe qui ne fait pas de boucle :

Les splines cardinales ont un paramètre multiplicateur qui modifie la longueur de chaque tangente. Il est positif et normalement inférieur à 1 mais ce n’est pas obligatoire. Une valeur négative provoque un bouclage de la courbe en chaque noeud ce qui n’est pas souhaitable (à priori). A noter que si alpha est nulle, on retrouve visuellement une interpolation linéaire avec des segments de droite. Avec alpha=0.5, on a affaire aux splines de Catmull-Rom, cette catégorie est parfois décrite sous une autre forme avec des bases différentes de celles d’Hermite et un calcul qui se fait sans les tangentes mais avec 4 points d’interpolation.

La formule des splines de Cardinal pour la tangente d’un noeud d’interpolation d’index ‘i’ est la suivante :

En faisant varier le paramètre alpha, on peut obtenir des courbes plus ou moins accentuées. Les 4 splines cardinales ci-dessous ont un alpha valant respectivement 0.1, 0.5, 1.0 et 3.0 avec une interpolation sur les mêmes points. Une valeur d’alpha élevée peut être intéressante pour simuler des circuits automobiles, on retrouve dans la spline ainsi générée des caractéristiques spécifiques (épingle, virage serré, ligne droite…), il faut juste veiller à ne pas avoir d’intersections entre les différentes parties de la courbe.

Splines de Kochanek-Bartels (TCB)

La principale limite des splines de Cardinal concerne les tangentes, il n’est pas facile de modifier l’intensité de la courbure comme on le désire et d’obtenir des variations localisées sur une portion de spline. En 1984, Kochanek et Bartels se sont attaqués à ce problème et ont élaboré une méthode qui permet de calculer des tangentes plus complexes. Cette catégorie de splines porte leurs noms : KB-Splines ou parfois sous le nom utilisé dans 3D Studio : TCB-Splines. Vous en aurez besoin si vous voulez calculer avec fidélité la trajectoire de la caméra contenue dans un fichier .3ds par exemple.

Pour chaque point de contrôle, il faut définir 3 nouveaux paramètres :

- Tension
- Continuité
- Tendance (”bias”)

La tension représente le rayon de courbure en ce point. Si on le fait varier, le virage sera plus ou moins “serré”. La continuité est un indicateur du “rebroussement” de la courbe, un changement de ce paramètre provoque des virages plus ou moins anguleux et dans les cas extrêmes on observera des “coins” aux emplacements des points de contrôle. La tendance est simplement la direction que la courbe prend lorsqu’elle passe sur le point concerné.

Avec ces 3 paramètres, on va calculer 2 tangentes par point au lieu d’une, cela permet de créer par exemple les rebroussements cités dans le paragraphe précédent. Nous avons donc une tangente “entrante” (E) et une tangente “sortante” (S). Si on interpole du point P1 au point P2, on va prendre la tangente sortante de P1 et l’entrante de P2 et appliquer la méthode vue pour les splines de Cardinal.

Les formules sont les suivantes pour un noeud d’index ‘i’ :

Si t=c=b=0, on retrouve les splines de Catmull-Rom. Etudions la variation des paramètres, on commence par modifier la tension, tout en laissant la continuité et le bias à 0. En haut à gauche, la tension est à 1. On obtient une interpolation classique avec des segments. En haut à droite, tension à 0.5, la courbe devient plus lisse. En bas à gauche, tension à -1. En bas à droite, la tension est à -5, on remarque à quel point les noeuds laissent “couler” la courbe sans la retenir dans les virages.

Variation du paramètre de tension

Maintenant la continuité, le reste des paramètres est à 0. En haut à gauche, elle vaut 3. En haut à droite, le paramètre est à 1. En bas à gauche, il est à -2. En bas à droite, cas un peu extrême, la continuité vaut -5. Quand elle est négative, la continuité agit un peu comme un nouveau noeud qui aurait été rajouté au milieu du segment à interpoler et qui aurait une tangente perpendiculaire à ce segment. On le devine grâce à la forme en S sur les courbes internes et une pointe très nette près des noeuds.

Variation de la continuité

Finalement, examinons les modifications de la tendance. Elle agit de manière symétrique quand on passe dans des valeurs négatives. Voici deux exemples avec des valeurs égales à 1 et 3. On s’aperçoit que la courbe “arrive” par la gauche sur le point marqué en rouge. La même valeur mais négative inverserait cette direction.

Variation de la tendance (bias)

Correction des tangentes en fonction du temps

On va voir qu’il existe un problème avec les tangentes de Kochanek-Bartels dans le contexte d’une interpolation selon un paramètre de temps. Il n’est pas question ici du simple affichage d’une spline mais du déplacement forcé d’un objet sur la spline (une caméra par exemple). En définissant un déplacement sur une spline dont les clés sont séparées par un intervalle de temps variable, des erreurs de vitesse et de direction vont apparaître inévitablement.

Les formules de la section précédente ne comportent aucune indication sur le temps, on se contente de prendre les positions et l’utilisateur n’a pas les moyens pour contrôler la vitesse de déplacement sur la trajectoire. Pour manipuler la vitesse de façon plus commode, on peut faire varier la longueur des tangentes en fonction du temps de chaque clé concernée, le résultat est une modification de la forme de la courbe. Le but est de forcer la continuité de la vitesse lors du passage sur le noeud et ceci pour les deux tangentes (mathématiquement, il faut que la dérivée première soit continue). C’est la solution initialement proposée par Kochanek et Bartels pour résoudre ces cas. Ils ont encore fixé comme hypothèse la continuité de la courbe (le paramètre continuité vaut 0), ce qui est assez logique quand on désire avoir une vitesse continue.

On a par exemple 3 noeuds avec le temps de passage sur chaque noeud. Pour simplifier, on a t=c=b=0 (Catmull-Rom). La tangente de P2, calculée sans correction selon le temps, est le vecteur bleu en P2. Il s’agit du même vecteur que ce soit pour la tangente entrante ou sortante. La vitesse sur le segment P1-P2 n’est évidemment pas égale à celle du segment P2-P3. En modifiant le temps en P2 (par exemple de 10 à 20), on va changer les vitesses sur les deux segments et pourtant la tangente ne varie pas puisqu’elle ne tient pas compte de ces paramètres temporels. Kochanel et Bartels proposent donc d’utiliser cette correction sur les tangentes :

La variable ’s’ désigne le temps en chaque noeud d’index ‘i’. Dans la figure, s1 = 0, s2=10 et s3=100. Il faut donc pondérer selon les différences de temps entre les clés utilisées dans le calcul de la tangente.

Dans un article plus récent sur ce type de splines, Dave Eberly fait remarquer que cette méthode n’est pas tout à fait correcte (voir remarque plus bas pour la référence). En effet, la tangente par rapport à une trajectoire représente la vitesse de l’objet qui suit cette trajectoire. Avec la correction de Kochanek-Bartels, les deux tangentes n’ont pas toujours la même longueur, cela voudrait dire que nous avons deux vitesses pour le même point. Il propose de les calculer plutôt comme suit, les formules peuvent paraître compliquées mais elles ne diffèrent que de quelques termes par rapport à celles de Kochanek-Bartels, elles assurent la continuité dite C1 alors que Kochanek-Bartels se sont contentés de G1 (j’explique dans le cours consacré aux courbes de Bézier de quoi il s’agit exactement). Si le paramètre de continuité n’est pas à 0 mais que l’on veut quand même avoir une vitesse continue, alors il faut pondérer les vecteurs avec les coefficients A et B. Ceux-ci qui sont calculés à partir des normes des tangentes (non modifiées).

Remarque

Le document PDF “Kochanek-Bartels Cubic Splines (TCB Splines)” de Dave Eberly est disponible sur http://www.magic-software.com – les étapes pour aboutir à ces formules et leur fonctionnement y sont expliqués plus en détail.

Conclusion

Le code ne devrait pas trop poser de difficulté. La méthode la plus simple consiste à avancer dans le tableau des clés. Une fois qu’on connait les noeuds à interpoler, on effectue une autre boucle avec un argument entre 0 et 1 qui est incrémenté avec un petit pas (par exemple 0.05), il correspond au t des fonctions d’Hermite. On trace ensuite des lignes entre ces différents points intermédiaires. Il existe des méthodes plus évoluées qui tiennent compte de la forme de la courbe. Ces techniques ne sont pas forcément nécessaires, elles s’adressent plutôt à des fins d’affichage de la spline pour du dessin vectoriel. En 3D, on utilise les splines pour le fameux “keyframing” et dans ce cas, on se contente de calculer la position exacte du point sur la spline selon un paramètre de temps.

J’ai préparé un projet en MFC et OpenGL qui illustre une utilisation en 3D. Il s’agit d’une caméra qui se déplace le long d’une spline d’Hermite, elle pointe toujours dans vers l’origine où se trouve un tore. La courbe est paramétrable et vous pouvez tester la différence entre une interpolation linéaire et une interpolation de type spline. Le code n’est compilable qu’avec Visual .NET (peut-être Visual 6.0 mais il faut refaire le projet), la présence des MFC empêche à ma connaissance d’utiliser le projet avec d’autres compilateurs. Néanmoins, le zip comporte un exécutable prêt à l’emploi.

Chargement du code : SplinesMFC_Src.zip (98k)

Vous pouvez lire aussi la suite de ce cours où j’introduis les courbes de Bézier et une autre catégorie de splines, les B-Splines.

Courbes d’interpolation et d’approximation II

Après avoir introduit les splines et leur calcul, nous allons nous intéresser à d’autres familles de courbe. La première partie du cours est dédiée à l’étude d’une courbe très célèbre dans le monde de l’informatique : la courbe de Bézier. La seconde partie du cours s’intéressera aux B-Splines qui sont des cousines de la courbe de Bézier.

Sans plus tarder, examinons de plus près cette fameuse courbe de Bézier.

Courbe de Bézier

On la doit à l’ingénieur français, Pierre Bézier, qui travaillait chez Renault dans les années 60. Il se pencha sur les problèmes liés à la conception des surfaces en 3D pour les premiers programmes de CAO (conception assistée par ordinateur). Le système UNISURF issu de ses recherches permettra à Renault de dessiner et découper la carrosserie de la plupart des automobiles de la firme.

L’enjeu était de trouver un moyen pour définir des courbes de manière précise afin que les machines puissent procéder aux découpes. Il fallait donc trouver un système de paramètres défini de manière rigoureuse et le plus simple possible. Les dessins complexes (carrosseries, coques, fuselages…) étaient jusque alors fait à main levée par les designers et aucune machine ne pouvait récupérer facilement l’information depuis un dessin. Les machines les plus avancées utilisaient des ellipses pour calculer les zones à découper. Les courbes d’interpolation connues en ce temps n’étaient pas adaptées pour ce travail car elles n’offraient pas un contrôle suffisant sur la forme des arcs et la géométrie finale des objets, il fallait aussi attendre que la technologie des machines-robots évolue en parallèle avec l’électronique. Paul de Casteljau, qui travaillait lui chez Citroen, avait défini dès 1958 des méthodes pour créer des surfaces en 3D mais son approche était moins pratique que celle de Bézier. Les travaux de Casteljau permirent à Bézier d’améliorer le concept grâce à l’ajout des “poignées de contrôle” et cette nouvelle famille de courbes remporta un vif succès dans l’industrie. Par la suite, un groupe de recherche d’Apple (ces personnes créeront plus tard Adobe) récupéra cette invention pour définir les premières polices vectorielles, les imprimantes fonctionnant un peu comme les machines de Renault.

De manière plus précise, la courbe de Bézier (cubique, c’est la plus courante) est une courbe d’interpolation qui nécessite 4 points pour définir un arc. Le premier point et le dernier sont des noeuds, la courbe passe par ces points. Les deux autres points sont des points de contrôle, ils permettent de définir la forme de la courbe, celle-ci ne passe pas par ces points de contrôle (sauf pour les cas spéciaux avec des noeuds alignés). Les points de contrôle correspondent aux “poignées” des programmes de dessin vectoriel.

On peut facilement créer des boucles en positionnant correctement les poignées et les points. Contrairement aux splines qui suivent une trajectoire plus aléatoire et moins intuitive, les courbes de Bézier permettent de définir facilement les limites de l’objet : une courbe de Bézier est toujours contenue dans le domaine décrit par l’enveloppe convexe, celle-ci est formée par les 4 points. Cette propriété permet de déterminer rapidement si la courbe pourrait être en collision avec un objet. Dans l’affirmative, il faudrait encore effectuer des tests supplémentaires pour en être certain.

Une courbe de Bézier cubique et quadratique avec leur enveloppe convexe

Le calcul des courbes de Bézier est analogue à celui des splines vues dans la première partie de ce cours. Des bases (polynômes) sont utilisées pour pondérer les 4 points qui constituent une courbe.

En fait, une courbe de Bézier peut être définie sur N points et cela modifie le degré de la courbe mais je ne parle ici que des courbes de Bézier cubiques, c’est à dire des courbes dont les bases sont de degré 3. Pour définir une courbe d’un degré N, il faut N+1 points. En général, on se contente des courbes de degré 2 (quadratique, 2 noeuds et 1 point de contrôle) ou de degré 3. Les applications 3D en temps réel qui doivent générer des surfaces utilisent plutôt des courbes quadratiques car l’évaluation est plus rapide et il y a moins de points de contrôle (simplification de la modélisation et/ou de la programmation). Les propriétés de l’enveloppe convexe sont maintenues pour tout N. Avec N=1, on se retrouve avec une droite normale. Des degrés supérieurs à 3 impliquent des calculs plus lourds et l’augmentation du nombre de points qui définissent la courbe peut provoquer l’apparition d’oscillations difficiles à gérer, c’est un problème classique des méthodes d’interpolation de degrés élevés.

Une autre propriété des courbes quadratiques, quand elles sont utilisées en 3D, est présentée dans la figure ci-dessous. Une courbe quadratique est définie par 3 points qui forment un triangle dans l’espace. Ce triangle est contenu dans un plan, la courbe évolue elle-même dans ce plan et cela limite les possibilités géométriques. En déplaçant le point de contrôle dans ce plan, on est assuré que la courbe y restera. Les courbes de Bézier cubiques et d’ordre supérieur, au contraire, peuvent évoluer complétement dans l’espace, on remarque aisément que toute tangente à la courbe (par exemple, les tangentes symbolisées par les poignées en vert sur le dessin) peut pointer dans n’importe quelle direction alors qu’avec une courbe quadratique, la tangente reste dans le plan. A noter qu’une courbe quadratique seule ne peut créer une boucle, on arrive au mieux à faire un segment de droite quand on place 2 points l’un sur l’autre.

A gauche : courbe de Bézier quadratique à 2 noeuds et 1 point de contrôle
A droite : courbe de Bézier cubique

Pour générer les bases nécessaires à l’interpolation des courbes de n’importe quel degré, on utilise les polynômes de Bernstein. Je donne ici la formule complète ainsi que les graphes correspondants aux 4 bases des courbes de Bézier de degré 3. (n=3, i=0,1,2,3)

Polynômes de Bernstein pour les courbes de Bézier cubiques

Une fois les bases déterminées, on peut calculer la courbe à proprement parler. L’opération est tout à fait similaire à celle abordée pour les splines du cours précédent. On a un paramètre ‘t’ qui varie entre 0 et 1 et on multiplie la valeur de chaque base au temps ‘t’ avec le point correspondant, on additionne les vecteurs pondérés pour obtenir la position finale. Dans notre cas, B0(t) sera multiplié avec la position P0, B1(t) avec la première poignée P1, B2(t) avec la deuxième poignée P2 et finalement B3(t) avec le point terminal P3 (voire figure ci-dessous). L’extension à des courbes de degré quelconque N est très facile, il suffit de calculer les bases de Bernstein selon N et de disposer de N+1 points.

Courbe de Bézier par morceaux et continuité

On remarque que les formules précédentes ne comportent aucune indication sur les tangentes contrairement aux splines, les tangentes étaient calculées grâce aux points qui suivaient et précédaient segment concerné. On va voir que cela pose des problèmes lorsqu’on met plusieurs “segments de courbe” (chaque segment étant une courbe de Bézier) les uns après les autres pour former une courbe plus longue. Chaque segment agit de manière indépendante et n’a aucune influence sur les autres segments. Cela permet d’introduire le concept de continuité. On a une continuité géométrique (et analytique) quand le point terminal d’une courbe (P3 dans une courbe cubique) est confondu avec le point initial du segment suivant (P1′), c’est à dire quand les deux lignes se suivent sans “trou” au milieu. Mathématiquement, on parle de continuité G0 (géométrique) et C0 (fonction continue sans “trou”). Toutefois, cette continuité géométrique n’est pas suffisante pour avoir une courbe bien lisse, on a des cassures et il faut trouver autre chose pour y remédier.

En haut, absence de continuité G0
En bas, la continuité G0 est respectée

Les cassures bien visibles dans la courbe du bas sont dues à un manque de continuité G1. De quoi s’agit-il ? Observons la deuxième courbe à l’endroit ou P2 et P3 sont confondus. Si on devait tracer des tangentes en P2 et en P3 (en prenant respectivement l’une ou l’autre des courbes), on verrait que celles-ci ne partent pas dans la même direction. On a ainsi une absence de continuité G1 car ces tangentes ne sont pas colinéaires (elles ne partent pas dans la même direction). Le concept de continuité en analyse va un peu plus loin, on parle alors de continuité C1. Il faut que les vecteurs décrivant les tangentes aient la même direction ET la même longueur. Cette condition n’est cependant pas nécessaire pour avoir un résultat visuel satisfaisant mais peut s’avérer important si la courbe est utilisée pour simuler la trajectoire d’un objet. En effet, la continuité C1 assure la continuité de la dérivée première de la courbe, cette dérivée n’est autre que la vitesse en physique. On aurait ainsi de brusques changements de vitesse si C1 n’était pas respectée.

La figure qui suit illustre le problème de la continuité de la dérivée première. J’ai du obligatoirement modifier la position des points de contrôle des deux courbes pour obtenir une continuité G1 (elle est en plus C1 dans mon exemple, avec les deux vecteurs de même longueur), ce qui a pour effet de changer la forme globale de la courbe tout en assurant un aspect lisse.

En haut : absence de continuité G1 avec des tangentes dans deux directions différentes
En bas : continuité G1 (et C1) avec une seule tangente –> courbe lisse

Le seul moyen d’obtenir une courbe lisse est d’aligner les poignées de contrôle sur la même droite. Si la continuité C1 est nécessaire, il faut que les poignées (la dernière de la première courbe et la première de la deuxième courbe) se trouvent à la même distance du noeud de jonction.

On parle parfois des continuités d’ordre supérieure. Par exemple, C2 correspond à la continuité de la dérivée seconde, c’est à dire à la continuité de l’accélération dans le cas d’un objet mobile. Pour avoir la continuité géométrique d’ordre 2 (G2 en un point), il faut que les rayons de courbure des deux courbes soient les mêmes sur ce point, c’est un indicateur de convexité (dans la figure, on voit que la courbe est convexe et devient concave au passage sur le noeud, G2 n’est pas respectée) . Les courbes de Bézier qui sont G1/C1 ont peu de chance de respecter cette condition et des contraintes supplémentaires sur la position des noeuds sont nécessaires pour y parvenir.

Il subsiste un problème avec les courbes de Bézier (disons une courbe lisse cubique avec une continuité G1). Quand on modifie la position d’une poignée de contrôle, toute la courbe sera modifiée. C’est particulièrement visible pour les points qui contrôlent la jonction entre deux courbes et le phénomène s’amplifie grandement avec des courbes de degré élevé. J’ai déplacé ici deux points pour garder la continuité G1 et C1 (le point rouge se trouve à égale distance des deux points jaunes) au détriment de la forme finale de la courbe qui est grandement modifiée. Cette influence globale des points de contrôle est parfois indésirable. Ce problème ainsi que celui de la continuité C2 est pallié par une autre catégorie de courbes : les B-Splines (cubiques).

Le déplacement d’un point de contrôle modifie toute la courbe

B-Splines

C’est une généralisation des courbes de Bézier assez nouvelle (1987) et que l’on doit à Barsky, Bartels (encore lui!) et Beaty. Les B-Splines utilisent un type de bases similaires à celui des Bézier, la propriété de l’enveloppe convexe est respectée mais la grande différence est liée à leur trajectoire. Les B-Splines ne passent pas obligatoirement pas les points de contrôle. Elles sont ainsi dans la catégorie des courbes d’approximation et non pas d’interpolation. On peut les obliger à interpoler avec des contraintes supplémentaires que je détaille plus loin dans ce chapitre. Finalement, elles rendent possible un contrôle localisé de la courbe, un déplacement d’un point de contrôle ne va pas modifier toute la courbe mais seulement une portion de celle-ci. Dans le cas des B-Splines cubiques, un point de contrôle ne peut modifier que le segment qui suit et celui qui précède. Une B-Spline est toujours considérée en tant que courbe découpée en plusieurs morceaux, ce n’est pas un segment de courbe à proprement parler comme la courbe de Bézier mais une “entité” segmentée. Avant d’aller plus loin dans les explications techniques, voici une B-Spline cubique découpée en plusieurs segments symbolisés par des traits rouges. On remarque que la courbe respecte la continuité G2 : à l’emplacement d’une jonction (traits rouges), les courbes qui arrivent par la gauche et par la droite sont les deux concaves ou convexes.

B-Splines avec une continuité G2

Dans la figure, il y a 7 points de contrôle et 5 segments avec 6 “coupures”. Le principe de la B-Spline est d’attribuer à chaque point une fonction. Cependant ces fonctions sont -toutes- les mêmes pour l’ensemble des points de contrôle s’il s’agit d’une B-Spline uniforme, ce qui va être le cas pour tout le reste de ce cours. Pour interpoler une courbe de Bézier, on avait aussi un paramètre ‘t’ qui variait de 0 à 1 et qui permettait d’indiquer la position sur la courbe et dans la base de Bernstein. La B-Spline utilise un système de base différent et un peu plus complexe. On attribue une valeur T à chaque début et fin de segment. Dans le dessin, le premier trait rouge à gauche aura pour valeur T=0, le second se verra attribuer T=1, le troisième correspondra à T=2 et ainsi de suite. Pour calculer les bases de chaque point, il faut introduire la formule récursive de Cox-de Boor. Pour mieux comprendre son utilisation, il est préférable de visualiser d’abord le résultat que l’on veut obtenir :

Les bases d’une B-Spline cubique

Ce graphique peut paraître un peu bizarre mais vous allez voir que ce n’est pas si compliqué. La formule de Cox-de Boor permet de calculer une approximation par morceaux de la courbe gaussienne avec un polynôme de degré donné, elle est représentée par la courbe en noir dans le graphique. Il s’agit ici d’une base pour des B-Splines cubiques. On décale et copie cette fonction sur l’axe des X d’une unité à chaque fois. Cela donne la série de fonctions en gris clair. Considérons maintenant un intervalle de 0 à 1 sur l’axe des X. Si l’on isole cette partie, on se rend compte que l’on est en présence de 4 fonctions différentes. La courbe verte est la partie terminale de la “cloche” qui commence en -3, la courbe bleue commence en 0. La courbe jaune fait partie de la cloche qui part de la position -2 et la rouge est une partie de celle qui commence en -1.

Comme pour les courbes de Bézier, ces 4 fonctions déterminent les pondérations pour 4 points de contrôle de la B-Spline. J’ai dis plus haut que le début de chaque segment de la B-Spline a un paramètre T qui lui est attribué. On voit que dans le graphique, le motif des 4 bases isolées se répètent dès que l’on avance d’une unité. Ainsi si l’on se place à la position 2 (qui correspond donc au segment de la B-Spline dont le début vaut T=2), on retrouve 4 bases identiques sauf qu’elles agiront sur d’autres points de contrôle. Comme une “bosse” complète partage un intervalle de largeur 4, elle influence plusieurs segments de la B-Spline finale.

C’est ce principe qui assure les modifications localisées des B-Splines. Une autre propriété fondamentale de ce type de base, c’est que l’addition des 4 fonctions donne toujours 1 (il faut être dans un intervalle où les 4 courbes sont définies). Cette contrainte sur la somme assure que la courbe sera contenue dans l’enveloppe convexe (cette propriété est aussi présente dans les bases de Bernstein). Finalement, la continuité G1 et G2 est garantie pour toute B-Spline d’ordre 3 et plus.

Je donne maintenant la formule de Cox-De Boor. Elle fonctionne de manière récursive en commençant avec un signal carré et en effectuant une convolution pour adoucir le signal quand on augmente le degré. Les calculs pour trouver les bases sous forme de polynômes étant un peu laborieux, je fournis directement les fonctions des 4 bases pour une B-Spline cubique. Le paramètre ‘t’ varie de 0 à 1. Le paramètre ‘t0′ indique où commence la fonction sur l’axe des X. Pour avoir une approximation de la courbe gaussienne complète, il faut commencer par exemple en t0=0 avec D0 qui varie de 0 à 1, ensuite t0=1 avec D1 qui varie de 1 à 2, t0=2 pour D2 et finalement t0=3 pour D3. La courbe finale a une largeur de 4 unités (c’est à dire la valeur du degré + 1)

Encadré : Formule de Cox-De Boor générale
En bas : les 4 bases d’une B-Spline cubique

B-Splines : le vecteur de noeuds

Dans la section précédente, j’ai brièvement indiqué que les B-Splines pouvaient aussi interpoler, c’est à dire passer par les noeuds sous certaines conditions. Pour aller directement aux faits, on peut obliger la B-Spline à interpoler en ajoutant plusieurs points à la suite et ceci au même endroit. Dans le cas d’une spline cubique, il faut 3 points au même endroit pour forcer l’interpolation. On perd au passage les différentes continuités (G1 et G2).

La B-Spline peut être symbolisée par les numéros de noeuds qui la composent et le nombre de fois qu’ils sont placés au même endroit, on stocke ces informations dans un “vecteur de noeuds”. Par exemple, la spline de gauche est représentée par [1,2,3,4,5,6,7,8,9,10]. Celle de droite sera symbolisée différement, au lieu d’avoir 3 points portant des numéros différents mais au même endroit, on enlève les numéros redondants et on écrit le même numéro plusieurs fois, on obtient : [1,2,3,4,5,6,6,6,7,8]. Le point ‘6′ correspond au point rouge qui a une multiplicité de 3 (comme si on avait 3 points au même endroit). Grâce à cette notation, on peut par exemple faire des B-Splines qui bouclent en retournant au premier noeud. Un noeud qui a une multiplicité de deux conserve la continuité C1. Un noeud qui apparait une fois assure la continuité C1 et C2.

Le vecteur de noeuds est plus important encore dans une sous-catégorie de B-Splines : les B-Splines non-uniformes. Ce type de splines est à l’origine des NURBS (non-uniform rational b-splines) connue dans le monde de la modélisation. Le principe est d’attribuer plus ou moins d’importance à certains segments en modifiant les fonctions de base. Dans les B-Splines uniformes, chaque approximation de la courbe gaussienne commence en 0,1,2,3,… On dit que l’espacement des noeuds est constant. Avec les non-uniformes, on peut commencer en 0, ensuite en 0.5, après en 1.5 et ainsi de suite avec des écarts non constants. Je ne vais pas traiter de ces splines dans ce cours mais on les rencontre souvent en pratique.

Exemples d’utilisations et applications

Pour vous montrer à quel point les courbes sont employées dans l’ingénierie et le monde scientifique, j’ai sélectionné quelques exemples pratiques qui touchent divers domaines.

Filtrage sonore et traitement du signal :

On veut éliminer les hautes fréquences d’un son. On utilise une courbe dont les noeuds sont des samples (intensité sonore) pris à intervalle régulier dans le son. En interpolant, on obtient une courbe lissée, résultat approximatif du son original. Pour l’analyse spectrale, on rencontre très souvent des équaliseurs qui interpolent le gain de chaque bande fréquentielle. Dans Winamp en particuler, l’équaliseur travaille avec 10 paramètres de gain et la courbe affichée est une spline (de plus, l’échelle est logarithmique et il faut tenir compte de cela lors du positionnement des noeuds). L’équaliseur de Sonique a aussi une interface graphique qui utilise, sauf erreur, des B-Splines. Cooledit dispose de filtres dont la visualisation est aussi basée sur cette catégorie de courbes. L’avantage des courbes de Bézier et autres catégories semblables, c’est que l’on est certain que la courbe ne sortira pas d’une zone donnée (donc pas de dépassement de valeurs).

On peut aussi employer les splines pour résoudre le problème inverse. En augmentant la fréquence d’un son (par exemple, passer de 22 kHz à 44 kHz), on doit rajouter des samples intermédiaires. Avec une spline, on s’approche plus du son idéal qu’avec une simple moyenne entre 2 samples (mais cela reste tout de même une approximation plus ou moins grossière).

Traitement d’images et morphing :

Comme pour le son, on veut modifier la résolution de l’image et il faut calculer des intensités intermédiaires. Les splines offrent une bonne approximation et des transitions douces entre les pixels. On peut aussi éliminer les hautes fréquences (les détails) d’une image en prenant comme noeuds, des intensités espacées par un certain nombre de pixels. On obtient ainsi un effet de flou.

La technique du morphing avec des splines consiste à créer une grille par image. Cette grille définit un quadrillage de splines dont les noeuds sont placés aux endroits pertinents de l’image (par exemple un oeil). Les noeuds étant positionnés en différents endroits entre les deux images, on calcule les positions intermédiaires et on appelle un deuxième algorithme qui déforme les deux images en conséquence, celles-ci sont ensuite mélangées par transparence. On peut comparer cela à une photographie imprimée sur une surface élastique que l’on étire en plusieurs endroits.

Dessin vectoriel :

On peut simuler l’écriture avec une plume en faisant varier la largeur de la spline en fonction de sa tangente (celle-ci indique la direction prise par la plume) et d’autres paramètres. Ce qui est très intéressant avec les splines, c’est qu’il y a peu de paramètres à stocker pour regénérer une courbe, on peut donc créer un format de fichier compact. Les splines de Kochanek-Bartels offrent des possibilités supplémentaires au niveau de l’édition de la courbe. Les fontes TrueType et Postscript stockent leur géométrie sous forme de courbes de Bézier.

Infographie et jeux :

Pour tout ce qui est lié aux animations d’objets, on implémente des splines car elles assurent des transformations fluides et plus naturelles, ceci est particulièrement important pour les mouvements de caméras et les mouvements d’objets complexes (personnages). Rares sont les jeux qui n’ont pas au moins une routine de splines implémentée dans leur code, on les retrouve partout (déplacements d’unité, interpolation lissée de paramètres,…).

Dans les jeux et particulièrement depuis Quake III, la mode est aux surfaces courbées. On parle de “patchs” de Bézier qui sont des surfaces formées par des courbes de Bézier. Cette technique permet d’adapter le nombre de polygones d’un objet. Mis à part certains problèmes liés aux continuités entre les patchs, la technique offre de nombreux avantages et une qualité indéniable, en particulier pour le rendu de terrains. Les patchs sont même supportés par les dernières cartes 3D.

Les splines permettent aussi de lisser des objets 3D et modéliser des surfaces courbées. Tous les outils de modélisation de haut niveau (3dsmax, Lightwave,…) comportent des plugins de modélisation à base de NURBS. Il ne faut cependant pas confondre cette technique avec la subdivision de surfaces qui est basée sur la décomposition des faces en un maillage plus fin selon la topologie de l’objet.

Reconnaissance de formes :

Certaines interfaces sont pilotées graphiquement, on peut exécuter des commandes avec la souris ou le stylo. En dessinant rapidement une spirale ou un carré, une action est aussitôt effectuée. Bien entendu, personne n’arrive à faire un spirale parfaite avec une souris et il faut analyser le résultat de manière plus souple. En simplifiant et en gardant les splines en tête, car il y a plusieurs manières et algorithmes pour aborder ce problème, la première étape consiste en un lissage de la trajectoire dessinée par le joueur avec une spline, cela élimine les petits détails (si on tremble par exemple) qui ne sont pas pertinents. On regarde ensuite les paramètres de la spline (on trouve facilement la courbure en un endroit donné). Si elle correspond, avec une certaine tolérance (logique floue) à un modèle stocké en mémoire, on peut effectuer l’action. En gros, grâce aux courbes, on extrait l’information essentielle et on rejette tous les petits détails inutiles.

Analyse numérique :

Les splines sont en premier lieu des outils mathématiques et les interpolations sont du domaine de l’analyse numérique. On veut par exemple calculer numériquement l’intégrale d’une fonction qui n’admet pas de primitives. Pour effectuer cela, on calcule des noeuds à intervalle régulier sur la fonction originale et on interpole avec une spline. Les splines étant basées sur des polynômes, on peut évaluer l’intégrale de chaque morceau facilement.

Compression :

Les bases des B-Splines sont utilisées pour la compression destructive avec ondelettes (wavelets). Le principe est en gros de calculer différentes fonctions et de leur attribuer des coefficients qui permettent d’approcher les données à compresser (un peu comme les séries de Fourier mais avec des bases différentes de sin/cos). On élimine ensuite les coefficients qui ne sont pas intéressants (proches de 0) pour reconstituer le flux de données, c’est ici que se produit la dégradation de la qualité.

Finances et statistiques :

Les splines permettent de calculer une courbe qui donne une idée de l’évolution des cours d’une action. Cela s’applique à tout échantillon qui peut être analysé statistiquement et de deviner des résultats intermédiaires. Par exemple, chaque deux semaines, on prend le nombre de personnes qui ont visité ProgrammationWorld et on veut faire un graphique qui donne une indication du nombre de visiteurs au jour près. En placant les noeuds à la même distance sur l’axe des X mais avec une valeur sur l’axe des Y qui varie (nombre de visites) et en interpolant avec une spline, on pourra estimer combien de personnes sont venues sur le site un jour donné. Cela donne aussi une indication sur la tendance des visites (à n’en pas douter, à la hausse).

Robotique :

On utilise des courbes en robotique pour améliorer la qualité des trajectoires et aussi traiter les collisions. Les splines demandant peu de paramètres, on peut facilement transmettre des données entre robots sans utiliser beaucoup de bande passante, ce qui ne serait pas le cas avec une multitude de points. J’ai récemment lu un article sur des robots volants dont les trajectoires sont évaluées grâce à des splines. Des contraintes étaient imposées sur la distance entre les robots, l’ordinateur calculait les splines adéquates puis envoyait les paramètres aux différents robots qui peuvent les traiter rapidement.

Conclusion

J’ai écrit un petit programme interactif en OpenGL / MFC qui permet d’afficher des courbes de Bézier cubiques et de rajouter des noeuds. Vous pourrez ainsi facilement observer les problèmes liés aux continuités quand les points sont déplacés. L’interpolation avec les polynômes de Bernstein s’effectue dans “splines.cpp”. Les autres fichiers sont principalement du code qui gère les MFC et la fenêtre en OpenGl. L’affichage de la courbe se trouve dans “GlView.cpp”.

Voila pour les courbes. Je traiterai peut-être dans un prochain cours des surfaces en 3D formées par les courbes de Bézier et autres splines. C’est une technique puissante qui revient souvent dans les applications et en particulier les jeux. Vous pouvez faire part de vos suggestions et de vos remarques sur le forum de Progworld.

Chargement des sources : BezierMFC_Src.zip (pour Visual .NET – 49k)

Sommaire des Cours

1) Programmation de jeux

2) Gestion des données

3) Génération de mondes aléatoires

4) Programmation d’un moteur de particules

5) Programmation de labyrinthes

6) Effet spéciaux en 2D

7) Création de fractales

Filtrage sur des images : les effets de flou.

9) I – Interpolations avec des splines

10) II – Courbes d’interpolation et d’approximation

Ces cours sont surtout destinés aux futurs programmeurs de jeux, mais ils contiennent des points essentiels à ceux qui veulent créer des logiciels. Nous allons dans ce cours vous enseigner la programmation de Jeux. Programmer un jeu ne se résume pas seulement a ouvrir Visual C++ et a commencer à coder…. en fait il y’a de longues étapes par lesquelles il est necessaire de passer. Certes celles-ci n’ont pas grand chose a voir avec la programmation mais elles vous simplifierons grandement la vie lors de votre l’étape de codage. Lorsque ce cours aura été assimilé, il sera neccessaire d’apprendre à utiliser Visual C++ ici, de connaître la programmation C ici et pour finir débuter la programmation de Jeux avec Direct X ici (certes la programmation avec d’autres langages est possible pour les jeux mais soyons réalistes, les performances seront toujours inferieures au C ou C++). Bonne lecture ! Pour tous commentaires (n’hesitez pas) un chti mail.

http://www.programmationworld.com/php/cours/index.php

FIN

REMEDE CONTRE LE SIDA

Remède sur le sida Images Appli est un institut de recherche privée de médecine rattaché à l’ONG Andri Afo Fiombonana . Son équipe de chercheurs dirigée par le professeur Andriamanalina Nirina a déclaré lors d’une conférence de presse le 10 Juillet au Carlton de Tana, avoir trouvé un remède au VIH SIDA. Selon cette équipe, 20 personnes touchées par le sida ont été traitée avec un succés de 100% . Ces 20 personnes seraient des personnes résidents en dehors de Madagascar. Néanmoins de nombreuses zones d’ombres persistent pour y croire totalement : d’abord il y a peu de transparence sur le remède en lui même. On sait qu’il est à base de plantes, mais il n’a jamais pu être validé par l’OMS, par des laboratoires étrangers ou même par l’Etat malgache. Par ailleurs, c’ets le flou total sur les 20 patients guéris par ce traitement, or lorsqu’on est certain d’avoir trouver un remède, les chercheurs n’hésitent généralement pas a montrer le fruit de leurs recherches ” de visu”, en chair et en os, ce qui n’est pas le cas. Un remède trouvé à Madagascar ? On ne demande qu’à y croire mais comme on doit se contenter d’affirmations sans validation autres que celles de Images Appli, on restera pour le moment très prudent ! Trèves de bla bla, voici donc les photos de cette conférence de presse au Carlton.

RESULTAT DU BACC 2008 cliquez-ici pour démarrer

Le Pr Andriamanalina Nirina est professeur de médécine à Ankatso et fondateur de l’ONG Andri Afo Fiombonana qui gère l’Institut Images Applique ( institut de management et de gestion appliquée)

LE POINT FOCAL QUI INTERESSE LE COMITE ETHIQUE EST DE SAVOIR QUI SUBVIENT A L’EQUIPE DE CHERCHEURS POUR FAIRE AVANCER LE PROJET.

A l’heure actuelle, plus d’une centaine de malades atteints du VIH/SIDA nous a adressé leurs souhaits de subir notre traitement. Pour cela, ils ont envoyé à maintes reprises leurs requêtes pour une approbation auprès des différents services de l’Administration à Madagascar, afin qu’ils puissent bénéficier de notre traitement contre cette grave maladie, mais en vain.
D’autant plus, après avoir constaté que l’ARV utilisé actuellement à Madagascar est parmi ce qui représente plus d’effets secondaires, ces malades se sont plaints.
Par ailleurs, depuis plus d’un mois, l’équipe de chercheurs a adressé au Comité d’éthique au sein du Ministère de la Santé une demande pour un contrôle d’essai mais les réponses à ce sujet demeurent encore floues.
Lors de la dernière réunion que nous avons eu le 14 août courant avec le Comité d’éthique, il n’était jamais question d’une discussion constructive voire même scientifique, sauf que de nous demander que s’il nous donne leur aval, pourrions-nous leur fournir le nom de notre subventionnaire pour faire avancer le projet en question.

Et cela ne nous amène nulle part…

LE VRAI ET SEUL REMEDE AU VIH SIDA DECOUVERT A MADAGASCAR

Depuis une décennie, une équipe de chercheurs scientifiques Malagasy s’est efforcé pour trouver une solution, voire un remède contre le VIH Sida, Cette équipe a finalement pu obtenir le fruit de ses efforts en découvrant le remède approprié. Il s’agit d’un virucide purement à la base de plantes (100%). Le traitement se base sur la phytothérapie et la durée de ce traitement est d’environ 1 mois.
L’absence totale de toxique et de bactérie a été constatée lors des tests effectués par ce groupe de chercheurs. D’ailleurs, le taux de guérison sur les 20 patients ayant subis des essais cliniques est de 100%, avec une régression totale des signes cliniques et une charge virale des malades traités. En fait, certains patients étaient en phase très critique.

UNE VERITABLE HISTOIRE DE PASSION POUR LES CHERCHEURS :

Afin d’obtenir beaucoup plus de crédibilité au résultat obtenu, ces chercheurs étaient obligés de faire ces tests dans un autre pays et en y passant leurs séjours dans le même toit que les patients atteints de la dite maladie, pour établir une relation de confiance et obtenir leur collaboration. Ils étaient très humains ces chercheurs, mais ils avaient également la foi et l’espérance quant à la réussite de leur recherche pour le bien de certains êtres vivants qui sont totalement dans le désespoir. En tout cas, cette histoire restera gravée dans la mémoire du monde entier et demeure une réalité unique et incontestable pour vaincre cette grave maladie.
Le premier traitement datait de 2003. Depuis cette date aucun symptôme de rechute n’a été constaté. Et pour que le premier patient en question soit réellement convaincu de l’efficacité du remède, un des chercheurs se portait volontaire pour prendre le médicament avec ce patient tous les jours durant le traitement.
Qui de vous ne serez pas touchés par ce travail passionné que c es chercheurs ont déployé consciencieusement avec amour et solidarité envers ses semblables atteints par ce destructeur fléau mondial . Une histoire qui fera verser les larmes des sentimentaux.
Depuis une décennie, cette équipe de chercheurs n’a reçu aucune aide ni soutient de la part d’une quelconque entité ou organisme ni sur le plan technique ni sur le plan financier…
Ils ont utilisé leurs propres moyens, leurs propres biens depuis belle lurette, ne serait-ce que pour l’achat des billets d’avion pour aller dans un autre pays, tous leur frais de séjour, …
Depuis toutes ces dernières années, ces chercheurs ont subi des entraves périlleux de tout genre sur leur travail voire même sur leur personne jusqu’à la tentative de kidnapping. Après toutes ces épreuves pour arrive au stade actuel, ces chercheurs lancent cette bonne nouvelle publiquement.

QUE NOUS RESERVE L’AVENIR ?

Dans le monde entier, tant de personnes sont atteints de cette grave maladie, bon nombre de gens est désespéré de ce qui arrive à un des membres de leur famille, tant nombre d’enfants sont condamné par cette maladie avant même leur naissance.
Tant de scientifiques ont mis leur temps dans leurs recherches, tant de hautes personnalités et organismes consacrent leur temps et leurs efforts dans la finance. Mais hélas, 25 ans se sont succédé…
Et actuellement, ce groupe de chercheurs a trouvé le remède pouvant entraîner un résultat dont le taux de guérison est de 100% sur les 20 patients traités. Ces chercheurs sont en phase de rédaction du protocole d’essais clinique contrôle auprès le Comité d’éthique du Ministère de la Santé à Madagascar.
Afin que cette équipe de chercheurs puisse se lancer sur le marché international, elle a besoin de faire un essai clinique élargie, avec beaucoup plus de nombres de personnes atteintes du virus VIH Sida. Cet essai a été revendiqué par l’OMS (Organisation Mondiale de la Santé). A l’heure actuelle, cette équipe a déjà pu réunir plus de 200 personnes volontaires à Madagascar pour participer à cet essai.
Mais pour arriver à cette étape, cette équipe a encore besoin de suivre toutes les procédures administratives par le biais de leur propre moyen financier.
C’est maintenant, qu’ils attendent les supports aussi bien matériels que financiers, des appuis et reconnaissances internationaux afin de finalise les procédures jusqu’a l’approbation par toutes les instances nationales et internationales de ce remède.
Ces chercheurs vont continuer le chemin avec leur foi tout en espérant, un jour, que ce remède puisse guérir ce grand nombre patients et enfants atteints et condamnés par le virus sida dans tout le monde entier…

VIDEO DE CHRIS ANGEL

Attention ceci n’est pas une blague ou une mise en scène!

N’éssai jamais de faire une chose pareil!!

ce sont des magie fait par le célèbre CHRIS ANGEL

http://www.youtube.com/watch?v=ovNwmhpbdlg

RETOUR A LA PAGE D’ACCUEIL

SPRINT DE 100 M BEIJING 2008

Usain Bolt, le nouveau recordman du monde et champion olympique du 100 m en9 secondes 69

100 m

la jamaicaine FRASER imite BOLT

Au lendemain du succè fracassant de son compatriote Usan Bolt,lajamaicaene

Shelly-Ann Fraser est devenue championne olympique du 100 m féminin,dimanche à Pekin,avec un temps

de10s78

17 août 2008

Aucune
des trois Jamaïcaines n'avait jusqu'ici remporté une médaille
internationale, mais elles ont parfaitement compensé l'absence de la
championne du monde en titre Veronica Campbell-Brown, seulement 4ème
aux sélections jamaïcaines fin juin  à Kingston.
Fraser est la première Jamacaïne Championne Olympique du 100 m. Samedi,

son compatriote Usain Bolt avait également été un pionnier sur la ligne

droite masculine.

 La Jamaïque, nation reine du sprint à Pékin / AFP