[Index Software] Jeux vidéo (développement)

[Bubu]

Le problème entre les API d'Opengl et de D3DX (obsolète, maintenant il y a DirectXMaths, qui utilise le SIMD) :
Les matrices sous OpenGl utilisent le stockage des valeurs d'une matrice normalement, comme en maths: Une colonne = un vecteur.
Alors que D3DX stocke ses vecteurs, en lignes dans la matrice.

Après ce n'est pas un si gros problème, il suffit de transposer la matrice (réflexion des valeurs par rapport à la diagonale).

Le seul problème, c'est que l'ordre de multiplication des matrices est inversé.
(Car vous devez le savoir surement, la multiplication des matrices n'est pas commutative. AxB est différent de BxA en général, c'est peut-être surprenant par rapport aux entiers et réels mais c'est comme ça )
Les matrices sont en bijection avec les applications linéaires, et donc parler de multiplications de matrices ou de compositions de fonctions linéaires, c'est la même chose.
Et on sait tous que la composition de fonctions linéaires n'est pas commutative. (g o f(x) != f o g(x))...

Honnêtement je préfère la version de D3DX, car on suit l'ordre logique du pipeline.
Alors que sous OpenGl, il faut raisonner à l'envers. Commencer par la fin (matrice de projection, puis matrice de scène, puis matrice de la vue) pour en arriver à la transformation finale.

Sous GLSL, le langage de shaders de DirectX, il suffit de préciser le préfixe raw_major devant la déclaration de la matrice.
Le shader transpose lui-même la matrice dans ce cas. (Enfin je pense qu'il calcule avec une matrice transposée directement).

[Bubu]

Les données élémentaires en 3D sont des vecteurs de 4 flottants.
[x, y, z, w]
Que ce soient les couleurs, les sommets ou les normales.

Pour les couleurs c'est le plus simple : [rouge, vert, bleu, opacité (alpha)], bref.

Mais pourquoi 4 composantes pour les sommets et les normales ?

Les normales ont w = 0 tout le temps. C'est pour annihiler les translations dans les calculs matriciels.
Car cela n'a aucun sens de translater les normales qui sont des vecteurs au sens géométrique. Les vecteurs géométriques n'ont pas de position, seulement une direction.
Ce qui n'empêche pas de devoir les normaliser après l'interpolation du rasteriser.

Les sommets, (les vertex (le vrai pluriel est vertices) ) ont w = 1 au début du pipeline.

Mais pourquoi alors s'embêter avec des vecteurs à 4 composantes, si c'est juste pour mettre 0 ou 1 dans la 4ème composante w ?
Et c'est la qu'interviennent les coordonnées homogènes.
Elles sont fondamentales pour calculer les positions des sommets à la projection. Ce qui fait que plus on s'éloigne, plus les objets rapetissent et se rapprochent du centre de l'écran.
En gros, on divise les coordonnées x et y par z (la profondeur) dans un repère centré sur l'écran. En fait c'est la matrice de projection qui place z à la place de w.
Ce qui n'est pas linéaire d'ailleurs. Et w ne vaut plus 1 du tout !
Le GPU fait la division par w automatiquement, c'est cablé. (Sauf pour certains shaders intermédiaires où il faut le faire manuellement).
Et donc on a une image en perspective.
Et voilà !

[Bubu]

Comment on génère les ombres ? Je vais parler du shadow mapping. (Il y a une autre technique illustre créée par John Carmack (en même temps qu'un autre qui avait déposé un brevet, mais qu'il a concédé à John Carmack : le shadow volume) Même invention par deux personnes en même temps)
Face à une scène pour une image résultat, on prend une photo (topographie car ce qui intéresse c'est la profondeur) du point de vue de la lumière. Une texture.
Ensuite on replace cette image dans l'objectif de la scène. On l'a replace dans le repère de la scène.
En fonction du résultat, c'est une catastrophe. (Ombres pixellisées) En fonction de la position et l'orientation des 2 scènes (lumière et globale) cela peut être raté.
Vu la puissance des GPUs actuels on a plus ce problème.
Et il y a des dizaines d'algorithmes qui permettent d'avoir des ombres propres.(Perspective shadow maps, calculées après la projection; trapézoidal shadow maps, qui placent la scène dans un trapèze), cascade shadow maps (on utilise plusieurs shadow maps de précisions différentes en fonction de la distance (Ces techniques améliorent artificiellement la résolution de la shadow map mais leurs contenus sont plus difficiles à exploiter); le PCF (Percentage-Closer Filtering), qui permet de mettre du "flou" sur le bord des ombres, etc. On n'en finira pas.

J'ai expliqué comment générer la shadow map, mais je n'ai pas expliqué comment on s'en sert.
La shadow map ne stocke que la profondeur d'impact de la lumière sur toute la scène. On se place selon le point de vue de la lumière, on utilise la bonne projection (une lampe directionnelle n'a pas la même matrice que celle d'une lampe torche...)
On utilise le GPU pour rendre la scène selon le point de vue de la lumière, pour obtenir uniquement le z-buffer selon ce point de vue.

Ensuite, il suffit dans le rendu final, après transformations car il faut replacer cette texture dans le repère de la scène et non du point de vue de la lumière,
de comparer la distance pour un pixel entre la shadow map transformée avec celle de l'objet dans la scène, si elle est inférieure, le pixel est éclairé, sinon il est dans l'ombre.
C'est très proche du raytracing. Mais c'est moins précis, énormément.

Pour choisir la meilleure technique, il faut savoir comment le point de vue de la lumière et celui de la scène interagissent. (Si vous êtes dans un RPG vu de dessus, si vous êtes dans un FPS, le bon algorithme n'est pas le même)
Car certains algorithmes déconnent si les points de vues de scène et de la lumière se chevauchent plus ou moins. (Et c'est aussi une grande difficulté pour le shadow volume).
Cependant, il y a des algorithmes où il n'y a pas ce problème.
Le plus simple et efficace, et sans défaut d'affichage quelque soient les points de vue des lumières et de la scène, est l'algorithme des cascades shadow map. Mais mal paramétré, les différences de résolutions sont visibles.

D'après mes maigres expériences, la gestion des ombres est extrêmement difficile au niveau mathématiques. La plus dure que je n'avais jamais rencontrée.
Car l'idée de base du shadow mapping est intuitive, mais ses implémentations beaucoup moins.
En plus aucune de ses implémentations n'est parfaite, elles dépendent fortement du point de vue de la caméra par rapport à celui des lumières.
Certains algorithmes sont inutilisables pour certaines configuration de la caméra par rapport à certaines lumières. (Projective shadow map (il y a pour cette dernière des détournements pour que cela fonctionne quand même, mais c'est inabordable pour mon niveau en maths), trapezoidal shadow map surtout).
La solution que j'ai utilisée pour mon mini moteur de jeu est le cascade shadow mapping... Mais en couleur ! On pouvait projeter une texture d'une surface transparente sur le sol opaque... Je me vante beaucoup car ce n'est pas beaucoup plus compliqué, c'est surtout beaucoup plus couteux en mémoire et un peu aussi en calcul). Imaginez qu'une vitre ait le dessin de Bubu (la pauvre), et bien il sera projeté sur le sol opaque... Cet algorithme prenait à peu près 40% du temps total de calcul pour générer une image affichable, finale... (Ce qui est trop, donc un de ses défauts)
Son autre défaut, c'est qu'il ne fonctionne qu'avec des surfaces transparentes (cumulées) sur une surface opaque... Transparent sur transparent = pas d'ombres.
L'ultime solution : le ray-tracing !

[Bubu]

La technique du shadow volume a été abandonnée.
Car son défaut n'est de prendre en compte que la géométrie.
Elle a pourtant été utilisée avec succès dans Doom3, Quake4, Deus Ex2, Far Cry. Entre autres.
Impossible avec cette technique d'avoir des contenus flous, ou en pénombre. C'est binaire : soit complètement éclairé, soit complètement à l'ombre,
ce qui donne des ombres avec des contours saillants.

Pour ce faire, encore une fois on rend la scène selon le point de vue de la lumière.

En utilisant le back face culling, comme dans la plupart des rendus. En gros, on oublie les faces qui sont tournées vers le fond. J'espère ne pas aller trop loin, mais les polygones ont une face visible et une face invisible. C'est en rapport direct avec le produit vectoriel. Un coté visible, un coté invisible. Les faces sont "polarisées".
C'est géré, c'est cablé, par le GPU, qui calcule la composante de la profondeur, z, du produit vectoriel, seulement de la normale mathématique de la face.
Si le z est négatif, la face est invisible.

Le résultat est un chapeau, la face visible de l'objet selon ce point de vue.
Ensuite on génère de la géométrie, un volume.. On crée un volume qui part de ce chapeau vers l'infini selon la direction de la lumière.
De manière simple, si on est dans le volume on est dans l'ombre, sinon on est éclairé.
.
Ensuite on comptabilise les impacts de la lumière sur ce volume grâce au stencil buffer.
Le stencil buffer est une texture d'entiers petits (qui a la résolution de l'écran). (positifs et négatifs, 8 bits sont largement suffisants)
En fonction du décompte dans le stencil buffer, on sait si le polygone pixel est à l'ombre ou non. Car le volume est exploité au pixel près.
Le stencil buffer est consulté dans le pixel shader pour savoir si le pixel est éclairé ou dans l'ombre.
Et il y a la difficulté de savoir si la scène est dans le champ de la lumière ou non. Car dans ce cas, c'est inversé. (décompte pair ou impair)

[EDIT]
Pour illustrer, si on est hors du champs de la lumière, si le décompte est pair, cela veut dire que la lumière est entrée puis sortie du volume d'ombre, donc le pixel est éclairé.
S'il n'y a aucun impact, c'est pareil : pixel éclairé. (Il n'est ni entré ni sorti du volume d'ombre).
Par contre si le décompte est impair, cela veut dire que la lumière est entrée mais jamais sortie. Donc le pixel est dans l'ombre.
En soit c'est plutôt intuitif.
2 Choses encore :
Si la scène est prise en étant dans le volume d'éclairage, il faut inverser la logique : Décompte impair donne éclairé, et pair donne dans l'ombre.
Et cet algorithme suppose que les volumes soient convexes.
Ce n'est pas un si gros problème car on a besoin que les volumes soient convexes déjà pour que le back face culling fonctionne correctement.
Les objets doivent selon tout point de vue avoir au moins une face avant, car sinon il pourrait y avoir des trous lors de l'affichage.
(Dans Assassins 'Creed le premier, ils n'ont pas respecté cette règle, et la capuche du héros est invisible selon certains points de vue. Quand on le regarde de profil, la partie de sa capuche du fond n'est pas affichée). C'est une honte quand on sait combien de designers ont bossé sur le personnage et combien de temps ils y ont passé, et combien ils en étaient payés ... ) Les logiciels de modélisation 3D permettent de créer des doubles faces pourtant, toujours affichées quelque soit le point de vue. 2 faces au lieu d'une seule, l'une vers l'avant, l'autre vers l'arrière (le fond)...
[\EDIT]


Mais voilà, la faiblesse de cet algorithme, génial au demeurant, c'est qu'il ne fonctionne qu'avec des objets opaques contre des objets opaques. Et sans pénombre.
Impotent si vous voulez générer des ombres avec des objets comme une feuille d'arbre, avec des contours qui sont fait grâce à l'opacité zéro.

Cet algorithme est abandonné.

[Bubu]

Pour changer du domaine graphique, je vais parler de physique dans les jeux.
La physique est responsable de l'évolution et des interactions des objets physiques.
Cela peut être simplement un objet qui tombe, ou des objets qui se cognent. (Collisions).

Dans une scène d'un jeu, il y a en réalité 2 scènes : la scène graphique, celle que l'on affiche, et la scène physique, qui permet l'interaction physique entre objets.
Les 2 scènes fonctionnent avec des données complètement différentes, mais servent pour gérer la scène complète, unique, du jeu.

Bien qu'ayant utilisé 2 algorithmes différents de détection de collisions, j'ai utilisé un moteur physique : PhysX de NVidia.
Car je n'ai étudié que la physique du point, et non du solide. C'est bien joli de détecter une collision, mais je ne savais pas comment calculer les mouvements après.

Comment détecter les collisions ? Déjà il faut définir les volumes sous forme de volumes convexes. Si on a un volume non convexe (concave), il faut le diviser en plusieurs volumes convexes.
Après les moteurs physiques sont sympas : il suffit de définir les volumes convexes sous forme d'une liste de points 3D. Et il calcule les métadonnées tout seul, de manière transparente.

L'autre objet physique principal : ce sont les terrains. C'est une grille en 2D (uniforme) , qui contient la hauteur. Pour faire rouler une voiture dessus, ou faire marcher un personnage dessus.

Il y a d'autres objets primitifs qui sont gérés également : les sphères, les boites (parallélépipèdes), les capsules (comme une gélule), les cylindres et j'en oublie certainement. Leur point commun ? Ils sont tous convexes.

On peut également définir des contraintes, des pivots, des joints, appelez ça comme vous voulez, qui relient les objets entre eux.
Pour un personnage vivant contrôlé par le joueur ou une AI, on le définit par une capsule. Dès qu'il meurt, on le remplace par une ragdoll (littéralement, une poupée de chiffon) soumise à la pesanteur et aux forces imposées. C'est un ensemble complexe de volumes et de joints entre eux, chacun avec ses axes de liberté. Par exemple, un coude ne peut se plier que dans un seul axe, et pas vers l'arrière.

La détection de collisions entre volumes convexes est très robuste, par contre pour les terrains elle l'est beaucoup moins. On peut se retrouver avec un personnage qui passe à travers le terrain, ou une voiture qui se retrouve avec une roue ou plusieurs sous le terrain. (MEGA BUG).

Il y a des techniques qui préviennent de passer sous le terrain, mais elles sont approximatives.

La base, c'est de simuler un taux de rafraichissement de la scène physique fixe, quelque soit le taux aléatoire de rafraichissement de la scène graphique.
Plus il est petit et plus la physique fonctionne bien. Parfois on fait plusieurs simulations physiques pour un seul rendu graphique.

Et il faut bien paramétrer le moteur physique. (Qui n'a jamais vu un objet cogné trembler à l'infini une fois tombé dans un jeu?)

Pour résoudre les multiples collisions entre objets, les moteurs physiques utilisent un solveur de contraintes.
En gros, ces systèmes prennent en compte toutes les collisions et cherchent à les résoudre simultanément entre elles. C'est approximatif. (Plus il y a de passes, plus la solution est stable, mais plus il y a de passes, plus c'est couteux).

Pour finir, vous avez forcément expérimenté les "collisions fantômes", c'est simplement un défaut de conception des niveaux, où la scène graphique et la scène physique ne collent pas !

Et je vais me contredire par rapport au fait que les GPUs ne servent qu'au rendu graphique dans les jeux : le moteur physique PhysX peut être accéléré par le matériel GPU, en option.
Mais je doute que cela soit utilisé dans les faits (pratiques, dans les jeux), à part pour les démos. Ou pour la recherche. Comme je l'ai déjà dit, il y a des GPUs sans port vidéo, uniquement dédiés au CUDA (GPGPU).



[EDIT] Je complète ma liste de ce que gèrent les moteurs physiques :
D'abord la détection continue de collisions. Qu'est ce que c'est ?
Au lieu de raisonner sur les états des objets (position et orientation) :
(L'orientation est sous forme d'un quaternion (extension des nombres complexes mais avec 3 composantes imaginaires pures (i,j,k). Les quaternions sont très puissants pour encoder l'orientation d'un objet 3D car on peut faire des interpolations, et en plus il n'a besoin que de 4 flottants pour être encodé au lieu de 16 pour une matrice de rotations équivalente. Mais vu que les GPUs n'utilisent que les matrices pour les transformations, il faut convertir le quaternion en matrice à la fin.)
Dans la détection continue de collisions on raisonne sur les transitions entre états.
On calcule le volume que parcourt l'objet entre les états.
Par exemple, quand on tire une balle d'une arme, si on modélise la balle comme un objet très rapide, on est quasiment sûr qu'elle va passer au travers de la cible sans détection de collision (discrète).
A une étape, la balle est devant la cible, à la suivante, elle est derrière. Raté !
Ce qui n'arriverait pas si on utilisait la détection continue de collisions : le volume entre les 2 étapes transpercerait la cible, donc la collision serait détectée.
(Dans les faits, on utilise un lancé de rayon dans ce cas)
Pareillement, dans un jeu de course, il vaut mieux l'utiliser sur un terrain (ce n'est pas un volume, mais une surface (qui n'a pas de dedans/dehors))
J'ai un peu perdu le fil depuis quelques années, mais cela ne m'étonnerait pas que ce soit utilisé dans les jeux récents de course de voitures.
Le problème c'est que c'est extrêmement couteux.
Bien que fiable à 100%, son coût énorme fait qu'on l'évite comme la peste. Cependant, dans un jeu où on a peu d'objets physiques c'est sans doute jouable à notre époque. A vérifier.

La gestion des tissus (déchirables), et des corps mous (soft body). Cela ne vous a pas échappé dans Assassin's Creed pour les vêtements des personnages.

Les fluides. Modélisés comme des ensembles de particules (toutes petites sphères sans orientation qui interagissent entre-elles) au niveau physique. Je ne m'y suis jamais intéressé, la vraie difficulté doit être dans les shaders pour les représenter comme une surface et un liquide. Il faut cependant utiliser un certain niveau de précision si on ne veut pas un liquide à l'apparence granuleuse. Très couteux aussi.
L'objet réel le plus proche de la simulation actuelle des fluides est le sable. D'ailleurs, d'un point de vue macroscopique, peut-on considérer le sable comme un fluide, comme dans les sabliers ?

Je crois que là c'est plus exhaustif.

[Tugdual]

Une bien jolie démo :

• La Comté du Seigneur des Anneaux modélisée sous Unreal Engine 4...

[Bubu]

Pour les scènes en milieux fermés, en intérieur. On utilise des secteurs et des portails.
L'idée est de subdiviser les niveau en secteurs, reliés entre eux par des portails.
Les portails sont des ouvertures, visibles selon le secteur où l'on est.
Par exemple, vous êtes dans un bâtiment, et via une fenêtre, vous voyez l'extérieur.
Eh bien on ne rend la scène que pour ce quadrilatère.
Sans cette technique, on rendrait en entier la scène extérieure, pour la couvrir ensuite des murs du bâtiment à part la fenêtre. Rendre une scène pour ensuite la couvrir de murs, c'est une grosse perte.
On ne rend que la scène selon ce qui est vu du portail, et non de toute la scène.

Après c'est récursif, un portail peut rendre visible un autre portail.

La contrainte est surtout pour les concepteurs de niveaux, qui doivent utiliser des portails qui relient les secteurs entre eux (de manière artificielle en fait).
Parfois les niveaux doivent aussi être construits en fonction de cette technique.
Pour le programmeur : les portails sont des rectangles. Qui font le lien entre un secteur et un autre.
Il y a l'aspect géométrique : savoir si le rectangle est visible selon le point de vue. Le champ de vue est représenté par une pyramide couchée tronquée à son sommet. Le view frustum. La face qui tronque la pyramide est l'écran, et la plus profonde est la limite en profondeur de la scène.
Le portail est représenté par un rectangle positionné en 3D.
Pour savoir si le portail est visible selon le point de vue, il faut donc détecter l'intersection entre un view frustum et un rectangle en 3D.
Une fois qu'on sait si le rectangle, le portail est visible, on fait un rendu de la scène visible derrière le portail dans une texture. Ensuite on place cette texture correctement dans la scène principale.

[Bubu]

Pour calculer les 8 points du volume (convexe) du view frustum, le volume visible de la scène, la solution la plus simple est de transformer le cube unitaire obtenu après la projection, par la matrice inverse de la projection. Le cube devient une pyramide tronquée horizontale qui part de l'écran et qui va jusqu'à la profondeur maximale. On calcule ensuite les normales de ses faces via produits vectoriels.
C'est une technique générique. J'en parle avec insistance, car souvent les programmeurs se prennent la tête pour calculer ce volume, alors que c'est très simple avec cette technique. C'est utilisé pour savoir aussi si un objet est dans le champ de vue ou non. (View frustum culling) Utile pour générer des ombres, ou la scène principale, pour savoir si on doit ou non tracer un objet. Après il faut accélerer la detection, en utilisant des arbres de partitionnement hiérarchique de l'espace. Les octrees, ou les kd-trees, quoique certains disent que pour les objets dynamiques il vaut mieux savoir s'ils sont visibles directement, individuellement.
Sous directX, la scène après projection est très simple : [-1, +1] en x, [-1, +1 ] en y, et [0, 1] en z. Cela fait 8 points (c'est un cube). Unitaire, c'est un consensus même si le terme n'est pas vraiment juste.
Ensuite on transforme ces 8 points par la matrice inverse de projection. Et on obtient les cordonnées du champ de vue selon le point de vue de la caméra avant projection.
Evidemment, on ne détecte pas la propre géométrie des objets pour savoir s'ils sont visibles (dans le view frustum), on utilise des volumes englobants rapides à calculer. C'est approximatif.
Bien programmé, on n'aura pas d'objets non affichés qui sont pourtant dans le champ de vue, mais on peut gérer des objets à tort qui ne sont pas visibles. C'est rare.
Les deux volumes englobants sont les bounding spheres (sphères englobantes), et les bounding boxes (boîtes englobantes).
Ils sont tous les deux puissants en fonction de la forme de l'objet qu'ils englobent. Un bon moteur gère les deux.
Une sphère englobante sera plus adaptée pour un ballon, une boîte englobante serait plus adaptée pour un immeuble rectangulaire.

Ce n'est pas un tuto, j'essaie de simplifier pour surtout donner les idées.
Pour ceux qui sont à l'aise avec mon propos :
Pour le view frustum culling, qui permet de ne pas gérer graphiquement les objets non visibles du point de vue de la caméra (ou du point de vue de la lumière pour les ombres), le view frustum est exprimé dans le repère du monde. Donc on multiplie la matrice de la caméra (view matrix) par la matrice de projection. Et on transforme le "cube unitaire" par l'inverse de la matrice obtenue, pour obtenir les 8 points du volume visible dans le repère du monde.
La chaîne de transformations des objets 3D sont : d'abord on place l'objet qui est dans son repère local dans le repère du monde, puis ensuite selon le repère de la caméra, pour finir dans le repère projectif via coordonnées homogènes, qui permet d'afficher la scène avec perspective.
Pourquoi le volume du point de vue (le view frustum) est exprimé dans le repère du monde ? Parce que les volumes englobants des objets sont dans ce même repère du monde.
Comme cela, les volumes englobants ne sont à calculer qu'une seule fois lors de l'initialisation du niveau, et on calcule la position du viewing frustum à chaque image (car il change dès qu'il change de position ou d'orientation à chaque image). Parfois, les volumes englobants des objets sont précalculés et font partie des donnés du niveau.
Car il vaut mieux calculer le view frustum pour chaque image dans le repère du monde, que de transformer les volumes englobants de tous les objets à chaque image pour les placer dans le repère de la caméra.

[EDIT]
Cela est valable pour les objets statiques (bâtiments, terrains entre autres), mais plus difficile pour les objets dynamiques.

Pour mon cas, et je suis loin d'être sûr que ce soit le meilleur, loin de là, je précalculais les volumes englobants dans un logiciel intermédiaire qui permettait de préciser les matériaux graphiques et physiques de l'objet, dans son repère local. Tout cela stocké dans un seul fichier. Pour les objets animés (personnage qui marche par exemple), je calculais le volume englobant en faisant défiler tous ses mouvements selon un pas très fin, et de chaque animation, pour calculer le volume englobant final. Il fallait ensuite transformer le volume en temps réel pour chaque image pour le placer dans la scène (via des arbres de partitionnement, une chose que certains déconseillent. Selon eux, ils faut les gérer directement car ils sont peu nombreux et que c'est couteux de les placer dedans à chaque frame). Pour les sphères englobantes, ce n'est pas un problème, mais pour les boîtes alignées, cela détériorait de beaucoup la précision du volume, beaucoup plus grand après le placement dans le niveau, car les boites englobantes devenaient orientées selon d'autres axes et donc il fallait calculer la boite englobante dans le repère du monde selon la boite englobante dans le repère local). Et j'aurais dû demander quand génère-t-on les volumes englobants pour les objets dynamiques, qui se déplacent et se déforment.
Faut-il générer les volumes englobants des objets animés pour chaque frame ?
Etc...

[Bubu]

Comment précalcule-t-on les volumes englobants ?
Que ce soit après le chargement du niveau, ou avant précalculés ?

1) Les sphères englobantes :
Le centre de la sphère est simplement le point moyen de tous les points de l'objets.
On fait la moyenne de tous les points de l'objet.
Pour calculer le rayon de la sphère, dans un second temps, on détermine le maximum de distance entre le centre et chaque point de l'objet.
(On raisonne sur les maxima des carrés des distances. (Pythagore) . Une fois l'énumération et les comparaisons faites, on ne calcule que la racine carré du maximum obtenu donc une seule fois, car la racine carré est couteuse).
Le résultat est un centre et un rayon.

2) Les boîtes englobantes :
Déjà il faut préciser qu'elles sont alignées sur les axes.
Certaines ne le sont pas. Mais ignorées car très couteuses.
L'acronyme est AABB. (Axis Aligned Bounding Boxes). Boites englobantes alignées sur les axes.
C'est aussi très basique.
On a 3 axes x, y et z.
On énumère les points de l'objet et on stocke le minimum et le maximum de chaque composante des points de l'objet.
Le résultat est 2 points, un point minimum (qui contient toutes les coordonnées x, y, z minimales) et un point max (qui contient toutes les coordonnées x, y, z maximales).

Ensuite, il y a des algorithmes qui permettent de savoir si une sphère ou une AABB est ou non dans le view frustum, champ de vue, même en partie.
Qui sont très puissants et simples à calculer, même si les algorithmes ne le sont pas immédiatement (celui pour les sphères est intuitif, par contre j'ai dû me renseigner pour celui des AABB.)


[EDIT:] Il y a aussi la possibilité de savoir lequel des volumes englobants est le mieux adapté.
Pour un objet donné, on précalcule la sphère englobante et la boîte englobante.
On compare ensuite le volume de chaque (selon le calcul classique pour calculer le volume d'une sphère étant donné son rayon, et le produit des distances des 3 axes pour la boîte alignée sur les axes) et on choisi le volume englobant le plus petit en terme de volume. Le choix du type de volume englobant est donc automatisable.
Mais, même si c'est pas compliqué et surtout si c'est précalculé, c'est jouable, mais je ne l'ai jamais implémenté.
(J'ai fait du tout l'un ou tout l'autre. Au début des sphères partout, puis ensuite des boîtes partout car statistiquement les boîtes sont plus précises)

[Bubu]

La géométrie 3D est complexe, même si elle utilise des notions, à part les matrices apprises dès la première année de cursus scientifique, bien comprises dès la Terminale Scientifique.
Je dirais qu' entre la géométrie 2D, et la géométrie 3D, la difficulté est exponentielle.

Et la géométrie 3D, c'est le quotidien des développeurs de jeux 3D.

Savoir quel objet est visible, comment animer un personnage, gérer les collisions, etc ... C'est franchement difficile.

[EDIT, pour ne pas polluer le forum], le créateur du moteur de Duke Nukem 3D était un lycéen (96)... et oui.
Ce moteur 3D ne rendait que des pièces 2D, des secteurs, reliées entre elles par des portails. C'est pourquoi certains disent que c'était un moteur 2.5 D.
Le résultat était quand même des images 3D.
Son moteur était beaucoup plus puissant que le moteur de John Carmack qui ne permettait pas d'avoir des secteurs superposés en hauteur, alors que le moteur de ce lycéen le permettait.

Pendant l'été entre les vacances du lycéen et son entrée en fac, les développeurs de Duke Nukem l'ont convoqué car ils peinaient à utiliser son moteur. Il a traversé les USA pour les aider.
Un lycéen qui aide des ingénieurs et des concepteurs de niveaux .....
Mais le résultat est obtenu, et Duke Nukem 3D, a été un succès mondial.

[Bubu]

Je voudrais mettre mon grain de sel sur les personnages animés, qui se déforment.
On les appellent les skin-meshes.
Je ne parle pas des personnages qui se déplacent, mais de la déformation de leur géométrie, sans changer de position.
Imaginez des personnages qui marchent sans se déplacer. (Le déplacement des personnages, c'est autre chose).
(Skin-meshes : ce sont des objets dont la peau s'étire et se contracte).
Cela passe par des "os", et des contributions entre les "os".
Tout est calculé par les logiciels, qui calculent tout.
Nous, développeurs, les utilisions aveuglément.

Pour la surface, la peau, on interpole les différentes positions des points en fonction des os qui codent la contribution des influences des os autours.
Et cela se calcule dans le vertex shader.

Evidemment la solution la plus efficace est d'utiliser un moteur déjà fait, comme Unity, Unreal ou Irrlicht.
Mais si le plaisir pour vous est d'en programmer un (il ne faut pas se leurrer, il ne sera pas aussi puissant que ceux nommés), pour charger les assets, les meshes, les objets quoi, il y a une magnifique bibliothèque valable en C++ ( et en Java je crois), qui prend en compte tous les formats populaires, et fournit un résultat unifié quelque soit le format fichier de l'objet 3D initial.
C'est la bibliothèque Open Source Assimp. Et elle calcule les métadonnées essentielles. Comme le repère TBN (tangente, binormale, normale) de chaque point pour le normal mapping, elle peut aussi triangulariser des quads (faces de quatre points transformées en 2 triangles), et elle fournit les résultats parfaitement, immédiatement exploitables.

[Bubu]

Je crois que j'aurai ensuite fait le tour, je vais parler du son dans une scène 3D.
DirectX, qui est constituée d'un ensemble d'APIs pour chaque domaine de la réalité virtuelle, y compris une bibliothèque mathématique, et a une bibliothèque pour gérer "les sons 3D".
On se demande ce que cela veut dire car nous n'avons en général que la stéréo (gauche/droite).
Alors c'est quoi ? En fait on place les émetteurs de sons (haut-parleurs), et le récepteur (micro) dans une scène 3D. Les émetteurs sont définis sous forme de cônes à une position 3D donnée, et le micro (à la même position et orientation 3D que la caméra). Après la bibliothèque se charge de convertir ces données en signal stéréo, 2 résultats gauche/droite.
Après on peut les déplacer pour chaque frame graphique 3D.
Et en prenant en compte la vitesse et l'accélération des émetteurs et du recepteur, on peut gérer l'effet Doppler acoustique. Important par exemple pour un jeu de course de véhicule...
(Le fameux effet qui fait que la fréquence du signal émetteur baisse quand on double un objet se déplaçant moins vite, ou l'inverse).
Pour cela la bibliothèque DirectX dédiée est très bien faite. Par contre, cette bibliothèque ne permet pas de charger un fichier son : il faut lui donner les données binaires du son (WAV).
Donc il faut une autre librairie extérieure pour cela, c'est la seule chose qui fait que l'on ne peut pas considérer cette librairie DirectX comme un moteur son.
L'autre raison pour laquelle on ne peut pas la considérer comme un moteur de sons 3D, c'est qu'elle ne gère pas la lecture des flux audios.
Quand on joue un son sur un thread, cela le bloque.
(Imaginez une appli où on a soit une animation, soit un jeu d'un son qui bloque tout le reste)
Donc il faut soi-même faire un gestionnaire de jeu de sons parallèle, en utilisant un autre thread.
Donc on joue les sons sur un autre thread, en parallèle, pour ne pas bloquer le processus principal.

[Bubu]

Un dernier sujet qui me met hors de moi, c'est quand les promoteurs des consoles quelles qu'elles soient, disent que leur console sont aptes à gérer le ray-tracing en temps réel (lancer de rayon).
C'est un mensonge. Edifiant.

Pourtant le ray-tracing existe bel et bien. C'est utilisé depuis longtemps pour la génération d'image de synthèses dans les films depuis longtemps(Terminator 2, Toy Story, Jurassic Park,...) Donc on voit que ce n'est pas nouveau. Ou même dans la série Gotham, où l'on voit des survolés de la ville. Evidemment, les concepteurs de la série ne se sont pas atteler à créer une ville en décors physiques. C'est valable aussi pour la série The Walking Dead, où la moitié des zombies dans les hordes et les décors sont totalement synthétiques.

Peut-être que dans des rendus hybrides (rasterisation / lancer de rayon), arriveront ils à utiliser le lancer de rayon par ci par là, mais globalement c'est une chimère.

Le lancer de rayon est une technique extrêmement lourde, même infiniment lourde, et même les dernières consoles sont incapables de gérer cette technologie en temps réel.

Peut être dans 20 ans verrons-nous des images photoréalistes générées grâce au ray tracing, et on aura la qualité de rendu égale à celle des films. On ne distinguera pas la différence entre ce rendu photoréaliste et la réalité. Mais c'est franchement pas pour demain. Mais dans un futur proche !


EDIT : Pour Toy Story (le premier), il fallait de plusieurs heures voire de journées pour générer une seule image sur leurs baies de serveurs dédiés. D'accord la technologie a beaucoup évolué, mais on n'est pas dans Alice au Pays des Merveilles, même aujourd'hui se serait impossible de générer ces images en temps réel, à moins d'avoir un super calculateur chez soi, ce qui n'est le cas de personne...


[EDIT2] Les paradigmes entre les images 3D pour les jeux ou pour les films, sont opposés.
Pour un film, la priorité est le photoréalisme. Peut importe le temps qu'il faudra pour calculer l'image.
Pour les jeux, c'est que le rendu soit obtenable en temps réel, même s'il n'est pas vraiment photoréaliste.

Pour le rendu des films, on n'utilise aucun raccourci, peu importe qu'il faille plusieurs jours de calcul pour générer l'image. L'essentiel, c'est qu'on ne se rende pas compte que se soit une image de synthèse.
Pour le rendu des jeux, c'est l'inverse. On tolère que l'image générée ne soit pas photoréaliste, car le but est de la générer en quelques dizaines de millisecondes au plus.

L'écart se rétrécie au fur et à mesure que la technologie progresse, mais on est très loin du 100% lancer de rayons dans les jeux.

Entre les deux techniques de rendu totalement opposées, lancer de rayon ou rastérisation, la plus compliquée est la rastérisation.
Le lancer de rayon (films), on bourrine sans vraiment prendre en compte le temps qu'il faudra pour calculer l'image. Si c'est trop lent, on rajoute des serveurs de calcul.
Pour la rastérisation(jeux), l'optimisation et l'approximation sont de rigueur. Toujours pareil, pour que l'image soit générée en 20 ms maximum en gros par le GPU.

[Bubu]

Les premières consoles du milieu des années 80 étaient programmées en assembleur. Quels que soient leurs processeurs.
La NES, le GameBoy (plus puissant malgré son affichage 2 bits), et ses équivalents de SEGA master system I et II, la megadrive, la super nintendo et la nintendo 64 (qui avait un GPU, en plus).
Elles avaient des architectures complexes. Notamment un processeur principal et un processeur audio. (Et un processeur graphique pour la N64, mais encore codé en assembleur)
Apparemment programmer pour la nintendo 64 était une horreur, du fait de son architecture très (trop) complexe. Mais cela n'a pas pour autant empêcher d'avoir des jeux formidables. (Mario 64 notamment)
Les consoles plus modernes passaient par le C, et maintenant le C++, en plus d'un langage de shaders pour GPU, pour les graphismes.

Après ce n'est pas anachronique, vu que John Carmack a codé ses shaders pour Doom3 en assembleur GPU, plus de 10 ans après...)

Pourquoi ? Car les GPUs sont très puissants, et il n'y a pas beaucoup de niveaux d'abstraction entre un shader codé en assembleur GPU ou un langage C-like.
Les GPU manipulent directement des vecteurs de 4 flottants, manipulent directement les matrices 4x4. Ils gérent aussi les produits scalaires, les produits vectoriels, la normalisation d'un vecteur... etc, etc ...
Utiliser GLSL ou HLSL pour programmer un shader, c'est juste que c'est plus simple à organiser.


Je préfère le GLSL au HLSL:
Les deux s'inspirent du C ce qui simplifie leur compréhension.
Dans le HLSL, on associe dans le même fichier le Vertex shader et le Pixel shader. (DirectX)
Alors que dans le GLSL (OpenGl), les deux shaders (Vertex shader et Fragment (soit Pixel) shader)sont dans des fichiers différents.
C'est beaucoup plus souple.
Le GLSL permet de mélanger les Vertex shaders et les Pixel shaders entre eux.
On a juste à s'assurer que le lien entre chaque type de shader correspond.

[Tedrainbow]

Zogal

En résumé, vague.

Les huit petit héro koala dans le jeu, de prévus.

Quatre garçon puis quatre filles dans le même village, donc probablement que ces un village remplis de petit koalas comme une petit population seul sur une île, loin des conflits du reste du monde.


je pense faire entre 72 populations de plus au maximum si j'ai asse d'idée pour les faire original et varié en taille de format même si sa reste un petit village quand même.

Maxum le style père noël, Dorla une magicienne avec le chapeau violet, Bodik avec une belle tache rouge sur le front avec un costume blanc, Holoj une jolie africaine avec sa peau plus brun que les autres, Fejos du style punk avec ces cheveux orange, Mirli comme créatrice ou dessinatrice comme centre d'intérêt spécialement, Renox plus exotique pour ces jolie fleur sur les oreille puis Fejod un petit japonais comme étranger en dernier.

Mais bien sûr, juste la moitié en combat en tant réel puis il se peut souvent que dans l'histoire le groupe, se dissipe entre, filles puis les garçons, ou une chicane, alors dans ces conditions deux personnages seront indisponible pour un moment, ou vous contrôler certain combat, seul ou en groupe de deux, trois puis quatre, au choix oui, ou non.

Le but du jeu, est pas en théorie vaincre un monstre puissant pour sauver la planète mais de pouvoir régler un de vos plus grand peur pour chacun de chaque personnages, durant le jeu.

Possible que un autre groupe de koala plus sombre, soi aux rendez-vous inverse de vos personnage que vous contrôler pour un petit plaisir de plus, des rivales pour chacun, du même village.



Exemple des différents groupes.

-Free-lance-
-Guerrier-
-Moine-
-Mage blanc-
-Mage noir-
-Voleur-

15 combinaison.

-Mage Rouge- (Mage Blanc + Mage Noir) Lv25
-Mage Bleu-(Mage Blanc + Moine) Lv25
-Mage Vert-(Moine + Free-lance) Lv25
-Rôdeur- (Voleur + Moine) Lv25
-Chevalier-(Mage Blanc + Guerrier) Lv25
-Érudit-(Mage Noir + Moine) Lv25
-Géomancien- (Free-lance + Voleur) Lv25
-Dragon- (Guerrier + Free-lance) Lv25
-Viking-(Guerrier + Moine) Lv25
-Chevalier Noir- (Mage Noir + Guerrier) Lv25
-Barde-(Free-lance + Mage Blanc) Lv25
-Evoker- (Mage Noir + Voleur) Lv25

66 combinaison.

-Ceinture Noire-(Chevalier + Viking) Lv50
-Dévot-(Géomancien + Rôdeur) Lv50
-Mage temporel-(Mage Bleu + Mage Vert) Lv50
-Invocateur-(Érudit + Evoker) Lv50
-Ninja- (Chevalier Noir + Dragon) Lv50
-Sage-(Barde + Mage Rouge) Lv50

15 combinaison.

-Gardian-(Ninja + Ceinture Noire) Lv75
-Élémentaliste-(Dévot + Invocateur) Lv75
-Prophète-(Sage + Mage temporel) Lv75
-Vampire-(Dévot + Ceinture Noire) Lv75
-Enchanteur-(Sage + Invocateur) Lv75
-Maître-(Ninja + Mage temporel) Lv75

15 combinaison.

Sa peut paraitre eu peu complexe a première vus mais au moins sa permet part la suite d'avoir un style de trois métier en même temp avec juste deux onglet comme les jeu habituels.

En fait, c'est la base de donné chiffré des valeur de stats, qui est vas être eu peu long pour les secondaire de 111, quand les trente premier seront enfin finie.
Chaque fichier ressemble eu peux comme cela, params classe (Numéro de la classe)

Chaque niveaux, du bonus, VIE MAX+, PM MAX+, FORCE+, DÉFENSE+, MAGIE+, ESPRIT+, VITESSE+, CHANCE+

Sa permet d'avoir, des stats de trois métier en même temps pour les valeur finals puis pas mal de combinaison.

Aussi cela veut dire que les attaques et magies, avec effet passive sont lier aux trois classe en même temps mais pas l'équipement, juste c'elle du métier principal, pour n'e pas avoir trop de liberté.
Cape, Amulette, Botte, Armes, Bouclier, Chapeau,
Veste, Anneau, Livre X3, Insigne X3, Effet Protection X10, Plus un double en fonction du héro koala sur les huit premier écrit plus haut.

Les équipement qui sont modifiable uniquement part nos soin.

Bonus PV max, Bonus PM max, Bonus Force, Bonus Défense,
Bonus Magie, Bonus Esprit, Bonus Vitesse, Bonus Chance,

Des bonus qui change avec des point durant le jeu de niveau rien ou le niveau 40 maximum, mais ont doit choisir quel équipement sera augmenter, tout est pas possible, ils faut faire un choix.
Bonus Feu, Bonus Glace, Bonus Foudre, Bonus Terre, Bonus Vent, Bonus Eau, Bonus Lumière, Bonus Ombres, Bonus Physique, Bonus None, Bonus Esprit, Bonus Coeur.

En fonction du personnage, six élément du haut est dans la liste d'équipement, qui permet automatiquement de modifier divers stats de base en fonction du niveau de l'élément actuel, zéro aux début puis le maximum est 200 Lv part éléments, se qui veut dire que chaque vingt LV augmente de +1 le bonus de l'élément.
courbe PV, courbe PM, courbe Force, courbe Défense,
courbe Magie, courbe Esprit, courbe Vitesse, courbe Chance,

Des bonus qui change avec des point permanant durant le jeu mais ont doit choisir quel équipement sera augmenter, tout est pas possible, ils faut faire un choix sur une valeur de un et 7 max.

Formule Puissance, Formule Concentrer, Formule Esquive,
Formule Mieux, Formule Âme, Formule Destin,
Formule Taille, Formule Tour, Formule Feu,
Formule Eau, Formule Glace, Formule Terre,
Formule Vent, Formule Foudre, Formule Lumière,
Formule Ombre, Formule Physique, Formule Nul,
Formule Esprit, Formule Cœur, Formule Sorts,
Formule Annuler, Formule L'esprit, Formule Corps,
Formule Nv,

Certaine formule peut être augmenter en équipement pour meilleur spécialisation.
Émotion A, Émotion B, Émotion C,

Puis pour les émotions il y a 24 émotions ADN, A-B-C
Qui augmente aussi divers stats important mais dans l'histoire seulement.

75 équipements.

Juste de précisé que l'intelligence des actions des monstre sont les suivants;
Aux début le nombre d'action (8) monstres normal et (16) patron plus dur mais seulement la moitié est tout identique en fonction de la variance du même ennemie que ont voit surnôtre écran,part la suite (12)--(24),
dans la moyen (16)(32), plus variés (20)(40), plus joli encore (24)(48), puis finalement comme cela.(28)--(56), donc, il est possible de savoir d'avance quel genre de monstre vous est en train de combattre en sachant si l'ennemie fait un sort qui est dans la deuxième moitié, différent de ces version mais cela veut aussi dire ces attribut n'est pas tout pareille, justement, se qui donne une vrais impression, que le monstre ou les ennemie identique son asse intelligent pour un jeu 2D.

Exemple de comment je les gère dans le jeu.


1,--Normal(4==12) 8/16 Boss(1==4) le Premier donjon, 4 monstres possible et un monstre plus puissant.
2,--Normal(15==60) 12/24 Boss(3==15) trois donjon 5 monstres possible et 3 monstre plus puissant.
3-- Normal(30==150) 16/32 Boss(5==30) 5 donjon 6 monstres possible et 4 monstre plus puissant.
4-- Normal(49==294) 20/40 Boss(7==49) 7 donjon 7 monstres possible et 7 monstre plus puissant.
5-- Normal(72==504) 24/48 Boss(9==72) 9 donjon 8 monstres possible et 9 monstre plus puissant.
6-- Normal(99==792) 28/56 Boss(11==99) 11 donjon 9 monstres possible et 11 monstre plus puissant.

Puis pour le mettre en place, dans l'onglet formation, je dois juste mettre tout les combinaisons de monstres que l'écran peu te donnée avec le hasard des variances avec quel que condition pour que de chaque combat, quand vous est au début des combats, le hasard léger vient de choisir aux hasard les ennemies à l'écran et le type de IA de chaque ennemie qui est pour l'heure de l'affrontement.

Pour se qui est de se préparé, ces asse simple en faite, chaque personnage peut, aux fur et mesure avoir une liste, de 41 compétences varié et quatre degrés de puissante de base pour chaque personnage même si en fait, six compétence sont au début du jeu, puis part la suite vous avez deux choix possible quand les niveaux de deux éléments monte du même nombres puis aussi d'autre compétence avec trois éléments de base.

Se qui fait que vous avez le choix, de base 24 compétence peux importe la partie pour celle de base et les quatre degré des six magie, puis part la suite il faut vous faire un choix contre deux type d'action qui s'égale mais différents, donc 15 pour les avancé et un total de 60 pour celle si, puis finalement les dernières de chaque personnages, qui de 20 styles avec encore de deux choix pour choisir le style que tu veux mais il est possible part exemple d'avoir aux final divers magie mais avec des degré différent de puissance, sur une cible ou sur tout les cibles, en fait il y a deux pour chacun, sur les quatre options possible.

Ont peut quand même, avoir d'autre compétence plus varié qui vas avec trois métier en même temps donc une dizaine de compétences si le niveaux est haut pour chaque classe et qui peut changez a tout moment.

Il y aussi une possibilité d'avoir des matéria comme dans final fantasy 7, pour changez vos compétence en combat plus facilement et qui permet d'avoir passivement des compétence qui normalement est disponible que avec un personnage spécifique mais part contre il faut les apprendre sur le long terme, pas aussi vite que changez automatiquement ou de manière naturel.

l'idée pour les magies, vient du type de jeu, Quest 64 mais en 2D aux lieux, pour le type de comment les magies fonctionne, 12 élément de base mais chaque personnage peu avoir une liste de maximum de six type, se qui fait que il y a six magie de base, ensuite une combinaison de deux ensemble te donne 15 puis part trois une vingtaine.
Se qui est un total de, 164 magie dans deux liste séparé.

Les 12 éléments sont les suivants.
Nv Feu-
Nv Eau-
Nv Glace-
Nv Éclair-
Nv Terre-
Nv Vent-
Nv Lumière-
Nv Ombre-
Nv Nul-
Nv Physique-
Nv Esprit-
Nv Coeur-

Part contre pour les magie des personnages ou des monstres, chaque sort fait aux moins trois effet différents minimum puis quatre fonctions avec les avancer mais plus forte en expert, cinq actions aux final.

Part exemple, un sort de base d'eau, peut guérir le lanceur avec une quantité de vie puis ensuite se faire un bouclier de protection sur lui même avant de lancé son jet d'eau pour son attaque sur l'ennemie, se n'est que un exemple.

Bien sûr, quand ont change de classe, forcément ont perd nos stats de base mais pas trop non plus, vus que les attributs de base suivant, PV, PM, FORCE, DEFENSE, MAGIE, ESPRIT, VITESSE, CHANCE augmente aussi avec une base de vos équipement pour divers système de construction de vos personnages mais n'e peut être changez part vous même,
il sont figé et n'e peut que changer leur augmentation que grâce aux système presque automatique dans le jeux en fonction des choix que vous faite, les équipement que vous pouvez changer sauf les anneaux et les amulettes puis les insigne et les émotion peut aussi augmenter ces valeurs, dit plus haut mais pas ceux la, Les Boucliers, Chapeaux, Vestes, Capes, Bottes et les armes augmente que des valeurs secondaires, pas d'attribut de base.