Developpez.com

Plus de 2 000 forums
et jusqu'à 5 000 nouveaux messages par jour

FAQ Programmation 3DConsultez toutes les FAQ

Nombre d'auteurs : 7, nombre de questions : 67, dernière mise à jour : 20 mai 2017 

 
OuvrirSommaireRendu 2D / 3DTechniques et optimisationsCulling (élimination des faces)

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 :

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.

Créé le 22 janvier 2006  par Laurent Gomila

Lien : Geometry culling in 3D engines

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 http://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.

Créé le 22 janvier 2006  par Laurent Gomila

Lien : 3D Backface Culling

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 http://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 :

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.

Mis à jour le 12 mai 2006  par Laurent Gomila

Lien : Visibility culling
Lien : Point-visibility in computer games
Lien : Occlusion culling algorithms
Lien : SurRender Umbra : a visibility determination framework for dynamic environments
Lien : Occlusion culling using DirectX 9

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 http://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 http://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 !

Créé le 22 janvier 2006  par Laurent Gomila

Lien : Optimized view frustum culling algorithms for bounding boxes

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 !

Créé le 22 janvier 2006  par Laurent Gomila
  

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2009-2017 Developpez Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.