3D Разрешение столкновений, перемещение AABB + многогранник

Question

Я пишу игровой движок в свободное время, но за пару недель я пытаюсь заставить столкновения работать.

В настоящее время я представляю коллайдеры объектов с AABB, а коллайдер для уровня представлен довольно простым (но не обязательно выпуклым) многогранником. Весь чертеж основан на спрайте, но основной код столкновения - 3D.

У меня обнаружено обнаружение столкновения AABB/треугольника, используя алгоритм this (который я могу наивно применять к каждому лицу в уровневой сетке), но я застреваю, пытаясь разрешить столкновение после того, как я обнаружил его существование.

Алгоритм, который я придумал, работает очень хорошо, но есть случаи, когда он ломается. Например, прохождение прямо в острый угол всегда будет подталкивать игрока в ту или другую сторону. Или, если у маленького сталкивающегося лица есть нормальный, который ближе к направлению движения игроков, чем все другие лица, он сначала «поп» игрока в этом направлении, хотя использование смещения с другого лица будет иметь лучший результат.

Для справки, мой текущий алгоритм выглядит следующим образом:

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 

А вот реализация:

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()); 
} 

Я Мессинг с сортировкой сталкивающихся забоев «расстояния столкновения в направлении игрока движение ", но я еще не нашел эффективного способа найти это значение расстояния для всех лиц.

Кто-нибудь знает об алгоритме, который будет работать лучше для того, что я пытаюсь выполнить?

Answer 1

Я очень подозрительно отношусь к первой части кода. Вы изменяете позицию лица на каждой итерации, верно? Это могло бы объяснить странные краевые случаи.

В 2D-примере, если квадрат подходит к острому углу и сталкивается с обеими стенами, его положение будет сначала изменено на одну стенку, что сделает его более проникающим во вторую стену. И затем вторая стена меняет свое положение, используя большее значение масштаба, так что кажется, что квадрат выталкивается только одной стеной.

Если произошло столкновение, когда нормальная поверхность S близка к движению игрока, она будет обработана позже всех других столкновений. Обратите внимание, что при работе с другими коллизиями позиция игрока изменяется и, вероятно, проникает больше в поверхность S. Таким образом, наконец, программа имеет дело с столкновением с поверхностью S, которая много выталкивает игрока.

Я думаю, что есть простое исправление. Просто вычислите проходы сразу и используйте временную переменную, чтобы суммировать все смещения, а затем изменить положение с полным перемещением.