EDIT / UPDATE: Ma plus grande question en ce moment est de savoir si l'équation "t = ..." de l'étape 3 est une bonne idée ou existe-t-il une meilleure façon de le faire. La plupart des autres problèmes ont été partiellement ou entièrement résolus, mais aucun commentaire ou réponse n'a vraiment abordé ce problème. Encore une fois, une solution analytique est probablement requise, les vitesses et les distances sont trop grandes, et les objets sont trop petits, pour toute solution itérative / récursive (quelques-unes sont suggérées ci-dessous dans les commentaires) auxquelles je peux penser (bien que s'il y a une solution itérative / récursive spéciale qui gérera très bien ce genre de situations, alors je suis définitivement ouvert). Merci beaucoup pour votre aide jusqu'à présent, vous êtes tous géniaux et j'apprécie vraiment vos pensées et votre aide!
J'essaie de détecter les collisions entre de petits objets à grande vitesse. Il s'agit d'une situation où le tunnelage peut se produire très facilement, même à des vitesses relativement faibles.
Le lancer de rayons ne fonctionnera pas, car il détecte une collision entre deux objets à grande vitesse, pas entre un objet et un mur fixe. (À moins que je ne comprenne mal le lancer de rayons?) La performance est TRÈS BEAUCOUP une considération; si possible, je veux éviter un gros coup de performance. J'ai déjà un quadtree fonctionnel et très efficace ( http://en.wikipedia.org/wiki/Quadtree ) implémenté, je vais donc le modifier et l'utiliser comme décrit ci-dessous.
Modifier: la réduction de l'intervalle de temps ne fonctionnera pas. Les vitesses sont trop élevées pour cette solution, ce qui signifie que les performances seraient trop importantes, tout en manquant la grande majorité des collisions de tunnellisation . (Par exemple, je pourrais avoir un objet d'une taille d'environ 1 unité allant à une vitesse mesurée en millions d'unités par intervalle de temps ...)
SOLUTION PROPOSÉE:
Étape 1:
Créez une boîte autour du mouvement de chaque objet, puis introduisez ces boîtes dans le quadtree pour générer une liste initiale des collisions possibles. Voir l'image suivante (cette image montre un objet cercle se déplaçant d'une position à une autre, et le mouvement générant un rectangle, qui sera introduit dans le quadtree):
Étape 2: (vous voudrez peut-être ignorer cette étape?)
Parcourez la liste des collisions possibles générées par le quadtree. Voyez si les rectangles se croisent à chaque collision possible. Si oui, passez à l'étape 3.
EDIT: Ci-dessous, Sean Middleditch a suggéré d'utiliser des volumes balayés / l'intersection des capsules (si les objets sont des cercles). Cela laisse trois options: 1) ignorer complètement l'étape 2. 2) Suivez l'étape 2 à ma façon. 3) Faites comme Sean. La méthode de Sean coûtera plus cher en calcul que mon idée de boîte, mais elle éliminera plus de faux positifs que la mienne, les empêchant ainsi de passer à l'étape finale.
Quelqu'un peut-il dire par expérience lequel de ces 3 choix est le meilleur? (J'ai l'intention d'utiliser ce moteur physique pour quelque chose de différent, donc je recherche la solution "généralement la meilleure" qui fonctionne le plus rapidement dans la plus grande variété de situations, pas seulement un cas de test spécifique dans lequel je peux facilement mesurer quelle solution est le plus rapide).
Étape 3:
Utilisez l'équation t = ci-dessous, si le discriminant (c'est-à-dire la partie sous la racine carrée) est négatif ou 0, pas de collision, s'il est positif, utilisez la valeur t comme moment de la collision (après quoi il est facile d'ajuster les positions en conséquence. ..si les deux objets continuent d'exister après la collision). Équation:
t = (-1/2 sqrt ((2 a w-2 a x + 2 b y-2 b z-2 c w + 2 c x-2 d y + 2 dz) ^ 2-4 (w ^ 2- 2 w x + x ^ 2 + y ^ 2-2 y z + z ^ 2) (a ^ 2-2 a c + b ^ 2-2 b d + c ^ 2 + d ^ 2-r ^ 2-2 r ss ^ 2)) - a w + a xb y + b z + c wc x + d yd z) / (w ^ 2-2 w x + x ^ 2 + y ^ 2-2 y z + z ^ 2 ) .
Où (1 et 2 sont utilisés pour désigner les objets 1 et 2):
t est une valeur de temps négative entre 0 et -1, où 0 est la trame actuelle et -1 est la trame précédente;
a = x position 1;
b = position y 1;
c = x position 2;
d = position y 2;
w = x vitesse 1;
x = x vitesse 2;
y = y vitesse 1;
z = vitesse y 2;
r = rayon 1;
s = rayon 2;
Dérivation: (^ 2 signifie carré)
Prenez des équations paramétriques (par exemple, newxpos1 = a + t w) pour les mouvements des objets et branchez-les dans la formule de distance (au carré des deux côtés): formule de distance au carré = (a + t w - (c + t x)) ^ 2 + (b + t y - (d + t * z)) ^ 2. Rappelez-vous, t va être négatif. Pour trouver le temps de collision pour deux objets circulaires, nous fixons le côté gauche égal à (r + s) ^ 2. En résolvant pour t en utilisant l'équation quadratique (et beaucoup d'algèbre très fastidieuse), nous obtenons l'équation "t = ..." ci-dessus.
Mes questions:
1) Est-ce une bonne façon de procéder? Cela fonctionnera-t-il du tout? Vais-je rencontrer des problèmes imprévus? (Je sais que je vais avoir des problèmes lorsque plus de 2 objets entrent en collision à la fois, mais je m'en fiche car le seul cas auquel je m'oppose vraiment est qu'ils ont de faibles vitesses relatives (si les vitesses relatives sont élevées) alors la solution "loufoque" que l'algorithme donne sera "assez bonne", et il sera impossible pour un humain de voir l'erreur), et si plus de 2 entrent en collision avec de faibles vitesses relatives dans le même pas de temps, la plupart des solutions être assez proche de toute façon, car je ne prévois pas d'avoir un tas de collisions inélastiques)
2) Mes performances vont-elles beaucoup souffrir? Je ne pense pas que ce sera le cas, mais si c'est le cas, y a-t-il une meilleure façon de le faire?
3) Dois-je sauter l'étape 2 et passer directement de l'étape 1 à 3? De toute évidence, l'étape 2 n'est pas vitale, mais elle peut améliorer les performances (OU elle peut coûter plus de temps processeur qu'elle n'en économise).
Tous les autres commentaires, suggestions ou critiques sont les bienvenus. Merci de votre aide!
la source
Réponses:
Vous avez essentiellement créé une version quelque peu trop enthousiaste des volumes balayés .
Prenez les deux positions de l'objet. "Balayez" l'objet du début à la fin. Pour une sphère, cela créerait une capsule. Pour une boîte, cela créerait un hexagone (ou une boîte plus longue si le mouvement se fait le long d'un seul axe). Pour les polygones convexes généraux, cela créerait un polygone convexe différent.
Vous pouvez désormais effectuer des tests d'intersection (y compris des requêtes quadtree) à l'aide de ce volume balayé. Vous pouvez calculer le moment où la collision s'est produite, faire avancer la simulation de l'heure de début à l'heure de la collision et recommencer.
Une autre option, un peu plus simple, consiste à faire ce que @ ashes999 a déclaré et à utiliser simplement un intervalle de temps plus court ou des vitesses plus petites. Il y a une vitesse maximale idéale dérivée de l'intervalle dans lequel aucun objet ne peut se déplacer plus loin que son côté le plus étroit dans une seule interaction physique. Pour les objets particulièrement petits ou particulièrement rapides, il se peut que vous ne puissiez pas trouver un intervalle raisonnablement petit qui fonctionne bien.
Voir Détection de collision en temps réel pour l'un des meilleurs livres d'introduction / intermédiaire sur le sujet de la détection des collisions.
la source
L'algorithme proposé dans la question fonctionne très bien: il est rapide et tout à fait précis , même lorsque les objets vont à des vitesses extrêmes. J'ai un quadtree implémenté, donc après avoir introduit les boîtes de l'étape 1 dans le quadtree, j'ai trouvé l'étape 2 inutile: mon programme fonctionnait presque aussi vite qu'auparavant.
J'utilise cet algorithme depuis quelques mois maintenant, et il semble être parfaitement précis pour déterminer t, le moment de la collision. Puisqu'il n'y a rien de mieux sur le Web, je recommande fortement d'utiliser celui-ci. (Certaines des réponses dans les autres réponses et commentaires ci-dessus sont excellentes, mais elles ne répondent pas tout à fait aux besoins énoncés par la question ou bien l'auteur était très ambigu sur quelque chose et n'est jamais revenu pour répondre lorsqu'il a été interrogé sur l'ambiguïté ).
la source
Je n'ai pas encore assez de réputation pour commenter, mais je voudrais juste ajouter que l'utilisation de ce que Sean Middleditch a mentionné ci-dessus permet de calculer votre "t". Au moins si j'ai bien compris sa réponse et que vous vous posez des questions correctement.
Voici un lien vers une réponse impressionnante de sam hocevar qui fournit la meilleure explication que j'ai jamais trouvée à ce sujet (il a aussi dessiné des images, hourra!)
/gamedev//a/55991/112940
Si c'est plus rapide que votre propre méthode, je ne peux pas le dire, mais il vous donne certainement tout ce dont vous avez besoin pour la mettre en œuvre et la comparer avec la vôtre.
Juste pour éviter de laisser une "réponse de lien seulement", je vais fournir un résumé rapide de son idée:
la source