IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Moteurs 3D Discussion :

Culling d'ombres : algo


Sujet :

Moteurs 3D

  1. #1
    Membre actif
    Profil pro
    Inscrit en
    Février 2006
    Messages
    396
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Février 2006
    Messages : 396
    Points : 230
    Points
    230
    Par défaut 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...

  2. #2
    Membre expérimenté

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2006
    Messages
    450
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Avril 2006
    Messages : 450
    Points : 1 630
    Points
    1 630
    Par défaut
    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 .
    Je ne réponds à aucune question par MP, posez vos questions sur le forum adéquat.
    Profils : G+ - LinkedIn

  3. #3
    Rédacteur
    Avatar de Laurent Gomila
    Profil pro
    Développeur informatique
    Inscrit en
    Avril 2003
    Messages
    10 651
    Détails du profil
    Informations personnelles :
    Âge : 39
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2003
    Messages : 10 651
    Points : 15 920
    Points
    15 920
    Par défaut
    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.

  4. #4
    Membre actif
    Profil pro
    Inscrit en
    Février 2006
    Messages
    396
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Février 2006
    Messages : 396
    Points : 230
    Points
    230
    Par défaut
    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.

  5. #5
    Rédacteur
    Avatar de Laurent Gomila
    Profil pro
    Développeur informatique
    Inscrit en
    Avril 2003
    Messages
    10 651
    Détails du profil
    Informations personnelles :
    Âge : 39
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Avril 2003
    Messages : 10 651
    Points : 15 920
    Points
    15 920
    Par défaut
    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.

  6. #6
    Membre actif
    Profil pro
    Inscrit en
    Février 2006
    Messages
    396
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Février 2006
    Messages : 396
    Points : 230
    Points
    230
    Par défaut
    Super, je regarde à ça, merci.

  7. #7
    Membre expérimenté

    Profil pro
    Programmeur
    Inscrit en
    Août 2002
    Messages
    1 091
    Détails du profil
    Informations personnelles :
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Programmeur

    Informations forums :
    Inscription : Août 2002
    Messages : 1 091
    Points : 1 679
    Points
    1 679
    Par défaut
    Citation Envoyé par zenux Voir le message
    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

    Mon site web | Mon blog | Mes photos | Groupe USA
    > BONJOUR, JE SUIS NOUVEAU SUR CE FORUM
    > presse la touche caps lock, stp
    > OH.. MERCI C EST BEAUCOUP PLUS FACILE COMME CA

  8. #8
    Membre actif
    Profil pro
    Inscrit en
    Février 2006
    Messages
    396
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Février 2006
    Messages : 396
    Points : 230
    Points
    230
    Par défaut
    Citation Envoyé par LeGreg Voir le message
    - 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 Personnellement les choses incorrecte, c'est pas ce que je préfère.

    Citation Envoyé par LeGreg Voir le message
    - 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 Voir le message
    - ombres pré-calculées. .....
    Le pré-calculées c'est pas vraiment pour moi

  9. #9
    Membre expérimenté

    Profil pro
    Programmeur
    Inscrit en
    Août 2002
    Messages
    1 091
    Détails du profil
    Informations personnelles :
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Programmeur

    Informations forums :
    Inscription : Août 2002
    Messages : 1 091
    Points : 1 679
    Points
    1 679
    Par défaut
    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..

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

    Le pré-calculées c'est pas vraiment pour moi
    Tout dépend jusqu'où tu pousses le professionalisme..

    Mon site web | Mon blog | Mes photos | Groupe USA
    > BONJOUR, JE SUIS NOUVEAU SUR CE FORUM
    > presse la touche caps lock, stp
    > OH.. MERCI C EST BEAUCOUP PLUS FACILE COMME CA

  10. #10
    Membre actif
    Profil pro
    Inscrit en
    Février 2006
    Messages
    396
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Février 2006
    Messages : 396
    Points : 230
    Points
    230
    Par défaut
    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.

Discussions similaires

  1. [HLSL XNA]aide pour algo d'ombres temps réel
    Par Acropole dans le forum XNA/Monogame
    Réponses: 3
    Dernier message: 31/07/2008, 16h49
  2. cherche algos Delphi pour : Huffman, R.S.A, D.E.S.
    Par X-Delphi dans le forum Débuter
    Réponses: 3
    Dernier message: 24/08/2002, 19h51
  3. Cherche l'algo crc 16 bits
    Par icepower dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 21/08/2002, 14h27
  4. Algo de calcul de FFT
    Par djlex03 dans le forum Traitement du signal
    Réponses: 15
    Dernier message: 02/08/2002, 18h45
  5. Recherche algo tree
    Par Anonymous dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 24/05/2002, 14h44

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo