Forum d'entraide en sciences
Bienvenue sur le forum d'entraide en sciences ! Inscrivez-vous gratuitement pour accéder à l'intégralité du forum ou connectez-vous si c'est déjà fait !

Bonne visite !

Collisions entre un triangle et un cercle

Aller en bas

Collisions entre un triangle et un cercle Empty Collisions entre un triangle et un cercle

Message par loacast le Lun 1 Mai 2006 - 21:34

Bonjour,

J'ai un problème dont je suis totalement incapable de résoudre.

Je réalise un jeu du nom d'asteroid, vous connaissez sûrrement ce jeu, et je souhaiterais vérifier la collision entre le vaisseau qui est triangulaire et l'astéroide qui s'apparente plus ou moins à un cercle.

Seriez-vous dans la capacité de m'aiguiller sur le cheminemant qui me permettrait de venir à bout de cette collision ?

Merci bien.

loacast
Membre
Membre

Nombre de messages : 18
Points : 5360
Date d'inscription : 19/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par Julien le Mar 2 Mai 2006 - 9:59

Qu'est-ce-que tu entends par "vérifier la collision entre le vaisseau" ?
Julien
Julien
Administrateur
Administrateur

Masculin Nombre de messages : 12291
Age : 32
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 20879
Date d'inscription : 10/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par loacast le Mar 2 Mai 2006 - 12:34

Et bien asteroid c'est un jeu où l'on controle un vaisseau (dont la forme est rectangulaire) et qui doit chooter des astéroides. Hors si le joueur n'arrive pas à éviter un astéroide, il y' a collision celà va sans dire.

Jaimerais donc savoir comment faire pour déterminer si un triangle intersecte un cercle.

Je vous demande évidemment pas l'algorithme, ça c'est mon travail, mais plutôt les calculs mathématiques qu'il faut réaliser.

Peut-être ne savez vous pas comment faire, mais qui ne tente rien n'a rien ;°).

loacast
Membre
Membre

Nombre de messages : 18
Points : 5360
Date d'inscription : 19/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par Julien le Mar 2 Mai 2006 - 12:37

Oui je connais bien ce jeu.

Mais est-ce-qu'il doit être très réaliste ou pas ?

Rotation du vaisseau sur lui même, attraction... ?
Julien
Julien
Administrateur
Administrateur

Masculin Nombre de messages : 12291
Age : 32
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 20879
Date d'inscription : 10/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par Julien le Mar 2 Mai 2006 - 12:39

En fait, je vois mal comment transcrire le problème avec des maths.

Chaque point du vaisseau compte j'imagine...

En fait, il s'agit de trouver quand un point du vaisseau "touche" un astéroïde, c'est ça ? Ca m'a lair assez complexe...
Julien
Julien
Administrateur
Administrateur

Masculin Nombre de messages : 12291
Age : 32
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 20879
Date d'inscription : 10/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par loacast le Mar 2 Mai 2006 - 13:09

lien pour télécharger la version actuelle

Je crois qu'en testant ce qui est existant ce sera bien plus clair.

Sinon tu n'as aucune formule mathématiques qui se cacherait pas là ?

loacast
Membre
Membre

Nombre de messages : 18
Points : 5360
Date d'inscription : 19/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par Julien le Mar 2 Mai 2006 - 15:10

loacast a écrit:
Sinon tu n'as aucune formule mathématiques qui se cacherait pas là ?
Je vais y réfléchir, mais je ne te promets rien !
Julien
Julien
Administrateur
Administrateur

Masculin Nombre de messages : 12291
Age : 32
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 20879
Date d'inscription : 10/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par loacast le Mar 2 Mai 2006 - 15:59

Je vais y réfléchir, mais je ne te promets rien !

C'est déjà super d'essayer Very Happy .

loacast
Membre
Membre

Nombre de messages : 18
Points : 5360
Date d'inscription : 19/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par Julien le Jeu 4 Mai 2006 - 9:38

Vu que la trajectoire d'un astéroïde est aléatoire, est-ce-que tu connais quand-même les coordonnées de chaque point le constituant ?
Julien
Julien
Administrateur
Administrateur

Masculin Nombre de messages : 12291
Age : 32
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 20879
Date d'inscription : 10/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par loacast le Dim 7 Mai 2006 - 10:45

Ca peut effectivement se trouver.

Au passage, s'avous vous comment déterminer le point d'intersection entre deux droites ?

loacast
Membre
Membre

Nombre de messages : 18
Points : 5360
Date d'inscription : 19/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par Julien le Dim 7 Mai 2006 - 11:27

Soit (d) la droite d'équation y=mx+p et (d') la droite d'équation y=m'x+p'.

On vérifie à l'aide des propriétés sur le parallélisme que les deux droites ne sont pas parallèles ou confondues.

Si elles ne le sont pas, on établit et on résout le système :
y=mx+p et y=m'x+p'

Le couple solution est le couple des coordonnées du point d'intersection.
Julien
Julien
Administrateur
Administrateur

Masculin Nombre de messages : 12291
Age : 32
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 20879
Date d'inscription : 10/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par loacast le Dim 7 Mai 2006 - 12:57

Merci de ton aide. Mais pourrais-tu rendre ton explication plus didactique parceque je suis vraiment pas doué en maths s'il te plait.

En tout cas, merci pour le temps que tu prends sur mes questions.

loacast
Membre
Membre

Nombre de messages : 18
Points : 5360
Date d'inscription : 19/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par Julien le Dim 7 Mai 2006 - 14:17

Dis-moi ce que tu ne comprends pas. Il s'agit de fonctions affines où m est le coefficient directeur et p l'ordonnée à l'origine...

Ceci pourra peut-être t'aider à mieux comprendre : http://www.zoneflash.net/animation.php?r=flash3-0033
Julien
Julien
Administrateur
Administrateur

Masculin Nombre de messages : 12291
Age : 32
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 20879
Date d'inscription : 10/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par loacast le Lun 8 Mai 2006 - 0:10

Ton lien est très explicite, par contre, pourquoi avoir choisi la notation d'. Ca m'embrouille pas mal car j'ai appris les dérivés hors si j'ai bien compris toi quand tu parles de d' c'est pour désigner la seconde droite ?

Néanmoins je comprend déjà mieux là où tu veux en venir.

Aurais tu un lien vers un cours expliquant comment résoudre y=mx+p et y=m'x+p' ?

Et merci encore.

loacast
Membre
Membre

Nombre de messages : 18
Points : 5360
Date d'inscription : 19/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par Julien le Lun 8 Mai 2006 - 9:35

Oui, d' désigne l'autre droite. Il n'est pas du tout question de dérivées là.

Pour résoudre un système d'équations de droites, regarde la fin de ce document : http://www.lombardf.com/~jean-eloi/pri/2nd1/maths/equation_droite.html
ou le 7°) de ce document : http://www.resoo.org/docs/_docs/maths_3e/maths/cours3e/ch63eme.htm#resgraph (méthode graphique).

Pose des questions si tu ne comprends pas quelque chose !
Julien
Julien
Administrateur
Administrateur

Masculin Nombre de messages : 12291
Age : 32
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 20879
Date d'inscription : 10/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par loacast le Lun 8 Mai 2006 - 21:03

A priori j'ai tout compris. Merci je reviendrais à cout sur !

loacast
Membre
Membre

Nombre de messages : 18
Points : 5360
Date d'inscription : 19/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par payne le Jeu 15 Juin 2006 - 23:53

Hey! Au juste... étant un bon programmeur en actionscript (en flash), dit-moi... fais-tu ton jeu avec Flash MX ? Si oui... je peux très bien t'aider ^^

_________________
BOO!!
Scared heh?
payne
payne
Membre
Membre

Masculin Nombre de messages : 1783
Age : 27
Localisation : Montréal, Québec, Canada
Profession / Etudes : Étudiant
Points : 5144
Date d'inscription : 09/06/2006

https://etudiant-scientific.forumactif.com/

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par loacast le Ven 16 Juin 2006 - 22:33

Non je programme en c++. Le problème est réglé mais c'est sympa de proposer ton aide.

loacast
Membre
Membre

Nombre de messages : 18
Points : 5360
Date d'inscription : 19/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par Julien le Sam 17 Juin 2006 - 9:37

Et tu l'as réglé comment le problème en gros ?
Julien
Julien
Administrateur
Administrateur

Masculin Nombre de messages : 12291
Age : 32
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 20879
Date d'inscription : 10/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par ephemere le Lun 19 Juin 2006 - 12:54

Il faut avant toute chose faire attention à ne pas trop vite foncer vers des calculs compliqués qui ralentiront le programme.

Si tu acceptes de remplacer ton triangle par un cercle, cela facilitera concidérablement le programme car il suffira de regarder si la distance entre le centre de ton vaisseau et le le centre de ton astéroïde est oui où non supérieur ou égal à la somme de leur rayon. Et il reste possible de jouer avec les couleurs pour que l'avant de ton vaisseau ne soit pas confondu avec l'arrière de celui-ci.

Mais si tu veux vraiment que ton vaisseau soit triangulaire, tu peux utiliser la formule qui donne la distance d'un point de coordonnées (m,n) à une droite d'équation ax+by+c=0. Cette formule est |am+bn+c| / (RACINE(a²+b²)). Tu dois ensuite faire une discution pour interprêter le résultat mais il faut penser à tout (un segment n'est qu'un morceau de droite,...).
ephemere
ephemere
Membre
Membre

Masculin Nombre de messages : 633
Age : 40
Localisation : Belgique
Profession / Etudes : Étudiant de 3ème cycle
Points : 5313
Date d'inscription : 05/05/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par loacast le Mer 21 Juin 2006 - 7:37

Le premier point que j'ai résolu (en demandant sur un forum hein) c'est comment savoir si un point est dans un triangle.


coord0 = (xPoint - triangle[1][0])*(yPoint - triangle[2][1])-(xPoint - triangle[2][1])*(yPoint-triangle[1][1]);
coord1 = (xPoint - triangle[2][0])*(yPoint - triangle[0][1])-(xPoint - triangle[0][0])*(yPoint - triangle[2][1]);
coord2 = (xPoint - triangle[0][0])*(yPoint - triangle[1]['y'])-(xPoint - triangle[1][0])*(yPoint - triangle[0][1]);


triangle est un tableau à 2 dimensions (pour illustrer le calcul, dans la réalité ce serait plutôt
un tableau d'objets vecteurs (un vecteur étant un point en OpenGL)) dont le premier index représente l'index du point et le second, x ou y.

coord0, coord1 et coord2 sont les trois coordonées barycentrique du point (xPoint, yPoint)

Si coord0, coord1 et coord2 sont tous les trois de même signe, (xPoint, yPoint) est dans le triangle, sinon il n'y est pas.


De là je me dis qu'un astéroide n'est pas rond mais composé d'un certain nombre de triangles. On cherche si une extermité du vaisseau est dans l'asteroide et si une extremité de l'asteroide est dans le vaisseau. Si la boucle du jeu est suffisement rapide, on peut ignorer les tests d'intersection sinon et bien on les prend en compte.

Il y'a mieux comme algorithme mais à priori les résultats ne devraient pas être trop mauvais. Pour ce qui est des performances je m'en
contrebalance, avant de faire saturer un ordi avec un jeu asteroides like il faut le vouloir quand même. Et d'ailleurs, c'est pas parceque
Laurent Testud l'a dit qu'il faut le croire. Très peu de jeux à l'heure actuelle utilisent les collisions en se basant sur des sphères.

loacast
Membre
Membre

Nombre de messages : 18
Points : 5360
Date d'inscription : 19/03/2005

Revenir en haut Aller en bas

Collisions entre un triangle et un cercle Empty Re: Collisions entre un triangle et un cercle

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum