Résolution 3D Collision, déplacement AABB + polyèdre

Question

J'ai écrit un moteur de jeu pendant mon temps libre, mais j'ai été bloqué pendant quelques semaines pour essayer de faire fonctionner les collisions. Actuellement, je représente les collisionneurs d'entités avec des AABB, et le collisionneur pour un niveau est représenté par un polyèdre assez simple (mais pas nécessairement convexe). Tous les dessins sont basés sur des sprites mais le code de collision sous-jacent est 3D. J'ai la détection de collision AABB/triangle en utilisant l'algorithme this, (que je peux appliquer naïvement à chaque visage dans le maillage de niveau), mais je suis coincé en essayant de résoudre la collision après avoir détecté son existence.

L'algorithme que j'ai trouvé fonctionne plutôt bien, mais il y a des cas limites où il casse. Par exemple, marcher droit dans un coin pointu va toujours pousser le joueur d'un côté ou de l'autre. Ou si un petit visage entrant en collision a une normale qui est plus proche de la direction du mouvement du joueur que tous les autres visages, il "pop" d'abord le joueur dans cette direction, même si l'utilisation du décalage d'un visage différent aurait meilleur résultat.

Pour référence, mon algorithme actuel ressemble:

Create list of all colliding faces 
Sort list in increasing order of the angle between face normal and negative direction of entity movement (i.e. process faces with the most "stopping power" first) 
For each colliding face in collision list: 
    scale = distance of collision along face normal 
    Entity position += face normal * scale 
    If no more collision: 
     break 

Et voici la mise en œuvre:

void Mesh::handleCollisions(Player& player) const 
{ 
    using Face = Face<int32_t>; 
    BoundingBox<float> playerBounds = player.getGlobalBounds(); 
    Vector3f negPlayerDelta = -player.getDeltaPos(); // Negative because face norm should be opposite direction of player dir 

    auto comparator = [&negPlayerDelta](const Face& face1, const Face& face2) { 
     const Vector3f norm1 = face1.normal(); 
     const Vector3f norm2 = face2.normal(); 
     float closeness1 = negPlayerDelta.dot(norm1)/(negPlayerDelta.magnitude() * norm1.magnitude()); 
     float closeness2 = negPlayerDelta.dot(norm2)/(negPlayerDelta.magnitude() * norm2.magnitude()); 
     return closeness1 > closeness2; 
    }; 

    std::vector<Face> collidingFaces; 
    for (const Face& face : _faces) 
    { 
     ::Face<float> floatFace(face); 
     if (CollisionHelper::collisionBetween(playerBounds, floatFace)) 
     { 
      collidingFaces.push_back(face); 
     } 
    } 
    if (collidingFaces.empty()) { 
     return; 
    } 
    // Process in order of "closeness" between player delta and face normal 
    std::sort(collidingFaces.begin(), collidingFaces.end(), comparator); 

    Vector3f totalOffset; 
    for (const Face& face : collidingFaces) 
    { 
     const Vector3f& norm = face.normal().normalized(); 
     Point3<float> closestVert(playerBounds.xMin, playerBounds.yMin, playerBounds.zMin); // Point on AABB that is most negative in direction of norm 
     if (norm.x < 0) 
     { 
      closestVert.x = playerBounds.xMax; 
     } 
     if (norm.y < 0) 
     { 
      closestVert.y = playerBounds.yMax; 
     } 
     if (norm.z < 0) 
     { 
      closestVert.z = playerBounds.zMax; 
     } 
     float collisionDist = closestVert.vectorTo(face[0]).dot(norm); // Distance from closest vert to face 
     Vector3f offset = norm * collisionDist; 
     BoundingBox<float> newBounds(playerBounds + offset); 
     totalOffset += offset; 
     if (std::none_of(collidingFaces.begin(), collidingFaces.end(), 
         [&newBounds](const Face& face) { 
          ::Face<float> floatFace(face); 
          return CollisionHelper::collisionBetween(newBounds, floatFace); 
         })) 
     { 
      // No more collision; we are done 
      break; 
     } 
    } 
    player.move(totalOffset); 
    Vector3f playerDelta = player.getDeltaPos(); 
    player.setVelocity(player.getDeltaPos()); 
} 

Je suis de déconner avec le tri des visages entrant en collision par « distance de collision dans le sens du joueur mouvement ", mais je n'ai pas encore trouvé un moyen efficace de trouver cette valeur de distance pour tous les visages.

Est-ce que quelqu'un connaît un algorithme qui fonctionnerait mieux pour ce que j'essaie d'accomplir?

Answer 1

Je suis assez suspect avec la première partie du code. Vous modifiez la position de l'entité à chaque itération, ai-je raison? Cela pourrait être en mesure d'expliquer les cas de bord étranges.

Dans un exemple 2D, si un carré marche vers un coin pointu et entre en collision avec les deux murs, sa position sera modifiée par une paroi en premier, ce qui le fera pénétrer plus dans la deuxième paroi. Et puis la deuxième paroi change de position en utilisant une valeur d'échelle plus grande, de sorte qu'il semble que le carré ne soit poussé que par un mur.

Si une collision se produit lorsque la normale de la surface S est proche du mouvement du joueur, elle sera traitée plus tard que toutes les autres collisions. Notez que lorsque vous faites face à d'autres collisions, la position du joueur est modifiée et est susceptible de pénétrer davantage dans la surface S. Ainsi, le programme traite enfin de la collision avec la surface S, ce qui fait beaucoup de bruit sur le joueur.

Je pense qu'il existe une solution simple. Il suffit de calculer les pénétrations à la fois, et d'utiliser une variable temporelle pour résumer tout le déplacement et ensuite changer la position avec le déplacement total.