Quel est le moyen le plus rapide de vérifier si deux AABB en mouvement se croisent?

J'ai deux AABB qui se déplacent, quel est le moyen le plus rapide de vérifier s'ils se croiseront sous un cadre?

En déplaçant, je veux dire non seulement pour vérifier avec la méthode d'intersection de rectangle habituelle, je veux dire une sorte de test simple et facile qui ne renvoie qu'un booléen, pas de temps de réponse ou quoi que ce soit d'autre.

Ce que je pense, c'est de le faire simplement comme ceci:

Mais cet hexagone est assez complexe et je ne sais pas comment calculer une intersection AABB - Polygone, y a-t-il peut-être un moyen plus simple?

N'importe quel langage de programmation que vous aimez le plus, je peux facilement le porter.

Merci.

Utilisez la somme de Minkowski

Un bon moyen de résoudre ce problème est de considérer l'intersection entre une ligne de mouvement ( v ) traduite à l'origine ( v ' ) et la somme de Minkowski de A tournée de 180 degrés à l'origine ( A' ) et ses obstacles (juste B dans ce cas): A » ⊕ B .

Dans l'image suivante, je place A smack-dab à l'origine d'un système de coordonnées arbitraires. Cela simplifie la compréhension car la rotation de A de 180 degrés donne A ' , et v traduit à l'origine est égal à v' .

La somme de Minkowski est le rectangle vert, et les points d'intersection d'un A en mouvement et d'un B stationnaire peuvent être trouvés en faisant l' intersection ligne-AABB . Ces points sont marqués par des cercles bleus.

Dans l'image suivante, une origine différente a été utilisée et les mêmes points d'intersection sont trouvés.

Plusieurs AABB mobiles

Pour que cela fonctionne pour deux AABB qui se déplacent de manière linéaire pendant une période de temps spécifique, vous devez soustraire le vecteur de vitesse de B du vecteur de vitesse de A et l'utiliser comme segment de ligne pour l'intersection ligne-AABB.

Pseudo code

def normalize(aabb):
    return {x1: min(aabb.x1, aabb.x2), x2: max(aabb.x1, aabb.x2),
            y1: min(aabb.y1, aabb.y2), y2: max(aabb.y1, aabb.y2),

def rotate_about_origin(aabb):
    return normalize({x1: -aabb.x1, x2: -aabb.x2
                      y1: -aabb.y1, y2: -aabb.y2})

# given normalized aabb's
def minkowski_sum(aabb1, aabb2):
    return {x1: aabb1.x1+aabb2.x1, x2: aabb1.x2+aabb2.x2,
            y1: aabb1.y1+aabb2.y1, y2: aabb1.y2+aabb2.y2}

def get_line_segment_from_origin(v):
    return {x1: 0, y1: 0, x2: v.x, y2: v.y}

def moving_objects_with_aabb_intersection(object1, object2):
    A = object1.get_aabb()
    B = object2.get_aabb()

    # get A'⊕B
    rotated_A = rotate_about_origin(A)
    sum_aabb = minkowski_sum(rotated_A, B)

    # get v'
    total_relative_velocity = vector_subtract(object1.get_relative_velocity(), object2.get_relative_velocity())
    line_segment = get_line_segment_from_origin(total_relative_velocity)

    # call your favorite line clipping algorithm
    return line_aabb_intersection(line_segment, sum_aabb)

Réponse à la collision

Selon le gameplay, vous effectuez soit une détection de collision plus fine (peut-être que les AABB contiennent des mailles), soit vous passez à la phase suivante: la réponse à la collision.

En cas de collision, l'algorithme d'intersection ligne-AABB renvoie respectivement 1 ou 2 points d'intersection selon que A termine son mouvement à l'intérieur de B ou le traverse, respectivement. (Ceci réduit les cas dégénérés où A effleure B le long de leurs côtés ou le long d'un de leurs coins respectifs.)

Quoi qu'il en soit, le premier point d'intersection le long du segment de ligne est le point de collision, vous devez le traduire à la bonne position dans le système de coordonnées mondial (le premier cercle bleu clair dans la deuxième image le long du v d' origine , appelez-le p ) et ensuite décider (par exemple, pour les collisions élastiques en réfléchissant v le long de la normale de collision en p ) quelle sera la position réelle de A à la fin de la trame ( At + 1 ).

S'il y a plus de 2 collisionneurs, cela deviendra un peu plus complexe, car vous voudriez également effectuer la détection de collision pour la deuxième partie réfléchie de v .

OBB - Boîte englobante orientée. Voici un tutoriel

En effet, un cadre de délimitation aligné avec le vecteur vitesse de l'objet A comme axe y (haut). Sa largeur et sa hauteur peuvent être calculées par les points de départ et d'arrivée de l'objet A. Vous comparez ensuite cela avec l'AABB de l'objet B (le traitant comme un OOBB) et votre or.

Si vous cherchez juste un test d'intersection rapide pour voir S'ils POURRAIENT éventuellement se croiser, vous pouvez créer un AABB qui entoure l'AABB de l'objet A dans les positions de départ et de fin. Si un AABB ne se croise pas avec ce tout englobant le AABB, alors il n'y a pas d'intersection; Cependant, cela pourrait conduire à des faux positifs, vous ne devez donc l'utiliser que comme test préliminaire.

Vous n'avez pas besoin d'OOB et vous n'avez pas besoin d'utiliser la détection de collision à pas de temps. Utilisez simplement le test de balayage AABB normal, voir ce lien . Essentiellement, il fait exactement ce que vous avez dans votre diagramme: l'AABB en mouvement est "balayé" d'un point de départ à un point final, puis utilisé pour la détection de collision avec d'autres AABB statiques.

Si vous craignez que ce test balayé soit plus cher car il renvoie un «temps d'impact», je pense que vous vous optimisez prématurément.

Des informations plus détaillées sur les tests balayés peuvent être trouvées dans l'excellent livre: Real-Time Collision Detection de Christer Ericson.

Vous devrez d'abord décomposer le mouvement en étapes plus petites et utiliser ces informations pour calculer un AABB de haut niveau. Si les grands AABB se croisent, vous pouvez alors vérifier les étapes plus petites pour être plus précis.

Estimer s'il peut y avoir eu une collision en vérifiant AABB (ou OOBB) en utilisant uniquement les positions de départ et de fin peut manquer des collisions si l'un des objets tourne rapidement et est plus long dans une dimension que dans l'autre.

Pour calculer une estimation plus précise de l'AABB, décomposez le mouvement en étapes plus petites et en utilisant uniquement l'AABB initial (et non le maillage de l'objet), faites pivoter l'AABB (maintenant juste une boîte, pas alignée sur l'axe) car l'objet tournerait et se déplacerait à chaque étape. Les points max et min pour chaque axe vous donneront l'AABB qui englobe tout le mouvement de l'objet.

S'il y a une intersection avec le plus grand AABB, vous pouvez alors utiliser les plus petits AABB qui ont déjà été calculés pour déterminer où la collision peut avoir été. Pour chacun des plus petits AABB qui se croisent avec l'autre objet, vous pouvez alors effectuer la détection d'intersection de maillage la plus coûteuse.

Vous devrez décomposer le mouvement en étapes plus petites. Par exemple:

Vous souhaitez décomposer le mouvement à l'aide de la plus grande composante (dans ce cas, l'axe X), puis vérifier la collision à chaque étape.

Cela peut sembler trop cher, mais sachez qu'un objet se déplaçant plus vite que sa propre largeur à chaque cycle sera extrêmement rapide, donc ce scénario n'est pas aussi courant que vous le pensez.

Vous devez également utiliser des vitesses relatives pour le contrôle de collision afin qu'un AABB soit "statique" et que l'autre se déplace à une vitesse de sa propre vitesse moins la vitesse de celle "statique".

Le moyen le plus rapide de voir si elles peuvent se croiser consiste à simplement étendre l'AABB en mouvement avec la vitesse.

par exemple, l'AABB se déplace vers la droite avec 0,1 x / image, puis vous l'étendez pour que le bord gauche reste le même et que le bord droit soit encore 0,1. Ensuite, vous pouvez vérifier avec le nouvel AABB. Si faux, il n'y a pas de collision. (retour précoce et précis pour les petites vitesses).

Ensuite, vous pouvez vérifier si la fin et le début de l'AABB de l'objet en mouvement se croisent. si vrai, retournez vrai.

Sinon, vous devez vérifier si la diagonale coupe l'ABB statique.

Cela implique d'obtenir les coordonnées de la diagonale où x = bord gauche de la statique et le bord droit voir si le y est à l'intérieur du bas et du haut. (répétez l'inverse)