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

Développement 2D, 3D et Jeux Discussion :

Collision : lancer de rayon


Sujet :

Développement 2D, 3D et Jeux

  1. #1
    Membre actif Avatar de Nyarlathotep
    Profil pro
    Étudiant
    Inscrit en
    Juin 2005
    Messages
    174
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2005
    Messages : 174
    Points : 217
    Points
    217
    Par défaut Collision : lancer de rayon
    Voila, je travaille actuellement sur un moteur de jeu. Dans l'univers évoluent des Modeles MD2 dans une MAP.
    La map est uniquement constituée de triangles.
    J'ai vu que pour détecter les collisions on pouvait passer par un arbre BSP.
    Mais j'ai également vu que l'on pouvait utiliser le lancer de rayon.
    Pour moi, l'idéal serait d'utiliser les deux : partitionner l'espace et ensuite faire une detection précise.

    Sur internet, les tutoriaux sur le lancer de rayon ne sont pas très clairs et bien que je soit en maths spé (Terminale S), j'avoue que je ne pige pas grand chose: il serait bien venu que l'un d'entre vous, ô developpeurs émérites, puisse m'expliquer en détail cette technique, et comment l'appliquer à mon projet.

    Comment faire, donc ?

    Merci d'avance pour vos réponses.
    "That is not dead which can eternal lie
    And with strange aeons even death may die"

    The Call of Cthulhu

  2. #2
    Expert confirmé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Décembre 2003
    Messages
    3 549
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Décembre 2003
    Messages : 3 549
    Points : 4 625
    Points
    4 625
    Boost ftw

  3. #3
    Membre actif Avatar de Nyarlathotep
    Profil pro
    Étudiant
    Inscrit en
    Juin 2005
    Messages
    174
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2005
    Messages : 174
    Points : 217
    Points
    217
    Par défaut
    Merci, loufoque, mais j'avoue que c'est une réponse plutôt vague sur le sujet. Mais effectivement je ne l'avait pas vue.

    Il me faudrait des informations plus précises sur ce sujet, comme par exemple, comment à partir d'une liste de points, pouvoir déterminer si un triangle est en intersection avec un autre (un plan, c'est facile, mais un triangle ?)

    En plus, je ne souhaite pas utiliser de moteur physique pour la simple et bonne raison que mon but actuel est de réaliser le mien... Donc pas la peine de me parler de Newton Game dynamics ou de Bullet, ...

    Ceci dit, je pourrais me contenter d'effectuer un partitionement de l'espace, mais les collisions ne seraient pas précises. Dans quelle mesure puis-je me contenter de boites englobantes non alignées sur les axes et autres algorithmes simples ?

    Dans mon jeu, si je tire un projectile, il doit suivre un rayon ( défini par un vecteur direction et une position initiale ), comment faire pour déterminer si le point ou se situe le projectile a traversé un polygone de l'environnement ?

    Voila, si vous avez bien observé, vous avez constaté que mon message ne comporte que des questions. Merci beaucoup de m'accorder un peu de temps et d'y apporter des formes de réponses.
    "That is not dead which can eternal lie
    And with strange aeons even death may die"

    The Call of Cthulhu

  4. #4
    Expert éminent sénior
    Avatar de Mat.M
    Profil pro
    Développeur informatique
    Inscrit en
    Novembre 2006
    Messages
    8 358
    Détails du profil
    Informations personnelles :
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Novembre 2006
    Messages : 8 358
    Points : 20 369
    Points
    20 369
    Par défaut
    Citation Envoyé par Nyarlathotep Voir le message
    Ceci dit, je pourrais me contenter d'effectuer un partitionement de l'espace, mais les collisions ne seraient pas précises. .
    Attention à la complexité algorithmique; plus tu descends dans la précision plus cela fait des calculs et sollicite des opérations du CPU..
    As-tu regardé autour de l'algo de Dijkstra ?

    Citation Envoyé par Nyarlathotep Voir le message
    J'ai vu que pour détecter les collisions on pouvait passer par un arbre BSP.
    Mais j'ai également vu que l'on pouvait utiliser le lancer de rayon.
    Qu'est-ce qui est bloquant alors ?
    Si tu utilises le lancer de rayon il faut convertir en coordonnées X et Y le projectile qui a un cap Theta et une vitesse v
    Citation Envoyé par Nyarlathotep Voir le message
    Dans mon jeu, si je tire un projectile, il doit suivre un rayon ( défini par un vecteur direction et une position initiale ), comment faire pour déterminer si le point ou se situe le projectile a traversé un polygone de l'environnement ?
    Mais dans le cas d'un projectile c'est simple ; comme je l'ai écris selon le X et Y du projectile , il faut regarder si à un instant t ces coordonnées X et Y sont confondues à un polygone..
    basiquement il faut balayer une liste de polygones et faire ce test.
    C'est l'explication grosso modo de Loufoque...
    mais pour faire plus simple il suffit par exemple de calculer la normale de ce polygone et la distance de cette normale avec le projectile..
    si elle est petite alors tu fais le test de collision..
    Sinon quelque chose de plus complexe c'est de faire des noeuds qui contient le "cout des distances" comme dans l'algo de Dijkstra.
    Regarde cette explication ( en anglais )
    http://www.devmaster.net/articles/pathfinding/
    Je suis en train de me cogner ce genre de problème mais pour le déplacement de personnages et unités pas pour un projectile
    une copie d'écran de ce que tu veux faire serait plus explicite
    Citation Envoyé par Nyarlathotep Voir le message
    Pour moi, l'idéal serait d'utiliser les deux : partitionner l'espace et ensuite faire une detection précise.
    Eh bien je ne comprends pas ; si tu as parcouru tous les noeuds de l'arbres que tu tombes sur une collision il suffit de balayer la zone selon un banal arc de cercle et voir si les coordonnées de l'arc de cercle appartiennent au triangle du terrain.

  5. #5
    Expert confirmé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Décembre 2003
    Messages
    3 549
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Décembre 2003
    Messages : 3 549
    Points : 4 625
    Points
    4 625
    Par défaut
    Il me faudrait des informations plus précises sur ce sujet, comme par exemple, comment à partir d'une liste de points, pouvoir déterminer si un triangle est en intersection avec un autre (un plan, c'est facile, mais un triangle ?)
    Ça n'a rien à voir avec le lancer de rayons.
    C'est des primitives que tu trouveras facilement en cherchant dans google.

    Ceci dit, je pourrais me contenter d'effectuer un partitionement de l'espace, mais les collisions ne seraient pas précises. Dans quelle mesure puis-je me contenter de boites englobantes non alignées sur les axes et autres algorithmes simples ?
    Le partionnement de l'espace n'est qu'une accélération pour trouver les objets avec lequel le rayon intersecte. Tu manipules toujours les mêmes objets, c'est juste que tu les ranges dans un arbre pour te permettre de ne pas avoir à tous les parcourir.
    Que tes nœuds soient des boîtes n'empêche pas tes feuilles d'être n'importe quoi.

    Dans mon jeu, si je tire un projectile, il doit suivre un rayon ( défini par un vecteur direction et une position initiale ), comment faire pour déterminer si le point ou se situe le projectile a traversé un polygone de l'environnement ?
    L'algorithme de lancer de rayon te donne l'objet intersecté le plus proche, comme je l'ai déjà expliqué.
    Boost ftw

  6. #6
    Membre actif Avatar de Nyarlathotep
    Profil pro
    Étudiant
    Inscrit en
    Juin 2005
    Messages
    174
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2005
    Messages : 174
    Points : 217
    Points
    217
    Par défaut
    Mais dans le cas d'un projectile c'est simple ; comme je l'ai écris selon le X et Y du projectile , il faut regarder si à un instant t ces coordonnées X et Y sont confondues à un polygone..
    Ce n'est pas possible aussi facilement dans mon cas, malheureusement, vu que un simple test coordonnées/coordonnées ne m'indiquerait pas si le projectile a traversé ou pas le polygone ( je travaille en 3D ).

    C'est des primitives que tu trouveras facilement en cherchant dans google.
    Je l'attendais, celle là. Effectivement, on trouve beaucoup de choses sur google, dont des documents à ce sujet, mais cela reste des mathématiques pures, et cela ne m'explique pas comment implémenter une intersection par exemple dans mon code (C++).

    L'algorithme de lancer de rayon te donne l'objet intersecté le plus proche, comme je l'ai déjà expliqué.
    Peux-tu m'envoyer le lien ?
    "That is not dead which can eternal lie
    And with strange aeons even death may die"

    The Call of Cthulhu

  7. #7
    Expert confirmé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Décembre 2003
    Messages
    3 549
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Décembre 2003
    Messages : 3 549
    Points : 4 625
    Points
    4 625
    Par défaut
    Tu parcoures tous les objets de ta scène, tu testes s'ils intersectent ton rayon, et parmi ceux-ci tu cherches l'objet le plus proche.

    Donc il te faut :
    - primitives pour test d'intersection rayon/tes objets
    - primitives pour distance point/tes objets

    Tu peux aller en plus vite en découpant ta scène et même tes objets eux-mêmes en boîtes ou autre ensembles imbriqués, ce qui constitue ce que l'on appelle une structure d'accélération.
    En effet, grâce à l'imbrication, tu peux éviter de faire un grand nombre de tests d'intersection.
    Boost ftw

  8. #8
    Inactif
    Profil pro
    Inscrit en
    Décembre 2007
    Messages
    180
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2007
    Messages : 180
    Points : 148
    Points
    148
    Par défaut
    j'ai pas pris le temps de lire tout le topic alors mes excuses si je répète ce qui a été déjà dit...

    pour faire simple:

    - on ne fait pas de collisions avec du lancer de rayons et des triangles, il faut d'autres algorithmes (spheres/box/solid... vs ngons/terrains/voxel/csg...)

    - dans le cas de collisions sur polygones il faut déjà que les collisions marchent en force brute sur un petit mesh avant de passer aux structures d'optimisation (quad tree, bsp, etc, leur chois dépend entièrement de l'aspect de ta map: resolution, angularité, etc)


    il est conseillé d'utiliser un moteur physique pour éviter de faire tout ce boulot (et se concentrer plutôt sur les problèmes de culling, de shaders, etc)

Discussions similaires

  1. lancer de rayon sur des surfaces parametriques
    Par ant12oine dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 04/05/2008, 10h21
  2. Lancer de rayon
    Par parano dans le forum OpenGL
    Réponses: 1
    Dernier message: 14/01/2007, 23h52
  3. OpenGL et le lancer de rayon
    Par Premium dans le forum OpenGL
    Réponses: 7
    Dernier message: 06/12/2006, 17h04
  4. Lancer de rayon
    Par Bethoring dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 29/11/2005, 22h28
  5. Lancer de Rayon
    Par Wyatt dans le forum OpenGL
    Réponses: 3
    Dernier message: 05/05/2005, 13h51

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