[Collisions] Implement separatin Axis Theorem for Collision System

[trommlbomml]

This would be an improvement for the existing collision system in the near phase. This extension was rejected from the MonoGame core project and is recommended to be implemented here. I would provide an implementation which will work with any convex shape. Additionally, it is a fast algorithm for finding out if two shapes collide and how to separate them properly.

[lithiumtoast]

@trommlbomml Hi,

Check out #74

Currently I need to finish PrimitiveBatch (see #152) before I can start #74 as I need an efficient way to draw convex shapes. Once PrimitiveBatch is done I'll be designing the collision system code.

Here's my separating axis theorem from my old code. The design of the code will probably change since I have to decouple the Entity Component System from collision objects for MonoGame.Extended

    public class SeperatingAxisNarrowphaseSolver : INarrowphaseSolver
    {
        NarrowphaseCollisionResult INarrowphaseSolver.Solve(Entity entityA, Entity entityB)
        {
            var collidableA = entityA.Components.Get<CollisionComponent>();
            var collidableB = entityB.Components.Get<CollisionComponent>();

            if (collidableA == null || collidableA.CollisionShape == null || collidableB == null ||
                collidableB.CollisionShape == null)
                return new NarrowphaseCollisionResult(entityA, entityB, Vector2.Zero);

            // Get the first shape.
            var shapeA = collidableA.CollisionShape;
            // Get the second shape.
            var shapeB = collidableB.CollisionShape;

            // If either shapes are not defined, then we can't solve this collision; abort with no collision.
            if (shapeA == null || shapeB == null)
                return new NarrowphaseCollisionResult(entityA, entityB, Vector2.Zero);

            // Initialize the minimum translation to a really large value so we garantee that any projection overlap is smaller.
            // This value will be the minimum required translation to seperate the two collidable objects.
            var minimumTranslation = float.MaxValue;
            // Initialize the minimum translation axis.
            // This value will be the axis which the minimum translation was found.
            var minimumTranslationAxis = Vector2.Zero;

            // Loop through all the axes for the first shape.
            // ReSharper disable ForCanBeConvertedToForeach
            for (var i = 0; i < shapeA.TransformedNormals.Count; i++)
                // ReSharper restore ForCanBeConvertedToForeach
            {
                // Get the transformed axis.
                var transformedAxis = shapeA.TransformedNormals[i];
                // Calculate the projection of the first shape.
                var projectionA = shapeA.Project(ref transformedAxis);
                // Calculate the projection of the second shape.
                var projectionB = shapeB.Project(ref transformedAxis);
                // projection.X = min, projection.Y = max

                // Determine if the projections do not overlap.
                if (projectionA.Y < projectionB.X || projectionB.Y < projectionA.X)
                    // Projections do not overlap, return a no collision result.
                    return new NarrowphaseCollisionResult(entityA, entityB, Vector2.Zero);

                // Projections overlap.
                // Calculate the projection overlap.
                var projectionOverlap = projectionA.Y < projectionB.Y
                    ? projectionA.Y - projectionB.X
                    : projectionB.Y - projectionA.X;

                // Check if the projection overlap is the new smallest translation.
                if (projectionOverlap >= minimumTranslation)
                    continue;

                minimumTranslation = projectionOverlap;
                minimumTranslationAxis = transformedAxis;
            }

            // Loop through all the axes for the second shape.
            // ReSharper disable ForCanBeConvertedToForeach
            for (var i = 0; i < shapeB.TransformedNormals.Count; i++)
                // ReSharper restore ForCanBeConvertedToForeach
            {
                // Get the transformed axis.
                var transformedAxis = shapeB.TransformedNormals[i];
                // Transform the axis.
                // Calculate the projection of the first shape.
                var projectionA = shapeA.Project(ref transformedAxis);
                // Calculate the projection of the second shape.
                var projectionB = shapeB.Project(ref transformedAxis);
                // projection.X = min, projection.Y = max

                // Determine if the projections do not overlap.
                if (projectionA.Y < projectionB.X || projectionB.Y < projectionA.X)
                {
                    // Projections do not overlap, return a no collision result.
                    return new NarrowphaseCollisionResult(entityA, entityB, Vector2.Zero);
                }

                // Projections overlap

                // Calculate the projection overlap.
                var projectionOverlap = projectionA.Y < projectionB.Y
                    ? projectionA.Y - projectionB.X
                    : projectionB.Y - projectionA.X;

                // Check if the projection overlap is the new smallest translation.
                if (projectionOverlap >= minimumTranslation)
                    continue;

                minimumTranslation = projectionOverlap;
                minimumTranslationAxis = transformedAxis;
            }

            // Determine if we need to flip our translation axis.
            var centerEdge = shapeA.TransformedCentroid - shapeB.TransformedCentroid;
            if (Vector2.Dot(centerEdge, minimumTranslationAxis) < 0)
                minimumTranslationAxis *= -1;

            var penetration = minimumTranslationAxis * minimumTranslation;

            // No seperating axis was found, every axis has a projection overlap; return the collision result.
            return new NarrowphaseCollisionResult(entityA, entityB, penetration);
        }
    }

[trommlbomml]

The design of the code will probably change since I have to decouple the Entity Component System from collision objects for MonoGame.Extended

that's a good decision I think. Important for me is to use the separating axis theorem without the ECS as I have an own implementation.

My implementation was as concrete as the other collision methods in MonoGame by having an extra method for each collision pair solving the SAT.

Maybe we could find an implementation in the middle, where each shape provides it's axis in a dedicated struct which is solved by a method like yours provide.

[lithiumtoast]

With @janfokke we have a prototype in the works for this ticket recently. More news soon.