Ray/Polygon Intersections

Raycasting is a particularly useful functionality in games, allowing you to do things such as cast beams of light and trace bullet paths. In this opening blog post, we'll look at how to deal with casting a ray into 2D space and calculating where it intersects a primitive object.

In 3D space this would be performed by constructing a plane, typically facing the ray origin, and testing if the ray intersects this plane. If an intersection is detected then a check is performed to see if the point is inside the polygon. Further calculations would then be made to find the exact point of intersection.

In 2D however, a much simpler approach would be to simply perform ray/line intersection tests for each side of the polygon. The algorithm could be optimised for first-intersection tests by only checking the segments on the half of the polygon closest to the ray origin. For the purposes of simplicity though, the approach I'm going to demonstrate simply tests all of the segments, as the number of vertices I will be dealing with are very small.

Ray/Line Intersection

The first step is the ray/line intersection test. XNA does possess a Ray structure, but this is more designed for 3D space and contains a lot of superfluous data and methods. As such, we'll represent a ray by simply passing two vectors, one representing the origin and the other representing the direction. As well as detecting whether we have an intersection, we will also want to detect where along the ray the intersection is using a float out argument.

Lines 4-13 eliminate the case where both lines are parallel, as this is not as straight-forward to deal with and would likely be intersecting another side of the polygon anyway. We construct a vector representing the segment from the start to end. If the dot product of the ray direction and the left perpendicular of the line segment is less than 0, then the lines are parallel and we can return false.

Lines 15-18 then deal with the more complex task of determining where an intersection would take place. This is done by taking the vector connecting the ray's origin and a point on the line, which we will call d, and dividing the dot product of this and the line segment by the previously calculated perpendicular/ray dot product. This gives us t, our depth of intersection on the ray. The variable s is the depth of intersection on the line segment. This is calculated by dividing the dot product of the right perpendicular of the line segment and vector d by the perpendicular/ray dot product.

Both s and t are scalars for the direction vectors. As such, if s is less than 0 or greater than 1 then the intersection point cannot be on the line segment, as it is futher away (or in the opposite direction in the case of values less than 0) than the segment connecting the two points. Likewise, t must be greater than 0 to indicate that the intersection is not in the opposite direction of the ray.

public static bool RayLineIntersect(Vector2 ro, Vector2 rd,
    Vector2 l1, Vector2 l2, out float t)
{
    Vector2 seg = l2 - l1;
    Vector2 segPerp = new Vector2(seg.Y, -seg.X);
    float perpDotd = Vector2.Dot(rd, segPerp);

    // If lines are parallel, return false.
    if (Math.Abs(perpDotd) <= float.Epsilon)
    {
        t = float.MaxValue;
        return false;
    }

    Vector2 d = l1 - ro;

    t = Vector2.Dot(segPerp, d) / perpDotd;
    float s = Vector2.Dot(new Vector2(rd.Y, -rd.X), d) / perpDotd;

    // If intersect is in right direction and in segment bounds, return true.
    return t >= 0.0f && s >= 0.0f && s <= 1.0f;  
}

Ray/Polygon Intersection

Now that we have the method for calculating whether a ray intersects a single line segment, we can determine if there is an intersection on a polygon by looping through each of the segments connecting the vertices. Of course at this stage we also need to calculate some additional information which would be useful when resolving collisions.

Lines 17-20 deal with where the ray first intersects the polygon, as this would be useful for tasks such as creating bullet impacts. This is done by comparing the t value from each of the line intersection tests at each positive test and continually storing the smallest value (the closest to the origin). A point of intersection can also be updated by simply taking the ray origin and adding the scaled ray direction segment to it.

Lines 22-23 then calculate the normal to the first intersecting edge, as this would be useful for physical projectiles such as grenades, which may bounce off obstacles. This is simply a case of taking the segment connecting the current vertices and storing the perpendicular.

public static bool RayPolygonIntersect(Vector2 ro, Vector2 rd,
    Vector2[] polygon, out float t, out Vector2 point, out Vector2 normal)
{
    t = float.MaxValue;
    point = ro;
    normal = rd;>

    // Comparison variables.
    float distance;
    int crossings = 0;

    for (int j = polygon.Length - 1, i = 0; i < polygon.Length; j = i, i++)
    {
        if (RayLineIntersect(ro, rd, polygon[j], polygon[i], out distance))
        {
            crossings++;

            // If new intersection is closer, update variables.
            if (distance < t)
            {
                t = distance;
                point = ro + (rd * t);

                Vector2 edge = polygon[j] - polygon[i];
                normal = Vector2.Normalize(new Vector2(-edge.Y, edge.X));
            }
        }
    }

    return crossings > 0 && crossings % 2 == 0;  
}

If the number of crossings occurred is above zero and perfectly divisible by 2 (i.e. the ray origin is outside the polygon) then we know we have an intersection. The GIF below demonstrates a quick sample I constructed using these two methods. The normal data has been omitted, however the point of intersection (and by extension the depth t) is visible as the small maroon square appearing on the surface of the octagon.

The concepts discussed are a slight modification of those found in the following blogpost: http://afloatingpoint.blogspot.co.uk/2011/04/2d-polygon-raycasting.html