Le module DynaTerrain en action !


Subtilités du C/C++

31 Jan 2013, by Jérôme Leclercq

Suite à un débat avec des étudiants en haute-école d'informatique, je me rends compte que les profs ont tendance à oublier des notions qui rendent pourtant la programmation en C et C++ bien plus facile (ou performante).


La consommation mémoire de vos variables


Le détail me choquant le plus est que le professeur conseille vivement, ou plutôt impose, l'utilisation d'un short (deux octets) plutôt que d'un int (quatre octets) lorsque le contenu de la variable ne dépassera pas une valeur comme 32 767 (ou 65 535 en non-signé).

Vous vous dites sûrement que c'est mieux car de cette façon le programme consommera moins de mémoire.

Pour commencer, nous ne sommes plus dans les années 80, la mémoire n'est plus vraiment une préoccupation, la majorité des ordinateurs ayant au moins de 2go de ram.
Cependant je suis d'accord, avoir beaucoup de mémoire ne signifie pas qu'on doit la gaspiller.

Mais voici la vérité, votre programme utilisera la même quantité de mémoire mais sera en prime plus lent.

Pourquoi ? Comment diable est-il possible que mes dix variables de type short consomment autant que mes dix variable de type int ?

C'est grâce (ou à cause, si vous préférez) à la pile.

Alors qu'est-ce que la pile ?

Il s'agit d'une zone mémoire, allouée lorsque votre programme se lance, dont il se sert pour stocker beaucoup d'informations sans devoir les allouer lui-même (Une allocation de mémoire est une demande de votre programme au système d'exploitation pour utiliser X octets contigus de RAM, et ça prend un certain temps à s'exécuter).

Lorsque vous appelez une fonction, il faut bien stocker les arguments quelque part, ainsi que l'adresse à laquelle le programme devra revenir une fois la fonction terminée, et bien cela est stocké sur la pile.

Tout comme vos variables.

Que se passe-t-il réellement lorsque vous déclarez un short ? et un int ? Votre programme ne fera rien de plus qu'avancer le pointeur de la pile, et dire que ces 2 ou 4 octets-là sont pour telle variable.

Cependant, comme la pile est allouée au début de votre programme et que la taille de celle-ci reste la même du début à la fin, votre programme consommera la même quantité de mémoire.

Alors j'en vois déjà certains me dire "Oui mais si la pile possède une taille fixe, je peux déclarer au total deux fois plus de short que d'int ?".

Et ils auront raison

Cependant, la pile est très grande comparée à ces quelques octets, sous Windows elle fait par défaut 1 mo, ce qui signifie 524288 short ou 262144 int, et honnêtement si votre programme utilise plus de, disons quelques kilo-octets de variable sur la pile, c'est qu'il a un défaut de conception.

Le dépassement de pile (stack overflow) ne se produit généralement que lorsque vos avez une récursion infinie (Une fonction qui s'appelle elle-même sans jamais s'arrêter), ou quand vous essayez de déclarer un tableau d'une taille très très grande dans la pile.

Pour les stockages de grande taille (Disons plus d'un ko), on utilise les allocations dynamiques pour allouer sur ce qu'on appelle le tas (malloc/free en C, new/delete en C++), et là on se préoccupe bien du type de variable (Car cette mémoire, elle, est précieuse).

Le tas (heap) n'est rien d'autre que la mémoire RAM de votre ordinateur, avec une limitation par l'OS.

En résumé: Ne vous souciez du type d'entier que dans le cas où vous allouez dynamiquement la mémoire.

(De toute façon, en pratique, on utilise généralement des types à taille fixe pour les allocations dynamiques, donc le short ne s'utilise quasiment jamais).

Ensuite, il est vrai que le processeur gère plus facilement (moins de cycles) les int que les short, pourquoi ? Parce que les int représentent les entiers naturels de votre processeur (Ce qu'on appelle des mots), où il peut donc effectuer les opérations plus simplement, autrement il lui faut appliquer un masque sur le nombre qu'il est en train de traiter.

Soyez cependant rassuré, la différence est si infime qu'aucun benchmark ne pourrait la mesurer efficacement, mais quand on écrit un moteur 3D on a tendance à vouloir grappiller des performances partout

Deux articles de stackoverflow.com (Un très bon site pour répondre à des questions):

http://stackoverflow.com/questions/10254511/when-to-use-short-instead-of-int

http://stackoverflow.com/questions/1851468/usage-of-short-in-c

Voici mon conseil pour les short/int, utilisez int partout (Sauf si cela vous fait perdre des points en cours ...), excepté dans vos structures, car celles-ci sont susceptibles d'être allouées dynamiquement


"else if" ou switch ?


Est-il préférable d'utiliser un enchaînement de conditions ou bien un switch

Si vous vous posez cette question, je considère que vous êtes dans la capacité d'utiliser un switch et je vous dirais alors d'en utiliser un.

Utilisez les switch dès que possible lorsque vous devez tester une valeur contre une liste d'autres valeurs du même type.

Alors pourquoi me demanderez-vous ? Un switch n'est-il pas strictement équivalent à une suite de if/else if ?

Hé bien non, les switch ont la possibilité d'être bien plus optimisés que les conditions (D'ailleurs un compilateur optimisant le code est susceptible de transformer une suite de else if en switch ).

Mais pourquoi sont-ils plus rapides ? La différence est-elle vraiment importante ?

Prenons le cas où vous désirez tester une valeur entre 1 et 5, et appliquer des instructions différente pour chaque valeur possible.

Test avec des conditions

Test avec un switch

La version que vous préférez, visuellement, ne regarde que vous, la tendance étant que les else if donnent un code avec moins de lignes et moins d’indentation, et donc qu'ils sont plus appréciables.

Cependant, le switch est ici beaucoup plus rapide.

Pourquoi ? Parce qu'un bon compilateur l'implémentera via une branch table (aussi appelée jump table).

Comment cela fonctionne ?

Voici la façon de procéder:

Tout d'abord, le compilateur va générer un tableau d'adresses, adresses de quoi ? Des instructions suivant le "case" correspondant à la valeur, de cette façon:

ptr[0] = (adresse des instructions du cas '1');
ptr[1] = (adresse des instructions du cas '2');
ptr[2] = (adresse des instructions du cas '3');
Etc..

Ensuite, le compilateur va ajouter du code pour tester si la variable est bien dans l'intervalle souhaité (1 à 5)

if (val >= 1 && val <= 5)

Si elle ne l'est pas, le programme sautera aux instructions suivant le default.

Si elle l'est, le programme va ensuite faire une copie (Pour ne pas modifier la variable originale, après tout nous ne faisons que des tests ici) de la valeur et appliquer ceci dessus :

val2 -= 1;

Pourquoi ? Parce que notre premier cas est à l'indice 0 du tableau, nous adaptons donc notre valeur pour que la borne minimale et le 0 correspondent.

Et c'est ici que la magie opère, il nous suffit maintenant de faire un saut (JMP) à l'adresse indiquée par la valeur de notre tableau correspondant à la variable.

En clair ?

goto ptr[val2]; // le goto représente le JMP de l'assembleur

Et voilà ! Nous sommes désormais en train d'exécuter les instructions voulues (Jusqu'au break ou la fin du switch)

Du côté du else if, avec une valeur de 5, nous devons tester quatre autres conditions avant d'arriver au code désiré.

Encore qu'ici ce n'est pas trop grave, nos processeurs sont bien assez rapides.

Mais qu'en est-il d'une dizaine, d'une centaine de cas ?

Cela peut se ressentir sur les performances, voire même assez fortement.

J'ai fait un programme C vous permettant de tester par vous-même, via un algorithme testant les lettres de l'alphabet, exécuté sur la longueur du mot entré, en boucle (une centaine de millions de fois).

Cela devrait vous donner une idée de la puissance des switch
(N'oubliez pas de compiler en release pour avoir les véritables performances !)

Comparaison else if/switch

Attention cependant,  cette comparaison ne vaut que pour des langages compilés, où votre code peut être optimisé par un programme externe (Ou JITé, comme le javascript de nos jours), dans les langages interprétés (Ex: PHP) le switch perd l'avantage, et peut se trouver être plus lent qu'une suite de conditions.


Les bons raccourcis du programmeur fainéant


Les concepteurs du C sont comme tout bon programmeur, des fainéants.

C'est pour cette raison qu'ils ont introduis dans le C (Et donc indirectement dans le C++) des raccourcis rendant le code bien plus court, ou lisible.

Par exemple, le test de booléen, j'ai vu beaucoup de fois ceci :

int isAdult = age > 18; // Imaginons un test compliqué qu'on ne fait qu'une fois pour des raisons de performances mais qu'on doit tester plusieurs fois dans le code
if (isAdult == 1)

Je trouve cette dernière ligne particulièrement horrible, on est très loin du code naturel qui ne fait pas saigner les yeux.

if (isAdult)

Voici donc un "raccourci" possible avec les conditions, si vous désirez tester si une valeur est différente de 0, vous pouvez omettre le test d'égalité.

C'est très fréquent de tomber sur ce genre de conditions dans le monde de la programmation (Tous les langages que je connais permettent d'ailleurs cette subtilité), et on s'y habitue très vite

(Techniquement, il ne s'agit pas d'une exception ou d'un raccourci, le if testant une expression, la différence ici étant que vous fournissez directement le résultat de l'expression).


Ensuite, alors que j'assistais à un cours de C sur les structures, le professeur s'est contenté de dire ceci:

Lorsque vous accédez à un membre d'une structure, utilisez le point, lorsque vous accédez à un membre d'un pointeur sur une structure, utilisez la flèche (->)

Alors oui, c'est tout à fait exact, mais, pourquoi ? Il serait bon de l'expliquer pour que les étudiants comprennent, car comment faire de la logique avec un langage dont on ne comprends pas la logique ?

Tout d'abord, lorsque vous accédez à une variable (disons un int) dans le code et voulez l'afficher, vous faites ceci :

printf("%d", var); // var est un int

Mais lorsque vous possédez un pointeur sur un int, et que vous voulez afficher l'int en question, il vous faut déréférencer (accès à la variable pointée) le pointeur avant tout (Et ce, avec l'opérateur étoile).

printf("%d", *pvar); // pvar est un pointeur sur la variable précédente (int*)

Alors, pourquoi cette règle ne s'appliquerait pas également aux structures ? Pourquoi faire un opérateur différent juste pour les structures ?

La vérité est que cet opérateur est également possible avec les structures.

Exemple:

printf("%d", user.age); // user est une structure (Disons User) contenant un entier nommé age
printf("%d", (*puser).age); // puser est un pointeur sur la structure précédente

Des explications s'imposent

Ici, nous déréférençons d'abord le pointeur vers la structure, et ensuite accédons à sa propriété age.

Cependant, comme le point (.) possède une priorité plus élevée que le déréférencement (*), il nous faut utiliser des parenthèses.

Cette notation est particulièrement pénible pour les programmeurs, c'est pour cela que l'opérateur flèche (->) existe, c'est un raccourci pour la notation précédente.

printf("%d", user->age); // Strictement équivalent à la ligne précédente, mais tellement plus sexy

Retenez donc cette règle:

ptr->var est un raccourci pour (*ptr).var.

Tout simplement


Il existe également un raccourci sur les opérations, en effet, plutôt que de faire :

valeur = valeur + 5;

Vous pouvez faire:

valeur += 5;

Et cela vaut pour toutes les opérations !

valeur %= 5;


Le "else if"


J'ai eu un total de trois professeurs de C n'aimant pas le "else if", ne le trouvant pas clair.

Personnellement, je ne saurais m'en passer, prenons le code suivant :

Code ici.

À quoi ressemblerait-il sans le "else if" ?

À ça.

Certains trouverons ça plus clair, d'autres non, sachez simplement que ça devient un enfer au niveau de l'identation avec la seconde forme dès qu'on dépasse plusieurs "else if".

J'ai entendu quelqu'un dire que le professeur avait dit que le else if n'était pas ANSI mais il l'est, et est présent dans énormément de langages (D'ailleurs certains ont même un mot-clé elseif pour économiser un espace rendre ça plus clair).


i++ et ++i


Une autre subtilité difficile à comprendre la première fois qu'on la voit, c'est la différence entre i++ et ++i.

Tout d'abord, qu'est-ce que ça signifie en C ? Nous avons vu plus haut que pour ajouter une valeur à une variable, nous pouvions faire ceci:

var += 1;

Mais ce serait sous-estimer la paresse des programmeurs, qui ont inventé ce raccourci :

var++;

Les deux codes incrémentent (Augmenter de un) la variable.

Cependant, quelle est la différence entre  

var++;

Et

++var;

Ces deux codes sont-ils équivalents ?
C'est là qu'est la subtilité, car pas tout à fait.

Pour vous en convaincre, voici un exemple:

Imaginons une variable i valant 0.

Dans un cas nous allons faire :

printf("%d", ++i);

Et évidemment, dans l'autre:

printf("%d", i++);

Qu'est-ce qui sera affiché dans chacun de ces deux cas ? Dans le premier nous obtiendrons 1, comme prévu, mais dans l'autre nous aurons !

Quel est ce maléfice ? En réalité, var++ va renvoyer la valeur de var avant d'effectuer l'incrémentation.

Quant à ++var, l'incrémentation se fera en premier et ensuite la valeur sera retournée.

Mais dans les deux cas, après l'instruction, la variable aura bien été incrémentée

Existe-t-il une différence de performance entre ces deux instructions ? En C, absolument aucune, le même code assembleur sera généré (au retour près) car on ne sait effectuer cette opération que sur des nombres, cependant en C++, certaines classes permettent d'utiliser ces opérateurs (Je pense notamment aux itérateurs), auquel cas il est plus rapide d'utiliser la version ++i.

(Pourquoi ? Hé bien simplement parce que ces classes doivent sauvegarder l'itérateur, l'incrémenter et ensuite renvoyer la copie dans la version i++).

Personnellement j'ai pris l'habitude de faire ++i tout le temps dans mes boucles


La magie de l'éclairage

29 Jan 2013, by Jérôme Leclercq

Cela va bientôt faire un mois que l'éclairage est présent dans Nazara, et ça n'a pas été une mince affaire

Je vais commencer par expliquer comment l'éclairage fonctionne dans les jeux vidéos.

Tout d'abord, on distingue trois types de lumières.

1. La lumière directionnelle


Ce type d'éclairage est le plus simple, la lumière vient d'une seule direction, la même peu importe le sommet. C'est comme si la source de lumière se situait à l'infini.

On l'utilise pour simuler un jardin ensoleillé par exemple (La lumière directionnelle représentant notre soleil).

Dans le fragment shader, ça donne ceci (Les codes ici sont des codes d'apprentissages, ceux de Nazara ont quelques différences notamment d'optimisation).

Les variables en CamelCase sont des uniformes envoyées par le moteur.

Code source ici

2. La lumière-point

Ici, l'éclairage provient d'une source, contrairement à la lumière directionnelle, il n'y a plus de .. direction

En effet, ce type de lumière émet d'un point dans toutes les directions (Jusqu'à une certaine distance tout en diminuant au fur et à mesure).

On peut ici imaginer la lumière émise par une ampoule

(Pour ceux qui me disent qu'une ampoule n'émet pas vers le bas à cause de son socle, ils ont tout à fait raison, mais en 3D temps-réel on fonctionne par approximation).

En voici le code:

Code source ici.

3. La lumière spot


(Ce screenshot représente un spot parfait, d'une ancienne version de Nazara, les spots ont maintenant une atténuation plus fine).

Ici, le nom de la lumière la décrit parfaitement, imaginez un spot au théâtre.

Il s'agit du type de lumière le plus complexe, mais également le plus réaliste

Dans Nazara, deux angles permettent de contrôler le spot (En plus de sa position et de sa direction), l'Inner angle et l'Outer angle.
L'inner angle représente l'angle dans lequel le spot donne le maximum de sa puissance (L'atténuation y est assez faible), entre l'inner et l'outer, l'aténuation devient beaucoup plus forte, et après l'outer angle, le spot ne vaut plus rien.

Et en code cela donne:

Code source ici.

Et voilà, on a pu faire le tour des trois types d'éclairage.

Maintenant, qu'est-ce qui pourrait encore améliorer nos graphismes ?

Pour commencer, une specular map (En noir et blanc, la valeur du pixel étant multipliée à notre valeur spéculaire), pour n'avoir des réflections qu'à certains endroits-clés (Pour contrer l'effet plastique).


(Ce screenshot est plus récent que les autres et montre les spots tels qu'ils sont maintenants).

C'est déjà mieux, non ? ;)

 Ensuite, ce qui permet généralement d'ajouter de la qualité en 3D, c'est le fait d'ajouter des sommets supplémentaires (La tesselation est une façon d'y arriver, avec la puissance de la carte graphique).

Mais nos calculs se produisent sur les pixels, et non pas sur les sommets, rajouter des sommets pourrait augmenter la quantité de données que la carte graphique peut interpoler.

Mais c'est beaucoup plus cher en terme de puissance de calculs et surtout de bande-passante...

Mais, quelles sont les données relative à l'éclairage et qui sont interpolées des sommets jusqu'au pixels ?

Les normales !

Mais on ne peut pas avoir plus de normales que de sommets. À moins que... Nooon, on va pas faire ça...

Hé bien si

C'est là exactement le principe du normal-mapping; avoir des sommets "virtuels" dans une texture pour augmenter les détails des réflexions lumineuses, sans devoir pour autant augmenter le nombre de sommets.

Mais comment stocker une normale dans une texture ?

C'est là que ça devient ingénieux (Ou bidouillé, c'est selon), on se sert de trois canaux de couleurs pour représenter les trois composantes d'un vecteur, ce qui ne pose pas de problème de précision étant donné qu'il s'agit d'un vecteur normalisé.

Par exemple, prenons la composante rouge (Donc X) à 128 (Soit la moitié), ce qui vaut 0.5 en composantes normalisées.
Appliquons-lui ce calcul : 

X = 2.0 * R - 1.0

Cela nous donnera 0, 128 correspond donc à la valeur 0

Sans surprise, 255 représente 1 et 0 représente -1

Pour voir la précision, prenons 129 (129/256 = 0,50390625 en coordonnées normalisées)

Multiplié par 2, moins 1, cela nous donne X = 0,0078125.

Ce qui est donc le pas entre chaque valeur de X, c'est donc bien assez précis

En revanche, le fait d'utiliser une texture qui est en réalité plaquée contre le mesh (Ce ne serait pas drôle sinon) nous oblige à devoir utiliser une matrice de transformation pour avoir la normale finale.

De quoi sera-t-elle composée ? De la normale interpolée, mais également de la tangente (Dépendant des UV) et de la binormale (Qui n'est rien d'autre que le produit scalaire des deux derniers).

Dans le vertex shader (On peut laisser la carte graphique interpoler la matrice sans problèmes):

Code source ici.

Cette matrice sera ensuite interpolée et envoyée au fragment shader, qui n'aura plus qu'à exécuter ceci :
vec3 normal = normalize(vLightToWorld * (2.0 * vec3(texture2D(MaterialNormalMap, vTexCoord)) - 1.0));
Tout simplement (Le reste des algorithmes d'éclairage reste le même). Et le résultat ?



Et voilà pour le normal mapping

À noter que le normal mapping est l'évolution du bump mapping, qui effectuait plus ou moins la même chose mais en utilisant une hauteur pour le pixel (Plus limité).

Il existe également le parallax mapping, qui est une technique différente, basée en plus sur le déplacement des UV pour accentuer l'illusion, mais de ce que j'en sache, ce n'est pas très utilisé pour les modèles (plutôt pour le décor).

Exemple (Irrlicht):

(Je vous assure que tous les murs de cette pièce sont plats).

Oh et une dernière chose, la technique présentée ici possède un défaut majeur, elle peut rapidement bouffer les ressources (Sa complexité est de O(o*l) o étant le nombre d'objets et l de lumières).

C'est pourquoi les jeux récents, utilisant beaucoup de lumières, utilisent une technique qui vient de faire son apparition depuis à peine quelques années, le Deferred Shading.

Son principe est ingénieux, voire assez simple (Sa programmation beaucoup moins ), on créé plusieurs textures de la taille du RenderTarget, et on les utilise pour stocker des informations.

Par exemple, une texture contiendra les informations sur les couleurs (et textures), une autre contiendra les informations sur la profondeur, une autre sur les normales (Exactement comme plus haut), etc ...

Ensuite, le fragment shader compose l'image finale avec toutes les informations enregistrées dans les textures, ce qui nous fait une complexité O(o+l), permettant des milliers de lumières dynamiques dans une même scène. En prime cela permet de n'avoir qu'une seule passe géométrique (Lors du remplissage des textures).

En revanche, cette technique ne fonctionne pas avec la transparence et le filtrage antialiasing.

Il faut donc faire le rendu des objets transparents séparément (À la façon "normale") et simuler le filtrage antialiasing avec du post-effect (Détection des bords).

Plus de détails (Ainsi que des images) lorsque je l'implémenterais


Pourquoi il est perturbant de modifier le ShaderBuilder de Nazara

5 Jan 2013, by Jérôme Leclercq

Le ShaderBuilder de Nazara est un générateur de code, vous lui dites que vous désirez un shader avec telles capacités (Éclairage, bump mapping, diffuse mapping) et il va alors créer un code capable de cela et le compiler pour vous.

Alors quand je dis "générateur de code", il ne faut pas (encore) voir de système de ShaderNode dynamique et très puissant, non non, il faut voir des imbrications de conditions pour rajouter du code.

Par contre c'est vraiment perturbant de modifier ce générateur (Je suis en train d'inclure l'éclairage) :



Le problème ici est qu'il me faut penser à deux cas en même temps, celui où le diffuse mapping est actif et celui où il ne l'est pas.

C'est pour l'instant assez faisable de s'y retrouver, mais j'ai peur pour l'intégration du bump mapping et du parrallax mapping ...


Le blog de Lynix, le retour

4 Jan 2013, by Jérôme Leclercq

Salut tout le monde !

Je me décide enfin à faire revivre ce blog, ça faisait longtemps !

Je suis passé de Wordpress à Chyrp, un moteur de blog que j'adore d'ailleurs, tout à l'air tellement bien foutu. C'est dommage qu'il ne soit pas très connu.

Il ne possède d'ailleurs pas de traduction française, mais honnêtement on s'en fout.


Je vais essayer de poster régulièrement, pour parler de Nazara, des techniques que j'emploie, de quelques astuces, essayons de réussir cette fois (J'ai pris spécialement un moteur de blog léger pour ne pas me gonfler de ce côté-là).


Revenez donc de temps en temps voir si j'ai tenu ma promesse !