D'un genre nouveau, voici un article qui parle du rendu 3D temps réel et plus précisément d'une technique d'optimisation de celui-ci ainsi que de son implémentation dans le [SCEngine](http://scengine.tuxfamily.org), mon moteur 3D que je ne présente plus. ## Batch batch batch ! À l'origine c'est le nom [d'un article](batchbatchbatch) assez connu publié par [nVidia](http://www.nvidia.com) en 2004, cela fait donc quelques temps déjà. L'article aborde en revanche un sujet qui est toujours d'actualité, le *batching*. ### Batching ou regrouper pour régner Vous l'aurez peut-être remarqué en faisant le petit curieux dans les dossiers de vos jeux vidéo, ou simplement en y jouant, que ceux-ci font appel à plusieurs types de ressources pour le rendu 3D ; des images et des modèles 3D principalement, mais aussi des types de matériaux et des shaders. Chacune de ces ressources est traitée différemment des autres bien qu'au final l'image soit un mélange harmonieux de celles-ci. Prenons un jeu de course de voitures. Le coureur A roule en Audi rouge avec des sponsors TLC. Le coureur B roule aussi en Audi mais cet hérétique est sponsorisé par SDZ et sa carrosserie est bleue. Enfin le coureur C roule en BMW bleue sponsorisé par TLC. Faisons les associations suivantes : * chaque modèle de voiture est un modèle 3D, c'est-à-dire un * [maillage](lienwp pour maillage) ; la couleur est définie par un * [shader](lien vers shader blabla) ; un sponsor c'est une * [texture](blaaaa), c'est-à-dire une image appliquée sur un modèle * 3D. Dans notre jeu de voitures nous avons les ressources suivantes : * modèles 3D : * une audi ; * une BMW ; * shaders : * un bleu ; * un rouge ; * textures : * un sponsor TLC ; * un sponsor SDZ. ### Déroulement du rendu et changement d'état Le batching n'est pas une technique algorithmique super intelligente qui diminue la complexité d'un algorithme quelconque. C'est une façon d'organiser le rendu 3D qui repose sur la connaissance du fonctionnement des cartes graphiques afin d'en tirer le meilleur profit. Basiquement un rendu 3D est on ne peut plus simple : :Code[C]: /* coureur A */ set_texture (tlc); set_shader (rouge); set_model (audi); set_position (a); render (); /* coureur B */ set_texture (sdz); set_shader (bleu); set_model (audi); set_position (b); render (); /* coureur C */ set_texture (tlc); set_shader (bleu); set_model (bmw); set_position (c); render (); Le principe est de spécifier les ressources qui seront utilisées, puis de lancer le rendu, rien de magique. Notez que spécifier la position où doit être dessiné l'objet est également un changement d'état. Seulement voilà, les fonctions `set_*()` coûtent vraiment très cher à la carte graphique car elles représentent un changement d'état. Pour la carte graphique un changement d'état c'est comme si vous passiez du BigMac à la salade de fruits, il faut un bon verre d'eau et le temps que le goût du BigMac s'en aille. En pratique la carte graphique va mettre les ressources demandées dans des zones de la mémoire graphique (VRAM) accessibles très rapidement, parfois même en mémoire cache, afin que le rendu soit rapide. Le problème c'est que déplacer ces ressources est une opération lourde, mieux vaut l'éviter au maximum afin d'accélérer le rendu global. C'est ça le batching ! Notez que les opérations qui ont lieu lors d'un changement d'état, comme toutes les opérations effectuées par le [GPU](prooot) d'ailleurs, sont décidées par le driver de la carte graphique. Les améliorations de performances peuvent donc varier d'une version du driver à l'autre, d'une carte graphique graphique à l'autre et plus notablement d'un constructeur à l'autre. Le batching a toutefois toujours été un gain dans la mesure où il repose sur un principe assez fondamental du fonctionnement des cartes. Puisque le batching consiste à regrouper les ressources identiques utilisées à plusieurs reprises, voyons comment nous pourrions dessiner nos voitures : :Code[C]: /* coureur A */ set_texture (tlc); set_shader (rouge); set_model (audi); set_position (a); render (); /* coureur B */ set_texture (sdz); set_shader (bleu); /* changement d'état inutile, on utilise déjà l'audi ! */ /* set_model (audi); */ set_position (b); render (); /* coureur C */ set_texture (tlc); /* changement d'état inutile */ /* set_shader (bleu); */ set_model (bmw); set_position (c); render (); Et là, horreur ! On se rend compte qu'il existe d'autres possibilités : :Code[C]: /* coureur A */ set_texture (tlc); set_shader (rouge); set_model (audi); set_position (a); render (); /* coureur C */ set_shader (bleu); set_model (bmw); set_position (c); render (); /* coureur B */ set_texture (sdz); set_model (audi); set_position (b); render (); Ceci en considérant bien entendu que l'ordre de rendu n'a aucune importance, ce qui est très souvent le cas en pratique. La véritable question est donc de savoir quels changements d'état sont véritablement coûteux. Et que faire si un coureur D avec une BMW rouge sponsorisé par SDZ fait son entrée en jeu ? À la première question la réponse est que ceci dépend du driver et qu'à ce niveau il devient difficile d'extraire une généralité. Constat personnel : les shaders sont relativement coûteux à mettre en place. Mais ce constat n'a été fait que sur une seule carte avec un seul driver. ## Implémentation simple Je vais présenter ici une implémentation générique et simple du batching. Son grand avantage est de ne rien coûter pendant le jeu ; tout est précalculé. Je vous laisse imaginer l'impact sur les performances si vous deviez à chaque frame trier vos ressources, ça ne serait pas si génial. ### Ce que je vous ai caché Bien que je ne vous ai pas (encore) menti, il y a en pratique des faits qui faciliteront vos choix tout comme ils ont facilité les miens. Premièrement, il faut savoir qu'un GPU calcul *beaucoup* plus rapidement qu'un CPU. Calculer un bon batching à la volée n'est donc pas une bonne idée, il vaut mieux laisser le GPU faire quelques changements d'états en trop, qui seront effectués plus rapidement que votre CPU ne les aurait trouvé. De même, outre les opérations que demandent un changement d'état à votre carte graphique, ce n'est pas toujours ça qui prend le plus de temps. Le simple fait que votre CPU fasse un appel de fonction du driver prend du temps. Bien que cela semble totalement improbable, il est fréquent que la carte graphique attende qu'un appel au driver se termine pour continuer son travail. % ce paragraphe pue un peu, surtout sur la fin Deuxièmement il y a des regroupements à favoriser en priorité, mais qui en bloqueront d'autres. C'est pratique, ça diminue les possibilités et donc facilite notre algorithme pour faire un bon batching ! Ça nous évitera de trop nous demander quoi faire quand le coureur D entrera en piste par exemple. Les drivers proposent même des fonctions intégrées pour faire ça directement, il s'agit du geometry instancing ! Il repose sur le même fait qu'énoncé plus haut, à savoir qu'il faut éviter les calculs CPU au maximum pendant le rendu. Vous pouvez ainsi rendre plusieurs instances du même modèle 3D avec un seul appel de fonction, le problème c'est que vous ne pouvez pas modifier les autres ressources pendant ce temps. On ne pourrait pas l'utiliser pour rendre nos deux Audi en même temps par exemple, car elles n'ont pas la même couleur. Il existe des astuces pour faire comme si ce problème n'existait pas, notamment pour spécifier la position de chaque instance, qui doit quand même changer parce que sinon ça ne servirait à rien ! Elles sont toutefois trop pointues et n'entrent donc pas dans le cadre de cet article. ### Notion d'entité et d'instance De mon côté, dans le SCEngine, j'ai fait les choix suivants. Ce que j'ai appelé une *entité* (type `SCE_SSceneEntity`) dans le moteur est un ensemble de ressources. La BMW bleue TLC serait donc une entité composée du modèle de la BMW, du shader bleu et de la texture TLC. Il y aurait trois entités puisque nous avons trois voitures différentes. Toutefois une entité représente que le modèle de la voiture et pas la voiture elle-même. Si on veut véritablement créer une voiture il faut attacher à l'entité correspondante une *instance*, définie dans le moteur par le type `SCE_SSceneEntityInstance`. L'idée est qu'il est possible d'attacher plusieurs instances à une seule entité, chaque instance étant uniquement différenciée par sa position et quelques paramètres obscurs qui font référence aux astuces pointues évoquées plus haut. Pour prendre l'exemple classique, il serait aisé de créer un champ d'astéroides avec seulement trois ou quatre entités différentes, les instances variraient suffisamment de taille et d'orientation (et de paramètres obscurs) pour donner l'illusion du réalisme alors qu'ils ont tous quasiment la même postérité. Dernier point important, les ressources peuvent bien sûr être partagées entre les entités. Puisque tous les astéroides ont la même tête, on pourrait partager le même shader qui ferait un effet "cailloux" ainsi que la même texture. N'oubliez pas que moins les programmeurs et les modeleurs feront les autistes et plus il y aura de bénéfices à faire sur les performances et le développement. Les programmeurs pourront peut-être se priver d'un peu de généricité au profit d'une méthode rapide à mettre en œuvre tout en conservant les mêmes performances, et les modeleurs et/ou graphistes éviteront de faire des doublons inutiles en se concentrant sur des ressources polyvalentes. Le rendu est ensuite effectué non pas instance par instance mais entité par entité, en toute logique. Une entité connaissant toutes ses instances, elle met en place les états qu'elle représente, c'est-à-dire ses ressources, puis lance le rendu de chaque instancee sans se soucier de changer un quelconque état. C'est déjà ça de gagné, mais on peut aller encore plus loin. ### Trier les entités qui partagent les mêmes ressources L'idée est de faire un précalcul pour le batching. Le précalcul est une sorte de tri et prend un certain temps ce qui implique de connaître quelles seront *toutes* les ressources utilisées. L'ajout d'une nouvelle ressource entraînera un batching non optimal ou un nouveau tri. Si c'est pour un jeu, faites un tri avant chaque niveau du jeu ou pendant chaque chargement par exemple. Le tri fonctionne de la manière suivante. Il choisi un type de ressource puis pour chaque ressource de ce type crée un groupe des entités qui utilisent cette ressource. Il choisi un autre type de ressource puis recommence l'opération mais cette fois-ci en limitant la recherche des entités aux groupes créés précédemment. On crée ainsi des sous-groupes, chaque entité d'un sous groupe a donc deux ressources en commune avec les autres entités de son sous-groupe, etc. En pratique toutes les entités sont classées dans une sorte de grand tableau, et un groupe est caractérisé par une séquence contigü dans ce tableau. Les sous-groupes sont des sous-séquences. #### Limites Évidemment parmi tous les sous-groupes, il y aura des entités qui utiliseront les mêmes ressources mais dont le groupe racine ne sera pas le même. shader : aaaaa bbb cccc texture : 11222 133 1224 Ceci représente un tableau d'entités trié. Ici les différents shaders sont représentés par des lettres et les différentes textures par des chiffres. Une colonne est une entité. Les groupes racine sont séparés par des espaces. Il existe en théorie un groupe encore inférieur qui trie les entités qui utilisent le même modèle 3D, mais à cause des astuces pointues et obscures il n'a pas été dessiné et n'existe pas vraiment en pratique. Pour en revenir à notre cas, on aurait bien voulu que les entités qui utilisent la texture 2 soient côte à côte, en faisant les bons décalages on pourrait obtenir ceci, qui est optimal : shader : bbb aaaaa cccc texture : 331 11222 2214 Voici donc ce que mon algorithme ne fait *pas*. Je vous^W m'offre les consolations suivantes : * ce sont des situations en pratique peu fréquentes ; le gain en * nombre de changements d'état est à peu près aussi grand que le * nombre de groupes racine, ce qui n'est pas énorme. Je rappelle que ce sont des consolations. Il serait intéressant de mesurer le gain moyen en nombre de changements d'états avec un nombre d'entités et de ressources donnés, en considérant que au début les entités sont rangées aléatoirement dans le tableau. ## Compléments : atlas de textures, branching, RenderRange(), ...