[C#, Unity3D] An optimized solver for intersection between a Line Segment and a Rect in 2D space with spacial partitioning.

2DLineRectIntersection.md

Overview

For a 2D Unity Project, I needed a really efficient way to get the intersection points between a line segment (as defined by two Vector2) and an axis-aligned Rect in 2D space, where the intersection points are returned as a parametric fraction of the length of the original line segment:

Note how when the line intersects the rect, the green line represents the portion inside the rect, and the parametric representation of the point of intersection along the line is displayed

In my use case the vast majority of lines are either completely inside or completely outside the rect, and so I needed an approach that was very efficient in cases where there is guaranteed no intersection and avoids unecessary raycasts when possible.

I also needed both the point of entry and point of exit.

Approach

We spacially partition the area around a rect into sectors, and given what sectors the line segment starts and ends in, we can can use a pre-computed lookup table to know what edges of the Rect should be raycast.

This minimizes the actual raycasts preformed significantly and is very efficient in cases where line segments are often completely inside or compltely outside the rect.

Details

We divide the Rect into the following sectors:

S0| S1 |S2
--+----+--
S3| S4 |S5
--+----+--
S6| S7 |S8

Where S4 is the Rect itself.

Given the sectors of the start and end point of a line segment, and whether we are checking for entering or exiting the Rect, we know what Raycasts could possibly need to be performed.

For example:

• From Sector 0 to Sector 1
  • Enter/Exit: Can never hit the rect
  • Result: 0 raycasts.
• From Sector 4 to Sector 7:
  • Enter: Already inside the rect
  • Exit: Can only hit edge S7
  • Result: 1 raycast.
• From Sector 6 to Sector 5
  • Enter: Can hit either edge S3 or S7
  • Exit: Can only hit edge S5
  • Result: 2 or 3 raycasts.

The necessary raycasts for all possible permutations of (1)Start Sector, (2)End Sector and (3)if we are checking for entering or exiting the rect are pre-computed in a static lookup table of 9 * 9 * 2 = 162 elements, which I have done offline.

That means at runtime, we determine the Sector of the start and end point, then perform only the raycasts necessary for entering and exiting the rect as determined by the lookup table. Since raycasting the sides of the Rect is the most computationally intensive part, this small bit of pre-processing saves time overall, especially in use cases where lots of line segments are tested but the majority are either completely inside or completely outside of the Rect.

The raycasts between the line segment and the sides of the Rect are also optimized to either solve for a horizontal or a vertical side intersection, since the sides of the rect are always axis aligned.

---

Notes

• This approach is specifically optimized for cases where the majority of line segments tested don't intersect with the Rect, and either lie completely inside or completely outside. If intersections were much more common then a brute force approach of testing the 4 sides until 2 hits are found might be marginally faster.
• If you only need the point of entry you could modify the lookup table to only store that, and simply return after that first raycast pass.
• This approach returns the parametric representation of the intersection and not a specific point. That is because in my use-case I actually don't need the point, but rather the fraction along the line where it intersects, which I then use in further calculations. It also makes handling non-intersections easier.
• While I did some preliminary benchmarking during testing I don't feel it's extensive enough to warrant including here. Benchmarking was performed against the approach listed here https://stackoverflow.com/a/38944633/928062 which only returns the entry point.

References

• https://ncase.me/sight-and-light/ : 2D Lighting tutorial that does a good job of explaining how to derive the parametric equation for line intersections.
  • Note that their final T1 = ... formula can divide by zero. See the issue here: ncase/sight-and-light#3

LineRectDemo.cs

using UnityEngine;
using UnityEditor;
using Raycast2DUtils;

// For in-editor testing only, so place in an 'Editor' folder
public class LineRectDemo : MonoBehaviour
{
    public GameObject obj1;
    public Vector3 Pos1 { get { return obj1.transform.position; } }

    public GameObject obj2;
    public Vector3 Pos2 { get { return obj2.transform.position; } }

    public Rect Rect2D
    {
        get
        {
            var width = transform.localScale.x;
            var height = transform.localScale.y;
            var xmin = transform.position.x - width / 2;
            var ymin = transform.position.y - height / 2;
            return new Rect(xmin, ymin, width, height);
        }
    }

    private void OnDrawGizmos()
    {
        if (obj1 == null || obj2 == null)
        {
            Debug.LogWarning("Obj1 and obj2 need to be set");
            return;
        }

        Gizmos.color = new Color(1, 0.5f, 0);
        DrawRect(Rect2D);

        Raycast2DLineRect.LineRectResult result = new Raycast2DLineRect.LineRectResult();
        Raycast2DLineRect.RaycastLineRect(Pos1, Pos2, Rect2D, ref result);

        Gizmos.color = result.HaveHit ? Color.red : Color.white;
        Gizmos.DrawLine(Pos1, Pos2);

        if (result.HaveHit)
        {
            Vector3 dir = Pos2 - Pos1;
            Vector3 entry = Pos1 + dir * result.t_entry;
            Vector3 exit  = Pos1 + dir * result.t_exit;

            Gizmos.color = Color.green;
            Gizmos.DrawLine(entry, exit);

            Handles.Label(entry, result.t_entry.ToString());
            Handles.Label(exit, result.t_exit.ToString());
        }

        Gizmos.color = Color.cyan;
        Gizmos.DrawWireSphere(Pos1, 0.05f);
        Gizmos.DrawWireSphere(Pos2, 0.05f);
    }

    static void DrawRect(Rect rect)
    {
        Vector3 topLeft = new Vector3(rect.xMin, rect.yMax, 0);
        Vector3 bottomRight = new Vector3(rect.xMax, rect.yMin, 0);

        Gizmos.DrawLine(rect.min, topLeft);
        Gizmos.DrawLine(rect.min, bottomRight);
        Gizmos.DrawLine(rect.max, topLeft);
        Gizmos.DrawLine(rect.max, bottomRight);
    }
}

Raycast2DLineRect.cs

using UnityEngine;

namespace Raycast2DUtils
{
    /// <summary>
    /// Find the 0, 1 or 2 intersections between a line segment and an axis-aligned Rect.
    /// </summary>
    /// Uses spacial partitioning around the rect to perform the bare minimum raycasts necessary.
    ///
    /// Written by JohannesMP 2018-07-07, released under the Public Domain - No Rights Reserved.
    ///
    public static class Raycast2DLineRect
    {
        /// <summary>
        /// Fraction of the line segment where it enters and exits the rect.
        /// </summary>
        public struct LineRectResult
        {
            /// <summary>
            /// The fraction along the line segment where it entered the rect.
            /// 0 if starting inside the rect.
            /// float.PositiveInfinity if no hits (entry or exit).
            /// </summary>
            public float t_entry;
            /// <summary>
            /// The fraction along the line segment where it exited the rect.
            /// 1 if ending inside the rect.
            /// float.PositiveInfinity if no hits (entry or exit).
            /// </summary>
            public float t_exit;

            public bool HaveHit { get { return t_entry != float.PositiveInfinity; } }
            public override string ToString() { return string.Format("t_entry={0}, t_exit={1}", t_entry, t_exit); }
        }

        /// <summary>
        /// Sectors around a rect
        /// </summary>
        /// Given a rectangle we divide the space around it into the following Sectors (S4 is the rectangle itself):
        ///      S0| S1 |S2
        ///      --+----+--
        ///      S3| S4 |S5
        ///      --+----+--
        ///      S6| S7 |S8
        ///
        /// Note that Sector enums are also used to identify the Side or Corner of the rectangle bordered by a sector
        enum Sector
        {
            __, // No sector - underscore used to make viewing RaycastLookup below easier
            S0, S1, S2,
            S3, S4, S5,
            S6, S7, S8
        }

        /// <summary>
        /// What raycasts to perform for the sectors a line segment ends and starts in, and whether it is entering or exiting.
        /// </summary>
        /// This pre-computed lookup tables enables us to avoid unnecessary raycasts.
        /// 
        /// Lookup is done as follows: [Sector1, Sector2, state(0:1)]
        ///     - state == 0: the line segment is entering the Rect
        ///     - state == 1: the line segment is exiting the Rect
        ///
        /// - If the result is Sector.__ a raycast would not return anything.
        /// - Otherwise the return enum indicates which Edge(s) should be raycast
        ///     - ex: S0 means that the edges that create the corner at sector 0 should be raycast, meaning Edge 1 and Edge 3.
        ///
        /// Examples: 
        ///     RaycastLookup[1,4,0] == S1
        ///         - A line segment from Sector 1 to 4 enters the rect at Edge 1
        ///     RaycastLookup[1,4,1] == __
        ///         - A line segment from Sector 1 to 4 does not exit the rect
        ///         
        ///     RaycastLookup[0,5,0] == S0
        ///         - A line segment from Sector 0 to 5 enters the rect at the Edges touching corner 0 (Edge 1 and Edge 3)
        ///     RaycastLookup[0,5,1] == S5
        ///         - A line segment from Sector 0 to 5 exits the rect at Edge 5
        static readonly Sector[,,] RaycastLookup =
        {
            // From 0 - top left corner
            {
                {Sector.__, Sector.__},     {Sector.__, Sector.__},     {Sector.__, Sector.__},
                {Sector.__, Sector.__},     {Sector.S0, Sector.S4},     {Sector.S0, Sector.S5},
                {Sector.__, Sector.__},     {Sector.S0, Sector.S7},     {Sector.S0, Sector.S8},
            },
            // From 1 - top edge
            {
                {Sector.__, Sector.__},     {Sector.__, Sector.__},     {Sector.__, Sector.__},
                {Sector.S1, Sector.S3},     {Sector.S1, Sector.S4},     {Sector.S1, Sector.S5},
                {Sector.S1, Sector.S6},     {Sector.S1, Sector.S7},     {Sector.S1, Sector.S8},
            },
            // From 2 - top right corner
            {
                {Sector.__, Sector.__},     {Sector.__, Sector.__},     {Sector.__, Sector.__},
                {Sector.S2, Sector.S3},     {Sector.S2, Sector.S4},     {Sector.__, Sector.__},
                {Sector.S2, Sector.S6},     {Sector.S2, Sector.S7},     {Sector.__, Sector.__},
            },
            // From 3 - left edge
            {
                {Sector.__, Sector.__},     {Sector.S3, Sector.S1},     {Sector.S3, Sector.S2},
                {Sector.__, Sector.__},     {Sector.S3, Sector.S4},     {Sector.S3, Sector.S5},
                {Sector.__, Sector.__},     {Sector.S3, Sector.S7},     {Sector.S3, Sector.S8},
            },
            // From 4 - center; no entry, only exit
            {
                {Sector.S4, Sector.S0},     {Sector.S4, Sector.S1},     {Sector.S4, Sector.S2},
                {Sector.S4, Sector.S3},     {Sector.S4, Sector.S4},     {Sector.S4, Sector.S5},
                {Sector.S4, Sector.S6},     {Sector.S4, Sector.S7},     {Sector.S4, Sector.S8},
            },
            // From 5 - right edge
            {
                {Sector.S5, Sector.S0},     {Sector.S5, Sector.S1},     {Sector.__, Sector.__},
                {Sector.S5, Sector.S3},     {Sector.S5, Sector.S4},     {Sector.__, Sector.__},
                {Sector.S5, Sector.S6},     {Sector.S5, Sector.S7},     {Sector.__, Sector.__},
            },
            // From 6 - bottom left corner
            {
                {Sector.__, Sector.__},     {Sector.S6, Sector.S1},     {Sector.S6, Sector.S2},
                {Sector.__, Sector.__},     {Sector.S6, Sector.S4},     {Sector.S6, Sector.S5},
                {Sector.__, Sector.__},     {Sector.__, Sector.__},     {Sector.__, Sector.__},
            },
            // From 7 - bottom edge
            {
                {Sector.S7, Sector.S0},     {Sector.S7, Sector.S1},     {Sector.S7, Sector.S2},
                {Sector.S7, Sector.S3},     {Sector.S7, Sector.S4},     {Sector.S7, Sector.S5},
                {Sector.__, Sector.__},     {Sector.__, Sector.__},     {Sector.__, Sector.__},
            },
            // From 8 - bottom right corner
            {
                {Sector.S8, Sector.S0},   {Sector.S8, Sector.S1},   {Sector.__, Sector.__},
                {Sector.S8, Sector.S3},   {Sector.S8, Sector.S4},   {Sector.__, Sector.__},
                {Sector.__, Sector.__},   {Sector.__, Sector.__},   {Sector.__, Sector.__},
            },
        };

        /// <summary>
        /// Find intersects of a Line segment and an axis-aligned Rect
        /// </summary>
        public static void RaycastLineRect(Vector2 begin, Vector2 end, Rect rect, ref LineRectResult res)
        {
            Vector3 dir = end - begin;

            int sectorBegin = GetRectPointSector(rect, begin);
            int sectorEnd   = GetRectPointSector(rect, end);

            res.t_entry = GetRayToRectSide(begin, dir, RaycastLookup[sectorBegin, sectorEnd, 0], rect, 0f);
            res.t_exit  = GetRayToRectSide(begin, dir, RaycastLookup[sectorBegin, sectorEnd, 1], rect, 1f);
        }

        /// <summary>
        /// Check in which sector relative to a rect a point is located in.
        /// </summary>
        /// 
        /// Return value maps to the rect as follows, where 4 is inclusive:
        ///     0| 1 |2     
        ///     -+---+-   ^
        ///     3| 4 |5   |
        ///     -+---+-   y
        ///     6| 7 |8    x-->
        /// 
        /// <returns>The sector relative to the rect that the point is in</returns>
        private static int GetRectPointSector(Rect rect, Vector2 point)
        { 
            // 0, 1 or 2
            if(point.y > rect.yMax)
            {
                if      (point.x < rect.xMin) return 0;
                else if (point.x > rect.xMax) return 2;
                return 1;
            }
            // 6, 7, or 8
            else if(point.y < rect.yMin)
            {
                if      (point.x < rect.xMin) return 6;
                else if (point.x > rect.xMax) return 8;
                return 7;
            }
            // 3, 4 or 5
            else
            {
                if      (point.x < rect.xMin) return 3;
                else if (point.x > rect.xMax) return 5;
                return 4;
            }
        }

        /// <summary>
        /// Perform the raycast on an edge or two edges on a corner of a rect.
        /// </summary>
        /// Edges are a guaranteed single raycast
        /// Corners consist of two edges to raycast. if the first is a miss, return the second.
        /// 
        /// <param name="side">The Direction(s) of the rect to raycast against</param>
        /// <param name="r4val">The intersect value to return for when we start or stop in the rect</param>
        /// <returns>The fraction along the ray</returns>
        private static float GetRayToRectSide(Vector2 begin, Vector2 dir, Sector side, Rect rect, float r4val)
        {
            float curFrac;
            switch (side)
            {
                // Raycast Corner S0 - consists of S1 and S3
                case Sector.S0:
                    curFrac = GetRayToRectSide(begin, dir, Sector.S1, rect, r4val);
                    return (curFrac == float.PositiveInfinity) ? GetRayToRectSide(begin, dir, Sector.S3, rect, r4val) : curFrac;

                // Raycast Edge S1 - Horizontal
                case Sector.S1: return RayToHoriz(begin, dir, rect.xMin, rect.yMax, rect.width);

                // Raycast Corner S2 - consists of S1 and S5
                case Sector.S2:
                    curFrac = GetRayToRectSide(begin, dir, Sector.S1, rect, r4val);
                    return (curFrac == float.PositiveInfinity) ? GetRayToRectSide(begin, dir, Sector.S5, rect, r4val) : curFrac;

                // Raycast Edge S3 - Vertical
                case Sector.S3: return RayToVert(begin, dir, rect.xMin, rect.yMin, rect.height);

                // Center S4 - return the intersection value provided by caller
                case Sector.S4: return r4val;

                // Raycast Edge S5 - Vertical
                case Sector.S5: return RayToVert(begin, dir, rect.xMax, rect.yMin, rect.height);

                // Raycast Corner S6 - consists of S3 and S7
                case Sector.S6:
                    curFrac = GetRayToRectSide(begin, dir, Sector.S3, rect, r4val);
                    return (curFrac == float.PositiveInfinity) ? GetRayToRectSide(begin, dir, Sector.S7, rect, r4val) : curFrac;

                // Raycast Edge S7 - Horizontal
                case Sector.S7: return RayToHoriz(begin, dir, rect.xMin, rect.yMin, rect.width);

                // Raycast Corner S8 - consists of S5 and S7
                case Sector.S8:
                    curFrac = GetRayToRectSide(begin, dir, Sector.S5, rect, r4val);
                    return (curFrac == float.PositiveInfinity) ? GetRayToRectSide(begin, dir, Sector.S7, rect,  r4val) : curFrac;

                // No Intersection
                default: return float.PositiveInfinity;
            }
        }

        /// <summary>
        /// Check if a given line segment and a strictly Horizontal line segment intersect. float.PositiveInfinity if no hit.
        /// </summary>
        /// /// <param name="width">The width of the horizontal line segment. Is Assumed non-zero.</param>
        /// <returns>The parametric fraction where the intersection lies on the 'from' segment. float.PositiveInfinity if no intersection</returns>
        private static float RayToHoriz(Vector2 fromPoint, Vector2 fromDir, float x, float y, float width)
        {
            // 1. Check if the extended horizontal line could intersect the segment
            float fromParam = (y - fromPoint.y) / fromDir.y;
            if (fromParam < 0 || fromParam > 1)
                return float.PositiveInfinity;
            // 2. Check if the horizontal line could reach the segment
            float lineParam = (fromPoint.x + fromDir.x * fromParam - x) / width;
            if (lineParam < 0 || lineParam > 1)
                return float.PositiveInfinity;
            return fromParam;
        }

        /// <summary>
        /// If a given line segment and a strictly Vertical line segment intersect. float.PositiveInfinity if no intersection.
        /// </summary>
        /// <param name="height">The height of the vertical line segment. Is Assumed non-zero.</param>
        /// <returns>The parametric fraction where the intersection lies on the 'from' segment. float.PositiveInfinity if no intersection</returns>
        private static float RayToVert(Vector2 fromPoint, Vector2 fromDir, float x, float y, float height)
        {
            float fromParam = (x - fromPoint.x) / fromDir.x;
            // 1. Check if the extended vertical line could intersect the segment
            if (fromParam < 0 || fromParam > 1)
                return float.PositiveInfinity;
            // 2. Check if the vertical line could reach the segment
            float lineParam = (fromPoint.y + fromDir.y * fromParam - y) / height;
            if (lineParam < 0 || lineParam > 1)
                return float.PositiveInfinity;
            return fromParam;
        }

        /// <summary>
        /// Check if a given 'from' line segment and a 'to' line segment intersect. float.PositiveInfinity if no intersection.
        /// </summary>
        /// Just for reference - RayToHoriz and RayToVert are specialized versions of this.
        /// <returns>The parametric fraction where the intersection lies on the 'from' segment. float.PositiveInfinity if no intersection</returns>
        private static float RayToRay(Vector2 fromPoint, Vector2 fromDir, Vector2 toPoint, Vector2 toDir)
        {
            // 1. Check where the extended 'to' line segment would intersect the 'from' line segment.
            float fromParam = (toDir.x * (fromPoint.y - toPoint.y) + toDir.y * (toPoint.x - fromPoint.x)) / (fromDir.x * toDir.y - fromDir.y * toDir.x);
            if (fromParam < 0 || fromParam > 1)
                return float.PositiveInfinity;

            // 2. Now check if the extended 'from' line segment would intersect the 'to' line segment.
            float toParam = (fromDir.x * (toPoint.y - fromPoint.y) + fromDir.y * (fromPoint.x - toPoint.x)) / (toDir.x * fromDir.y - toDir.y * fromDir.x);
            if (toParam < 0 || toParam > 1)
                return float.PositiveInfinity;

            return fromParam;
        }
    }
}

Good stuff, really well done!