Ne rendez pas l'herbe derrière la colline : élimination des objets occultés tenant compte du terrain

Par Oleg Sidorkin, CTO et cofondateur de Cinevva

La partie 28 présentait le prototype 57 et comparait ses quatre méthodes d'élimination en quelques paragraphes. Voici la version longue : pourquoi ces quatre-là, quelles étaient les quatre autres et le raisonnement qui sous-tend celle que nous allons mettre en production.

Il y a une colline entre la caméra et une prairie. Inutile de rendre la prairie. Tous les moteurs AAA modernes le savent. La plupart des moteurs 3D pour navigateur ne le savent pas, y compris le nôtre jusqu'à la semaine dernière.

Cet article est le fruit d'une recherche menée sérieusement, ancrée dans notre véritable base de code, de la création d'un prototype fonctionnel et d'une évaluation des techniques selon leur utilité pour nous en particulier, sachant que nous déployons aujourd'hui sur WebGL et demain sur WebGPU.

Vous pouvez essayer le prototype en direct ci-dessous avant de poursuivre votre lecture. T/Y/U/I permettent de basculer entre les méthodes d'élimination, C fait défiler les préréglages de caméra et B affiche en fil de fer rouge les chunks masqués afin que vous puissiez voir ce que le test élimine. Le HUD indique combien d'instances sont rejetées à chaque étape.

Ouvrir le prototype 57 dans un nouvel onglet ↗ · Voir le code source

Ce que fait actuellement notre moteur — et ce qu'il ne fait pas

Notre gestionnaire de streaming de chunks charge autour du joueur un anneau de chunks de 64 m, répartis sur trois niveaux de détail. Chaque chunk contient des arbres instanciés dispersés sur la carte de hauteurs. La logique d'élimination, qui se trouve dans Chunk.updateObjectVisibility, repose sur un simple test de distance : les arbres situés à moins de 60 m sont rendus avec leur maillage complet, ceux situés entre 60 et 140 m sous forme de panneaux d'affichage, et ceux au-delà ne sont pas rendus.

Cette méthode passe à côté de deux énormes catégories de travail inutile :

1. Tout ce qui se trouve dans le disque de 60 m, mais derrière la caméra. Nous retrions le tampon d'instances chaque fois que le joueur se déplace de plus de 4 m, mais nous ne testons pas le tronc de vue. En moyenne, la moitié du disque est donc envoyée au GPU pour être simplement découpée après la transformation des sommets.
2. Tout ce qui se trouve dans le disque de 60 m, mais derrière une colline. Notre terrain présente 80 m de dénivelé et de nombreuses vallées. Lorsque la caméra est dans une vallée, la plus grande partie de la végétation située dans le rayon d'élimination est géométriquement masquée par la crête la plus proche. Nous la rendons quand même.

Cet article se concentre sur la deuxième catégorie. C'est aussi celle que les moteurs AAA corrigent grâce à tout un arsenal d'astuces qui, à première vue, ne se transpose pas facilement au navigateur.

Gilbert Sanders, de Guerrilla, explique comment Horizon Zero Dawn rend la végétation de son monde ouvert. Les vingt dernières minutes sont consacrées à la chaîne d'élimination, et c'est une véritable leçon magistrale sur les raisons pour lesquelles « rendre moins » est préférable à « rendre plus vite ».

Huit techniques, évaluées pour notre cas

J'ai étudié la chaîne moderne d'élimination des objets occultés et évalué chaque élément selon son intérêt pour un monde ouvert procédural, fondé sur une carte de hauteurs et exécuté dans un navigateur. Deux axes : la valeur — la quantité de travail inutile éliminée dans notre scène — et le coût — l'effort d'ingénierie, ainsi que la part de notre pile technique qu'il faut modifier. Le raisonnement complet se trouve dans le dossier de recherche à l'origine de cet article ; en voici la version courte.

1. Élimination par tronc de vue pour chaque instance. Valeur élevée, faible coût. À l'heure actuelle, nous ne testons pas du tout le tronc de vue pour notre végétation instanciée. L'ajout de ce test réduit approximativement de moitié le travail dans n'importe quelle vue, demande une trentaine de lignes de code et peut être mis en production dès aujourd'hui avec WebGL. C'est de loin le gain facile le plus important, et nous aurions dû le faire il y a plusieurs mois.

2. Lancer de rayon sur l'horizon de la carte de hauteurs. Valeur élevée, coût faible à moyen. On fait progresser un rayon de la caméra vers chaque instance candidate en échantillonnant la hauteur du terrain le long du trajet. Si le terrain dépasse le rayon à un moment quelconque, l'instance est occultée. Cette approche fonctionne précisément parce que notre monde est une carte de hauteurs, ce qui réduit la visibilité à un problème unidimensionnel le long de la direction horizontale. La version dense a une complexité O(nombre d'étapes) par instance et par image. La version accélérée — l'élément suivant — la ramène à O(log(nombre d'étapes)).

3. Accélération par pyramide de hauteurs maximales. Valeur élevée, coût moyen. Une mipmap 2D de la carte de hauteurs dans laquelle chaque texel stocke la hauteur maximale du terrain à l'intérieur de son empreinte. Elle permet au lancer de rayon sur l'horizon d'avancer par grands pas lorsque les environs sont plats et de n'affiner le test qu'au niveau des collines. C'est cette structure qui rend la technique nº 2 suffisamment peu coûteuse pour la production.

4. Élimination hiérarchique par tampon de profondeur (Hi-Z/HZB). Valeur élevée, coût élevé. On construit une mipmap du tampon de profondeur, on projette les limites de chaque instance dans l'espace écran, puis on les teste avec le niveau de mipmap approprié. C'est la méthode GPU moderne de référence, utilisée par Nanite dans Unreal, la géométrie virtuelle de Bevy et le portage WebGPU de VTK. Elle fonctionne pour tout, pas seulement pour le terrain, mais nécessite WebGPU, des appels de rendu indirects et une passe de calcul. Elle devient rentable lorsque nous rendons des millions de brins d'herbe, et non quelques milliers d'arbres.

5. Hi-Z en deux passes, à la manière de Nanite. Gain marginal par rapport à la nº 4, coût élevé. On effectue un nouveau rendu de la profondeur de l'image actuelle après la première passe afin d'éviter l'artefact de désoccultation sur une image. Cela ne vaut le coup qu'une fois que notre pipeline piloté par le GPU est suffisamment avancé pour que ce coût ne soit qu'incrémental.

6. Rastériseur logiciel d'occultation (Frostbite/Intel MOC). Valeur moyenne, coût élevé. On rastérise sur le CPU un tampon de profondeur basse résolution contenant les grands éléments occultants. Aucune latence de relecture. Les implémentations de référence sont en C++ avec AVX/SSE ; leur portage vers WASM constitue un véritable projet, alors que notre lancer de rayon sur la carte de hauteurs apporte l'essentiel des mêmes gains pour une fraction du travail.

7. PVS précalculé. Faible valeur, coût élevé. Une solution élégante pour les cartes statiques de l'époque de Quake. Notre terrain est procédural et infini : tout prétraitement doit donc s'effectuer au moment du streaming des chunks, ce qui coûte à peu près autant que de calculer directement la visibilité à l'exécution. À écarter.

8. Élimination par horizon à la manière de Cesium. Aucun intérêt pour nous, coût moyen. Cette technique est conçue pour les ellipsoïdes planétaires. Notre monde est relativement plat et délimité ; les calculs ne s'appliquent pas et ne produiraient soit aucun effet, soit des éliminations erronées. À écarter.

Conclusion : implémenter maintenant la nº 1 et les nº 2+3 sur le CPU, avec WebGL. Prévoir la nº 4 pour la migration vers WebGPU. Écarter le reste.

Pourquoi le lancer de rayon sur une carte de hauteurs l'emporte pour les terrains dans le navigateur

Le conseil habituel de toute présentation moderne sur le rendu est : « Construisez un tampon Hi-Z. » La présentation approfondie de Brian Karis sur Nanite à la SIGGRAPH 2021 est la référence en la matière, et vous devriez la regarder au moins une fois.

C'est la bonne réponse pour un moteur qui fait déjà tout passer par des appels de rendu indirects pilotés par le GPU. La plupart des moteurs pour navigateur, y compris le nôtre, ne fonctionnent pas ainsi. Nous avons des tampons d'instances gérés côté CPU, des appels de rendu WebGL et aucune étape de calcul. Greffer Hi-Z sur cette pile implique de migrer simultanément vers WebGPU, de réécrire le pipeline de végétation pour utiliser des appels indirects et d'ajouter une passe de construction de la pyramide de profondeur. Cela représente trois mois de travail avant même d'obtenir la première image démontrant la validité de l'idée.

Le lancer de rayon sur la carte de hauteurs fonctionne sur le CPU, avec WebGL et avec les données dont nous disposons déjà. Il exploite une caractéristique de notre monde dont les moteurs AAA ne peuvent pas tirer parti : nos éléments occultants sont décrits par une fonction de hauteur unidimensionnelle. Échantillonner cette fonction le long d'un rayon ne demande que deux lectures de tableau et une multiplication. Un tampon Hi-Z devrait redécouvrir le même fait pixel par pixel.

La technique a été publiée pour la première fois sous le titre « Horizon Occlusion Culling for Hierarchical Terrains » lors d'IEEE Visualization 2002 (PDF). Elle est restée dans la boîte à outils pendant deux décennies parce qu'elle présente le bon profil : peu coûteuse lorsque le terrain est plat, coûteuse uniquement là où se trouvent réellement des collines et trivialement parallélisable.

Représentation de la pyramide de hauteurs maximales

Le lancer de rayon naïf échantillonne terrainHeight en environ 24 points le long de chaque rayon et s'interrompt dès que le terrain le traverse. Cela convient pour des milliers d'arbres. La méthode s'effondre avec des centaines de milliers de brins d'herbe.

La solution consiste à créer une mipmap de la carte de hauteurs dans laquelle chaque texel stocke la hauteur maximale à l'intérieur de son empreinte :

level 0 (256×256, 2.25m per texel):  max h of 4×4 jittered samples
level 1 (128×128, 4.5m  per texel):  max(0,0), max(1,0), max(0,1), max(1,1)
level 2 ( 64×64,  9.0m per texel):  same reduction one level up
...
level 8 (   1×1,  576m per texel):  global max

Lorsque le segment du rayon est long et plat, on échantillonne un niveau grossier : une seule lecture nous indique qu'« aucun point du terrain dans ce carré de 9 m ne dépasse jamais 12 m d'altitude, et le rayon se trouve ici à 30 m, donc on peut continuer ». Ce n'est que lorsqu'un texel grossier indique que « le terrain pourrait dépasser le rayon » que l'on descend d'un niveau pour affiner le test. L'ensemble de la structure n'occupe que quelques centaines de Ko et se construit en quelques dizaines de millisecondes.

Sous forme de schéma :

                                            ray from eye
        eye 1.7m                          o─────────────────────►
              o─────────────────────────·─·─·─·─·─·──────────────
              │                          \                       │
              │   level 3 (huge step)     \   level 0 (refine)   │
              │   "no terrain above 8m"    \   "9m hill here!"   │
              │                              \                   │
        ──────┴────────────/▔▔▔\─────────────/▔▔▔▔▔\─────────────
                                 hill A (8m)   hill B (12m)
                                                ↑
                                                blocks here

Pour le segment du rayon qui passe à proximité de la colline A, la lecture au niveau 3 — « la hauteur maximale dans cette zone de 18 m de large est de 8 m » — nous indique déjà que le rayon, à une altitude de 1,7 m plus quelques mètres d'élévation, ne rencontre aucun obstacle. Une seule requête nous permet de sauter 36 m de progression. Au-dessus de la colline B, le niveau 3 indique « le maximum est ici de 12 m » ; nous descendons alors d'un niveau, et le niveau 0 confirme « oui, 12 m à ce texel précis ». Nous rejetons donc l'instance.

La construction de la pyramide se trouve dans height-pyramid.mjs, et les méthodes d'élimination qui l'utilisent dans cull.mjs. Les deux fichiers sont consultables dans le navigateur du code source du prototype.

Ce que montre réellement le prototype

Ouvrez le prototype 57 ci-dessus et essayez les quatre méthodes :

• T0 correspond à ce que fait actuellement la version de production. Uniquement un test de distance. Depuis C1 — le fond de la vallée —, le HUD indique qu'environ 12 000 brins d'herbe sont visibles.
• T1 ajoute l'élimination par tronc de vue pour chaque instance. Le nombre d'éléments visibles est approximativement divisé par deux, car tout ce qui se trouve derrière la caméra ou sur les côtés est éliminé avant d'atteindre le GPU.
• T2 ajoute le lancer de rayon exhaustif sur la carte de hauteurs. Dans C1, le nombre diminue encore de 60 à 80 %, car la plus grande partie du champ se trouve de l'autre côté de la crête la plus proche. La colonne Cull-ms augmente, car nous échantillonnons terrainHeight environ 24 fois par instance.
• T3 remplace la méthode exhaustive par la pyramide de hauteurs maximales. Cull-ms revient à une valeur proche de T1 tout en conservant le gain de visibilité. C'est la méthode à mettre réellement en production.

Ce comportement correspond à ce que constatent les moteurs de production. La série en deux parties d'Acerola sur le rendu de l'herbe — Comment les jeux parviennent-ils à rendre autant d'herbe ? et Ce que j'ai fait pour optimiser l'herbe de mon jeu — est l'explication la plus accessible sur YouTube des raisons pour lesquelles il faut consacrer ses efforts d'ingénierie à l'étape d'élimination plutôt qu'à celle de l'ombrage.

La caméra C3 et le cas d'échec « sommet de colline »

Le troisième préréglage de caméra du prototype place la caméra au sommet d'une colline, tournée vers l'ensemble de l'aire de jeu. Dans ce cas, l'élimination par horizon ne fait presque rien, car aucun terrain ne se trouve entre la caméra et la majeure partie du monde. Le HUD montre que T2/T3 ne réduisent le nombre d'éléments visibles que de 5 à 10 % par rapport à T1.

C'est une fonctionnalité, pas un bug. La technique cesse de fonctionner exactement là où elle le devrait : lorsqu'il n'y a rien pour masquer la vue. L'élimination par tronc de vue continue d'effectuer un vrai travail, l'élimination par distance continue de limiter le budget et le test d'horizon revient proprement à une opération sans effet. Si vous implémentez cette technique, vous devez vérifier que ce cas sans effet reste lui aussi peu coûteux. C'est pourquoi la pyramide de hauteurs maximales est importante même lorsqu'aucun rayon n'est rejeté : le niveau le plus grossier suffit souvent à confirmer que « rien n'est masqué ».

Ce que nous allons mettre en production

Il reste trois choses à faire, dans cet ordre.

Premièrement, intégrer T1 et T3 à la version de production de Chunk.updateObjectVisibility. La pyramide doit être placée un niveau plus haut, dans le gestionnaire de chunks, car elle couvre plusieurs chunks. L'élimination reste dans Chunk afin que le regroupement existant par chunk continue de fonctionner. Effort estimé : une journée, tests compris. Deuxièmement, faire de même pour l’herbe dès que nous en aurons. Le prototype actuel répartit 12 000 brins sur une zone de jeu de 576 m ; la densité en production devrait être environ dix fois supérieure. Les chemins de culling sur CPU traitent 12 000 brins en moins d’une milliseconde, et c’est l’accélération par pyramide qui permet de maintenir cette performance à 120 000.

Troisièmement, lors de la migration vers THREE.WebGPURenderer, porter cette même boucle dans un shader de calcul. Les métadonnées deviennent un tampon de stockage. Le culling écrit les arguments de drawIndirect. La pyramide est téléversée sous forme de texture 2D, avec la réduction par maximum déjà intégrée. La structure du code reste presque identique, et c’est bien là tout l’intérêt : nous ne faisons pas reposer la migration sur un nouvel algorithme, nous transférons un algorithme déjà éprouvé vers une voie plus rapide.

Guerrilla a présenté la version GPU de cette approche pour le système de placement procédural d’Horizon Zero Dawn ; le pipeline de rendu importe moins que les structures de données, et les leurs ont la même forme :

Le Hi-Z trouvera toujours sa place lorsque nous intégrerons des bâtiments et des éléments de décor denses qui produisent des occultations dans des directions que la carte de hauteur ne peut pas décrire. Mais la pyramide de carte de hauteur restera dans le pipeline, car elle est nettement moins coûteuse que le Hi-Z pour les instances proches du sol, et l’herbe qui chevauche la silhouette d’une crête correspond précisément au cas que le Hi-Z gère le moins bien.

Références

La justification complète, classée par priorité, ainsi que les décisions architecturales figurent ci-dessus ; voici les sources de référence pour chaque technique, approximativement dans l’ordre où elles apparaissent dans la pile.

• Yalim & Akman, Culling d’occultation par horizon pour les terrains hiérarchiques (IEEE Visualization 2002, l’article fondateur sur le culling par horizon du terrain).
• Turitzin, Tampons de profondeur hiérarchiques (l’explication la plus claire de la construction et de l’interrogation des chaînes de mipmaps Hi-Z).
• VKGuide, Culling basé sur le calcul (référence pour le pipeline de culling piloté par GPU ; le portage vers WebGPU est mécanique).
• Kruskonja, Culling d’occultation en deux passes (l’architecture de type Nanite expliquée en dehors des présentations d’Epic).
• Karis et al., Nanite — Analyse approfondie (SIGGRAPH 2021) (la référence moderne sur le culling piloté par GPU à l’échelle AAA).
• Karis, Conférence HPG 2022 : le parcours vers Nanite (contexte plus général expliquant l’importance de l’étape de culling).
• Sanders, Entre technologie et art : la végétation d’Horizon Zero Dawn (la pile de culling de végétation AAA de bout en bout).
• Guerrilla, Placement procédural à l’exécution basé sur le GPU dans Horizon Zero Dawn (placement instancié et visibilité par instance).
• Scthe, Nanite WebGPU (une implémentation WebGPU de référence, avec HZB).
• Kitware, Culling d’occultation WebGPU dans VTK (le premier HZB en production côté navigateur dont j’ai connaissance).
• Acerola, Comment les jeux parviennent-ils à afficher autant d’herbe ? et Comment j’ai optimisé l’herbe de mon jeu (la présentation YouTube accessible).
• RasterGrid, Culling d’occultation basé sur une carte Hi-Z (l’introduction au Hi-Z qui fait toujours référence).
• Intel, Culling d’occultation logiciel masqué (la famille des rastériseurs CPU, si vous décidez un jour que l’option nº 6 en vaut la peine).