Trouver le point de contact avec SAT

Le théorème de l'axe de séparation (SAT) facilite la détermination du vecteur de translation minimum, c'est-à-dire le vecteur le plus court pouvant séparer deux objets en collision. Cependant, ce dont j'ai besoin, c'est du vecteur qui sépare les objets le long du vecteur que se déplace l'objet pénétrant (c'est-à-dire le point de contact).

J'ai dessiné une image pour aider à clarifier. Il y a une case, passant de la position avant à la position après. Dans sa position après, il coupe le polygone gris. SAT peut facilement renvoyer le MTV, qui est le vecteur rouge. Je cherche à calculer le vecteur bleu.

Ma solution actuelle effectue une recherche binaire entre les positions avant et après jusqu'à ce que la longueur du vecteur bleu soit connue à un certain seuil. Cela fonctionne mais c'est un calcul très coûteux car la collision entre les formes doit être recalculée à chaque boucle.

Existe-t-il un moyen plus simple et / ou plus efficace de trouver le vecteur de point de contact?

Ce dont vous parlez est assez difficile si vous le structurez comme d'abord déplacer un objet, puis tester la collision, puis reculer jusqu'à ce que vous soyez hors de l'objet. Il vaut probablement mieux considérer cela comme un test d'intersection dynamique : un objet en mouvement contre un objet stationnaire.

Heureusement, la séparation des tests d'axe peut vous aider ici! Voici une description de l'algorithme, gracieuseté de Ron Levine :

L'algorithme va comme ça. Vous travaillez avec le vecteur de vitesse relative des deux corps convexes. La projection de chacun des deux corps et du vecteur de vitesse relative sur un axe de séparation particulier à t ₀ donne deux intervalles 1-D et une vitesse 1-D, de sorte qu'il est facile de dire si les deux intervalles se coupent, et sinon, si ils se séparent ou se déplacent ensemble. S'ils sont séparés et s'écartent sur l'un des axes de séparation (ou, en fait, sur n'importe quel axe), alors vous savez qu'il n'y a pas de collision future. Si sur un axe de séparation, les deux intervalles projetés se coupent en t₀ ou sont séparés et se déplacent ensemble, alors il est facile de calculer (par deux expressions linéaires 1D simples) le premier moment futur auquel les deux intervalles se coupent pour la première fois et (en supposant un mouvement rectiligne continu) le dernier moment futur auquel les deux les intervalles se croisent et commencent à s'écarter. (S'ils se coupent à t ₀, le premier moment d'intersection futur est t ₀). Faites cela pour au plus tous les axes de séparation. Si le maximum sur tous les axes du premier temps d'intersection futur est inférieur au minimum sur tous les axes du dernier temps d'intersection futur, alors ce temps d'intersection futur maximum le plus tôt est le moment exact de la première collision des deux polyèdres 3D, sinon il n'est pas une collision à l'avenir.

En d'autres termes, vous parcourez tous les axes comme vous le feriez normalement dans un test d'axe de séparation statique. Au lieu de sortir tôt si vous ne trouvez aucun chevauchement, vous continuez et vérifiez la vitesse projetée de l'objet en mouvement. Si elle se déplace loin de l'objet statique, alors vous tôt au départ. Sinon, vous pouvez résoudre assez facilement le premier et le dernier temps de contact (c'est un intervalle 1D qui se déplace vers un autre intervalle 1D). Si vous faites cela pour tous les axes et que vous gardez le maximum du premier temps d'intersection et le minimum du dernier temps d'intersection, alors vous savez si votre objet en mouvement va frapper l'objet statique, ainsi que quand. Vous pouvez donc faire avancer votre objet en mouvement exactement jusqu'au point où il heurtera l'objet statique.

Voici un pseudocode approximatif et entièrement non vérifié pour l'algorithme:

t_min := +∞
t_max := -∞
foreach axis in potential_separating_axes
    a_min := +∞
    a_max := -∞
    foreach vertex in a.vertices
        a_min = min(a_min, vertex · axis)
        a_max = max(a_max, vertex · axis)
    b_min := +∞
    b_max := -∞
    foreach vertex in b.vertices
        b_min = min(b_min, vertex · axis)
        b_max = max(b_max, vertex · axis)
    v := b.velocity · axis
    if v > 0 then
        if a_max < b_min then
            return no_intersection
        else if (a_min < b_min < a_max) or (b_min < a_min < b_max) then
            t_min = min(t_min, (a_max - b_min) / v)
            t_max = max(t_max, 0)
        else
            t_min = min(t_min, (a_max - b_min) / v)
            t_max = max(t_max, (a_min - b_max) / v)
    else if v < 0 then
        // repeat the above case with a and b swapped
    else if v = 0 then
        if a_min < b_max and b_min < a_max then
            t_min = min(t_min, 0)
            t_max = max(t_max, 0)
        else
            return no_intersection
if t_max < t_min then
    // advance b by b.velocity * t_max
    return intersection
else
    return no_intersection

Voici un article sur Gamasutra qui parle de cette implémentation pour quelques tests primitifs différents. Notez que tout comme SAT, cela nécessite des objets convexes.

En outre, c'est un peu plus compliqué qu'un simple test d'axe de séparation. Soyez absolument sûr que vous en avez besoin avant de l'essayer. Un très grand nombre de jeux poussent simplement les objets les uns des autres le long du vecteur de traduction minimum, car ils ne pénètrent tout simplement pas très loin les uns dans les autres sur une image donnée et c'est à peu près imperceptible visuellement.

Vous souhaitez utiliser l'écrêtage polygonal. C'est mieux expliqué avec des photos, que je n'ai pas, mais ce type l'a fait, alors je vais le laisser l'expliquer.

http://www.codezealot.org/archives/394

Le collecteur de contacts renvoie un point sur l'un des objets qui est "le plus responsable" de la collision, et non le point direct de la collision. Cependant, vous n'avez pas vraiment besoin de ce point de collision directe. Vous pouvez simplement éloigner les objets en utilisant la profondeur de pénétration et la normale que vous avez déjà, et utiliser le collecteur de contact pour appliquer d'autres effets physiques (faire dégringoler / rouler la boîte sur la pente, par exemple).

Notez que votre image illustre un petit problème: le point sur le vecteur bleu que vous demandez ne sera trouvé dans aucune simulation physique, car ce n'est pas vraiment là que la boîte frapperait. La boîte frapperait avec son coin en bas à gauche quelque part plus haut sur la pente car juste un petit coin pénètre.

La profondeur de pénétration sera relativement petite, et le simple fait de pousser la boîte hors de la pente le long de la normale de pénétration mettra la boîte suffisamment près de la position "correcte" pour être presque imperceptible dans la pratique, surtout si la boîte va rebondir, dégringoler ou glissez ensuite de toute façon.

Projetez simplement le vecteur MAT sur le vecteur direction. Le vecteur résultant peut être ajouté au vecteur de direction pour compenser la pénétration. Projetez-le de la même manière, comme vous le faites sur l'Axe lorsque vous effectuez le SAT. Cela place l'objet exactement sur la position où il touche l'autre objet. Ajoutez un petit epsilon pour lutter contre les problèmes de virgule flottante.

Il y a quelques mises en garde à ma réponse, que je vais aborder en premier: elle ne concerne que les boîtes englobantes non tournantes. Il suppose que vous essayez de traiter les problèmes de tunneling , c'est-à-dire les problèmes causés par des objets se déplaçant à grande vitesse.

Une fois que vous avez identifié le MTV, vous connaissez le bord / la surface normale que vous devez tester. Vous connaissez également le vecteur de vitesse linéaire de l'objet interpénétré.

Une fois que vous avez établi qu'à un moment donné de l'image, une intersection s'est produite, vous pouvez ensuite effectuer des opérations binaires en demi-pas, en fonction des points de départ suivants: Identifiez le sommet qui a pénétré en premier pendant l'image:

vec3 vertex;
float mindot = FLT_MAX;
for ( vert : vertices )
{
    if (dot(vert, MTV) < mindot)
    {
         mindot = dot(vert, MTV);
         vertex = vert;
    }
}

Une fois le sommet identifié, le demi-pas binaire devient beaucoup moins cher:

//mindistance is the where the reference edge/plane intersects it's own normal. 
//The max dot product of all vertices in B along the MTV will get you this value.
halfstep = 1.0f;
vec3 cp = vertex;
vec3 v = A.velocity*framedurationSeconds;
float errorThreshold = 0.01f; //choose meaningful value here
//alternatively, set the while condition to be while halfstep > some minimum value
while (abs(dot(cp,normal)) > errorThreshold)
{            
    halfstep*=0.5f;
    if (dot(cp,normal) < mindistance) //cp is inside the object, move backward
    {
        cp += v*(-1*halfstep);
    }
    else if ( dot(cp,normal) > mindistance) //cp is outside, move it forward
    {
        cp += v*(halfstep);
    }
}

return cp;

Ceci est raisonnablement précis, mais ne fournira qu'un seul point de collision, dans un seul cas.

Le fait est qu'il est généralement possible de dire à l'avance si un objet se déplacera assez rapidement par image pour pouvoir tunneler comme ça, donc le meilleur conseil est d'identifier les sommets principaux le long de la vitesse et de faire un test de rayon le long du vecteur de vitesse. Dans le cas d'objets en rotation, vous devrez effectuer une sorte de slerp binaire à demi-pas afin de déterminer le bon point de contact.

Dans la plupart des cas, cependant, on peut supposer en toute sécurité que la plupart des objets de votre scène ne se déplaceront pas assez rapidement pour pénétrer aussi loin dans une seule image, donc aucun demi-pas n'est nécessaire, et une détection de collision discrète suffira. Les objets à grande vitesse comme les balles, qui se déplacent trop vite pour être vus, peuvent être tracés par rayons pour les points de contact.

Fait intéressant, cette méthode à mi-étape peut également vous donner l'heure (presque) exacte à laquelle l'objet s'est produit pendant la trame:

float collisionTime = frametimeSeconds * halfstep;

Si vous effectuez une sorte de résolution de collision physique, vous pouvez alors corriger la position de A en:

v - (v*halfstep)

alors vous pouvez faire votre physique normalement à partir de là. L'inconvénient est que si l'objet se déplace assez rapidement, vous le verrez se téléporter le long de son vecteur de vitesse.