Construire un monde ouvert dans le navigateur, partie 18 : un pinceau de dispersion qui semble guidé par l’IA
Par Oleg Sidorkin, CTO et cofondateur de Cinevva
Vous découvrez la série ? Consultez le guide de la série. Il explique ce qu’est un spike et contient des liens vers toutes les parties.
La partie 17 a doté le joueur d’un ensemble d’animations digne d’un jeu de combat et d’un moyen d’importer n’importe quel modèle CC0 dans le monde. Cette partie revient aux outils de création. La palette du spike 34 place un accessoire par clic, ce qui convient pour mettre en scène un objet principal, mais ne sert à rien pour créer une forêt. Le spike 37 introduit le pinceau : faites-le glisser sur le terrain et les arbres apparaissent là où ils devraient pousser.
Un placement « par IA » sans IA
Ouvrir le spike 37 dans un nouvel onglet ↗ · Voir le code source
Ce spike cherche à déterminer si un pinceau purement heuristique peut sembler suffisamment intelligent pour se passer d’un LLM. Le critère d’un placement « par IA » est concret : les arbres évitent les falaises, les rochers s’inclinent dans la pente et les galets de plage s’arrêtent au bord de l’eau, le tout dès le premier coup de pinceau. Nous y sommes parvenus avec des prédicats de pente et d’altitude, des tirages pondérés et un espacement propre à chaque famille, sans le moindre appel à un modèle.
Le pinceau fonctionne sur une carte de hauteurs CPU de 257×257 comportant des reliefs ajustés à la main afin que chaque préréglage dispose d’une zone appropriée : des montagnes au nord pour les sélections à pentes mixtes, une bande de falaises à l’est pour les éboulis, une plaine côtière au sud pour la plage et la prairie, et une cuvette lacustre au sud-ouest. Le terrain précalcule les couleurs des sommets à partir d’un classificateur de biome (altitude, slope). Avant même de peindre le premier arbre, on peut donc voir où un préréglage s’appliquera. Cinq préréglages sont fournis sous forme de données plates, chacun avec une liste de sélections telles que { category, weight, slopeMin, slopeMax, altMin, altMax, minSpacing, alignToSlope }. Cliff and Scree définit slopeMin: 0.3, de sorte que les rochers ne soient placés que sur de véritables pentes, ainsi que alignToSlope: true, afin que le vecteur vertical de chaque bloc rocheux suive la normale de la surface.
Pour chaque trait, le moteur de dispersion échantillonne densityPerM2 × area points candidats à l’intérieur du disque du pinceau, lit la hauteur et la pente de chaque candidat, filtre les sélections du préréglage selon les prédicats satisfaits, en choisit une par tirage pondéré, puis vérifie l’espacement à l’aide d’une table de hachage spatiale limitée au rayon concerné. L’ensemble est déterministe : un générateur aléatoire Mulberry32 initialisable contrôle chaque tirage, si bien que (seed, brush events) reproduit exactement n’importe quelle session. Sur le terrain initial, un trait Mixed Forest appliqué à une prairie plate a placé 139 candidats sur 158 en 5 ms. Sur une falaise, le même préréglage n’en a placé que 106 sur 226, et le HUD a indiqué que 81 avaient été rejetés à cause de la pente. Cette ventilation des rejets constitue toute l’expérience utilisateur : on comprend pourquoi la falaise n’a reçu que quelques arbres au lieu de devoir le deviner.
L’intérêt de conserver les préréglages sous forme de données plates est que la future version fondée sur un LLM ne nécessitera qu’un remplacement de JSON, pas une réécriture. paint({ preset }) ne se soucie pas de savoir si preset.picks provient d’une recette ajustée à la main ou d’un worker ayant transformé « forêt de feuillus avec des blocs rocheux couverts de mousse » en pondérations. Le moteur ne code jamais en dur l’identifiant d’un accessoire non plus : l’utilisation d’un autre catalogue ne nécessite donc aucune modification du moteur.
De 300 appels de rendu à 49
La première version affichait chaque placement sous la forme d’un clone(true) d’un groupe composé de plusieurs maillages. Cela convient pour quelques centaines d’accessoires, mais devient un obstacle à la limite de 2 500, où le nombre d’appels de rendu grimpe à plusieurs milliers. Avant d’en arriver là, nous sommes passés à InstancedMesh, avec un lot par (propId, partIndex). La capacité de chaque lot double à mesure qu’il grandit : un InstancedMesh plus grand est alloué, les matrices actives y sont copiées, le parent de la scène est remplacé et l’ancien attribut est libéré. L’effacement utilise une suppression par échange, de sorte que retirer une instance reste une opération O(1), quelle que soit la taille du lot. Le déterminisme, l’espacement et le HUD des rejets restent inchangés, car cette substitution se déroule entièrement sous le niveau de l’enregistrement du placement.
Un diagnostic effectué sur le pack MegaKit a permis de trancher une véritable question d’architecture. Un maillage glTF à plusieurs primitives — tronc et feuilles — peut parvenir dans three.js soit sous la forme d’un seul maillage doté d’un tableau de matériaux et de geometry.groups, soit sous celle de maillages frères distincts ayant chacun un seul matériau. Pour ce pack, le chargeur choisit la seconde voie : chaque partie est un maillage à matériau unique dont les groupes sont vides. C’est la meilleure structure pour la dispersion, car des lots distincts par primitive permettent au lot des troncs de grandir indépendamment de celui des feuilles si leurs nombres divergent. Le nombre d’appels de rendu reste identique dans les deux cas, mais la structure de mémoire est meilleure avec cette séparation. Le gain mesuré s’est confirmé : un trait de forêt qui nécessitait environ 300 appels de rendu n’en demandait plus que 49, et une session complète à plusieurs traits a atteint 3 221 instances à 75 FPS avec 51 appels de rendu, un plafond que la méthode par clonage ne pouvait jamais atteindre avant l’effondrement du budget d’image.
LOD selon la distance et quatre bugs qui s’y cachaient
L’instanciation a réduit le nombre d’appels de rendu, mais chaque instance affichait toujours l’intégralité de ses triangles, même pour les arbres situés à 90 m dont le détail des feuilles ne représentait que deux pixels. Nous avons donc précalculé trois niveaux de LOD par partie d’accessoire avec meshoptimizer — complet, 50 %, 15 % —, étendu la clé de lot à (propId, partIndex, lod) et ajouté une méthode move() qui transfère un placement entre des lots frères sans allocation. Les plages de distance vont de 0 à 30 m, de 30 à 90 m, puis au-delà, avec une hystérésis de ±4 m autour de chaque limite afin qu’une caméra stationnant près d’un seuil ne déplace pas sans cesse un placement dans un sens puis dans l’autre tout en retéléversant sa matrice à chaque image. La réévaluation est plafonnée à 4 Hz et n’a lieu que si la caméra s’est réellement déplacée. Une caméra immobile ne coûte donc qu’une comparaison de distance au carré par image.
C’est dans ce chemin de LOD que se cachaient les bugs les plus instructifs. Le premier se manifestait par des placements qui disparaissaient ou se dupliquaient lorsque la caméra tournait autour de la scène, et le problème empirait à mesure que celle-ci se remplissait. La cause était une matrice temporaire partagée : move() lisait la transformation d’un placement dans _tmpMat, définie au niveau du module, mais la suppression par échange du lot source utilisait cette même _tmpMat pour son réagencement interne. Elle écrasait donc la matrice transportée avant que la destination ne puisse l’écrire. Le bug épargnait uniquement le cas où l’emplacement déplacé était déjà le dernier de son lot, soit une probabilité d’environ 1/count. Cela correspond exactement au « scintillement rare qui empire à mesure que la scène grandit » observé pendant le test de jeu. La correction a consisté à réserver une matrice _carryMat exclusivement à move(). Après un test de résistance totalisant 1 274 déplacements, le groupe est resté identique au pixel près.
Le deuxième bug était plus subtil : chaque transition de LOD semblait fluide, sauf la première. Les arbres passant au LOD1 présentaient un changement visible d’ombrage alors que leur silhouette variait à peine, tandis que les réductions de triangles plus importantes aux niveaux suivants restaient imperceptibles. Le simplificateur utilisant LockBorder ne déplace ni ne crée jamais de sommets, de sorte que les sommets conservés gardent exactement leurs normales. Pourtant, nous appelions tout de même computeVertexNormals() après chaque simplification. Le LOD0 conserve intactes les normales originales créées par l’artiste, tandis que le LOD1 et les suivants recevaient le recalcul générique de three.js fondé sur la moyenne des faces. Le passage de 0 à 1 était le seul endroit de la chaîne où le régime des normales changeait, et c’est donc là que se produisait le saut visuel. La suppression de cette unique ligne défensive a corrigé l’ombrage et, en prime, réduit de moitié environ le temps de précalcul par accessoire, puisque nous avons cessé de recalculer les normales de quatre LOD par partie.
L’examen de la sortie du simplificateur a révélé un troisième gain. Chaque LOD était un original.clone() doté d’un nouvel index, et BufferGeometry.clone() copie en profondeur chaque attribut. Cinq LOD conservaient donc cinq copies indépendantes des tampons de positions, de normales, d’UV et de couleurs, alors que leurs valeurs étaient strictement identiques bit pour bit. Nous avons remanié le système pour partager les références d’attributs et ne conserver qu’un tampon d’index privé par LOD. Pour une partie d’arbre typique, le nombre d’identités d’attributs distinctes est ainsi passé de 20 à 9, et chaque tampon de sommets n’est plus téléversé qu’une seule fois vers le GPU. Ce stockage partagé impose deux règles : ne jamais modifier les données d’attribut depuis un LOD particulier et ne jamais appeler dispose() sur la géométrie d’un seul LOD, car ces deux opérations affecteraient tous les LOD frères partageant le tampon.
Le quatrième bug n’avait rien à voir avec la peinture. Le simple fait d’agiter le curseur au-dessus du terrain faisait chuter la fréquence d’images, sans qu’aucun bouton soit enfoncé. Le gestionnaire pointermove effectuait un lancer de rayon sur le maillage du terrain, un plan de 131 072 triangles dépourvu de structure spatiale. three.js parcourait donc l’intégralité du tampon d’index à chaque événement, jusqu’à 1 000 événements par seconde. Nous n’avions absolument pas besoin du maillage pour cette recherche, puisque le terrain est une carte de hauteurs paramétrique. Une marche de rayon adaptative sur sampleHeight — grands pas très au-dessus de la surface, minimum de 0,4 m à proximité, puis 12 dichotomies lors du changement de signe — nécessite environ 8 à 30 échantillons par rayon au lieu de 131 072 tests de triangles. Elle est environ trois ordres de grandeur moins coûteuse, et le survol respecte de nouveau la fréquence d’images maximale.
Le coût ne fait que se déplacer ; assurez-vous qu’il quitte le clic
Après la migration du spike vers WebGPURenderer avec three r184 — la cible de production —, un profil DevTools a montré que le tout premier coup de pinceau bloquait l’exécution pendant 265 ms, dont 79 % dans le WASM de meshoptimizer. Le précalcul représentait un véritable travail, environ 180 appels de simplification pour un préréglage à froid, mais il s’exécutait dans le gestionnaire de clic parce que preloadProps se contentait de récupérer et d’analyser les scènes sans jamais déclencher le précalcul des LOD. La correction a consisté à faire exécuter l’intégralité de ce précalcul en arrière-plan lors de la sélection d’un préréglage : preloadProps appelle désormais le chemin de résolution des parties, met en cache la promesse en cours afin qu’un clic rapide la rejoigne au lieu de créer une tâche en double, et mémorise le prétraitement par géométrie que le simplificateur répétait quatre fois par partie. Dans le HUD, le premier coup de pinceau est passé de 209 ms à 4 ms. Le temps WASM n’a pas disparu : il a simplement quitté le chemin critique de l’utilisateur et s’exécute pendant que celui-ci observe le terrain pour décider où peindre.
C’est la leçon récurrente de ce spike. Presque aucune de ces corrections n’a changé ce que le pinceau fait. Elles ont changé le moment où le coût est payé : plus pendant le clic, plus pendant le survol, plus au niveau du seuil près duquel la caméra stationne. Un outil de dispersion qui semble instantané n’effectue pas moins de travail : il l’effectue lorsque l’utilisateur ne l’attend pas.
Technologies abordées dans ce chapitre
Dispersion heuristique selon l’adéquation. Un pinceau échantillonne des points candidats dans un disque, lit (height, slope) pour chaque point dans une carte de hauteurs CPU, filtre les sélections d’un préréglage selon des prédicats de pente et d’altitude, en choisit une par tirage pondéré, puis la rejette si elle enfreint l’espacement minimal propre à sa famille, suivi dans une table de hachage spatiale. Les sélections alignées sur la pente font pivoter leur vecteur vertical selon la normale de la surface. Le placement paraît ainsi intentionnel — les arbres évitent les falaises, les rochers s’inclinent dans les pentes et les galets s’arrêtent au bord de l’eau — sans aucun poids appris. Le préréglage reste constitué de données plates, de sorte qu’une liste de sélections générée par un LLM puisse le remplacer directement.
Placement déterministe avec des chargements asynchrones. Un générateur aléatoire Mulberry32 initialisable contrôle chaque tirage, de sorte que (seed, brush events) reproduise exactement une session. Les tirages aléatoires ont lieu avant tout await, et les réservations d’espacement sont insérées dans l’index spatial avant la résolution du clone glTF. Les candidats concurrents se respectent donc mutuellement, et le chargement asynchrone des ressources ne peut pas perturber la séquence.
InstancedMesh répartis en lots avec modifications O(1). Un InstancedMesh par (propId, partIndex, lod), avec une capacité doublée à la demande en copiant les matrices actives dans un tampon plus grand. L’effacement et l’éviction FIFO utilisent une suppression par échange et un tableau de références inverses qui corrige l’index de l’instance déplacée. Une suppression reste donc O(1), quelle que soit la taille du lot. Un diagnostic a confirmé que les parties glTF arrivent sous forme de maillages à matériau unique. La création d’un lot par primitive constitue donc le chemin actif et fournit à chaque primitive un lot dont la capacité peut grandir indépendamment.
LOD selon la distance, avec hystérésis et tampons d’attributs partagés. Trois niveaux simplifiés par meshopt pour chaque partie, sélectionnés selon des plages de distance avec une hystérésis de ±4 m afin qu’une caméra proche d’un seuil ne provoque pas des basculements incessants, réévalués à une fréquence plafonnée et uniquement lors d’un véritable mouvement de caméra. Puisque la simplification LockBorder ne déplace jamais les sommets, tous les LOD partagent les mêmes tampons de positions, de normales, d’UV et de couleurs, et ne diffèrent que par leur tampon d’index privé. Le nombre de tampons de sommets GPU distincts est ainsi réduit d’environ moitié. La suppression d’un appel défensif à computeVertexNormals conserve les normales de l’artiste à l’identique dans tous les LOD et élimine l’unique discontinuité d’ombrage de la chaîne. Consultez LOD et meshoptimizer.
Lancer de rayon analytique sur une carte de hauteurs pour les recherches à haute fréquence. Une recherche liée à pointermove sur un maillage plan de 131 000 triangles parcourt l’intégralité du tampon d’index à chaque événement. Son remplacement par une marche de rayon adaptative sur la fonction de hauteur analytique — grands pas loin de la surface, petit pas minimal à proximité, dichotomie lors du changement de signe de
Sortir le travail du chemin critique de l’interaction. Les opérations ponctuelles coûteuses — précalcul des LOD meshopt, compilation des pipelines WGSL — doivent s’exécuter pendant les périodes d’inactivité, pas dans le gestionnaire de clic. Le préchargement du précalcul complet du préréglage actif lors de sa sélection, la mise en cache de la promesse en cours afin qu’un clic rapide la rejoigne plutôt que de la dupliquer, et la mémorisation du prétraitement par géométrie ont réduit la latence du premier coup de pinceau de 209 ms à 4 ms, sans diminuer la quantité totale de travail.
Partie 18 sur 29. Précédent : Partie 17 - Des animations qui n'avaient pas besoin de reciblage, et une recherche de ressources en direct Suivant : Partie 19 - L'imposteur qui doit survivre à une forêt Guide de la série : /fr/blog/2026-02-25-open-world-browser-series-guide