Culling d'ombres : algo

Bonjour,

J'ai fait un petit moteur 3d qui utilise les octree avec du frustum culling pour ne pas envoyer les objets 3d à la carte graphique si il ne sont pas visible à l'écran.

Le problème c'est lors de la phase d'ombrage : un objet peut-être en dehors du frustum tout en ayant sont ombre dans le frustum.

Ma question : comment savoir si l'ombre d'un objet qui se trouve en dehors du frustum sera visible ? Je cherche principalement un algorithme performant.

J'ai déjà trouvé une solution qui à l'air assez performante (quoi que...faut voir) :
- créer une enveloppe convexe avec le frustum et la light et si l'octree se trouve dans cette enveloppe convexe alors l'ombre des objets contenu dans l'octree sera sûrement visible.

L'idée est bonne mais pour construire une enveloppe convexe (quick hull), c'est pas si simple, Y a-t-il d'autre solution ?

Merci d'avance...

J'ai personnellement implémenté que l'algo du shadow mapping et je sais qu'il fallait faire un rendu de la scène du point de vue de la light donc ce que tu dois savoir :

Est-ce que le frustum de la light intersecte le frustum de la caméra si oui faire un calcul d'ombre portée générée par cette light sinon zapper complet le calcul de l'ombre portée.

Pendant le calcul de la light ce qui nous intéresse ce n'est que les objets qui sont dans le frustum de la light et pas forcément ceux qui sont dans le frustum de la caméra donc n'"afficher" que les objets dans le frustum de la light. Tu obtiens ton rendu en profondeur et il suffit de projeter ce rendu pour obtenir les ombres portées (algo du shadow mapping).

Sinon pour les ombres portées volumiques je ne sais pas si elles sont adaptées à ce que je dis et je ne sais pas non plus si ce que je dis est vraiment très performant. C'est juste pour donner une idée comme ça :D.

Un quick hull ce n'est pas forcément simple, maintenant un quick hull à 9 points dont 8 sont déjà une sous-enveloppe convexe, ça peut l'être beaucoup plus.

A part ça je pense que c'est la meilleure méthode, tu peux faire des approximations plus rapides mais il y aura toujours des cas non gérés et au final ce sera plus chiant à rattraper.

TanEK : merci pour ta réponse mais j'aurais du préciser que j'utilise des shadow volume...donc ta solution ne me semble pas vraiment adaptée.

Laurent : oui j'y ai pensé aussi qu'il y avait peut-être moyen de simplifié le quick hull dans cette situation. Je vais regarder à tout ça, merci.

Regarde du côté des algorithmes de quick hull incrémentaux, comme ça tu pourras construire ton enveloppe en une itération avec ton frustum + la position de la lumière.

Super, je regarde à ça, merci.

Citation:

---

Envoyé par zenux

Ma question : comment savoir si l'ombre d'un objet qui se trouve en dehors du frustum sera visible ? Je cherche principalement un algorithme performant.

---

Tout dépend des algorithmes que tu utilises et du type de jeu que tu prévois de faire.

Quelques pistes cependant utilisées dans plusieurs jeux commerciaux :

- solution la plus simple est de ne générer des ombres que pour des objets visibles par la caméra. Éventuellement avec un frustum légèrement plus inclusif ou par hystérésis pour augmenter la qualité en réduisant le clipping. Pour rappel, hystérésis = considération de l'état de la frame précédente dans la frame courante ce qui évite des cas pathologiques ou l'ombre oscille entre l'état visible/pas visible une frame sur deux. Malgré son apparente incohérence cette méthode est utilisée dans quelques jeux, souvent en conjonction avec d'autres techniques pour limiter les artefacts (jeux à la Command and conquer, mmorpgs comme Everquest II).

- Pour un jeu à environnement fermé, il est souvent possible de limiter l'influence de chaque lumière par atténuation (fall-off), ce qui fait que une fois sorti de la zone d'influence de la lumière il est possible de ne plus considérer tous les objets dans sa zone d'influence ce qui est une très grosse optimisation. Voir ce genre d'optimisation dans des jeux à la "Splinter cell" : si le cone d'illumination de la lumière (s'il s'agit d'un spot) n'intercepte pas le "frustum" alors il est inutile de tracer la shadow map correspondante. Pour savoir quels objets sont dans la shadow map il faut réitérer les calculs de visibilité pour le frustum du cone de lumière. La lumière omni sans attenuation est à bannir dans ce cas là bien entendu.

- ombres pré-calculées. On peut imaginer les light maps bien entendu, mais il est aussi possible d'avoir des ombres plus proche du rendu "stencil shadow volume" avec une découpe géométrique du terrain entre ombre et lumière. C'est particulièrement utile quand on ne peut pas avoir une zone d'influence limitée comme ci dessus. Et ce n'est vraiment possible que lorsque la lumière est statique (soleil à une heure fixe de la journée, torche qui ne peut pas être éteinte). Éventuellement la lumière peut même osciller entre éteint/allumé en l'absence d'autre mouvement. Des lumières pré-calculées sous formes "géometriques" ont été utilisées dans Doom III ou la démo Animusic de ATI (lors de la sortie de la radeon 9700). Ça ne peut pas être appliqué aux objets en mouvement qui eux doivent être ombrées de manière classique/dynamique mais avec moins de risques d'artefacts. Half life 2 par exemple va simplement affecter une valeur "éclairé/dans l'ombre" à chaque objet/personnage en mouvement en fonction d'une zone précalculée. Et il en retirera aussi un "vecteur d'éclairage" qui déterminera la direction de son ombre projetée. Le reste des ombres est préalculé dans une light map.

- Situation la pire : toute lumière du monde affecte tout objet qui peut projeter une ombre sur lui-meme et sur le monde entier et le tout de manière totalement dynamique. C'est la pire situation parce que le coût devient N*N*M (N = nombre d'objets, M = nombre de lumières). C'est un problème d'illumination globale qu'il est impossible d'optimiser quand tu as retiré toute spécificité au problème (pas de sphère d'influence des lumières, pas de limitation d'affichage des ombres aux objets proches, et pas de limitation de la self illumination). Il parait évident que c'est ce qu'il faut éviter, en mettant des contraintes de design sur le jeu.

LeGreg

Citation:

---

Envoyé par LeGreg

- solution la plus simple est de ne générer des ombres que pour des objets visibles par la caméra. Éventuellement avec un frustum légèrement plus inclusif ou par hystérésis pour augmenter la qualité en réduisant le clipping. Pour rappel, hystérésis = considération de l'état de la frame précédente dans la frame courante ce qui évite des cas pathologiques ou l'ombre oscille entre l'état visible/pas visible une frame sur deux. Malgré son apparente incohérence cette méthode est utilisée dans quelques jeux, souvent en conjonction avec d'autres techniques pour limiter les artefacts (jeux à la Command and conquer, mmorpgs comme Everquest II).

---

Ca c'est ce que j'ai fait quand j'avais présenté mon moteur 3d devant les profs lors de mon travail de fin d'étude :yaisse2: Personnellement les choses incorrecte, c'est pas ce que je préfère.

Citation:

---

Envoyé par LeGreg

- Pour un jeu à environnement fermé, il est souvent possible de limiter l'influence de chaque lumière par atténuation (fall-off), ce qui fait que une fois sorti de la zone d'influence de la lumière il est possible de ne plus considérer tous les objets dans sa zone d'influence ce qui est une très grosse optimisation. Voir ce genre d'optimisation dans des jeux à la "Splinter cell" : si le cone d'illumination de la lumière (s'il s'agit d'un spot) n'intercepte pas le "frustum" alors il est inutile de tracer la shadow map correspondante. Pour savoir quels objets sont dans la shadow map il faut réitérer les calculs de visibilité pour le frustum du cone de lumière. La lumière omni sans attenuation est à bannir dans ce cas là bien entendu.

---

J'ai déjà implémenté cette optimisation mais je trouve que l'influence d'une lumière et parfois très grande et donc cette optimisation ne suffit pas. Si une lumière n'éclaire qu'a 5% ça ne se voit pas comme ça à l'oeil nu mais si j'éteins cette lumière, on voit la différence. Faudrait peut-être que je me trouve une autre formule pour l'atténuation que la formule de base d'OpenGL : 1/(Kc + d*Kl + d*d*Kq).
J'ai pensé à une formule exponentiel : 1/(K^d), j'aurais donc un éclairage assez fort quand on se trouve proche de la lumière et si on s'éloigne, la taux de luminosité diminuerai rapidement, ce qui me permettrai d'avoir une plus petite zone d'influence.

Citation:

---

Envoyé par LeGreg

- ombres pré-calculées. .....

---

Le pré-calculées c'est pas vraiment pour moi :)

De toute façon les ombres et les lumières dynamiques c'est l'une des plus grosses sources de coûts et de casse-têtes divers et variés. Après les coûts ne seront pas les mêmes si tu as des stencil shadow volume (n * m * overdraw du volume), et shadow maps (n*m nombres d'objet dans le cone de la lumière), la qualité sera différente également.

Après tu n'abordes pas les choses de la même façon si tu fais un jeu vidéo ou un papier académique. Mais si tu fais un jeu, garantir que le jeu sera jouable quoi qu'il arrive nécessite quelques contraintes de design..

Citation:

---

J'ai déjà implémenté cette optimisation mais je trouve que l'influence d'une lumière et parfois très grande et donc cette optimisation ne suffit pas.

---

L'intéret de l'optimisation est justement que ta sphère (ou cone) d'influence n'est pas trop grande. Peut-etre qu'il faut subdiviser ton problème, ou revoir tes règles de design (pas de lumière omni qui éclaire toute la scène), ou continuer à optimiser le reste de ton moteur pour que la performance globale soit acceptable. (si tu utilises les stencil shadow volume pense à passer au shadow maps par ex, essaie de mesurer l'overdraw, le sample shadowvolume du DXSDK permet de visualiser l'overdraw et tu peux voir que c'est parfois assez dramatique).

Citation:

---

Le pré-calculées c'est pas vraiment pour moi

---

Tout dépend jusqu'où tu pousses le professionalisme..

Pour l'instant, je reste sur les shadow volume et c'est pas le nombre d'optimisation qui manque. J'ai pourtant beaucoup hésité entre les shadow volume et shadow map.

Si j'ai bien tout compris des gros désavantages :
shadow volume : pas facile d'obtenir de l'ombrage correcte avec des textures transparentes
shadow maps : très lent pour les lumières omni-directionnelles.

Je crois que le jeu Far cry utilise les shadow volume pour les lumières omni et pour le reste c'est des shadow maps.
Maintenant Crysis n'utilise plus que des shadow maps. Est-ce THE technique pour l'avenir ? J'en sais trop rien....

Je vais tenter d'obtenir une zone d'influence plus petite pour les lumières sans trop y perdre en qualité et je verrais bien si il est encore nécessaire d'utiliser la méthode de l'enveloppe convexe.