Déterminer si deux objets en mouvement rapide doivent être soumis pour un contrôle de collision

8

J'ai un moteur de physique 2D de base en marche. C'est à peu près un moteur de particules, utilise simplement des formes de base comme les AABB et les cercles, donc aucune rotation n'est possible. J'ai implémenté CCD qui peut donner un TOI précis pour deux objets en mouvement rapide et tout fonctionne sans problème.

Mon problème est maintenant que je ne peux pas comprendre comment déterminer si deux objets en mouvement rapide doivent même être vérifiés l'un contre l'autre en premier lieu. J'utilise un arbre quadruple pour le partitionnement spatial et pour chaque objet en mouvement rapide, je le compare aux objets dans chaque cellule qu'il passe. Cela fonctionne très bien pour déterminer la collision avec la géométrie statique, mais cela signifie que tout autre objet en mouvement rapide qui pourrait entrer en collision avec lui, mais qui n'est dans aucune des cellules qui sont vérifiées, n'est jamais pris en compte.

La seule solution à laquelle je puisse penser est soit d'avoir les cellules suffisamment grandes et de croiser les doigts pour que cela soit suffisant, soit d'implémenter une sorte d'algorithme de force brute. Existe-t-il une façon appropriée de régler ce problème, peut-être que quelqu'un a résolu ce problème de manière efficace. Ou peut-être existe-t-il une meilleure façon de partitionner l'espace qui en tient compte?

Voici un schéma:

entrez la description de l'image ici

Les "zones d'effet" des objets A et B se croisent, elles doivent être vérifiées l'une par rapport à l'autre. Mais avec la façon dont je vérifie actuellement les collisions, cela ne tient pas compte de cela. Encore une fois, je peux penser à quelques solutions à cela, comme vérifier réellement si les chemins des objets se croisent une fois que leur vitesse est supérieure à x, ou quelque chose, mais cela ressemble à un hack et c'est un gâchis à essayer d'implémenter.

collision-detection physics dreta
la source
Pourriez-vous donner un exemple de scénario dans lequel votre méthode échoue?
Anko
1
Je pense que cela se passerait comme ceci: les objets A et B sont dans cette configuration: [A] [] [B]. A va vers la droite et B vers la gauche. Ils vont vite. Le contrôle de collision se déroule comme suit: la cellule suivante est-elle vide pour A? Oui, bcs il n'y a rien dans la cellule du milieu. La cellule suivante est-elle vide pour B? Oui. Donc pas de collision. Mais la vraie physique montrerait que A et B sont susceptibles d'entrer en collision (en particulier dans ce jeu à une dimension que je décris;)
Cystack
@Cystack J'ai implémenté CCD. La situation que vous avez décrite n'est pas un problème. Les deux objets vont directement l'un à l'autre, l'implémentation que j'ai décrite va le ramasser et le résoudre.
dreta
La physique de la situation est claire. Disons que vous pouvez identifier un objet comme «se déplaçant rapidement» à l'avance. Ensuite, lorsque vous effectuez un contrôle de collision, vous devez vérifier non seulement la cellule dans laquelle se trouve actuellement l'objet, mais également toutes les cellules qu'il a traversées au dernier pas de temps. Ainsi, chaque objet se déplaçant rapidement a en fait plusieurs emplacements, comme toute la bande verte que vous avez dessinée dans l'image ci-dessus.
theJollySin
@theJollySin j'ai déjà décrit la solution que vous proposez, c'est un hack, un cas particulier, je cherche une solution générale s'il y en a une.
dreta

Réponses:

5

Le problème dont vous parlez est souvent appelé `` détection de collision à large phase '' et votre solution est un `` volume balayé '', pas vraiment un hack, juste comment il est fait (prenez simplement l'AABB de l'objet, y compris le début et la fin du mouvement et utilisez-le pour la collision - bien que les choses deviennent un peu délicates avec les rotations).

Ensuite, l'algorithme de détection des collisions à large bande qui accélère ce processus est appelé «balayage et élagage».

Jeff Gates
la source
J'ai supprimé SAP avant que ce problème ne se pose. Je fais cela en JavaScript, ce qui rend visible la surcharge des listes.Les tableaux peuvent également devenir peu fiables en termes de performances. Je suppose que je vais devoir reconsidérer les choses. Merci, l'algorithme résout effectivement le problème.
dreta