L'ambient occlusion

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.

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

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.

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

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

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.

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.

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.

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.

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

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