CODEWITHSUNDEEP
c++algorithm3dcollision-detection
0x5453
0x5453

Reputation: 13599

3D Collision resolution, moving AABB + polyhedron

I have been writing a game engine in my free time, but I've been stuck for a couple weeks trying to get collisions working.

Currently I am representing entities' colliders with AABBs, and the collider for a level is represented by a fairly simple (but not necessarily convex) polyhedron. All the drawing is sprite-based but the underlying collision code is 3D.

I've got AABB/triangle collision detection working using this algorithm, (which I can naively apply to every face in the level mesh), but I am stuck trying to resolve the collision after I have detected its existence.

The algorithm I came up with works pretty well, but there are some edge cases where it breaks. For example, walking straight into a sharp corner will always push the player to one side or the other. Or if a small colliding face happens to have a normal that is closer to the players direction of movement than all other faces, it will "pop" the player in that direction first, even though using the offset from a different face would have had a better result.

For reference, my current algorithm looks like:

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

And here's the implementation:

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

I have been messing with sorting the colliding faces by "collision distance in the direction of player movement", but I haven't yet figured out an efficient way to find that distance value for all faces.

Does anybody know of an algorithm that would work better for what I am trying to accomplish?

Upvotes: 2

Views: 905

Answers (1)

quanke0801
quanke0801

Reputation: 41

I'm quite suspicious with the first part of code. You modify the entity's position in each iteration, am I right? That might be able to explain the weird edge cases.

In a 2D example, if a square walks towards a sharp corner and collides with both walls, its position will be modified by one wall first, which makes it penetrate more into the second wall. And then the second wall changes its position using a larger scale value, so that it seems the square is pushed only by one wall.

If a collision happens where the surface S's normal is close to the player's movement, it will be handled later than all other collisions. Note that when dealing with other collisions, the player's position is modified, and likely to penetrate more into surface S. So at last the program deal with collision with surface S, which pops the player a lot.

I think there's a simple fix. Just compute the penetrations at once, and use a temporal variable to sum up all the displacement and then change the position with the total displacement.

Upvotes: 0

Related Questions