L'ambient occlusion
Date de publication : 24/04/2006 , Date de mise à jour : 24/04/2006
Par
Laurent Gomila (Autres articles)
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.
1. Introduction
2. Principes de l'ambient occlusion
2.1. Idée générale
2.2. L'algorithme
2.3. Optimisations
2.4. L'algorithme multi-passes
2.5. La "bent normal"
3. Accélération des calculs à l'aide d'un octree
3.1. Détail de l'octree
3.2. Résultats
4. Conclusion
5. Références
6. Téléchargements
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. 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 (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.
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.
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 :
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.
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 :
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é :
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.
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
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 :
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.
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 :
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
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.
Ambient occlusion fields,
Janne Kontkannen et Samuli Laine.
Une application intéressante de l'ambient occlusion en temps réel.
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.
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 !
 
|
