détection de collision entre Accelerating Sphères

Question

J'écris un moteur physique/simulateur qui intègre vol spatial 3D, la gravitation planétaire/stellaire, la poussée des navires et des effets relativistes. Jusqu'à présent, il va très bien, cependant, une chose que je besoin d'aide est le calcul de la détection de collision algorithim.

La simulation itérative de mouvement que je me sers est essentiellement comme suit:

(Note:. 3D vecteurs sont MAJUSCULES)

For each obj 

    obj.ACC = Sum(all acceleration influences) 

    obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2  (*EQ.2*) 

    obj.VEL = obj.VEL + (obj.ACC * dT) 

Next 

Où:

obj.ACC is the acceleration vector of the object 
obj.POS is the position or location vector of the object 
obj.VEL is the velocity vector of the object 

obj.Radius is the radius (scalar) of the object 

dT is the time delta or increment 

Ce que je essentiellement besoin de faire est de trouver une formule efficace qui découle de (eq.2) ci-dessus pour deux objets (obj1, obj2) et dire si elles entrent en collision jamais, un sd si oui, à quelle heure. J'ai besoin l'heure exacte à la fois pour que je puisse déterminer si elle est dans cet incrément de temps particulier (parce accelleratons sera différent à différents incréments de temps) et aussi pour que je puisse localiser la position exacte (que je sais comment faire, compte tenu de la temps)

pour ce moteur, je modélise tous les objets comme des sphères, tout cette formule/algortithim doit faire est de comprendre à quel points:

(obj1.POS - obj2.POS).Distance = (obj1.Radius + obj2.Radius) 

où .distance est une valeur scalaire positive. (Vous pouvez également conciliez les deux parties si cela est plus facile, d'éviter la fonction racine carrée implicite dans le calcul .distance). (Oui, je suis au courant de beaucoup, beaucoup d'autres questions de détection de collision, cependant, leurs solutions semblent toutes être très particulières à leur moteur et hypothèses, et aucune ne semble correspondre à mes conditions: 3D, sphères et accélération appliquées . dans les incréments de simulation Permettez-moi de savoir si je me trompe)

---

Quelques Clarifications:.

1) Il ne suffit pas pour moi de vérifier pour * Intersection * des deux sphères avant et après la incrément de temps. Dans de nombreux cas, leurs vitesses et changements de position dépasseront de loin leurs rayons.

2) RE: efficacité, je ne suis pas besoin d'aide (à ce moment de toute façon) par rapport à déterminer les candidats probables pour les collisions, je pense que j'ai que couvert.

---

Une autre précision, ce qui semble venir beaucoup:

3) Mon équation (EQ .2) de mouvement incrémental est une équation quadratique qui applique à la fois la vitesse et Accélération:

obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2 

les moteurs de physique que je l'ai vu, (et certainement tous les moteurs de jeu que j'ai jamais entendu parler) que linéaire équations de mouvement incrémental qui s'appliquent seulement Velocity:

obj.POS = obj.POS + (obj.VEL * dT) 

Voilà pourquoi je ne peux pas utiliser les solutions couramment publiées pour la détection des collisions trouvées sur pile Débordement, sur Wikipédia et partout sur le Web, tel que trouver l'intersection/approche la plus proche de deux segments de ligne. Ma simulation traite des accélérations variables qui sont fondamentales pour les résultats, donc ce dont j'ai besoin est l'intersection/approche la plus proche de deux segments paraboliques.

Answer 1

Sur la page Web mentionnée par AShelley, la méthode du point d'approche le plus proche est développée pour le cas de deux objets se déplaçant à une vitesse constante. Cependant, je crois que la même méthode de calcul vectoriel peut être utilisée pour dériver un résultat dans le cas de deux objets se déplaçant tous les deux avec une accélération constante non nulle (dépendance quadratique du temps).

Dans ce cas, la dérivée temporelle de la fonction de la distance au carré est du 3ème ordre (cubique) au lieu du 1er ordre. Il y aura donc 3 solutions au Temps de l'approche la plus proche, ce qui n'est pas surprenant puisque le chemin des deux objets est incurvé de sorte que plusieurs intersections sont possibles. Pour cette application, vous voudrez probablement utiliser la valeur la plus ancienne de t qui se trouve dans l'intervalle défini par l'étape de simulation actuelle (si une telle durée existe).

J'ai travaillé l'équation dérivée qui devrait donner le temps d'approche le plus proche:

0 = |D_ACC|^2 * t^3 + 3 * dot(D_ACC, D_VEL) * t^2 + 2 * [ |D_VEL|^2 + dot(D_POS, D_ACC) ] * t + 2 * dot(D_POS, D_VEL)

où:

D_ACC = ob1.ACC-obj2.ACC

D_VEL = ob1.VEL-obj2.VEL (avant mise à jour)

D_POS = ob1.POS-obj2.POS (également avant la mise à jour)

et dot(A, B) = A.x*B.x + A.y*B.y + A.z*B.z

(Notez que le carré de l'ampleur |A|^2 peut être calculée en utilisant dot(A, A))

Pour résoudre ce pour t, vous aurez probablement besoin d'utiliser des formules comme celles found on Wikipedia.

Bien sûr, cela vous donnera seulement le moment de approche la plus proche. Vous devrez tester la distance à ce moment (en utilisant quelque chose comme l'équation 2). S'il est supérieur à (obj1.Radius + obj2.Radius), il peut être ignoré (c'est-à-dire sans collision). Cependant, si la distance est inférieure, cela signifie que les sphères entrent en collision avant ce moment. Vous pouvez ensuite utiliser une recherche itérative pour tester la distance à des moments antérieurs. Il pourrait aussi être possible de trouver une autre dérivation (encore plus compliquée) qui prenne en compte la taille, ou qui soit possible de trouver une autre solution analytique, sans recourir à la résolution itérative.

Modifier: à cause de l'ordre supérieur, quelques-unes des solutions à l'équation sont en fait des moments de séparation plus loin. Je crois dans tous les cas que l'une des trois solutions ou deux des trois solutions sera une période de séparation la plus éloignée. Vous pouvez tester analytiquement si vous êtes à un minimum ou un maximum par l'évaluation de la dérivée seconde par rapport au temps (au niveau des valeurs de t que vous avez trouvé en définissant la dérivée première à zéro):

D''(t) = 3 * |D_ACC|^2 * t^2 + 6 * dot(D_ACC, D_VEL) * t + 2 * [ |D_VEL|^2 + dot(D_POS, D_ACC) ]

Si la dérivée seconde évalue à un nombre positif, alors vous savez que la distance est au minimum, pas un maximum, pour le temps t donné.

Answer 2

On dirait que vous voulez le Closest Point of Approach (CPA). Si elle est inférieure à la somme des rayons, vous avez une collision. Il y a un exemple de code dans le lien. Vous pouvez calculer chaque image avec la vélocité actuelle et vérifier si l'heure du CPA est inférieure à la taille de votre tick. Vous pouvez même mettre en cache le temps cpa, et seulement mettre à jour lorsque l'accélération a été appliquée à l'un ou l'autre élément. Tracer une ligne entre l'emplacement de départ et l'emplacement final de chaque sphère.

Answer 3

Si les segments de ligne qui en résultent se croisent, les sphères sont définitivement entrés en collision à un moment donné et des calculs astucieux peuvent déterminer à quel moment la collision s'est produite. Assurez-vous également de vérifier si la distance minimale entre les segments (s'ils ne se croisent pas) est toujours inférieure à 2 * rayon. Cela indiquera également une collision. De là, vous pouvez revenir en arrière votre temps delta pour arriver exactement à la collision afin que vous puissiez calculer correctement les forces.

Avez-vous envisagé d'utiliser une bibliothèque de physique qui fait déjà ce travail? De nombreuses bibliothèques utilisent des systèmes beaucoup plus avancés et plus stables (meilleurs intégrateurs) pour résoudre les systèmes d'équations avec lesquels vous travaillez. Bullet Physics vient à l'esprit.