Ce que l'on appelle communément culling en programmation 3D, est le fait d'éliminer prématurément des parties de la scène qui ne seront pas visibles à l'écran ; soit parce qu'elles sont cachées, soit parce qu'elles ne sont pas dans le champ de vision.

Le culling se décline en plusieurs techniques, dont les principales sont :

• Le backface culling ;
• L'occlusion culling ;
• Le frustum culling ;
• Le contribution culling.

Chaque technique de culling a un domaine d'application plus ou moins particulier, il faudra donc apprendre à utiliser la ou les bonnes selon les besoins et le type de votre application. N'hésitez pas non plus à combiner certaines d'entre elles : certaines s'y prêtent tout particulièrement.

Quoi qu'il en soit, le culling est l'une des optimisations les plus importantes dans une application 3D, qu'il ne faudra donc jamais négliger pour peu que vous affichiez plus de 100 polygones. N'oubliez pas que ce que vous voyez à l'écran ne représente bien souvent qu'une infime partie de la géométrie, et qu'il est donc inutile d'envoyer au hardware tout le reste.
Il ne faut également pas tomber dans l'excès inverse : un culling trop précis peut ralentir vos performances. Ainsi on ne pousse pratiquement jamais celui-ci au niveau le plus bas (test triangle par triangle), on se contente de tester des blocs de polygones. En clair, il vaudra mieux éliminer 100 000 polygones en 0.1 milliseconde, que 109 354 en 3 millisecondes.

Le backface culling est l'élimination des faces qui « tournent le dos » à la caméra et que l'on ne voit donc pas.

Le principe est simple : on calcule d'une part le vecteur entre la position de la caméra et le centre du polygone à tester, et d'autre part le vecteur normal à ce même polygone. Si leur produit scalaire est positif alors cela signifie que le triangle est orienté dans le même sens que la vue (il nous tourne le dos), et qu'il peut donc être éliminé du rendu.

Il s'agit d'un type de culling que l'on peut appliquer dans n'importe quelle situation, pour peu qu'on ait une vue en perspective et des polygones à afficher.
Il est cependant de moins en moins utilisé : d'une part il nécessite un test triangle par triangle (très lent), et d'autre part il est effectué par n'importe quel hardware de manière bien plus rapide. Tout ce que vous économiserez en l'implémentant vous-même, c'est l'étape « transformation et éclairage » (voir https://jeux.developpez.com/faq/3d/?page=definitions#DEFINITIONS_pipeline) ; vu la rapidité avec laquelle les cartes graphiques actuelles expédient cette étape, le gain est plus que douteux.
Vous pouvez donc très certainement oublier le backface culling pour le moment, et vous attarder sur un type de culling plus poussé et plus efficace.

L'occlusion culling est la technique consistant à éliminer du rendu les polygones ou objets cachés par d'autres, et donc invisibles à l'écran.

De nombreux algorithmes existent pour effectuer de l'occlusion que l'on peut principalement classer en trois catégories :

• les techniques basées sur l'image ;
• les techniques basées sur la géométrie ;
• les techniques de précalcul de visibilité.

Les techniques basées sur l'image
Le principe est de déterminer quels éléments sont cachés par un test de pixel. En général, on effectue un rendu des occluders de la scène dans une surface, puis on teste les rendus des boîtes englobantes des autres objets sur cette surface pour déterminer si oui ou non ils doivent être affichés.
Les techniques les plus courantes sont les hierarchical Z-buffers (HZB), ainsi que les hierarchical occlusion maps (HOM).
Depuis quelque temps, un test d'occlusion a été intégré directement au hardware et aux API 3D (OpenGL 1.5 et DirectX 9) : l'occlusion query. Cela permet de récupérer, en général de manière asynchrone, le nombre de pixels qui ont passé le test de Z-buffer, et qui seront donc visibles. En comparant ce nombre avec 0, on peut très simplement déterminer si un objet va être caché ou non. À noter que l'utilisation de cette fonctionnalité n'est généralement pas adaptée aux rendus volumineux, cela implique trop d'allers-retours entre le GPU et le CPU et cela casse par la même occasion le parallélisme.

Les techniques basées sur la géométrie
Elles sont plus rares, car soumises à plus de problèmes que l'approche précédente (imprécision des calculs en flottants, difficulté de fusionner plusieurs occluders). En général, ces algorithmes sont proche des shadow volumes, en cela qu'ils extrudent un volume à partir d'un certain point de vue. On peut notamment citer la méthode des solid occluders, ou des shadow frusta.

Les techniques de précalcul de visibilité
La famille d'algorithmes qui correspond à cette approche est principalement ce que l'on appelle les portails, couplés ou non à des arbres BSP (voir https://jeux.developpez.com/faq/3d/?page=partitionnement#PARTITIONNEMENT_choix). Cela consiste à découper la scène en secteurs reliés par des zones minces : les portails. Puis pour chaque secteur, on définit par un précalcul quels autres secteurs seront visibles selon un certain point de vue. La construction des secteurs et des portails est généralement effectuée par les artistes, mais elle peut aussi être automatisée.
On trouve également d'autres techniques un peu plus évoluées, telles que la méthode des projections étendues.
Ces techniques peuvent être très efficaces, mais ne peuvent gérer efficacement les éléments dynamiques. À réserver donc à certains environnements (par exemple les intérieurs).

Par-dessus toutes ces techniques, on peut également trouver tout un tas d'optimisations plus ou moins intéressantes :

• Directional discretized occluders, qui simplifie les occluders par une succession de plans obtenus via l'utilisation d'un octree ;
• Virtual occluders, qui consiste à fusionner plusieurs petits occluders en de plus grosses représentations ;
• Occupancy maps, qui éliminent des requêtes d'occlusion inutiles ;
• Adaptive hierarchical occlusion culling algorithm, qui permet d'organiser les tests et la recherche d'occluders.

Quelle que soit la technique utilisée, l'occlusion culling est généralement plutôt coûteux en termes de performances, mais pour certains types de scènes avec de forts taux d'occlusion, il peut se révéler d'un gain impressionnant.

Le frustum culling est la technique par laquelle on va éliminer du rendu les polygones ou objets se trouvant en dehors du champ de vision (frustum).

En général, le frustum culling s'appuie sur une structure de partitionnement de l'espace (voir https://jeux.developpez.com/faq/3d/?page=partitionnement#PARTITIONNEMENT_def). On découpe au préalable la scène selon l'une de ces structures, puis, pendant le rendu, on peut déterminer avec plus ou moins de précision quels morceaux de la scène seront dans le champ de vision ou non, notamment avec l'un des tests d'intersection impliquant le frustum (voir https://jeux.developpez.com/faq/3d/?page=intersections#INTERSECTIONS_def).

Le frustum culling est applicable à peu près partout, d'autant plus que l'éventail des structures de partitionnement permet de couvrir la plupart des cas de figure (intérieurs, extérieurs, 2D…). Ne vous en privez donc pas !

Le contribution culling part d'un principe extrêmement simple : si un objet apparaît de manière minuscule à l'écran (très certainement parce qu'il se trouve trop loin), alors on peut tout aussi bien se passer de l'afficher sans que cela altère trop la scène.

En pratique, on effectue la projection en 2D du modèle (ou plutôt de son volume englobant, c'est nettement plus rapide) et on compte le nombre de pixels qu'il utiliserait à l'écran ; si ce nombre est très faible, alors on n'affiche pas le modèle.

Le contribution culling est plutôt anecdotique comparé aux autres algorithmes de culling tels que frustum et occlusion culling, mais il peut parfois se révéler très pratique dans certaines situations, ne l'oubliez donc pas !