Discussion :

[[Hugo]]

Bonjour,

Je me pose une pitite question sur des collisions : dans un espace 3D, pour 2 segments dont les extrémités se déplacent chacune à une vitesse différente (en norme et direction : donc on a 4 vecteurs vitesses), existe-t-il des recettes pour détecter des collisions entre ces segments ? Si vous avez des pistes, je serais très intéressés !!

Merci beaucoup !

Marc

[Zavonen]

Je pense que le problème est résolu dès qu'on a la distance des deux segments. Il suffit de contrôler cette distance à intervalles de temps réguliers.
Le calcul de cette distance (en 3D) fait à mon avis intervenir la perpendiculaire commune aux deux droites porteuses, que l'on peut avoir par un banal produit vectoriel.
Après il faut faire une étude de cas suivant la position des deux segments par rapport à cette perpendiculaire commune.

[pseudocode]

Ne faut-il pas déjà que les 4 points soient coplanaires ?

Très en forme notre Pseudocode !!!
Bien sûr on calcule la distance d'une extrêmité par rapport au plan des 3 autres. Si c'est bon on est ramené à un pb plan.
Excuse moi Pseudocode, par erreur j'ai édité ton post au lieu d'en faire un nouveau.

[[Hugo]]

Merci pour vos réponses, toutefois je pense que le problème est un peu plus tordu que cela... et je crois que je ferais bien de préciser, je m'aperçois que j'ai mal formulé mon affaire.
J'ai 4 points(a, b, c et d), associés 2 à 2 pour former deux segments [ab] et [cd]. Je connais sur un pas de temps la vitesse de chacun de ces points, va, vb, vc et vd. La question est de prévoir si une interstection va se produire pendant le pas de temps et si oui à quel moment ?
Les 4 vecteurs vitesse sont indépendants, ce qui signifie que la longueur et l'orientation relative des segments va varier pendant le pas de temps et en toute généralité, ils n'ont pas de normale commune.
Encore une fois, merci pour vos suggestions

Marc

[pseudocode]

Excuse moi Pseudocode, par erreur j'ai édité ton post au lieu d'en faire un nouveau.

Il vous en prie . Pseudocode se quote et de se répond a lui-même.

La question est de prévoir si une interstection va se produire pendant le pas de temps et si oui à quel moment ?

Meme réponse. Le point D est d'un coté du plan ABC "avant", et de l'autre coté du plan ABC "après". A partir de là, chercher l'instant "t" pour lequel les 4 points sont coplanaires. Et de là retour au cas en 2 dimensions.

Bon il y a le cas ou le point D reste du meme coté de ABC (la trajectoire de D est tangeante au plan), mais ce cas est indetectable avec une discrétisation du temps.

[[Hugo]]

Salut pseudocode,

Merci de ta patience : mon crâne épais commence à laisser passer l'info que tu distilles si patiemment... Pour dire autrement, je prends les coordonnées de mes 4 points et je regarde si le système va devenir lié sur mon pas de temps (déterminant nul), et si oui, je regarde si collision il y a dans le plan en regardant si mes segments s'intersectent ?
Pour le cas où D est tangent, on va de toute façon annuler le déterminant, non ?

Encore merci

Marc

[pseudocode]

Merci de ta patience : mon crâne épais commence à laisser passer l'info que tu distilles si patiemment... Pour dire autrement, je prends les coordonnées de mes 4 points et je regarde si le système va devenir lié sur mon pas de temps (déterminant nul), et si oui, je regarde si collision il y a dans le plan en regardant si mes segments s'intersectent ?

Yes. En cas d'intersection, le déterminant va changer de signe entre "t" et "t+1". On cherche alors le "t+dt" pour lequel le déterminant est égal à zéro. On se retrouve en géométrie plane pour tester s'il y a réellement intersection des 2 segments (= l'intersection des 2 droites de support est comprise dans chaque segment).

Pour le cas où D est tangent, on va de toute façon annuler le déterminant, non ?

Ca dépend du pas de discrétisation. Si le déterminant a "t" ou "t+1" est égal à zéro => idem cas précédant. Mais si les déterminants à "t" et "t+1" sont tous les 2 de meme signe, on n'a aucun moyen de savoir s'il s'est annulé entre les 2 instants.

[[Hugo]]

En fait, l'idée à laquelle on pense est plutôt la suivante :
on connaît les vitesses sur un pas de temps et on paramètre les positions sur le pas de temps, on en tire un polynôme de degrés 3 en temps et on cherche ses racines et on voit si la ou les racines réelles tombent dans le pas de temps : si oui, l'intersection a lieu à ce moment... du coup, il me semble qu'on ne peut pas rater les intersections...

Merci tout plein !!

Marc

[Zavonen]

Le point générique du segment [AB] est donné par:
x(t)=txA+(1-t)xB
y(t)=tyA+(1-t)yB
z(t)=tzA+(1-t)zB
avec 0 <= t <=1
De la même façon le point générique du segment [CD] est donné par:
x(s)=sxC+(1-s)xD
y(s)=syC+(1-s)yD
z(ts=szC+(1-s)zD
avec 0 <= s <=1
De sorte que l'existence d'une intersection revient à l'existence d'un couple solution (s,t) avec 0 <= t <=1 et 0 <= s <=1
au système surdéterminé.
(xA-xB)t+(xD-xC)s=xD-xB
(yA-yB)t+(yD-yC)s=yD-yB
(zA-zB)t+(zD-zC)s=zD-zB
On extrait s et t des deux premières par les formules de Cramer, et on porte le résultat dans la troisième, ce qui nous donne une équation entre les 12 variables
f(xA,xB,xC,xD,yA,yB,yC,yD,zA,zA,zC,zD)=0
qui doit exactement correspondre à la coplanarité des 4 points A,B,C,D.
On fait donc comme suggère Pseudocode surveillance du signe de f entre deux instants t et t+1, s'il y a changement de signe on peut supposer qu'il y a eu intersection (condition nécessaire). Il suffit alors de vérifier que les deux solutions données par les formules de Cramer sont bien toutes les deux dans l'intervalle [0,1]

[[Hugo]]

Merci Zavonen
Je viens de sortir s et t, ça fait des fomules jolies tout plein .
Je me pose une petite question : selon toi, y a-t-il besoin de se préoccuper de la troisième relation si on s'est déjà assuré de la coplanarité des 4 points via la nullité du déterminant ? ça m'a l'air redondant...

Encore un grand merci !

Marc

[Zavonen]

Je me pose une petite question : selon toi, y a-t-il besoin de se préoccuper de la troisième relation si on s'est déjà assuré de la coplanarité des 4 points via la nullité du déterminant ? ça m'a l'air redondant...

Je le pense aussi ...