Un objet a une position et un vecteur vitesse. Habituellement, seule la position est utilisée pour vérifier si deux objets entrent en collision. Ceci est problématique pour les objets se déplaçant très rapidement car il peut arriver que l'objet se déplace si rapidement qu'il se trouve devant le premier objet dans le premier contrôle de collision et derrière celui-ci le deuxième contrôle de collision.

À présent, il existe également des contrôles de collision basés sur les lignes, dans lesquels vous ne vérifiez que si le vecteur de mouvement de chaque objet intersecte le cadre de sélection de l'autre. Cela peut être vu comme une expansion d'un point. Cela ne fonctionne que si l'objet en mouvement rapide est vraiment petit.

Donc, mon idée est la suivante: au lieu d’agrandir un point, pourquoi ne pas élargir un rectangle? Cela se traduit par un hexagone.

Maintenant, jusqu'ici tout va bien. Mais comment vérifier si deux hexagones de ce type se croisent? Notez que ce sont des hexagones très spécifiques.

Question supplémentaire : Est-il possible de calculer où exactement (ou plutôt après combien de temps) la collision s’est produite? Cela pourrait être très utile pour détecter ce qui s’est réellement passé, comme où et avec combien de puissance, et pour simuler comment ils se sont déplacés dans le temps écoulé entre la collision et la fin de la trame.

La solution est en réalité plus simple que prévu. L'astuce consiste à utiliser la soustraction de Minkowski avant votre technique hexagonale.

Voici vos rectangles A et B, avec leurs vitesses vAet vB. Notez que vAet vBne sont pas réellement des vitesses, elles sont la distance parcourue au cours d'une image.

Maintenant, remplacez le rectangle B par un point P et le rectangle A par le rectangle C = A + (- B), qui a pour dimensions la somme des dimensions de A et B. Les propriétés de l'addition de Minkowski indiquent qu'il se produit une collision entre le point et le nouveau rectangle si et seulement si une collision entre les deux rectangles d'origine se produit:

Mais si le rectangle C se déplace le long du vecteur vAet que le point P se déplace le long du vecteur vB, un simple changement de repère nous indique qu'il en va de même si le rectangle C était immobile et le point P se déplaçait le long du vecteur vB-vA:

Vous pouvez ensuite utiliser une simple formule d'intersection de segments de boîte pour indiquer le lieu de la collision dans le nouveau cadre de référence.

La dernière étape consiste à revenir au cadre de référence approprié. Divisez simplement la distance parcourue par le point jusqu'à l'intersection entourée par la longueur du vecteur vB-vAet vous obtiendrez une valeur stelle que 0 < s < 1. La collision se produit à un moment s * Toù Test la durée de votre image.

Commentaire de madshogo :
L’énorme avantage de cette technique par rapport à celle de la réponse de M. Beast est qu’en l’absence de rotation, la "soustraction de Minkowski" A + (- B) peut être calculée une fois pour tous les timesteps suivants !

Ainsi, le seul algorithme prenant du temps dans tout cela (somme de Minkowski, complexité O (mn) où m est le nombre de sommets dans A et n le nombre de sommets dans B ) ne peut être utilisé qu'une seule fois, ce qui fait de la détection de collision une constante. problème de temps!

Plus tard, vous pouvez jeter la somme une fois que vous êtes certain que A et B se trouvent dans différentes parties de votre scène (de votre quadtree?) Et ne se rencontrent plus.

En revanche, la méthode de Mr Beast nécessite pas mal de calculs à chaque pas de temps.

De plus, pour les rectangles alignés sur les axes, A + (- B) peut être calculé beaucoup plus simplement qu'en calculant toutes les sommes, sommet par sommet. Développez simplement A en ajoutant la hauteur de B à sa hauteur et la largeur de B à sa largeur (une moitié de chaque côté).

Mais tout cela ne fonctionne que si ni A ni B ne sont en rotation et si les deux sont convexes. Si la rotation existe ou si vous utilisez des formes concaves, vous devez utiliser des volumes / zones balayés.
fin de commentaire

Tout d'abord, dans le cas des rectangles alignés sur les axes, la réponse de Kevin Reid est la meilleure et l'algorithme est le plus rapide.

Deuxièmement, pour les formes simples, utilisez les vitesses relatives (voir ci-dessous) et le théorème de séparation des axes pour la détection de collision. Il va vous dire si une collision se produit dans le cas de mouvement linéaire (pas de rotation). Et s’il existe une rotation, vous avez besoin d’un peu de temps pour qu’elle soit précise. Maintenant, pour répondre à la question:

Comment savoir dans le cas général si deux formes convexes se croisent?

Je vais vous donner un algorithme qui fonctionne pour toutes les formes convexes et pas seulement les hexagones.

Supposons que X et Y sont deux formes convexes. Elles se croisent si et seulement si elles ont un point commun, c'est-à-dire qu'il existe un point x ∈ X et un point y ∈ Y tel que x = y . Si vous considérez l'espace comme un espace vectoriel, cela revient à dire x - y = 0 . Et maintenant nous arrivons à cette affaire Minkowski:

La somme de Minkowski de X et Y est l'ensemble de tout x + y pour x ∈ X et y ∈ Y .

Un exemple pour X et Y

X, Y et leur somme de Minkowski, X + Y

En supposant que (-Y) est l'ensemble de tout -y pour y ∈ Y , alors vu le paragraphe précédent, X et Y se croisent si et seulement si X + (-Y) contient 0 , c'est-à-dire l'origine .

Remarque secondaire: pourquoi écris-je X + (-Y) au lieu de X - Y ? Eh bien, parce qu’en mathématiques, il existe une opération appelée différence de Minkowski de A et B qui s’écrit parfois X - Y et qui n’a pourtant rien à voir avec l’ensemble des x - y pour x ∈ X et y Y (le vrai Minkowski). la différence est un peu plus complexe).

Nous aimerions donc calculer la somme de Minkowski de X et -Y et déterminer si elle contient l'origine. L'origine n'est pas spéciale par rapport à un autre point, de sorte que pour déterminer si l'origine est dans un certain domaine, nous utilisons un algorithme qui pourrait nous indiquer si un point donné appartient à ce domaine.

La somme de Minkowski de X et Y a une propriété cool, qui est que si X et Y sont convexes, alors X + Y est aussi. Et il est beaucoup plus facile de savoir si un point appartient à un ensemble convexe que si cet ensemble n'était pas (connu pour être) convexe.

Nous ne pouvons pas calculer tous les x - y pour x ∈ X et y Y car il existe une infinité de tels points x et y , alors espérons-le, puisque X , Y et X + Y sont convexes, nous pouvons simplement utiliser les points "les plus à l'extérieur" définissant les formes X et Y , qui sont leurs sommets, et nous obtiendrons les points les plus à l'extérieur de X + Y , ainsi que d'autres.

Ces points supplémentaires sont "entourés" par les points les plus externes de X + Y, de sorte qu'ils ne contribuent pas à définir la forme convexe obtenue. Nous disons qu'ils ne définissent pas la " coque convexe " de l'ensemble des points. Donc, ce que nous faisons, c'est que nous nous en débarrassons en préparation de l'algorithme final qui nous indique si l'origine est dans la coque convexe.

La coque convexe de X + Y. Nous avons supprimé les sommets "intérieurs".

Nous avons donc

Un premier algorithme naïf

boolean intersect(Shape X, Shape Y) {

  SetOfVertices minkowski = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      minkowski.addVertice(x-y);
    }
  }
  return contains(convexHull(minkowski), Vector2D(0,0));

}

Les boucles ont évidemment une complexité O (mn) où m et n sont le nombre de sommets de chaque forme. L' minkoswkiensemble contient au plus mn éléments. L' convexHullalgorithme a une complexité qui dépend de l'algorithme que vous avez utilisé , et vous pouvez viser O (k log (k)), où k est la taille de l'ensemble des points. Dans notre cas, nous obtenons donc O (mn log (mn) ) . L' containsalgorithme a une complexité linéaire avec le nombre d'arêtes (en 2D) ou de faces (en 3D) de la coque convexe, donc cela dépend vraiment de vos formes de départ, mais ne sera pas supérieur à O (mn). .

Je vais vous laisser google pour l' containsalgorithme pour les formes convexes, c'est un assez commun. Je peux le mettre ici si j'en ai le temps.

Mais c’est la détection de collision que nous effectuons afin de pouvoir l’optimiser beaucoup

À l’origine, deux corps A et B se déplaçaient sans rotation pendant un dt de temps (d'après ce que je peux dire en regardant vos images). Appelons v _A et v _B les vitesses respectives de A et B , qui sont constantes pendant notre pas de temps de durée dt . Nous obtenons ce qui suit:

et, comme vous le signalez dans vos images, ces corps balayent des zones (ou des volumes en 3D) au fur et à mesure qu'ils se déplacent:

et ils finissent comme A ' et B' après le pas de temps.

Pour appliquer notre algorithme naïf ici, il suffirait de calculer les volumes balayés. Mais nous ne faisons pas cela.

Dans le repère de B , B ne bouge pas (duh!). Et A a une certaine vitesse par rapport à B que vous obtenez en calculant v _A - v _B (vous pouvez faire l’inverse, calculer la vitesse relative de B dans le repère de A ).

De gauche à droite: vitesses dans le repère de base; vitesses relatives; calcul des vitesses relatives.

En ce qui concerne B comme immobile dans son propre cadre de référence, il suffit de calculer le volume A balaye comme il se déplace au cours dt avec sa vitesse relative v _A - v _B .

Cela diminue le nombre de sommets à utiliser dans le calcul de la somme de Minkowski (parfois considérablement).

Une autre optimisation possible est au point où vous calculez le volume balayé par l’un des corps, disons A. Il n’est pas nécessaire de traduire tous les sommets composant A. Seuls ceux qui appartiennent à des arêtes (faces en 3D) dont extérieur normal "face" la direction du balayage. Vous avez sûrement déjà remarqué cela lorsque vous avez calculé vos zones balayées pour les carrés. Vous pouvez déterminer si une normale se situe dans le sens de balayage en utilisant son produit scalaire avec le sens de balayage, ce qui doit être positif.

La dernière optimisation, qui n'a rien à voir avec votre question concernant les intersections, est vraiment utile dans notre cas. Il utilise les vitesses relatives mentionnées ci-dessus et la méthode dite de séparation des axes. Vous le savez sûrement déjà.

Supposons que vous connaissiez les rayons de A et B par rapport à leurs centres de masse (c’est-à-dire la distance entre le centre de masse et le sommet le plus éloigné de celui-ci), comme ceci:

Une collision peut se produire que s'il est possible que le cercle de délimitation de A rencontre celui de B . Nous voyons ici que ce ne sera pas, et la façon de dire l'ordinateur qui est de calculer la distance de C _B à I comme dans l'image ci - dessous et assurez - vous qu'il est plus grand que la somme des rayons de A et B . Si c'est plus gros, pas de collision. Si c'est plus petit, alors collision.

Cela ne fonctionne pas très bien avec les formes qui sont plutôt longues, mais dans le cas de carrés ou d'autres formes similaires, c'est une très bonne heuristique pour éliminer les collisions. .

Le théorème des axes séparateurs appliqué à B et le volume balayé par A vous indiquent toutefois si la collision se produit ou non. La complexité de l'algorithme associé est linéaire avec la somme des nombres de sommets de chaque forme convexe, mais elle est moins magique au moment de gérer réellement la collision.

Notre nouvel algorithme, plus performant, utilise les intersections pour détecter les collisions, mais n'est pas aussi performant que le théorème des axes séparateurs pour indiquer si une collision se produit ou non.

boolean mayCollide(Body A, Body B) {

  Vector2D relativeVelocity = A.velocity - B.velocity;
  if (radiiHeuristic(A, B, relativeVelocity)) {
    return false; // there is a separating axis between them
  }

  Volume sweptA = sweptVolume(A, relativeVelocity);
  return contains(convexHull(minkowskiMinus(sweptA, B)), Vector2D(0,0));

}

boolean radiiHeuristic(A, B, relativeVelocity)) {
  // the code here
}

Volume convexHull(SetOfVertices s) {
  // the code here
}

boolean contains(Volume v, Vector2D p) {
  // the code here
}

SetOfVertices minkowskiMinus(Body X, Body Y) {

  SetOfVertices result = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      result.addVertice(x-y);
    }
  }
  return result;

}

Je ne pense pas que l'utilisation de l'hexagone soit utile. Voici un schéma permettant d’obtenir des collisions exactes pour les rectangles alignés sur l’axe:

Deux rectangles alignés sur des axes se chevauchent si et seulement si leurs plages de coordonnées X se chevauchent et si leurs plages de coordonnées Y se chevauchent. (Cela peut être considéré comme un cas particulier du théorème des axes de séparation.) En d'autres termes, si vous projetez les rectangles sur les axes X et Y, vous réduisez le problème à deux intersections ligne à ligne.

Calculez l' intervalle de temps sur lequel les deux lignes d'un axe se croisent (par exemple, il commence à l'heure (séparation actuelle des objets / vitesse relative d'approche des objets)) et procédez de la même manière pour l'autre axe. Si ces intervalles de temps se chevauchent, le temps le plus tôt dans le chevauchement est le moment de la collision.

Je ne pense pas qu'il existe un moyen facile de calculer la collision de polygones avec plus de côtés qu'un rectangle. Je le décomposerais en formes primitives telles que des lignes et des carrés:

function objectsWillCollide(object1,object2) {
    var lineA, lineB, lineC, lineD;
    //get projected paths of objects and store them in the 'line' variables

    var AC = lineCollision(lineA,lineC);
    var AD = lineCollision(lineA,lineD);
    var BC = lineCollision(lineB,lineC);
    var BD = lineCollision(lineB,lineD);
    var objectToObjectCollision = rectangleCollision(object1.getRectangle(), object2.getRectangle());

    return (AC || AD || BC || BD || objectToObjectCollision);
}

Notez que j'ignore l'état de démarrage de chaque objet, car cela aurait dû être vérifié lors du calcul précédent.

Théorème d'axe séparé

Le théorème des axes séparés dit "Si nous pouvons trouver un axe sur lequel deux formes convexes ne se croisent pas, les deux formes ne se croisent pas" ou plus facilement réalisable pour l'informatique:

"Deux formes convexes ne se croisent que si elles se croisent sur tous les axes possibles."

Pour les rectangles alignés sur les axes, il y a exactement 2 axes possibles: x et y. Mais le théorème n'est pas limité aux rectangles, il peut s'appliquer à n'importe quelle forme convexe en ajoutant simplement les autres axes sur lesquels les formes pourraient se croiser. Pour plus de détails sur le sujet, consultez ce tutoriel du développeur de N: http://www.metanetsoftware.com/technique/tutorialA.html#section1

Mis en œuvre, il ressemble à ceci:

axes = [... possible axes ...];
collision = true;
for every index i of axes
{
  range1[i] = shape1.getRangeOnAxis(axes[i]);
  range2[i] = shape2.getRangeOnAxis(axes[i]);
  rangeIntersection[i] = range1[i].intersectionWith(range2[i]);
  if(rangeIntersection[i].length() <= 0)
  {
    collision = false;
    break;
  }
}

Les axes peuvent être aussi représentés que des vecteurs normalisés.

Une plage est une ligne à 1 dimension. Le début doit être défini sur le plus petit point projeté, la fin sur le point le plus grand projeté.

Application au rectangle "balayé"

L'hexagone dans la question est produit en "balayant" l'AABB de l'objet. Le balayage ajoute exactement un axe de collision possible à n'importe quelle forme: le vecteur de mouvement.

shape1 = sweep(originalShape1, movementVectorOfShape1);
shape2 = sweep(originalShape2, movementVectorOfShape2);

axes[0] = vector2f(1.0, 0.0); // X-Axis
axes[1] = vector2f(0.0, 1.0); // Y-Axis
axes[2] = movementVectorOfShape1.normalized();
axes[3] = movementVectorOfShape2.normalized();

Jusqu'ici tout va bien, nous pouvons déjà vérifier si les deux hexagones se croisent. Mais c'est encore mieux.

Cette solution fonctionnera pour toutes les formes convexes (par exemple les triangles) et toutes les formes convexes balayées (par exemple les octogones balayés). Cependant, plus la forme est complexe, moins elle sera efficace.

Bonus: Où la magie se produit.

Comme je l'ai dit, les seuls axes supplémentaires sont les vecteurs de mouvement. Le mouvement est le temps multiplié par la vitesse, de sorte qu’il ne s’agit pas uniquement d’axes spatiaux, mais d’axes spatio-temporels.

Cela signifie que nous pouvons déduire le temps dans lequel la collision aurait pu se produire à partir de ces deux axes. Pour cela, nous devons trouver l'intersection entre les deux intersections sur les axes de mouvement. Avant de pouvoir le faire, nous devons cependant normaliser les deux plages afin de pouvoir les comparer.

shapeRange1 = originalShape1.getRangeOnAxis(axes[2]);
shapeRange2 = originalShape2.getRangeOnAxis(axes[3]);
// Project them on a scale from 0-1 so we can compare the time ranges
timeFrame1 = (rangeIntersection[2] - shapeRange1.center())/movementVectorOfShape1.project(axes[2]);
timeFrame2 = (rangeIntersection[3] - shapeRange2.center())/movementVectorOfShape2.project(axes[3]);
timeIntersection = timeFrame1.intersectionWith(timeFrame2);

Lorsque j'ai posé cette question, j'ai un peu déjà accepté le compromis selon lequel il y aurait quelques rares faux positifs avec cette méthode. Mais je me suis trompé. En vérifiant cette intersection temporelle, nous pouvons vérifier si la collision s'est réellement produite et résoudre ces faux positifs:

if(collision)
{
  [... timeIntersection = see above ...]
  if(timeIntersection.length() <= 0)
    collision = false;
  else
    collisionTime = timeIntersection.start; // 0: Start of the frame, 1: End of the frame
}

Si vous remarquez des erreurs dans les exemples de code, faites-le-moi savoir, je ne l'ai pas encore implémenté et je n'ai donc pas pu le tester.

Tant que les zones balayées sont toutes les deux fermées (pas de trous dans la limite formée par les lignes de contour), les opérations suivantes fonctionneront (réduisez simplement vos tests de collision en ligne à ligne et point-rect / point-tri):

1. Est-ce que leurs bords se touchent? (collisions ligne à ligne) Vérifiez si une ligne de bord d'une zone balayée croise une ligne de bord de l'autre zone balayée. Chaque zone balayée a 6 côtés.

2. Le petit est-il à l'intérieur du grand? (Utilisez des formes alignées sur les axes (point-rect et point-tri)) Réorientez (faites pivoter) les zones balayées de sorte que la plus grande soit alignée sur un axe et testez si la plus petite est interne (en vérifiant si des points d'angle ( doit être tout ou rien) se trouvent dans la zone balayée alignée sur l'axe). Ceci est fait en décomposant votre hexagone en tris et rects.

Le test que vous effectuez en premier dépend de la probabilité de chacun (faites le premier le plus souvent).

Vous trouverez peut-être plus facile d’utiliser un cercle englobant balayé (une capsule plutôt qu’un hex) car il est plus facile de le scinder en deux demi-cercles et un rectangle quand il est aligné sur l’axe. ..Je vais vous laisser dessiner la solution