Monogame-Extended/source/MonoGame.Extended/Collisions/BoundingVolumeIntersection.cs

using System;
using System.Runtime.CompilerServices;
using Microsoft.Xna.Framework;

namespace MonoGame.Extended.Collisions;

/// <summary>
/// Provides intersection tests between bounding volume types.
/// </summary>
public static class BoundingVolumeIntersection
{
    #region Rectangle (AABB) Tests

    /// <summary>
    /// Tests if two axis-aligned bounding rectangles intersect.
    /// </summary>
    /// <param name="a">The first rectangle.</param>
    /// <param name="b">The second rectangle.</param>
    /// <returns><see langword="true"/> if the rectangle overlap; otherwise, <see langword="false"/>.</returns>
    /// <remarks>
    /// Tests for overlap on both X and Y axes independently.
    /// Exits early on first separating axis found.
    /// Based on section 4.2.1 (min-max representation).
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool Intersects(in BoundingRectangle a, in BoundingRectangle b)
    {
        // Exit with no intersection if separated along axis
        if (a.Max.X < b.Min.X || a.Min.X > b.Max.X) return false;
        if (a.Max.Y < b.Min.Y || a.Min.Y > b.Max.Y) return false;

        // Overlapping on all axes means AABBs are intersecting
        return true;
    }

    #endregion

    #region Circle Tests

    /// <summary>
    /// Tests if two circles intersect.
    /// </summary>
    /// <param name="a">The first circle.</param>
    /// <param name="b">The second circle.</param>
    /// <returns><see langword="true"/> if the circles overlap; otherwise, <see langword="false"/>.</returns>
    /// <remarks>
    /// Uses squared distance comparison to avoid expensive square root operation.
    /// Based on section 4.3.1
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool Intersects(in BoundingCircle a, in BoundingCircle b)
    {
        // Calculate squared distance between centers
        Vector2 d = a.Center - b.Center;
        float distSquared = d.X * d.X + d.Y * d.Y;

        // Sphere intersect if squared distance is less than squared sum of radii
        float radiusSum = a.Radius + b.Radius;
        return distSquared <= radiusSum * radiusSum;
    }

    #endregion

    #region Circle-Rectangle Tests

    /// <summary>
    /// Tests if a circle intersects an axis-aligned bounding rectangle.
    /// </summary>
    /// <param name="circle">The circle to test.</param>
    /// <param name="rect">The rectangle to test.</param>
    /// <returns><see langword="true"/> if the circle and rectangle overlap; otherwise, <see langword="false"/>.</returns>
    /// <remarks>
    /// Finds closest point on rectangle to circle center, then performs distance test.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool Intersects(in BoundingCircle circle, in BoundingRectangle rect)
    {
        // Find the closest point on the rectangle to the circle center
        float closestX = Math.Clamp(circle.Center.X, rect.Min.X, rect.Max.X);
        float closestY = Math.Clamp(circle.Center.Y, rect.Min.Y, rect.Max.Y);

        // Calculate squared distance from the circle center to closest point
        float dx = circle.Center.X - closestX;
        float dy = circle.Center.Y - closestY;
        float distSquared = dx * dx + dy * dy;

        // Circle intersects if distance to closest point is less than radius
        return distSquared <= circle.Radius * circle.Radius;
    }

    /// <summary>
    /// Tests if a rectangle intersects a circle.
    /// </summary>
    /// <param name="rect">The rectangle to test.</param>
    /// <param name="circle">The circle to test.</param>
    /// <returns><see langword="true"/> if the rectangle and circle overlap; otherwise, <see langword="false"/>.</returns>
    /// <remarks>
    /// Finds closest point on rectangle to circle center, then performs distance test.
    /// </remarks>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool Intersects(in BoundingRectangle rect, in BoundingCircle circle)
    {
        return Intersects(circle, rect);
    }

    #endregion

    #region Oriented Bounding Rectangle (OBB) Tests

    /// <summary>
    /// Tests if two oriented bounding rectangles intersect using Separating Axis Theorem.
    /// </summary>
    /// <param name="a">The first oriented bounding rectangle.</param>
    /// <param name="b">The second oriented bounding rectangle.</param>
    /// <returns><see langword="true"/> if the rectangles overlap; otherwise, <see langword="false"/>.</returns>
    /// <remarks>
    /// Uses Separating Axis Theorem (SAT). <br/>
    /// Tests 4 potential separating axes: the 2 local exes from each OBB. <br/>
    /// If volumes fail to overlap on any axis, they are not intersecting.
    /// </remarks>
    public static bool Intersects(in OrientedBoundingRectangle a, in OrientedBoundingRectangle b)
    {
        // Compute rotation matrix expressing b in a's coordinate frame.
        float r00 = Vector2.Dot(a.AxisX, b.AxisX);
        float r01 = Vector2.Dot(a.AxisX, b.AxisY);
        float r10 = Vector2.Dot(a.AxisY, b.AxisX);
        float r11 = Vector2.Dot(a.AxisY, b.AxisY);

        // Compute translation vector from a to b in a's coordinate frame.
        Vector2 t = b.Center - a.Center;
        float tx = Vector2.Dot(t, a.AxisX);
        float ty = Vector2.Dot(t, a.AxisY);

        // Compute common subexpressions
        // This handles near-parallel edges that produce near-zero cross products
        float ar00 = MathF.Abs(r00) + MathExtended.Epsilon;
        float ar01 = MathF.Abs(r01) + MathExtended.Epsilon;
        float ar10 = MathF.Abs(r10) + MathExtended.Epsilon;
        float ar11 = MathF.Abs(r11) + MathExtended.Epsilon;

        // Test separating axis L = A.AxisX
        float ra = a.HalfExtents.X;
        float rb = b.HalfExtents.X * ar00 + b.HalfExtents.Y * ar01;
        if (MathF.Abs(tx) > ra + rb)
        {
            return false;
        }

        // Test separating axis L = A.AxisY
        ra = a.HalfExtents.Y;
        rb = b.HalfExtents.X * ar10 + b.HalfExtents.Y * ar11;
        if (MathF.Abs(ty) > ra + rb)
        {
            return false;
        }

        // Test separating axis L = B.AxisX
        ra = a.HalfExtents.X * ar00 + a.HalfExtents.Y * ar10;
        rb = b.HalfExtents.X;
        if (MathF.Abs(tx * r00 + ty * r10) > ra + rb)
        {
            return false;
        }

        // Test separating axis L = B.AxisY
        ra = a.HalfExtents.X * ar01 + a.HalfExtents.Y * ar11;
        rb = b.HalfExtents.Y;
        if (MathF.Abs(tx * r01 + ty * r11) > ra + rb)
        {
            return false;
        }

        // No separating axis found, must be intersecting
        return true;
    }

    /// <summary>
    /// Tests if an oriented bounding rectangle intersects an axis-aligned rectangle.
    /// </summary>
    /// <param name="obb">The oriented bounding rectangle.</param>
    /// <param name="aabb">The axis-aligned rectangle.</param>
    /// <returns><see langword="true"/> if the rectangle overlap; otherwise, <see langword="false"/>.</returns>
    public static bool Intersects(in OrientedBoundingRectangle obb, in BoundingRectangle aabb)
    {
        OrientedBoundingRectangle aabbAsObb = OrientedBoundingRectangle.FromAxisAligned(aabb.Center, aabb.HalfExtents);
        return Intersects(obb, aabbAsObb);
    }

    /// <summary>
    /// Tests if an axis-aligned rectangle intersects an oriented bounding rectangle.
    /// </summary>
    /// <param name="aabb">The axis-aligned rectangle.</param>
    /// <param name="obb">The oriented bounding rectangle.</param>
    /// <returns><see langword="true"/> if the rectangles overlap; otherwise, <see langword="false"/>.</returns>
    public static bool Intersects(in BoundingRectangle aabb, in OrientedBoundingRectangle obb)
    {
        return Intersects(obb, aabb);
    }

    /// <summary>
    /// Tests if a circle intersects an oriented bounding rectangle.
    /// </summary>
    /// <param name="circle">The circle to test.</param>
    /// <param name="obb">The oriented bounding rectangle to test.</param>
    /// <returns><see langword="true"/> if the circle and rectangle overlap; otherwise, <see langword="false"/>.</returns>
    public static bool Intersects(in BoundingCircle circle, in OrientedBoundingRectangle obb)
    {
        // Find closest point on OBB to circle center
        Vector2 closest = GeometricPrimitives.ClosestPointOnOBB(obb, circle.Center);

        // Test if distance from circle center to closest point is less than radus
        float distSquared = GeometricPrimitives.DistanceSquared(circle.Center, closest);
        return distSquared <= circle.Radius * circle.Radius;
    }

    /// <summary>
    /// Tests if an oriented bounding rectangle intersects a circle.
    /// </summary>
    /// <param name="obb">The oriented bounding rectangle.</param>
    /// <param name="circle">The circle to test.</param>
    /// <returns><see langword="true"/> if the rectangle and circle overlap; otherwise, <see langword="false"/>.</returns>
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool Intersects(in OrientedBoundingRectangle obb, in BoundingCircle circle)
    {
        return Intersects(circle, obb);
    }

    #endregion

    #region Point Containment Tests

    /// <summary>
    /// Tests if a point is contained within an axis-aligned rectangle.
    /// </summary>
    /// <param name="rect">The rectangle to test.</param>
    /// <param name="point">The point to test.</param>
    /// <returns><see langword="true"/> if the point is inside or on the boundary, otherwise, <see langword="false"/>.</returns>
    public static bool Contains(in BoundingRectangle rect, Vector2 point)
    {
        return point.X >= rect.Min.X && point.X <= rect.Max.X &&
               point.Y >= rect.Min.Y && point.Y <= rect.Max.Y;
    }

    /// <summary>
    /// Tests if a point is contained within a circle.
    /// </summary>
    /// <param name="circle">The circle to test.</param>
    /// <param name="point">The point to test.</param>
    /// <returns><see langword="true"/> if the point is inside or on the boundary; otherwise, <see langword="false"/>.</returns>
    /// <remarks>
    /// uses squared distance to avoid square root operation.
    /// </remarks>
    public static bool Contains(in BoundingCircle circle, Vector2 point)
    {
        Vector2 d = point - circle.Center;
        float distSquared = d.X * d.X + d.Y * d.Y;
        return distSquared <= circle.Radius * circle.Radius;
    }

    /// <summary>
    /// Tests if a point is contained within an oriented bounding rectangle.
    /// </summary>
    /// <param name="obb">The oriented bounding rectangle.</param>
    /// <param name="point">The point to test.</param>
    /// <returns><see langword="true"/> if the point is inside or on the boundary; otherwise, <see langword="false"/>.</returns>
    public static bool Contains(in OrientedBoundingRectangle obb, Vector2 point)
    {
        // Transform point into OBB's local coordinate system
        Vector2 d = point - obb.Center;
        float distX = Vector2.Dot(d, obb.AxisX);
        float distY = Vector2.Dot(d, obb.AxisY);

        // Test against half-extents
        return MathF.Abs(distX) <= obb.HalfExtents.X + MathExtended.Epsilon
               && MathF.Abs(distY) <= obb.HalfExtents.Y + MathExtended.Epsilon;
    }

    #endregion


}