Qu'est-ce qu'un bon algorithme pour détecter une collision entre des sphères en mouvement?

27

Si (à des fins de détection de collision) les objets 3D sont représentés dans un jeu par des sphères, quel est un bon algorithme pour détecter une collision entre sphères?

Si chaque objet a une position à partir de la dernière image et une nouvelle position (souhaitée), quel est un bon algorithme qui identifiera les collisions où les sphères ne se sont pas intersectées dans l'image précédente, et elles peuvent ne pas se croiser dans la deuxième image, mais ils se sont croisés quelque part entre les deux?

collision-detection kevin42
la source

Réponses:

18

Fondamentalement, vous cherchez une trace.

Cette page vous aidera probablement: http://www.realtimerendering.com/intersections.html

Sphère en mouvement / Sphère: (emplacement) Ajoutez le rayon de la sphère en mouvement à la sphère statique et traitez la sphère en mouvement comme un rayon. Utilisez ce rayon pour effectuer une intersection rayon / sphère. Voir Gomez; Schroeder pour le code (l'article a un bug dans la dérivation, le code est très bien); et RTR2, p. 622.

Tetrad
la source
1
Cela ne fonctionne pas si les deux sphères bougent (même pas si vous le faites deux fois). Il me semble que vous devez d'abord vérifier la distance entre les lignes couvrant le mouvement a et le mouvement couvrant b, et si cela est inférieur au rayon a + rayon b, vous risquez une collision. Après cela, je ferais une vérification pour voir où ce point est dans le temps pour la sphère a et où pour la sphère b pour voir si les temps sont proches. Si c'est le cas, je comparerais la vitesse à la distance dans le temps pour ce point, si c'est toujours une collision possible, je ferais un raffinement par étapes.
Kaj
15
En fait, il suffit de rendre le mouvement relatif. Donc, si les deux sphères se déplacent, il vous suffit de soustraire la vitesse de l'une des sphères des deux afin d'avoir une sphère "en mouvement" et une sphère "stationnaire". Ensuite, vous pouvez utiliser ce qui précède.
Tetrad
8

Utilisez un test de balayage comme démontré dans cet article Gamasutra.

Firas Assaad
la source
4

Du haut de ma tête:

  1. Créez deux segments de ligne à partir du milieu de chaque cercle, de l'endroit où il a commencé à celui où il s'est déplacé à ce pas de temps.
  2. Trouvez la distance minimale entre ces deux segments de ligne; comme expliqué ici .
  3. Si cette distance est inférieure ou égale au rayon du premier cercle plus le second, ils sont entrés en collision; sinon ils ne l'ont pas fait.

Et c'est tout ce qu'il y a à faire, je m'attends à ce que ce soit assez rapide.

Robert Massaioli
la source
1

Voici un autre bel article sur Gamasatura .

Mateen Ulhaq
la source
1
Je me rends compte que c'est 7 ans plus tard, mais cette réponse est uniquement un lien. Heureusement, le lien est toujours vivant, mais s'il ne l'était pas, votre réponse ne serait ... pas une réponse.
Draco18s
0

Parler comme quelqu'un qui a fait ça: ça ne vaut pas la peine . À moins que votre conception de jeu n'en ait absolument besoin, et ce n'est certainement pas le cas, vous consacrerez beaucoup plus d'efforts au balayage que vous ne le pensez vraiment. Et ce sera plus lent que vous ne le souhaitiez.

ZorbaTHut
la source
Il pourrait faire un jeu de billard pour tout ce que vous savez.
Kaj
S'il faisait un jeu de billard, son "design de jeu en a absolument besoin" .
deft_code
Vous avez raison, ne réinventez pas la roue . Mais juste pour excersise cela peut valoir la peine.
user712092
4
Je ne suis pas d'accord avec le découragement direct comme réponse .
bobobobo
Je suis d'accord avec @bobobobo, la question n'est pas de savoir si cela en vaut la peine ou non, un futur utilisateur qui voit ce fil pourrait avoir absolument besoin de la réponse, peu importe le coût. Ce serait mieux comme commentaire.
TomTsagk
0

Il y a un article sur la dérivation de la détection de collision avec les mathématiques sur Flipcode . Il a un cercle-cercle. Il y a comment détecter précisément le point de collision et vérifier s'il y a une collision.

user712092
la source
Je me rends compte que c'est 7 ans plus tard, mais cette réponse est uniquement un lien. Heureusement, le lien est toujours vivant, mais s'il ne l'était pas, votre réponse ne serait ... pas une réponse.
Draco18s
0

La détection de collision pour un objet en mouvement est généralement appelée "calcul du volume balayé", voici quelques codes / articles sur ce sujet.

http://www.gpu-voxels.org/demos/ (Démo)

Bibliothèques de code source:

https://github.com/fzi-forschungszentrum-informatik/gpu-voxels

https://libigl.github.io/tutorial/#swept-volume

https://github.com/gradientspace/geometry3Sharp

Des articles:

http://gamma.cs.unc.edu/SV/sm03.pdf

https://www.cs.columbia.edu/~allen/PAPERS/abrams.swept.pdf (malheureusement pas de code source)

http://www.realtimerendering.com/intersections.html (Collection assez lourde de liens)

TarmoPikaro
la source
1
Les réponses qui contiennent uniquement un lien (ou dans ce cas, plusieurs) ne contiennent pas de réponse réelle. Vous devez inclure les informations pertinentes dans votre message afin que si ces liens disparaissent, votre message est toujours compréhensible.
Draco18s
Les informations derrière les liens expliquent un peu mieux que moi pour le moment. Il existe également des vidéos de démonstration derrière les liens, ce qui donne une idée de ce qui se passe en temps réel.
TarmoPikaro
1
meta.stackexchange.com/a/8259/313685
Draco18s