L'ambient occlusion

Ce tutoriel présent 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.

Article lu   fois.

L'auteur

Site personnel

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

1. 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.
A 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 oeuvre, puis nous verrons comment accélérer les calculs avec la mise en place d'une structure de partitionnement, un octree.

2. Principes de l'ambient occlusion

2.1. 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é, quelque soit le nombre ou le type de lumières présents à 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 toute.

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'execution.

A gauche : sans ambient occlusion ; à droite : avec ambient occlusion
A 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

2.2. 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
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 :

Formule de Heron

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

Demi-perimetre du triangle

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

 
Sélectionnez

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 :

Equation des form factors

A est l'aire du disque émetteur.
cosE est le cosinus de l'angle entre la normale de l'émetteur et le vecteur reliant les centres des deux disques.
cosR 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.

Schématisation de la formule des form-factors

A 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 :

 
Sélectionnez

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 :

 
Sélectionnez

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.

2.3. 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éometrie 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ée par la normale du receveur. Cela se fait également assez rapidement : nous avons déjà calculé la valeur de CosR 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 la fameuse 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 CosE suffira à déterminer si oui ou non notre élement é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 :

 
Sélectionnez

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

2.4. L'algorithme multi-passes

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é :

 
Sélectionnez

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
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.

2.5. 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'élement.

A gauche : normale classique - à droite : bent normal
A gauche : normale classique - à droite : bent normal

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

3. 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'occurence ici un octree. Pour ceux qui ignoreraient ce que sont les structures de partitionnement de l'espace ou les octrees, jetez un oeil à la FAQ 3D.

3.1. 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'auront pas à gérer le gros problème des octrees, à savoir lorsque qu'un élément se trouve dans plusieurs noeuds. 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 noeuds à 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 noeud qui contient moins de 100 éléments ne sera pas subdivisé).

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

Le calcul de la distance entre un noeud 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 noeud. Ainsi le calcul devient très simple :

 
Sélectionnez

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

Pour ce qui est de l'élimination des noeuds ne faisant pas partie de l'hémisphère orientée 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 noeud. Si un seul de ces 8 sommets se trouve dans l'hémisphère, alors nous ne pouvons pas éliminer le noeud.

 
Sélectionnez

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 capable d'éliminer très rapidement des calculs de grosses parties de la scène.

3.2. 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 :

 
Sélectionnez

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.

4. 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é.

5. Références

Image non disponibleDynamic 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.

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

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

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

6. Téléchargements

Le code source de l'application accompagnant ce tutoriel, ainsi que l'executable 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)Image non disponible

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 !

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

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.