L'ambient occlusion

Laurent Gomila

Ce tutoriel présente une technique simple et efficace pour améliorer le réalisme de vos scènes 3D, en leur ajoutant des ombres douces « gratuites » : l'ambient occlusion.

- Titre : L'ambient occlusion

- Auteur : Laurent Gomila

- Parution : 24 avril 2006

- Mise à jour : 27 novembre 2019

- Licence : 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 ® 2006 Laurent Gomila. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Introduction

- II. Principes de l'ambient occlusion

- II-A. Idée générale

- II-B. L'algorithme

- II-C. Optimisations

- II-D. L'algorithme multipasse

- II-E. La « bent normal »

- III. Accélération des calculs à l'aide d'un octree

- III-A. Détail de l'octree

- III-B. Résultats

- IV. Conclusion

- V. Références

- VI. Téléchargements

I - Introduction

Avec la montée en puissance des cartes graphiques actuelles et la liberté offerte par les nouvelles versions de shaders, on voit naître de plus en plus de techniques « compliquées » permettant d'améliorer le réalisme des scènes 3D.

La technique de l'ambient occlusion est en marge de cet étalage de puissance, puisqu'elle ne fait qu'utiliser la bonne vieille couleur diffuse des sommets (vertex color), et de surcroît ne nécessite qu'un précalcul. N'oubliez pas que, comme son nom l'indique, cette technique calcule une couleur ambiante.
À noter que des techniques existent pour réaliser cette technique en temps réel, mais nous ne nous y intéresserons pas ici, l'intérêt étant déjà plus limité.

Nous détaillerons donc le principe de cette technique, très simple à mettre en œuvre, puis nous verrons comment accélérer les calculs avec la mise en place d'une structure de partitionnement, un octree.

II - Principes de l'ambient occlusion

II-A - Idée générale

L'ambient occlusion part d'une idée simple : l'ombrage en un point est fonction de la géométrie voisine. Par exemple, l'intérieur d'un tube ne sera jamais très éclairé, quels que soient le nombre ou le type de lumières présentes à l'extérieur du tube.

Ainsi on peut mettre sur pied un algorithme qui va calculer un facteur d'occlusion (et donc un ombrage) en chaque point de la scène, sans avoir besoin de connaître l'éclairage appliqué à celle-ci. D'où la possibilité de le précalculer une fois pour toutes.

Bien entendu les résultats ne seront pas toujours physiquement exacts, mais cela va ajouter énormément de réalisme à la scène, et tout cela sans coûter un seul centime à l'exécution.

À gauche : sans ambient occlusion - à droite : avec ambient occlusion. Notez l'ajout réaliste d'ombre dans les yeux ou la bouche par exemple, là où la lumière n'est censée que peu éclairer

II-B - L'algorithme

La première idée qui viendrait à l'esprit pour calculer l'occlusion en un point, et qui est celle utilisée par la plupart des logiciels de modélisation 3D, serait de lancer un nombre suffisant de rayons partant de ce point à travers la scène, et de déduire l'occlusion en faisant le rapport du nombre de rayons interceptés par le nombre de rayons lancés.
Cependant, bien que pouvant bénéficier d'une structure de partitionnement pour accélérer les calculs, cette méthode nécessite beaucoup de rayons pour obtenir des résultats corrects. De plus, elle est moins adaptée que la méthode que nous allons étudier pour le temps réel.

La méthode employée est plus proche des techniques de radiosité. Plutôt que de lancer des rayons et de calculer pour chacun les intersections avec l'ensemble de la scène, on va calculer pour chaque sommet la contribution à l'occlusion du point courant. De ce fait, on pourra associer à chaque sommet de la scène un disque, disque qui sera défini par un centre (la position du sommet), une orientation (la normale du sommet), et une aire (dont nous allons voir la formule).

Les sommets de la scène définissent des disques (image tirée du livre GPU Gems 2, chapitre disponible en ligne)

L'aire du disque associé à un sommet est calculée par la moyenne des aires des triangles qu'il partage.
La formule utilisée ici pour déterminer l'aire d'un triangle est la formule de Heron :

Avec a, b et c les longueurs des trois côtés, et s le demi-périmètre du triangle :

Une fois les disques calculés pour chaque sommet de la scène, l'algorithme est relativement simple :

Pour chaque sommet Receveur de la scène
Receveur.Occlusion = 0
Pour chaque sommet Emetteur
Receveur.Occlusion = Receveur.Occlusion + FormFactor(Receveur, Emetteur)
Fin pour
Receveur.Occlusion = Clamp(Receveur.Occlusion)
Fin pour

Comme vous le voyez, l'occlusion en un point n'est que la somme des contributions de chaque autre sommet (toujours modélisés par leur disque associé).

La contribution d'un point à un autre est déterminée par ce que l'on appelle la méthode des form-factors. L'équation correspondante est fonction de l'aire du disque émetteur, ainsi que de l'orientation du disque émetteur et du disque receveur.

Voici l'équation utilisée :

A est l'aire du disque émetteur.
cosθE est le cosinus de l'angle entre la normale de l'émetteur et le vecteur reliant les centres des deux disques.
cosθR est le cosinus de l'angle entre la normale du receveur et le vecteur reliant les centres des deux disques.
Ces deux cosinus sont calculés simplement par un produit scalaire entre les deux vecteurs en question.

À noter que l'on pourra trouver d'autres formules qui fonctionnent tout aussi bien, ne vous étonnez donc pas si vous en croisez des différentes lors de vos éventuelles lectures. L'important est que la formule utilisée soit fonction de l'orientation relative des deux éléments, ainsi que de l'aire de l'émetteur.

Notre fonction FormFactor peut donc s'écrire ainsi :

Fonction FormFactor(Receveur, Emetteur)
RcvToEmt = Emetteur.Position - Receveur.Position
Distance = Norme(RcvToEmt)
Normalise(RcvToEmt)
cosE = ProdScalaire(RcvToEmt, Emetteur.Normale)
cosR = ProdScalaire(RcvToEmt, Receveur.Normale)

renvoyer cosE * cosR * Emetteur.Aire / (Pi * Distance * Distance * Emetteur.Aire)
Fin fonction

Une fois la contribution de chaque disque ajoutée à l'occlusion d'un point, il ne faut pas oublier de ramener cette valeur entre 0 et 1. Cela peut être fait avec une fonction exponentielle par exemple :

Fonction Clamp(Occlusion)
NouvelleOcclusion = exp(-Occlusion)
Si NouvelleOcclusion < 0
NouvelleOcclusion = 0
Fin si
Si NouvelleOcclusion > 1
NouvelleOcclusion = 1
Fin si

renvoyer NouvelleOcclusion
Fin fonction

Finalement, la couleur ambiante d'un sommet sera le niveau de gris correspondant à la valeur de l'occlusion à la fin de l'algorithme.

II-C - Optimisations

Souvenez-vous de ce que nous disons en début d'article : l'ambient occlusion part de l'idée simple que l'ombrage d'un point dépend principalement de la géométrie voisine. Nous n'avons visiblement pas encore exploité ce point, voyons donc comment modifier notre algorithme pour en tenir compte. Puisque nous calculons déjà la distance entre deux éléments, il suffit d'ajouter un test sur cette distance : si elle est trop élevée, on passe à l'élément suivant. Plutôt que de prendre une distance fixe, on choisit habituellement une valeur proportionnelle à l'aire de l'émetteur, ce qui permet de ne pas éliminer les très gros éléments, qui bien qu'étant lointains, vont tout de même contribuer de manière non négligeable à l'occlusion. Il est conseillé de choisir comme valeur entre 10 et 100 fois l'aire de l'émetteur, mais rien ne vous empêche de réaliser des tests pour trouver la valeur qui donne les meilleurs résultats de performance/aspect visuel.

Une autre observation que nous pouvons faire, et dont nous ne tenons pas compte dans notre algorithme, est que les éléments se trouvant « dans le dos » d'un sommet ne vont logiquement pas contribuer à son occlusion ; nous pourrons donc éliminer ceux-ci des calculs. Mathématiquement parlant, un élément émetteur se trouve dans le dos d'un élément receveur si celui-ci n'est pas contenu dans l'hémisphère orienté par la normale du receveur. Cela se fait également assez rapidement : nous avons déjà calculé la valeur de CosθR dans l'algorithme, il suffit donc de regarder si cette valeur est négative afin de savoir si l'élément émetteur ne se trouve pas dans le fameux hémisphère, et l'éliminer le cas échéant.

Enfin, une dernière optimisation un peu plus personnelle : on peut éliminer des calculs les éléments émetteurs qui ne font pas face au receveur. Imaginez un mur par exemple, et notre élément receveur derrière ce mur : notre algorithme va ajouter une contribution pour la face du mur dirigée vers le receveur, et une autre pour la face opposée. En toute logique il n'en faudrait qu'une, c'est ce que cette condition va permettre de corriger. Après quelques tests les résultats visuels semblent d'ailleurs bien meilleurs. Là encore, un simple test du signe de CosθE suffira à déterminer si oui ou non notre élément émetteur fait face au receveur, afin de l'éliminer si besoin.

Voici donc à quoi ressemble maintenant notre fonction de calcul d'occlusion entre deux éléments :

Fonction FormFactor(Receveur, Emetteur)
RcvToEmt = Emetteur.Position - Receveur.Position
Distance = Norme(RcvToEmt)

////// Ajout du test de distance maximale //////
Si (Distance > 100 * Emetteur.Aire)
renvoyer 0

Normalise(RcvToEmt)
cosE = ProdScalaire(-RcvToEmt, Emetteur.Normale)
cosR = ProdScalaire( RcvToEmt, Receveur.Normale)

////// Ajout des tests de cosinus //////
Si (cosE < 0) ou (cosR < 0)
renvoyer 0

renvoyer cosE * cosR * Emetteur.Aire / (Pi * Distance * Distance * Emetteur.Aire)
Fin fonction

II-D - L'algorithme multipasse

Si vous pratiquez des tests suffisamment poussés, vous pourrez peut-être remarquer que certaines zones sont obscurcies plus qu'elles ne devraient l'être. Ceci est dû au fait qu'on ne tient pas compte de l'occlusion d'un élément pour calculer sa contribution. En effet, imaginez un point à l'intérieur d'une boîte fermée, et un point à l'extérieur : il n'y a aucune chance que le point à l'intérieur vienne obscurcir le point à l'extérieur. Cependant, notre algorithme n'en tient pas compte, ce qui va donc produire des zones trop ombrées.

Afin de tenir compte de ce phénomène et le corriger, il suffit d'effectuer plusieurs passes de l'algorithme, en multipliant la contribution d'un élément par son facteur d'occlusion, calculé à la passe précédente. Ainsi, un élément très « occludé » participera beaucoup moins à l'occlusion des autres points.

Voici l'algorithme modifié :

Pour i = 0 à NbPasses
Pour chaque sommet Receveur de la scène
Receveur.Occlusion = 0
Pour chaque sommet Emetteur
Receveur.Occlusion = Receveur.Occlusion + FormFactor(Receveur, Emetteur) * Emetteur.OcclusionPrecedente
Fin pour
Receveur.Occlusion = Clamp(Receveur.Occlusion)
Fin pour

Pour chaque sommet S de la scène
S.OcclusionPrecedente = S.Occlusion
Fin pour
Fin pour

De gauche à droite et de haut en bas : 1 passe, 2 passes, 4 passes et 50 passes

Comme vous le voyez, à chaque passe l'algorithme retire une certaine quantité d'ombrage « superflu ». En général, deux passes sont suffisantes pour arriver à un résultat visuel satisfaisant.

II-E - La « bent normal »

Le calcul d'occlusion nous permet d'obtenir l'ombrage en un point, ce qui est le but premier, mais nous pouvons également en déduire autre chose de très utile : ce que l'on appelle la « bent normal ». Il s'agit en fait d'une normale modifiée, qui représente la direction vers laquelle un point est le plus éclairé. On l'obtient facilement en faisant la moyenne des directions vers les autres éléments (vecteur RcvToEmt dans notre algorithme), pondérées par le facteur d'occlusion associé à l'élément.

À gauche : normale classique - à droite : bent normal

Une telle normale est utilisée entre autres pour l'environnement mapping, et donne des résultats plus intéressants et réalistes comparés à la normale classique.

III - Accélération des calculs à l'aide d'un octree

Bien que n'étant pas exécuté en temps réel, le calcul d'ambient occlusion peut vite devenir très long pour des scènes de plusieurs centaines de milliers de polygones. Ainsi nous allons tenter de l'accélérer en utilisant une structure de partitionnement, en l'occurrence ici un octree. Pour ceux qui ignoreraient ce que sont les structures de partitionnement de l'espace ou les octrees, jetez un œil à la FAQ 3D.

III-A - Détail de l'octree

Nous allons construire notre octree de manière à ce que les feuilles contiennent un tableau d'éléments. Notez que nous n'aurons pas à gérer le gros problème des octrees, à savoir lorsqu'un élément se trouve dans plusieurs nœuds. En effet, nos éléments ne sont que des points (et non des triangles comme habituellement), donc il n'y a aucun risque qu'ils figurent dans plusieurs nœuds à la fois.

On peut imaginer plusieurs conditions d'arrêts pour la construction de l'octree, ici nous fixerons un nombre d'éléments minimum. Là encore la valeur à choisir n'est pas fixe, et mieux vaudra faire des tests pour trouver la valeur optimale. Dans les exemples qui suivent, cette valeur a été fixée à 100 (c.-à-d. qu'un nœud qui contient moins de 100 éléments ne sera pas subdivisé).

Afin de tirer parti de la structure de l'octree, il faut un moyen d'éliminer rapidement des nœuds. Nous pouvons pour cela reprendre les deux premières conditions décrites dans le paragraphe 2.3 : nous pouvons éliminer les nœuds trop distants du point examiné, tout comme ceux qui se trouveront dans son dos.

Le calcul de la distance entre un nœud et un point n'est pas trivial, nous allons donc nous autoriser une approximation et prendre la distance entre un point et la sphère englobante du nœud. Ainsi le calcul devient très simple :

Vector3 PointToCenter = Sphere.Centre - Point.Position
Distance = PointToCenter.Norme - Sphere.Rayon

Pour ce qui est de l'élimination des nœuds ne faisant pas partie de l'hémisphère orienté par la normale du receveur, nous procédons de la même manière que précédemment (test du signe du cosinus), il faut simplement le faire pour les 8 sommets de la boîte englobante du nœud. Si un seul de ces 8 sommets se trouve dans l'hémisphère, alors nous ne pouvons pas éliminer le nœud.

bool Quit = true
Pour i = 0 à 8
Vector3 PointToSommet = Sommet[i] - Point.Position
Si (ProduitScalaire(PointToSommet, Point.Normale) > 0)
Quit = false
Fin pour
Fin pour

Si (Quit = true)
renvoyer 0

Avec ces deux tests, nous sommes maintenant capables d'éliminer très rapidement des calculs de grosses parties de la scène.

III-B - Résultats

Voyons à présent ce que nous avons gagné en utilisant un octree.

Les modèles utilisés pour les tests sont tirés du SDK DirectX 9 :

Head_Big_Ears.x
-> 17 575 sommets
-> 34 560 faces

scanner.x
-> 276 420 sommets
-> 92 140 faces

Modèle

Temps sans octree

Temps avec octree

Head_Big_Ears

13 sec

3 sec

Scanner

2 h 08 min

5 min 20 sec

Le gain est évident, on peut voir à quel point l'algorithme en force brute est inefficace par rapport à une approche structurée.

IV - Conclusion

L'ambient occlusion est une technique sympathique qui permet d'ajouter beaucoup de réalisme aux scènes 3D, accessible à tous les programmes et à toutes configurations. N'hésitez donc pas à l'utiliser pour vos éléments statiques. De plus ce n'est qu'une couleur ambiante, qui peut se marier sans souci à d'autres techniques d'éclairage temps réel plus évoluées.

Concernant l'aspect temps réel, l'intérêt est à voir, mais apparemment les recherches s'orientent dans ce sens, à creuser donc si vous souhaitez aller plus loin dans l'exploitation de la technique.

Enfin, si vous lisez l'article tiré de GPU Gems 2, vous verrez que l'ambient occlusion ne se limite pas à calculer l'ombrage, mais peut être utilisé également pour des calculs d'illumination globale plus poussés, tenant compte des reflets induits par la couleur diffuse des objets par exemple ; un peu à la manière des calculs de radiosité.

V - Références

Dynamic ambient occlusion and indirect lighting - GPU Gems 2 chapitre 14, Michael Bunnell.
Un article simple et complet avec de jolies images pour bien comprendre l'ambient occlusion. L'attention est portée sur la réalisation en temps réel (et donc par le GPU) de ces calculs.

Accelerated ambient occlusion using spatial subdivision structures, Chris Wassenius.
Discussion sur l'ambient occlusion et l'accélération des calculs par l'utilisation d'un octree.

Ambient occlusion fields, Janne Kontkannen et Samuli Laine.
Une application intéressante de l'ambient occlusion en temps réel.

Ambient occlusion - wikipedia
Une définition simple et illustrée, ainsi que d'autres liens pour approfondir vos recherches.

VI - Téléchargements

Le code source de l'application accompagnant ce tutoriel, ainsi que l'exécutable et un modèle, sont fournis ci-dessous. L'application a été développée en C++ à l'aide de Visual C++ 2005, et utilise DirectX 9 pour le rendu.

Télécharger les sources de cet article (zip, 991 Ko)

Si vous cherchez le fichier d3dx9_29.dll : le voici (1.02 Mo)

Une version PDF de cet article est disponible : Télécharger (123 Ko)

Si vous avez des suggestions, remarques, critiques, si vous avez remarqué une erreur, ou bien si vous souhaitez des informations complémentaires, n'hésitez pas à me contacter !